操作系統(tǒng)第四章 并發(fā)處理

1、第四章 并發(fā)處理4.1并發(fā)活動(dòng)進(jìn)程的引入 假設(shè)某個(gè)作業(yè)job由輸入I，計(jì)算C，打印P三個(gè)操作組成。1. 單道批處理系統(tǒng)中，作業(yè)序列的處理過程如下：C1I1I2P2P1C2tjob1job2為了提高資源利用率和系統(tǒng)吞吐量，引入多道批處理系統(tǒng)。2、多道批處理系統(tǒng)中，作業(yè)序列的處理過程如下：I1C1P1I2C3P2I3C2P3t從圖中可以看出：有的程序段的執(zhí)行是有先后次序的，如C1，I2先于C2；有的程序段可以并發(fā)執(zhí)行，如P1，C2，I3； 可以用偽代碼描述并發(fā)執(zhí)行的程序段，由Dijkstra提出，Cobegin（Concomitant begin） S1;S2; ;Sn;Coend表示S1，S2，

2、Sn可以并發(fā)執(zhí)行。例如：S0;Cobegin S1;S2; ;Sn;CoendSn+1; 表示先執(zhí)行S0，再并發(fā)執(zhí)行S1，S2，Sn；當(dāng)S1，S2，Sn全部執(zhí)行完畢后，再執(zhí)行Sn+1。S0S1S2SnSn+1也可以用先后次序圖（以后也稱進(jìn)程流圖）表示，它是一個(gè)有向無環(huán)圖。4.1.5并發(fā)執(zhí)行程序的特點(diǎn)1.間斷性 如果Ci-1完成后，若Ii未完成，則Ci也無法處理，導(dǎo)致計(jì)算程序段暫停。2.失去程序的封閉性 程序在并發(fā)執(zhí)行時(shí)，是多個(gè)程序共享系統(tǒng)中的各種資源，因而這些資源的狀態(tài)將由多個(gè)程序來改變，致使程序的運(yùn)行失去封閉性。3.不可再現(xiàn)性 當(dāng)初始條件相同時(shí)，程序多次執(zhí)行，其結(jié)果必然重復(fù)出現(xiàn)，稱為可再現(xiàn)性

3、。例如：有一公共變量x，r1，r2為2個(gè)寄存器。假設(shè)CPU分時(shí)執(zhí)行p1,p2。有兩個(gè)程序段：P1:r1=x; r1+; x=r1;P2:r2=x; r2+; x=r2;方式一執(zhí)行：P1:r1=x; r1+; x=r1;P2:r2=x; r2+; x=r2;結(jié)果：x=x+2例如：有一公共變量x，r1，r2為2個(gè)寄存器。假設(shè)CPU分時(shí)執(zhí)行p1,p2。 有兩個(gè)程序段：P1:r1=x; r1+; x=r1;P2:r2=x; r2+; x=r2;方式二執(zhí)行：P1:r1=x;P2:r2=x; r2+; x=r2; P1:r1+; x=r1;結(jié)果：x=x+1 可見，并發(fā)執(zhí)行的程序可能發(fā)生不可再現(xiàn)性。 為了描

4、述并發(fā)執(zhí)行程序的活動(dòng)規(guī)律因而引進(jìn)新的概念進(jìn)程。4.2進(jìn)程的概念 進(jìn)程20世紀(jì)60年代初期提出，可翻譯為process，task，action等。 定義1：進(jìn)程時(shí)一個(gè)具有獨(dú)立功能的程序關(guān)于某個(gè)數(shù)據(jù)集合的一次運(yùn)行活動(dòng)。 定義2：從核心看來，進(jìn)程是分了類的，根據(jù)一組規(guī)則操縱的數(shù)據(jù)結(jié)構(gòu)。進(jìn)程與程序的關(guān)系：1. 進(jìn)程與程序的聯(lián)系 進(jìn)程=程序（程序段、數(shù)據(jù)段、棧段）+進(jìn)程控制塊（PCB） 程序是構(gòu)成進(jìn)程的組成部分之一，一個(gè)進(jìn)程存在的目的就是執(zhí)行其所對(duì)應(yīng)的程序。進(jìn)程和程序的區(qū)別 程序是靜止的，進(jìn)程是動(dòng)態(tài)的（有生命周期的） 進(jìn)程是能獨(dú)立運(yùn)行的單位，能與其它進(jìn)程并發(fā)執(zhí)行。 進(jìn)程是資源分配的基本單位，也是CPU調(diào)

5、度的基本單位。4.2.2進(jìn)程的類型1.系統(tǒng)進(jìn)程 它們運(yùn)行OS的程序，也稱守護(hù)進(jìn)程（Daemon進(jìn)程）。系統(tǒng)啟動(dòng)時(shí)創(chuàng)建，運(yùn)行時(shí)CPU處于核心態(tài)。2.用戶進(jìn)程 這類進(jìn)程運(yùn)行用戶程序，直接為用戶 服務(wù)。進(jìn)程的特征：進(jìn)程的特征： 并發(fā)性：可以與其它進(jìn)程在宏觀上同時(shí)先前推進(jìn)。 動(dòng)態(tài)性：進(jìn)程是執(zhí)行中的程序。 獨(dú)立性：進(jìn)行是資源分配和調(diào)度的基本單位。 交互性：進(jìn)程在運(yùn)行時(shí)可能會(huì)與其它進(jìn)程發(fā)生直接或間接的相互作業(yè)。 異步性：每個(gè)進(jìn)程都可以相對(duì)獨(dú)立，不可預(yù)知的速度向前推進(jìn)。 結(jié)構(gòu)性：每個(gè)進(jìn)程都對(duì)應(yīng)1個(gè)進(jìn)程控制塊。4.2.3進(jìn)程的狀態(tài)進(jìn)程的基本狀態(tài) 就緒狀態(tài)（Ready）：獲得了除CPU以外的所有資源，一旦獲得C

6、PU控制權(quán)，就可以立即運(yùn)行。 運(yùn)行狀態(tài)（Running）：當(dāng)就緒進(jìn)程由OS的進(jìn)程調(diào)度程序調(diào)度，得到CPU控制權(quán)，占用CPU運(yùn)行的狀態(tài)。 等待狀態(tài)（Wait）：若某一進(jìn)程正在等待某一事件的發(fā)生而暫時(shí)停止，這時(shí)，即使獲得CPU控制權(quán)也無法執(zhí)行?；蜃枞麪顟B(tài)（Block）、睡眠狀態(tài)（Sleep）。二、進(jìn)程狀態(tài)變遷圖1、進(jìn)程的三態(tài)模型：運(yùn)行等待就緒 時(shí)間片到 被搶占進(jìn)程調(diào)度 I/O請(qǐng)求 中斷請(qǐng)求服務(wù)等I/O請(qǐng)求完成等進(jìn)程隊(duì)列模型：CPU創(chuàng)建就緒隊(duì)列OS調(diào)度時(shí)間片用完等待事件1等待事件2等待事件n 事件1發(fā)生事件n發(fā)生事件2發(fā)生 因等待的原因不同可以分為若干個(gè)等待隊(duì)列，這樣發(fā)現(xiàn)和喚醒等待的進(jìn)程較為方便。二

7、、進(jìn)程狀態(tài)變遷圖2、進(jìn)程的五態(tài)模型：運(yùn)行等待就緒 時(shí)間片到 被搶占進(jìn)程調(diào)度 I/O請(qǐng)求 中斷請(qǐng)求服務(wù)等I/O請(qǐng)求完成等終止創(chuàng)建結(jié)束接納創(chuàng)建態(tài)(Create)：進(jìn)程剛剛建立（如建立PCB），完成初始化，但未分配內(nèi)存等資源。終止態(tài)(Terminated)：正常結(jié)束或異常結(jié)束。13.在進(jìn)程基本狀態(tài)轉(zhuǎn)換圖中，增加換出（將進(jìn)程換出至輔存）和換入（將進(jìn)程從輔存換入至主存）兩個(gè)操作，試畫出進(jìn)程狀態(tài)轉(zhuǎn)換圖。二、進(jìn)程狀態(tài)變遷圖3、UNIX系統(tǒng)進(jìn)程狀態(tài)變遷圖（p106）4.2.4進(jìn)程的描述進(jìn)程控制塊（Process Contral Block） 進(jìn)程的活動(dòng)除包括CPU執(zhí)行的程序及對(duì)相關(guān)數(shù)據(jù)的操作，還需要用一個(gè)數(shù)據(jù)

8、結(jié)構(gòu)來刻畫進(jìn)程的動(dòng)態(tài)特征，描述進(jìn)程的狀態(tài)、占用資源、調(diào)度信息等，這個(gè)數(shù)據(jù)結(jié)構(gòu)即PCB。 每個(gè)進(jìn)程包括4個(gè)要素：程序段、數(shù)據(jù)段、棧段、進(jìn)程控制塊（PCB）。進(jìn)程的組成：指針指針1指針2指針3其它信息程序段數(shù)據(jù)段堆棧段進(jìn)程控制塊PCB進(jìn)程控制塊PCB的其它信息包括一下主要內(nèi)容： 進(jìn)程標(biāo)識(shí)符（Pid）：由OS創(chuàng)建進(jìn)程時(shí)給出，要求唯一 進(jìn)程的狀態(tài)（Status） :作為進(jìn)程調(diào)度時(shí)分配處理機(jī)的主要依據(jù)。為了便于對(duì)進(jìn)程實(shí)施管理，通常把具有相同狀態(tài)的進(jìn)程鏈接在一起，組成各種隊(duì)列。如就緒隊(duì)列、各種等待隊(duì)進(jìn)程控制塊PCB的其它信息包括一下主要內(nèi)容：當(dāng)前隊(duì)列指針（next）：指向相同狀態(tài)的下一個(gè)PCB 。next

9、nextnextnextnextnextnextRun-startReady-q-startWait-pt-startPCBiPCB2PCB1PCBn進(jìn)程控制塊PCB的其它信息包括一下主要內(nèi)容：總鏈指針（all_q_next）：就系統(tǒng)中所有進(jìn)程的PCB勾鏈起來。nextAll-q-nextnextAll-q-nextnextAll-q-nextnextAll-q-nextNext=All-q-nextnextAll-q-nextNext=All-q-nextRun-startReady-q-startWait-pt-startPCBiPCB2PCB1PCBnAll-start進(jìn)程控制塊PCB的

10、其它信息包括一下主要內(nèi)容：程序開始地址（start_addr）：表示進(jìn)程的程序從此開始執(zhí)行。進(jìn)程優(yōu)先級(jí)（priority）：CPU現(xiàn)場(chǎng)保護(hù)區(qū)（cpu_status）:進(jìn)程控制塊PCB的其它信息包括一下主要內(nèi)容：通信信息（communication information）:如：記錄消息緩沖隊(duì)列指針htprhptrPCB消息緩沖區(qū)1消息緩沖區(qū)2 消息緩沖區(qū)n進(jìn)程控制塊PCB的其它信息包括一下主要內(nèi)容：家族信息（process_family）：如父進(jìn)程的標(biāo)識(shí)符ppid占有資源清單（own_resource）P103 unix系統(tǒng)的進(jìn)程控制塊4.3進(jìn)程控制 進(jìn)程控制是對(duì)系統(tǒng)中的全部進(jìn)程實(shí)施有效的管理

11、。這些管理功能是由一些具有特定功能的程序段原語實(shí)現(xiàn)的。原語是一種特殊的系統(tǒng)調(diào)用命令，它可以完成一個(gè)特定的功能，其特定是執(zhí)行時(shí)不可中斷。 思考：如何實(shí)現(xiàn)原語執(zhí)行時(shí)不可中斷？ 執(zhí)行原語之前關(guān)中斷，執(zhí)行完之后開中斷。進(jìn)程控制原語有：創(chuàng)建原語、撤銷原語、阻塞原語、喚醒原語、延遲原語。執(zhí)行終止就緒等待延遲創(chuàng)建創(chuàng)建原語撤銷原語阻塞原語喚醒原語延遲原語4.3.2進(jìn)程創(chuàng)建進(jìn)程的創(chuàng)建可來源以下事件：1. 用戶向系統(tǒng)提交作業(yè)或程序；2. OS創(chuàng)建服務(wù)進(jìn)程3. 已存在的進(jìn)程創(chuàng)建新的進(jìn)程，如父進(jìn)程創(chuàng)建子進(jìn)程。一般來說進(jìn)程的創(chuàng)建過程如下： 申請(qǐng)一個(gè)空閑的PCB； 初始化PCB，如進(jìn)程號(hào)，優(yōu)先級(jí)，狀態(tài)等 為新的進(jìn)程分配資

12、源，如內(nèi)存等 將新進(jìn)程插入就緒隊(duì)列。4.3.3進(jìn)程的撤銷引起進(jìn)程終止的事件： 正常結(jié)束，如程序執(zhí)行完畢 異常結(jié)束，如溢出 外界干預(yù)，如程序執(zhí)行時(shí)用戶ctrl+break算法： 由運(yùn)行指針得到當(dāng)前進(jìn)程的pid; 釋放本進(jìn)程所占用的資源給父進(jìn)程； 該進(jìn)程從總鏈隊(duì)列中摘除； 釋放此pcb結(jié)構(gòu)； 轉(zhuǎn)OS進(jìn)程調(diào)度；4.3.4進(jìn)程阻塞（block,supend,wait）引起進(jìn)程阻塞的事件 請(qǐng)求OS服務(wù) 請(qǐng)求中斷處理 新的數(shù)據(jù)還未到達(dá) 無新工作可做算法：wait(chan)Chan進(jìn)程等待的原因 p104 int p_wchan 保護(hù)當(dāng)前進(jìn)程的CPU現(xiàn)場(chǎng)到PCB結(jié)構(gòu)中；置該進(jìn)程為“等待”狀態(tài)；將該進(jìn)程的P

13、CB插入到等待chan的等待隊(duì)列；轉(zhuǎn)OS進(jìn)程調(diào)度； 4.3.4進(jìn)程喚醒 當(dāng)進(jìn)程等待的事件發(fā)生后，喚醒等待該事件的所有進(jìn)程。Wakeup（chan）找到該阻塞原因chan的隊(duì)列指針；For（等待該事件的進(jìn)程）將進(jìn)程移出此等待隊(duì)列；置進(jìn)程狀態(tài)為“就緒”；將進(jìn)程插入“就緒隊(duì)列”； 可以看出：當(dāng)前進(jìn)程執(zhí)行Wakeup（chan）原語之后繼續(xù)執(zhí)行。4.3.6進(jìn)程延遲 將需要延遲的進(jìn)程的PCB按其延遲時(shí)間加入到延遲隊(duì)列的適當(dāng)位置。 Delay(seconds) Seconds:需延遲的秒數(shù) Clock_ticks=secondsclock_rate /需延遲的機(jī)內(nèi)時(shí)間 Clock_rate:為時(shí)鐘速率，即

14、時(shí)鐘中斷信號(hào)/秒（如50次/秒）算法：保護(hù)調(diào)用延遲原語的進(jìn)程的CPU現(xiàn)場(chǎng)；計(jì)算clock_ticks;封鎖延遲隊(duì)列；以clock_ticks值檢索延遲隊(duì)列并插入合適位置；置該進(jìn)程為延遲狀態(tài)；解鎖延遲隊(duì)列；轉(zhuǎn)OS進(jìn)程調(diào)度；注意:延遲隊(duì)列是臨界資源，使用之前需上鎖，使用完畢要解鎖。延遲隊(duì)列的結(jié)構(gòu)：PCB中有deltatime項(xiàng)，其值為進(jìn)程所需延遲的clock_ticks與延遲隊(duì)列中的前一個(gè)進(jìn)程的clock_ticks數(shù)之差。例如：有進(jìn)程A,B,C的clock_ticks分別為2，5，10，則延遲隊(duì)列為：Pid=AnextDeltatime=2Pid=BnextDeltatime=3Pid=CNex

15、t=Deltatime=5Delay-q-start假設(shè)進(jìn)程假設(shè)進(jìn)程D的的clock_ticks=8，則應(yīng)該插入延遲隊(duì)列的什么則應(yīng)該插入延遲隊(duì)列的什么位置呢？位置呢？插入延遲隊(duì)列過程如下：Deltatimenew=clock_ticksD;i=1;Time= Deltatimenew deltatimeiIf time0 則 Deltatimenew=time； i+；goto If time0 則插入相比較進(jìn)程的前面，該進(jìn)程的deltatime=deltatimenew; 后一個(gè)進(jìn)程的deltatime= time;思考：畫出插入進(jìn)程D后的延遲隊(duì)列？插入進(jìn)程D后的延遲隊(duì)列:Pid=Anext

16、Deltatime=2Pid=BnextDeltatime=3Pid=CNext=Deltatime=2Delay-q-startPid=DnextDeltatime=3分析這樣處理延遲隊(duì)列有什么好處？二、延遲喚醒進(jìn)程它是一個(gè)系統(tǒng)進(jìn)程，系統(tǒng)初始化時(shí)被創(chuàng)建，由時(shí)鐘中斷激活，直到系統(tǒng)關(guān)閉。當(dāng)時(shí)鐘中斷信號(hào)到來時(shí)執(zhí)行以下算法：封鎖延遲隊(duì)列；取延遲隊(duì)列的首元素；將deltatime- -;If (deltatime=0) 則從延遲隊(duì)列取下該進(jìn)程PCB；解鎖延遲隊(duì)列；該進(jìn)程PCB插入就緒隊(duì)列；中斷返回； 實(shí)驗(yàn)二4.4進(jìn)程的相互制約關(guān)系1.競(jìng)爭(zhēng)關(guān)系原本不存在邏輯關(guān)系的諸進(jìn)程因共享資源而產(chǎn)生的制約關(guān)系，又稱互

17、斥關(guān)系。如學(xué)生在圖書館占座位2.協(xié)作關(guān)系一組并發(fā)進(jìn)程，為了完成任務(wù)需要分工協(xié)作。這種協(xié)作進(jìn)程之間需要排定執(zhí)行的先后次序。也稱同步關(guān)系。如：一個(gè)作業(yè)分為輸入I、計(jì)算C、輸出P三個(gè)過程段。進(jìn)程之間充足哪幾種相互制約關(guān)系？各時(shí)由什么原因引起的？下列活動(dòng)分別屬于哪種制約關(guān)系？（1）若干同學(xué)交納學(xué)費(fèi)（2）兩隊(duì)舉行籃球比賽（3）A考試炒B的答案（4）4個(gè)同學(xué)參加4100米接力解：因競(jìng)爭(zhēng)資源產(chǎn)生的互斥；相互等待、相互制約的同步；（1）互斥（2）互斥（3）同步（4）同步 進(jìn)程互斥（Mutual exclusion）:是指若干進(jìn)程因相互爭(zhēng)奪獨(dú)占型資源而產(chǎn)生的競(jìng)爭(zhēng)制約關(guān)系。 進(jìn)程同步（Synchronizatio

18、n）：并發(fā)進(jìn)程在一些關(guān)鍵點(diǎn)上可能需要互相等待或互通消息，這種制約關(guān)系稱為同步。 如何實(shí)現(xiàn)進(jìn)程間的互斥、同步？4.4.2進(jìn)程互斥臨界資源：一次僅允許1個(gè)進(jìn)程使用的資源。（獨(dú)占型資源）如：打印機(jī)，公共的變量、鏈表、數(shù)據(jù)結(jié)構(gòu)等臨界區(qū)（critical section）:每個(gè)進(jìn)程中訪問臨界資源的那段代碼，又稱臨界段。 對(duì)臨界資源必須互斥使用，否則會(huì)發(fā)生錯(cuò)誤，例如：例如：有一公共變量x，r1，r2為2個(gè)寄存器。假設(shè)CPU分時(shí)執(zhí)行p1,p2。 有兩個(gè)程序段：P1:r1=x; r1+; x=r1;P2:r2=x; r2+; x=r2;方式一執(zhí)行：P1:r1=x; r1+; x=r1;P2:r2=x; r2+

19、; x=r2;結(jié)果：x=x+2公共變量X是臨界資源CS0CS1例如：有一公共變量x，r1，r2為2個(gè)寄存器。假設(shè)CPU分時(shí)執(zhí)行p1,p2。 有兩個(gè)程序段：P1:r1=x; r1+; x=r1;P2:r2=x; r2+; x=r2;方式二執(zhí)行：P1:r1=x;P2:r2=x; r2+; x=r2; P1:r1+; x=r1;結(jié)果：x=x+1公共變量X是臨界資源CS0CS1可見，對(duì)臨界資源的使用必須互斥，否則結(jié)果可能會(huì)產(chǎn)生錯(cuò)誤。互斥應(yīng)遵循的原則：1. 空閑讓進(jìn)：臨界資源處于空閑狀態(tài)時(shí)，應(yīng)允許1個(gè)請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)。2. 忙則等待：當(dāng)已有進(jìn)程進(jìn)入自己的臨界區(qū)時(shí)，其它所有試圖進(jìn)入

20、臨界區(qū)的進(jìn)程必須等待。3. 有限等待：要求訪問臨界資源的進(jìn)程，應(yīng)保證能在有限的時(shí)間內(nèi)進(jìn)入自己的臨界區(qū)。4. 讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放CPU，以免進(jìn)程陷入“忙等待”。 例如：演講時(shí)的話筒。 互斥是同步的特例4.5同步機(jī)構(gòu) 實(shí)現(xiàn)互斥方法之一鎖 對(duì)每個(gè)臨界資源設(shè)置一個(gè)鎖位W（1bit）按慣例，w=0，表示資源可用；w=1，表示資源已被占用 這樣，當(dāng)進(jìn)程使用臨界資源之前必須完成上鎖操作，即w置1；當(dāng)進(jìn)程使用完臨界資源后，須開鎖操作，即w置0，為此，系統(tǒng)提供了lock(w)和unlock(w)2個(gè)原語。算法一Lock(w)test:if (w=1) goto test; Els

21、e W=1;Unlock(w)w=0;改進(jìn)算法二Lock(w)while (w=1) 保護(hù)當(dāng)前進(jìn)程的現(xiàn)場(chǎng)至進(jìn)程的PCB; 將當(dāng)前進(jìn)程的PCB插入w的等待隊(duì)列； 置該進(jìn)程為“等待”狀態(tài)； 轉(zhuǎn)OS的進(jìn)程調(diào)度； W=1;Unlock(w)if (w的等待隊(duì)列不空) 移出等待隊(duì)列的首元素； 將該進(jìn)程插入就緒隊(duì)列； 置該進(jìn)程為“就緒”狀態(tài)； W=0;4.5.2信號(hào)燈（信號(hào)量semaphore）和P、V操作1965年，dijkstra提出的信號(hào)量機(jī)制是一種有效的同步工具。信號(hào)量struct semaphore int s; /s初值0，其值只 能由P、V操 作改變 Queue q; /q是初始狀態(tài)為空 的

22、 排隊(duì)站 P(s)s- -; If (s0)保留當(dāng)前進(jìn)程的現(xiàn)場(chǎng)； 將該進(jìn)程插入s的等待隊(duì)列q中；置該進(jìn)程為“等待”狀態(tài)；轉(zhuǎn)OS的進(jìn)程調(diào)度程序；理解為：申請(qǐng)一個(gè)資源，如果申請(qǐng)不到就進(jìn)入等待狀態(tài)。思考：當(dāng)進(jìn)程執(zhí)行p(s)后，對(duì)當(dāng)前進(jìn)程的狀態(tài)有何影響？s0時(shí)，沒有影響；s0時(shí)，當(dāng)前進(jìn)程由運(yùn)行狀態(tài)變?yōu)榈却隣顟B(tài)。V(s)s+; If (s0) 移出s等待隊(duì)列q的首元素； 將該進(jìn)程插入就緒隊(duì)列； 置該進(jìn)程為“就緒”狀態(tài)； 理解為：釋放一個(gè)資源，如果有進(jìn)程因申請(qǐng)不到該資源而等待的話，就喚醒1個(gè)等待的進(jìn)程。 思考：當(dāng)進(jìn)程執(zhí)行v(s)后，對(duì)當(dāng)前進(jìn)程的狀態(tài)有何影響？ 答：沒有影響。4.6.2使用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥

23、 設(shè)置一個(gè)互斥信號(hào)量mutex，只要把進(jìn)入臨界區(qū)的操作置于p(mutex)和v(mutex)之間，即可實(shí)現(xiàn)進(jìn)程互斥。Main()semaphore mutex=1;CobeginPa();pb();CoendPa( )P(mutex);Csa;V(mutex);Pb( ) P(mutex);Csb;V(mutex);有2個(gè)并發(fā)進(jìn)程，若mutex=1,表示沒有進(jìn)程進(jìn)入臨界區(qū)；Mutex=0,表示有1個(gè)進(jìn)程進(jìn)入臨界區(qū)；Mutex=-1,表示有1個(gè)進(jìn)程進(jìn)入臨界區(qū)，另1個(gè)進(jìn)程等待進(jìn)入。思考：對(duì)于n個(gè)并發(fā)進(jìn)程，分析mutex的取值范圍以及每個(gè)值的物理 意義。對(duì)于n個(gè)并發(fā)進(jìn)程，mutex的值可為1,0，-

24、1，-（n-1），當(dāng)mutex0時(shí)， mutex 的值為等待進(jìn)入臨界區(qū)的進(jìn)程數(shù)。例：以下算法用于解決兩個(gè)臨界區(qū)的問題。兩個(gè)進(jìn)程P0，P1共享如下變量，Boolean:flag0 . .1=false,false;Int turn; /turn的初值為0或1P0( ) Flag0:=true; While turn0 do Begin While flag0; Turn:=0; End; Cs0; Flag1:=falseP1( ) Flag1:=true; While turn1 do Begin While flag0; Turn:=1; End; Cs1; Flag0:=false分析：t

25、urn=0,p0進(jìn)入臨界區(qū)；turn=1,p1進(jìn)入臨界區(qū)。4.6進(jìn)程互斥與同步的實(shí)現(xiàn)4.6.3進(jìn)程同步的實(shí)現(xiàn)進(jìn)程同步:并發(fā)進(jìn)程在一些關(guān)鍵點(diǎn)上可能需要互相等待與互通消息，這種互相等待與互通消息稱為進(jìn)程同步。同步問題可以分為二類：一一組合作進(jìn)程按邏輯需要所確定的次序執(zhí)行。例如看病的流程：掛號(hào)、問診、化驗(yàn)、處方二共享緩沖區(qū)（或共享數(shù)據(jù)）的合作進(jìn)程同步。例如：計(jì)算進(jìn)程把計(jì)算結(jié)果buf打印進(jìn)程取出結(jié)果打印。一合作進(jìn)程的執(zhí)行次序用1個(gè)圖表示進(jìn)程集合的執(zhí)行時(shí)間軌跡，圖的連接描述了進(jìn)程的開始和結(jié)束的次序約束，此圖稱為進(jìn)程流圖或先后次序圖。sssfffP1P2P3順序P1P2P3P1P2P3并行順序/并行SfP

26、aPbPc例1：用P、V操作描述進(jìn)程流圖中這3個(gè)進(jìn)程的同步。方法一：Semaphore Sb=0; /表示Pb是否可以開始 Sc=0; /表示Pc是否可以開始Main()cobegin Pa();Pb();Pc(); coend Pa() V(Sb); V(Sc);Pb() P(Sb); Pc() P(Sc); SfPaPbPc例1：用P、V操作描述進(jìn)程流圖中這3個(gè)進(jìn)程的同步。方法二：Semaphore Sa=0; /表示Pa是否結(jié)束Main()cobegin Pa();Pb();Pc(); coend Pa() V(Sa); V(Sa);Pb() P(Sa); Pc() P(Sa); Sf例

27、2：用P、V操作描述進(jìn)程流圖中進(jìn)程的同步。方法一：Semaphore S7=0; /依次表示Pi是否結(jié)束,i=0.7Main()cobegin P1();P2();P3();P4();P5();P6();P7();P8(); coend P1() V(s1); V(s1); V(s1);P1P2P3P4P5P6P7P8P2() V(s2); V(s2); V(s2);P3()P(s1); P(s2); V(s3);P4()P(s1); P(s2); V(s4);P5()P(s1); P(s2); V(s5);P6()P(s3); V(s6);P7()P(s5); V(s7);P8()P(s4)

28、; P(s6); P(s7);例3：人走路時(shí)的同步問題，假定先左腿，后右腿。問題一：能否設(shè)置1個(gè)信號(hào)量解決？Semaphore s=0; /表示右腿是否可以移動(dòng)Main()cobegin L_leg();R_leg();CoendL_leg()while(1) 左腿向前； 右手前擺； 左手后擺； V(s); R_leg()while(1) p(s); 右腿向前； 左手前擺； 右手后擺； 可能存在左腿不停向前移動(dòng)的情況。例3：人走路時(shí)的同步問題，假定先左腿，后右腿。改進(jìn)方法二Semaphore SL=1; /表示左腿能否向前 SR=0;/表示右腿能否向前Main()cobegin L_leg()

29、;R_leg();CoendL_leg()while(1) p(SL)； 左腿向前； 右手前擺； 左手后擺； V(SR); R_leg()while(1) p(SR); 右腿向前； 左手前擺； 右手后擺； V(SL); 思考：Semaphore SL=0; /表示左腿能否向前 SR=0;/表示右腿能否向前算法如何修改？L_leg()while(1) 左腿向前； 右手前擺； 左手后擺； V(SR); P(SL); R_leg()while(1) p(SR); 右腿向前； 左手前擺； 右手后擺； V(SL); 二、共享緩沖區(qū)的合作進(jìn)程的同步cpiop單緩沖區(qū)進(jìn)程cp負(fù)責(zé)計(jì)算，并把計(jì)算結(jié)果送入緩沖區(qū)

30、；打印進(jìn)程iop負(fù)責(zé)從緩沖區(qū)中取出數(shù)據(jù)，并打??；同步規(guī)則：?jiǎn)尉彌_區(qū)空，iop進(jìn)程等待； 單緩沖區(qū)滿，cp進(jìn)程等待；Semaphore Sa=0;/表示單緩沖區(qū)是否有數(shù)據(jù) Sb=1;/表示單緩沖區(qū)是否空Main()cobegin cp();iop();CoendCp()while(計(jì)算未完成) 計(jì)算； P(sb); 計(jì)算結(jié)果送入單緩沖區(qū)； V(sa); 方法一Iop()while(打印未完成) p(sa); 從單緩沖區(qū)取出數(shù)據(jù)； V(sb); 打印數(shù)據(jù)； 方法二Iop()while(打印未完成) p(sa); 從單緩沖區(qū)取出數(shù)據(jù)； 打印數(shù)據(jù)； V(sb); 方法二，cp()與iop()不能并發(fā)。

31、4.6.4生產(chǎn)者消費(fèi)者問題（ProducerConsumer）123n 有界緩沖區(qū)p1pmC1Ck同步規(guī)則：緩沖區(qū)空，消費(fèi)者進(jìn)程等待； 緩沖區(qū)滿，生產(chǎn)者進(jìn)程等待；設(shè)置2個(gè)同步信號(hào)量 1個(gè)互斥信號(hào)量Semaphore Full=0;/表示緩沖區(qū)中產(chǎn)品的數(shù)目 Empty=n;/表示空緩沖區(qū)的數(shù)目 Mutex=1;/互斥訪問有界緩沖區(qū)產(chǎn)品產(chǎn)品Main（）cobegin P1();pm(); C1();ck();CoendPi()while(1) 生產(chǎn)一個(gè)產(chǎn)品； P(empty); P(mutex); 產(chǎn)品送入緩沖區(qū)； V(mutex); V(full); Cj()while(1) P(full);

32、P(mutex); 從緩沖區(qū)中取出產(chǎn)品； V(mutex); V(full); 消費(fèi)1個(gè)產(chǎn)品； Main（）cobegin P1();pm(); C1();ck();Coend思考：2個(gè)p操作能否互換位置？Pi()while(1) 生產(chǎn)一個(gè)產(chǎn)品； P(mutex); P(empty); 產(chǎn)品送入緩沖區(qū)； V(mutex); V(full); Cj()while(1) P(full); P(mutex); 從緩沖區(qū)中取出產(chǎn)品； V(mutex); V(full); 消費(fèi)1個(gè)產(chǎn)品； 例：某展覽館可以同時(shí)容納1000名參觀者，假設(shè)入口和出口每次只能1人進(jìn)出，試用P、V操作描述參觀者進(jìn)程的同步。Sem

33、aphore N=1000;/表示展覽館可以容納的人數(shù) M1=1;/互斥進(jìn)入入口 M2=1;/互斥進(jìn)入出口Pi()p(n);P(m1);從入口進(jìn)入展覽館；V(m1);參觀；P(m2);從出口離開展覽館；V(m2);V(n);Main（）cobegin P1();pn(); Coend習(xí)題課：1、桌子上有一個(gè)空盤子，允許存放一個(gè)水果。父親可向盤中放蘋果或橘子，兒子專等吃盤中的橘子，女兒專等吃盤中的蘋果。規(guī)定當(dāng)盤子空時(shí)，一次只能放一個(gè)水果，請(qǐng)用P、V操作實(shí)現(xiàn)父親、兒子、女兒三個(gè)并發(fā)進(jìn)程的同步。Semaphore disk=1;/表示盤子是否空 apple=0;/表示盤子中是否有蘋果 orange=

34、0;/表示盤子中是否有橘子Main（）cobegin Father();son();daughter(); CoendFather()while(1) p(disk); 向盤子中放入一個(gè)水果；If (是蘋果) v(apple);If (是橘子) v(orange);Son()while(1) p(orange); 從盤子中取走橘子； V(disk); 吃橘子； daughter()while(1) p(apple); 從盤子中取走蘋果； V(disk); 吃蘋果； 2、有一個(gè)閱覽室共有100個(gè)座位，讀者進(jìn)入時(shí)必須在入口刷卡進(jìn)入，讀者離開時(shí)也必須在出口刷卡，請(qǐng)用P、V操作描述讀者進(jìn)程的同步。Se

35、maphore N=100;/表示閱覽室可以容納的人數(shù) M1=1;/互斥入口刷卡機(jī) M2=1;/互斥出口刷卡機(jī)Main（）cobegin P1();pn(); CoendPi()p(n);P(m1);從入口刷卡進(jìn)入閱覽室；V(m1);閱覽；P(m2);從出口刷卡離開閱覽室；V(m2);V(n);3、哲學(xué)家問題：有甲、乙、丙、丁四個(gè)哲學(xué)家進(jìn)餐，每人進(jìn)餐時(shí)都需要使用刀、叉各一把，吃完后放下刀叉思考問題，請(qǐng)用P、V操作描述這四個(gè)哲學(xué)家的同步。SemaphoreF1=1;/表示第一把刀是否可用F2=1;/表示第二把刀是否可用K1=1;/表示第一把叉是否可用K2=1;/表示第二把叉是否可用注意規(guī)則：按先

36、刀后叉，或先叉后刀的順序。甲（） While（1） p(k1); P(f1); 進(jìn)餐； V(k1); V(f1); 思考； 乙（） While（1） p(k2); P(f1); 進(jìn)餐； V(k2); V(f1); 思考； 丙（） While（1） p(k2); P(f2); 進(jìn)餐； V(k2); V(f2); 思考； ?。ǎ?While（1） p(k1); P(f2); 進(jìn)餐； V(k1); V(f2); 思考； 食物乙甲丙丁刀1叉1叉2刀23、哲學(xué)家問題：有甲、乙、丙、丁四個(gè)哲學(xué)家進(jìn)餐，每人進(jìn)餐時(shí)都需要使用刀、叉各一把，吃完后放下刀叉思考問題，請(qǐng)用P、V操作描述這四個(gè)哲學(xué)家的同步。Semap

37、horeF1=1;/表示第一把刀是否可用F2=1;/表示第二把刀是否可用K1=1;/表示第一把叉是否可用K2=1;/表示第二把叉是否可用注意規(guī)則：按先刀后叉，或先叉后刀的順序。如果不注意會(huì)出現(xiàn)什么問題？甲（） While（1） p(k1); P(f1); 進(jìn)餐； V(k1); V(f1); 思考； 乙（） While（1） p(f1); P(k2); 進(jìn)餐； V(k2); V(f1); 思考； 丙（） While（1） p(k2); P(f2); 進(jìn)餐； V(k2); V(f2); 思考； ?。ǎ?While（1） p(f2); P(k1); 進(jìn)餐； V(k1); V(f2); 思考； 食物乙

38、甲丙丁刀1叉1叉2刀24、中國的哲學(xué)家問題：n個(gè)哲學(xué)家圍在桌子前進(jìn)餐、思考，桌子一次放著n根筷子，用P、V操作描述這n個(gè)哲學(xué)家的活動(dòng)，并保證哲學(xué)家不會(huì)餓死。食物123in in-1ni-1規(guī)則：進(jìn)餐時(shí)左右競(jìng)爭(zhēng)相鄰的筷子。如奇數(shù)號(hào)的哲學(xué)家先拿左手邊的筷子（i-1），后拿右手邊的筷子（i）;如偶數(shù)號(hào)的哲學(xué)家先拿右手邊的筷子（i），后拿右手邊的筷子（i-1）;規(guī)則：進(jìn)餐時(shí)左右競(jìng)爭(zhēng)相鄰的筷子。如奇數(shù)號(hào)的哲學(xué)家先拿左手邊的筷子（i-1），后拿右手邊的筷子（i）;如偶數(shù)號(hào)的哲學(xué)家先拿右手邊的筷子（i），后拿右手邊的筷子（i-1）;Semaphore sn=1;philosopheri ()while(1)

39、 if (I mod 2 = 0)/偶數(shù)號(hào)哲學(xué)家 p(si); p(si-1); 進(jìn)餐； v(si); v(si-1)； 思考； Else/奇數(shù)號(hào)哲學(xué)家 If (i=1) p(sn) else p(si-1); p(si); 進(jìn)餐； v(si); If (i=1) v(sn); else v(si-1); 思考； 4、過獨(dú)木橋問題方法一：Semaphore bridgemutex=1; /互斥獨(dú)木橋West_easti()p(bridgemutex); 從西向東過橋； V(bridgemutex);Eest_westj()p(bridgemutex); 從東向西過橋； V(bridgemute

40、x);問題：對(duì)向互斥，同向也互斥改進(jìn)方法二：Semaphore bridgemutex=1; /互斥獨(dú)木橋 M1=1; /互斥count1 M2=1; /互斥count2Int count1=0;/記錄從西向東的過橋人數(shù) Count2=0;/記錄從東向西的過橋人數(shù)West_easti()p(m1); Count1+; If (count1=1) p(bridgemutex);/第一個(gè)人上橋時(shí)封鎖對(duì)向上橋 V(m1);從西向東過橋；p(m1); Count1- -; If (count1=0) v(bridgemutex);/最后一個(gè)人下橋時(shí)解鎖對(duì)向上橋 V(m1);Eest_westj()p(

41、m2); Count2+; If (count2=1) p(bridgemutex);/第一個(gè)人上橋時(shí)封鎖對(duì)向上橋 V(m2);從東向西過橋；p(m2); Count2- -; If (count2=0) v(bridgemutex);/最后一個(gè)人下橋時(shí)解鎖對(duì)向上橋 V(m2);5、讀者寫者問題：某數(shù)據(jù)庫文件有若干讀、寫進(jìn)程，它們之間讀、寫操作的要求是：讀-寫互斥，寫-寫互斥，讀-讀不互斥，請(qǐng)用信號(hào)量的P、V操作描述這一組進(jìn)程的同步。Semaphore DBmutex=1;/數(shù)據(jù)庫文件互斥信號(hào)量 M=1;/互斥訪問count Int count=0;/記錄讀進(jìn)程數(shù)Main()cobegin R

42、eader1(); ;readern(); Writer1();writern();CoendReaderi()p(m); Count+; If (count=1) p(DBmutex);/第一個(gè)讀者讀數(shù)據(jù)庫時(shí)，阻止寫 V(m);讀數(shù)據(jù)庫文件；p(m); Count- -; If (count=0) v(DBmutex);/最后一個(gè)讀者讀完數(shù)據(jù)庫后，允許寫 V(m);Writerj() p(DBmutex); 寫數(shù)據(jù)庫文件； v(DBmutex);6. 有一個(gè)倉庫，可以存放A和B兩種產(chǎn)品，但要求每次只能存入一種產(chǎn)品（A或B）；-NA產(chǎn)品的數(shù)量B產(chǎn)品的數(shù)量M用信號(hào)量的P、V操作描述產(chǎn)品的入庫過程。分析：ABM，即（AB）maxM1，說明在當(dāng)前庫存量和B不入庫時(shí)，允許A產(chǎn)品入庫的最大數(shù)量，用信號(hào)量Sa表示，初值為M1;-NAB，即BAN，（BA）maxN1，說明在當(dāng)前庫存量和A不入庫時(shí)，允許B產(chǎn)品入庫的最大數(shù)量，用信號(hào)量Sb表示，初值為N1;SemaphoreMutex=1;/互斥信號(hào)量Sa=M1;Sb=N1;Main（）while（1） 取一個(gè)產(chǎn)品； If （是A產(chǎn)品）P(Sa); P(mutex) A產(chǎn)品入庫； V(mutex); V(sb); Else P(Sb); P(mutex) B產(chǎn)品入庫； V(mutex); V(sa); 14.在一個(gè)盒子里存放了