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

2.1進(jìn)程的基本概念2.2進(jìn)程管理2.3進(jìn)程調(diào)度2.4進(jìn)程間的同步與互斥2.5進(jìn)程通訊2.6死鎖第二章進(jìn)程管理2.1進(jìn)程的基本概念程序的順序執(zhí)行和并發(fā)執(zhí)行順序執(zhí)行是單道批處理系統(tǒng)的執(zhí)行方式，也用于簡(jiǎn)單的單片機(jī)系統(tǒng)；

現(xiàn)在的操作系統(tǒng)多為并發(fā)執(zhí)行，具有許多新的特征。引入并發(fā)執(zhí)行的目的是為了提高資源利用率。順序執(zhí)行的特征順序性

封閉性

可再現(xiàn)性

例：程序段

read(disk,&a,4);/*從磁盤(pán)讀a*/read(tape,&b,4);/*從帶讀b*/c=a+b;

printf(“c=%f\n”,c);程序的順序執(zhí)行

是一個(gè)有向無(wú)環(huán)圖，圖中每個(gè)結(jié)點(diǎn)表示一個(gè)語(yǔ)句、一段程序或一個(gè)進(jìn)程1.前驅(qū)圖有向邊<Vi,Vj>表示Vj僅在

Vi執(zhí)行完后才能開(kāi)始執(zhí)行

S1S3S7S6S4S2S5S2S1S3前驅(qū)圖有回路的前驅(qū)圖程序并行性表示類(lèi)Pascal的并行語(yǔ)句。COBEGINs1；s2；…；snCOENDCOBEGIN/COEND相當(dāng)于一個(gè)括號(hào)，表示其中的所有語(yǔ)句s1,s2,…sn可并行執(zhí)行。2.并行語(yǔ)言并發(fā)執(zhí)行的條件（Bernstein條件）程序P(i)針對(duì)變量的讀集R(i)和寫(xiě)集W(i)條件：任意兩個(gè)程序P(i)和P(j)，同時(shí)滿足：R(i)W(j)=;W(i)R(j)=;W(i)W(j)=;1966年，由Bernstein給出并發(fā)執(zhí)行的條件。前兩條保證一個(gè)程序的兩次讀之間數(shù)據(jù)不變化；最后一條保證寫(xiě)的結(jié)果不丟掉。例：s1:read(disk,&a,4);/*從磁盤(pán)讀a*/s2:read(tape,&b,4);/*從帶讀b*/s3:

c=a+b;R(s1)=W(s1)={a}s1和s2可并發(fā)，s2和s3不可并發(fā)多道程序系統(tǒng)：資源共享；程序的并發(fā)運(yùn)行例：intN=0;/*全局變量*/

cobegin

progamA{while(1){…..N++;…..}}progamB{while(1){…..

printf(“N=%d\n”,N);N=0;…..}}coend并發(fā)執(zhí)行的特征間斷(異步)性：“運(yùn)行－暫停－運(yùn)行”；并發(fā)程序之間依賴相互、相互制約不可再現(xiàn)性并發(fā)程序與它的執(zhí)行過(guò)程并非一一對(duì)應(yīng)進(jìn)程(PROCESS)的概念一個(gè)具有一定獨(dú)立功能的程序在一個(gè)數(shù)據(jù)集合上的一次動(dòng)態(tài)執(zhí)行過(guò)程。是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位進(jìn)程的定義是并發(fā)程序的一次執(zhí)行過(guò)程，它由一個(gè)動(dòng)作序列組成，每個(gè)動(dòng)作是在某數(shù)據(jù)集上執(zhí)行一段程序，整個(gè)活動(dòng)的結(jié)果是提供一種系統(tǒng)或用戶功能。動(dòng)態(tài)性：產(chǎn)生、執(zhí)行、暫停、消亡。有一個(gè)生存期獨(dú)立性：是系統(tǒng)進(jìn)行資源分配和調(diào)度的獨(dú)立單位，是能獨(dú)立運(yùn)行的基本單位并發(fā)性：程序在建立進(jìn)程后并發(fā)運(yùn)行進(jìn)程的特征

進(jìn)程＝程序＋數(shù)據(jù)＋PCB(進(jìn)程控制塊，processcontrolblock)進(jìn)程是動(dòng)態(tài)的，程序是靜態(tài)的進(jìn)程是暫時(shí)的，程序的永久的進(jìn)程與程序的組成不同進(jìn)程與程序的區(qū)別進(jìn)程與程序的聯(lián)系通過(guò)多次執(zhí)行，一個(gè)程序可對(duì)應(yīng)多個(gè)進(jìn)程；通過(guò)調(diào)用關(guān)系，一個(gè)進(jìn)程可包括多個(gè)程序。運(yùn)行狀態(tài)：進(jìn)程分配到必要的資源，在CPU上執(zhí)行時(shí)的狀態(tài)就緒狀態(tài)：進(jìn)程分配到必要的資源，還沒(méi)獲得在CPU上執(zhí)行的狀態(tài)阻塞狀態(tài)（等待狀態(tài)）：進(jìn)程的執(zhí)行由于本身不具備運(yùn)行條件而受到阻塞，處于暫停狀態(tài)進(jìn)程的狀態(tài)2.2進(jìn)程管理三種基本調(diào)度狀態(tài)RunningReadyBlocked等待事件

(系統(tǒng)服務(wù)請(qǐng)求，如請(qǐng)求I/O))被調(diào)度或分派時(shí)間片用完事件發(fā)生掛起：強(qiáng)迫進(jìn)程釋放分配到的資源，將進(jìn)程調(diào)出到外存活動(dòng)：未被掛起的就緒和阻塞狀態(tài)稱為活動(dòng)就緒和活動(dòng)阻塞靜止：被掛起的就緒和阻塞狀態(tài)稱為靜止就緒和靜止阻塞進(jìn)程的狀態(tài)細(xì)分的進(jìn)程調(diào)度狀態(tài)ReadyaRunningBlockedaBlockedsReadyswakeup(喚醒)事件發(fā)生掛起suspend時(shí)間片完被調(diào)度schoduler解掛

active掛起

suspend解掛

active掛起

suspend等待事件

sleep事件發(fā)生wakeup(喚醒)圖：具有掛起功能的進(jìn)程狀態(tài)變化進(jìn)程的狀態(tài)轉(zhuǎn)換：三狀態(tài)進(jìn)程模型程序：描述進(jìn)程要完成的功能數(shù)據(jù)集合：包含程序運(yùn)行所需的數(shù)據(jù)和工作區(qū)進(jìn)程控制塊（PCB）：包含進(jìn)程的描述信息和控制信息，是進(jìn)程動(dòng)態(tài)特性的反映進(jìn)程的物理結(jié)構(gòu)程序和數(shù)據(jù)集合是進(jìn)程的實(shí)體進(jìn)程控制塊是進(jìn)程存在的唯一標(biāo)志進(jìn)程控制塊（PCB,processcontrolblock)進(jìn)程控制塊是由OS維護(hù)的用來(lái)記錄進(jìn)程相關(guān)信息的一塊內(nèi)存。進(jìn)程標(biāo)識(shí)符：進(jìn)程標(biāo)識(shí)符(processID)（內(nèi)部標(biāo)識(shí)符）：唯一，通常是一個(gè)整數(shù)；進(jìn)程名（外部標(biāo)識(shí)符）：不唯一，由字母數(shù)字組成；位置信息：指出進(jìn)程的程序和數(shù)據(jù)在內(nèi)存和外存中的物理位置現(xiàn)場(chǎng)信息：寄存器值（通用、程序計(jì)數(shù)器PC、狀態(tài)PSW，地址包括棧指針）狀態(tài)信息：進(jìn)程現(xiàn)行狀態(tài)進(jìn)程優(yōu)先級(jí)：進(jìn)程使用CPU的優(yōu)先級(jí)別資源清單：已分配到的資源等同步與互斥機(jī)構(gòu)進(jìn)程通訊機(jī)制隊(duì)列指針家族聯(lián)系資源占用信息：虛擬地址空間的現(xiàn)狀、打開(kāi)文件列表進(jìn)程控制塊的內(nèi)容順序表：將所有PCB連續(xù)存放在內(nèi)存。要經(jīng)常掃描整個(gè)表索引表：同一狀態(tài)的PCB建立一個(gè)index表（由index指向PCB），多個(gè)狀態(tài)對(duì)應(yīng)多個(gè)不同的index表各狀態(tài)形成不同的索引表：就緒索引表、阻塞索引表鏈表：同一狀態(tài)的進(jìn)程的PCB成一鏈表，多個(gè)狀態(tài)對(duì)應(yīng)多個(gè)不同的鏈表各狀態(tài)的形成不同的鏈表：就緒鏈表、阻塞鏈表PCB的組織方式進(jìn)程控制進(jìn)程控制的功能完成進(jìn)程狀態(tài)的轉(zhuǎn)換。原語(yǔ)(primitive)：由若干條指令構(gòu)成的“原子操作(atomicoperation)”過(guò)程，作為一個(gè)整體而不可分割－－要么全都完成，要么全都不做。許多系統(tǒng)調(diào)用就是原語(yǔ)。2.3進(jìn)程調(diào)度作業(yè)狀態(tài)及其轉(zhuǎn)換提交狀態(tài)后備狀態(tài)：作業(yè)的全部信息已輸入到磁盤(pán)的專用區(qū)（后備作業(yè)區(qū)）中，等待運(yùn)行執(zhí)行狀態(tài)：被作業(yè)調(diào)度程序選中，分配了必要資源，建立了PCB，進(jìn)入進(jìn)程的就緒狀態(tài)，等待運(yùn)行完成狀態(tài)：作業(yè)完成任務(wù)，釋放資源調(diào)度的層次作業(yè)調(diào)度（高級(jí)調(diào)度）：選擇作業(yè)，調(diào)入內(nèi)存，分配資源建立進(jìn)程，將PCB插入就緒進(jìn)程隊(duì)列進(jìn)程調(diào)度（低級(jí)調(diào)度）：將CPU分配給進(jìn)程，進(jìn)行進(jìn)程間切換，運(yùn)行被調(diào)度進(jìn)程中級(jí)調(diào)度：進(jìn)程映象在內(nèi)存和盤(pán)交換區(qū)間的對(duì)換操作。防止死鎖。作業(yè)從提交到完成，要經(jīng)歷三級(jí)調(diào)度進(jìn)程調(diào)度算法非剝奪搶占方式：一旦進(jìn)程占用CPU就一直運(yùn)行，直到終止或阻塞剝奪搶占方式：系統(tǒng)強(qiáng)行剝奪已分配給現(xiàn)運(yùn)行進(jìn)程的CPU，使其進(jìn)入就緒進(jìn)程隊(duì)列按占用處理器的方式，進(jìn)程調(diào)度有兩種方式：進(jìn)程調(diào)度方式設(shè)計(jì)目標(biāo)：目標(biāo)不同，系統(tǒng)的要求不同CPU利用率：吞吐量：系統(tǒng)在單位時(shí)間內(nèi)完成的作業(yè)數(shù)目周轉(zhuǎn)時(shí)間：從作業(yè)提交到完成的時(shí)間間隔等待時(shí)間：進(jìn)程在就緒進(jìn)程隊(duì)列中的等待時(shí)間，通常用來(lái)衡量調(diào)度程序的性能響應(yīng)時(shí)間：從向系統(tǒng)發(fā)出請(qǐng)求到系統(tǒng)首次開(kāi)始響應(yīng)的時(shí)間間隔資源利用率：最大限度地使各種資源并行操作合理的系統(tǒng)開(kāi)銷(xiāo)調(diào)度算法性能標(biāo)準(zhǔn)按先進(jìn)先出組織就緒狀態(tài)的進(jìn)程隊(duì)列總是把CPU分配給就緒狀態(tài)的進(jìn)程隊(duì)列的隊(duì)首進(jìn)程最簡(jiǎn)單的進(jìn)程調(diào)度算法屬于非剝奪搶占方式進(jìn)程調(diào)度算法先來(lái)先服務(wù)算法（FCFS）例：進(jìn)程P1,P2,P3，它們的CPU運(yùn)行時(shí)間為3，3，24個(gè)單位時(shí)間FCFS特點(diǎn)：僅考慮作業(yè)提交時(shí)間，未考慮系統(tǒng)資源使用率（1）P3,P1,P2順序進(jìn)入就緒進(jìn)程隊(duì)列，幾乎同時(shí)到達(dá)平均周轉(zhuǎn)時(shí)間=(24+27+30)/3=27（2）P1,P2,P3順序進(jìn)入就緒進(jìn)程隊(duì)列，幾乎同時(shí)到達(dá)平均周轉(zhuǎn)時(shí)間=(3+6+30)/3=13要求就緒狀態(tài)的進(jìn)程隊(duì)列中每個(gè)進(jìn)程有下一個(gè)CPU運(yùn)行期的時(shí)間值把CPU分配給就緒狀態(tài)的進(jìn)程隊(duì)列中下一個(gè)CPU運(yùn)行期最短的進(jìn)程短者優(yōu)先的原則進(jìn)程調(diào)度算法短CPU運(yùn)行期優(yōu)先算法（SCBF）優(yōu)點(diǎn)：等待時(shí)間最小，系統(tǒng)吞吐量高缺點(diǎn)：已知進(jìn)程的CPU運(yùn)行時(shí)間，很難實(shí)現(xiàn)例：進(jìn)程P1,P2,P3,P4，它們的CPU運(yùn)行時(shí)間為6，3，8，7個(gè)單位時(shí)間，P3,P1,P2,P4順序進(jìn)入就緒進(jìn)程隊(duì)列，幾乎同時(shí)到達(dá)

FCFS算法：平均周轉(zhuǎn)時(shí)間=(8+14+17+24)/4=15.75SCBF算法：平均周轉(zhuǎn)時(shí)間=(3+9+16+24)/4=13系統(tǒng)自動(dòng)按一定原則為每個(gè)進(jìn)程規(guī)定一個(gè)調(diào)度優(yōu)先權(quán)把CPU分配給就緒狀態(tài)的進(jìn)程隊(duì)列具有最高優(yōu)先權(quán)的進(jìn)程常用的調(diào)度算法進(jìn)程調(diào)度算法優(yōu)先權(quán)調(diào)度算法確定優(yōu)先權(quán)的方法：靜態(tài)優(yōu)先權(quán)法動(dòng)態(tài)優(yōu)先權(quán)法進(jìn)程創(chuàng)建時(shí)確定其優(yōu)先權(quán)，運(yùn)行期間不改變按進(jìn)程類(lèi)型確定按作業(yè)要求的資源類(lèi)型和數(shù)量確定按作業(yè)提交的時(shí)間順序確定按用戶類(lèi)型和要求確定靜態(tài)優(yōu)先權(quán)法優(yōu)點(diǎn)：簡(jiǎn)單易實(shí)現(xiàn)，系統(tǒng)開(kāi)銷(xiāo)小缺點(diǎn)：未能反映進(jìn)程的動(dòng)態(tài)性進(jìn)程創(chuàng)建時(shí)賦一個(gè)優(yōu)先權(quán)初值，運(yùn)行期間動(dòng)態(tài)調(diào)整其權(quán)值動(dòng)態(tài)優(yōu)先權(quán)法特點(diǎn)：防止一個(gè)進(jìn)程壟斷或長(zhǎng)期等待CPU時(shí)間片輪轉(zhuǎn)算法簡(jiǎn)單輪轉(zhuǎn)法就緒狀態(tài)的所有進(jìn)程按FCFS組成隊(duì)列首先CPU分給隊(duì)首的進(jìn)程，規(guī)定一個(gè)時(shí)間片就緒隊(duì)列中的所有進(jìn)程輪流使用CPUT=NqN就緒隊(duì)列中進(jìn)程數(shù)，T為系統(tǒng)響應(yīng)時(shí)間，時(shí)間片為q多隊(duì)列輪轉(zhuǎn)法常用雙就緒狀態(tài)進(jìn)程隊(duì)列輪轉(zhuǎn)法首先對(duì)前臺(tái)就緒進(jìn)程隊(duì)列以時(shí)間片輪轉(zhuǎn)法調(diào)度，當(dāng)前臺(tái)就緒進(jìn)程隊(duì)列為空時(shí)，才對(duì)后臺(tái)就緒進(jìn)程隊(duì)列按FCFS算法調(diào)度按調(diào)度級(jí)別設(shè)置多個(gè)就緒進(jìn)程隊(duì)列按級(jí)別劃分時(shí)間片各級(jí)就緒進(jìn)程隊(duì)列按FIFO組織，F(xiàn)CFS調(diào)度最后一級(jí)按循環(huán)輪轉(zhuǎn)方式組織調(diào)度多級(jí)反饋隊(duì)列調(diào)度算法2.4進(jìn)程間的同步與互斥臨界資源進(jìn)程間的制約關(guān)系間接制約：進(jìn)行競(jìng)爭(zhēng)－－獨(dú)占分配到的部分或全部共享資源，“互斥”直接制約：進(jìn)行協(xié)作－－等待來(lái)自其他進(jìn)程的信息，“同步”系統(tǒng)中一次僅允許一個(gè)進(jìn)程使用的一類(lèi)資源。打印機(jī)，卡片輸入機(jī)，磁帶機(jī)、共享變量等?；コ猓憾鄠€(gè)進(jìn)程不能同時(shí)使用同一個(gè)資源；死鎖：多個(gè)進(jìn)程互不相讓，都得不到足夠的資源；饑餓：一個(gè)進(jìn)程一直得不到資源（其他進(jìn)程可能輪流占用資源）共享變量的修改沖突例：民航售票系統(tǒng)，n個(gè)售票處

/*ProcessPi,i=1,2,...,n*/…../*按訂票要求找到共享數(shù)據(jù)x[k]*//*x[k]存放某月某日某次航班的現(xiàn)有票數(shù)*/R=x[k];/*現(xiàn)有票數(shù)*/

if(R>=1){R--;

x[k]=R;

輸出一張機(jī)票；

}else

顯示“票已售完”；臨界區(qū)臨界區(qū)的訪問(wèn)過(guò)程臨界區(qū)：訪問(wèn)臨界資源的程序段。同類(lèi)臨界區(qū)：對(duì)同一臨界資源進(jìn)行操作的程序段。臨界區(qū)(criticalsection)：進(jìn)程中訪問(wèn)臨界資源的一段代碼。進(jìn)入?yún)^(qū)(entrysection)：在進(jìn)入臨界區(qū)之前，檢查可否進(jìn)入臨界區(qū)的一段代碼。退出區(qū)(exitsection)剩余區(qū)(remaindersection)：代碼中的其余部分?？臻e則入：其他進(jìn)程均不處于臨界區(qū)；忙則等待：已有進(jìn)程處于其臨界區(qū)；有限等待：等待進(jìn)入臨界區(qū)的進(jìn)程不能"死等"；讓權(quán)等待：不能進(jìn)入臨界區(qū)的進(jìn)程，應(yīng)釋放CPU（如轉(zhuǎn)換到阻塞狀態(tài)）互斥應(yīng)遵循的準(zhǔn)則有兩個(gè)進(jìn)程Pi,Pj，其中的Pi設(shè)立一個(gè)公用整型變量turn：描述允許進(jìn)入臨界區(qū)的進(jìn)程標(biāo)識(shí)進(jìn)程互斥的軟件方法算法1：?jiǎn)螛?biāo)志互斥算法缺點(diǎn)：強(qiáng)制輪流進(jìn)入臨界區(qū)，沒(méi)有考慮進(jìn)程的實(shí)際需要。容易造成資源利用不充分：在Pi出讓臨界區(qū)之后，Pj使用臨界區(qū)之前，Pi不可能再次使用臨界區(qū)；設(shè)立一個(gè)標(biāo)志數(shù)組flag[]：描述進(jìn)程是否要求進(jìn)入臨界區(qū)或已在臨界區(qū)，初值均為FALSEturn=j;描述可進(jìn)入的進(jìn)程（同時(shí)修改標(biāo)志時(shí)）在進(jìn)入?yún)^(qū)先修改、后檢查、后修改者等待算法2：雙標(biāo)志

intflag[2]={0,0};

intturn=0;/*進(jìn)程pi的結(jié)構(gòu)*/while(1){

flag[i]=1;

while(flag[j]){

if(turn==j){

flag[i]=0;

while(turn==j);

flag[i]=1;}

/*進(jìn)入臨界區(qū)*/criticalsection/*退出臨界區(qū)]*/turn=j;

flag[i]=0;

remaindersection}每一類(lèi)臨界資源設(shè)置一把鎖lock。lock表示資源的兩種狀態(tài)：TRUE表示正被占用（鎖關(guān)狀態(tài)）；FALSE表示空閑（鎖開(kāi)狀態(tài)）進(jìn)程互斥的鎖操作方法加鎖操作開(kāi)鎖操作執(zhí)行臨界區(qū)程序不能實(shí)現(xiàn)所有的同類(lèi)臨界區(qū)互斥；臨界區(qū)太長(zhǎng)時(shí)，降低了中斷響應(yīng)速度；擴(kuò)大了互斥范圍；加鎖時(shí)CPU不斷測(cè)試，處于忙等待。優(yōu)點(diǎn)：簡(jiǎn)單、可靠鎖操作方法用開(kāi)、關(guān)中斷實(shí)現(xiàn)鎖操作關(guān)中斷開(kāi)中斷執(zhí)行臨界區(qū)程序缺點(diǎn)：信號(hào)量表示臨界資源的實(shí)體，是一個(gè)數(shù)據(jù)結(jié)構(gòu)，其值僅能由P、V操作來(lái)改變。信號(hào)量(semaphore)阻塞等待信號(hào)量數(shù)據(jù)結(jié)構(gòu)：typedef

struct{

intvalue;/*信號(hào)量的值*/PCB*ptr_of_semque;}semaphore;

PCB:進(jìn)程控制塊的數(shù)據(jù)類(lèi)型

ptr_of_semque：指向等待使用該信號(hào)量的進(jìn)程隊(duì)列的隊(duì)首Value:指定一個(gè)非負(fù)整數(shù)值，表示空閑資源總數(shù)－－若為非負(fù)值表示當(dāng)前的空閑資源數(shù)，若為負(fù)值其絕對(duì)值表示當(dāng)前等待臨界區(qū)的進(jìn)程數(shù)ptr_of_semque：初值為空信號(hào)量初始化：P原語(yǔ)wait(s)externPCB*curproc;voidp(s)semaphore*s;{s->value--;

if(s->value<0){

Insert(curproc,s->ptr_of_semque);

Block(curproc);}}V原語(yǔ)通常喚醒進(jìn)程等待隊(duì)列中的頭一個(gè)進(jìn)程V原語(yǔ)signal(s)voidV(s)semaphore*s;{PCB*pcb_ptr;s->value++;

if(s->value<=0){

pcb_ptr=Remove(s->prt_of_semque);

Wakeup(pcb_ptr);/*進(jìn)程狀態(tài)置為活動(dòng)就緒*/}}為臨界資源設(shè)置一個(gè)互斥信號(hào)量mutex(MUTualExclusion)，其初值為1；在每個(gè)進(jìn)程中將臨界區(qū)代碼置于P(mutex)和V(mutex)原語(yǔ)之間必須成對(duì)使用P和V原語(yǔ)，P、V原語(yǔ)不能次序錯(cuò)誤、重復(fù)或遺漏利用信號(hào)量實(shí)現(xiàn)互斥信號(hào)量實(shí)現(xiàn)互斥模型：

semaphoremutex={1,NULL};

cobegin

programpi{while(1){

P(&mutex)；

criticalsectionforpi;/*進(jìn)程pi臨界區(qū)*/

V(&mutex)；

remaindersectionforpi;}}

coend解決共享變量的修改沖突例：民航售票系統(tǒng)，n個(gè)售票處

semaphoremutex={1,NULL};

cobegin

programpi{………

P(&mutex)；

R=x[k];/*現(xiàn)有票數(shù)*/

if(R>=1){R--;

x[k]=R;

V(&mutex)；

輸出一張機(jī)票；

}

else{

V(&mutex)；

顯示“票已售完”；

}}coend

設(shè)置一個(gè)同步信號(hào)量proceed1，其初值為0利用信號(hào)量實(shí)現(xiàn)同步

semaphoreproceed1={0,NULL};

cobegin

進(jìn)程p1………P(&proceed1)；

………

進(jìn)程p2………V(&proceed1)；

……….

coend

例：一輛公共汽車(chē)上，司機(jī)和售票員進(jìn)程的同步

semaphoredrive_sem={0,NULL};semaphoreconductor_sem={0,NULL};

cobegin

programdrive{while(1){driving;/*正常行車(chē)*/stopping;

V(&conductor_sem)；/*喚醒開(kāi)門(mén)*/

P(&drive_sem)；/*等待關(guān)門(mén)*/startacar;}}

programconductor{while(1){selltickets;/*售票*/

P(&conductor_sem)；/*等待停車(chē)*/openthedoor;closethedoor;

V(&drive_sem)；/*喚醒司機(jī)開(kāi)車(chē)*/}}coend

1.生產(chǎn)者－消費(fèi)者問(wèn)題(theproducer-consumerproblem)問(wèn)題描述：若干進(jìn)程通過(guò)有限的共享緩沖區(qū)交換數(shù)據(jù)。其中，"生產(chǎn)者"進(jìn)程不斷寫(xiě)入，而"消費(fèi)者"進(jìn)程不斷讀出；共享緩沖區(qū)共有N個(gè)；任何時(shí)刻只能有一個(gè)進(jìn)程可對(duì)共享緩沖區(qū)進(jìn)行操作。經(jīng)典應(yīng)用示例采用信號(hào)量機(jī)制：full是"滿"數(shù)目，初值為0，empty是"空"數(shù)目，初值為N。full+empty=Nmutex用于訪問(wèn)緩沖區(qū)時(shí)的互斥，初值是1每個(gè)進(jìn)程中各個(gè)P操作的次序是重要的：先檢查資源數(shù)目，再檢查是否互斥――否則可能死鎖(為什么？)

＃defineN100

＃defineMAXLEN80

typedef

struct{

intnum;chararray[MAXLEN];}Message;semaphoremutex={1,NULL};semaphoreempty={N,NULL};

semaphorefull={0,NULL};Messagebuffers[N];

int

p_index=0,c_index=0;

cobegin

programproduceri{Messagep_puf;while(1){produceamessageinp_buf;算法：

P(&empty)；

P(&mutex)；

memcpy((char*)&buffers[p_index],(char*)&p_buf,sizeof(Message));

p_index=(p_index+1)%N;

V(&mutex)；

V(&full)；}}programconsumerj{Messagec_buf;while(1){

P(&full)；

P(&mutex)；

memcpy((char*)&c_buf,(char*)&buffers[c_index],sizeof(Message));

c_index=(c_index+1)%N;

V(&mutex)；

V(&empty)；

consumethemessageinc_buf;}}coend

2.讀者－寫(xiě)者問(wèn)題(thereaders-writersproblem)問(wèn)題描述：對(duì)共享資源的讀寫(xiě)操作，任一時(shí)刻“寫(xiě)者”最多只允許一個(gè)，而“讀者”則允許多個(gè)“讀－寫(xiě)”互斥，“寫(xiě)－寫(xiě)”互斥，"讀－讀"允許采用信號(hào)量機(jī)制：rwmutex表示"允許寫(xiě)"，初值是1。公共變量Readcount表示“正在讀”的進(jìn)程數(shù)，初值是0；rmutex表示讀者對(duì)Readcount的互斥操作，初值是1。

semaphorerwmutex={1,NULL},rmutex

={1,NULL};

int

readcount=0;

cobegin

programreaderi{

P(&rmutex)；

readcount++;

if(readcount==1)

P(&rwmutex)；

V(&rmutex)；

readdata;

P(&rmutex)；

readcount--;

if(readcount==0)

V(&rwmutex)；

V(&rmutex)；}算法：programwriterj{

P(&rwmutex)；

writeorupdatedata;

V(&rwmutex)；}coend

寫(xiě)者長(zhǎng)期阻塞寫(xiě)者優(yōu)先算法：cobegin

programreaderi{

P(&rwmutex)；

P(&rsem)；

V(&rwmutex)；

readdata;

V(&rsem)；}programwriterj{

inti;

P(&rwmutex)；

for(i=1;i<=10;i++)

P(&rsem)；

writeorupdatedata;for(i=1;i<=10;i++)V(&rsem)；

V(&rmutex)；}coend

semaphorerwmutex={1,NULL},rsem={10,NULL};低級(jí)通信：只能傳遞狀態(tài)和整數(shù)值（控制信息），包括進(jìn)程互斥和同步所采用的信號(hào)量和管程機(jī)制。優(yōu)點(diǎn)是速度快。缺點(diǎn)是：傳送信息量小、效率低編程復(fù)雜高級(jí)通信：能夠傳送任意數(shù)量的數(shù)據(jù)，包括三類(lèi)：消息緩沖、管道、共享存儲(chǔ)區(qū)。2.5進(jìn)程間通信進(jìn)程間通信的類(lèi)型直接通信和間接通信直接通信：信息直接傳遞給接收方，如管道。在發(fā)送時(shí)，指定接收方的地址或標(biāo)識(shí)，也可以指定多個(gè)接收方或廣播式地址；在接收時(shí)，允許接收來(lái)自任意發(fā)送方的消息，并在讀出消息的同時(shí)獲取發(fā)送方的地址。間接通信：借助于收發(fā)雙方進(jìn)程之外的共享數(shù)據(jù)結(jié)構(gòu)作為通信中轉(zhuǎn)，如消息隊(duì)列。管道：用于連接一個(gè)讀進(jìn)程和一個(gè)寫(xiě)進(jìn)程，以實(shí)現(xiàn)它們之間通信的共享文件（pipe文件）常用于命令行所指定的輸入輸出重定向和管道命令。在使用管道前要建立相應(yīng)的管道，然后才可使用。管道(pipe)通訊無(wú)名管道：用于父子進(jìn)程或子進(jìn)程間通信有名管道：用于父進(jìn)程間通信（又稱FIFO通信）例：MSDOS命令

DIR|MORE進(jìn)程間數(shù)據(jù)交換以消息為單位應(yīng)用系統(tǒng)使用系統(tǒng)提供的一組通信原語(yǔ)來(lái)實(shí)現(xiàn)通信消息的發(fā)送不需要接收方準(zhǔn)備好，隨時(shí)可發(fā)送。消息(message)緩沖通訊諸進(jìn)程通過(guò)共享存儲(chǔ)區(qū)中的數(shù)據(jù)的讀或?qū)憗?lái)實(shí)現(xiàn)通信應(yīng)用程序?qū)崿F(xiàn)對(duì)共享存儲(chǔ)區(qū)訪問(wèn)的互斥與同步是進(jìn)程間通信最有效的機(jī)制相當(dāng)于內(nèi)存，可以任意讀寫(xiě)和使用任意數(shù)據(jù)結(jié)構(gòu)，需要進(jìn)程互斥和同步的輔助來(lái)確保數(shù)據(jù)一致性共享存儲(chǔ)區(qū)(sharedmemory)2.6死鎖(DEADLOCK)死鎖：當(dāng)一個(gè)進(jìn)程提出使用某資源的請(qǐng)求后，使系統(tǒng)中的一些進(jìn)程處于無(wú)休止的阻塞狀