運(yùn)籌學(xué)第3章課件

§3.1進(jìn)程的概念§3.2進(jìn)程的描述§3.3進(jìn)程狀態(tài)及其轉(zhuǎn)換§3.4進(jìn)程控制§3.5進(jìn)程互斥§3.6進(jìn)程同步§3.7進(jìn)程通信§3.8死鎖問題§3.9線程本章小結(jié)本章內(nèi)容進(jìn)程管理第三章1進(jìn)程的定義和特征進(jìn)程的同步和互斥用信號(hào)量機(jī)制解決進(jìn)程同步、互斥、前趨圖問題

進(jìn)程死鎖本章重點(diǎn)和難點(diǎn)：2§3.1進(jìn)程的概念問題：如何充分準(zhǔn)確地反映現(xiàn)代操作系統(tǒng)程序并發(fā)性、資源共享性、用戶隨機(jī)性？需要：1、準(zhǔn)確細(xì)致地描述計(jì)算機(jī)程序的執(zhí)行過程2、更加精準(zhǔn)貼切的資源分配的基本單位3前趨圖概念：前趨圖是一個(gè)有向無環(huán)圖。要求每個(gè)結(jié)點(diǎn)可用于表示一條語句、一個(gè)程序段等結(jié)點(diǎn)間的有向邊表示在兩個(gè)結(jié)點(diǎn)之間存在的前趨關(guān)系如果(pi，pj)可寫成pi—>pj，稱pi是pj的前驅(qū)，而pj是pi的直接后繼。51234567存在下面的前驅(qū)關(guān)系：P1->P2，P1->P3；P1->P4；P2->P5；P3->P5；P5->P7;P4->P6,P6->P7或表示為：P＝{P1,P2,P3,P4,P5,P6,P7}={(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,p5),(P4,P6),(P5,P7),(P6,P7)}前趨圖（續(xù)1）6注意：前驅(qū)圖中不存在循環(huán)。如：S2S3

，

S3S2

顯然這種前驅(qū)關(guān)系是不可能滿足的，S3的執(zhí)行要依賴于S2的執(zhí)行結(jié)果，S2的執(zhí)行結(jié)果又要依賴于S3的執(zhí)行結(jié)果，這種程序是不可能執(zhí)行下去的。

前趨圖（續(xù)2）73.1.1程序的并發(fā)執(zhí)行程序的順序執(zhí)行CPU是通過時(shí)序脈沖來控制順序執(zhí)行指令。其執(zhí)行過程可以描述為：RepeatIR←M［pc］

pc←pc+1〈Execute(instructioninIR)〉UntilCPUhaltIR：指令寄存器，pc：程序計(jì)數(shù)器，M：存儲(chǔ)器。82.多道程序系統(tǒng)中程序執(zhí)行環(huán)境的變化現(xiàn)代OS均支持多個(gè)程序并發(fā)運(yùn)行。須具有下述三個(gè)特點(diǎn)：(1)獨(dú)立性-各程序邏輯上獨(dú)立的，之間無邏輯上的制約關(guān)系。(2)隨機(jī)性-在多道程序環(huán)境下，特別是在多用戶環(huán)境下，程序和數(shù)據(jù)的輸入與執(zhí)行的開始時(shí)間都是隨機(jī)的。(3)資源共享——資源共享將導(dǎo)致對(duì)進(jìn)程執(zhí)行速度的制約。硬件資源：CPU、輸入輸出設(shè)備，存儲(chǔ)器軟件資源：各種例行程序、各種共享的數(shù)據(jù)1、多道程序環(huán)境下執(zhí)行程序的道數(shù)>計(jì)算機(jī)系統(tǒng)中CPU的個(gè)數(shù)2、單CPU中，則由N－1道程序處在等待CPU的狀態(tài)；3、輸入輸出設(shè)備有限將導(dǎo)致這些設(shè)備被共享、內(nèi)存有限將導(dǎo)致內(nèi)存被共享

113.程序的并發(fā)執(zhí)行

I1I2I4I3C1C2C3P1C4P4P3P2程序并發(fā)執(zhí)行時(shí)的前驅(qū)圖12(1)什么是程序的并發(fā)執(zhí)行簡(jiǎn)單解釋：交替操作技術(shù)。目的：增強(qiáng)計(jì)算機(jī)系統(tǒng)處理能力、提高資源利用率分為兩種情形：第一，多道程序系統(tǒng)的程序執(zhí)行環(huán)境變化所引起的多道程序的并發(fā)執(zhí)行（宏觀上是同時(shí)進(jìn)行微觀上仍是順序執(zhí)行）。第二，在某道程序的幾個(gè)程序段中（例如幾個(gè)程序），包含著一部分可以同時(shí)執(zhí)行或順序顛倒執(zhí)行的代碼。例如語句：read(a)；read(b)；同時(shí)執(zhí)行不會(huì)改變順序程序所具有的邏輯性質(zhì)。14邏輯上互相獨(dú)立的程序或程序段在執(zhí)行過程中，其執(zhí)行時(shí)間在客觀上互相重疊，即一個(gè)程序段的執(zhí)行尚未結(jié)束，另一個(gè)程序段的執(zhí)行已經(jīng)開始。程序的并行執(zhí)行：指一組程序按獨(dú)立的、異步的速度執(zhí)行。并行執(zhí)行不等于時(shí)間上的重疊。并發(fā)執(zhí)行過程描述為：程序的并發(fā)科學(xué)定義

S0 Cobegin P1；P2；...Pn CoendSnP1，P2，…，Pn也可由同一程序段中的不同語句組成15Bernstein提出兩相鄰語句S1，S2可并發(fā)執(zhí)行條件：將程序中任一語句Si劃分為兩個(gè)變量的集合

R(Si)和W(Si)R(Si)={a1a2…am}，aj(j=1，…，m)是語句Si在執(zhí)行期間必須對(duì)其進(jìn)行參考的變量集合；W(Si)={b1b2…bn}，bj(j=1，…，n)是語句Si在執(zhí)行期間必須對(duì)其進(jìn)行修改、訪問的變量集合；16如果對(duì)于語句S1和S2，須有①R(S1)∩W(S2)={φ}，②W(S1)∩R(S2)={φ}，③W(S1)∩W(S2)={φ}同時(shí)成立，則語句S1和S2是可以并發(fā)執(zhí)行的。改寫：若兩個(gè)程序p1、p2能滿足下述條件，他們便能并發(fā)執(zhí)行，且具有可再現(xiàn)性。R(p1)∧W(p2)∨R(p2)∧W(p1)∨W(p1)∧W(p2)=φ17例：若有兩條語句Ci＝a－b和Wi＝c＋1，判斷它們是否可以并發(fā)執(zhí)行？

解：它們的“讀集”和“寫集”分別為

R（C：=a－b）={a，b}；R（W：=c＋1）={c}W（C：=a－b）={c}；W（Wi：=c＋1）={w}R（C：=a－b）∩W（Wi:=

c＋1）={Φ}R（W：=c＋1）∩W（C：=a－b）={c}結(jié)論：兩條語句不能并發(fā)執(zhí)行18例：設(shè)有兩個(gè)程序段。getaddr(top)：取內(nèi)存數(shù)據(jù)塊地址；reladdr(blk)：將內(nèi)存數(shù)據(jù)塊地址blk放入堆棧S中。分別描述為：proceduregetaddr(top)begin localr r←(top) top←top-1 return(r)end

procedurereladdr(blk)begin top←top+1 (top)←blkEnd結(jié)論：存在程序的并發(fā)執(zhí)行使得其執(zhí)行結(jié)果不再具有封閉性和可再現(xiàn)性，且可能造成程序出現(xiàn)錯(cuò)誤。getaddr和reladdr程序段進(jìn)行順序執(zhí)行，其執(zhí)行結(jié)果具有封閉性和可再現(xiàn)性。

若采用并發(fā)執(zhí)行，則在單CPU系統(tǒng)中，將有可能出現(xiàn)此種情況：reladdr執(zhí)行未完，getaddr開始并搶占了處理機(jī)。導(dǎo)致getaddr的執(zhí)行結(jié)果失敗。20錯(cuò)誤分析：兩程序段共享堆棧S，使得執(zhí)行結(jié)果受執(zhí)行速度影響（程序員不希望的）。措施：采取適當(dāng)?shù)牟呗灾萍s、控制各并發(fā)程序段的執(zhí)行速度，就是控制和協(xié)調(diào)各程序段執(zhí)行過程中的軟、硬件資源的共享和競(jìng)爭(zhēng)。為此，必須有一個(gè)描述各程序段執(zhí)行過程和共享資源的基本單位。程序——順序性、靜態(tài)性以及孤立性，無法反映操作系統(tǒng)所應(yīng)該具有的程序段執(zhí)行的并發(fā)性、用戶隨機(jī)性，以及資源共享等特征。

引入的對(duì)象——必須能描述程序的執(zhí)行過程且能作為共享資源的基本單位——進(jìn)程。21(1)進(jìn)程,動(dòng)態(tài)概念，程序，靜態(tài)概念。程序是指令的有序集合，沒有任何執(zhí)行的含義。而進(jìn)程則強(qiáng)調(diào)執(zhí)行過程，它動(dòng)態(tài)地被創(chuàng)建，并被調(diào)度執(zhí)行后消亡。(2)進(jìn)程具有并發(fā)特征，而程序沒有。由進(jìn)程的定義可知，進(jìn)程具有并發(fā)特征的兩個(gè)方面，即獨(dú)立性和異步性。即在不考慮資源共享的情況下，各進(jìn)程的執(zhí)行是獨(dú)立的，執(zhí)行速度是異步的。程序不反映執(zhí)行過程，不具有并發(fā)特征。(3)進(jìn)程是競(jìng)爭(zhēng)計(jì)算機(jī)系統(tǒng)資源的基本單位，其并發(fā)性受到系統(tǒng)自己的制約。制約即對(duì)進(jìn)程獨(dú)立性和異步性的限制。(4)不同的進(jìn)程可以包含同一程序，只要該程序所對(duì)應(yīng)的數(shù)據(jù)集不同。（

1個(gè)程序可以對(duì)應(yīng)多個(gè)進(jìn)程，但1個(gè)進(jìn)程只能對(duì)應(yīng)1個(gè)程序）進(jìn)程與程序的區(qū)別233.1.3作業(yè)和進(jìn)程的關(guān)系(1)作業(yè)是用戶向計(jì)算機(jī)提交任務(wù)的任務(wù)實(shí)體。在用戶向計(jì)算機(jī)提交作業(yè)之后，系統(tǒng)將它放入外存中的作業(yè)等待隊(duì)列中等待執(zhí)行。而進(jìn)程則是完成用戶任務(wù)的執(zhí)行實(shí)體，是向系統(tǒng)申請(qǐng)分配資源的基本單位。任一進(jìn)程，只要它被創(chuàng)建，總有相應(yīng)的部分存在于內(nèi)存中。(2)一個(gè)作業(yè)可由多個(gè)進(jìn)程組成。且必須至少由一個(gè)進(jìn)程組成，但反過來不成立。(3)作業(yè)的概念主要用在批處理系統(tǒng)中。而進(jìn)程的概念則用在幾乎所有的多道系統(tǒng)中。243.2.1進(jìn)程控制塊PCB創(chuàng)建一個(gè)進(jìn)程時(shí)，應(yīng)首先創(chuàng)建其PCB：反映各并發(fā)進(jìn)程間的制約關(guān)系和資源共享關(guān)系。當(dāng)一個(gè)進(jìn)程完成其功能之后，系統(tǒng)則釋放PCB，進(jìn)程也隨之消亡。進(jìn)程的PCB所包含的內(nèi)容基本內(nèi)容：(1)描述信息①進(jìn)程名或進(jìn)程標(biāo)識(shí)號(hào)②用戶名或用戶標(biāo)識(shí)號(hào)③家族關(guān)系26(2)控制信息①進(jìn)程當(dāng)前狀態(tài)就緒態(tài)、執(zhí)行態(tài)和等待狀態(tài)。②進(jìn)程優(yōu)先級(jí)選取進(jìn)程占有處理機(jī)的重要依據(jù)。與進(jìn)程優(yōu)先級(jí)有關(guān)的PCB表項(xiàng)有：a.占有CPU時(shí)間；b.進(jìn)程優(yōu)先級(jí)偏移；c.占據(jù)內(nèi)存時(shí)間。③程序開始地址④各種計(jì)時(shí)信息給出進(jìn)程占有和利用資源的有關(guān)情況。⑤通信信息通信信息用來說明該進(jìn)程在執(zhí)行過程中與別的進(jìn)程所發(fā)生的信息交換情況。27(3)資源管理信息①占用內(nèi)存大小及其管理用數(shù)據(jù)結(jié)構(gòu)指針（進(jìn)程頁表指針）。②復(fù)雜系統(tǒng)中，還有對(duì)換或覆蓋用的有關(guān)信息，如對(duì)換程序段長(zhǎng)度，對(duì)換外存地址等。這些信息在進(jìn)程申請(qǐng)、釋放內(nèi)存中使用。③共享程序段大小及起始地址。④輸入輸出設(shè)備的設(shè)備號(hào)，所要傳送的數(shù)據(jù)長(zhǎng)度、緩沖區(qū)地址、緩沖區(qū)長(zhǎng)度及所用設(shè)備的有關(guān)數(shù)據(jù)結(jié)構(gòu)指針等。這些信息在進(jìn)程申請(qǐng)釋放設(shè)備進(jìn)行數(shù)據(jù)傳輸中使用。⑤指向文件系統(tǒng)的指針及有關(guān)標(biāo)識(shí)等。進(jìn)程可使用這些信息對(duì)文件系統(tǒng)進(jìn)行操作。283.2.2進(jìn)程上下文進(jìn)程上下文：進(jìn)程執(zhí)行活動(dòng)全過程的靜態(tài)描述。包括計(jì)算機(jī)系統(tǒng)中與執(zhí)行該進(jìn)程有關(guān)的各種寄存器的值、程序段在經(jīng)過編譯之后形成的機(jī)器指令代碼集（或稱正文段）、數(shù)據(jù)集及各種堆棧值和PCB結(jié)構(gòu)(圖3.2)。這里，有關(guān)寄存器和棧區(qū)的內(nèi)容是重要的。例如，沒有程序計(jì)數(shù)器PC和程序狀態(tài)寄存器PS，CPU將無法知道下條待執(zhí)行指令的地址和控制有關(guān)操作。30圖3.2進(jìn)程上下文結(jié)構(gòu)31進(jìn)程切換：新老進(jìn)程的上下文發(fā)生轉(zhuǎn)換。在UNIXSystemⅤ中，進(jìn)程上下文由用戶級(jí)、寄存器級(jí)、系統(tǒng)級(jí)上下文組成。用戶級(jí)：用戶正文段、用戶數(shù)據(jù)、用戶棧等組成。寄存器級(jí)：由程序寄存器PC、處理機(jī)狀態(tài)字寄存器PS、棧指針和通用寄存器的值組成。系統(tǒng)級(jí)：靜態(tài)部分與動(dòng)態(tài)部分。動(dòng)態(tài)：進(jìn)程進(jìn)入和退出不同的上下文層次時(shí)，系統(tǒng)為各層上下文中相關(guān)聯(lián)的寄存器值所保存和恢復(fù)的記錄。靜態(tài)：包括PCB結(jié)構(gòu)、虛地址空間映射到物理空間用的有關(guān)表格和核心棧32圖3.3UNIXSystemⅤ進(jìn)程上下文組成系統(tǒng)級(jí)上下文的動(dòng)態(tài)部分是與寄存器上下文相關(guān)聯(lián)的333.2.3進(jìn)程空間進(jìn)程空間的大小只與處理機(jī)的位數(shù)有關(guān)。16位：空間大小為216，32：進(jìn)程空間大小為232。用戶程序、進(jìn)程的各種控制表格等都按一定的結(jié)構(gòu)排列在進(jìn)程空間中。另外，在UNIX以及Linux等操作系統(tǒng)中，進(jìn)程空間還被劃分為用戶空間和系統(tǒng)空間兩大部分。

圖3.4進(jìn)程空間34§3.3進(jìn)程狀態(tài)及其轉(zhuǎn)換3.3.1進(jìn)程狀態(tài)就緒狀態(tài)、執(zhí)行狀態(tài)、等待狀態(tài)。就緒狀態(tài)：擁有除CPU之外的其他資源；分配到處

理機(jī)后，便可立即投入運(yùn)行；執(zhí)行狀態(tài)：進(jìn)程正在處理機(jī)上運(yùn)行的狀態(tài)。該進(jìn)程已

獲得必要的資源和處理機(jī)注：只有處于就緒狀態(tài)的進(jìn)程經(jīng)調(diào)度選中之后才可進(jìn)入執(zhí)行狀態(tài)。等待狀態(tài)：（阻塞狀態(tài)）進(jìn)程等待某種事件完成（例如，等待輸入/輸出操作的完成）而暫時(shí)不能運(yùn)行的狀態(tài)。處于該狀態(tài)的進(jìn)程不能參加競(jìng)爭(zhēng)處理機(jī)，此時(shí)，即使分配給它處理機(jī)，它也不能運(yùn)行。35進(jìn)程調(diào)度程序把處理機(jī)分配給進(jìn)程狀態(tài)變化：（1）就緒狀態(tài)變化到運(yùn)行狀態(tài)。（2）運(yùn)行狀態(tài)變化到就緒狀態(tài)。

（3）運(yùn)行狀態(tài)變化到等待狀態(tài)。

（4）等待狀態(tài)變化到就緒狀態(tài)3.3.2進(jìn)程狀態(tài)轉(zhuǎn)換圖3.5進(jìn)程狀態(tài)轉(zhuǎn)換36進(jìn)程狀態(tài)轉(zhuǎn)換運(yùn)行就緒等待圖2－4進(jìn)程的狀態(tài)及其轉(zhuǎn)換371)活動(dòng)就緒→靜止就緒2)活動(dòng)阻塞→靜止阻塞3)靜止就緒→活動(dòng)就緒4)靜止阻塞→活動(dòng)阻塞5)執(zhí)行→靜止就緒。6)靜止阻塞→靜止就緒狀態(tài)轉(zhuǎn)換細(xì)分進(jìn)程的掛起掛起：暫時(shí)被淘汰出內(nèi)存（資源不足）。當(dāng)條件允許時(shí)，再次調(diào)回內(nèi)存，重新進(jìn)入就緒態(tài)。

引起掛起狀態(tài)的原因有如下幾方面：

（1）終端用戶的請(qǐng)求。當(dāng)終端用戶在自己的程序運(yùn)行期間發(fā)現(xiàn)有可疑問題時(shí)，希望暫停使自己的程序靜止下來。亦即，使正在執(zhí)行的進(jìn)程暫停執(zhí)行；若此時(shí)用戶進(jìn)程正處于就緒狀態(tài)而未執(zhí)行，則該進(jìn)程暫不接受調(diào)度，以便用戶研究其執(zhí)行情況或?qū)Τ绦蜻M(jìn)行修改。我們把這種靜止?fàn)顟B(tài)成為“掛起狀態(tài)”。

（2）父進(jìn)程的請(qǐng)求。有時(shí)父進(jìn)程希望掛起自己的某個(gè)子進(jìn)程，以便考察和修改子進(jìn)程，或者協(xié)調(diào)各子進(jìn)程間的活動(dòng)。

（3）負(fù)荷調(diào)節(jié)的需要。當(dāng)實(shí)時(shí)系統(tǒng)中的工作負(fù)荷較重，已可能影響到對(duì)實(shí)時(shí)任務(wù)的控制時(shí)，可由系統(tǒng)把一些不重要的進(jìn)程掛起，以保證系統(tǒng)能正常運(yùn)行。

（4）操作系統(tǒng)的需要。操作系統(tǒng)有時(shí)希望掛起某些進(jìn)程，以便檢查運(yùn)行中的資源使用情況或進(jìn)行記賬38§3.4進(jìn)程控制進(jìn)程控制——系統(tǒng)使用一些具有特定功能的程序段來創(chuàng)建、撤消進(jìn)程以及完成進(jìn)程各狀態(tài)間的轉(zhuǎn)換，從而達(dá)到多進(jìn)程高效率并發(fā)執(zhí)行和協(xié)調(diào)、實(shí)現(xiàn)資源共享的目的。

一般地，把系統(tǒng)態(tài)下執(zhí)行的某些具有特定功能的程序段稱為原語——分為兩類機(jī)器指令級(jí)：執(zhí)行期間不允許中斷，它是一個(gè)

不可分割的基本單位。功能級(jí)：作為原語的程序段不允許并發(fā)執(zhí)行。39進(jìn)程控制的原語：創(chuàng)建原語、撤消原語、阻塞原語、喚醒原語等。為何用原語？1、保證封閉性和可再現(xiàn)性；2、減少系統(tǒng)開銷，降低系統(tǒng)復(fù)雜度。用程序段做成原語。403.4.1進(jìn)程創(chuàng)建與撤消1.進(jìn)程創(chuàng)建(1)由系統(tǒng)程序模塊統(tǒng)一創(chuàng)建。例如在批處理系統(tǒng)中，由操作系統(tǒng)的作業(yè)調(diào)度程序?yàn)橛脩糇鳂I(yè)創(chuàng)建相應(yīng)的進(jìn)程以完成用戶作業(yè)所要求的功能。進(jìn)程之間的關(guān)系是平等(2)由父進(jìn)程創(chuàng)建。如在層次結(jié)構(gòu)的系統(tǒng)中；進(jìn)程之間有隸屬關(guān)系，構(gòu)成樹型結(jié)構(gòu)。屬于某個(gè)家族的一個(gè)進(jìn)程可以繼承其父進(jìn)程所擁有的資源。（3）系統(tǒng)資源分配和管理工作的系統(tǒng)進(jìn)程，須由操作系統(tǒng)創(chuàng)建。（4）實(shí)現(xiàn)：創(chuàng)建原語—>掃描PCB鏈表調(diào)用者提供的有關(guān)參數(shù)填入空PCB表—>PCB結(jié)構(gòu)。進(jìn)程名\進(jìn)程優(yōu)先級(jí)\進(jìn)程正文段起始地址\資源清單

其實(shí)現(xiàn)過程如圖3.6。4142圖3.6創(chuàng)建原語流圖2.進(jìn)程撤消導(dǎo)致進(jìn)程被撤消的情形：(1)進(jìn)程完成任務(wù)正常終止。(2)由于某種錯(cuò)誤導(dǎo)致非正常終止。(3)祖先進(jìn)程要求撤消某子進(jìn)程。實(shí)現(xiàn)：撤消原語—>檢查PCB進(jìn)程鏈—>找進(jìn)程的PCB結(jié)構(gòu)—>釋放資源、

從PCB進(jìn)程鏈摘下PCB結(jié)構(gòu)—>歸還PCB空隊(duì)列；

注：先考慮子進(jìn)程的撤銷（原理同）。創(chuàng)建原語和撤消原語：完成進(jìn)程從無到有，從存在到消亡的變化。43圖3.7撤消原語流圖443.4.2進(jìn)程的阻塞與喚醒1、被創(chuàng)建后的進(jìn)程最初處于2、經(jīng)調(diào)度程序選中后進(jìn)入3、阻塞原語：a\進(jìn)程期待某事件發(fā)生，被該進(jìn)程自己調(diào)用阻塞自己。b\阻塞進(jìn)程過程：首先，中斷處理機(jī)和保存CPU現(xiàn)場(chǎng)；其次，將被阻塞進(jìn)程置“阻塞”狀態(tài)后插入等待隊(duì)列；然后，調(diào)度程序選擇新的就緒進(jìn)程投入運(yùn)行（避免處

理機(jī)空閑）。45就緒狀態(tài)；執(zhí)行狀態(tài)；執(zhí)行狀態(tài)；等待狀態(tài)；圖3.8阻塞原語圖464、喚醒原語1）事件發(fā)生進(jìn)程被喚醒；2）喚醒進(jìn)程的兩種方法：a系統(tǒng)進(jìn)程喚醒：系統(tǒng)進(jìn)程統(tǒng)一控制事件的發(fā)生，將消息通知等待進(jìn)程進(jìn)入就緒隊(duì)列。b事件發(fā)生進(jìn)程喚醒;3)過程：首先，喚醒原語將被喚醒進(jìn)程從等待隊(duì)列中摘下；其次，被喚醒進(jìn)程置為就緒狀態(tài)之后，送入就緒隊(duì)列；然后，返回原調(diào)用程序，或轉(zhuǎn)向進(jìn)程調(diào)度.47等待狀態(tài)；就緒狀態(tài)；圖3.9喚醒原語48§3.5進(jìn)程互斥3.5.1資源共享所引起的制約分析進(jìn)程的并發(fā)執(zhí)行的原因：1）用戶程序的執(zhí)行開始時(shí)間的隨機(jī)性；2）提高資源利用率的需要3）資源有限性導(dǎo)致資源的競(jìng)爭(zhēng)、共享對(duì)進(jìn)程的執(zhí)行過程的制約。臨界區(qū)分析賦值語句： X=X+1；匯編語言書寫：LOADA，XADDIA，1STOREA，X三語句執(zhí)行期間，發(fā)生中斷？原因：執(zhí)行速度和對(duì)資源競(jìng)爭(zhēng)失控。結(jié)果：錯(cuò)49設(shè)有兩個(gè)計(jì)算進(jìn)程ＰA，ＰB共享內(nèi)存ＭS。其中ＭS分為三個(gè)領(lǐng)域，即系統(tǒng)區(qū)、進(jìn)程工作區(qū)和數(shù)據(jù)區(qū)（如圖3.10）。圖3.10多進(jìn)程共享內(nèi)存棧區(qū)示例50分析：1、ＰA或ＰB

取空（getspace）數(shù)據(jù)塊時(shí)：從棧取數(shù)據(jù)塊位置；2、ＰA或ＰB釋放（release(ad)）數(shù)據(jù)塊時(shí)：將釋放數(shù)據(jù)塊地址入棧頂；這里，ad為待釋放數(shù)據(jù)塊的地址。3、若棧Ｓ非空，ＰA或ＰB可以用任意順序釋放和獲取數(shù)據(jù)塊。4、下面的描述，在進(jìn)程并發(fā)執(zhí)行時(shí)，getspace或release(ad)將有可能完不成所要求的功能。getspace和release(ad)可進(jìn)一步描述為：51 getspace: begin local g g←stack［top］

top←top-1 end release(ad): begin top←top+1 stack［top］←ad end設(shè)時(shí)刻t0時(shí)，top=h0，則getspace和release(ad)可能按以下順序執(zhí)行：首先：

release(ad)的第一句執(zhí)行，

t0：top←top+1 → top=h0+1；其次：getspace執(zhí)行，得：52t1：g←stack［top］→g=stack［h0+1］；t2：top←top-1 → top=h0；然后：release(ad)的第二句執(zhí)行，得：t3：stack［top］←ad→stack［h0］←ad；分析結(jié)果：1、調(diào)用getspace進(jìn)程，取到一個(gè)未定義值；2、調(diào)用release(ad)進(jìn)程把所釋放的空塊地址ad放入了h0中，覆蓋了h0中的內(nèi)容。如何保證執(zhí)行結(jié)果的正確性？把getspace和release(ad)：兩個(gè)各以一個(gè)動(dòng)作完成的順序執(zhí)行單位。臨界區(qū)（criticalregion）定義：不允許多個(gè)并發(fā)進(jìn)程交叉執(zhí)行的一段程序。由于它由屬于不同并發(fā)進(jìn)程的程序段共享公用數(shù)據(jù)或公用數(shù)據(jù)變量而引起的。故也被稱為訪問公用數(shù)據(jù)的那段程序。532.間接制約令不允許交叉執(zhí)行的臨界區(qū)按不同的公用數(shù)據(jù)劃分為不同的類（class）。如：以公用數(shù)據(jù)棧Ｓ劃分的臨界區(qū)集合是{getspace,release}。對(duì)類給定一個(gè)唯一的標(biāo)識(shí)名，系統(tǒng)容易區(qū)分。在程序的描述中，可用下列標(biāo)準(zhǔn)形式來描述臨界區(qū)：

when〈類名〉do〈臨界區(qū)〉od設(shè)類{getspace，release}的類名為sp，則getspace和release(ad)可重新描述為：

getspace: whenspdogetspce←stack［top］

top←top-1od release(ad):whenspdotop←top+1 stack［top］←adod54間接制約含義：

1、由于共享某一公有資源而引起的在臨界區(qū)內(nèi)不允許并發(fā)進(jìn)程交叉執(zhí)行的現(xiàn)象，稱為由共享公有資源而造成的對(duì)并發(fā)進(jìn)程執(zhí)行速度的間接制約，簡(jiǎn)稱間接制約。2、“間接”二字主要是指各并發(fā)進(jìn)程的速度受公有資源制約，非進(jìn)程間直接制約。3、受間接制約的類中各程序段在執(zhí)行順序上是任意的。

對(duì)于每一類，系統(tǒng)都有相應(yīng)的分配和釋放相應(yīng)公有資源的管理辦法，以制約并發(fā)進(jìn)程。這就是互斥。553.什么是互斥1、定義：一組并發(fā)進(jìn)程中的一個(gè)或多個(gè)程序段，因共享某一公有資源而導(dǎo)致它們必須以一個(gè)不允許交叉執(zhí)行的單位。2、不允許兩個(gè)以上的共享該資源的并發(fā)進(jìn)程同時(shí)進(jìn)入臨界區(qū)稱為互斥。一般情況下，作為程序段的一個(gè)過程不允許多個(gè)進(jìn)程共同訪問它（純過程除外）。純過程：1）在執(zhí)行過程中不改變過程自身代碼的一類過程。2）便于多個(gè)進(jìn)程共享。但編制純過程要對(duì)有關(guān)變量和工作區(qū)作相應(yīng)的處理，使得執(zhí)行效率受到影響。56一組并發(fā)進(jìn)程互斥執(zhí)行時(shí)必須滿足如下準(zhǔn)則：(1)

不能假設(shè)各并發(fā)進(jìn)程的相對(duì)執(zhí)行速度。(2)某個(gè)進(jìn)程不在臨界區(qū)時(shí)，它不阻止其他進(jìn)程進(jìn)入臨界區(qū)。(3)若干個(gè)進(jìn)程申請(qǐng)進(jìn)入臨界區(qū)時(shí)，只能允許一個(gè)進(jìn)程進(jìn)入。(4)進(jìn)程應(yīng)在有限時(shí)間內(nèi)得以進(jìn)入臨界區(qū)。

準(zhǔn)則(1)，(2)，(3)：保證各并發(fā)進(jìn)程享有平等的、獨(dú)立的競(jìng)爭(zhēng)和使用公有資源的權(quán)利，且保證每一時(shí)刻至多只有一個(gè)進(jìn)程在臨界區(qū)；準(zhǔn)則(4)：并發(fā)進(jìn)程不發(fā)生死鎖的重要保證。競(jìng)爭(zhēng)公有資源間接制約進(jìn)程互斥共享私有資源直接制約進(jìn)程同步。573.5.2互斥的加鎖實(shí)現(xiàn)推想：把臨界區(qū)中的各個(gè)過程按不同時(shí)間排列調(diào)用。須做到：每個(gè)進(jìn)程事先知道其他并發(fā)進(jìn)程與系統(tǒng)的動(dòng)作。不可能：用戶程序執(zhí)行的隨機(jī)性決定的。辦法：對(duì)臨界區(qū)加鎖。58設(shè)Ｓ:臨界區(qū)類名,

key［Ｓ］:鎖定位。加鎖后的臨界區(qū)程序描述如下：

lock(key［Ｓ］) 〈臨界區(qū)〉 unlock(key［Ｓ］)key［Ｓ］=1：臨界區(qū)可用key［Ｓ］=0：不可用。unlock(key［Ｓ］)只用一條語句即可實(shí)現(xiàn)。即：

key［Ｓ］←1lock(key［Ｓ］)須滿足key［Ｓ］=0時(shí)，不允許任何進(jìn)程進(jìn)入臨界區(qū)，而key［Ｓ］=1時(shí)僅允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)的準(zhǔn)則，實(shí)現(xiàn)起來較為困難。59一種簡(jiǎn)便的實(shí)現(xiàn)方法是：

lock(x)beginlocalv repeat v←x untilv=1 x←0 end缺點(diǎn)：不能保證并發(fā)進(jìn)程互斥執(zhí)行所要求的準(zhǔn)則(3)。因?yàn)椋和瑫r(shí)有幾個(gè)進(jìn)程調(diào)用lock(key［Ｓ］)時(shí)，在x←0語句執(zhí)行之前，可能已有兩個(gè)以上進(jìn)程由于key［Ｓ］=1而進(jìn)入臨界區(qū)。解決：硬件設(shè)置“測(cè)試與設(shè)置指令”，保證第一步和第二步執(zhí)行不可分離。注意：在系統(tǒng)實(shí)現(xiàn)時(shí)鎖定位key［Ｓ］總是設(shè)置在公有資源所對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)中的。603.5.3信號(hào)量和Ｐ，Ｖ原語信號(hào)量（semaphore）分析加鎖實(shí)現(xiàn)進(jìn)程之間互斥？缺點(diǎn)：1）循環(huán)測(cè)試鎖定位，

犧牲CPU時(shí)間；進(jìn)程多，開銷大；存在一些影響系統(tǒng)可靠性和執(zhí)行效率的問題。2）會(huì)導(dǎo)致不公平現(xiàn)象；舉例：進(jìn)程PA和PB反復(fù)使用臨界區(qū)

PA A：lock(key［Ｓ］) 〈Ｓ〉61 unlock(key［Ｓ］) GotoA PB B：lock(key［Ｓ］)

＜Ｓ＞

unlock(key［Ｓ］) GotoB分析：只有PA執(zhí)行完unlock(key［Ｓ］)之后、執(zhí)行GotoA語句之前的瞬間發(fā)生進(jìn)程調(diào)度，使PA

讓出處理機(jī)給PB，PB才有可能得到執(zhí)行。這顯然不太可能。所以，PB

將永遠(yuǎn)處于饑餓（starvation）原因：能否進(jìn)入臨界區(qū)是依靠自己的測(cè)試判斷決定。舉例：學(xué)生使用教室解決：引入信號(hào)量機(jī)制（教室管理員：信號(hào)量）62信號(hào)量的含義1、荷蘭科學(xué)家E.W.Dijkstra提出來的；2、信號(hào)量sem是一整數(shù)（初值>0）

a、sem>=0,資源實(shí)體數(shù)b、sem<0,正在等待使用臨界區(qū)的進(jìn)程數(shù);

3、建立一個(gè)信號(hào)量須做到a、說明所建信號(hào)量所代表的意義b、賦初值c、建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)（指向等待使用臨界區(qū)的進(jìn)程）。632.Ｐ，Ｖ原語1）含義：信號(hào)量的數(shù)值僅能由Ｐ，Ｖ原語操作改變Ｐ|Ｖ分別是荷蘭語Passeren和Verhoog的頭字母;相當(dāng)于英文的pass和increment的意思2）過程：采用Ｐ，Ｖ原語，可以把類名為Ｓ的臨界區(qū)描述為WhenＳdoＰ(sem)臨界區(qū)Ｖ(sem)od。A、一次Ｐ原語操作：sem減1；B、一次Ｖ原語操作：sem加1。C、若某進(jìn)程正在臨界區(qū)內(nèi)執(zhí)行時(shí)，其他進(jìn)程如果執(zhí)行了Ｐ操作，則該進(jìn)程將在等待隊(duì)列中等待（不同于加鎖），直到其他進(jìn)程做Ｖ操作后，進(jìn)入臨界區(qū)（可能繼續(xù)等待），Ｐ原語的執(zhí)行真正結(jié)束。643）Ｐ原語的主要?jiǎng)幼鳎?1)sem減1；(2)若sem減1后仍大于或等于零，則進(jìn)程繼續(xù)執(zhí)行；若sem減1后小于零，則該進(jìn)程被阻塞后入該信號(hào)相對(duì)應(yīng)的隊(duì)列中等待，然后轉(zhuǎn)進(jìn)程調(diào)度。4）Ｖ原語的操作主要?jiǎng)幼鳎?1)sem加1；(2)若相加結(jié)果大于零，進(jìn)程繼續(xù)執(zhí)行；(3)若相加結(jié)果小于或等于零，則從該信號(hào)的等待隊(duì)列中喚醒一等待進(jìn)程，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。65圖3.11Ｐ原語操作流程3.12Ｖ原語操作流程分析：PV過程若不用原語實(shí)現(xiàn)，怎樣？多進(jìn)程同時(shí)調(diào)用Ｐ或Ｖ操作，有可能在Ｐ操作剛把sem-1而未把對(duì)應(yīng)進(jìn)程送入等待隊(duì)列時(shí)，Ｖ操作開始執(zhí)行。從而，Ｖ操作將無法發(fā)現(xiàn)等待進(jìn)程而返回。結(jié)論：Ｐ，Ｖ操作都必須以原語實(shí)現(xiàn)，且在Ｐ，Ｖ原語執(zhí)行期間不允許中斷發(fā)生。66?!使用加鎖法的P、V原語軟件實(shí)現(xiàn)方法: Ｐ（sem）：

begin

封鎖中斷；

lock(lockbit) val［sem］=val［sem］-1 ifval［sem］<0

保護(hù)當(dāng)前進(jìn)程CPU現(xiàn)場(chǎng) 當(dāng)前進(jìn)程狀態(tài)置為″等待″

將當(dāng)前進(jìn)程插入信號(hào)sem等待隊(duì)列 轉(zhuǎn)進(jìn)程調(diào)度

fi unlock(lockbit)；開放中斷

end67Ｖ（sem）：

begin

封鎖中斷；

lock(lockbit) va［sem］=val［sem］+1 ifval［sem］≤0 localk

從sem等待隊(duì)列中選取一等待進(jìn)程，將

其指針置入k中 將k插入就緒隊(duì)列 進(jìn)程狀態(tài)置“就緒”

fi unlock(lockbit)；開放中斷end使用加鎖法的P、V原語軟件實(shí)現(xiàn)方法(續(xù)):683.5.4用Ｐ，Ｖ原語實(shí)現(xiàn)進(jìn)程互斥用信號(hào)量實(shí)現(xiàn)兩并發(fā)進(jìn)程PA，PB互斥的描述如下：sem：互斥信號(hào)量，值范圍為(1,0,-1)。A、sem=1表示進(jìn)程PA和PB都未進(jìn)入類名為Ｓ的臨界區(qū)B、sem=0表示進(jìn)程PA或PB已進(jìn)入類名為Ｓ的臨界區(qū)C、sem=-1表示進(jìn)程PA和PB中，一個(gè)進(jìn)程已進(jìn)入臨界區(qū)，而另一個(gè)進(jìn)程等待進(jìn)入臨界區(qū)。2)描述：

PA： Ｐ(sem) 〈Ｓ〉

Ｖ(sem)： ：

69PB： Ｐ(sem) 〈Ｓ〉

Ｖ(sem)：

：舉例9：生產(chǎn)圍棋的工人不小心把相等數(shù)量的黑子和白子混裝載一個(gè)箱子里，現(xiàn)要用自動(dòng)分揀系統(tǒng)把黑子和白子分開，該系統(tǒng)由兩個(gè)并發(fā)執(zhí)行的進(jìn)程組成，功能如下：

（1）進(jìn)程A專門揀黑子，進(jìn)程B專門揀白子；

（2）每個(gè)進(jìn)程每次只揀一個(gè)子，當(dāng)一個(gè)進(jìn)程在揀子時(shí)不允許另一個(gè)進(jìn)程去揀子；分析：

第一步：確定進(jìn)程間的關(guān)系。由功能（2）可知進(jìn)程之間是互斥的關(guān)系。

第二步：確定信號(hào)量及其值。由于進(jìn)程A和進(jìn)程B要互斥進(jìn)入箱子去揀棋子，箱子是兩個(gè)進(jìn)程的公有資源，所以設(shè)置一個(gè)信號(hào)量s，其值取決于公有資源的數(shù)目，由于箱子只有一個(gè)，s的初值就設(shè)為1。

70實(shí)現(xiàn)：begin

s:semaphore;s:=1;

cobegin

processA

begin

L1:P(s);

揀黑子；

V(s);

gotoL1;

end;

processB

begin

L2:P(s);

揀白子；

V(s);

gotoL2;

end;coend;

end;

提示：判斷進(jìn)程間是否互斥，關(guān)鍵是看進(jìn)程間是否共享某一公有資源，一個(gè)公有資源與一個(gè)信號(hào)量相對(duì)應(yīng)。確定信號(hào)量的值是一個(gè)關(guān)鍵點(diǎn)，它代表了可用資源實(shí)體數(shù)。71問題：使用P、V原語和加鎖法在實(shí)現(xiàn)并發(fā)進(jìn)程間的互斥時(shí)有何異同?加鎖法是對(duì)臨界區(qū)加鎖以實(shí)現(xiàn)互斥。當(dāng)某個(gè)進(jìn)程進(jìn)入臨界區(qū)后，就鎖定臨界區(qū)直到它退出臨界區(qū)，其他進(jìn)程要進(jìn)入時(shí)，須要不斷測(cè)試臨界區(qū)是否被用著，直到臨界區(qū)空才能進(jìn)入。可靠性、執(zhí)行效率不高。P，V原語操作能改變信號(hào)量的數(shù)值，信號(hào)量（sem）可代表管理相應(yīng)臨界區(qū)公共資源的實(shí)體。當(dāng)sem>=0時(shí)，表示可供并發(fā)進(jìn)程使用的資源實(shí)體數(shù)，當(dāng)sem<0是時(shí)，表示正在等待使用臨界區(qū)的進(jìn)程數(shù)。而一次P操作使得sem減1，一次V操作使得sem加1。

P，V操作中進(jìn)程不需象加鎖時(shí)要不斷的測(cè)試，而是在隊(duì)列里等待其他進(jìn)程執(zhí)行V操作時(shí)，就可以進(jìn)入臨界區(qū)了。這樣P，V操作比加鎖更簡(jiǎn)單，且表達(dá)能力強(qiáng)，但P，V相對(duì)來說不安全，會(huì)出現(xiàn)死鎖，遇復(fù)雜同步互斥問題時(shí)會(huì)更復(fù)雜。72§3.6進(jìn)程同步3.6.1同步的概念已知：間接制約——影響進(jìn)程執(zhí)行速度問題：是否存在著其他制約關(guān)系影響執(zhí)行速度？看下面的例子。計(jì)算進(jìn)程和打印進(jìn)程共同使用同一緩沖區(qū)Buf。計(jì)算進(jìn)程反復(fù)地把每次計(jì)算結(jié)果放入Buf中，而打印進(jìn)程則把計(jì)算進(jìn)程每次放入Buf中的數(shù)據(jù)通過打印機(jī)打印輸出。如果不采取任何制約措施，這兩個(gè)進(jìn)程的執(zhí)行起始時(shí)間和執(zhí)行速度都是彼此獨(dú)立的，其相應(yīng)的控制段可以描述為：73PC

: A: localBuf Repeat Buf←Buf Until Buf=空 計(jì)算 得到計(jì)算結(jié)果

Buf←計(jì)算結(jié)果

Goto APP: : B: localPri Repeat Pri←Buf Until Pri≠空 打印Buf中的數(shù)據(jù) 清除Buf中的數(shù)據(jù)

Goto B分析：1、假設(shè)：兩進(jìn)程對(duì)buf已經(jīng)采取互斥措施；2、存在兩處測(cè)試；

導(dǎo)致CPU時(shí)間的極大浪費(fèi)；3、PC、PP

互相制約；互為條件和結(jié)果；結(jié)論：一組在異步環(huán)境下的并發(fā)進(jìn)程，各自的執(zhí)行結(jié)果互為對(duì)方的執(zhí)行條件，從而限制各進(jìn)程的執(zhí)行速度的過程稱為并發(fā)進(jìn)程間的直接制約。執(zhí)行起始時(shí)間的隨機(jī)性和執(zhí)行速度的獨(dú)立性解決：采用消息機(jī)制。同步進(jìn)程間通過消息的傳遞決定進(jìn)程的運(yùn)行。74同步的定義：

把異步環(huán)境下的一組并發(fā)進(jìn)程，因直接制約而互相發(fā)送消息而進(jìn)行互相合作、互相等待，使得各進(jìn)程按一定的速度執(zhí)行的過程稱為進(jìn)程間的同步。

具有同步關(guān)系的一組并發(fā)進(jìn)程稱為合作進(jìn)程，合作進(jìn)程間互相發(fā)送的信號(hào)稱為消息或事件。過程1：wait(消息名)——等待合作進(jìn)程發(fā)來的消息過程2：signal(消息名)——向合作進(jìn)程發(fā)送消息利用過程wait和signal，可以簡(jiǎn)單地描述上面例子中的計(jì)算進(jìn)程PC和打印進(jìn)程PP的同步關(guān)系如下：75(1)設(shè)消息名Bufempty表示Buf空，消息名Buffull表示Buf中裝滿了數(shù)據(jù)。(2)初始化Bufempty=true，Buffull=false。(3)描述：

PC

：

A: wait(Bufempty)

計(jì)算

Buf←計(jì)算結(jié)果

Bufempty←false signal(Buffull) Goto A等待到消息名為true的進(jìn)程繼續(xù)執(zhí)行向合作進(jìn)程發(fā)送所需要的消息名，并將其值置為true76 PP ：

B: wait(Buffull)

打印Buf中的數(shù)據(jù) 清除Buf中的數(shù)據(jù)

Buffull←false

signal(Bufempty) Goto B

等待到消息名為true的進(jìn)程繼續(xù)執(zhí)行向合作進(jìn)程發(fā)送所需要的消息名，并將其值置為true773.6.2私用信號(hào)量進(jìn)程間的同步的另一實(shí)現(xiàn)方法：信號(hào)量原理：把各進(jìn)程之間發(fā)送的消息作為信號(hào)量；私用信號(hào)量（

PrivateSemaphvre）：僅與制約進(jìn)程及被制約進(jìn)程有關(guān)的。是從制約進(jìn)程發(fā)送來的進(jìn)程Pi的執(zhí)行條件所需要的消息。公用信號(hào)量：互斥時(shí)使用的信號(hào)量。783.6.3用Ｐ，Ｖ原語操作實(shí)現(xiàn)同步Ｐ，Ｖ原語+私用信號(hào)量實(shí)現(xiàn)進(jìn)程同步1、首先，設(shè)置私用信號(hào)量；2、其次，私用信號(hào)量賦初值；3、然后，利用Ｐ，Ｖ原語和私用信號(hào)量規(guī)定各進(jìn)程

的執(zhí)行順序。79例10：設(shè)進(jìn)程PA和PB通過緩沖區(qū)隊(duì)列傳遞數(shù)據(jù)（如圖3.13）。PA為發(fā)送進(jìn)程，PB為接收進(jìn)程。PA發(fā)送數(shù)據(jù)時(shí)調(diào)用發(fā)送過程deposit(data)，PB接收數(shù)據(jù)時(shí)調(diào)用過程remove(data)。且數(shù)據(jù)的發(fā)送和接收過程滿足如下條件：(1)在PA至少送一塊數(shù)據(jù)入一個(gè)緩沖區(qū)之前，PB不可能從緩沖區(qū)中取出數(shù)據(jù)（假定數(shù)據(jù)塊長(zhǎng)等于緩沖區(qū)長(zhǎng)度）；(2)PA往緩沖隊(duì)列發(fā)送數(shù)據(jù)時(shí)，至少有一個(gè)緩沖區(qū)是空的；(3)由PA發(fā)送的數(shù)據(jù)塊在緩沖隊(duì)列中按先進(jìn)先出（FIFO）方式排列。描述發(fā)送過程deposit(data)和接收過程remove(data)。圖3.13緩沖區(qū)隊(duì)列80分析：1、PA調(diào)用的過程deposit(data)和PB調(diào)用的過程remove(data)必須同步執(zhí)行（？）2、分三步描述過程deposit(data)和remove(data)：（1)設(shè)Bufempty為進(jìn)程PA的私用信號(hào)量，Buffull為進(jìn)程PB的私用信號(hào)量；（2)令Bufempty的初始值為n（n為緩沖隊(duì)列的緩沖區(qū)個(gè)數(shù)），Buffull的初始值為0；（3)描述：81PA:deposit(data):beginlocalx/*x:緩沖區(qū)的區(qū)號(hào) P(Bufempty)； 按FIFO方式選擇一個(gè)空緩沖區(qū)Buf(x)；

Buf(x)←data Buf(x)置滿標(biāo)記/*便于區(qū)別和搜索空緩沖區(qū)及

非空緩沖區(qū) Ｖ（Buffull）/*

Buffull置為1，并將消息傳給PB

endPB:remove(data):Beginlocalx

Ｐ（Buffull）； 按FIFO方式選擇一個(gè)裝滿數(shù)據(jù)的緩沖區(qū)Buf(x) data←Buf(x) Buf(x)置空標(biāo)記 Ｖ(Bufempty)end82思考1：在該題中需要考慮互斥嗎？為什么？如果每次只允許一個(gè)進(jìn)程對(duì)緩沖隊(duì)列進(jìn)行操作時(shí)怎么辦？思考2：在例9中，若增加以下條件（3）：（3）當(dāng)一個(gè)進(jìn)程揀了一個(gè)棋子（黑子或白子）以后，必讓另一個(gè)進(jìn)程揀一個(gè)棋子（黑子或白子）

請(qǐng)用P、V原語實(shí)現(xiàn)進(jìn)程操作。833.6.4生產(chǎn)者-消費(fèi)者問題（producer-consumerproblems）概念的產(chǎn)生：同步和互斥問題模型化。生產(chǎn)者：釋放資源的進(jìn)程，如計(jì)算進(jìn)程PC消費(fèi)者：使用同類資源的進(jìn)程，如打印進(jìn)程PP外部設(shè)備、內(nèi)存及緩沖區(qū)、臨界區(qū)、數(shù)據(jù)等84例11把一個(gè)長(zhǎng)度為ｎ的有界緩沖區(qū)（n>0)與一群生產(chǎn)者進(jìn)程Ｐ1，Ｐ2，…，Ｐm和一群消費(fèi)者進(jìn)程Ｃ1，Ｃ2，…，Ｃk聯(lián)系起來（如圖3.14所示）。設(shè)生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程是互相等效的，其中，各生產(chǎn)者進(jìn)程使用的過程deposit(data)和各消費(fèi)者使用的過程remove(data)可描述如下：生產(chǎn)者和消費(fèi)者之間滿足如下條件：(1)消費(fèi)者想接收數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是滿的；(2)生產(chǎn)者想發(fā)送數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是空的。

(3)由于有界緩沖區(qū)是臨界資源，因此，各生產(chǎn)者進(jìn)程和各消費(fèi)者進(jìn)程之間必須互斥執(zhí)行。85圖3.14生產(chǎn)者-消費(fèi)者問題86具有n個(gè)緩沖區(qū)的緩沖池生產(chǎn)者——消費(fèi)者問題871）mutex：公用信號(hào)量；初值1，可用有界緩沖區(qū)個(gè)數(shù)avail：為生產(chǎn)者進(jìn)程私用信號(hào)量，初值為nfull：消費(fèi)者進(jìn)程私用信號(hào)量。初值為0；deposit(data):begin

Ｐ（avail） Ｐ（mutex） 送數(shù)據(jù)入緩沖區(qū)某單元 Ｖ（mutex） Ｖ（full）end88remove(data):beginＰ（full）Ｐ（mutex） 取緩沖區(qū)中某單元數(shù)據(jù)Ｖ（mutex）Ｖ（avail）

end

注：Ｐ、Ｖ原語的操作次序。1、Ｖ原語是以任意次序。2、但Ｐ原語則不然，如果次序混亂，

將會(huì)造成進(jìn)程之間的死鎖。問題：為什么？89P操作順序不當(dāng)會(huì)產(chǎn)生死鎖

例：有執(zhí)行順序如下：Producer:Consumer:P(empty);P(mutex);P(mutex);P(full);Oneunit->buf;Oneunitbuf;V(mutex);V(mutex);V(full);V(full);分析：當(dāng)full=0,mutex=1時(shí)，執(zhí)行順序有：Consumer.P(mutex);Consumer.P(full);//顯然，Consumer阻塞，等待Producer發(fā)出的full信號(hào)；Producer.P(empty);Producer.P(mutex);//顯然，Producer阻塞，等待Consumer發(fā)出的empty信號(hào)；結(jié)果：發(fā)生死鎖！問：還有其他的執(zhí)行序列可以產(chǎn)生死鎖嗎？90P、V小結(jié)1、信號(hào)量的物理含義：

1)S>0表示有S個(gè)資源可用

2)S=0表示無資源可用

3)S<0則|S|表示S等待隊(duì)列中的進(jìn)程個(gè)數(shù)

4)P(S):表示申請(qǐng)一個(gè)資源

5)V(S)表示釋放一個(gè)資源。信號(hào)量的初值應(yīng)該大于等于02、P.V操作必須成對(duì)出現(xiàn)，有一個(gè)P操作就一定有一個(gè)V操作

1)當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程

2)當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn)

3)如果P(S1)和P(S2)兩個(gè)操作在一起，那么P操作的順序至

關(guān)重要,一個(gè)同步P操作與一個(gè)互斥P操作在一起時(shí)同步P操作在互斥P操作前.而兩個(gè)V操作無關(guān)緊要91

1、必須置一次且只能置一次初值

2、初值不能為負(fù)數(shù)

3、只能執(zhí)行P、V操作信號(hào)量的使用92§3.7進(jìn)程通信（communication）含義：進(jìn)程間信息交換（傳送數(shù)據(jù)）。分類：根據(jù)通信內(nèi)容可以劃分為二種。A、低級(jí)通信：進(jìn)程間控制信息的交換（傳送一兩個(gè)

字節(jié)，控制進(jìn)程執(zhí)行速度）信號(hào)量機(jī)制作為同步工具是卓有成效的，但作為通信工具則不夠理想？

（效率低。通信對(duì)用戶不透明。）B、高級(jí)通信：大批量數(shù)據(jù)傳送（為了交換信息）。用戶可以直接利用操作系統(tǒng)所提供的一組通信命令933.7.1進(jìn)程的通信方式在單機(jī)系統(tǒng)中，進(jìn)程間通信可分為4種形式：(1)主從式；(2)會(huì)話式；(3)消息或郵箱機(jī)制；(4)共享存儲(chǔ)區(qū)方式。主從式特點(diǎn)：①主進(jìn)程可自由地使用從進(jìn)程的資源或數(shù)據(jù)；②從進(jìn)程的動(dòng)作受主進(jìn)程的控制；③主進(jìn)程和從進(jìn)程的關(guān)系是固定的。例：終端控制進(jìn)程和終端進(jìn)程。94會(huì)話方式特點(diǎn)：①使用進(jìn)程在使用服務(wù)進(jìn)程所提供的服務(wù)之前，必須得到服務(wù)進(jìn)程的許可；②服務(wù)進(jìn)程根據(jù)使用進(jìn)程的要求提供服務(wù)，但對(duì)所提供服務(wù)的控制由服務(wù)進(jìn)程自身完成。③使用進(jìn)程和服務(wù)進(jìn)程在通信時(shí)有固定連接關(guān)系。例：用戶進(jìn)程與磁盤管理進(jìn)程之間的通信。95消息或郵箱機(jī)制的特點(diǎn)：①只要存在空緩沖區(qū)或郵箱，發(fā)送進(jìn)程就可以發(fā)送消息。②與會(huì)話系統(tǒng)不同，發(fā)送進(jìn)程和接收進(jìn)程之間無直接連接關(guān)系，接收進(jìn)程可能在收到某個(gè)發(fā)送進(jìn)程發(fā)來的消息之后，又轉(zhuǎn)去接收另一個(gè)發(fā)送進(jìn)程發(fā)來的消息③發(fā)送和接收進(jìn)程間存在緩沖區(qū)或郵箱來存放被傳送消息。消息的組成緩沖區(qū)或郵箱通信結(jié)構(gòu)96共享存儲(chǔ)區(qū)方式：1、不要求數(shù)據(jù)移動(dòng)；2、共享數(shù)據(jù)區(qū)屬于互相通信進(jìn)程的一個(gè)組成部分；3、兩個(gè)需要互相交換信息的進(jìn)程通過對(duì)同一共享數(shù)據(jù)區(qū)（sharedmemory）的操作來達(dá)到互相通信的目的。973.7.2消息緩沖機(jī)制原理圖：兩通信進(jìn)程必須滿足下列條件1在發(fā)送進(jìn)程把消息寫入緩沖區(qū)和把緩沖區(qū)掛入消息隊(duì)列時(shí)，應(yīng)禁止其他進(jìn)程對(duì)緩沖區(qū)消息隊(duì)列的訪問。同理，接收進(jìn)程取消息時(shí)也禁止其他進(jìn)程訪問緩沖區(qū)消息隊(duì)列2當(dāng)緩沖區(qū)中沒有信息存在時(shí)，接收進(jìn)程不能接收到任何消息3發(fā)送進(jìn)程是否可以發(fā)送消息，則由發(fā)送進(jìn)程是否申請(qǐng)到緩沖區(qū)決定。發(fā)送進(jìn)程在自己的內(nèi)存空間設(shè)置一個(gè)把要發(fā)送的消息填入發(fā)送區(qū)發(fā)送區(qū)接收區(qū)接收進(jìn)程在自己的內(nèi)存空間設(shè)置一個(gè)公用緩沖區(qū)需要互斥訪問98分析：1)mutex:控制對(duì)緩沖區(qū)訪問的互斥信號(hào)量，SM:接收進(jìn)程的私用信號(hào)量;2)賦初值。Mutex=1，SM=0（等待接收的消息個(gè)數(shù)）3)過程功能：send(m)：消息m送往緩沖區(qū)；Receive(m)：消息m從緩沖區(qū)讀往自己的數(shù)據(jù)區(qū)，Send(m)和Receive(n)可分別描述為：99Send(m): begin

向系統(tǒng)申請(qǐng)一個(gè)消息緩沖區(qū) Ｐ（mutex）/*使用公用緩沖區(qū) 將發(fā)送區(qū)消息m送入新申請(qǐng)的消息緩沖區(qū)

把消息緩沖區(qū)掛入接收進(jìn)程的消息隊(duì)列 Ｖ（mutex）/*釋放緩沖區(qū) Ｖ（SM）/*向接收進(jìn)程發(fā)送消息

endReceive(n): begin

Ｐ（SM）/*等待接收的消息的個(gè)數(shù) Ｐ（mutex）/*使用公用緩沖區(qū) 摘下消息隊(duì)列中的消息n

將消息n從緩沖區(qū)復(fù)制到接收區(qū) 釋放緩沖區(qū) Ｖ（mutex）/*釋放公用緩沖區(qū)

end100特別注意：

雖然緩沖區(qū)總數(shù)已知，但消息隊(duì)列是按接收進(jìn)程排列，故同一時(shí)間內(nèi)，系統(tǒng)中存在著多個(gè)消息隊(duì)列；且這些隊(duì)列長(zhǎng)度不固定。結(jié)論：發(fā)送進(jìn)程無法在Send過程用Ｐ操作判斷信號(hào)量SM1013.7.3郵箱通信郵箱含義：由發(fā)送進(jìn)程申請(qǐng)建立一與接收進(jìn)程鏈接的大小固定的私有數(shù)據(jù)結(jié)構(gòu)。構(gòu)成：邏輯上分成兩部分：信箱頭和由若干格子組成的信箱體信箱中每個(gè)格子存放一封信，信箱中格子的數(shù)目和每格的大小在創(chuàng)建信箱時(shí)確定。優(yōu)點(diǎn)：發(fā)送與接收的隨機(jī)性。條件：

進(jìn)程間的通信要滿足

a.發(fā)送進(jìn)程發(fā)送消息時(shí)，郵箱中至少要有一個(gè)空格存放該消息

b.接收進(jìn)程接收消息時(shí)，郵箱中至少要有一個(gè)消息存在。102發(fā)送進(jìn)程A

郵箱頭

…郵箱體接收進(jìn)程BDeposite(m)Remove(m)

郵箱通信結(jié)構(gòu)郵箱頭：郵箱名稱、郵箱大小、擁有該郵箱的進(jìn)程名郵箱體：存放消息103算法設(shè)計(jì)：1、定義：fromnum：發(fā)送進(jìn)程的私用信號(hào)量；mesnum：接收進(jìn)程的私用信號(hào)量；2、賦初值：fromnum=n，信箱的空格數(shù)，

mesnum=0。消息個(gè)數(shù)3、描述：

Deposit(m);BeginlocalxP(fromnum)空格數(shù)減1

選擇空格x

將消息m放入空格x中置格x的標(biāo)志為滿V(mesnum)向接收進(jìn)程發(fā)送消息end

消息個(gè)數(shù)＋1Remove(m)beinglocalxP(mesnum)消息個(gè)數(shù)減1

選擇滿格x

把滿格x中的消息取出放m中置格x標(biāo)志為空

V(mesnum)空格個(gè)數(shù)加1end1043.7.4進(jìn)程通信的實(shí)例——和控制臺(tái)的通信1、定義：KCP：鍵盤控制進(jìn)程；DCP：顯示控制進(jìn)程；CCP：會(huì)話控制進(jìn)程，完成用戶進(jìn)程和控制臺(tái)終端的通信2、通信過程如圖3.18。進(jìn)程死鎖1261051、控制臺(tái)鍵盤的輸入放入緩沖隊(duì)列inbuf中2、CCP從inbuf中取出消息(來自控制臺(tái)的指示)3、CCP的提問，以消息形式放入outbuf中；4、DCP從outbuf中取出消息送至顯示器，以供操作員判斷106KCP和DCP的動(dòng)作1）KCP和鍵盤KP發(fā)生通信；2）DCP和顯示器動(dòng)作DP的通信；107KCP可描述如下：設(shè)T-Ready：鍵盤KP私用信號(hào)量；初值為0T-Busy：控制進(jìn)程KCP的私用信號(hào)量，初值1。 初始化｛清除所有inbuf和echobuf} beginlocalx

Ｐ（T-Ready） 從鍵盤數(shù)據(jù)傳輸緩沖x中取出字符m記為x.m Send(x.m)

將x.m送入echonuf

Ｖ（T-Busy）

end

repeatlocalx

Ｐ（T-Busy）把鍵入字符放入數(shù)據(jù)傳輸緩沖x

Ｖ（T-Ready）Until終端關(guān)閉鍵盤動(dòng)作KP：108初始化{清除輸出緩沖outbuf，echo模式置false}beginifoutbuf滿then receive(k)/*CCPk*/

Ｐ（D-Busy） 把k送入顯示器數(shù)據(jù)緩沖區(qū) Ｖ（D-Ready）else echo模式置true echobuf中字符置入顯示器數(shù)據(jù)緩沖區(qū)

fi設(shè)D-Ready：0(DP);D-Busy:1(DCP)。

repeatif echo模式

then打印顯示器數(shù)據(jù)緩沖區(qū)

中字符

else

Ｐ（D-Ready）打印顯示器數(shù)據(jù)緩沖區(qū)中消息Ｖ（D-Busy）

Until 顯示器關(guān)機(jī)DCP動(dòng)作：顯示器動(dòng)作DP：109(2)CCP和KCP及DCP的接口CCP從inbuf中讀出消息消息寫入outbuf?Read(x):BeginP（inbuf-full）

Copy(inbufintox)/*把inbuf中的所有字符讀到用戶進(jìn)程數(shù)據(jù)區(qū)x處

Ｖ（inbuf-empty）

endWrite(y):begin

Ｐ（outbuf-empty）

Copy(outbuffromy)/*把用戶進(jìn)程y處的消息寫到outbuf中

Ｖ（outbuf-full）

end110這里，inbuf-full和inbuf-empty分別是CCP和KCP的私用信號(hào)量，在過程Send(m)和Read(x)中使用，其初值分別為0和1。由于在KCP中，Send(m)被用來將字符一個(gè)個(gè)地送入inbuf中，Send(m)過程必須要作一定的改動(dòng)，也就是要加入緩沖計(jì)數(shù)功能和把inbuf的長(zhǎng)度看作是固定的。另外，outbuf-full和outbuf-empty則是DCP和CCP的私用信號(hào)量，在過程receive(k)和write(y)中使用。其初值分別為0和1。由于outbuf的長(zhǎng)度是固定的，所以receive(k)過程也應(yīng)作相應(yīng)的修改。111(3)CCP與用戶進(jìn)程的接口除了和KCP及DCP的通信之外，CCP還要從各用戶進(jìn)程那里得到提問和向提問的用戶進(jìn)程轉(zhuǎn)達(dá)從控制臺(tái)來的指示。因此，CCP和用戶進(jìn)程之間也存在著通信關(guān)系。設(shè)各用戶進(jìn)程向CCP發(fā)出的提問，用消息組成隊(duì)列RQ。各用戶進(jìn)程把消息送入RQ時(shí)，必須互斥操作，否則將引起RQ隊(duì)列混亂。因此，設(shè)互斥用信號(hào)量rq，初值為1。另外，CCP只有在用戶進(jìn)程提問之后才負(fù)責(zé)向控制臺(tái)轉(zhuǎn)發(fā)提問和向用戶進(jìn)程轉(zhuǎn)達(dá)控制臺(tái)的指示。因此，還必須為CCP設(shè)置一私用信號(hào)量question以計(jì)算用戶進(jìn)程所提出的問題數(shù)目。信號(hào)量question的初值為0。112另外，由于各用戶進(jìn)程在CCP發(fā)出回答消息之后，不一定馬上就能處理CCP所發(fā)出的回答消息，因而，需設(shè)置相應(yīng)的消息接收隊(duì)列SQi。SQi和RQ的關(guān)系如圖3.19。圖3.19CCP和用戶進(jìn)程接口113與對(duì)RQ隊(duì)列的操作時(shí)相同，對(duì)SQi隊(duì)列的操作也必須是互斥的，因而，設(shè)互斥信號(hào)量sqi，其初值為1。除此之外，為了保證CCP和各用戶進(jìn)程之間在獲得回答的同步，還需設(shè)一私用信號(hào)量answeri以計(jì)算SQi中的消息個(gè)數(shù)。CCP和用戶進(jìn)程的接口可描述如下：

U-receive(m): begin

Ｐ（question）

whenrqdo從RQ中取出mod return(m) end114這里，采用了互斥變量rq作為臨界區(qū)名。U-receive(m)描述從RQ取出一個(gè)消息的過程。

S-answer(a，i): begin whensqido把a(bǔ)插入SQi中od

Ｖ（answeri）

end115(4)CCP的動(dòng)作作為實(shí)現(xiàn)用戶進(jìn)程與控制臺(tái)通信的方法之一，利用上面所述的各種接口，可以描述實(shí)現(xiàn)嚴(yán)格的順序會(huì)話CCP進(jìn)程。會(huì)話控制進(jìn)程CCP：

local k，m，x repeat U-receive(m)

將消息m的進(jìn)程標(biāo)號(hào)置入k中 將消息m解碼變換到x Write(x) Read(x)

將x編碼到m S-answer(m，k) untilCCP結(jié)束1163.7.5進(jìn)程通信的實(shí)例——管道1.管道pipe1）含義：管道（pipe）通訊由UNIX首創(chuàng)的一種借助文件和文件系統(tǒng)形成的一種通信方式。指用于連接一個(gè)讀進(jìn)程和一個(gè)寫進(jìn)程，以實(shí)現(xiàn)它們之間通信的共享方式，又稱pipe文件。

2）管道通信：

向管道（共享文件）提供輸入的發(fā)送進(jìn)程（即寫進(jìn)程），以字符流形式將大量的數(shù)據(jù)送入管道；而接收管道輸出的接收進(jìn)程（即讀進(jìn)程），可從管道接收數(shù)據(jù)，由于發(fā)送和接收都是利用管道進(jìn)行通信的，故稱為管道通信。1173）

Pipe的建立和使用方式A、pipe文件在使用之前，必須先由使用者建立并打開；B、建立pipe的主要工作是在系統(tǒng)打開文件表中建立該pipe的兩個(gè)表目；C、表目作用：分別用于控制該pipe的寫操作（寫入端）和讀操作（讀出端）。此時(shí)，pipe本身還是個(gè)空白文件。

系統(tǒng)文件write(Fd[1],buf,size)

功能：把buf中的長(zhǎng)度為size字符的消息送入管道入口fd[1]fd[1]—pipe入口

buf:存放消息的空間

size:要寫入的字符長(zhǎng)度系統(tǒng)文件read(fd[0],buf,size)fd[0]――Pipe的出口功能：從pipe出口fd[0]讀出size字符的消息置入buf中。注：pipe只允許建立者及其子進(jìn)程使用。一進(jìn)程及其所有‘子孫’構(gòu)成一個(gè)進(jìn)程族，同族中的多個(gè)進(jìn)程可共享一個(gè)pipe，為了避免混亂，通常一個(gè)pipe為兩個(gè)進(jìn)程專用，且一個(gè)進(jìn)程只用其寫入端，另一進(jìn)程只用其讀出端。118

圖3.20管道通信示意圖4）Pipe文件的讀寫操作的同步與互斥

如同消息緩沖一樣，在對(duì)pipe文件進(jìn)行讀寫操作過程中要對(duì)發(fā)送進(jìn)程和接送進(jìn)程實(shí)施正確的同步與互斥以確保通信的正確性.接收進(jìn)程：當(dāng)接收進(jìn)程讀pipe時(shí)，若發(fā)現(xiàn)pipe為空，則進(jìn)入等待狀態(tài)。一旦有發(fā)送進(jìn)程對(duì)該pipe執(zhí)行寫操作是喚醒等待進(jìn)程.發(fā)送進(jìn)程：當(dāng)發(fā)送進(jìn)程在寫pipe時(shí)，總是先按pipe文件的當(dāng)前長(zhǎng)度設(shè)置，如果pipe文件長(zhǎng)度已經(jīng)到4096字節(jié)，但仍有一部分信息沒有寫入，則系統(tǒng)使要求寫pipe的進(jìn)程進(jìn)入睡眠狀態(tài)，當(dāng)讀pipe進(jìn)程收走了全部信息時(shí)，此時(shí)，系統(tǒng)再喚醒待寫的進(jìn)程。它將余下部分信息繼續(xù)送入pipe中。注：管道按先進(jìn)現(xiàn)出方式FIFO傳送消息，

且只能單向傳送消息1192.示例例1：用C語言編寫一個(gè)程序，建立一個(gè)pipe，同時(shí)父進(jìn)程生成一個(gè)子進(jìn)程，子進(jìn)程向pipe中寫入一字符串，父進(jìn)程從pipe中讀出該字符串。解：程序如下：

#include〈stdio.h〉 main() { intx，fd［2］；

charbuf［30］，s［30］；

pipe(fd)；/*創(chuàng)建管道*/ while((x=fork())==-1)；/*創(chuàng)建子進(jìn)程失敗時(shí)，循環(huán)*/ if(x==0)120 { sprintf(buf，″Thisisanexample＼n″)；

write(fd［1］，buf，30)；/*把buf中字符寫入管道*/ exit(0)；

} else/*父進(jìn)程返回*/ { wait(0)；

read(fd［0］，s，30)；/*父進(jìn)程讀管道中字符*/ printf(″%s″，s)；

} }121例2：編寫一程序，建立一個(gè)管道。同時(shí)，父進(jìn)程生成子進(jìn)程P1，P2，這兩個(gè)子進(jìn)程分別向管道中寫入各自的字符串，父進(jìn)程讀出它們（如圖3.21）。圖3.21父進(jìn)程和子進(jìn)程P1，P2通信例子解：程序框圖如圖3.22所示，源程序如下：122圖3.22例2程序流圖123#include〈stdio.h〉main(){inti，r，p1，p2，fd［2］；charbuf［50］，s［50］；pipe(fd)；/*父進(jìn)程建立管道*/while((p1=fork())==-1)；/*創(chuàng)建子進(jìn)程P1，失敗時(shí)循環(huán)*/if(p1==0)

/*由子進(jìn)程P1返回，執(zhí)行子進(jìn)程P1*/{lockf(fd［1］，1，0)；/*加鎖鎖定寫入端*/sprintf(buf，″childprocessP1issendingmessages!＼n″)；

printf(″childprocessP1!＼n″)；write(fd［1］，buf，50)；/*把buf中的50個(gè)字符寫入管道*/sleep(5)；/*睡眠5秒，讓父進(jìn)程讀*/lockf(fd［1］，0，0)；/*釋放管道寫入端*/exit(0)；/*關(guān)閉P1*/}else/*從父進(jìn)程返回，執(zhí)行父進(jìn)程*/{while((p2=fork())==-1)；/*創(chuàng)建子進(jìn)程P2，失敗時(shí)循環(huán)*/if(p2==0)/*從子進(jìn)程P2返回，執(zhí)行P2*/{124lockf(fd［1］，1，0)；/*鎖定寫入端*/sprintf(buf，″childprocessP2issendingmessages＼n″)；

printf(″childprocessP2!＼n″)；

write(fd［1］，buf，50)；/*把buf中字符寫入管道*/sleep(5)；/*睡眠等待*/lockf(fd［1］，0，0)；/*釋放管道寫入端*/exit(0)；/*關(guān)閉P2*/}wait(0)；if(r=read(fd［0］，s，50)==-1)printf(″can′treadpipe＼n″)；elseprintf(″%s＼n″,s)；wait(0)；if(r=read(fd［0］，s，50)==-1)printf(″can′treadpipe＼n″)；elseprintf(″%s＼n″,s)；exit(0)；

}}lockf為保證進(jìn)程互斥使用管道的系統(tǒng)調(diào)用，sleep為保證當(dāng)前進(jìn)程睡眠，轉(zhuǎn)讓處理機(jī)的系統(tǒng)調(diào)用。125§3.8死鎖問題3.8.1死鎖的概念死鎖的定義死鎖——各并發(fā)進(jìn)程彼此互相等待對(duì)方所擁有的資源，且這些并發(fā)進(jìn)程在得到對(duì)方的資源之前不會(huì)釋放自己所擁有的資源。從而造成大家都想得到資源而又都得不到資源，各并發(fā)進(jìn)程不能繼續(xù)向前推進(jìn)的狀態(tài)。 圖3.22死鎖的概念126舉例：生產(chǎn)