計算機操作系統(tǒng)教程.ppt

1、計算機操作系統(tǒng)教程,P、V操作,P、V操作的引入,為禁止兩個進程同時進入臨界區(qū)，使用了鎖操作方法。 但這帶來兩個問題： 1.當臨界資源被占用，不停的測試會造成錯誤。 2.無法實現(xiàn)同步 為此E.W.Dijkstra提出了一種解決同步，互斥問題的更一般的方法，這就是信號量以及有關(guān)的P、V操作,信號量,信號量是表示資源的實體，是一個與隊列有關(guān)的整型變量，其值只能由P、V操作來改變。 操作系統(tǒng)利用信號量對進程和資源進行控制和管理。 根據(jù)用途的不同，分為公用信號量和私用信號量。公用信號量通常用于實現(xiàn)進程之間的互斥，初值為1，他所聯(lián)系的一組并發(fā)進程均可對其實施P,V操作；私用信號量一般用于實現(xiàn)進程間的同步

2、，初值為0或為某個正整數(shù)n，僅允許擁有它的進程對其實施P、V操作。,P、V操作的定義,P、V操作是定義在信號量S上的兩個操作。 P(S): (1）S:=S-1; (2) 若S=0，則調(diào)用P(S)的進程繼續(xù)運行。 (3)若S0,則調(diào)用P(S)的進程被阻塞，并把它插入到等待信號量S的阻塞隊列中,V(S): (1)S:=S+1; (2)若S0,則調(diào)用V(S)的進程繼續(xù)運行； (3)若S=0，從等待信號量S的阻塞隊列中喚醒頭一個進程，然后調(diào)用V(S)的進程繼續(xù)運行,對P、V操作的分析： 當信號量的初值為1時，如果有若干個進程都要求進入臨界區(qū)時，由于每個進程都要調(diào)用P(S)過程，則只有第一個調(diào)用P(S)

3、的進程，執(zhí)行P操作而使S為0，立即進入臨界區(qū)；而其余進程在執(zhí)行完P(guān)操作后，由于S變?yōu)樨撝刀M入阻塞，被插入到等待信號量S的阻塞隊列中。由于信號量的初值為1，P操作起到限制一次只有一個進程進入臨界區(qū)的作用。任何一個進程，在執(zhí)行完臨界區(qū)操作后，在退出臨界區(qū)前必須調(diào)用V操作，從而保證了進程在臨界區(qū)內(nèi)逗留有限時間，當一個進程進退出臨界區(qū)時，如有進程在等待進入臨界區(qū)，V操作將喚醒位于阻塞隊列中的頭一個進程，使其可以進入臨界區(qū)，因而不會出現(xiàn)進程無限等待進入臨界區(qū)的情況這完全符合對臨界區(qū)管理的三條原則。,對P、V操作的分析：（續(xù)） 信號量S0時的數(shù)值表示某類可用資源的數(shù)量，執(zhí)行P操作意味著申請分配一個單位的

4、資源。因此可描述為S:=S-1，當S0時，表示已無資源可用，此時S的絕對值表示信號量S的阻塞隊列中的進程數(shù)；而執(zhí)行一次V操作意味著釋放一個單位的資源，描述為S:=S+1,若此時S=0，表明信號量地阻塞隊列中仍有被阻塞額進程，因此在執(zhí)行V操作時應(yīng)喚醒該隊列的第一個進程,互斥模式,S:=1 進程P1 進程P2 P(S) P(S) S1 S2 V(S) V(S) 分析：由于信號量的初值為1，故第一個進程P1執(zhí)行P操作后信號量減為0,表明臨界資源空閑，可分配給該進程，使之進入臨界區(qū)。若此時又有第二個進程P2欲進入臨界區(qū)，也應(yīng)先執(zhí)行P操作。結(jié)果使S=-1，表示臨界資源已被占用，因此第二進程變?yōu)樽枞麪顟B(tài)，

5、當?shù)谝粋€進程在臨界區(qū)內(nèi)將S1執(zhí)行完后再執(zhí)行V操作，釋放該資源而使信號量恢復(fù)到0，有喚醒了第二個進程P2。待第二個進程P2完成對臨界資源的使用（S2）后，有執(zhí)行V操作，最后信號量恢復(fù)到初值1.,同步模式,進程P1 進程P2 L1：P(S) L2：V(S) 分析：設(shè)進程P1先到達L1點，當它執(zhí)行P(S)時，使S=-1； 于是P1進入阻塞狀態(tài)并進入信號量S的阻塞隊列； 然后進程P2到達L2點，當它執(zhí)行到V(S)時，將S值變?yōu)?，于是喚醒P1,使其轉(zhuǎn)變?yōu)榫途w狀態(tài)，當再次調(diào)度到進程P1時，則P1可在L1點后繼續(xù)運行下去，由此可見，當進程P1到達L1時，除非進程P2已過了L2點，否則進程P1就要暫停執(zhí)行，

6、這就是說，P1在L1點必須與進程P2進行同步。在這種同步操作中，進出那個P1受到進程P2的制約，而進程P2卻不受進程P1的制約，所以是非對稱的。,P、V操作舉例,例1：假定某一時刻，觀察者已記錄了N輛車，又在記錄下一輛車，此時，報告者也開始工作。 觀察者 begin L：observe a lorry； count := count +1； goto L end；,執(zhí)行順序1： （觀察者）count := count + 1; （報告者）report; （報告者）count := 0; 這是正確的結(jié)果。,報告者 begin print count； count := 0； end；,執(zhí)行順序2

7、： （報告者）report count; （觀察者）count := count +1; （報告者）count := 0; 觀察者剛剛記錄的一輛車的信息丟失了 造成不正確的因素是與進程占用處理器的時間、 執(zhí)行的速度以及外界的影響有關(guān)。這些因素都與時間 有關(guān)，所以，稱它們?yōu)椤芭c時間有關(guān)的錯誤”,例2：飛機航班有N個售票處，每個售票處通過終端訪問系統(tǒng)的公共數(shù)據(jù)區(qū)。,售票處1 begin 從數(shù)據(jù)單元中取出現(xiàn) 有余票； 做減1操作； 把結(jié)果送回到數(shù)據(jù)單元 end;,售票處2 begin 從數(shù)據(jù)單元中取出現(xiàn) 有余票； 做減1操作； 把結(jié)果送回到數(shù)據(jù)單元 end;,假定現(xiàn)有余票為1 執(zhí)行順序： （售票處1

8、）從數(shù)據(jù)單元中取出現(xiàn)有余票； （售票處2）從數(shù)據(jù)單元中取出現(xiàn)有余票； （售票處1）做減1操作； （售票處1）把結(jié)果送回到數(shù)據(jù)單元； （售票處2）做減1操作； （售票處2）把結(jié)果送回到數(shù)據(jù)單元； 結(jié)果是把一張票賣給了兩個顧客。 與時間有關(guān)的錯誤產(chǎn)生的原因：多個進程不受限制的對同一數(shù)據(jù)對象進行存取操作。,用P、V操作實現(xiàn)售票系統(tǒng)的互斥 將S定義為信號量，初值為1，余票的數(shù)量值放在整型變量A中。,PROCESS Pi r : integer; begin P(S); r := A; if r = 1 then begin r := r 1; A := r; V(S); 售出一張票; end else

9、 售出票已售完; end；,PROCESS Pi r : integer; begin P(S); r := A; if r = 1 then begin r := r 1; A := r; V(S); 售出一張票; end else begin V(S); 售出票已售完 end end；,例3：有m個生產(chǎn)者和r個消費者共享容量為n的緩沖器（m、r、n均大于1）。每個生產(chǎn)者把自己生產(chǎn)的物品存入緩沖區(qū)，每個消費者從緩沖區(qū)中取出物品去消費。要求用P、V操作對這些生產(chǎn)者和消費者進行正確管理。 定義：整型數(shù)組：B0n-1 整型變量：k，t 初值均為0 信號量：S1：初值1 用于生產(chǎn)者放入物品 S2：初

10、值1 用于消費者取出物品 SP：初值n 緩沖區(qū)是否可用 SG：初值0 緩沖區(qū)里是否有物品,PROCESS Pi begin L1: produce a product; P(SP); P(S1); Bk := product; k := (k + 1) mod n; V(S1); V(SG); goto L1 end,PROCESS Cj begin L2: P(SG); P(S2); take a product from Bt; t := (t + 1) mod n; V(S2); V(SP); consume; goto L1 end,生產(chǎn)者分別向緩沖區(qū)送產(chǎn)品，由S1控制互斥訪問。 消費

11、者分別從緩沖區(qū)中取出產(chǎn)品，由S2控制互斥訪問,例4：讀者寫者問題： 規(guī)定：允許多個進程同時讀；只允許一個進程寫；當有進程讀時不允許其它進程寫。 第一種方案：定義信號量：S: semaphore；初值1；定義一個整數(shù)：rs ，初值0；,讀者： PROCESS Readeri begin rs := rs + 1; if rs = 1 then P(S); read file F; rs := rs 1; if rs = 0 then V(S); end;,寫者： PROCESS Writerj begin P(S); write file F; V(S); end; 問題：對共享變量rs訪問的程

12、序段也是臨界區(qū)。,課后練習,24有一閱覽室，讀者進入時必須先在一張登記表上進行登記。該表為每一作為列出了一個表目，包括座號，姓名。讀者離開時要撤銷登記信息。閱覽室有100個作為，試問： (1)為描述讀者的動作，應(yīng)編寫幾個程序，應(yīng)該設(shè)置幾個進程？進程和程序之間的對應(yīng)關(guān)系如何？ （2)試用P,V操作描述這些進程之間的同步算法。 分析：設(shè)讀者有任意多個，但能同時閱覽的只能100人，所以，設(shè)一個信號量S代表空座位數(shù)目，初值為100，用它來控制進入閱覽室的讀者進程不超過100。另設(shè)信號量m，用于控制對登記表這一共享資源的互斥使用，其初值為1。,(1)需編寫一個程序，100個進程，進程之間通過登記表之間存

13、在同步關(guān)系,（2）Process 第i個讀者進程 begin P(S); P(m); 填寫登記表； V(m); 坐下閱覽; P(m); 在登記表上去掉登記； V(m); V(S); goto L1; end,25設(shè)有兩個優(yōu)先級相同的進程P1，P2如下所示。令信號量S1，S2的初值為0，試問P1，P2并發(fā)運行結(jié)束后，x=? ,y=? ,z=? 進程P1 進程P2 y:=1; x:=1; y:=y+2; x:=x+1; V(S1); P(S1); z:=y+1; x:=x+y; P(S2); V(S2); y:=x+y z:=x+z X=5, y8， Z 9.,28.桌上有一只盤子，每次只能放一個水果。爸爸專向盤子中放蘋果，媽媽專向盤子中方桔子，一個女兒專等吃盤中的蘋果，一個兒子專等吃盤中的桔子，試用P、V操作寫出他們能同步的程序。,semaphore S_Plate=1, S_Apple=0, S_Orange=0;,void father( ) / 父親進程 while(1) P(S_Plate); 往盤子中放入一個蘋果； V(S_Apple); ,void mother( ) / 母親進程 while(1) P(S_Plate); 往盤子中放入一個桔子； V(S_Orange