第四章互斥同步與通訊課件

第四章互斥、同步與通訊進(jìn)程(線(xiàn)程)之間的相互作用：

互斥、同步、通訊4.1并發(fā)進(jìn)程(concurrentprocesses)4.2進(jìn)程互斥(mutualexclusion)4.3進(jìn)程同步(synchronization)4.4進(jìn)程高級(jí)通訊(communication)第四章互斥、同步與通訊進(jìn)程(線(xiàn)程)之間的相互作用：4.1.1順序程序及其特性程序的順序性有兩層含義:(1)內(nèi)部順序性：指一個(gè)進(jìn)程的所有指令

按序執(zhí)行;(2)外部順序性：指多個(gè)進(jìn)程依次執(zhí)行;例如,假設(shè)有兩個(gè)進(jìn)程P1和P2：P1活動(dòng):a1a2a3a4P2活動(dòng):b1b2b3順序執(zhí)行時(shí),有如下兩種情形:情形1:a1a2a3a4

b1b2b3

情形2:b1b2b3

a1a2a3a4

4.1并發(fā)進(jìn)程4.1.1順序程序及其特性4.1并發(fā)進(jìn)程順序程序的特性：(1)順序性：處理機(jī)嚴(yán)格按指令次序依次執(zhí)行，僅當(dāng)一條指令執(zhí)行完才開(kāi)始執(zhí)行下一指令；(2)封閉性：程序在執(zhí)行過(guò)程中獨(dú)占系統(tǒng)的全部資源。該程序的運(yùn)行環(huán)境只與其自身動(dòng)作有關(guān)，不受其它程序及外界因素影響；(3)可再現(xiàn)性：程序的執(zhí)行結(jié)果只與初始條件有關(guān)，與執(zhí)行速度無(wú)關(guān)。給定相同的初始條件，程序的任意多次執(zhí)行一定得到相同結(jié)果。順序程序的特性：4.1.2并發(fā)程序及其特性程序的并發(fā)性有兩層含義:(1)內(nèi)部并發(fā)性：指一個(gè)進(jìn)程的所有指令不一定按序執(zhí)行;(2)外部并發(fā)性:指多個(gè)進(jìn)程交叉執(zhí)行。例如，假設(shè)有兩個(gè)進(jìn)程：P1活動(dòng):a1a2a3a4P2活動(dòng):b1b2b3

內(nèi)部并發(fā)性如：P2:b1,b3,b2;……

外部并發(fā)性如:情形1:a1b1b2a2a3b3a4情形2:b1b2a1a2a3b3a4

……并發(fā)進(jìn)程在執(zhí)行過(guò)程中出現(xiàn)哪種交叉情形是不可預(yù)知的,這就是并發(fā)程序的不確定性。4.1.2并發(fā)程序及其特性并發(fā)程序的特性：(1)交叉性：一個(gè)進(jìn)程的某些指令可交叉執(zhí)行，不同的進(jìn)程亦可交叉執(zhí)行；程序并發(fā)執(zhí)行時(shí)，不同的交叉可能導(dǎo)致不同的計(jì)算結(jié)果。OS應(yīng)保證只產(chǎn)生導(dǎo)致正確結(jié)果的交叉，去除那些可能導(dǎo)致不正確結(jié)果的交叉。(2)非封閉性：一個(gè)進(jìn)程的運(yùn)行環(huán)境可能被其它進(jìn)程改變，從而相互影響。(3)不可再現(xiàn)性：并發(fā)程序的多次執(zhí)行可能對(duì)應(yīng)不同的交叉，因而不能期望重新運(yùn)行的程序能夠再現(xiàn)上次運(yùn)行的結(jié)果。如運(yùn)行時(shí)間并發(fā)程序的特性：4.1.2與時(shí)間有關(guān)的錯(cuò)誤例如圖書(shū)借閱系統(tǒng)(設(shè)x:某種書(shū)冊(cè)數(shù)，當(dāng)前x=1)終端1：終端2：CYCLECYCLE等待借書(shū)者；等待借書(shū)者；IFx>=1ThenIFx>=1ThenBeginBeginx:=x-1;x:=x-1;借書(shū)借書(shū)EndEndElse無(wú)書(shū)Else無(wú)書(shū)EndEnd12344.1.2與時(shí)間有關(guān)的錯(cuò)誤例如圖書(shū)借閱系統(tǒng)(設(shè)x:某上述錯(cuò)誤的發(fā)生與進(jìn)程的推進(jìn)速度有關(guān)(速度是時(shí)間的函數(shù))。當(dāng)進(jìn)程P1執(zhí)行到③處被中斷,之后P2插入,則不會(huì)發(fā)生上述錯(cuò)誤。若一種錯(cuò)誤的發(fā)生與進(jìn)程的推進(jìn)速度有關(guān)，則稱(chēng)這種錯(cuò)誤為與時(shí)間有關(guān)的錯(cuò)誤。發(fā)生與時(shí)間有關(guān)錯(cuò)誤的原因：(1)進(jìn)程執(zhí)行交叉(interleave)。(2)涉及公共變量(x)。若兩個(gè)進(jìn)程同時(shí)對(duì)變量x進(jìn)行操作,其中一個(gè)進(jìn)程對(duì)x的操作僅做了一部分時(shí),另一個(gè)進(jìn)程中途插入，則可能使變量x處于一種不確定狀態(tài)，從而失去其數(shù)據(jù)完整性。OS必須防止這種情況的發(fā)生。上述錯(cuò)誤的發(fā)生與進(jìn)程的推進(jìn)速度有關(guān)(速度是時(shí)間的函數(shù)4.2進(jìn)程互斥

(mutualexclusion)

進(jìn)程互斥是進(jìn)程間發(fā)生的一種間接相互作用,這種相互作用是進(jìn)程本身不希望的,也是運(yùn)行進(jìn)程感覺(jué)不到的。

進(jìn)程互斥可能發(fā)生在相關(guān)進(jìn)程之間,也可能發(fā)生在無(wú)關(guān)進(jìn)程之間。4.2進(jìn)程互斥

(mutualexclusion)4.2.1共享變量與臨界區(qū)

(sharedvariable&criticalregion)1.共享變量與臨界區(qū)的概念共享變量：可以被多個(gè)進(jìn)程訪(fǎng)問(wèn)的變量。也稱(chēng)公共變量。

臨界區(qū)：訪(fǎng)問(wèn)共享變量的程序段。也稱(chēng)為臨界段(criticalsection)。共享變量與臨界區(qū)的關(guān)系：

一組公共變量CR1CR2CRn…….4.2.1共享變量與臨界區(qū)一組公共變量CR1CR2CRn2.共享變量與臨界區(qū)的表示共享變量的表示(說(shuō)明)：

shared<一組變量>

如，sharedx1,x2;臨界區(qū)的表示:

region<一組變量>do<語(yǔ)句>這是一個(gè)語(yǔ)句,稱(chēng)作臨界區(qū)語(yǔ)句。其中<語(yǔ)句>可為任意語(yǔ)句,包括臨界區(qū)語(yǔ)句。例如，regionx1,x2do{…(訪(fǎng)問(wèn)x1,x2)…}再如，sharedb:array[0,..,n-1]ofinteger;regionbdobegin……(訪(fǎng)問(wèn)b)end;

2.共享變量與臨界區(qū)的表示若一個(gè)臨界區(qū)語(yǔ)句中的<語(yǔ)句>部分包括另一個(gè)臨界區(qū)語(yǔ)句,便發(fā)生了臨界區(qū)嵌套。例如，sharedx1,x2;sharedy1,y2;

regionx1,x2do{……

regiony1,y2do{……}……}若一個(gè)臨界區(qū)語(yǔ)句中的<語(yǔ)句>部分包括另一個(gè)臨界區(qū)語(yǔ)句,再如，sharedx1,x2;sharedy1,y2;

regionx1,x2doregiony1,y2dobeginbegin………….

regiony1,y2doregionx1,x2dobeginbegin…….…….endendend;end;再如，sharedx1,x2;4.2.2臨界區(qū)與進(jìn)程互斥進(jìn)程互斥:兩個(gè)或兩個(gè)以上的進(jìn)程不能同時(shí)進(jìn)入關(guān)于同一組共享變量的臨界區(qū),否則可能發(fā)發(fā)生與時(shí)間有關(guān)的錯(cuò)誤,這種現(xiàn)象被稱(chēng)作進(jìn)

程互斥。進(jìn)程互斥有兩層含義:(1)不容許多個(gè)進(jìn)程同時(shí)進(jìn)入關(guān)于同一組共享變量的相同的臨界區(qū)；(2)不容許多個(gè)進(jìn)程同時(shí)進(jìn)入關(guān)于同一組共享變量的不同的臨界區(qū)。注意：進(jìn)程互斥是相對(duì)于共享變量而言的。4.2.2臨界區(qū)與進(jìn)程互斥當(dāng)然，若容許多個(gè)進(jìn)程同時(shí)進(jìn)入關(guān)于同一組共享變量的臨界區(qū)，也不是一定會(huì)發(fā)生錯(cuò)誤。是否會(huì)發(fā)生錯(cuò)誤與進(jìn)程并發(fā)執(zhí)行時(shí)的推進(jìn)速度有關(guān)。

不容許多個(gè)進(jìn)程同時(shí)進(jìn)入關(guān)于同一組共享變量的臨界區(qū)，是保證正確性的要求。這件事的實(shí)現(xiàn)應(yīng)由OS及并發(fā)程序設(shè)計(jì)者在編寫(xiě)程序時(shí)保證，這需要必要的互斥機(jī)制。當(dāng)然，若容許多個(gè)進(jìn)程同時(shí)進(jìn)入關(guān)于同一組共享變量使用嵌套的臨界區(qū)時(shí)需特別注意，否則可能會(huì)發(fā)生不期望的后果。例如，sharedx;sharedy;

regionxdo{regionydo{……(1)……(2)

regionydo{regionxdo{…………}}}}當(dāng)進(jìn)程P1執(zhí)行到(1)、進(jìn)程P2執(zhí)行到(2)時(shí)，P1已進(jìn)入關(guān)于x的臨界區(qū)，要求進(jìn)入關(guān)于y的臨界區(qū)，P2則反之。由于臨界區(qū)是互斥的，因此二者均無(wú)法繼續(xù)向前推進(jìn)，這種現(xiàn)象稱(chēng)為死鎖(第五章)。使用嵌套的臨界區(qū)時(shí)需特別注意，否則可能會(huì)發(fā)生不4.2.3進(jìn)程互斥的實(shí)現(xiàn)

進(jìn)程互斥的實(shí)現(xiàn)就是實(shí)現(xiàn)對(duì)臨界區(qū)的管理。

對(duì)臨界區(qū)的管理應(yīng)滿(mǎn)足如下管理原則：(進(jìn)程互斥的Requirements)(1)正確性原則(correctness)：mutualexclusion一次只允許一個(gè)進(jìn)程活動(dòng)在關(guān)于同一組公共變量的臨界區(qū)中。即任意時(shí)刻最多只能有一個(gè)進(jìn)程處于關(guān)于同一組共享變量的臨界區(qū)中；4.2.3進(jìn)程互斥的實(shí)現(xiàn)(2)公平性原則(fairness)：boundedwaiting一個(gè)請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程應(yīng)在有限時(shí)間內(nèi)獲得進(jìn)入該臨界區(qū)的機(jī)會(huì)；(3)進(jìn)展性原則(progress)：臨界區(qū)空閑時(shí)，競(jìng)爭(zhēng)進(jìn)入臨界區(qū)的多個(gè)進(jìn)程在有限時(shí)間內(nèi)確定下一個(gè)進(jìn)入臨界區(qū)的進(jìn)程。以上原則是對(duì)互斥的實(shí)現(xiàn)而言的。臨界區(qū)的管理實(shí)現(xiàn)后，使用時(shí)，如果不慎可能會(huì)違背上述原則。例如，臨界區(qū)中的程序出現(xiàn)了死循環(huán)。

(2)公平性原則(fairness)：bounded臨界區(qū)相當(dāng)于一個(gè)獨(dú)占型資源。對(duì)臨界區(qū)資源的管理應(yīng)滿(mǎn)足如下調(diào)度原則:

(1)當(dāng)關(guān)于某一組共享變量的所有臨界區(qū)均為空閑時(shí),一個(gè)要求進(jìn)入該組共享變量某一臨界區(qū)的進(jìn)程應(yīng)能立即進(jìn)入;(2)當(dāng)關(guān)于某一組共享變量的某一臨界區(qū)域被占用時(shí),一個(gè)要求進(jìn)入該組共享變量某一臨界區(qū)域的進(jìn)程應(yīng)等待;(3)當(dāng)一個(gè)進(jìn)程離開(kāi)關(guān)于某一組共享變量的某一臨界區(qū)時(shí),應(yīng)容許某一個(gè)等待進(jìn)入關(guān)于該組共享變量某一臨界區(qū)域的進(jìn)程進(jìn)入。臨界區(qū)相當(dāng)于一個(gè)獨(dú)占型資源。4.2.3.1進(jìn)程互斥的軟件實(shí)現(xiàn)

進(jìn)程互斥的軟件實(shí)現(xiàn)指完全用程序?qū)崿F(xiàn)進(jìn)程的互斥，不需特殊硬件指令的支持。進(jìn)程互斥的軟件實(shí)現(xiàn)方法可用于單CPU和多CPU環(huán)境中。進(jìn)程互斥的軟件實(shí)現(xiàn)有忙式等待問(wèn)題。4.2.3.1進(jìn)程互斥的軟件實(shí)現(xiàn)進(jìn)程互斥的軟Repeat

criticalsection

remaindersectionUntilfalseentrysectionexitsectionFramework進(jìn)程互斥的軟件實(shí)現(xiàn)算法：Lamport面包店算法Eisenberg算法兩種算法均假定系統(tǒng)中進(jìn)程的個(gè)數(shù)有限，如n個(gè)實(shí)現(xiàn)進(jìn)程互斥的軟件的結(jié)構(gòu)框架：Repeatentrysectionexitsectio面包店算法的基本思想來(lái)源于顧客在面包店購(gòu)買(mǎi)面包時(shí)的排隊(duì)原理。顧客進(jìn)入面包店前,首先抓一個(gè)號(hào)碼,然后按號(hào)碼由小到大的次序依次進(jìn)入面包店購(gòu)買(mǎi)面包。這里假定：

(1)面包店按由小到大的次序發(fā)放號(hào)碼,且兩個(gè)或兩個(gè)以上的顧客有可能得到相同號(hào)碼(要使顧客的號(hào)碼不同，需互斥機(jī)制)。

(2)若多個(gè)顧客抓到相同號(hào)碼,則按顧客名字的字典次序排序(假定顧客沒(méi)有重名)。計(jì)算機(jī)系統(tǒng)中,顧客相當(dāng)于進(jìn)程,每個(gè)進(jìn)程有一個(gè)唯一的標(biāo)識(shí),用Pi,i=1,2,…表示。對(duì)于Pi和Pj，若有i<j，即Pi先進(jìn)入臨界區(qū)，則先為Pi服務(wù)。1.Lamport面包店算法面包店算法的基本思想來(lái)源于顧客在面包店購(gòu)買(mǎi)面包時(shí)的排面包店算法的基本思想：

首先設(shè)置一個(gè)發(fā)號(hào)器，按由小到大的次序發(fā)放號(hào)碼。進(jìn)程進(jìn)入臨界區(qū)前先抓一個(gè)號(hào)碼，然后按號(hào)碼由小到大的次序依次進(jìn)入臨界區(qū)。若多個(gè)進(jìn)程抓到相同的號(hào)碼，則按進(jìn)程編號(hào)依次進(jìn)入。面包店算法的基本思想：

實(shí)現(xiàn)面包店算法所需的數(shù)據(jù)結(jié)構(gòu):intchoosing[n]；intnumber[n]；或choosing:ARRAY[0..n-1]OFinteger;number:ARRAY[0..n-1]OFinteger;choosing[n]用來(lái)表示進(jìn)程是否正在抓號(hào)，其初值均為0。若進(jìn)程i正在抓號(hào)，則choosing[i]賦為1，否則choosing[i]為0。number[n]用來(lái)記錄進(jìn)程抓到的號(hào)碼，其初值均為0。若number[i]為0,則進(jìn)程Pi沒(méi)有抓號(hào)；若number[i]不為0,則其正整數(shù)值為進(jìn)程Pi抓到的號(hào)碼。實(shí)現(xiàn)面包店算法所需的數(shù)據(jù)結(jié)構(gòu):為便于面包店算法的描述,引入下述表記法：<1>設(shè)(a,b):Pi，(c,d):Pj，則

(a,b)<(c,d)iff(a<c)or(a=candb<d)<2>max(a0,…,an-1)=k：對(duì)所有的i,0in-1,k≥ai,k為正整數(shù)。為便于面包店算法的描述,引入下述表記法：算法4.1Lamport面包店算法do{choosing[i]=1;number[i]=max(number[0],number[1],…,

number[n-1])+1;

choosing[i]=0;for(j=0;j<n;j++){

while(choosing[j])skip;while((number[j]<>0)&&(number[j],j)<(number[i],i))skip;};

臨界區(qū)

number[i]=0;

其余部分}while(1);(1)P1抓到1尚未賦值(2)P2抓到1(3)P3抓到2算法4.1Lamport面包店算法(1)P1抓到1尚未變量choosing的作用

當(dāng)進(jìn)程Pi計(jì)算完max(…)+1但尚未將值賦給number[i]時(shí)，進(jìn)程Pj中途插入，計(jì)算max(…)+1，得到相同的值。在這種情況下，choosing[j]保證編號(hào)較小的進(jìn)程先進(jìn)入臨界區(qū)。

變量choosing的作用忙式等待：上述Lamport面包店算法中，若while循環(huán)的循環(huán)條件成立，則進(jìn)程將重復(fù)測(cè)試，直到條件為假。實(shí)際上，當(dāng)while循環(huán)條件成立時(shí)，進(jìn)程Pi不能向前推進(jìn)，而在原地踏步，這種原地踏步被稱(chēng)為忙式等待(busywaiting)。忙式等待空耗CPU資源，因而是低效的。忙式等待：驗(yàn)證面包店算法是否滿(mǎn)足臨界區(qū)管理原則：(1)正確性：若進(jìn)程Pj已在CS，而進(jìn)程Pi(ij)擁有與Pj不同的號(hào)，則(number[j],j)<(number[i],i))。此時(shí)進(jìn)程Pi若試圖進(jìn)入該臨界區(qū)，則忙式等待，直至進(jìn)程Pj離開(kāi)臨界區(qū)。(2)公平性：因進(jìn)程按FIFO次序進(jìn)入臨界區(qū)，且進(jìn)程個(gè)數(shù)有限，故進(jìn)程不會(huì)無(wú)限等待進(jìn)入臨界區(qū)。(3)進(jìn)展性：當(dāng)多個(gè)進(jìn)程競(jìng)爭(zhēng)進(jìn)入臨界區(qū)時(shí)，下述條件之一成立：<1>一個(gè)進(jìn)程抓到最小號(hào)碼；<2>若干進(jìn)程抓到最小號(hào)碼。情形<1>抓到最小號(hào)碼的進(jìn)程獲準(zhǔn)進(jìn)入臨界區(qū)；情形<2>抓到最小號(hào)碼且編號(hào)最小的進(jìn)程獲準(zhǔn)進(jìn)入臨界區(qū)。因而能在有限時(shí)間內(nèi)確定進(jìn)入臨界區(qū)的進(jìn)程。驗(yàn)證面包店算法是否滿(mǎn)足臨界區(qū)管理原則：

Eisenberg算法采用的數(shù)據(jù)結(jié)構(gòu):enumflag[n](idle,want_in,in_cs);intturn;//intherangeof(0,n-1)intj;//intherangeof(0,n-1)或flag:ARRAY[0..n-1]OF(idle,want_in,in_cs);

其中,flag[i]=idle:進(jìn)程Pi不想進(jìn)入臨界區(qū),

flag[i]=want_in:進(jìn)程Pi想進(jìn)入臨界區(qū),

flag[i]=in_cs:進(jìn)程Pi想進(jìn)或已進(jìn)臨界區(qū),flag的所有元素初值均為idle，

turn的初值為0到n-1之間的任一正整數(shù)，

j為每個(gè)進(jìn)程擁有的一個(gè)局部變量,其初值為0到n-1之間的任一正整數(shù)。2.Eisenberg/Mcguire算法Eisenberg算法采用的數(shù)據(jù)結(jié)構(gòu):2.Eisenbe算法4.2

Eisenberg/Mcguire算法do{

do{

flag[i]=want_in;

j=turn;//turn表示允許進(jìn)入CS的進(jìn)程編號(hào)while(j!=i)if(flag[j]!=idle)

j=turn;elsej=(j+1)%n;//mod

flag[i]=in_cs;

j=0;while((j<n)&&(j==i||flag[j]!=in_cs))

j++;}while(j!=n);turn=i;

臨界區(qū)算法4.2Eisenberg/Mcguire算法//臨界區(qū)

j=(turn+1)%n;while(flag[j]==idle)

j=(j+1)%n;turn=j;flag[i]=idle;其余部分}while(1);

//臨界區(qū)

驗(yàn)證Eisenberg算法是否滿(mǎn)足臨界區(qū)管理原則：(1)互斥性：僅當(dāng)對(duì)所有的ji且flag[j]in-cs時(shí),進(jìn)程Pi才進(jìn)入其臨界區(qū),故滿(mǎn)足互斥性原則。(2)公平性：一個(gè)進(jìn)程離開(kāi)臨界區(qū)時(shí)，它必須在循環(huán)次序中指定唯一一個(gè)競(jìng)爭(zhēng)進(jìn)程作為其后繼，故任一要求進(jìn)入臨界區(qū)的進(jìn)程最多在n-1個(gè)進(jìn)程進(jìn)入并離開(kāi)臨界區(qū)后一定能進(jìn)入臨界區(qū),故滿(mǎn)足公平性。(3)進(jìn)展性：如果沒(méi)有進(jìn)程正處于臨界區(qū)或離開(kāi)臨界區(qū)，則turn的值不變。競(jìng)爭(zhēng)進(jìn)程按循環(huán)次序turn,

turn+1,…,n-1,0,…,turn-1進(jìn)入臨界區(qū)，故滿(mǎn)足進(jìn)展性原則。Eisenberg算法同樣存在忙式等待問(wèn)題。驗(yàn)證Eisenberg算法是否滿(mǎn)足臨界區(qū)管理原則：4.2.3.2進(jìn)程互斥的硬件實(shí)現(xiàn)用硬件方法實(shí)現(xiàn)互斥通常比軟件方法簡(jiǎn)單。

1.硬件提供“測(cè)試并建立”(TestandSet,TS)指令

“測(cè)試并建立”指令實(shí)質(zhì)上是取出內(nèi)存某一單元的值，再給該單元賦一個(gè)新值。該指令在執(zhí)行時(shí)不可被分割，是原子的。

“測(cè)試并建立”指令的定義如下:intTS(int&target){inttemp;temp:=*target;*target=1;return(temp);}4.2.3.2進(jìn)程互斥的硬件實(shí)現(xiàn)用硬件方法實(shí)現(xiàn)互斥若硬件提供了“測(cè)試并建立”指令,則可按如下方法實(shí)現(xiàn)進(jìn)程互斥：對(duì)每組共享變量,定義一個(gè)全局變量：intlock;//lock初值為0,表示無(wú)進(jìn)程在臨界區(qū)

算法4.3

基于TS指令的互斥算法

(不公平)do{while(TS(lock))skip;

臨界區(qū)

lock=0;其余部分}while(1);若lock當(dāng)前值為0,則賦為1,進(jìn)入臨界區(qū)；若lock當(dāng)前值為1,則反復(fù)測(cè)試直到lock變?yōu)?,存在忙式等待。若硬件提供了“測(cè)試并建立”指令,則可按如下方法實(shí)2.硬件提供“交換”(swap)指令

交換指令將兩個(gè)內(nèi)存單元中的內(nèi)容相互交換。交換指令也是原子的。

交換指令的定義如下:voidswap(int&a,&b){inttemp;temp=*a;*a=*b;*b=temp;}交換指令在執(zhí)行時(shí)也是不可分割的,即要求在一個(gè)指令周期內(nèi)執(zhí)行完。2.硬件提供“交換”(swap)指令若硬件提供了“交換”指令,則可按如下方法實(shí)現(xiàn)進(jìn)程互斥：對(duì)每組共享變量，定義一個(gè)全局變量:int

lock

;//lock初值為0

對(duì)每個(gè)要求進(jìn)入關(guān)于該組共享變量的臨界區(qū)的進(jìn)程，定義一個(gè)局部變量:intkey;算法4.4基于swap指令的互斥算法

(不公平)do{key=1;do{swap(&lock,&key);}while(key==1)

臨界區(qū)

lock=0;其余部分}while(1);若硬件提供了“交換”指令,則可按如下方法實(shí)現(xiàn)進(jìn)程互斥：上述兩個(gè)互斥算法均不滿(mǎn)足有限等待原則。

為滿(mǎn)足有限等待原則,需引入新的全局變量:intwaiting[n];//初值均為0intlock;//初值為0每一進(jìn)程亦需引入新的局部變量:intj;intkey;

上述兩個(gè)互斥算法均不滿(mǎn)足有限等待原則。算法4.5公平性硬件互斥算法do{waiting[i]=1;key=1;while(waiting[i]&&key)

key=TS(&lock);//忙式等待waiting[i]=0;

臨界區(qū)

j=(i+1)%n;//modwhile((j!=i)&&(!waiting[j]))

j=(j+1)%n;if(j==i)lock=0;elsewaiting[j]=0;其余部分}while(1);算法4.5公平性硬件互斥算法3.硬件提供“開(kāi)/關(guān)中斷”指令開(kāi)/關(guān)中斷是實(shí)現(xiàn)進(jìn)程互斥的一種特殊硬件方法。若硬件提供了開(kāi)/關(guān)中斷指令,則進(jìn)程進(jìn)入臨界區(qū)前只需執(zhí)行一條關(guān)中斷指令,離開(kāi)臨界區(qū)時(shí)只需執(zhí)行一條開(kāi)中斷指令。算法4.6開(kāi)/關(guān)中斷互斥算法do{關(guān)中斷

臨界區(qū)

開(kāi)中斷其余部分}while(1)3.硬件提供“開(kāi)/關(guān)中斷”指令由于中斷是進(jìn)程切換的必要條件，關(guān)中斷后不會(huì)發(fā)生進(jìn)程切換，故進(jìn)入臨界區(qū)的進(jìn)程將連續(xù)不斷地執(zhí)行完臨界區(qū)的全部指令，因而滿(mǎn)足互斥性。易證，它亦滿(mǎn)足公平性。

用開(kāi)關(guān)中斷法實(shí)現(xiàn)進(jìn)程互斥的優(yōu)點(diǎn):(1)實(shí)現(xiàn)效率高。(2)不存在忙式等待問(wèn)題。(3)簡(jiǎn)單易行。

用開(kāi)關(guān)中斷法實(shí)現(xiàn)進(jìn)程互斥的缺點(diǎn):(1)僅在單CPU系統(tǒng)中有效。{因?yàn)樵诙郈PU系統(tǒng)中，關(guān)中斷不能阻止代表不同進(jìn)程的多個(gè)CPU同時(shí)對(duì)關(guān)于同一組共享變量的臨界區(qū)進(jìn)行訪(fǎng)問(wèn)}(2)影響系統(tǒng)的并發(fā)性。由于中斷是進(jìn)程切換的必要條件，關(guān)中斷后不會(huì)發(fā)生進(jìn)程4.2.4多處理機(jī)環(huán)境下的進(jìn)程互斥

單處理機(jī)環(huán)境中可使用硬件提供的swap指令或TS指令實(shí)現(xiàn)進(jìn)程互斥，這些指令涉及對(duì)同一存儲(chǔ)單元的兩次或兩次以上操作，這些操作將在幾個(gè)指令周期內(nèi)完成。由于中斷只發(fā)生在兩條機(jī)器指令之間，同一指令內(nèi)的多個(gè)指令周期不可中斷，因而swap或TS指令的執(zhí)行不會(huì)交叉進(jìn)行。

多處理機(jī)環(huán)境中情況有所不同。例如，兩個(gè)CPU執(zhí)行TS(lock)可能發(fā)生指令周期的交叉。由于TS指令包括取數(shù)、送數(shù)兩個(gè)指令周期，若lock初始為0，CPU1和CPU2可能分別執(zhí)行完前一指令周期并通過(guò)檢測(cè)(均為0)，然后分別執(zhí)行后一指令周期將lock置為1，結(jié)果都取回0作為判斷臨界區(qū)空閑的依據(jù)，故不能實(shí)現(xiàn)互斥。4.2.4多處理機(jī)環(huán)境下的進(jìn)程互斥單處理機(jī)環(huán)境中可使用內(nèi)存Initial:0CPU1CPU2Bus1.讀03.寫(xiě)1

2.讀04.寫(xiě)1內(nèi)存Initial:0CPU1CPU2Bus1.讀03.多CPU環(huán)境中要利用TS指令實(shí)現(xiàn)進(jìn)程互斥，需提供進(jìn)一步的硬件支持，以保證TS指令執(zhí)行的原子性。這種支持目前多以“鎖總線(xiàn)”(bus-locking)的形式提供。由于TS指令對(duì)內(nèi)存的兩次操作都需經(jīng)過(guò)總線(xiàn)，故在執(zhí)行TS指令前鎖住總線(xiàn)，在執(zhí)行TS指令后開(kāi)放總線(xiàn)，可保證TS指令執(zhí)行的原子性。多CPU環(huán)境中要利用TS指令實(shí)現(xiàn)進(jìn)程互斥，需提供進(jìn)一步算法4.6多處理機(jī)互斥算法do{b=1;while(b){

lock(bus);//忙式等待

b=TS(&lock);

unlock(bus);}

臨界區(qū)

lock=0;其余部分}while(1)算法4.6多處理機(jī)互斥算法自旋鎖：忙式等待鎖稱(chēng)為自旋鎖(spin-lock)。上述多處理機(jī)互斥算法中的鎖為自旋鎖。自旋鎖是在多處理機(jī)系統(tǒng)中經(jīng)常采用的互斥方法。自旋鎖一般是低效的。在許多SMP系統(tǒng)中，允許多個(gè)CPU同時(shí)執(zhí)行目態(tài)程序。由于一次只允許一個(gè)CPU執(zhí)行OS代碼，因而利用自旋鎖可實(shí)現(xiàn)這種控制。一次只允許一個(gè)CPU執(zhí)行核心代碼，使得系統(tǒng)的并發(fā)性不高。若期望核心程序在多CPU之間的并行執(zhí)行，可將核心分為若干相對(duì)獨(dú)立的部分，不同的CPU可同時(shí)進(jìn)入并執(zhí)行核心中的不同部分。實(shí)現(xiàn)時(shí)可為每個(gè)相對(duì)獨(dú)立的區(qū)域設(shè)置一個(gè)自旋鎖。自旋鎖：忙式等待鎖稱(chēng)為自旋鎖(spin-lock4.3進(jìn)程同步例如，司機(jī)-售票員問(wèn)題司機(jī)活動(dòng)：售票員活動(dòng)：do{do{啟動(dòng)車(chē)輛關(guān)車(chē)門(mén)正常行駛售票到站停車(chē)開(kāi)車(chē)門(mén)}while(1)}while(1)進(jìn)程同步是進(jìn)程之間的直接相互作用，是合作進(jìn)程之間有意識(shí)的行為,這種相互作用只發(fā)生在相關(guān)進(jìn)程之間。4.3進(jìn)程同步例如，司機(jī)-售票員問(wèn)題

4.3.1進(jìn)程同步的概念

進(jìn)程同步：一組進(jìn)程，為了協(xié)調(diào)其推進(jìn)速度，在某些點(diǎn)處需要相互等待與相互喚醒，進(jìn)程之間的這種相互制約關(guān)系稱(chēng)為進(jìn)程同步。

注意：進(jìn)程同步僅發(fā)生于有邏輯關(guān)系的進(jìn)程之間；進(jìn)程互斥可能發(fā)生于任意兩個(gè)進(jìn)程之間。與進(jìn)程同步相關(guān)的另一概念是進(jìn)程合作。

進(jìn)程合作：一組進(jìn)程單獨(dú)不能正常進(jìn)行,但并發(fā)可以正常進(jìn)行的現(xiàn)象稱(chēng)為進(jìn)程合作。參與合作的進(jìn)程稱(chēng)為合作進(jìn)程。進(jìn)程同步是合作進(jìn)程之間的直接相互作用。4.3.1進(jìn)程同步的概念4.3.2進(jìn)程同步機(jī)制

同步機(jī)制：用于實(shí)現(xiàn)進(jìn)程間同步的工具稱(chēng)作同步機(jī)制，亦稱(chēng)同步設(shè)施。

典型的同步機(jī)制：

信號(hào)燈與PV操作(semaphoreandPVoperations)管程(monitor)條件臨界區(qū)(conditionalcriticalregion)路徑表達(dá)式(pathexpression)會(huì)合(rendezvous)(用于分布式系統(tǒng)）事件(traditionalUNIX)4.3.2進(jìn)程同步機(jī)制

同步機(jī)制應(yīng)滿(mǎn)足的基本要求:

(1)描述能力夠用。即用此種同步機(jī)制應(yīng)能描述操作系統(tǒng)及并發(fā)程序設(shè)計(jì)中所遇到的各種同步問(wèn)題(例如，生產(chǎn)者消費(fèi)者問(wèn)題、讀者寫(xiě)者問(wèn)題、哲學(xué)家就餐問(wèn)題);(2)可以實(shí)現(xiàn);(3)效率高;(4)使用方便。同步機(jī)制應(yīng)滿(mǎn)足的基本要求:4.3.3信號(hào)燈與PV操作荷蘭E.W.Dijkstra于1965年提出。這種同步機(jī)制包括一種信號(hào)燈變量及對(duì)此種變量所能進(jìn)行的操作：P操作和V操作。

1.信號(hào)燈與PV操作的定義

信號(hào)燈類(lèi)型定義如下：typedefsemaphorestruct{intvalue;pointer_to_PCBqueue;}

信號(hào)燈變量說(shuō)明如下：

semaphore

s;4.3.3信號(hào)燈與PV操作荷蘭E.W.Dijk可見(jiàn),一個(gè)信號(hào)燈變量包括兩部分：值部分s.value和指針部分s.queue。在任意時(shí)刻，s.queue可能指向空，也可能指向一個(gè)PCB隊(duì)列的首部。初始時(shí)s.queue指向空。S.valueS.queuePCBPCBPCBS.valueS.queue…可見(jiàn),一個(gè)信號(hào)燈變量包括兩部分：值部分s.val

P操作原語(yǔ)的定義:voidP(semaphore*s){s->value--；if(s->value<0)

asleep(s->queue);}

asleep(s->queue)：(1)將執(zhí)行此操作的那個(gè)進(jìn)程的PCB插入s->queue所指PCB隊(duì)列的尾部,其狀態(tài)由運(yùn)行轉(zhuǎn)為等待；(2)轉(zhuǎn)到處理機(jī)調(diào)度程序。

原語(yǔ):一段不可間斷執(zhí)行的程序稱(chēng)為原語(yǔ)。說(shuō)明：P操作對(duì)應(yīng)申請(qǐng)資源。P操作原語(yǔ)的定義:

V操作原語(yǔ)的定義:voidV(semaphore*s){s->value++;if(s->value<=0)

wakeup(s->queue);}wakeup(s->queue)：將s->queue所指隊(duì)列首部的PCB取出并將其插入就緒隊(duì)列,其狀態(tài)由等待轉(zhuǎn)為就緒。

說(shuō)明：V操作對(duì)應(yīng)釋放資源

V操作原語(yǔ)的定義:使用信號(hào)燈變量的規(guī)定：(1)必須置一次初值,只能置一次初值,且初值必需為非負(fù)整數(shù)：(2)只能執(zhí)行P操作和V操作,其它操作均非法。關(guān)于信號(hào)燈變量的幾個(gè)有用結(jié)論：(1)當(dāng)s->value<0時(shí),|s->value|為s->queue中等待進(jìn)程的個(gè)數(shù);(2)當(dāng)s->value≥0時(shí),s->queue為空;使用信號(hào)燈變量的規(guī)定：(3)當(dāng)s->value初值為1,可用來(lái)實(shí)現(xiàn)進(jìn)程互斥。這只需在進(jìn)入CS時(shí)執(zhí)行一次P操作,離開(kāi)CS時(shí)執(zhí)行一次V操作。(4)當(dāng)s->value初值為0,可用來(lái)實(shí)現(xiàn)進(jìn)程同步。這只需在后進(jìn)行的動(dòng)作前執(zhí)行一次P操作，在先進(jìn)行的動(dòng)作后執(zhí)行一次V操作。(5)當(dāng)s->value初值為正整數(shù),可用來(lái)管理同種組

合資源。使用資源前執(zhí)行一次P操作(申請(qǐng)),用完后執(zhí)行一次V操作(歸還)。(3)當(dāng)s->value初值為1,可用來(lái)實(shí)現(xiàn)進(jìn)程互斥。組合資源：若干相對(duì)獨(dú)立的資源構(gòu)成的資源集合,其中每個(gè)相對(duì)獨(dú)立的資源稱(chēng)為子資源。同種組合資源:相同類(lèi)型子資源構(gòu)成的組合資源.對(duì)同種組合資源進(jìn)行管理時(shí)semaphoreS=子資源個(gè)數(shù);//初值例如，2臺(tái)打印機(jī)semaphoreS=2;P(S)；//申請(qǐng)使用V(S)；//釋放組合資源：若干相對(duì)獨(dú)立的資源構(gòu)成的資源集用信號(hào)燈變量實(shí)現(xiàn)進(jìn)程互斥……sharedx,y,z:integer;CR1CR2CRnsharedx,y,z:integer;P(mutex)P(mutex)P(mutex)CR1CR2CRnV(mutex)V(mutex)V(mutex)……semaphoremutex=1;用信號(hào)燈變量實(shí)現(xiàn)進(jìn)程互斥……sharedx,y,z:semaphoremutex=1;終端1：終端2：CYCLECYCLE等待借書(shū)者；等待借書(shū)者；

P(mutex)

P(mutex)IFx>=1ThenIFx>=1ThenBeginBeginx:=x-1;x:=x-1;

V(mutex)

V(mutex)

借書(shū)借書(shū)EndEndElseV(mutex);ElseV(mutex);//無(wú)書(shū)EndEnd例圖書(shū)借閱系統(tǒng)

semaphoremutex=1;例圖書(shū)借閱系統(tǒng)用信號(hào)燈變量實(shí)現(xiàn)進(jìn)程同步semaphoreS=0;

P(S)后動(dòng)作先動(dòng)作

V(S)P1P2用信號(hào)燈變量實(shí)現(xiàn)進(jìn)程同步P(S)先動(dòng)作P1P2例司機(jī)-售票員問(wèn)題semaphores1=0,s2=0;司機(jī)活動(dòng)：售票員活動(dòng)：RepeatRepeat

P(S1)關(guān)車(chē)門(mén)啟動(dòng)車(chē)輛V(S1)正常行駛售票到站停車(chē)P(S2)

V(S2)開(kāi)車(chē)門(mén)UntilfalseUntilfalse例司機(jī)-售票員問(wèn)題2.信號(hào)燈與PV操作的應(yīng)用用信號(hào)燈與PV操作解決進(jìn)程同步及互斥問(wèn)題.Classicalsynchronizationproblems

(1)Producersandconsumersproblem(2)Readersandwritersproblem(3)Diningphilosophersproblem(4)Cigarettesmokersproblem(5)Sleepybarbersproblem……

2.信號(hào)燈與PV操作的應(yīng)用例1生產(chǎn)者-消費(fèi)者問(wèn)題假設(shè)某工廠(chǎng)生產(chǎn)線(xiàn)上有一只用來(lái)裝物品的箱子,其中有k個(gè)位置(k≥1),每個(gè)位置可容納一件物品，如圖所示01……k-1箱子(容量k)用數(shù)組表示itemtypeB[n];

生產(chǎn)者消費(fèi)者生產(chǎn)物品放入B中從B中取物品消費(fèi)之例1生產(chǎn)者-消費(fèi)者問(wèn)題假設(shè)某工廠(chǎng)生產(chǎn)線(xiàn)上10K-1in(in+1)%kout(out+1)%kin為放入指針,初值0out為取出指針,初值0為實(shí)現(xiàn)方便,將箱子中的位置(緩沖區(qū))作成環(huán)形。10K-1in(in+1)%kout(out+1)%k生產(chǎn)者-消費(fèi)者問(wèn)題分析需解決的同步問(wèn)題：箱子滿(mǎn)時(shí),P1等待于①,P2執(zhí)行到④將其喚醒；箱子空時(shí),P2等待于③,P1執(zhí)行到②將其喚醒。生產(chǎn)者活動(dòng)P1:do{加工一件物品;物品放入箱中;}while(1);消費(fèi)者活動(dòng)P2:do{箱中取一物品;消耗這件物品;}while(1);─①─④─③─②生產(chǎn)者-消費(fèi)者問(wèn)題分析需解決的同步問(wèn)題：生產(chǎn)者活動(dòng)P1:消費(fèi)從資源角度看：箱子中的位置相當(dāng)于生產(chǎn)者資源,可用一個(gè)信號(hào)燈變量S1表示,其初值為k；物品相當(dāng)于消費(fèi)者資源,可用一個(gè)信號(hào)燈變量S2

表示,其初值為0。生產(chǎn)者資源：箱子B消費(fèi)者資源：物品semaphoreS1=k;semaphoreS2=0;放前：P(S1)取前：P(S2)放后：V(S2)取后：V(S1)從資源角度看：同步問(wèn)題的解決：生產(chǎn)者活動(dòng)：消費(fèi)者活動(dòng)：

RepeatRepeat

加工一件物品

P(S2)P(S1)

箱中取一物品

物品放入箱中

V(S1)V(S2)

消耗這件物品

UntilfalseUntilfalse同步問(wèn)題的解決：需解決的互斥問(wèn)題：需解決對(duì)關(guān)于共享變量B,in,out的臨界區(qū)的互斥:semaphoremutex=1;互斥問(wèn)題的解決：生產(chǎn)者活動(dòng)：消費(fèi)者活動(dòng)：RepeatRepeat

加工一件物品P(S2)

P(S1)

P(mutex)

P(mutex)

箱中取一物品物品放入箱中V(mutex)

V(mutex)

V(S1)

V(S2)

消耗這件物品UntilfalseUntilfalse需解決的互斥問(wèn)題：互斥問(wèn)題的解決：生產(chǎn)者-消費(fèi)者問(wèn)題的自動(dòng)機(jī)描述22…10-1-2P(S)P(S)P(S)P(S)P(S)V(S)

V(S)

V(S)

V(S)

V(S)

S.value=空閑資源數(shù)|S.value|=等待進(jìn)程數(shù)...S.queue=空空閑資源數(shù)=0生產(chǎn)者-消費(fèi)者問(wèn)題的自動(dòng)機(jī)描述22…10-1-2P(S)P(

生產(chǎn)者-消費(fèi)者問(wèn)題的求解程序itemTypeB[k];semaphore

S1=k;//S1表示箱子中的位置semaphoreS2=0;//S2表示物品intin=0;intout=0;semaphoremutex=1;//初值為1,用于實(shí)現(xiàn)進(jìn)程互斥voidproducer(){whlie(1){produceItem(&item);//生產(chǎn)一件產(chǎn)品P(S1);P(mutex);B[in]=item;

in=(in+1)%k;V(mutex);V(S2);}}生產(chǎn)者-消費(fèi)者問(wèn)題的求解程序voidconsumer(){itemTypetemp;while(1){P(S2);P(mutex);

temp=B[out];

out=(out+1)%k;V(mutex);V(S1);//然后消費(fèi)一件產(chǎn)品}}fork(producer,0);…;fork(producer,m-1);fork(consumer,0);…;fork(consumer,n-1);voidconsumer(){并發(fā)性提高策略生產(chǎn)者的共享變量:B[in],in消費(fèi)者的共享變量:B[out],out當(dāng)inout時(shí),生產(chǎn)者和消費(fèi)者不操作B的相同分量;當(dāng)in=out時(shí),緩沖區(qū)或空或滿(mǎn),PV操作已保證空時(shí)

消費(fèi)者不會(huì)取,滿(mǎn)時(shí)生產(chǎn)者不會(huì)放?？梢?jiàn),生產(chǎn)者和消費(fèi)者任何情況下均不操作B的相同分量。為提高程序的并發(fā)性,可將用于互斥的信號(hào)燈變量分為兩個(gè):mutex1和mutex2,分別用于生產(chǎn)者的互斥和消費(fèi)者的互斥:semaphoremutex1=1,mutex2=1;并發(fā)性提高策略生產(chǎn)者活動(dòng)：消費(fèi)者活動(dòng)：RepeatRepeat

加工一件物品P(S2)P(S1)P(mutex2)

P(mutex1)

箱中取一物品物品放入箱中V(mutex2)V(mutex1)V(S1)V(S2)消耗這件物品UntilfalseUntilfalse生產(chǎn)者活動(dòng)：消費(fèi)生產(chǎn)者-消費(fèi)者問(wèn)題在OS及并發(fā)程序設(shè)計(jì)中經(jīng)常遇到。箱子相當(dāng)于緩沖區(qū)生產(chǎn)者和消費(fèi)者相當(dāng)于進(jìn)程進(jìn)程之間通過(guò)一個(gè)長(zhǎng)度有界的緩沖區(qū)通訊生產(chǎn)者-消費(fèi)者問(wèn)題又稱(chēng)作有界緩沖區(qū)問(wèn)題生產(chǎn)者-消費(fèi)者問(wèn)題在OS及并發(fā)程序設(shè)計(jì)中經(jīng)常遇到一組公共數(shù)據(jù)DBRm…W1R1Wn…設(shè)有一組共享數(shù)據(jù)DB和兩組并發(fā)進(jìn)程,一組進(jìn)程只對(duì)此組數(shù)據(jù)執(zhí)行讀操作,另一組進(jìn)程可對(duì)此組數(shù)據(jù)執(zhí)行寫(xiě)操作和讀操作。前一組進(jìn)程稱(chēng)作讀者,后一組進(jìn)程稱(chēng)作寫(xiě)者.要求:(1)R-R可同時(shí)(2)W-W不可同時(shí)(2)R-W不可同時(shí)例2讀者—寫(xiě)者問(wèn)題一組公共數(shù)據(jù)DBRm…W1R1Wn…設(shè)有一組共Solution1:不考慮R-R不互斥semaphorer_w_w=1;Reader()Writer()P(r_w_w);P(r_w_w);{讀操作}{寫(xiě)操作}V(r_w_w);V(r_w_w);分析:寫(xiě)者活動(dòng)正確,但R-R不能并發(fā)。改進(jìn):最先進(jìn)入的R執(zhí)行P,最后離開(kāi)的R執(zhí)行VSolution1:不考慮R-R不互斥Solution2:考慮R-R不互斥intreadCount=0;Reader()readCount:=readCount+1;IfreadCount=1ThenP(r_w_w);{讀操作}readCount:=readCount-1;IfreadCount=0ThenV(r_w_w);分析:對(duì)Read_count操作不互斥.改進(jìn):用信號(hào)燈變量mutex實(shí)現(xiàn)對(duì)readCount的互斥.Solution2:考慮R-R不互斥Solution3:考慮對(duì)readCount的互斥intreadCount=0;semaphoremutex=1;Reader()

P(mutex);readCount:=readCount+1;IfreadCount=1ThenP(r_w_w);V(mutex);{讀操作}P(mutex);readCount:=readCount-1;IfreadCount=0ThenV(r_w_w);V(mutex);Solution3對(duì)應(yīng)的程序如下：Solution3:考慮對(duì)readCount的互斥intreadCount=0;//readCount記錄讀者的數(shù)目semaphorer_w_w=1;semaphoremutex=1;reader(){while(1){<otheractions>P(&mutex);//mutex實(shí)現(xiàn)對(duì)readCount的互斥

readCount=readCount+1;if(readCount==1)P(&r_w_w);

//r_w_w實(shí)現(xiàn)R-W間及W-W間的互斥

V(&mutex);<readoperations>P(&mutex);

readCount=readCount-1;if(readCount==0)V(&r_w_w);V(&mutex);}}intreadCount=0;//readwriter(){while(1){<otheraction>

P(&r_w_w);<writeoperation>

V(&r_w_w);}}fork(reader,0);…;fork(reader,m-1);fork(writer,0);…;fork(writer,n-1);分析:R-R不互斥.若讀者源源不斷,寫(xiě)者可能餓死.事實(shí)上,寫(xiě)者的操作是更新數(shù)據(jù),應(yīng)優(yōu)先進(jìn)行,否則讀者將讀到過(guò)時(shí)的數(shù)據(jù).改進(jìn):寫(xiě)者優(yōu)先,即一旦有寫(xiě)者等待,正在讀的讀者都結(jié)束后,寫(xiě)者進(jìn)入,新到達(dá)的讀者等待.writer(){分析:R-R不互斥.若例3哲學(xué)家就餐問(wèn)題(DiningPhilosophersProblem)ProposedandsolvedbyE.W.Dijkstrain1965.Roomph0ph4ph3ph2ph1f0f4f3f2f1例3哲學(xué)家就餐問(wèn)題(DiningPhilosopher哲學(xué)家活動(dòng)：Repeat思考進(jìn)食Untilfalse進(jìn)食：需要“叉子”叉子：不同種組合資源哲學(xué)家活動(dòng)：哲學(xué)家活動(dòng)(包含資源活動(dòng))Repeat

思考取左叉取右叉

進(jìn)食放左叉放右叉Untilfalse哲學(xué)家活動(dòng)(包含資源活動(dòng))哲學(xué)家問(wèn)題的解法：VARforkArray[0..4]ofSemophore=(1,1,1,1,1)philosopher(i):beginrepeatTHINK;P(fork[i])P(fork[i+1]mod5)EATV(fork[i])V(fork[i+1]mod5)untilfalseend;死鎖情況：每位哲學(xué)家拿到左叉，等待右叉。哲學(xué)家問(wèn)題的解法：死鎖情況：每位哲學(xué)家拿到左叉，等待右叉。解決死鎖的辦法：限制最多4位哲學(xué)家同時(shí)進(jìn)餐，VARforkArray[0..4]ofSemophore=(1,1,1,1,1)VARcount:semophore=4philosopher(i):beginrepeatTHINK;P(count)P(fork[i])P(fork[i+1]mod5)EATV(fork[i+1]mod5)V(fork[i])