第２章進(jìn)程和處理機(jī)管理要求學(xué)生掌握順序程序和并發(fā)程序；進(jìn)程的定義、特點及狀態(tài)變遷；進(jìn)程管理；進(jìn)程間的同步與互斥；進(jìn)程通信；死鎖產(chǎn)生的原因與解除方法。第２章進(jìn)程和處理機(jī)管理

2.1進(jìn)程及其有關(guān)概念

2.2進(jìn)程管理

2.3進(jìn)程的同步與互斥

2.4進(jìn)程通信

2.5死鎖

2.6小結(jié)2.1.1順序程序

1.順序程序：程序中若干操作必須按照某種先后次序來執(zhí)行，并且每次操作前和操作后的狀態(tài)之間都有一定的關(guān)系。2.1進(jìn)程及其有關(guān)概念2.順序程序的基本特征

(1)程序執(zhí)行的順序性(2)資源利用的獨占性，又叫程序執(zhí)行的封閉性(3)執(zhí)行結(jié)果的確定性2.1.2并發(fā)程序

1.并發(fā)執(zhí)行：如果有多個程序段同時在系統(tǒng)中運行且執(zhí)行時間是重疊的，即使重疊很小，我們也稱這幾個程序段是并發(fā)執(zhí)行的。

2.要求：兩個或兩個程序處于運行狀態(tài)2.1進(jìn)程及其有關(guān)概念圖2-1三個并發(fā)程序段示意圖2.1.2并發(fā)程序

3.用語句形式描述并發(fā)程序（執(zhí)行如圖2-2）

s0;cobegins1;s2;…sn;coend sn+1; 2.1進(jìn)程及其有關(guān)概念圖2-2并發(fā)程序執(zhí)行的優(yōu)先圖2.1.2并發(fā)程序

4.并發(fā)執(zhí)行和并行執(zhí)行的區(qū)別：

前者是在一段時間內(nèi)，從宏觀上看好象它們是在同時執(zhí)行，而實際上CPU是按照一定的策略在輪流執(zhí)行它們，在任一時刻，實際上只有一個程序段在執(zhí)行。而并行執(zhí)行需要多CPU的支持，在任一時刻，可以實現(xiàn)多個程序段的真正同時執(zhí)行。5.引入并發(fā)程序的目的：主要是為了提高資源利用率，從而提高系統(tǒng)效率2.1進(jìn)程及其有關(guān)概念6.比較順序程序和并發(fā)執(zhí)行

舉例：假設(shè)有A和B兩個程序段，它們各自的執(zhí)行過程如圖2.3所示。2.1進(jìn)程及其有關(guān)概念圖2-3順序程序舉例如果這兩個程序段是順序執(zhí)行，則CPU利用率=40/80=50%DEV1利用率=15/80=18.75%DEV2利用率=25/80=31.25%6.比較順序程序和并發(fā)執(zhí)行2.1進(jìn)程及其有關(guān)概念圖2-4并發(fā)程序舉例如果這兩個程序段按照如圖2-4的順序并發(fā)執(zhí)行，那么CPU利用率=40/45=89%DEV1利用率=15/45=33%DEV2利用率=25/45=56%2.1.2并發(fā)程序

7.并發(fā)執(zhí)行的特征：(1)并發(fā)性(2)程序結(jié)果的不可再現(xiàn)性（見下頁例子）(3)在并發(fā)環(huán)境下程序的執(zhí)行是間斷性的，即程序“執(zhí)行---暫停---執(zhí)行”(4)開放性⑸獨立性⑹制約性：分為間接制約和直接制約(7)程序和計算不在一一對應(yīng)2.1進(jìn)程及其有關(guān)概念例如，A向某帳號存錢，B從某帳號取錢。程序如右：①先執(zhí)行A，后執(zhí)行B，即先存錢，后取錢，其結(jié)果為s=900。②t1時刻：執(zhí)行A中的n=s;n=n+100;t2時刻：執(zhí)行B中的m=s;m=m-200;s=m;t3時刻：執(zhí)行A中的s=n;則結(jié)果為s=1100。程序結(jié)果的不可再現(xiàn)性舉例main(){ints=1000；//最初余額cobeginwhile(A未完成){n=s;n=n+100;s=n;}while{m=s;m=m-200;s=m;}coend}2.1.3進(jìn)程的定義及其特征

1.進(jìn)程定義最能反映進(jìn)程實質(zhì)的定義有：1）進(jìn)程是程序的一次執(zhí)行2）進(jìn)程是可以和別的計算并發(fā)執(zhí)行的計算3）進(jìn)程可定義為一個數(shù)據(jù)結(jié)構(gòu)及能在其上進(jìn)行操作的一個程序。4）進(jìn)程是一個程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行所發(fā)生的活動。2.1進(jìn)程及其有關(guān)概念5）進(jìn)程是程序在一個數(shù)據(jù)集合上的運行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨立單位。進(jìn)程的一個正式的定義是：：進(jìn)程是在自身的虛擬地址空間運行的一個單獨的程序，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨立單位

這個定義包含的含義是：1）進(jìn)程一個動態(tài)的概念，而程序是一個靜態(tài)的概念。

3.1進(jìn)程的基本概念2）進(jìn)程包含了一個數(shù)據(jù)集合和運行其上的程序。3）同一程序運行于若干個不同的數(shù)據(jù)集合上時，它將屬于若干個不同的進(jìn)程，或者說，兩個不同的進(jìn)程可包含相同的程序。4）系統(tǒng)分配資源是以進(jìn)程為單位的，所以只有進(jìn)程才可能在不同的時刻處于幾種不同的狀態(tài)，例如，等待，就緒，運行。5）從微觀上看，進(jìn)程是輪換地占有處理機(jī)而運行的；從宏觀上看，進(jìn)程是并發(fā)運行的2.1進(jìn)程及其有關(guān)概念2.1.3進(jìn)程的定義及其特征

2.進(jìn)程和程序的區(qū)別:

⑴進(jìn)程是程序的一次運行，屬于動態(tài)概念；程序是指令的集合，是靜態(tài)概念。⑵進(jìn)程包含數(shù)據(jù)和運行其上的程序，這樣靜態(tài)地觀察進(jìn)程與程序含義相近。⑶同一程序運行于若干個不同的集合上時，它將屬于若干個不同的進(jìn)程。或者說，兩個不同的進(jìn)程可以包含相同的程序。2.1進(jìn)程及其有關(guān)概念2.1.3進(jìn)程的定義及其特征

2.進(jìn)程和程序的區(qū)別:

⑷進(jìn)程能逼真的描述并發(fā)活動，而程序不明顯。⑸微觀上，進(jìn)程是輪流搶占處理機(jī)而運行的，宏觀上，進(jìn)程是并發(fā)運行的。⑹程序存儲需要介質(zhì)，進(jìn)程執(zhí)行要處理。⑺進(jìn)程是由程序和數(shù)據(jù)兩部分組成的。⑻進(jìn)程可以創(chuàng)建其他進(jìn)程，可以處于等待、就緒、運行等幾種不同的狀態(tài)。2.1進(jìn)程及其有關(guān)概念2.1.3進(jìn)程的定義及其特征

3.進(jìn)程和作業(yè)的區(qū)別:一個正在執(zhí)行的進(jìn)程稱為一個作業(yè)，而且作業(yè)可以包含一個或多個進(jìn)程，尤其是當(dāng)使用了管道和重定向命令時。4.進(jìn)程的特征⑴動態(tài)⑵并發(fā)⑶獨立⑷交互⑸異步

2.1進(jìn)程及其有關(guān)概念2.1.4進(jìn)程的類型1、系統(tǒng)進(jìn)程和用戶進(jìn)程，兩者的區(qū)別:⑴系統(tǒng)進(jìn)程被分配一個初始資源集，這些資源可以獨占，也可被擁有更高優(yōu)先權(quán)的系統(tǒng)進(jìn)程優(yōu)先使用。用戶進(jìn)程要通過系統(tǒng)服務(wù)請求手段競爭系統(tǒng)資源。⑵用戶進(jìn)程不能直接做I／O操作，而系統(tǒng)進(jìn)程可以直接進(jìn)行。⑶系統(tǒng)進(jìn)程在管態(tài)下活動，用戶進(jìn)程在目態(tài)下活動。2.1進(jìn)程及其有關(guān)概念2.1.4進(jìn)程的類型2、父進(jìn)程和子進(jìn)程系統(tǒng)或用戶首先創(chuàng)建的進(jìn)程稱父進(jìn)程；在父進(jìn)程下面的進(jìn)程稱子進(jìn)程。進(jìn)程圖如圖2-5所示：進(jìn)程圖：是一棵包含一個根結(jié)點有向樹，Pi到結(jié)點Pj的一條邊表示進(jìn)程Pj是由進(jìn)程Pi創(chuàng)建的2.1進(jìn)程及其有關(guān)概念圖2.5進(jìn)程圖2.1.4進(jìn)程的類型2、父進(jìn)程和子進(jìn)程進(jìn)程圖反映了進(jìn)程間的父子關(guān)系：創(chuàng)建與被創(chuàng)建、控制與被控制關(guān)系，體現(xiàn)了進(jìn)程間的層次關(guān)系。

父子進(jìn)程間的關(guān)系主要為：⑴進(jìn)程控制：父創(chuàng)建或刪除子⑵運行方式：同時運行或最后運行⑶資源共享：全部或部分共享資源2.1進(jìn)程及其有關(guān)概念2.2.1進(jìn)程的狀態(tài)及其轉(zhuǎn)換1、進(jìn)程的三個基本狀態(tài)⑴運行狀態(tài)⑵就緒狀態(tài)

⑶等待狀態(tài)。也叫阻塞狀態(tài)、掛起狀態(tài)、封鎖狀態(tài)、凍結(jié)狀態(tài)、睡眠狀態(tài)。2、引起進(jìn)程狀態(tài)轉(zhuǎn)換的原因大致如下：⑴CPU調(diào)度；⑵進(jìn)程在運行過程中需要等待某一事件；⑶如果進(jìn)程所等待的事件發(fā)生變化；⑷一個具體的進(jìn)程在任何一個指定的時刻必須而且只能處于一種狀態(tài)。2.2進(jìn)程管理2.2進(jìn)程管理圖2-6進(jìn)程狀態(tài)變遷圖2.2.2進(jìn)程的組成1、進(jìn)程的組成

進(jìn)程由三部分組成：程序、數(shù)據(jù)集合和進(jìn)程控制塊(ProcessControlBlok，PCB)前兩者稱為進(jìn)程的實體，用PCB描述實體的存在和變化。2.2進(jìn)程管理PCB數(shù)據(jù)程序圖2-7進(jìn)程的組成2.2.2進(jìn)程的組成2、進(jìn)程控制塊PCB1)PCB的作用：標(biāo)識進(jìn)程存在的唯一實體2）進(jìn)程控制塊PCB常用的信息如表2-13）PCB中的內(nèi)容主要分為如下3大部分：進(jìn)程標(biāo)識符、處理器狀態(tài)信息、進(jìn)程控制信息

2.2進(jìn)程管理進(jìn)程標(biāo)識符進(jìn)程當(dāng)前狀態(tài)當(dāng)前隊列指針總鏈指針程序開始地址進(jìn)程優(yōu)先級CPU現(xiàn)場保護(hù)區(qū)進(jìn)程通信家族聯(lián)系占有資源清單表2-1PCB的一般結(jié)構(gòu)2.2.2進(jìn)程的組成3、PCB表的兩種組織方式

1）線性表；2）鏈接表。如圖2-8所示

2.2進(jìn)程管理(a)PCB的線性表Next0Next1Next2

∧PCB1PCB2PCBnReady-head高低(b)按優(yōu)先級排列的就緒隊列鏈接表priority2.2.2進(jìn)程的組成3、PCB表的兩種組織方式

2.2進(jìn)程管理Next0Next1Next2

∧PCB1PCB2PCBnReady-head先后(c)按先來先服務(wù)排列的就緒隊列鏈接表FCFS圖2-8PCB表的組織方式4、進(jìn)程的狀態(tài)轉(zhuǎn)換用PCB隊列來表示

2.2進(jìn)程管理圖2.9狀態(tài)轉(zhuǎn)換2.2.3進(jìn)程控制

原語：程序、我們把系統(tǒng)態(tài)下執(zhí)行的某些具有特定功能的程序段。原語可以是機(jī)器指令集的擴(kuò)充，其特點是執(zhí)行期間不允許中斷，它是一個不可分割的基本單位。用于進(jìn)程控制的原語有：創(chuàng)建原語、撤消原語、阻塞原語、喚醒原語等2.2進(jìn)程管理2.2.3進(jìn)程控制

1、創(chuàng)建進(jìn)程創(chuàng)建進(jìn)程原語，操作系統(tǒng)主要完成以下幾項工作：1)創(chuàng)建一個PCB。2)賦予一個統(tǒng)一的進(jìn)程標(biāo)識符。3)為進(jìn)程映象分配空間。4)初始化進(jìn)程控制塊。5)設(shè)置相應(yīng)的鏈接,如把新進(jìn)程加到就緒隊列的鏈表中。2.2進(jìn)程管理假設(shè)我們用n表示進(jìn)程名（外部標(biāo)識符），CPU的初始狀態(tài)為S，優(yōu)先數(shù)為K，內(nèi)存始址為M，資源清單為R，申請的PCB的內(nèi)部標(biāo)識符為i，則創(chuàng)建進(jìn)程原語可描述為：創(chuàng)建原語Create(n,S,K,M,R,acc){i=getnewinternalname(n)；∥為n申請一個PCB，標(biāo)號送入iid[i]=n；∥進(jìn)程外部標(biāo)識符登記第i個PCB相應(yīng)域

priority[i]=K；∥置優(yōu)先數(shù)

cpustate[i]=S；∥置CPU狀態(tài)

mainstore[i]=M；∥置內(nèi)存始址

resourcesp[i]=R；∥置資源表

status[i]=“readys”；∥置該進(jìn)程為就緒狀態(tài)

sdata[i]=RL；∥指向就緒隊列

parent[i]=*；∥置創(chuàng)建它的父進(jìn)程名insert(progeny(*),i)；∥插入進(jìn)程簇中

setaccountingdata；∥建立記帳信息

insert(RL,i)∥將PCB插入就緒隊列}2、刪除進(jìn)程又稱撤消進(jìn)程刪除進(jìn)程的3種情形：1）正常終止；2）由于錯誤非正常終止；3）祖先進(jìn)程要求撤銷

刪除進(jìn)程通常需要完成以下工作：1）定位欲刪除的進(jìn)程PCB；2）回收進(jìn)程所占的全部資源；3）遞歸地刪除其所有“子孫”進(jìn)程；4）刪除PCB，處理記賬信息；5）若刪除的是正在運行的進(jìn)程，則請求重新調(diào)度，否則返回。2.2進(jìn)程管理刪除進(jìn)程原語Kill操作如下：Delete(n){Sched=false;//置調(diào)度標(biāo)志為假I=getinternatname(n);//找內(nèi)部進(jìn)程號Kill(i);//調(diào)刪除進(jìn)程過程If(sched)Scheduler;//若i為運行態(tài)，則重新調(diào)度}

kill(i){If(status[i]==”Executing”)//若i為運行態(tài){stop(i);//停止i的執(zhí)行，保存CPU信息sched=true;//置重新調(diào)度標(biāo)志}remove(sdata[i],i);//從隊列中刪去i進(jìn)程for(alls∈progency(i))kill(s)//刪除i的所有子進(jìn)程for(allr∈(mainstore(i)∪resoure(i)))ifowned[r]then//如果是i的祖先的資源，則全部歸還insert(avail(semaphore(r)),data(r));//給它的祖先for(allR∈creaeresources(i))removeresourcesdescriptot[R];//創(chuàng)建時申請的資源全部歸還給系統(tǒng)removepch[i];//釋放PCB}2.2.3進(jìn)程控制

3、掛起進(jìn)程

進(jìn)程掛起方式：自身掛起；掛起指定標(biāo)識符的進(jìn)程；進(jìn)程全部或部分子孫進(jìn)程掛起

在掛起進(jìn)程控制中主要完成以下工作：1）定位欲掛起的進(jìn)程PCB；2）將其運行的有關(guān)現(xiàn)場信息放至調(diào)用者指定的區(qū)域；3）將進(jìn)程變?yōu)閽炱馉顟B(tài)；4）如果進(jìn)程從運行狀態(tài)變?yōu)閽炱馉顟B(tài)，則請求重新調(diào)度。2.2進(jìn)程管理假設(shè)掛起指定標(biāo)識符為n的進(jìn)程，調(diào)用者指定區(qū)域為a，則掛起進(jìn)程原語可描述為：2.2進(jìn)程管理Suspend(n,a){i=get-internal-name(n);//根據(jù)指定標(biāo)識符n獲取進(jìn)程內(nèi)部號S=status[i];//把狀態(tài)賦給sIf(s==”Executing”)Stop(i);//若進(jìn)程為執(zhí)行態(tài)，則中斷ＣＰＵA=copy-PCB[i];//保存ＰＣＢ狀態(tài)到指定區(qū)域Status(i)=(s=”Blockeda”?”Blockeds”:”Ready”);//若狀態(tài)為活動阻塞，則掛起進(jìn)程為靜止阻塞，否則為就緒狀態(tài)

If(s=”Executing”)Scheduler;//若為執(zhí)行態(tài)，則重新調(diào)度}2.2.3進(jìn)程控制

4、喚醒進(jìn)程

進(jìn)程喚醒方法：1）有系統(tǒng)進(jìn)程喚醒；2）有事件發(fā)生進(jìn)程喚醒

喚醒進(jìn)程原語完成的主要工作如下：1）定位被喚醒的進(jìn)程PCB；2）將其改變?yōu)榫途w狀態(tài)，插入就緒隊列；3）請求重新調(diào)度。2.2進(jìn)程管理假設(shè)喚醒指定標(biāo)識符為n的進(jìn)程，則喚醒進(jìn)程原語可描述為：2.2進(jìn)程管理

Wakeup(n){i=get-internal-name(n);/／找到喚醒進(jìn)程nRemove(WL[r],i);/／從等待隊列中出隊Status[i]=”ready”;／/將其變?yōu)榫途w隊列Insert(RL,i);/／插入就緒隊列Scheduler;/／重新調(diào)度}在以上算法中，WL為等待隊列，RL為就緒隊列。2.2.4進(jìn)度調(diào)度進(jìn)程調(diào)度（也稱CPU調(diào)度）:按照某種調(diào)度算法從就緒隊列中選取進(jìn)程分配CPU，也叫低調(diào)

衡量各種調(diào)度算法性能優(yōu)劣的指標(biāo):

1）CPU利用率——主要目標(biāo)CPU利用率=CPU利用的時間/開機(jī)運行的總時間

2）等待時間3）響應(yīng)時間4）I/O設(shè)備的利用率5）“時空”代價2.2進(jìn)程管理2.2.4進(jìn)度調(diào)度進(jìn)程調(diào)度方式：剝奪調(diào)度和非剝奪調(diào)度下面介紹幾種常見的進(jìn)程調(diào)度方法1.先來先服務(wù)（Firstcomefirstservice,FCFS）2.輪轉(zhuǎn)法（RR，RoundRobin）將CPU的處理時間分成固定大小的時間片，進(jìn)程時間片內(nèi)輪轉(zhuǎn)執(zhí)行

關(guān)鍵問題：如何確定時間片的大小

時間片q=RT/Nmax2.2進(jìn)程管理將考慮下面3個進(jìn)程，它們按1，2，3的順序處于就緒隊列中：進(jìn)程下一個CPU周期

P124P23P33

2.2進(jìn)程管理圖2-10執(zhí)行過程1圖2-11執(zhí)行過程2FCFS調(diào)度算法其他調(diào)度算法2.輪轉(zhuǎn)法設(shè)有如下4個就緒進(jìn)程：進(jìn)程下一個CPU周期

P16P23P31P47

則如圖2-12所示2.2進(jìn)程管理01234567qATT圖2-12平均周轉(zhuǎn)時間ATT與時間片q之間的關(guān)系2.2.4進(jìn)度調(diào)度3.多級反饋輪轉(zhuǎn)法思想：不同級別的就緒隊列分配給不同時間片，優(yōu)先級高的為第一級隊列，時間片最小，隨著隊列級別降低，時間片加大

例如：考慮由3個隊列組成的多級隊列調(diào)度3個隊列的編號分別為0,1,2，如下圖2.2進(jìn)程管理2.2.4進(jìn)度調(diào)度4.優(yōu)先數(shù)法（Priority）思想：按進(jìn)程的優(yōu)先級確定調(diào)度優(yōu)先權(quán)優(yōu)先級確定方法：（1）靜態(tài)法：可按進(jìn)程類型、資源的要求、用戶要求指定（2）動態(tài)法：原則是合理地分配CPU時間、緊急的程序優(yōu)先2.2進(jìn)程管理實例解釋：假設(shè)就緒狀態(tài)有4個進(jìn)程，每個進(jìn)程所需運行時間如下所示。進(jìn)程 所需運行時間

1 62 33147進(jìn)程到達(dá)次序為1，2，3，4。試分別按先來先服務(wù)調(diào)度算法、短進(jìn)程優(yōu)先調(diào)度算法和時間片輪轉(zhuǎn)法(時間片分1，3，5，6)給出進(jìn)程調(diào)度順序，并計算平均等待時間。2.2進(jìn)程管理解：（1）先來先服務(wù)調(diào)度算法進(jìn)程調(diào)度順序為：

平均等待時間：T=1／4×(0+6+9+10)=6.25（2）短進(jìn)程優(yōu)先調(diào)度算法進(jìn)程調(diào)度順序為：平均等待時間：T=1／4×(4+1+0+10)=3.75（3）時間片輪轉(zhuǎn)法

2.2進(jìn)程管理解：·時間片為1，進(jìn)程調(diào)度順序如下：

平均等待時間：T=1/4×((0+3+2+2+1+1)+(1+3+2)+2+(3+2+2+1+1+1)=1／4×(9+6+2+10)=6.75·時間片為3，進(jìn)程調(diào)度順序如下：平均等待時間：T=1／4×((0+7)+3+6+(7+3))=1／4×(7+3+6+10)=6.52.2進(jìn)程管理解：·時間片為5，進(jìn)程調(diào)度順序如下：平均等待時間：T=1／4×((0+9)+5+8+(9+1))=1／4×(9+5+8+10)=8·時間片為6，相當(dāng)于先來先服務(wù)調(diào)度算法。其進(jìn)程調(diào)度順序和平均等待時間與先來先服務(wù)調(diào)度算法相同。總結(jié)：短進(jìn)程優(yōu)先調(diào)度算法使進(jìn)程平均等待時間最小。對于時間片輪轉(zhuǎn)法，進(jìn)程平均等待時間與時間片的大小有關(guān)。

2.2進(jìn)程管理進(jìn)程間的兩種主要關(guān)系：

1、互斥關(guān)系，也稱間接制約關(guān)系：各進(jìn)程間競爭、互斥使用共享資源

2、同步關(guān)系，也稱直接制約關(guān)系：指多個進(jìn)程發(fā)生的事件存在某種時序關(guān)系，需要相互合作，共同完成一項任務(wù)。譬如公共汽車上司機(jī)與售票員的合作就是一種同步關(guān)系。2.3進(jìn)程的同步與互斥同步與互斥的特點比較如表2-1所示。2.3進(jìn)程的同步與互斥同

步互

斥進(jìn)程—進(jìn)程時間次序上受到某種限制相互清楚對方的存在及其作用，交換信息往往指有幾個進(jìn)程共同完成一個任務(wù)舉例：生產(chǎn)與消費之間，發(fā)送與接受之間，作者與讀者之間，供者與用者之間進(jìn)程—資源—進(jìn)程競爭到某一物理資源時不允許進(jìn)程工作不一定清楚其它進(jìn)程情況往往指多個任務(wù)多個進(jìn)程間通訊制約舉例：交通十字路口，單軌火車的撥道岔表2-1同步與互斥的比較2.3.1臨界區(qū)

臨界資源：一次只允許一個進(jìn)程使用的資源

臨界區(qū)：在進(jìn)程中涉及到臨界資源的程序段

使用臨界區(qū)、解決互斥問題應(yīng)遵守以下原則：

1）有空讓進(jìn)2）等待3）多中擇一4）有限等待5）讓權(quán)等待2.3進(jìn)程的同步與互斥2.3.1臨界區(qū)

我們先看一下幾個問題：問題1：設(shè)進(jìn)程P1，P2，共享一臺打印機(jī)問題2：生產(chǎn)者／消費者問題(Producer／Consumer)這里，生產(chǎn)者和消費者進(jìn)程因為共享使用著一個軟件資源――產(chǎn)品系列，若按不恰當(dāng)?shù)膱?zhí)行順序，則隊列操作就會出現(xiàn)混亂。2.3進(jìn)程的同步與互斥小結(jié)：從以上二個例子可以看到，進(jìn)程之間若共享互斥資源(共享外設(shè)—打印機(jī)，共享隊列等)，則會出現(xiàn)互斥問題，即存在臨界區(qū)問題。2.3.2互斥

進(jìn)程互斥進(jìn)入方法：

1、用禁止中斷實現(xiàn)互斥

2、用鎖操作原語實現(xiàn)互斥為共享資源設(shè)置一把鎖。鎖用變量W表示：W=0表示共享資源可用。W=1表示共享資源不可用，已有進(jìn)程訪問

有關(guān)鎖的基本操作如下：

2.3進(jìn)程的同步與互斥加鎖原語LOCK（W）{while(W);W=1;}開鎖原語UNLOCK（W）{W=0;}2.3.2互斥

3、信號量及P、V操作原語實現(xiàn)互斥

信號量(Semaphore)是表示資源的物理實體，是一個與隊列有關(guān)的整型變量。信號量是一個數(shù)據(jù)結(jié)構(gòu),一般定義如下：

strucsemaphore{intvalue; pointer_PCBqueue;}2.3進(jìn)程的同步與互斥信號量說明：

semaphores;3、信號量及P、V操作原語實現(xiàn)互斥P、V操作是指在信號量上定義的兩個操作。設(shè)信號量為s，對s的P操作記為P(s)，對它的操作記為V(s)。2.3進(jìn)程的同步與互斥P操作對應(yīng)的過程如下：P(s){s.value――;if(s.value<0){該進(jìn)程狀態(tài)置為等待狀態(tài);

將該進(jìn)程的PCB插入相應(yīng)的等待隊列末尾s.queue;}}V操作對應(yīng)的過程如下：V(s){s.value++;if(s.value<=0){喚醒相應(yīng)等待隊列s.queue中等待的一個進(jìn)程;改變其狀態(tài)為就緒態(tài);并將其插入就緒隊列;

}}3、信號量及P、V操作原語實現(xiàn)互斥P(s)表示申請一個資源，V(s)表示釋放一個資源。P.V操作必須成對出現(xiàn)2.3進(jìn)程的同步與互斥P1P2…………P(s);P(s);使用打印機(jī);使用打印機(jī)；V(s);V(s);…………下面通過幾個例子進(jìn)一步說明。例1用PV操作解決打印機(jī)共享的問題（如右）s的初值為1，表示打印機(jī)是可用的。例2生產(chǎn)者／消費者問題（自行閱讀）例3用P、V操作實現(xiàn)如圖2-17所示的優(yōu)先圖2.3.3進(jìn)程同步

1、同步類別：

(1)對系統(tǒng)資源的共享。(2)諸進(jìn)程合作完成某工作的邏輯順序。

2、利用信號量機(jī)制解決進(jìn)程同步問題舉例設(shè)有若干個生產(chǎn)者進(jìn)程P1，P2，….Pn，若干個消費者進(jìn)程C1，C2，…Cm，它們通過一個有界緩沖池聯(lián)系起來。其同步問題是：P進(jìn)程不能往“滿”緩沖區(qū)中放產(chǎn)品，C進(jìn)程不能從“空”緩沖區(qū)中取產(chǎn)品。可以采用P.V操作解決。設(shè)各生產(chǎn)者使用的信號量為S1，消費者使用的信號量為S2。2.3進(jìn)程的同步與互斥例1：設(shè)只有一個生產(chǎn)者、一個消費者且緩沖區(qū)的大小為1。S1初值為1、S2為0。S1=1表示最初有一個緩沖區(qū)空間可用，S2=0表示最初沒有產(chǎn)品可消費。2.3進(jìn)程的同步與互斥P：while(true){

生產(chǎn)一個產(chǎn)品;P(s1);

送產(chǎn)品到緩沖區(qū);V(s2);};C：while(true){P(s2);

從緩沖區(qū)取產(chǎn)品;V(s1);

消費產(chǎn)品;};例4再看第二種情況：只有一個生產(chǎn)者、一個消費者且緩沖區(qū)的大小為n。設(shè)S1初值為n，S2初值為0。S1=n表示最初有n個緩沖區(qū)空間可用，S2=0表示最初沒有產(chǎn)品可消費。2.3進(jìn)程的同步與互斥P：i=0;while(true){

生產(chǎn)產(chǎn)品;P(S1);

往Buffer[i]放產(chǎn)品;V(S2);i=(i+1)%n;};

C：j=0;while(true){P(S2);

從Buffer[j]取產(chǎn)品;V(S1);

消費產(chǎn)品;j=(j+1)%n;};例5再看第三種情況：有m一個生產(chǎn)者、k個消費者且緩沖區(qū)的大小為n。設(shè)S1初值為n，S2初值為0，mutex的初值為1（默認(rèn)值）。2.3進(jìn)程的同步與互斥P：i=0;while(true){

生產(chǎn)產(chǎn)品;P(S1);P(mutex);

往Buffer[i]放產(chǎn)品;V(mutex);V(S2);i=(i+1)%n;};C：j=0;while(true){P(S2);P(mutex);

從Buffer[j]取產(chǎn)品;V(mutex);V(S1);

消費產(chǎn)品;j=(j+1)%n;};2.4.1進(jìn)程通信的概念

1、進(jìn)程通信：是指進(jìn)程之間的信息交換。2、進(jìn)程通信類型1)

共享存儲器系統(tǒng)2)消息系統(tǒng)進(jìn)程間的信息交換以消息或者報文為單位消息系統(tǒng)有兩種通信方式：a）直接通信方式

原語：send(接收者ID，消息)和receive(發(fā)送者ID，消息)2.4進(jìn)程通信b）間接通信方式如右圖，進(jìn)程間有中間實體（信箱）2.4進(jìn)程通信發(fā)送進(jìn)程接收進(jìn)程信箱頭信箱1信箱2

間接通信方式3)

利用共享文件（管道）的通信方式

發(fā)送進(jìn)程接收進(jìn)程圖3-12利用共享文件（管道）通信2.4.2消息通信

通信鏈：是指進(jìn)程之間進(jìn)行通信存在的鏈路連接，通信鏈有物理通信鏈和邏輯通信鏈之分。

通信方式主要有：直接或間接通信；對稱或非對稱通信。

1、直接通信

直接通信的一個基本原則是：發(fā)送/接收消息的每一個進(jìn)程，通信時都必須明顯地指明接收/發(fā)送方的名字。2.4進(jìn)程通信2.4.2消息通信

1、直接通信直接通信通信鏈的屬性主要包括以下方面：1）參加通信的雙方；2）每條通信鏈嚴(yán)格地對應(yīng)兩個進(jìn)程；3）任意一對進(jìn)行通信的進(jìn)程，均嚴(yán)格地存在一條通信鏈；4）通信鏈?zhǔn)请p向的，可雙向傳輸

其中，send和receive原語定義為：

Send(P,message):發(fā)送message給進(jìn)程P；

Receive(Q,message):接收來自進(jìn)程Q的message2.4進(jìn)程通信生產(chǎn)者/消費者問題采用直接通信方式的進(jìn)程間的通信進(jìn)程：2.4進(jìn)程通信typedefitem=…；itemnextp,nextc;cobegin;producer{do{…produceaniteminnextp;…send(consumer,nextp);}while(true);}

consumer{do{receive(producer,nextc);…consumetheiteminnextc;…}while(true);}coend利用消息緩沖區(qū)實現(xiàn)直接通訊方式的通訊鏈：2.4進(jìn)程通信圖2-19消息緩沖區(qū)的直接通訊2.4.2消息通信

2、間接通信，又稱郵箱(mailbox)通訊方式進(jìn)程間通過信箱實現(xiàn)通信郵箱是一種數(shù)據(jù)結(jié)構(gòu)，結(jié)構(gòu)如圖2-20

使用信箱的規(guī)則：1）若發(fā)送信件時郵箱已滿，則發(fā)送進(jìn)程被置為“等郵箱”狀態(tài)，直到信箱有空時才被釋放。2）若取信件時信箱中無信，則接收進(jìn)程被置為“等信件”狀態(tài)，直到有信件時才被釋放。2.4進(jìn)程通信圖2-20郵箱結(jié)構(gòu)2.4.2消息通信

2、間接通信，又稱郵箱(mailbox)通訊方式send和receive原語定義如下：send(A,message)：向郵箱A送入message；receive(A,message)：從郵箱A取出message2.4進(jìn)程通信

send實現(xiàn)步驟如下所示：{查找指定郵箱A；若郵箱未滿，則把信件message送入郵箱且釋放“等信件”者；若郵箱已滿置發(fā)送信件進(jìn)程為“等郵箱”狀態(tài)；}receive實現(xiàn)步驟如下所示:{查找指定郵箱A；若郵箱中有信，則取出一封信存于message中且釋放“等郵箱”者；若郵箱中無信件則置接收信件進(jìn)程“等信件”狀態(tài)；}2.4.2消息通信

2、間接通信，又稱郵箱(mailbox)通訊方式在間接通訊方式中，通訊鏈具有如下屬性:1)只有當(dāng)兩個進(jìn)程有了一個可共享的郵箱時，通訊鏈才在二者之間建立。2)通訊鏈能夠聯(lián)系兩個以上的進(jìn)程。3)每一對通訊進(jìn)程之間必須有一組不同的鏈，每條鏈對應(yīng)一個郵箱。4)通訊鏈可以是單向的，又可以是雙向的，如圖2-21所示。2.4進(jìn)程通信2.4進(jìn)程通信圖2-21郵箱通信方式2.5