1、主要內(nèi)容： 同步與同步機(jī)制 信號(hào)量及其操作 信號(hào)量的應(yīng)用 哲學(xué)家進(jìn)餐問題 生產(chǎn)者-消費(fèi)者問題 讀者-寫者問題 理發(fā)師問題,3.3 信號(hào)量與PV操作,3.1.1 同步與同步機(jī)制,著名的生產(chǎn)者-消費(fèi)者問題是計(jì)算機(jī)操作系統(tǒng)中并發(fā)進(jìn)程內(nèi)在關(guān)系的一種抽象，是典型的進(jìn)程同步問題。 在操作系統(tǒng)中，生產(chǎn)者進(jìn)程可以是計(jì)算進(jìn)程、發(fā)送進(jìn)程；而消費(fèi)者進(jìn)程可以是打印進(jìn)程、接收進(jìn)程等等。解決好生產(chǎn)者-消費(fèi)者問題就解決好了一類并發(fā)進(jìn)程的同步問題。 生產(chǎn)者-消費(fèi)者問題表述：有n個(gè)生產(chǎn)者和m個(gè)消費(fèi)者，連接在k個(gè)單位緩沖區(qū)的有界環(huán)形緩沖池上，故又叫有界緩沖問題。其中pi和cj都是并發(fā)進(jìn)程，只要緩沖區(qū)未滿，生產(chǎn)者進(jìn)程pi所生產(chǎn)的產(chǎn)

2、品就可以放入緩沖區(qū)；只要緩沖區(qū)非空，消費(fèi)者進(jìn)程cj就可以從緩沖區(qū)取走并消耗產(chǎn)品。,.,.,int k; typedef anyitem item; /item類型 nextp, nextc: item; item bufferk; int in=0, out=0, counter=0;,process producer(void) while(TRUE) produce an item in nextp; if(counter=k) sleep(producer); bufferin=nextp; in=(in+1) % k; counter+; if(counter=1) wakeup(co

3、nsumer); ,process consumer(void) while(TRUE) if(counter=0) sleep(consumer); nextc=bufferout; out=(out+1) % k; counter-; if(counter=k-1) wakeup(producer); consume the item in nextc; ,生產(chǎn)者和消費(fèi)者單獨(dú)運(yùn)行都是正確的，但是，如果并發(fā)執(zhí)行（交替執(zhí)行）就會(huì)產(chǎn)生錯(cuò)誤： 結(jié)果不唯一 永遠(yuǎn)等待 出現(xiàn)錯(cuò)誤結(jié)果的原因在于各個(gè)進(jìn)程訪問緩沖區(qū)的速率不同，要得到正確結(jié)果，需要調(diào)整并發(fā)進(jìn)程的速度，這需要通過在進(jìn)程間交換信號(hào)或消息來調(diào)整相互

4、速率，達(dá)到進(jìn)程協(xié)調(diào)運(yùn)行的目的。這種協(xié)調(diào)過程稱為進(jìn)程同步。 操作系統(tǒng)實(shí)現(xiàn)進(jìn)程同步的機(jī)制稱為同步機(jī)制，它通常由同步原語組成。常用的同步機(jī)制有：信號(hào)量與PV操作、管程和消息傳遞。,3.3.2 信號(hào)量與PV操作,1.前節(jié)種種方法解決臨界區(qū)調(diào)度問題的缺點(diǎn) 1)對(duì)不能進(jìn)入臨界區(qū)的進(jìn)程，采用忙式等待測(cè)試法，浪費(fèi)CPU時(shí)間。 2)將測(cè)試能否進(jìn)入臨界區(qū)的責(zé)任推給各個(gè)競(jìng)爭(zhēng)的進(jìn)程會(huì)削弱系統(tǒng)的可靠性，加重了用戶編程負(fù)擔(dān)。 3）這些方案只能解決進(jìn)程競(jìng)爭(zhēng)，不能解決進(jìn)程協(xié)作問題。 2.信號(hào)量同步機(jī)制的提出 1965年荷蘭計(jì)算機(jī)科學(xué)家E.W.Dijkstra提出了新的同步工具-信號(hào)量和P、V操作。他將交通管制中多種顏色的信號(hào)

5、燈管理交通的方法引入操作系統(tǒng)，讓兩個(gè)或多個(gè)進(jìn)程通過特殊變量展開交互。一個(gè)進(jìn)程在某一特殊點(diǎn)上被迫停止執(zhí)行直到接收到一個(gè)對(duì)應(yīng)的特殊變量值，這種特殊變量就是信號(hào)量(Semaphore)。,進(jìn)程可以使用P、V兩個(gè)特殊操作來發(fā)送和接收信號(hào)，如果協(xié)作進(jìn)程的相應(yīng)信號(hào)仍未送到，則進(jìn)程被掛起直到信號(hào)送達(dá)為止。（注意：這里的“掛起”并不是第二章里的被對(duì)換到硬盤上，而是轉(zhuǎn)入等待狀態(tài)！） 操作系統(tǒng)中，信號(hào)量是用來表示物理資源的實(shí)體，用一個(gè)結(jié)構(gòu)性變量表示，有兩個(gè)分量：一個(gè)是信號(hào)量的值，另一個(gè)是指向信號(hào)量的隊(duì)列的指針。 除賦初值外，信號(hào)量?jī)H能由同步原語P和V對(duì)其進(jìn)行操作，沒有任何其他方法可以檢查和操作信號(hào)量。 原語是操作

6、系統(tǒng)內(nèi)核中執(zhí)行時(shí)不可中斷的過程，即原子操作。Dijkstra發(fā)明了兩個(gè)信號(hào)量操作原語：P操作原語和V操作原語（荷蘭語中“測(cè)試（Proberen）”和“增量（Verhogen）”的頭字母）。常用的其他符號(hào)有：wait和signal；up和down；sleep和wakeup等。 利用信號(hào)量和P、V操作既可以解決并發(fā)進(jìn)程的競(jìng)爭(zhēng)問題，又可以解決并發(fā)進(jìn)程的協(xié)作問題。,信號(hào)量的分類 信號(hào)量按其用途分為2種： 公用信號(hào)量：初值常常為1，用來實(shí)現(xiàn)進(jìn)程間的互斥。相關(guān)進(jìn)程均可對(duì)其執(zhí)行P、V操作。 私有信號(hào)量：初值常常為可用資源數(shù)，多用來實(shí)現(xiàn)進(jìn)程同步。擁有該信號(hào)量的一類進(jìn)程可以對(duì)其執(zhí)行P操作，而另一類進(jìn)程可以對(duì)其執(zhí)

7、行V操作，多用于并發(fā)進(jìn)程的同步。 信號(hào)量按照取值可以分為兩種： 二元信號(hào)量： 僅允許取0和1，主要用于解決進(jìn)程互斥； 一般信號(hào)量（計(jì)數(shù)信號(hào)量）：允許取任意整數(shù)值，主要用于解決進(jìn)程同步問題。,一般信號(hào)量 數(shù)據(jù)類型：s是結(jié)構(gòu)性變量，其中成員value為整型變量，系統(tǒng)初始化時(shí)為其賦初值；成員list為等待使用此類資源的進(jìn)程隊(duì)列的頭指針。 P(s): 將s的成員value的值減一； 若結(jié)果小于0，則執(zhí)行P操作的進(jìn)程被阻塞，并且進(jìn)入s的成員list指向的隊(duì)列；否則，執(zhí)行P操作的進(jìn)程繼續(xù)執(zhí)行。 (2) V(s): 將s的成員value的值加一； 如果結(jié)果小于等于0，則執(zhí)行V操作的進(jìn)程從s的成員list指向

8、的隊(duì)列中喚醒一個(gè)進(jìn)程（使其轉(zhuǎn)變?yōu)榫途w態(tài)），隨后自己繼續(xù)執(zhí)行；如果結(jié)果大于0，則執(zhí)行V操作的進(jìn)程繼續(xù)執(zhí)行。,結(jié)構(gòu)型信號(hào)量和PV操作的實(shí)現(xiàn)： typdef struct semaphore int value; struct pcb *list; ; void P(semaphore ,其中 W(s.list)和R(s.list)是操作系統(tǒng)的基本系統(tǒng)調(diào)用， W(s.list)表示把調(diào)用它的進(jìn)程置成等待信號(hào)量s狀態(tài)，并移入s信號(hào)量隊(duì)列，同時(shí)釋放CPU，轉(zhuǎn)向進(jìn)程調(diào)度； R(s.list)表示釋放一個(gè)等待s信號(hào)量的進(jìn)程，轉(zhuǎn)換成就緒態(tài)并且移入就緒隊(duì)列，執(zhí)行該操作的進(jìn)程繼續(xù)執(zhí)行（時(shí)間片未到期）或者轉(zhuǎn)向進(jìn)程調(diào)

9、度（時(shí)間片已到期）。 進(jìn)程從隊(duì)列中移出時(shí)的次序按照FCFS算法，被阻塞的時(shí)間越長(zhǎng)的進(jìn)程越優(yōu)先出隊(duì)，一避免饑餓現(xiàn)象。,結(jié)構(gòu)型信號(hào)量與PV操作的關(guān)系,推論1：若信號(hào)量s.value為正值，則該值等于在封鎖進(jìn)程之前對(duì)信號(hào)量s可施行的P操作數(shù)、亦等于s所代表的實(shí)際還可以使用的物理資源數(shù) 推論2：若信號(hào)量s.value為負(fù)值，則其絕對(duì)值等于登記排列在該信號(hào)量s隊(duì)列之中等待的進(jìn)程個(gè)數(shù)、亦即恰好等于對(duì)信號(hào)量s實(shí)施P操作而被封鎖起來并進(jìn)入信號(hào)量s隊(duì)列的進(jìn)程數(shù) 推論3：通常，P操作意味著請(qǐng)求一個(gè)資源，V操作意味著釋放一個(gè)資源。在一定條件下，P操作代表掛起進(jìn)程操作，而V操作代表喚醒被掛起進(jìn)程的操作,記錄型信號(hào)量與

10、PV操作的注意事項(xiàng),P 操作 信號(hào)量的值減一 如果滿足if條件，執(zhí)行了P操作的進(jìn)程會(huì)掛起，P操作語句之后的語句都不會(huì)再執(zhí)行。 被掛起的進(jìn)程，除非另一個(gè)進(jìn)程調(diào)用V()來喚醒它，否則永遠(yuǎn)不會(huì)執(zhí)行。 V 操作 信號(hào)量的值加一 如果滿足if條件，執(zhí)行V操作的進(jìn)程會(huì)去喚醒另一個(gè)正在等待的進(jìn)程（被掛起的進(jìn)程）。 執(zhí)行V操作的進(jìn)程不會(huì)自愿停止， V操作后面的語句會(huì)接著執(zhí)行 被喚醒的進(jìn)程只是進(jìn)入了就緒隊(duì)列，并不一定有機(jī)會(huì)馬上被執(zhí)行 被喚醒的進(jìn)程，從掛起點(diǎn)接著執(zhí)行，也就是P操作之后的語句,2 二元信號(hào)量,設(shè)s為一個(gè)結(jié)構(gòu)型數(shù)據(jù)結(jié)構(gòu),其中一個(gè)為value,它僅能取值0和1,另一個(gè)分量為信號(hào)量隊(duì)列頭指針list ty

11、pedef struct binary_semaphore int value; struct pcb *list; ; void BP(binary_semaphore 可以證明，二元信號(hào)量與其他結(jié)構(gòu)信號(hào)量具有一樣的表達(dá)能力。,3.3.3 信號(hào)量實(shí)現(xiàn)進(jìn)程互斥,semaphore mutex; mutex= 1; cobegin process Pi() /i=1,2,n . P(mutex); 臨界區(qū)； V(mutex); . coend;,信號(hào)量解決機(jī)票問題,哲學(xué)家吃通心面問題,有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤通心面，每人面前有一只空盤于，每?jī)扇酥g放一把叉子。每個(gè)哲學(xué)家思考、饑餓

12、、然后吃通心面。為了吃面，每個(gè)哲學(xué)家必須獲得兩把叉子，且每人只能直接從自己左邊或右邊去取叉子,哲學(xué)家吃通心面問題示意圖,4,0,0,1,4,3,1,2,3,2,哲學(xué)家,叉子,哲學(xué)家吃通心面問題,semaphore fork5; for(int i;i5;i+) forki := 1; cobegin process Philosopher_i() / i=0,1,2,3,4, while(true) think()； P(forki)； P(forki+1%5)； eat()； V(forki)； V(fork(i+1)%5)； coend,上述算法能夠?qū)崿F(xiàn)進(jìn)程的互斥（同步），但是，它可能發(fā)生

13、死鎖：如果每一個(gè)哲學(xué)家依次拿起右邊（或者左邊）的叉子，結(jié)果就會(huì)出現(xiàn)每一個(gè)人都拿到一把叉子，而都等待第二把叉子的現(xiàn)象。 解決死鎖問題的方案： 至多允許4位哲學(xué)家吃面； 奇數(shù)號(hào)哲學(xué)家先拿左邊的叉子，偶數(shù)號(hào)哲學(xué)家先拿右邊的叉子； 規(guī)定每一個(gè)哲學(xué)家都必須拿到兩把叉子才能吃面，否則一把也不拿即當(dāng)拿不到第二把叉子時(shí)，即放棄已拿到的第一把。注意：實(shí)現(xiàn)該方案需要修改信號(hào)量和PV操作的定義！,生產(chǎn)者消費(fèi)者問題,生產(chǎn)者和消費(fèi)者共享緩沖區(qū) 緩沖區(qū)中有空時(shí)，生產(chǎn)者可放入產(chǎn)品（不許放重），否則等待 緩沖區(qū)中有產(chǎn)品時(shí)，消費(fèi)者可取出產(chǎn)品（不許取重），否則等待 一個(gè)生產(chǎn)者、一個(gè)消費(fèi)者共享一個(gè)緩沖區(qū) 一個(gè)生產(chǎn)者、一個(gè)消費(fèi)者共享

14、多個(gè)緩沖區(qū) 多個(gè)生產(chǎn)者、多個(gè)消費(fèi)者共享多個(gè)緩沖區(qū) 多個(gè)生產(chǎn)者、多個(gè)消費(fèi)者共享一個(gè)緩沖區(qū) 多個(gè)生產(chǎn)者、一個(gè)消費(fèi)者共享多個(gè)緩沖區(qū) 一個(gè)生產(chǎn)者、多個(gè)消費(fèi)者共享多個(gè)緩沖區(qū),一個(gè)生產(chǎn)者一個(gè)消費(fèi)者共享一個(gè)緩沖區(qū),int B; semaphfore empty; /可以使用的空緩沖區(qū)數(shù)目 semaphore full; /緩沖區(qū)內(nèi)可以使用的產(chǎn)品的數(shù)目 empty=1; /初始緩沖區(qū)內(nèi)允許放入一件產(chǎn)品 full=0; /初始緩沖區(qū)內(nèi)沒有產(chǎn)品,cobegin process producer() while(true) produce(); P(empty); append() to B; V(full); c

15、oend,process consumer() while(true) P(full); take() from B; V(empty); ,過程分析,情況一： Producer: P(empty); empty=0; (進(jìn)入臨界區(qū)) Consumer: P(full); full=-1; (掛起) Producer: V(full); full=0; (喚醒consumer) Consumer: 臨界區(qū)語句； (進(jìn)入臨界區(qū)),過程分析,情況二： Consumer: P(full); full=-1; (掛起) Producer: P(empty); empty=0; 臨界區(qū); V(full)

16、; full=0;(喚醒消費(fèi)者) Consumer: 臨界區(qū)語句； V(empty) ; empty= 1; Producer: .,一個(gè)生產(chǎn)者一個(gè)消費(fèi)者共享多個(gè)緩沖區(qū),前面的例子里生產(chǎn)者和消費(fèi)者共享的是一個(gè)緩沖區(qū)，實(shí)際上，他們也可以共享多個(gè)緩沖區(qū)。 為了實(shí)現(xiàn)協(xié)調(diào)，必須增加一個(gè)信號(hào)量。 mutex信號(hào)量（初值1），使進(jìn)程互斥地訪問緩沖區(qū) empty信號(hào)量（初值k），保證生產(chǎn)者不向滿的緩沖區(qū)存 full信號(hào)量（初值0），保證消費(fèi)者不從空的緩沖區(qū)取,m個(gè)消費(fèi)者和n個(gè)生產(chǎn)者共享多個(gè)緩沖區(qū),int Bk; semaphore empty; empty=k; semaphore full; full=0

17、; semaphore mutex; mutex=1; int in=0; int out=0;,cobegin process producer_i() while(true) produce(); P(empty); P(mutex); append() to Bin; in :=(in+1) % k; V(mutex); V(full); coend;,process consumer_j () while(true) P(full); P(mutex); take() from Bout; out=(in+1) % k; V(mutex); V(empty); consume(); ,

18、實(shí)例分析,情況一 (producer在臨界區(qū)中， consumer加入) producer_i: P(empty);(empty=k-1) P(mutex);(mutex=0) 臨界區(qū) consumer_i: P(full); (full=-1;) 掛起 producer_i: V(mutex);(mutex=1) V(full); (full=0;)(喚醒consomer_i) comsumer_i: P(mutex); (mutex=0;) 臨界區(qū)； V(mutex);(mutex=1;) V(empty); (empty=k),實(shí)例分析,情況二： (consumer先啟動(dòng)) consum

19、er_i: P(full); (full=-1;) 掛起 producer_i: P(empty);(empty=k-1;) P(mutex);(mutex=0) 臨界區(qū)； V(mutex);(mutex=1) V(full);(full=0;) comsumer_i: P(mutex); (mutex=0;) 臨界區(qū)； V(mutex);(mutex=1;) V(empty); (empty=k),P操作的次序,如果有多個(gè)P操作，必須注意它們之間的順序 一般來說，用于互斥的信號(hào)量上的P操作應(yīng)該在后面。 V操作的次序無關(guān)緊要。 討論：如果在生產(chǎn)者進(jìn)程中將P(mutex)和P(empty)交換則

20、 若緩沖區(qū)已滿 （empty=0;full=k;mutex=1;）,則 producer: P(mutex);(mutex=0) P(empty);(empty=-1;) 掛起 consumer: P(full);(full=k-1); P(mutex);(mutex=-1); 掛起,讀者寫者問題,有兩組并發(fā)進(jìn)程：讀者和寫者，共享一個(gè)文件F，要求： 允許多個(gè)讀者同時(shí)執(zhí)行讀操作 任一寫者在完成寫操作之前不允許其它讀者或?qū)懻吖ぷ?寫者執(zhí)行寫操作前，應(yīng)讓已有的寫者和讀者全部退出,單純使用信號(hào)量不能解決問題，需要引入計(jì)數(shù)器readcount對(duì)讀進(jìn)程計(jì)數(shù)，mutex代表對(duì)計(jì)數(shù)器操作的互斥信號(hào)量，writ

21、elock表示是否允許寫的信號(hào)量。 int readcount=0; semaphore writeblock, mutex; writeblock=1; mutex=1;,cobegin process reader_i() P(mutex); readcount+; if(readcount=1) P(writeblock); V(mutex); 讀文件； P(mutex); readcount-; if(readcount=0) V(writeblock) ; V(mutex); ,process writer_j() P(writeblock); 寫文件； V(writeblock);

22、 coend,本算法中，讀者是優(yōu)先的，當(dāng)存在讀者時(shí)，寫者將被延遲，而且只要有一個(gè)讀者活躍，隨后的讀者都被允許訪問文件，從而導(dǎo)致寫者長(zhǎng)時(shí)間等待，并可能出現(xiàn)寫者饑餓的現(xiàn)象。 解決的方案：增加信號(hào)量修改程序，可以得到寫者具有優(yōu)先權(quán)的方案，確保當(dāng)一個(gè)寫者進(jìn)程想要訪問文件時(shí)，不允許新的讀者進(jìn)程訪問。 讀者寫者鎖： 允許多名讀者同時(shí)以只讀方式存取有鎖保護(hù)的對(duì)象；或者一位寫者以寫方式存取有鎖保護(hù)的對(duì)象 。 當(dāng)一名或多名讀者已經(jīng)上鎖后，此時(shí)形成讀鎖，寫者將不能訪問有讀鎖保護(hù)的對(duì)象；當(dāng)鎖被請(qǐng)求者用于寫操作時(shí)，形成寫鎖，其他進(jìn)程的讀寫操作必須等待。,寫者優(yōu)先的算法（增加一個(gè)信號(hào)量s，用于在寫進(jìn)程到來之后封鎖后來的

23、讀進(jìn)程）,cobegin process reader_i() P(s); P(mutex); readcount+; if(readcount=1) P(writeblock); V(mutex); V(s); 讀文件； P(mutex);,readcount-; if(readcount=0) V(writeblock) ; V(mutex); process writer_j() P(s); P(writeblock); 寫文件； V(writeblock); V(s); coend,讀者寫者鎖： 允許多名讀者同時(shí)以只讀方式存取有鎖保護(hù)的對(duì)象；或者一位寫者以寫方式存取有鎖保護(hù)的對(duì)象 。

24、當(dāng)一名或多名讀者已經(jīng)上鎖后，此時(shí)形成讀鎖，寫者將不能訪問有讀鎖保護(hù)的對(duì)象；當(dāng)鎖被請(qǐng)求者用于寫操作時(shí)，形成寫鎖，其他進(jìn)程的讀寫操作必須等待。,理發(fā)師問題,理發(fā)店有一位理發(fā)師、一把理發(fā)椅和n把供等候理發(fā)的顧客坐的椅子 如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺 當(dāng)一個(gè)顧客到來時(shí)，它必須叫醒理發(fā)師 如果理發(fā)師正在理發(fā)時(shí)又有顧客來到，則如果有空椅子可坐，他們就坐下來等待，否則就離開,int waiting0； /等候理發(fā)的顧客數(shù) int CHAIRS=n; /為顧客準(zhǔn)備的椅子數(shù) semaphore customers, barbers，mutex; customers = 0; barbers= 0; mutex := 1; cobegin process barber() while(true) P(cutomers);