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

1、進(jìn)程間的相互作用 進(jìn)程間的聯(lián)系 進(jìn)程的同步機(jī)制信號量及P.V操作（解決進(jìn)程同步互斥問題） 進(jìn)程間的聯(lián)系相交進(jìn)程與無關(guān)進(jìn)程相交進(jìn)程：指多個(gè)并發(fā)進(jìn)程在邏輯上有某種聯(lián)系無關(guān)進(jìn)程（不相交進(jìn)程）：在邏輯上無任何聯(lián)系的進(jìn)程直接作用和間接作用直接作用：進(jìn)程間的相互聯(lián)系是有意識的安排的，直接作用只發(fā)生在相交進(jìn)程間間接作用：進(jìn)程間要通過某種中介發(fā)生聯(lián)系，是無意識安排的，可發(fā)生在相交進(jìn)程之間，也可發(fā)生在無關(guān)進(jìn)程之間進(jìn)程的同步（直接作用）進(jìn)程的同步：synchronism指系統(tǒng)中多個(gè)進(jìn)程中發(fā)生的事件存在某種時(shí)序關(guān)系，需要相互合作，共同完成一項(xiàng)任務(wù)。具體說，一個(gè)進(jìn)程運(yùn)行到某一點(diǎn)時(shí)要求另一伙伴進(jìn)程為它提供消息，在未獲得

2、消息之前，該進(jìn)程處于等待狀態(tài)，獲得消息后被喚醒進(jìn)入就緒態(tài)。進(jìn)程的互斥（間接作用）mutual exclusion 由于各進(jìn)程要求共享資源，而有些資源需要互斥使用，因此各進(jìn)程間競爭使用這些資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥 臨界資源（臨界資源（Critical resourceCritical resource）：）：系統(tǒng)中某些資源系統(tǒng)中某些資源一次只允許一個(gè)進(jìn)程使用，這樣的資源稱為臨界資源一次只允許一個(gè)進(jìn)程使用，這樣的資源稱為臨界資源或互斥資源或共享變量?；蚧コ赓Y源或共享變量。 臨界區(qū)（臨界區(qū)（Critical regionCritical region）：）：把不允許多個(gè)并發(fā)進(jìn)把不允許多個(gè)并發(fā)

3、進(jìn)程交叉執(zhí)行的一段程序稱為臨界區(qū)或臨界部分。程交叉執(zhí)行的一段程序稱為臨界區(qū)或臨界部分。 臨界區(qū)就是訪問公用數(shù)據(jù)的那段程序。臨界區(qū)就是訪問公用數(shù)據(jù)的那段程序。 例如堆棧操作中的例如堆棧操作中的get(top)get(top)和和rel(blkrel(blk) )程序。程序。程 序 段1程 序 段2程 序 段n共 享 變 量臨界區(qū)（互斥區(qū)）：critical section一個(gè)程序片段的集合，這些程序片段分散在不同的進(jìn)程中，對某個(gè)共享的數(shù)據(jù)結(jié)構(gòu)（共享資源）進(jìn)行操作。 在進(jìn)程中涉及到臨界資源的程序段叫臨界區(qū)。 多個(gè)進(jìn)程的臨界區(qū)稱為相關(guān)臨界區(qū)。 在臨界區(qū)前面增加一段用于進(jìn)行檢查的代碼，稱為進(jìn)入?yún)^(qū)。 在

4、臨界區(qū)后面加上一段代碼，稱為退出區(qū)。 進(jìn)程中除了進(jìn)入?yún)^(qū)、臨界區(qū)及退出區(qū)之外的其它部分的代碼，稱為剩余區(qū)。使用互斥區(qū)的原則：空閑讓進(jìn)：當(dāng)無進(jìn)程在互斥區(qū)時(shí)，任何有權(quán)使用互斥區(qū)的進(jìn)程可進(jìn)入忙則等待：不允許兩個(gè)以上的進(jìn)程同時(shí)進(jìn)入互斥區(qū)有限等待：任何進(jìn)入互斥區(qū)的要求應(yīng)在有限的時(shí)間內(nèi)得到滿足讓權(quán)等待：處于等待狀態(tài)的進(jìn)程應(yīng)放棄占用CPU，以使其他進(jìn)程有機(jī)會得到CPU的使用權(quán)使用互斥區(qū)的原則：前提：任何進(jìn)程無權(quán)停止其它進(jìn)程的運(yùn)行 進(jìn)程之間相對運(yùn)行速度無硬性規(guī)定進(jìn)程互斥的解決有兩種做法:由競爭各方平等協(xié)商引入進(jìn)程管理者，由管理者來協(xié)調(diào)競爭各方對互斥資源的使用具體方法：硬件（當(dāng)一個(gè)進(jìn)程進(jìn)入臨界區(qū),就屏蔽所有中斷，

5、但成本高）軟件（用編程解決，但常常忙等待 ）進(jìn)程互斥的軟件方法 通過平等協(xié)商方式實(shí)現(xiàn)進(jìn)程互斥的最初方法是軟件方法 。其基本思路是在進(jìn)入?yún)^(qū)檢查和設(shè)置一些標(biāo)志，如果已有進(jìn)程在臨界區(qū)，則在進(jìn)入?yún)^(qū)通過循環(huán)檢查進(jìn)行等待；在退出區(qū)修改標(biāo)志。 其中的主要問題是設(shè)置什么標(biāo)志和如何檢查標(biāo)志。設(shè)有兩個(gè)計(jì)算進(jìn)程PA、PB共享內(nèi)存MS。其中MS分為三個(gè)領(lǐng)域，即系統(tǒng)區(qū)、進(jìn)程工作區(qū)和數(shù)據(jù)區(qū)。這里數(shù)據(jù)區(qū)被劃分大小相等的塊，每個(gè)塊中既可能放有數(shù)據(jù)，也有可能未放有數(shù)據(jù)。系統(tǒng)區(qū)主要是堆棧S，其中存放那些空數(shù)據(jù)塊的地址。 如圖所示： getspace（） int g; gstacktop; toptop-1;執(zhí)行g(shù)etspace就

6、是獲取一個(gè)空數(shù)據(jù) release(ad) toptop+1 ； stacktopad ； release(ad)就是釋放一個(gè)地址為ad的數(shù)據(jù)塊 信號量：semaphore 是一個(gè)數(shù)據(jù)結(jié)構(gòu) 定義如下： struct semaphore int value;pointer_PCB queue; 信號量說明： semaphore s;P、V操作P(s) s.value = s.value -; if (s.value 0) 該進(jìn)程狀態(tài)置為等待狀態(tài)； 將該進(jìn)程的PCB插入相應(yīng)的等待隊(duì)列末尾s.queue; V操作V(s) s.value = s.value +; if (s.value = 0) 喚醒

7、相應(yīng)等待隊(duì)列s.queue中等待的一個(gè)進(jìn)程； 改變其狀態(tài)為就緒態(tài) 并將其插入就緒隊(duì)列； P、V操作為原語操作原語：primitive or atomic action 是由若干多機(jī)器指令構(gòu)成的完成某種特定功能的一段程序，具有不可分割性即原語的執(zhí)行必須是連續(xù)的，在執(zhí)行過程中不允許被中斷 實(shí)現(xiàn)：開關(guān)中斷信號量的使用： 必須置一次且只能置一次初值 初值不能為負(fù)數(shù) 只能執(zhí)行P、V操作用用P P、V V操作解決進(jìn)程間互斥問題操作解決進(jìn)程間互斥問題P(mutex)V(mutex)P1P2P3互斥區(qū)互斥區(qū)P(mutex)P(mutex)V(mutex)V(mutex)三個(gè)進(jìn)程共用兩個(gè)I/O緩沖區(qū)。解：設(shè)用信

8、號量S表示共享資源，S初始值為2 互斥例子例：用信號量及例：用信號量及P P、V V原語實(shí)現(xiàn)兩個(gè)并發(fā)進(jìn)程原語實(shí)現(xiàn)兩個(gè)并發(fā)進(jìn)程PaPa和和PbPb互斥?；コ?。兩進(jìn)程都想進(jìn)入臨界區(qū)兩進(jìn)程都想進(jìn)入臨界區(qū)S S。解：解：1 1）設(shè)）設(shè)semsem為互斥信號量，表示臨界區(qū)是否可進(jìn)入為互斥信號量，表示臨界區(qū)是否可進(jìn)入2 2）設(shè)）設(shè)semsem的初始值為的初始值為1 1，表示臨界區(qū)可用，表示臨界區(qū)可用3 3）描述：）描述：PaPa： PbPb: :P(sem) P(semP(sem) P(sem) ) V(sem) V(semV(sem) V(sem) ) 例：大學(xué)校門處要求來客登記，只有一張登記表，例：大

9、學(xué)校門處要求來客登記，只有一張登記表，登記表同時(shí)只能由一個(gè)人使用，用登記表同時(shí)只能由一個(gè)人使用，用P P、V V原語描述一原語描述一個(gè)校外人員進(jìn)入大學(xué)的過程。個(gè)校外人員進(jìn)入大學(xué)的過程。解：解：1 1）設(shè)互斥信號量）設(shè)互斥信號量mutexmutex，表示登記表是否正在使用，表示登記表是否正在使用2 2）設(shè)）設(shè)mutexmutex初始值為初始值為1 1，表示登記表沒有人使用，表示登記表沒有人使用3 3）描述：）描述：Enter:Enter: P(mutex P(mutex) /) /申請登記表申請登記表 登記登記 V(mutexV(mutex) /) /釋放登記表釋放登記表 有A、B兩進(jìn)程，A進(jìn)程

10、從卡片機(jī)讀信息入緩沖區(qū)，B進(jìn)程負(fù)責(zé)加工讀進(jìn)緩沖區(qū)的卡片 解：設(shè)信號量S1：緩沖區(qū)中有否可供加工的信息，初始值為0；信號量S2：緩沖區(qū)是否為空，初始值為1。同步例子 下列活動屬于哪種制約關(guān)系 (1) 若干同學(xué)去圖書館借書 (2) 兩隊(duì)進(jìn)行籃球比賽 (3) 流水線生產(chǎn)的各道工序 (4) 商品生產(chǎn)和社會消費(fèi)習(xí)題 某倉庫有兩名發(fā)貨員，一名審核員。當(dāng)顧客提貨時(shí)，只要發(fā)貨員空閑，允許顧客進(jìn)入倉庫提貨，顧客離開時(shí)，審核員檢驗(yàn)顧客提貨是否正確。其工作流程如下圖所示。為了利用PV操作正確地協(xié)調(diào)他們之間的工作，設(shè)置了兩個(gè)信號量S1和S2，初值分別位2，1。圖中的a，b，c，d應(yīng)分別填（）。顧客進(jìn)程 （i =1，2

11、，n）a在倉庫提貨bc檢驗(yàn)d應(yīng)用實(shí)例 例1 P1進(jìn)程和P2進(jìn)程共享一臺打印機(jī)，用信號量和P、V操作實(shí)現(xiàn)它們的互斥。 例2 矩陣A+B=矩陣和，用信號量和P、V原語操作實(shí)現(xiàn)它們的同步。A用甲進(jìn)程表示，B用乙進(jìn)程表示。 例3 矩陣A+B= C，用信號量和P、V原語操作實(shí)現(xiàn)它們的同步。A用甲進(jìn)程表示，B用乙進(jìn)程表示，C用丙進(jìn)程表示。 例4 設(shè)公共汽車上，司機(jī)和售票員的活動分別是 司機(jī)活動：啟動車輛；正常運(yùn)行；到站停車 售票員活動：關(guān)門；售票；開門 用信號量和P、V操作實(shí)現(xiàn)它們的關(guān)系經(jīng)典的生產(chǎn)者消費(fèi)者問題消費(fèi)者消費(fèi)者生產(chǎn)者生產(chǎn)者經(jīng)典的生產(chǎn)者消費(fèi)者問題同步問題： P進(jìn)程不能往“滿”的緩沖區(qū)中放產(chǎn)品，設(shè)置

12、信號量為S1 Q進(jìn)程不能從“空”的緩沖區(qū)中取產(chǎn)品，設(shè)置信號量S2S1初值為1，S2初值為0P： Q：while (true) while (true) 生產(chǎn)一個(gè)產(chǎn)品; P(s2); P(s1) ; 從緩沖區(qū)取產(chǎn)品; 送產(chǎn)品到緩沖區(qū); V(s1); V(s2); 消費(fèi)產(chǎn)品; ;.PQ放 消 息取 消 息nn個(gè) 緩 沖 區(qū)(Buffer)ij多個(gè)緩沖區(qū)的生產(chǎn)者和消費(fèi)者P：i = 0;while (true) 生產(chǎn)產(chǎn)品; P(S1); 往Buffer i放產(chǎn)品; V(S2); i = (i+1) % n; ;Q： j = 0; while (true) P(S2); 從Bufferj取產(chǎn)品; V(S

13、1); 消費(fèi)產(chǎn)品; j = (j+1) % n; ;共享緩沖區(qū)共享緩沖區(qū)n n生產(chǎn)指針生產(chǎn)指針消費(fèi)指針消費(fèi)指針Producer 1Producer 2.Producer MConsumer 1Consumer 2.Consumer K滿滿空空指針移動方向指針移動方向 P1 有界緩沖區(qū) Q1 P2 Q2 P3 Q3 : : Pm-1 Qk-1 Pm QkQ： j = 0; while (true) P(S2); P(mutex); 從Bufferj取產(chǎn)品; V(mutex); V(S1); 消費(fèi)產(chǎn)品; j = (j+1) % n; ;n個(gè)緩沖區(qū)、m個(gè)生產(chǎn)者和k個(gè)消費(fèi)者P：i = 0;while

14、(true) 生產(chǎn)產(chǎn)品; P(S1); P(mutex); 往Buffer i放產(chǎn)品; V(mutex); V(S2); i = (i+1) % n; ;有錯誤？若顛倒兩個(gè)有錯誤？若顛倒兩個(gè)P操作的順操作的順 序？序？ P：i = 0;while (true) 生產(chǎn)產(chǎn)品; P(mutex); P(S1); 往Buffer i放產(chǎn)品; V(mutex); V(S2); i = (i+1) % n; ;Q： j = 0; while (true) P(mutex); P(S2); 從Bufferj取產(chǎn)品; V(mutex); V(S1); 消費(fèi)產(chǎn)品; j = (j+1) % n; ;錯誤錯誤Q：

15、j = 0; while (true) P(S2); P(mutex); 從Bufferj取產(chǎn)品; j = (j+1) % n; V(mutex); V(S1); 消費(fèi)產(chǎn)品;n個(gè)緩沖區(qū)、m個(gè)生產(chǎn)者和k個(gè)消費(fèi)者P：i = 0;while (true) 生產(chǎn)產(chǎn)品; P(S1); P(mutex); 往Buffer i放產(chǎn)品; i = (i+1) % n; V(mutex); V(S2); ;正正 確確P.V操作討論1) 信號量的物理含義：S0表示有S個(gè)資源可用S=0表示無資源可用S=1 & S2 = 1 & & Sn = 1)/滿足資源要求時(shí)的處理；滿足資源要求時(shí)的處理；

16、for (i = 1; i = n; +i) -Si; /注：與注：與P的處理不同，這里是在確信可滿足的處理不同，這里是在確信可滿足 / / 資源要求時(shí)，才進(jìn)行減資源要求時(shí)，才進(jìn)行減1操作；操作；break;else /某些資源不夠時(shí)的處理；某些資源不夠時(shí)的處理； 調(diào)用進(jìn)程進(jìn)入第一個(gè)小于1信號量的等待隊(duì)列Si.queue; 阻塞調(diào)用進(jìn)程; Ssignal(S1, S2, , Sn)/V操作for (i = 1; i = ti；即當(dāng)資源數(shù)量低于ti時(shí)，便不予分配）占用值為di（表示資源的申請量，即Si = Si - di）對應(yīng)的P、V原語格式為：Swait(S1, t1, d1; .; Sn,

17、tn, dn);Ssignal(S1, d1; .; Sn, dn);一般“信號量集”可以用于各種情況的資源分配和釋放，幾種特殊情況： Swait(S, d, d)表示每次申請d個(gè)資源，當(dāng)少于d個(gè)時(shí)，便不分配 Swait(S, 1, 1)表示互斥信號量 Swait(S, 1, 0)可作為一個(gè)可控開關(guān) （當(dāng)S1時(shí)，允許多個(gè)進(jìn)程進(jìn)入臨界區(qū)； 當(dāng)S=0時(shí)，禁止任何進(jìn)程進(jìn)入臨界區(qū)）3 IPC經(jīng)典問題1.讀者寫者問題 有兩組并發(fā)進(jìn)程: 讀者和寫者,共享一組數(shù)據(jù)區(qū) 要求： 允許多個(gè)讀者同時(shí)執(zhí)行讀操作 不允許讀者、寫者同時(shí)操作 不允許多個(gè)寫者同時(shí)操作第一類：讀者優(yōu)先如果讀者來：1）無讀者、寫者，新讀者可以讀

18、2）有寫者等，但有其它讀者正在讀，則新讀者也可以讀3）有寫者寫，新讀者等如果寫者來：1）無讀者，新寫者可以寫2）有讀者，新寫者等待3）有其它寫者，新寫者等待第一類讀者寫者問題的解法讀者： while (true) P(mutex); readcount +; if (readcount=1) P (w); V(mutex); 讀; P(mutex); readcount -; if (readcount=0) V(w); V(mutex); ;寫者： while (true) P(w); 寫; V(w); ;第一類讀者寫者問題的解法（一般信號量集）寫者：Swait(wmutex,1,1; rc

19、ount,R,0);寫；Ssignal(wmutex,1);讀者：Swait(rcount,1,1; wmutex,1,0);讀；Ssignal(rcount,1);2.哲學(xué)家就餐問題有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每兩人之間放一只筷子 每個(gè)哲學(xué)家的行為是思考，感到饑餓，然后吃通心粉為了吃通心粉，每個(gè)哲學(xué)家必須拿到兩只筷子，并且每個(gè)人只能直接從自己的左邊或右邊去取筷子用用P P、V V原語實(shí)現(xiàn)原語實(shí)現(xiàn) 哲學(xué)家問題哲學(xué)家問題 例：例：5 5個(gè)哲學(xué)家在圓桌前進(jìn)餐，兩個(gè)人之間各放一個(gè)哲學(xué)家在圓桌前進(jìn)餐，兩個(gè)人之間各放一根筷子。哲學(xué)家或者思考或者分別取左右手邊的筷

20、根筷子。哲學(xué)家或者思考或者分別取左右手邊的筷子進(jìn)餐。請用子進(jìn)餐。請用P P、V V原語描述每個(gè)哲學(xué)家的進(jìn)餐過程。原語描述每個(gè)哲學(xué)家的進(jìn)餐過程。0123414032用用P P、V V原語實(shí)現(xiàn)原語實(shí)現(xiàn) 哲學(xué)家問題哲學(xué)家問題( (完整完整) )解：解：1 1）設(shè)公用信號）設(shè)公用信號量量mutexmutex表表示哲學(xué)家是否能同時(shí)取到示哲學(xué)家是否能同時(shí)取到2 2個(gè)個(gè)筷子，筷子，sisi表示是否能取到表示是否能取到第第I I個(gè)筷子（個(gè)筷子（i=0,1,2,3,4 i=0,1,2,3,4 ） 2 2）設(shè)初始值）設(shè)初始值mutexmutex=1=1，si=1 si=1 （i=0,1,2,3,4 i=0,1,2

21、,3,4 ） 3 3）描述第）描述第i i個(gè)哲學(xué)家個(gè)哲學(xué)家PiPi：Pi:while(true) think; P(mutex); P(si); P(s(i+1) mod 5); V(mutex); eat; V(si); V (s(i+1) mod 5); 解決思路如下：讓奇數(shù)號的哲學(xué)家先取右手邊的筷子，讓偶數(shù)號解決思路如下：讓奇數(shù)號的哲學(xué)家先取右手邊的筷子，讓偶數(shù)號的哲學(xué)家先取左手邊的筷子。的哲學(xué)家先取左手邊的筷子。 這樣任何一個(gè)哲學(xué)家拿到一只筷子以后，就已經(jīng)阻止了鄰座這樣任何一個(gè)哲學(xué)家拿到一只筷子以后，就已經(jīng)阻止了鄰座的一個(gè)哲學(xué)家吃飯的企圖，除非某個(gè)哲學(xué)家一直吃下去，否則不的一個(gè)哲學(xué)家吃飯的企圖，除非某個(gè)哲學(xué)家一直吃下去，否則不會有人餓死。會有人餓死。描述第描述第i i個(gè)哲學(xué)家個(gè)哲學(xué)家PiPi：Pi:While(true) if (i mod 2=0) P(si); P(s(i+1)mod 5); Eat; V(si); V(s(i+1)mod 5);else P(s(i+1)m