第二章 進(jìn)程線(xiàn)程管理

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

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

2.1進(jìn)程的基本概念

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

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

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

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

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

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

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

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

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

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

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

執(zhí)行活動(dòng)就緒活動(dòng)阻塞時(shí)間片到進(jìn)程調(diào)度I/O請(qǐng)求I/O完成內(nèi)存外存靜止就緒靜止阻塞I/O完成掛起掛起激活激活2.1.4進(jìn)程控制塊及其組織方式

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

2.進(jìn)程控制塊的信息

進(jìn)程控制塊包含下述4類(lèi)信息：（1）進(jìn)程標(biāo)識(shí)信息。（2）進(jìn)程說(shuō)明信息。（3）處理機(jī)狀態(tài)信息。（4）進(jìn)程的控制信息。

2.1.4進(jìn)程控制塊及其組織方式

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

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

阻塞原語(yǔ)入口圖

喚醒原語(yǔ)2.2.4進(jìn)程掛起及激活1、進(jìn)程的掛起

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

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

P(S)：whileS<=0donoop；

S:=S-1；

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

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

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

進(jìn)入售票廳占有一個(gè)窗口購(gòu)票；

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

前趨圖舉例

2.3.2信號(hào)量機(jī)制semaphorevara,b,c,d,e,f,g=0,0,0,0,0,0,0;beginparbegin//并發(fā)程序開(kāi)始

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信號(hào)量機(jī)制舉例：V(S1)P(S1)V(S2)P(S2)2.3.2信號(hào)量機(jī)制vars1,s2:semaphore:=0,0；司機(jī)進(jìn)程：beginwhile(true){P(S1);//等待售票員發(fā)送關(guān)門(mén)信息啟動(dòng)車(chē)輛；正常行車(chē)；到站停車(chē)；

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

關(guān)車(chē)門(mén);V(S1);//給司機(jī)發(fā)送關(guān)門(mén)信息售票；

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

對(duì)生產(chǎn)者—消費(fèi)者問(wèn)題可描述如下:一、生產(chǎn)者和消費(fèi)者問(wèn)題varmutex,empty,full:semaphore:=1,n,0；buffer:array［0,…,n-1］ofitem；in,out:integer∶=0,0；beginparbegin一、生產(chǎn)者和消費(fèi)者問(wèn)題Producer:beginrepeatproduceraniteminnextp；

P(empty)；

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

P(mutex)；

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

buffer(in):=nextp；

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

V(mutex)；

//釋放緩沖區(qū)

V(full)；

//緩沖池得到一個(gè)滿(mǎn)緩沖區(qū)

untilfalse；end一、生產(chǎn)者和消費(fèi)者問(wèn)題Consumer:beginrepeat

P(full);//獲得一個(gè)滿(mǎn)緩沖區(qū)

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

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

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

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

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

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

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

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

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

readcount:=readcount+1;

V(rmutex);…performreadoperation;…

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

//readcount=0，表示該進(jìn)程是最后一//個(gè)讀進(jìn)程，這時(shí)允許寫(xiě)進(jìn)程執(zhí)行。

V(rmutex);untilfalse;endwriter:beginrepeat

P(mutex);performwriteoperation;

V(mutex);untilfalse;end2.3.3典型進(jìn)程同步問(wèn)題某寺廟，有小和尚，老和尚若干。有一水缸，由小和尚提水入缸供老和尚飲用。水缸可容10桶水，水取自同一井中。水井徑窄，每次中能容下一個(gè)桶取水。水桶總數(shù)為3個(gè)。每人一次取缸水僅為1桶，且不可同時(shí)進(jìn)行。試用記錄型信號(hào)量給出有關(guān)取水、入水的算法描述。根據(jù)題意，定義信號(hào)量及其初值如下：（1）水桶為臨界資源需互斥使用，定義信號(hào)量bucket，因有3個(gè)桶，故初值為3；（2）水井一次只能允許下一個(gè)桶取水，定義互斥信號(hào)量well，初值為1;（3）水缸一次只能允許一個(gè)人取水，定義互斥信號(hào)量jar，初始值為1；（4）empty和full用于小和尚和老和尚之間的同步制約關(guān)系。因?yàn)楦啄艽?0桶水，所以empty初始值為10；開(kāi)始時(shí)缸中沒(méi)有水，full的初始值為0。semaphorebucket=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);}}作業(yè)習(xí)題2P89第6,9,11題

重點(diǎn)回顧經(jīng)典進(jìn)程的同步問(wèn)題生產(chǎn)者—消費(fèi)者問(wèn)題哲學(xué)家進(jìn)餐問(wèn)題讀者－寫(xiě)者問(wèn)題2.3.4管程機(jī)制

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

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

2.3.4管程機(jī)制

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

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

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

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

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

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

producer:beginrepeatproduceaniteminnextp;p_c.put(nextp);untilfalseendconsumer:beginrepeatp_c.get(nextc);consumetheiteminnextc;untilfalseend2.4進(jìn)程通信

2.4.1進(jìn)程通信分類(lèi)高級(jí)通信機(jī)制可分為三大類(lèi)：1．共享存儲(chǔ)器系統(tǒng)

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

3．管道通信

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

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

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

(3)確定對(duì)方是否存在，只有確定了對(duì)方已存在時(shí)，才能進(jìn)行通信。2.4.2消息傳遞系統(tǒng)1、消息緩沖機(jī)制（1）消息緩沖區(qū)消息緩沖區(qū)由操作系統(tǒng)負(fù)責(zé)管理，每個(gè)消息緩沖區(qū)存放一個(gè)消息，消息緩沖區(qū)的數(shù)據(jù)結(jié)構(gòu)：TypemessageBuffer=recordsender:integer;//發(fā)送消息的進(jìn)程標(biāo)識(shí)符size:integer;//消息長(zhǎng)度text:string;//消息正文next:pointer;//指向下一個(gè)消息緩沖區(qū)的指針End2.4.2消息傳遞機(jī)制（2）進(jìn)程PCB中有關(guān)數(shù)據(jù)項(xiàng)TypePCB=record…mutex:semaphore;//消息隊(duì)列互斥信號(hào)量，初值為1sm:semaphore;//消息隊(duì)列中消息個(gè)數(shù)信號(hào)量，初值為0mq:pointer;