信號量與PV操作

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

2、品就可以放入緩沖區(qū)；只要緩沖區(qū)非空，消費者進程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ā)執(zhí)行（交替執(zhí)行）就會產(chǎn)生錯誤： 結果不唯一 永遠等待 出現(xiàn)錯誤結果的原因在于各個進程訪問緩沖區(qū)的速率不同，要得到正確結果，需要調(diào)整并發(fā)進程的速度，這需要通過在進程間交換信號或消息來調(diào)整相互

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

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

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

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

8、的隊列中喚醒一個進程（使其轉變?yōu)榫途w態(tài)），隨后自己繼續(xù)執(zhí)行；如果結果大于0，則執(zhí)行V操作的進程繼續(xù)執(zhí)行。,結構型信號量和PV操作的實現(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)用它的進程置成等待信號量s狀態(tài)，并移入s信號量隊列，同時釋放CPU，轉向進程調(diào)度； R(s.list)表示釋放一個等待s信號量的進程，轉換成就緒態(tài)并且移入就緒隊列，執(zhí)行該操作的進程繼續(xù)執(zhí)行（時間片未到期）或者轉向進程調(diào)

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

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

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

12、、然后吃通心面。為了吃面，每個哲學家必須獲得兩把叉子，且每人只能直接從自己左邊或右邊去取叉子,哲學家吃通心面問題示意圖,4,0,0,1,4,3,1,2,3,2,哲學家,叉子,哲學家吃通心面問題,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,上述算法能夠實現(xiàn)進程的互斥（同步），但是，它可能發(fā)生

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

14、多個緩沖區(qū) 多個生產(chǎn)者、多個消費者共享多個緩沖區(qū) 多個生產(chǎn)者、多個消費者共享一個緩沖區(qū) 多個生產(chǎn)者、一個消費者共享多個緩沖區(qū) 一個生產(chǎn)者、多個消費者共享多個緩沖區(qū),一個生產(chǎn)者一個消費者共享一個緩沖區(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; (進入臨界區(qū)) Consumer: P(full); full=-1; (掛起) Producer: V(full); full=0; (喚醒consumer) Consumer: 臨界區(qū)語句； (進入臨界區(qū)),過程分析,情況二： Consumer: P(full); full=-1; (掛起) Producer: P(empty); empty=0; 臨界區(qū); V(full)

16、; full=0;(喚醒消費者) Consumer: 臨界區(qū)語句； V(empty) ; empty= 1; Producer: .,一個生產(chǎn)者一個消費者共享多個緩沖區(qū),前面的例子里生產(chǎn)者和消費者共享的是一個緩沖區(qū)，實際上，他們也可以共享多個緩沖區(qū)。 為了實現(xiàn)協(xié)調(diào)，必須增加一個信號量。 mutex信號量（初值1），使進程互斥地訪問緩沖區(qū) empty信號量（初值k），保證生產(chǎn)者不向滿的緩沖區(qū)存 full信號量（初值0），保證消費者不從空的緩沖區(qū)取,m個消費者和n個生產(chǎn)者共享多個緩沖區(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、實例分析,情況一 (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),實例分析,情況二： (consumer先啟動) 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操作的次序,如果有多個P操作，必須注意它們之間的順序 一般來說，用于互斥的信號量上的P操作應該在后面。 V操作的次序無關緊要。 討論：如果在生產(chǎ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ā)進程：讀者和寫者，共享一個文件F，要求： 允許多個讀者同時執(zhí)行讀操作 任一寫者在完成寫操作之前不允許其它讀者或寫者工作 寫者執(zhí)行寫操作前，應讓已有的寫者和讀者全部退出,單純使用信號量不能解決問題，需要引入計數(shù)器readcount對讀進程計數(shù)，mutex代表對計數(shù)器操作的互斥信號量，writ

21、elock表示是否允許寫的信號量。 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)先的，當存在讀者時，寫者將被延遲，而且只要有一個讀者活躍，隨后的讀者都被允許訪問文件，從而導致寫者長時間等待，并可能出現(xiàn)寫者饑餓的現(xiàn)象。 解決的方案：增加信號量修改程序，可以得到寫者具有優(yōu)先權的方案，確保當一個寫者進程想要訪問文件時，不允許新的讀者進程訪問。 讀者寫者鎖： 允許多名讀者同時以只讀方式存取有鎖保護的對象；或者一位寫者以寫方式存取有鎖保護的對象 。 當一名或多名讀者已經(jīng)上鎖后，此時形成讀鎖，寫者將不能訪問有讀鎖保護的對象；當鎖被請求者用于寫操作時，形成寫鎖，其他進程的讀寫操作必須等待。,寫者優(yōu)先的算法（增加一個信號量s，用于在寫進程到來之后封鎖后來的

23、讀進程）,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,讀者寫者鎖： 允許多名讀者同時以只讀方式存取有鎖保護的對象；或者一位寫者以寫方式存取有鎖保護的對象 。

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