發(fā)送進(jìn)程和接收進(jìn)程的同步問題

1、BUF1BUFnBUF2 .Pb Pa1 1 發(fā)送進(jìn)程和接收進(jìn)程的同步問題發(fā)送進(jìn)程和接收進(jìn)程的同步問題 利用信號(hào)量可以解決合作進(jìn)程之間的同利用信號(hào)量可以解決合作進(jìn)程之間的同步。步。 例：設(shè)進(jìn)程例：設(shè)進(jìn)程Pa,PbPa,Pb通過緩沖區(qū)隊(duì)列傳送數(shù)通過緩沖區(qū)隊(duì)列傳送數(shù)據(jù)據(jù) 經(jīng)典的進(jìn)程同步問題經(jīng)典的進(jìn)程同步問題 發(fā)送和接送過程滿足的條件是發(fā)送和接送過程滿足的條件是： 1)1)在在PaPa至少送一塊數(shù)據(jù)入一個(gè)緩沖區(qū)之至少送一塊數(shù)據(jù)入一個(gè)緩沖區(qū)之前前,Pb,Pb不可能從緩沖區(qū)中取出數(shù)據(jù)不可能從緩沖區(qū)中取出數(shù)據(jù) 2)Pa2)Pa往緩沖隊(duì)列發(fā)送數(shù)據(jù)時(shí)往緩沖隊(duì)列發(fā)送數(shù)據(jù)時(shí), ,至少有一個(gè)至少有一個(gè)緩沖區(qū)是空的緩

2、沖區(qū)是空的; ; 3) 3)由由PaPa發(fā)送的數(shù)據(jù)塊在緩沖隊(duì)列中按先發(fā)送的數(shù)據(jù)塊在緩沖隊(duì)列中按先進(jìn)先出進(jìn)先出(FIFO)(FIFO)方式排列方式排列. . 描述發(fā)送過程描述發(fā)送過程deposit (data)deposit (data)和接受過和接受過程程remove (data) .remove (data) .BUF1BUFnBUF2 .Pb Pa 1)1)BufemptyBufempty進(jìn)程進(jìn)程PaPa的私用信號(hào)量的私用信號(hào)量, , BuffullBuffull 進(jìn)程進(jìn)程PbPb的私用信號(hào)量的私用信號(hào)量; ; 2)Bufempty 2)Bufempty的初始值為的初始值為n(n n(n

3、為緩沖隊(duì)列的緩沖區(qū)為緩沖隊(duì)列的緩沖區(qū)個(gè)數(shù)個(gè)數(shù)),Buffull),Buffull的初始值為的初始值為0;0; 發(fā)送過程發(fā)送過程Deposit(data),Deposit(data),接送過程接送過程Remove(data),Remove(data),這這兩個(gè)過程必須同步，因?yàn)閮蓚€(gè)過程必須同步，因?yàn)? ,因?yàn)檫^程因?yàn)檫^程deposit(data)deposit(data)的的執(zhí)行結(jié)果是過程執(zhí)行結(jié)果是過程remove(data)remove(data)的執(zhí)行條件的執(zhí)行條件, ,而當(dāng)緩沖而當(dāng)緩沖隊(duì)列全部裝滿數(shù)據(jù)時(shí)隊(duì)列全部裝滿數(shù)據(jù)時(shí),remove(data),remove(data)的執(zhí)行結(jié)果又是的執(zhí)

4、行結(jié)果又是deposit(data)deposit(data)的執(zhí)行條件。的執(zhí)行條件。 BUF1BUFnBUF2 .Pb Pa Pa:deposit(data) Pb:remove(data) begin local x begin local x P(Bufempty) P(Buffull) 按按FIFO方式選擇一個(gè)方式選擇一個(gè) 按按FIFO方式選擇一個(gè)方式選擇一個(gè) 空緩沖空緩沖Buf(x); 裝滿數(shù)據(jù)的緩沖裝滿數(shù)據(jù)的緩沖Buf(x) Buf(x)-data data-Buf(x) Buf(x)置滿標(biāo)記置滿標(biāo)記 Buf(x)置空標(biāo)記置空標(biāo)記 V(Buffull) V(Bufempty) en

5、d end發(fā)送過程發(fā)送過程deposit (data)deposit (data)和接受過程和接受過程remove (data)remove (data)123 . nP1P2P3 .Pn.C1C2C3.Cn Dijkstra Dijkstra把同步問題抽象成一種生產(chǎn)者和消把同步問題抽象成一種生產(chǎn)者和消費(fèi)者關(guān)系，計(jì)算機(jī)系統(tǒng)中的許多問題都可以被歸費(fèi)者關(guān)系，計(jì)算機(jī)系統(tǒng)中的許多問題都可以被歸結(jié)為生產(chǎn)者和消費(fèi)者關(guān)系，例如，生產(chǎn)者可以是結(jié)為生產(chǎn)者和消費(fèi)者關(guān)系，例如，生產(chǎn)者可以是計(jì)算進(jìn)程，消費(fèi)者是打印進(jìn)程，輸入時(shí)輸入進(jìn)程計(jì)算進(jìn)程，消費(fèi)者是打印進(jìn)程，輸入時(shí)輸入進(jìn)程是生產(chǎn)者，計(jì)算進(jìn)程是消費(fèi)者。我們可以通過一是

6、生產(chǎn)者，計(jì)算進(jìn)程是消費(fèi)者。我們可以通過一個(gè)緩沖區(qū)把生產(chǎn)者和消費(fèi)者聯(lián)系起來個(gè)緩沖區(qū)把生產(chǎn)者和消費(fèi)者聯(lián)系起來2 2 生產(chǎn)者消費(fèi)者生產(chǎn)者消費(fèi)者的同步問題的同步問題(The Proceducer-(The Proceducer-Consumer Problem)Consumer Problem)舉例：舉例： 生產(chǎn)者把產(chǎn)品生產(chǎn)出來，送入倉(cāng)庫(kù)。給生產(chǎn)者把產(chǎn)品生產(chǎn)出來，送入倉(cāng)庫(kù)。給消費(fèi)者發(fā)信號(hào)，消費(fèi)者得到信號(hào)后，到倉(cāng)庫(kù)消費(fèi)者發(fā)信號(hào)，消費(fèi)者得到信號(hào)后，到倉(cāng)庫(kù)取產(chǎn)品，取走產(chǎn)品后給生產(chǎn)者發(fā)信號(hào)取產(chǎn)品，取走產(chǎn)品后給生產(chǎn)者發(fā)信號(hào)產(chǎn)品倉(cāng) 庫(kù)一個(gè)生產(chǎn)者一個(gè)消費(fèi)者經(jīng)典的進(jìn)程同步問題經(jīng)典的進(jìn)程同步問題n生產(chǎn)者消費(fèi)者問題是相互

7、合作進(jìn)程關(guān)系的一種抽象n輸入計(jì)算打印 生產(chǎn)者 消費(fèi)者 生產(chǎn)者 消費(fèi)者系統(tǒng)中使用資源的進(jìn)程消費(fèi)者系統(tǒng)中釋放資源同類資源的進(jìn)程生產(chǎn)者產(chǎn)品倉(cāng) 庫(kù)一個(gè)生產(chǎn)者一個(gè)消費(fèi)者 1 想接收數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是滿的想接收數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是滿的 2 生產(chǎn)者想發(fā)送數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是空的生產(chǎn)者想發(fā)送數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是空的同步問題同步問題由于緩沖區(qū)是臨界資源，所以生產(chǎn)者和消費(fèi)者之間必須互斥的訪問臨界資源用信號(hào)量解題的關(guān)鍵步驟： 信號(hào)量的設(shè)置； 給信號(hào)量賦初值（常用的互斥和同步信號(hào)量值的大小）； P、V操作安排的位置（其中，P的順序不能顛倒，V的順序任意

8、） 要解決進(jìn)程的同步問題要滿足的條件要解決進(jìn)程的同步問題要滿足的條件設(shè)：公用信號(hào)量 mutex 表示緩沖區(qū)的個(gè)數(shù) 初值為1（消費(fèi)者）私用信號(hào)量 full 表示有界緩沖區(qū)中非空單元數(shù) 初值為0 （生產(chǎn)者）私用信號(hào)量 avail 表示有界緩沖區(qū)中空的單元數(shù) 初值為ndeposit（data）： begin P(avail) 檢查緩沖區(qū)中是否有空單元 執(zhí)行后n-1 P(mutex) 檢查緩沖區(qū)是否可用 執(zhí)行后 mutex0 送數(shù)據(jù)入緩沖區(qū) V(full) 執(zhí)行后，非空單元數(shù)加1 0+11 V(mutex) 釋放緩沖區(qū)中的資源 endRemove（data）： begin P(full) 檢查緩沖區(qū)是

9、否有數(shù)據(jù) P(mutex) 訪問緩沖區(qū) 取緩沖區(qū)中某單元數(shù)據(jù) V(avail) 取走數(shù)據(jù)以后，有界緩沖區(qū)的空單元個(gè)數(shù)加1 V(mutex) 釋放緩沖區(qū) end deposit（data）： begin P(avail) P(mutex) 送數(shù)據(jù)入緩沖區(qū) V(full) V(mutex) endRemove（data）： begin P(full) P(mutex) 取緩沖區(qū)中某單元數(shù)據(jù) V(avail) V(mutex) end 公用信號(hào)量公用信號(hào)量, ,互斥時(shí)使用的信互斥時(shí)使用的信號(hào)量號(hào)量（二元信號(hào)量）：它僅允（二元信號(hào)量）：它僅允許取值為許取值為“”與與“”，用，用作互斥。它聯(lián)系著一組共行

10、進(jìn)作互斥。它聯(lián)系著一組共行進(jìn)程，初值為，每個(gè)進(jìn)程均可程，初值為，每個(gè)進(jìn)程均可對(duì)之施加、操作。對(duì)之施加、操作。 私用信號(hào)量：私用信號(hào)量：一般信號(hào)量一般信號(hào)量（資（資源信號(hào)量）：它聯(lián)系著一組共源信號(hào)量）：它聯(lián)系著一組共行進(jìn)程，但其初值為，或?yàn)樾羞M(jìn)程，但其初值為，或?yàn)槟硞€(gè)正整數(shù)，表示資源的數(shù)某個(gè)正整數(shù)，表示資源的數(shù)目，主要用于進(jìn)程同步。目，主要用于進(jìn)程同步。只允只允許擁有它的許擁有它的進(jìn)程對(duì)之施加操進(jìn)程對(duì)之施加操作，對(duì)作，對(duì)V操作沒有限制操作沒有限制 次序次序 次序次序（消費(fèi)者）私用信號(hào)量 full 表示有界緩沖區(qū)中非空單元數(shù) 初值為0 （生產(chǎn)者）私用信號(hào)量 avail 表示有界緩沖區(qū)中空的單元數(shù)

11、初值為n幾個(gè)經(jīng)典的進(jìn)程同步問題v生產(chǎn)者消費(fèi)者問題v哲學(xué)家進(jìn)餐問題v讀者寫者問題v圖書館閱覽室問題v理發(fā)師問題 v吃水果問題v司機(jī)售票員問題v過河問題生產(chǎn)者消費(fèi)者問題一個(gè)最著名的進(jìn)程同步問題問題描述：一組生產(chǎn)者向一組消費(fèi)者提供消息，它們共享一個(gè)有界緩沖池，生產(chǎn)者存入消息，消費(fèi)者從中取得消息。 哲學(xué)家進(jìn)餐問題n哲學(xué)家進(jìn)餐問題是典型的同步問題，是由Dijkstra提出并解決的。n問題描述5個(gè)哲學(xué)家，他們的生活方式是交替的思考和進(jìn)餐。哲學(xué)家們公用一張圓桌，分別坐在周圍的5張椅子上，圓桌上有5個(gè)碗和5支筷子，平時(shí)一個(gè)哲學(xué)家進(jìn)行思考，饑餓時(shí)便試圖取用其左、右最靠近他的筷子，只有他拿到兩只筷子時(shí)才能進(jìn)餐，放

12、下筷子又繼續(xù)思考。例：例：利用信號(hào)量解決讀者和寫者問題利用信號(hào)量解決讀者和寫者問題 一個(gè)文件可能被多個(gè)進(jìn)程共享，為了一個(gè)文件可能被多個(gè)進(jìn)程共享，為了保證讀寫的正確性和文件的一致性，系統(tǒng)保證讀寫的正確性和文件的一致性，系統(tǒng)要求，當(dāng)有讀者進(jìn)程讀文件時(shí)，不允許任要求，當(dāng)有讀者進(jìn)程讀文件時(shí)，不允許任何寫者進(jìn)程寫，但允許多讀者同時(shí)讀；當(dāng)何寫者進(jìn)程寫，但允許多讀者同時(shí)讀；當(dāng)有寫者進(jìn)程寫時(shí)，不允許任何其它寫者進(jìn)有寫者進(jìn)程寫時(shí)，不允許任何其它寫者進(jìn)程寫，也不允許任何讀者進(jìn)行讀。程寫，也不允許任何讀者進(jìn)行讀。n為了解決讀者和寫者問題，需設(shè)置兩個(gè)信為了解決讀者和寫者問題，需設(shè)置兩個(gè)信號(hào)量：號(hào)量：n（1 1）讀互斥

13、信號(hào)量）讀互斥信號(hào)量rmutex,rmutex,用于使讀者互用于使讀者互斥地訪問共享變量斥地訪問共享變量readcount,readcount,這里這里readcountreadcount是記錄有多少讀者正在讀是記錄有多少讀者正在讀; ; n（2 2）寫互斥信號(hào)量）寫互斥信號(hào)量wmutex,wmutex,用于實(shí)現(xiàn)讀寫用于實(shí)現(xiàn)讀寫互斥。讀者互斥。讀者者問題進(jìn)行如下描述：者問題進(jìn)行如下描述：struct semapore rmutex,wmutexstruct semapore rmutex,wmutex=1,1;=1,1;int readcountint readcount:=0;:=0;cob

14、egincobeginvord readeri(vordvord readeri(vord)(i=1,2,)(i=1,2,k)k) while(true) while(true) p(rmutex p(rmutex) )； ifif readcount=0 then readcount=0 then p(wmutex p(wmutex); ); readcount:=readcount readcount:=readcount+1; +1; v(rmutex); v(rmutex); 讀文件；讀文件； p(rmutex p(rmutex) )； readcount:=readcount-1;r

15、eadcount:=readcount-1;ifif readcount=0 then readcount=0 thenv(wmutex);v(wmutex);v(rmutex);v(rmutex); vord writerj(vordvord writerj(vord)(j=1,2,)(j=1,2,m),m) while(true) while(true) p (wmutex p (wmutex);); 寫文件；寫文件； v(wmutex v(wmutex) )； CoendCoend 課后練習(xí)課后練習(xí) 圖書館閱覽室問題問題描述：假定閱覽室最多可同時(shí)容納100個(gè)人閱讀，讀者進(jìn)入時(shí)，必須在閱覽室門口的一個(gè)登記表上登記，內(nèi)容包括姓名、座號(hào)等，離開時(shí)要撤掉登記內(nèi)容。用P、V操作描述讀者進(jìn)程的同步算法。 理發(fā)師問題問題描述：一個(gè)理發(fā)店由一個(gè)有幾張椅子的等候室和一個(gè)放有一張理發(fā)椅的理發(fā)室組成。若沒有要理發(fā)的顧客，則理發(fā)師就去睡覺；若一顧客走進(jìn)理發(fā)店且所有的椅子都被占用了，則該顧客就離開理發(fā)店；若理發(fā)師正在為人理發(fā)，則該顧客就找一張空椅子坐下等待；若理發(fā)師在睡覺，則顧客就喚醒他，設(shè)計(jì)一個(gè)協(xié)調(diào)理發(fā)師和顧客的程序。 吃水果問題n問題描述：桌上有一只盤子，每次只能放一個(gè)水果，爸爸專向盤中放蘋果，媽媽專向盤中放桔子，兒子專等吃盤里的桔子，女兒專等吃盤里的蘋果。只要盤子空，