【2】章2進程控制與同步-3課件

上次問題描述OS進行進程創(chuàng)建、終止、阻塞、掛起等的過程；什么是同步；使并發(fā)執(zhí)行的諸進程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性控制同步的關(guān)鍵在哪里。不被打斷的進行標(biāo)志值的判斷和修改同步原則空閑讓進，忙則等待，有限等待，讓權(quán)等待7/19/20231山東農(nóng)業(yè)大學(xué)計算機系第2章進程管理2.1進程基本概念2.2進程控制

2.3進程同步（信號量） 2.4經(jīng)典進程同步問題2.5進程通信2.6線程7/19/20232山東農(nóng)業(yè)大學(xué)計算機系2.信號量機制荷蘭科學(xué)家Dijkstra(狄克斯特拉)提出的一種卓有成效的進程同步機制。Edsger

Wybe

Dijkstra

(1930.5~2002.8)7/19/20233山東農(nóng)業(yè)大學(xué)計算機系1）

整型信號量信號量定義為一個整型量；根據(jù)初始情況賦相應(yīng)的值；僅能通過兩個原子操作來訪問。P操作wait(S): WhileS<=0dono-op;S:=S-1;V操作signal(S): S:=S+1;對比軟件解決法7/19/20234山東農(nóng)業(yè)大學(xué)計算機系例：對臨界資源的互斥使用程序1:wait(s)使用Rsignal(s)程序2:wait(s)使用Rsignal(s)S=1給共享變量R設(shè)置一個信號量swait(){WhileS<=0dono-op;S:=S-1;}signal(){s=s+1}S=0S=1S=0S=17/19/20235山東農(nóng)業(yè)大學(xué)計算機系2）記錄型信號量整型信號量符合“有限等待”原則signal釋放資源后，當(dāng)CPU被分配給等待進程后，等待進程仍可繼續(xù)執(zhí)行，可以符合“有限等待”。但整型信號量不符合“讓權(quán)等待”原則整型信號量的wait操作，當(dāng)s≤0時，當(dāng)前進程會占著CPU不斷測試；信號量原語不能被打斷，這個占有CPU的進程會一直不斷的占據(jù)CPU循環(huán)下去，陷入忙等。7/19/20236山東農(nóng)業(yè)大學(xué)計算機系改進：條件不符時應(yīng)能夠主動放棄CPU新問題：放棄CPU的進程進入阻塞隊列：因等待某信號量而放棄CPU的等待進程會有“若干”個，需將它們組織管理起來，并在合適的時候喚醒。7/19/20237山東農(nóng)業(yè)大學(xué)計算機系*信號量結(jié)構(gòu)信息發(fā)生變化不僅要有值的處理，還有隊列的處理。此時形成記錄型數(shù)據(jù)結(jié)構(gòu)，包括兩部分：整型變量value(代表資源數(shù)目)進程鏈表L(鏈接所有等待進程)：代碼描述：typeSemaphore=record value：integer; L：listofPCB;end;

操作：S.Value，S.L7/19/20238山東農(nóng)業(yè)大學(xué)計算機系指針●數(shù)值（-3）●PCB1●PCB20PCB3記錄型信號量Value>0，表示當(dāng)前可用資源的數(shù)量；Value≤0，其絕對值表示等待使用該資源的進程數(shù)，即在該信號量隊列上排隊的PCB的個數(shù)。7/19/20239山東農(nóng)業(yè)大學(xué)計算機系*P、V操作也有所變化不僅修改資源數(shù)，還要處理進程的阻塞、喚醒等操作。先修改資源數(shù)，再判斷處理。P操作wait():

S.value=S.value-1;ifS.value<0thenblock(S,L)V操作signal()：

S.value=S.value+1;ifS.value<=0thenwakeup(S,L)7/19/202310山東農(nóng)業(yè)大學(xué)計算機系定義信號量semaphore代表可用資源實體的數(shù)量。又叫信號燈。當(dāng)≥0，代表可供并發(fā)進程使用的資源實體數(shù)當(dāng)<0，表示正在等待使用該資源的進程數(shù)。建立一個信號量必須經(jīng)過說明，包括信號量所代表的意義賦初值建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，以便指向等待使用臨界區(qū)的進程。除初值外，信號量的值僅能由標(biāo)準(zhǔn)原子操作P、V操作來改變。

PV操作是荷蘭語通過和釋放的意思。7/19/202311山東農(nóng)業(yè)大學(xué)計算機系3）信號量的基本應(yīng)用實現(xiàn)進程互斥實現(xiàn)進程間的前趨關(guān)系（有序）7/19/202312山東農(nóng)業(yè)大學(xué)計算機系實現(xiàn)多個進程互斥設(shè)置一互斥信號量mutex，初值為1。進程i：V(mutex);criticalsection操作共享資源RremaindersectionP(mutex);

S.value=S.value-1;ifS.value<0thenblock(S,L)

S.value=S.value+1;ifS.value<=0thenwakeup(S,L)7/19/202313山東農(nóng)業(yè)大學(xué)計算機系互斥信號量注意點：互斥信號量mutex初值為1；每個進程中將臨界區(qū)代碼置于P(mutex)和V(mutex)原語之間必須成對使用P和V原語（在同一進程中），不能次序錯誤、重復(fù)或遺漏：遺漏P原語則不能保證互斥訪問遺漏V原語則不能在使用臨界資源之后將其釋放（給其他等待的進程）；7/19/202314山東農(nóng)業(yè)大學(xué)計算機系實現(xiàn)有序前趨關(guān)系:

并發(fā)執(zhí)行的進程P1和P2中，分別有代碼C1和C2，要求C1要在C2開始前完成；為每對前趨關(guān)系設(shè)置一個同步信號量S12，并賦初值為0。則只有V操作所在進程獲得cpu時能運行P1：C1；signal(S)；P2：wait(S)；C2；7/19/202315山東農(nóng)業(yè)大學(xué)計算機系控制同步順序的注意點信號量值為0的點是限制的關(guān)鍵所在；成對使用P和V原語（在有先后關(guān)系的兩個進程中），不能次序錯誤、重復(fù)或遺漏，否則同步順序出錯。7/19/202316山東農(nóng)業(yè)大學(xué)計算機系一個簡單同步舉例例：設(shè)有一供者和一用者，如何用信號量來控制二者對緩沖區(qū)的同步使用。注意思考： 信號量是針對資源設(shè)置的，分析本問題各對象關(guān)心的資源，想想需要設(shè)置幾個信號量，初值又如何？緩沖區(qū)供者用者7/19/202317山東農(nóng)業(yè)大學(xué)計算機系V(s2);將數(shù)據(jù)送入緩沖區(qū)；…P(s1);V(s1);從緩沖區(qū)取數(shù)來用；P(s2);供者：用者：………注意：需要兩個信號量s1表示空緩沖的個數(shù)，初值為1；s2表示滿緩沖的個數(shù)，初值為0；初值決定了執(zhí)行的初始狀態(tài)，值得思考7/19/202318山東農(nóng)業(yè)大學(xué)計算機系練習(xí)：1）如何利用互斥信號量解決上次課兩個加法進程對共享變量操作的問題？A：R1=x；R1=R1+1；x=R1B：R2=x；R2=R2+1；x=R2Var

mutex:semaphore:=1;x:integer;processA:beginrepeat

P(mutex); R1=x; R1=R1+1; x=R1;

V(mutex);untilfalse;7/19/202319山東農(nóng)業(yè)大學(xué)計算機系2）民航售票系統(tǒng)問題n個售票處。每個售票處通過終端訪問系統(tǒng)的公用數(shù)據(jù)區(qū)假定公用數(shù)據(jù)區(qū)中分別用Ri表示某時間i次航班的現(xiàn)存票數(shù)。Pi表示某售票處的處理進程，試用信號量實現(xiàn)進程間的互斥關(guān)系。7/19/202320山東農(nóng)業(yè)大學(xué)計算機系Vars:semaphore:=1;begin

parbeginprocessPi:begin end

parendendrepeatP(s);按旅客定票要求找到RiIFRi

>=1then

Ri

=Ri

-1;

輸出一張票；EndifV(s);輸出“票已售完”；untilfalse;7/19/202321山東農(nóng)業(yè)大學(xué)計算機系3）用信號量實現(xiàn)司機和售票員的同步。司機：RepeatP(s1);

離站；行車；到站；

V(s2);Untilfalse;售票員：Repeat

關(guān)車門；

V(s1);

售票；

P(s2);

開車門；乘客上下車；Untilfalse;初值如何？同步信號量成對出現(xiàn)在不同進程中7/19/202322山東農(nóng)業(yè)大學(xué)計算機系4）AND型信號量出現(xiàn)原因：一些應(yīng)用往往需要兩個或多個共享資源，而不是前述的一個資源。進程同時要求的共享資源越多，發(fā)生死鎖可能性越大。解決思想： 一次性分配給進程所需資源，用完一起釋放。Wait操作時對它所有需要的資源都要判斷，有AND條件，故稱“AND同步”、“同時wait”。ProcessA：

wait(Dmutex);

wait(Emutex);ProcessB：

wait(Emutex);

wait(Dmutex);7/19/202323山東農(nóng)業(yè)大學(xué)計算機系Swait(S1,S2,…,Sn)if（S1>=1and…andSn>=1）thenfori:=1tondoSi:=Si-1;

endforelse

將進程阻塞在第一個不能滿足資源信號量的隊列中。

endifSsignal(S1,S2,…,Sn)fori:=1tondoSi:=Si+1;

喚醒所以與si相關(guān)的阻塞進程

endfor

7/19/202324山東農(nóng)業(yè)大學(xué)計算機系5）信號量集引入原因：每次只能獲得或釋放一個單位的資源，低效；某些時候資源分配有下限的限制；修改：在大于可分配設(shè)置的下界值t前提下，每次可分配d個。7/19/202325山東農(nóng)業(yè)大學(xué)計算機系Swait(S1,t1,d1,…,Sn,tn,dn)ifS1>=t1and…andSn>=tnthenfori:=1tondoSi:=Si-di;

endforelse…

endifSsignal(S1,d1,…,Sn,dn)fori:=1tondoSi:=Si+di;….

endforAND信號量機制上加以擴充，每種資源參數(shù)有三：

S為信號量（現(xiàn)有值）；

t為下限值（現(xiàn)有不能少于該條件）；d為需求值；7/19/202326山東農(nóng)業(yè)大學(xué)計算機系信號量集的一個特例只有一個信號量S的幾種特殊情況：

Swait(S,d,d)，，允許每次申請d個資源，若現(xiàn)有資源數(shù)少于d，不予分配。

Swait(S,1,1)，蛻化為一般的記錄型信號量，一次申請一個，至多分配一個(S>1時可計數(shù)，或S=1時可控制互斥)。

Swait(S,1,0)，當(dāng)S>=1時，允許多個進程進入某特定區(qū)，當(dāng)S變?yōu)?后，阻止任何進程進入特定區(qū)，相當(dāng)于可控開關(guān)。并不對S資源的數(shù)量產(chǎn)生影響。7/19/202327山東農(nóng)業(yè)大學(xué)計算機系*體驗Swait(S,1,0)的開關(guān)作用(選看)給車庫位數(shù)定義資源信號量S=5通行證p=0車庫入口進程P_in：Repeat

Swait(S,1,0)

發(fā)通行證 signal（p）Untilfalse車輛進程P_car：repeat wait（p）

wait(S)

停車

…shopping

取車

signal（S）Untilfalse需求為0，可見不改變車庫資源數(shù)，主要進行判斷7/19/202328山東農(nóng)業(yè)大學(xué)計算機系*信號量題目做題一般方法：分析問題，找出同步、互斥關(guān)系根據(jù)資源設(shè)置信號量變量寫出代碼過程，并注意P、V操作的位置檢查代碼，模擬機器運行，體驗信號量的變化和程序運行過程是否正確。7/19/202329山東農(nóng)業(yè)大學(xué)計算機系名詞解釋同步、臨界資源、臨界區(qū)、讓權(quán)等待默寫記錄型信號量的wait，signal原語。它與整型信號量的區(qū)別是什么？AND信號量機制可解決什么問題？用基本記錄型信號量解決如下同步關(guān)系，并回答問題：四人有什么同步關(guān)系，應(yīng)設(shè)置幾個信號量，初值為多少？程序雖然無序請求，但在信號量控制下，是在合理的同步運行，請給出所有錯誤的無序請求下信號量起控制作用的過程分析。作業(yè)一空盤放一水果父放梨，母放橘兒取梨，