第二章-進程線程管理課件

第二章進程線程管理第二章進程線程管理第二章進程線程管理第二章進程線程管理第二章進程線程管理第二章進程線程管理1第二章進程(線程)管理第二章進程(線程)管理2本章內(nèi)容2.1進程的基本概念2.2進程控制2.3進程同步2.4進程通信2.5線程本章內(nèi)容2.1進程的基本概念32.1進程的基本概念2.1.1程序執(zhí)行過程1．前趨圖2.1進程的基本概念2.1.1程序執(zhí)行過程42.1進程的基本概念2．順序執(zhí)行及其特征

程序順序執(zhí)行具有如下特征。（1）順序性。處理機的操作嚴格按照程序所規(guī)定的順序執(zhí)行,每一操作必須在上一操作結(jié)束之后才能開始。（2）封閉性。程序在封閉環(huán)境下運行，獨占系統(tǒng)所有資源。即程序一旦開始運行，其執(zhí)行結(jié)果不受其它程序和外界因素影響。（3）可再現(xiàn)性。只要程序執(zhí)行時的初始條件和執(zhí)行環(huán)境相同,程序重復(fù)執(zhí)行時獲得完全相同結(jié)果。2.1進程的基本概念2．順序執(zhí)行及其特征程序順序執(zhí)行具有如下52.1進程的基本概念3．并發(fā)執(zhí)行及其特征

2.1進程的基本概念3．并發(fā)執(zhí)行及其特征62.1進程的基本概念

并發(fā)執(zhí)行的多個程序的特征：（1）間斷性。程序在執(zhí)行過程中，由于等待資源或及其它程序協(xié)作完成任務(wù)，每個程序的執(zhí)行過程往往不是“一氣呵成”，而是呈現(xiàn)出“執(zhí)行－暫停－執(zhí)行”的間斷性活動規(guī)律。（2）失去封閉性。程序并發(fā)執(zhí)行時,多個程序共享系統(tǒng)資源,系統(tǒng)資源的狀態(tài)將由多個程序改變。即一個程序在運行時，其運行環(huán)境會受其它程序的影響，失去了順序執(zhí)行的封閉性。2.1進程的基本概念并發(fā)執(zhí)行的多個程序的特征：72.1進程的基本概念

（3）相互作用和制約性。并發(fā)執(zhí)行程序既有相互獨立的一面，表現(xiàn)為每個程序為用戶提供特定的功能，它們之間相互獨立；也有時也會直接或間接制約的一面。（4）不可再現(xiàn)性。程序并發(fā)執(zhí)行時,由于失去了封閉性,導(dǎo)致其失去可再現(xiàn)性。即使初始條件相同，程序多次執(zhí)行的結(jié)果也可能不同。2.1進程的基本概念（3）相互作用和制約性。并發(fā)執(zhí)行程序82.1進程的基本概念例1：有兩個循環(huán)程序A和B，它們共享一個變量N。程序A每執(zhí)行一次時，都要做N∶=N+1操作；程序B每執(zhí)行一次時，都要執(zhí)行Print(N)操作，然后再將N置成“0”。程序A和B以不同的速度運行。

(1)N∶=N+1在Print(N)和N∶=0之前，此時得到的N值分別為n+1,n+1,0。

(2)N∶=N+1在Print(N)和N∶=0之后，此時得到的N值分別為n,0,1。

(3)N∶=N+1在Print(N)和N∶=0之間，此時得到的N值分別為n,n+1,0。2.1進程的基本概念例1：有兩個循環(huán)程序A和B，它們共享一92.1進程的基本概念例2：假設(shè)某飛機定票系統(tǒng)在t0時刻有A、B、C、D四個終端程序同時都要對機票庫中的某航班當(dāng)前剩余票數(shù)X進行操作。如果每個終端程序的當(dāng)前定票需求為N，并對共享變量X進行如下操作：在機票數(shù)據(jù)庫中取出當(dāng)前剩余票數(shù)X；判斷X>0（有票嗎）？如果有，X≥N（票夠嗎）？如果夠，則出票（打印票據(jù)）；X＝X－N（修改剩余票數(shù)）；將X回寫到數(shù)據(jù)庫中；2.1進程的基本概念例2：假設(shè)某飛機定票系統(tǒng)在t0時刻有A102.1.2進程的定義和特征

1.為何引入進程從程序并發(fā)執(zhí)行角度和系統(tǒng)資源共享角度分析一下引入進程的必要性。（1）程序并發(fā)執(zhí)行角度（2）系統(tǒng)資源共享角度2.1.2進程的定義和特征1.為何引入進程112.1.2進程的定義和特征

2.進程的定義進程是一個可并發(fā)執(zhí)行的具有獨立功能的程序在某個數(shù)據(jù)集合的一次執(zhí)行過程，它也是操作系統(tǒng)進行資源分配和保護的基本單位。為了更好的描述和管理并發(fā)執(zhí)行的多個進程，操作系統(tǒng)中為每個進程配置了一個進程控制塊PCB（ProcessControlBlock）。2.1.2進程的定義和特征2.進程的定義122.1.2進程的定義和特征

3.進程的構(gòu)成進程包括程序，數(shù)據(jù)和PCB2.1.2進程的定義和特征3.進程的構(gòu)成132.1.2進程的定義和特征

4.進程的上下文進程的物理實體和支持進程運行的環(huán)境合稱為進程上下文（ProcessContext）。進程在進程上下文中執(zhí)行。進程上下文包括用戶級上下文、系統(tǒng)級上下文和寄存器上下文。當(dāng)一個進程被系統(tǒng)調(diào)度而占用處理機時，發(fā)生進程切換，切換的內(nèi)容主要是進程上下文。2.1.2進程的定義和特征4.進程的上下文142.1.2進程的定義和特征

5.進程的特征進程具有如下特征：（1）動態(tài)性（2）共享性（3）并發(fā)性（4）獨立性（5）異步性 2.1.2進程的定義和特征5.進程的特征152.1.2進程的定義和特征6.進程和程序的區(qū)別①進程和程序的最大區(qū)別就是進程是程序的一次執(zhí)行過程，它是一個動態(tài)概念。程序是一個靜態(tài)概念。②進程能夠并發(fā)執(zhí)行。③進程是資源分配和獨立運行的基本單位，而程序不是。④進程由含有代碼和數(shù)據(jù)的用戶地址空間、進程控制塊和執(zhí)行棧區(qū)等部分組成，而程序只是靜態(tài)代碼。⑤進程和程序之間是多對多的關(guān)系。一個程序可被多個進程共用，一個進程在其活動中又可調(diào)用若干個程序。2.1.2進程的定義和特征6.進程和程序的區(qū)別162.1.3進程狀態(tài)和進程轉(zhuǎn)換1.進程的3種基本狀態(tài)進程執(zhí)行時的間斷性決定了進程可能具有多種狀態(tài)。事實上，運行中的進程可能具有以下三種基本狀態(tài)。2.1.3進程狀態(tài)和進程轉(zhuǎn)換1.進程的3種基本狀態(tài)172.1.3進程狀態(tài)和進程轉(zhuǎn)換1)就緒(Ready)狀態(tài)當(dāng)進程已分配到除CPU以外的所有必要資源后，只要再獲得CPU，便可立即執(zhí)行，進程這時的狀態(tài)稱為就緒狀態(tài)。在一個系統(tǒng)中處于就緒狀態(tài)的進程可能有多個，通常將它們排成一個隊列，稱為就緒隊列。2)執(zhí)行狀態(tài)進程已獲得CPU，其程序正在執(zhí)行。在單處理機系統(tǒng)中，只有一個進程處于執(zhí)行狀態(tài)；在多處理機系統(tǒng)中，則有多個進程處于執(zhí)行狀態(tài)。2.1.3進程狀態(tài)和進程轉(zhuǎn)換1)就緒(Ready)狀態(tài)182.1.3進程狀態(tài)和進程轉(zhuǎn)換3)阻塞狀態(tài)正在執(zhí)行的進程由于發(fā)生某事件而暫時無法繼續(xù)執(zhí)行時，便放棄處理機而處于暫停狀態(tài)，亦即進程的執(zhí)行受到阻塞，把這種暫停狀態(tài)稱為阻塞狀態(tài)，有時也稱為等待狀態(tài)或封鎖狀態(tài)。致使進程阻塞的典型事件有：請求I/O，申請緩沖空間等。通常將這種處于阻塞狀態(tài)的進程也排成一個隊列。有的系統(tǒng)則根據(jù)阻塞原因的不同而把處于阻塞狀態(tài)的進程排成多個隊列。2.1.3進程狀態(tài)和進程轉(zhuǎn)換3)阻塞狀態(tài)192.1.3進程狀態(tài)和進程轉(zhuǎn)換執(zhí)行就緒阻塞時間片到進程調(diào)度I/O請求I/O完成2.1.3進程狀態(tài)和進程轉(zhuǎn)換執(zhí)行就緒阻塞時202.1.3進程狀態(tài)和進程轉(zhuǎn)換2.創(chuàng)建和終止?fàn)顟B(tài)

2.1.3進程狀態(tài)和進程轉(zhuǎn)換2.創(chuàng)建和終止?fàn)顟B(tài)212.1.3進程狀態(tài)和進程轉(zhuǎn)換3.掛起1)引入掛起的原因在不少系統(tǒng)中進程只有上述三種狀態(tài)，但在另一些系統(tǒng)中，又增加了一些新狀態(tài)，最重要的是掛起狀態(tài)。引入掛起狀態(tài)的原因有：(1)終端用戶的請求(2)父進程請求(3)負荷調(diào)節(jié)的需要(4)操作系統(tǒng)的需要2.1.3進程狀態(tài)和進程轉(zhuǎn)換3.掛起222.1.3進程狀態(tài)和進程轉(zhuǎn)換2)進程狀態(tài)的轉(zhuǎn)換在引入掛起狀態(tài)后，又將增加從掛起狀態(tài)(又稱為靜止?fàn)顟B(tài))到非掛起狀態(tài)(又稱為活動狀態(tài))的轉(zhuǎn)換；或者相反。此時把狀態(tài)細分為：運行態(tài)活動就緒、靜止就緒活動阻塞、靜止阻塞可有以下幾種狀態(tài)轉(zhuǎn)換情況：(1)活動就緒→靜止就緒。當(dāng)進程處于未被掛起的就緒狀態(tài)時，稱此為活動就緒狀態(tài)，表示為Readya。當(dāng)用掛起原語Suspend將該進程掛起后，該進程便轉(zhuǎn)變?yōu)殪o止就緒狀態(tài)，表示為Readys，處于Readys狀態(tài)的進程不再被調(diào)度執(zhí)行。2.1.3進程狀態(tài)和進程轉(zhuǎn)換2)進程狀態(tài)的轉(zhuǎn)換232.1.3進程狀態(tài)和進程轉(zhuǎn)換(2)活動阻塞→靜止阻塞。當(dāng)進程處于未被掛起的阻塞狀態(tài)時，稱它是處于活動阻塞狀態(tài)，表示為Blockeda。當(dāng)用Suspend原語將它掛起后，進程便轉(zhuǎn)變?yōu)殪o止阻塞狀態(tài)，表示為Blockeds。處于該狀態(tài)的進程在其所期待的事件出現(xiàn)后，將從靜止阻塞變?yōu)殪o止就緒。(3)靜止就緒→活動就緒。處于Readys狀態(tài)的進程，若用激活原語Active激活后，該進程將轉(zhuǎn)變?yōu)镽eadya狀態(tài)。(4)靜止阻塞→活動阻塞。處于Blockeds狀態(tài)的進程，若用激活原語Active激活后，該進程將轉(zhuǎn)變?yōu)锽lockeda狀態(tài)。下圖示出了具有掛起狀態(tài)的進程狀態(tài)圖。2.1.3進程狀態(tài)和進程轉(zhuǎn)換(2)活動阻塞→靜止阻塞。當(dāng)242.1.3進程狀態(tài)和進程轉(zhuǎn)換3.掛起操作

執(zhí)行活動就緒活動阻塞時間片到進程調(diào)度I/O請求I/O完成內(nèi)存外存靜止就緒靜止阻塞I/O完成掛起掛起激活激活2.1.3進程狀態(tài)和進程轉(zhuǎn)換3.掛起操作執(zhí)行活動就緒活動252.1.4進程控制塊及其組織方式

1.進程控制塊的作用進程控制塊的具體作用如下：（1）PCB是進程在系統(tǒng)中存在的唯一標(biāo)識。（2）保存CPU現(xiàn)場信息。（3）提供進程管理所需信息。（4）提供進程調(diào)度所需信息。（5）實現(xiàn)及其它進程的同步和通信。2.1.4進程控制塊及其組織方式1.進程控制塊的作用262.1.4進程控制塊及其組織方式

2.進程控制塊的信息

進程控制塊包含下述4類信息：（1）進程標(biāo)識信息。（2）進程說明信息。（3）處理機狀態(tài)信息。（4）進程的控制信息。

2.1.4進程控制塊及其組織方式2.進程控制塊的信息272.1.4進程控制塊及其組織方式

3.進程控制塊的組織方式常用的PCB組織方式有以下三種：（1）線性方式（2）鏈接方式。2.1.4進程控制塊及其組織方式3.進程控制塊的組織282.1.4進程控制塊及其組織方式

3.進程控制塊的組織方式（3）索引方式2.1.4進程控制塊及其組織方式3.進程控制塊的組織29重點回顧進程的定義和特征進程狀態(tài)就緒(Ready)狀態(tài)執(zhí)行狀態(tài)阻塞狀態(tài)掛起重點回顧進程的定義和特征30執(zhí)行重點回顧就緒阻塞時間片到進程調(diào)度I/O請求I/O完成執(zhí)行重點回顧就緒阻塞時間片到進程調(diào)度I/O請31重點回顧執(zhí)行活動就緒活動阻塞時間片到進程調(diào)度I/O請求I/O完成內(nèi)存外存靜止就緒靜止阻塞I/O完成掛起掛起激活激活重點回顧執(zhí)行活動就緒活動阻塞時間片到進程調(diào)度I/O請求I/O322.2進程控制2.2.1進程創(chuàng)建系統(tǒng)中導(dǎo)致創(chuàng)建新進程的典型事件：①操作系統(tǒng)初始化。當(dāng)操作系統(tǒng)啟動時，通常會創(chuàng)建若干進程，特別是創(chuàng)建一些常駐系統(tǒng)進程。②作業(yè)調(diào)度。多道批處理系統(tǒng)中，當(dāng)作業(yè)調(diào)度程序選中某個作業(yè)時，將其裝入內(nèi)存，為其創(chuàng)建進程，并把創(chuàng)建好的進程插入到就緒進程隊列。③提供服務(wù)。當(dāng)某一進程向操作系統(tǒng)提出某種服務(wù)請求時，系統(tǒng)將專門創(chuàng)建一個進程來提供其所要求的服務(wù)。④應(yīng)用請求。當(dāng)用戶向系統(tǒng)提出某種應(yīng)用請求時，系統(tǒng)為其創(chuàng)建新進程。2.2進程控制2.2.1進程創(chuàng)建332.2.1進程創(chuàng)建進程的創(chuàng)建(CreationofProcess)過程一旦操作系統(tǒng)發(fā)現(xiàn)了要求創(chuàng)建新進程的事件后，便調(diào)用進程創(chuàng)建原語Creat()按下述步驟創(chuàng)建一個新進程。(1)申請空白PCB。為新進程申請獲得惟一的數(shù)字標(biāo)識符，并從PCB集合中索取一個空白PCB。(2)為新進程分配資源。為新進程的程序和數(shù)據(jù)，以及用戶棧分配必要的內(nèi)存空間。(3)初始化進程控制塊。(4)將新進程插入就緒隊列，如果進程就緒隊列能夠接納新進程，便將新進程插入就緒隊列。2.2.1進程創(chuàng)建進程的創(chuàng)建(CreationofPr34入口圖創(chuàng)建原語流圖入口圖創(chuàng)建原語流圖352.2.2進程執(zhí)行及進程切換系統(tǒng)進行進程切換時通常進行如下工作：①保存被中斷進程的處理器現(xiàn)場信息；②修改當(dāng)前運行進程的PCB，將運行狀態(tài)改為其他狀態(tài)，并把它插入到相應(yīng)的PCB隊列中；③選擇另一個進程運行，并修改該進程的PCB，使其狀態(tài)變?yōu)檫\行態(tài)；④將當(dāng)前進程存儲管理數(shù)據(jù)修改為新選進程的存儲管理數(shù)據(jù)；⑤恢復(fù)被選進程上次切換出處理機時的處理機現(xiàn)場，開始運行該進程。2.2.2進程執(zhí)行及進程切換系統(tǒng)進行進程切換時通常進行如下361、引起進程阻塞和喚醒的事件請求系統(tǒng)服務(wù)：正在執(zhí)行的程序請求操作系統(tǒng)服務(wù)，但是由于某種原因操作系統(tǒng)沒有立即滿足該進程的要求，該進程只能轉(zhuǎn)變?yōu)樽枞麪顟B(tài)來等待。啟動某操作：當(dāng)進程啟動某種操作后，如果該進程必須在該操作完成之后才能繼續(xù)執(zhí)行，所有必須先使進程阻塞。新數(shù)據(jù)尚未到達無新工作可做：系統(tǒng)往往設(shè)置一些具有某特定功能的系統(tǒng)進程，每當(dāng)這種進程完成任務(wù)以后便把自己阻塞起來等待新任務(wù)的到來。（發(fā)送進程）2.2.3進程的阻塞及喚醒1、引起進程阻塞和喚醒的事件2.2.3進程的阻塞及喚醒372、進程阻塞過程當(dāng)有阻塞事件發(fā)生時，進程便調(diào)用阻塞原語block()把自己阻塞。進入block后，應(yīng)先立即停止執(zhí)行，把進程控制塊中的執(zhí)行狀態(tài)改為阻塞狀態(tài)，并把它插入阻塞隊列。3、進程喚醒過程當(dāng)阻塞進程所期待的事件出現(xiàn)時，則調(diào)用喚醒原語wakeup()，將等待事件的進程喚醒。喚醒原語執(zhí)行的過程是：首先把被阻塞進程從等待該事件的阻塞隊列中移出，將其PCB中的阻塞狀態(tài)改為就緒狀態(tài)，然后把該進程插入到就緒隊列中。block()和wakeup()是一對作用剛好相反的原語。2.2.3進程的阻塞及喚醒2、進程阻塞過程2.2.3進程的阻塞及喚醒38入口圖

阻塞原語入口圖

喚醒原語入口圖阻塞原語入口圖喚醒原語392.2.4進程掛起及激活1、進程的掛起

當(dāng)出現(xiàn)了引起進程掛起的事件時，比如，用戶進程請求將自己掛起，或父進程請求將自己的某個子進程掛起，系統(tǒng)將利用掛起原語suspend()將指定進程或處于阻塞狀態(tài)的進程掛起。掛起原語的執(zhí)行過程是：首先檢查被掛起進程的狀態(tài)，若處于活動就緒狀態(tài)，便將其改為靜止就緒；對于活動阻塞狀態(tài)的進程，則將之改為靜止阻塞。最后，若被掛起的進程正在執(zhí)行，則轉(zhuǎn)向調(diào)度程序重新調(diào)度。2.2.4進程掛起及激活1、進程的掛起402.2.4進程掛起及激活2．進程的激活過程當(dāng)發(fā)生激活進程的事件時，例如，父進程或用戶進程請求激活指定進程，若該進程駐留在外存而內(nèi)存中已有足夠的空間時，則可將在外存上處于靜止就緒狀態(tài)的該進程換入內(nèi)存。這時，系統(tǒng)將利用激活原語active()將指定進程激活。激活原語的執(zhí)行過程是：先將進程從外存調(diào)入內(nèi)存，檢查該進程的現(xiàn)行狀態(tài)，若是靜止就緒，便將之改為活動就緒；若為靜止阻塞，便將之改為活動阻塞。2.2.4進程掛起及激活2．進程的激活過程412.2.5進程撤銷1．引起進程撤銷的事件正常結(jié)束：計算機系統(tǒng)中，都有一個表示進程已經(jīng)運行完成的指示。（批處理，Holt。分時系統(tǒng)中，LogsOff）異常結(jié)束：越界錯誤、保護錯、特權(quán)指令錯、非法指令錯、運行超時、等待超時、算術(shù)運算錯、I/O故障外界干預(yù)：操作員或操作系統(tǒng)干預(yù)、父進程請求、父進程終止2．進程的撤銷過程2.2.5進程撤銷1．引起進程撤銷的事件42入口圖終止原語流圖入口圖終止原語流圖432.3進程同步2.3.1進程同步的基本概念1．進程同步的兩種制約關(guān)系在多道程序環(huán)境下，當(dāng)程序并發(fā)執(zhí)行時，由于資源共享和進程合作，使同處于一個系統(tǒng)中的諸進程之間可能存在著以下兩種形式的制約關(guān)系。(1)間接制約(進程互斥)：源于資源共享。(2)直接制約(進程同步)：主要源于進程間的合作。重點2.3進程同步2.3.1進程同步的基本概念重點442.3.1進程同步的基本概念

同步及互斥的比較同步互斥進程及進程之間有序合作進程及進程之間共享臨界資源相互清楚對方的存在及其作用，直接合作不清楚對方的情況，只是共享同一臨界資源多個進程合作完成一個任務(wù)各個進程之間沒有任何合作工作例如：發(fā)送消息進程和接受消息進程之間；輸入進程、計算進程和輸出進程之間等。例如：共享打印機的若干進程之間；共享同一全局變量的若干進程之間等。2.3.1進程同步的基本概念同步及互斥的比較452.3.1進程同步的基本概念2．臨界資源及臨界區(qū)臨界資源也稱獨占資源，是指某段時間內(nèi)只允許一個進程使用的資源。比如打印機等硬件資源，以及只能互斥使用的變量、表格、隊列等軟件資源。臨界資源的使用只能采用互斥方式。當(dāng)一個進程正在使用某個臨界資源且尚未使用完畢時，其它進程必須阻塞等待。只有當(dāng)使用該資源的進程釋放該資源時，其它進程才可使用。任何進程不能在其他進程沒有使用完臨界資源時使用該資源，否則將會導(dǎo)致錯誤。各個進程中訪問臨界資源的、必須互斥執(zhí)行的程序代碼段稱為臨界區(qū)。2.3.1進程同步的基本概念2．臨界資源及臨界區(qū)462.3.1進程同步的基本概念2．臨界資源及臨界區(qū)2.3.1進程同步的基本概念2．臨界資源及臨界區(qū)472.3.1進程同步的基本概念3．同步機制應(yīng)遵循的準則①空閑讓進。當(dāng)無進程處于某臨界資源對應(yīng)的臨界區(qū)時，表明該臨界資源處于空閑狀態(tài)，應(yīng)充許一個請求進入臨界區(qū)的進程立即進入臨界區(qū)。②忙則等待。當(dāng)有進程已進入某臨界資源對應(yīng)的臨界區(qū)時，表明該臨界資源正在被使用，因而其它試圖進入該臨界資源對應(yīng)臨界區(qū)的進程必須在進入?yún)^(qū)代碼處等待。③有限等待。對要求訪問臨界資源的進程應(yīng)保證其在有限時間內(nèi)能進入自己的臨界區(qū)，以免陷入“死等”狀態(tài)。④讓權(quán)等待。當(dāng)進程不能進入自己的臨界區(qū)時，應(yīng)立即阻塞自己并釋放處理機，以免進程陷入“忙等”狀態(tài)。2.3.1進程同步的基本概念3．同步機制應(yīng)遵循的準則482.3.1進程同步的基本概念4．實現(xiàn)臨界區(qū)互斥的基本方法（1）軟件實現(xiàn)方法軟件方法是指編程人員編寫程序時在臨界區(qū)前面設(shè)置檢查語句，檢查如果有其他并發(fā)執(zhí)行的進程在臨界區(qū)中，則不允許進程進入臨界區(qū)，只能在臨界區(qū)外“忙等”或阻塞。當(dāng)其他進程退出臨界區(qū)后，進程能夠進入臨界區(qū)運行。常見的軟件實現(xiàn)方法有：Dekker算法和Peterson算法等。（2）硬件實現(xiàn)方法2.3.1進程同步的基本概念4．實現(xiàn)臨界區(qū)互斥的基本方法492.3.1進程同步的基本概念4．實現(xiàn)臨界區(qū)互斥的基本方法①中斷禁用為保證多個并發(fā)進程互斥使用臨界資源，只需保證一個進程在執(zhí)行臨界區(qū)代碼時不被中斷即可，這可通過系統(tǒng)內(nèi)核為啟用和禁用中斷而定義的原語來實現(xiàn)。②專用機器指令編程人員利用專用機器指令來實現(xiàn)臨界區(qū)的互斥使用。在臨界區(qū)代碼前通過硬件指令來檢查某一全局變量是否有其他并發(fā)執(zhí)行的進程在臨界區(qū)中使用。若沒有，則可進入臨界區(qū)；若有，則重復(fù)檢查，處于“忙等”狀態(tài)。當(dāng)進程執(zhí)行完臨界區(qū)代碼退出時，修改該全局變量，允許其他并發(fā)執(zhí)行的進程進入臨界區(qū)執(zhí)行。2.3.1進程同步的基本概念4．實現(xiàn)臨界區(qū)互斥的基本方法502.3.2信號量機制1．常見信號量分類(1)整型信號量最初由Dijkstra把整型信號量定義為一個用于表示資源數(shù)目的整型量S，它及一般整型量不同，除初始化外，僅能通過兩個標(biāo)準的原子操作(AtomicOperation)P(S)和V(S)來訪問。P(S)和V(S)操作可描述為：

P(S)：whileS<=0donoop；

S:=S-1；

V(S)：S:=S+1；wait(S)和signal(S)是兩個原語，因此，它們在執(zhí)行時是不可中斷的。重點2.3.2信號量機制1．常見信號量分類重點512.3.2信號量機制(2)記錄型信號量在整型信號量機制中的P操作，只要是信號量S≤0，就會不斷地測試。因此，該機制并未遵循“讓權(quán)等待”的準則，而是使進程處于“忙等”的狀態(tài)。記錄型信號量機制則是一種不存在“忙等”現(xiàn)象的進程同步機制。但在采取了“讓權(quán)等待”的策略后，又會出現(xiàn)多個進程等待訪問同一臨界資源的情況。為此，在記錄型信號量機制中，除了需要一個用于代表資源數(shù)目的整型變量value外，還應(yīng)增加一個進程鏈表指針L，用于鏈接上述的所有等待進程。記錄型信號量是由于它采用了記錄型的數(shù)據(jù)結(jié)構(gòu)而得名的。它所包含的上述兩個數(shù)據(jù)項可描述為：2.3.2信號量機制(2)記錄型信號量522.3.2信號量機制記錄型信號量的value值：用于表示資源數(shù)目或請求使用某一資源的進程個數(shù)的整形量。S.value是及臨界區(qū)內(nèi)所使用的公用資源有關(guān)的信號量。S.value≥0：可供并發(fā)進程使用的資源數(shù)S.value<0：正在等待使用臨界區(qū)的進程數(shù)信號量的值除初始化外，只能通過P、V原語來修改2.3.2信號量機制記錄型信號量的value值：用于表示資532.3.2信號量機制P(S)原語操作的主要動作是：S.value-1；如果S.value-1以后仍大于等于零，則進程繼續(xù)進行；如果S.value-1以后小于零，則將該進程阻塞以后插入阻塞隊列，然后轉(zhuǎn)進程調(diào)度。如下圖所示V(S)原語操作的主要動作是：S.value+1；如果相加后結(jié)果大于零，則繼續(xù)進行；相加后結(jié)果小于等于零，則從該信號的等待隊列中喚醒一個等待進程，然后返回原進程繼續(xù)執(zhí)行或者轉(zhuǎn)進程調(diào)度。如下圖所示2.3.2信號量機制P(S)原語操作的主要動作是：54入口圖P原語操作功能入口圖V原語操作功能2.3.2信號量機制入口圖P原語操作功能入口圖V原語操作功能2.3.2信號55typesemaphore=record

value:integer；

L:listofprocess；end相應(yīng)地，P(S)和V(S)操作可描述為：procedureP(S)

varS：semaphore；

begin

S.value:=S.value-1；

ifS.value<0then block(S.L)；

endprocedureV(S)

varS:semaphore；

begin

S.value:=S.value+1；

ifS.value<=0thenwakeup(S.L)；

endtypesemaphore=recordprocedure562.3.2信號量機制2．信號量的應(yīng)用（1）利用信號量實現(xiàn)進程互斥關(guān)系為使多個進程能互斥地訪問某臨界資源，只須為該資源設(shè)置一互斥信號量mutex，并設(shè)其初始值為1，然后將各進程訪問該資源的臨界區(qū)CS置于P(mutex)和V(mutex)操作之間即可。利用信號量實現(xiàn)進程互斥的進程可描述如下：2.3.2信號量機制2．信號量的應(yīng)用57(1)利用信號量實現(xiàn)進程互斥必須成對使用P和V原語：遺漏P原語則不能保證互斥訪問，遺漏V原語則不能在使用臨界資源之后將其釋放（給其他等待的進程）；P、V原語不能次序錯誤、重復(fù)或遺漏(1)利用信號量實現(xiàn)進程互斥5804/01/1159P(mutex)V(mutex)P1P2P3互斥區(qū)P(mutex)P(mutex)V(mutex)V(mutex)(1)利用信號量實現(xiàn)進程互斥04/01/1159P(mutex)V(mutex)P1P259首先需要找到共享的臨界資源；如右圖所示程序中，每個進程中含有多個變量，但只有共享的公共變量a才是共享的臨界資源，而c和y都不是；找到了共享的臨界資源a，則每個程序中涉及該資源a的程序段都是臨界區(qū)；為臨界資源a設(shè)置信號量mutex及其初值；再針對每個臨界區(qū)使用mutex的P、V操作將臨界區(qū)括起來。(1)利用信號量實現(xiàn)進程互斥—舉例首先需要找到共享的臨界資源；如右圖所示程序中，每個進程中含有60重點回顧進程控制進程同步的兩種制約關(guān)系間接制約(進程互斥)：源于資源共享。直接制約(進程同步)：主要源于進程間的合作。臨界資源及臨界區(qū)臨界資源也稱獨占資源，是指某段時間內(nèi)只允許一個進程使用的資源。比如打印機等硬件資源，以及只能互斥使用的變量、表格、隊列等軟件資源。各個進程中訪問臨界資源的、必須互斥執(zhí)行的程序代碼段稱為臨界區(qū)。重點回顧進程控制61重點回顧記錄型信號量需要一個用于代表資源數(shù)目的整型變量value外，還應(yīng)增加一個進程鏈表指針L，用于鏈接上述的所有等待進程。記錄型信號量的value值：用于表示資源數(shù)目或請求使用某一資源的進程個數(shù)的整形量。信號量的值除初始化外，只能通過P、V原語來修改重點回顧記錄型信號量62重點回顧P(S)原語操作的主要動作是：S.value-1；如果減1以后仍大于等于零，則進程繼續(xù)進行；如果減1以后小于零，則將該進程阻塞以后插入阻塞隊列，然后轉(zhuǎn)進程調(diào)度。V(S)原語操作的主要動作是：S.value+1；如果相加后結(jié)果大于零，則繼續(xù)進行；相加后結(jié)果小于等于零，則從該信號的等待隊列中喚醒一個等待進程，然后返回原進程繼續(xù)執(zhí)行或者轉(zhuǎn)進程調(diào)度。重點回顧P(S)原語操作的主要動作是：63例：某車站售票廳有20個窗口，任何時刻最多可容納20名購票者進入，當(dāng)售票廳中少于20名購票者時，則廳外的購票者可立即進入，否則需在廳外等待。若把一個購票者看作一個進程，請用P、V操作管理這些并發(fā)進程，要求如下：⑴在主函數(shù)中給出信號量的定義和初值。⑵給出一個購票者進程的算法。⑶給出當(dāng)購票者最多不超過n(設(shè)n>20)個時，信號量可能的變化范圍。(1)利用信號量實現(xiàn)進程互斥—舉例例：某車站售票廳有20個窗口，任何時刻最多可容納20名購票者64判斷該問題是互斥問題還是同步問題：可以將該售票廳的每個窗口看作是一個臨界資源為每個購票者進程共享，每個購票者進程只能使用其中一個窗口。售票廳有20個窗口，所以有20個同類的臨界資源，一次可以允許20個進程進入，并且先來者先進入。由此可知：該問題滿足互斥的2個必要條件（共享臨界資源，共享方式是先來者先進入），所以該問題是互斥問題。根據(jù)互斥問題的解決方法設(shè)置信號量并賦初值：設(shè)置一個信號量mutex，初值為20。用信號量的P、V操作將臨界區(qū)括起來。問題分析判斷該問題是互斥問題還是同步問題：問題分析65⑴．主函數(shù)算法：main(){

semaphoremutex=20; cobegin P1();…Pi();…Pn(); coend}⑵．購票者i的算法：Pi(){ P(mutex);

進入售票廳占有一個窗口購票；

V(mutex);}算法描述⑴．主函數(shù)算法：⑵．購票者i的算法：算法描述66⑶．信號量mutex的取值范圍：－(n－20)≤mutex≤20其物理含義是：當(dāng)mutex=20時，表示售票廳內(nèi)沒有購票者進入，20個窗口都是空閑的，表示可用資源個數(shù)；當(dāng)mutex=0時，表示售票廳內(nèi)已經(jīng)進入了20個購票者，每個窗口都被分配，沒有等待的購票者，可用資源為0；當(dāng)mutex=－(n－20)時，表示一共有n個購票者，其中20個購票者已經(jīng)進入廳內(nèi)，分別占有一個窗口，還有n－20個購票者在廳外等待，絕對值表示等待進程個數(shù)。結(jié)論：當(dāng)mutex≥0時其值表示可用資源個數(shù)；當(dāng)mutex＜0時其絕對值表示等待進程的個數(shù)。信號量討論⑶．信號量mutex的取值范圍：信號量討論67(2)利用信號量實現(xiàn)前趨關(guān)系還可利用信號量來描述程序或語句之間的前趨關(guān)系。設(shè)有兩個并發(fā)執(zhí)行的進程P1和P2。P1中有語句S1；P2中有語句S2。我們希望在S1執(zhí)行后再執(zhí)行S2。為實現(xiàn)這種前趨關(guān)系，我們只須使進程P1和P2共享一個公用信號量S，并賦予其初值為0，將V(S)操作放在語句S1后面；而在S2語句前面插入P(S)操作，即在進程P1中，用S1；V(S)；在進程P2中，用P(S)；S2；(2)利用信號量實現(xiàn)前趨關(guān)系還可利用信號量來描述程序或語句之68(2)利用信號量實現(xiàn)前趨關(guān)系下圖示出了一個前趨圖，其中S1，S2，S3，…，S6是最簡單的程序段(只有一條語句)。為使各程序段能正確執(zhí)行，應(yīng)設(shè)置若干個初始值為“0”的信號量。如為保證S1→S2，S1→S3的前趨關(guān)系，應(yīng)分別設(shè)置信號量a和b，同樣，為了保證S2→S4，S2→S5，S3→S6，S4→S6和S5→S6，應(yīng)設(shè)置信號量c，d，e，f，g。圖

前趨圖舉例

(2)利用信號量實現(xiàn)前趨關(guān)系下圖示出了一個前趨圖，其中S1，692.3.2信號量機制semaphorevara,b,c,d,e,f,g=0,0,0,0,0,0,0;beginparbegin//并發(fā)程序開始

beginS1;V(a);V(b);end; beginP(a);S2;V(c);V(d);end; beginP(b);S3;V(e);end; beginP(c);S4;V(f);end; beginP(d);S5;V(g);end; beginP(e);P(f);P(g);S6;end;parend//并發(fā)程序結(jié)束end2.3.2信號量機制semaphorevara,b,c702.3.2信號量機制舉例：V(S1)P(S1)V(S2)P(S2)2.3.2信號量機制舉例：V(S1)P(S1)V(S2)P712.3.2信號量機制vars1,s2:semaphore:=0,0；司機進程：beginwhile(true){P(S1);//等待售票員發(fā)送關(guān)門信息啟動車輛；正常行車；到站停車；

V(S2)；//給售票員發(fā)送到站信息}end;售票員進程：beginwhile(true){

關(guān)車門;V(S1);//給司機發(fā)送關(guān)門信息售票；

P(S2)；//等待司機發(fā)送到站信息開車門；上下乘客；}end；2.3.2信號量機制vars1,s2:semaphore722.3.3典型進程同步問題一、生產(chǎn)者進程和消費者問題描述：有一群生產(chǎn)者進程在生產(chǎn)產(chǎn)品，并將這些產(chǎn)品提供給消費者進程去消費。為使生產(chǎn)者進程及消費者進程能并發(fā)執(zhí)行，在兩者之間設(shè)置了一個具有n個緩沖區(qū)的緩沖池，生產(chǎn)者進程將它所生產(chǎn)的產(chǎn)品放入一個緩沖區(qū)中；消費者進程可從一個緩沖區(qū)中取走產(chǎn)品去消費。盡管所有的生產(chǎn)者進程和消費者進程都是以異步方式運行的，但它們之間必須保持同步，即:1)消費者想接收數(shù)據(jù)時，有界緩沖區(qū)中至少有一個單元是滿的2)生產(chǎn)者想接收數(shù)據(jù)時，有界緩沖區(qū)中至少有一個單元是空的重點和難點2.3.3典型進程同步問題一、生產(chǎn)者進程和消費者問題描述：73一、生產(chǎn)者和消費者問題可利用一個數(shù)組來表示上述的具有n個(0，1，…，n-1)緩沖區(qū)的緩沖池。用輸入指針in來指示下一個可投放產(chǎn)品的緩沖區(qū)，每當(dāng)生產(chǎn)者進程生產(chǎn)并投放一個產(chǎn)品后，輸入指針加1；用一個輸出指針out來指示下一個可從中獲取產(chǎn)品的緩沖區(qū)，每當(dāng)消費者進程取走一個產(chǎn)品后，輸出指針加1?！璶…….…321P1P2P3.Pn.C1C2C3.Cn有界緩沖區(qū)n圖生產(chǎn)者-消費者問題一、生產(chǎn)者和消費者問題…n…….…321P1C1有界緩沖區(qū)n74一、生產(chǎn)者和消費者問題由以上分析得:公用信號量mutex保證生產(chǎn)者進程和消費者進程之間對緩沖池的互斥使用，初值為1;信號量empty表示有界緩沖區(qū)中的空單元數(shù)，初值為n；信號量full表示有界緩沖區(qū)中的非空單元數(shù)，初值為0。信號量mutex表示有界緩沖區(qū)中的個數(shù)。

對生產(chǎn)者—消費者問題可描述如下:一、生產(chǎn)者和消費者問題由以上分析得:75一、生產(chǎn)者和消費者問題varmutex,empty,full:semaphore:=1,n,0；buffer:array［0,…,n-1］ofitem；in,out:integer∶=0,0；beginparbegin一、生產(chǎn)者和消費者問題varmutex,empty,f76一、生產(chǎn)者和消費者問題Producer:beginrepeatproduceraniteminnextp；

P(empty)；

//獲得一個空緩沖區(qū)

P(mutex)；

//互斥使用緩沖區(qū)

buffer(in):=nextp；

in:=(in+1)modn；//把產(chǎn)品——nextp放入緩沖區(qū)中

V(mutex)；

//釋放緩沖區(qū)

V(full)；

//緩沖池得到一個滿緩沖區(qū)

untilfalse；end一、生產(chǎn)者和消費者問題Producer:77一、生產(chǎn)者和消費者問題Consumer:beginrepeat

P(full);//獲得一個滿緩沖區(qū)

P(mutex);//互斥使用緩沖區(qū)

nextc:=buffer(out);out:=(out+1)modn;//把產(chǎn)品拷入nextc

V(mutex); //釋放緩沖區(qū)

V(empty);//緩沖池得到一個空緩沖區(qū)

consumertheiteminnextc;untilfalse;endparendend一、生產(chǎn)者和消費者問題Consumer:78重點回顧經(jīng)典進程的同步問題生產(chǎn)者—消費者問題重點回顧經(jīng)典進程的同步問題79一、生產(chǎn)者和消費者問題Consumer:beginrepeat

P(full);

P(mutex);

nextc:=buffer(out);out:=(out+1)modn;

V(mutex);

V(empty);

consumertheiteminnextc;untilfalse;endProducer:beginrepeatproduceraniteminnextp；

P(empty)；

P(mutex)；

buffer(in):=nextp；

in:=(in+1)modn；

V(mutex)；

V(full)；

untilfalse；end一、生產(chǎn)者和消費者問題Consumer:Producer:80P,V操作討論1)信號量的物理含義：S.value>0表示有S.value個資源可用S.value=0表示無資源可用S.value<0則|S.value|表示S等待隊列中的進程個數(shù)P(S):表示申請一個資源V(S)表示釋放一個資源。信號量的初值應(yīng)該大于等于0P,V操作討論1)信號量的物理含義：81P,V操作討論2)P.V操作必須成對出現(xiàn)，有一個P操作就一定有一個V操作當(dāng)為互斥操作時，它們同處于同一進程當(dāng)為同步操作時，則不在同一進程中出現(xiàn)如果P(S1)和P(S2)兩個操作在一起，那么P操作的順序至關(guān)重要,一個同步P操作及一個互斥P操作在一起時同步P操作在互斥P操作前而兩個V操作無關(guān)緊要P,V操作討論2)P.V操作必須成對出現(xiàn)，有一個P操作就一82P,V操作討論3)P.V操作的優(yōu)缺點優(yōu)點：簡單，而且表達能力強（用P.V操作可解決任何同步互斥問題）缺點：不夠安全；P,V操作使用不當(dāng)會出現(xiàn)死鎖；遇到復(fù)雜同步互斥問題時實現(xiàn)復(fù)雜P,V操作討論3)P.V操作的優(yōu)缺點83二、哲學(xué)家進餐問題

問題描述：5個哲學(xué)家圍繞一張圓桌而坐，桌子上放著5支筷子，每兩個哲學(xué)家之間放一支；哲學(xué)家的動作包括思考和進餐，進餐時需要同時拿起他左邊和右邊的兩支筷子，思考時則同時將兩支筷子放回原處。如何保證哲學(xué)家們的動作有序進行？如：不出現(xiàn)相鄰者同時要求進餐；不出現(xiàn)有人永遠拿不到筷子；二、哲學(xué)家進餐問題問題描述：如何保證哲學(xué)家們的動作有序進84二、哲學(xué)家進餐問題

varchopstick:array［0,…,4］ofsemaphore;第i位哲學(xué)家的活動可描述為：repeat P(chopstick［i］); P(chopstick［(i+1)mod5］); … Eating;… V(chopstick［i］); V(chopstick［(i+1)mod5］); … Thinking;untilfalse;二、哲學(xué)家進餐問題varchopstick:ar85二、哲學(xué)家進餐問題上述解法可保證不會有兩個相鄰的哲學(xué)家同時進餐，但有可能引起死鎖?？刹扇∫韵聨追N方法解決死鎖問題：(1)至多只允許有四位哲學(xué)家同時去拿左邊的筷子，最終能保證至少有一位哲學(xué)家能夠進餐，并在用畢時能釋放出他用過的兩只筷子，從而使更多的哲學(xué)家能夠進餐。(2)僅當(dāng)哲學(xué)家的左、右兩只筷子均可用時，才允許他拿起筷子進餐。(3)規(guī)定奇數(shù)號哲學(xué)家先拿他左邊的筷子，然后再去拿右邊的筷子，而偶數(shù)號哲學(xué)家則相反。按此規(guī)定，將是1、2號哲學(xué)家競爭1號筷子；3、4號哲學(xué)家競爭3號筷子。即五位哲學(xué)家都先競爭奇數(shù)號筷子，獲得后，再去競爭偶數(shù)號筷子，最后總會有一位哲學(xué)家能獲得兩只筷子而進餐。二、哲學(xué)家進餐問題上述解法可保證不會有兩個相鄰的哲學(xué)家同時進86三、讀者寫者問題問題描述：多個進程間共享一個數(shù)據(jù)文件，把只要求讀文件的進程稱為“Reader”進程，其他進程則稱為“Writer”進程。允許多個“Reader”進程同時讀取共享文件，但不允許一個Writer進程和其他Reader進程或Writer進程同時訪問共享對象。即："讀－寫"互斥"寫－寫"互斥"讀－讀"允許三、讀者寫者問題問題描述：87三、讀者寫者問題為實現(xiàn)Reader及Writer進程間在讀或?qū)憰r的互斥而設(shè)置了一個互斥信號量mutex。另外，再設(shè)置一個整型變量Readcount表示正在讀的進程數(shù)目。由于只要有一個Reader進程在讀，便不允許Writer進程去寫。因此，僅當(dāng)Readcount=0,表示尚無Reader進程在讀時，Reader進程才需要執(zhí)行P(Wmutex)操作。若P(mutex)操作成功，Reader進程便可去讀，相應(yīng)地，做Readcount+1操作。同理，僅當(dāng)Reader進程在執(zhí)行了Readcount減1操作后其值為0時，才須執(zhí)行V(mutex)操作，以便讓W(xué)riter進程寫。又因為Readcount是一個可被多個Reader進程訪問的臨界資源，因此，應(yīng)該為它設(shè)置一個互斥信號量rmutex。三、讀者寫者問題為實現(xiàn)Reader及Writer進程間在讀或88讀者-寫者問題可描述如下：Varrmutex,mutex:semaphore:=1,1;Readcount:integer:=0;Reader:beginrepeat三、讀者寫者問題讀者-寫者問題可描述如下：三、讀者寫者問題89

P(rmutex);ifreadcount=0thenP(mutex);

//readcount=0，表示該進程是第一個讀者進//程。因讀進程優(yōu)先，阻塞寫進程。

readcount:=readcount+1;

V(rmutex);…performreadoperation;…

P(rmutex);readcount:=readcount-1;ifreadcount=0thenV(mutex);

//readcount=0，表示該進程是最后一//個讀進程，這時允許寫進程執(zhí)行。

V(rmutex);untilfalse;endwriter:beginrepeat

P(mutex);performwriteoperation;

V(mutex);untilfalse;endP(rmutex);writer:begin902.3.3典型進程同步問題某寺廟，有小和尚，老和尚若干。有一水缸，由小和尚提水入缸供老和尚飲用。水缸可容10桶水，水取自同一井中。水井徑窄，每次中能容下一個桶取水。水桶總數(shù)為3個。每人一次取缸水僅為1桶，且不可同時進行。試用記錄型信號量給出有關(guān)取水、入水的算法描述。根據(jù)題意，定義信號量及其初值如下：（1）水桶為臨界資源需互斥使用，定義信號量bucket，因有3個桶，故初值為3；（2）水井一次只能允許下一個桶取水，定義互斥信號量well，初值為1;（3）水缸一次只能允許一個人取水，定義互斥信號量jar，初始值為1；（4）empty和full用于小和尚和老和尚之間的同步制約關(guān)系。因為缸能存10桶水，所以empty初始值為10；開始時缸中沒有水，full的初始值為0。2.3.3典型進程同步問題某寺廟，有小和尚，老和尚91semaphorebucket=3,jar=1,full=0,empty=10,well=1;little_monk(){//小和尚入水算法while(1){P(empty);P(bucket);P(well);

從水井中打水；

V(well);P(jar);

倒入水缸；

V(jar);V(bucket);V(full);}}

old_monk(){//老和尚取水算法while(1){P(full);P(bucket);P(jar);

從缸中取水；

V(jar);V(empty);

從桶中倒出飲用;V(bucket);}}semaphorebucket=3,jar=1,full=92作業(yè)習(xí)題2P89第6,9,11題

作業(yè)習(xí)題293重點回顧經(jīng)典進程的同步問題生產(chǎn)者—消費者問題哲學(xué)家進餐問題讀者－寫者問題重點回顧經(jīng)典進程的同步問題942.3.4管程機制

1．為何引入管程雖然信號量機制是一種有效的進程同步機制，但其存在以下缺點：①信號量的P、V操作由用戶在各個進程中分散使用，使用不當(dāng)容易造成死鎖，增加了用戶編程負擔(dān)。②信號量機制涉及多個程序的關(guān)聯(lián)內(nèi)容，程序代碼可讀性差。③使用信號量機制不利于代碼的修改和維護，程序模塊獨立性差，任一變量或一段代碼的修改都可能影響全局。④信號量機制的正確性很難保證。操作系統(tǒng)或并發(fā)進程通常會采用多個信號量，它們關(guān)系錯綜復(fù)雜，很難保證沒有邏輯錯誤。為了解決上述問題，Hoare和Hanson于1973年提出了管程機制。2.3.4管程機制1．為何引入管程952.3.4管程機制

2．管程的定義一個管程定義了一個數(shù)據(jù)和能為并發(fā)進程執(zhí)行的一組操作，這組操作能同步進程和改變管理中的數(shù)據(jù)。因此，管程是一種并發(fā)性的結(jié)構(gòu)，它包括用于分配一個或一組共享資源的數(shù)據(jù)和過程，使用者使用時可忽略管程內(nèi)部的實現(xiàn)細節(jié)，減輕了編程者負擔(dān)。管程由四部分組成：管程的名稱局部于管程內(nèi)部的共享數(shù)據(jù)結(jié)構(gòu)說明對該數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程對管程內(nèi)部共享數(shù)據(jù)設(shè)置初始值的語句

2.3.4管程機制2．管程的定義962.3.4管程機制

3．條件變量在任何時刻，最多只有一個進程在管程中執(zhí)行，因此用管程很容易實現(xiàn)互斥，只要將需要互斥訪問的資源用數(shù)據(jù)結(jié)構(gòu)來描述，并將該數(shù)據(jù)結(jié)構(gòu)放入管程中便可。但當(dāng)一進程進入管程執(zhí)行管程的某個過程時，如因某種原因而被阻塞，應(yīng)立即退出該管程，否則會出現(xiàn)因阻擋其它進程進入管程，而它本身又無法退出管程，形成死鎖。為此，系統(tǒng)中引入了條件變量。條件變量的定義格式為：VarX:condition。對條件變量只能執(zhí)行以下兩種操作:①X.wait操作。②X.signal操作。2.3.4管程機制3．條件變量972.3.4管程機制

x.wait：正在調(diào)用管程的進程因x條件需要被阻塞或掛起，則調(diào)用x.wait將自己插入到x條件的等待隊列上，并釋放管程，直到x條件變化。此時其它進程可以使用該管程。x.signal：正在調(diào)用管程的進程發(fā)現(xiàn)x條件發(fā)生了變化，則調(diào)用x.signal，重新啟動一個因x條件而阻塞或掛起的進程。如果存在多個這樣的進程，則選擇其中的一個，如果沒有，則繼續(xù)執(zhí)行原進程，而不產(chǎn)生任何結(jié)果。這及信號量機制中的signal操作不同，因為后者總是要執(zhí)行s:=s+1操作，因而總會改變信號量的狀態(tài)。2.3.4管程機制x.wait：正在調(diào)用管程的進程982.3.4管程機制

4．管程解決生產(chǎn)者—消費者問題利用管程來解決生產(chǎn)者—消費者問題,首先為它們建立一個管程，命名為p_c。管程p_c中整型變量count表示緩沖池中己存放的產(chǎn)品數(shù)目，條件變量notfull、notempty分別對應(yīng)于緩沖池不全滿、緩沖池不全空兩個條件。此外，管程p_c中有兩個局部過程：①過程put：負責(zé)將產(chǎn)品投放到緩沖池中，當(dāng)count≥n時，表示緩沖池已滿，生產(chǎn)者進程需等待；②過程get：負責(zé)從緩沖池中取出產(chǎn)品，當(dāng)count≤0時，表示緩沖池已空，消費者進程需等待。2.3.4管程機制4．管程解決生產(chǎn)者—消費者問題992.3.4管程機制

管程p_c描述如下：typep_c=monitorVarin,out,count:integer;Buffer:array[0,…,n-1]ofitem;notfull,notempty:condition;procedureentryput(Varproduct:item)beginifcount≥nthennotfull.wait;/*不全滿條件不成立*/buffer[in]:=product;in:=(in+1)modn;count:=count+1;notempty.signal;/*緩沖池不全空條件成立*/end2.3.4管程機制管程p_c描述如下：1002.3.4管程機制

procedureentryget(Varproduct:item)beginifcount≤0thennotempty.wait;

/*緩沖池不全空條件不成立*/product:=buffer[out];out:=(out+1)modn;count:=count-1;notfull.signal;/*緩沖池不全滿條件成立*/endbeginin:=out:=0;count:=0;end2.3.4管程機制procedureentr1012.3.4管程機制

producer:beginrepeatproduceaniteminnextp;p_c.put(nextp);untilfalseendconsumer:beginrepeatp_c.get(nextc);consumetheiteminnextc;untilfalseend2.3.4管程機制producer:consume1022.4進程通信

2.4.1進程通信分類高級通信機制可分為三大類：1．共享存儲器系統(tǒng)

2．消息傳遞系統(tǒng)

3．管道通信

2.4進程通信2.4.1進程通信分類1031．共享存儲器系統(tǒng)基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式。在這種通信方式中，要求諸進程公用某些數(shù)據(jù)結(jié)構(gòu)，借以實現(xiàn)諸進程間的信息交換。如在生產(chǎn)者—消費者問題中，就是用有界緩沖區(qū)這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)通信的。低級通信(2)基于共享存儲區(qū)的通信方式。在存儲器中劃出了一塊共享存儲區(qū)，諸進程可通過對其中數(shù)據(jù)實現(xiàn)通信。高級通信。進程在通信前，先向系統(tǒng)申請獲得共享存儲區(qū)中的一個分區(qū)，并指定該分區(qū)的關(guān)鍵字；若系統(tǒng)已經(jīng)給其他進程分配了這樣的分區(qū)，則將該分區(qū)的描述符返回給申請者，繼之，由申請者把獲得的共享存儲分區(qū)連接到本進程上；此后，便可像讀、寫普通存儲器一樣地讀、寫該公用存儲分區(qū)。1．共享存儲器系統(tǒng)基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式。在這種通信方式1042．消息傳遞系統(tǒng)消息傳遞系統(tǒng)(Messagepassingsystem)是當(dāng)前應(yīng)用最為廣泛的一種進程間的通信機制。在該機制中，進程間的數(shù)據(jù)交換是以格式化的消息(message)為單位的；在計算機網(wǎng)絡(luò)中，又把message稱為報文。程序員直接利用操作系統(tǒng)提供的一組通信命令(原語)，不僅能實現(xiàn)大量數(shù)據(jù)的傳遞，而且還隱藏了通信的實現(xiàn)細節(jié)，使通信過程對用戶是透明的，從而大大減化了通信程序編制的復(fù)雜性，因而獲得了廣泛的應(yīng)用。在微內(nèi)核操作系統(tǒng)中，微內(nèi)核及服務(wù)器之間的通信，都采用了消息傳遞機制。高級通信方式。又因其實現(xiàn)方式的不同而進一步分成直接通信方式和間接通信方式兩種。2．消息傳遞系統(tǒng)消息傳遞系統(tǒng)(Messagepassing1053．管道通信所謂“管道”，是指用于連接一個讀進程和一個寫進程以實現(xiàn)它們之間通信的一個共享文件，又名pipe文件。向管道(共享文件)提供輸入的發(fā)送進程(即寫進程)，以字符流形式將大量的數(shù)據(jù)送入管道；而接受管道輸出的接收進程(即讀進程)，則從管道中接收(讀)數(shù)據(jù)。由于發(fā)送進程和接收進程是利用管道進行通信的，故又稱為管道通信。這種方式首創(chuàng)于UNIX系統(tǒng)，由于它能有效地傳送大量數(shù)據(jù)，因而又被引入到許多其它的操作系統(tǒng)中。3．管道通信所謂“管道”，是指用于連接一個讀進程和一個寫進程1063．管道通信為了協(xié)調(diào)雙方的通信，管道機制必須提供以下三方面的協(xié)調(diào)能力：

(1)互斥，即當(dāng)一個進程正在對pipe執(zhí)行讀/寫操作時，其它(另一)進程必須等待。

(2)同步，指當(dāng)寫(輸入)進程把一定數(shù)量(如4KB)的數(shù)據(jù)寫入pipe，便去睡眠等待，直到讀(輸出)進程取走數(shù)據(jù)后，再把它喚醒。當(dāng)讀進程讀一空pipe時，也應(yīng)睡眠等待，直至寫進程將數(shù)據(jù)寫入管道后，才將之喚醒。

(3)確定對方是否存在，只有確定了對方已存在時，才能進行通信。3．管道通信為了協(xié)調(diào)雙方的通信，管道機制必須提供以下三方面的1072.4.2消息傳遞系統(tǒng)1、消息緩沖機制（1）消息緩沖區(qū)消息緩沖區(qū)由操作系統(tǒng)負責(zé)管理，每個消息緩沖區(qū)存放一個消息，消息緩沖區(qū)的數(shù)據(jù)結(jié)構(gòu)：TypemessageBuffer=recordsender:integer;//發(fā)送消息的進程標(biāo)識符size:integer;//消息長度text:string;//消息正文next:pointer;//指向下一個消息緩沖區(qū)的指針End2.4.2消息傳遞系統(tǒng)1、消息緩沖機制1082.4.2消息傳遞機制（2）進程PCB中有關(guān)數(shù)據(jù)項TypePCB=record…mutex:semaphore;//消息隊列互斥信號量，初值為1sm:semaphore;//消息隊列中消息個數(shù)信號量，初值為0mq:pointer;//消息隊列隊首指針….End2.4.2消息傳遞機制（2）進程PCB中有關(guān)數(shù)據(jù)項1092.4.2消息傳遞機制（3）發(fā)送原語發(fā)送進程調(diào)用發(fā)送原語send(receiver,a)，申請一個消息緩沖區(qū)，把以a為首地址的發(fā)送區(qū)中的消息復(fù)制到該消息緩沖區(qū)，并將其掛接到接收進程的消息隊列上。2.4.2消息傳遞機制（3）發(fā)送原語1102.4.2消息傳遞機制

2.4.2消息傳遞機制1112.4.2消息傳遞機制Procdeuresend(receiver,a)begin getbuf(a.size,i);//根據(jù)消息長度，申請消息緩沖區(qū)i i.sender:=a.sender;//將a復(fù)制到i i.size:=a.size;i.text:=a.text;i.next:=0;getid(reciver,j);//得到接收進程的PCB指針jp(j.mutex);//互斥使用消息隊列insert(j.mq,i);//將消息i掛接到接收進程j的消息隊列尾部v(j.mutex);v(j.sm);//進程j的消息數(shù)加1End2.4.2消息傳遞機制Procdeuresend(rec1122.4.2消息傳遞機制（4）接收原語接收進程調(diào)用接收原語receive(b)，從消息隊列Mq中把第一個消息緩沖區(qū)的數(shù)據(jù)復(fù)制到以b為首的接收區(qū)內(nèi)。Procdeurereceive(b)Begin j=internalname;//得到本進程的ID p(j.sm); p(j.mutex);remove(j.mq,i);//多j.mq隊首取第一個消息i v(j.mutex); b.sender:=i.sender;//將i中的內(nèi)容復(fù)制到b b.size:=i.size;b.text:=i.text;releasebuf(i);//釋放iEnd

2.4.2消息傳遞機制（4）接收原語1132.4.2消息傳遞機制2、信箱機制信箱即是共享的數(shù)據(jù)結(jié)構(gòu)，用來暫存通信進程的消息。發(fā)送方把消息送到信箱，接收方從信箱中取走數(shù)據(jù)，每個信箱有唯一的標(biāo)識。在這種方式下，消息在信箱中可以安全地保存，只允許核準的目標(biāo)用戶進程隨時訪問信箱。信箱可分為如下三類：①私用信箱：②公用信箱③共享信箱2.4.2消息傳遞機制2、信箱機制114重點回顧管程由四部分組成：管程的名稱局部于管程內(nèi)部的共享數(shù)據(jù)結(jié)構(gòu)說明對該數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程對管程內(nèi)部共享數(shù)據(jù)設(shè)置初始值的語句高級進程通信機制可分為：共享存儲器系統(tǒng)

消息傳遞系統(tǒng)

管道通信重點回顧管程由四部分組成：1152.5線程

2.5.1進程的局限性在沒有引入線程時，進程是資源分配的基本單位，也是獨立調(diào)度和運行的基本單位。因此具有處理機切換開銷大等一些一些局限性。2.5線程2.5.1進程的局限性1162.5.2線程及其屬性

1、線程定義線程通常被描述為：線程是進程內(nèi)的一個執(zhí)行單元。線程是進程內(nèi)的一個可調(diào)度實體。線程是進程中相對獨立的一個控制流序列。

2.5.2線程及其屬性1、線程定義1172.5.2線程及其屬性

2.5.2線程及其屬性1182.5.2線程及其屬性

2、線程屬性線程具有下述屬性:①輕型實體。②獨立調(diào)度單位。③可并發(fā)執(zhí)行。④共享進程資源。2.5.2線程及其屬性2、線程屬性1192.5.2線程及其屬性

3、線程及進程2.5.2線程及其屬性3、線程及進程1202.5.5線程的實現(xiàn)1．內(nèi)核支持線程內(nèi)核支持線程KST(KernelSupportedThreads)，也都同樣是在內(nèi)核的支持下運行的，即無論是用戶進程中的線程，還是系統(tǒng)進程中的線程，他們的創(chuàng)建、撤消和切換等也是依靠內(nèi)核，在內(nèi)核空間實現(xiàn)的。此外，在內(nèi)核空間還為每一個內(nèi)核支持線程設(shè)置了一個線程控制塊，內(nèi)核是根據(jù)該控制塊而感知某線程的存在，并對其加以控制。2.5.5線程的實現(xiàn)1．內(nèi)核支持線程1212．用戶級線程用戶級線程ULT(UserLevelThreads)僅存在于用戶空間中。對于這種線程的創(chuàng)建、撤消、線程之間的同步及通信等功能，都無須利用系統(tǒng)調(diào)用來實現(xiàn)。對于用戶級線程的切換，通常發(fā)生在一個應(yīng)用進程的諸多線程之間，這時，也同樣無須內(nèi)核的支持?？梢?，這種線程是及內(nèi)核無關(guān)的。這些線程的任務(wù)控制塊都是設(shè)置在用戶空間，而線程所執(zhí)行的操作也無須內(nèi)核的幫助，因而內(nèi)核完全不知道用戶級線程的存在。2．用戶級線程用戶級線程ULT(UserLevelThr1222.5.6線程模型有三種不同的模型：一對一、多對一和多對多模型。1)一對一模型該模型是為每一個用戶線程都設(shè)置一個內(nèi)核控制線程及之連接，當(dāng)一個線程阻塞時，允許調(diào)度另一個線程運行。在多處理機系統(tǒng)中，則有多個線程并行執(zhí)行。2)多對一模型3)多對多模型2.5.6線程模型有三種不同的模型：一對一、多對一和多對多1232.5.6線程模型

2.5.6線程模型124本章學(xué)習(xí)目