進程間制約關(guān)系

1、操作系統(tǒng)第操作系統(tǒng)第8 8課課進程間的制約關(guān)系進程間的制約關(guān)系今日內(nèi)容今日內(nèi)容u進程的互斥進程的互斥u進程的同步進程的同步u信號量和信號量和P P、V V操作操作內(nèi)容回顧內(nèi)容回顧: :進程間的制約關(guān)系進程間的制約關(guān)系u進程的并發(fā)，使一個進程何時占有處理進程的并發(fā)，使一個進程何時占有處理機、占有多長時間、執(zhí)行速度的快慢、機、占有多長時間、執(zhí)行速度的快慢、以及外界對進程產(chǎn)生作用等都帶有隨機以及外界對進程產(chǎn)生作用等都帶有隨機性。因此，一個進程對其他進程的影響性。因此，一個進程對其他進程的影響無法預測。進程間存在制約關(guān)系。無法預測。進程間存在制約關(guān)系。&間接制約間接制約&直接制約直接制約共享變量修改引

2、起的沖突共享變量修改引起的沖突一個飛機售票系統(tǒng)，兩個終端，運行兩個進程：一個飛機售票系統(tǒng)，兩個終端，運行兩個進程：例：對輸入井文件目錄的管理例：對輸入井文件目錄的管理u為輸出井設(shè)置一張為輸出井設(shè)置一張 “ “輸出井文件輸出井文件目錄表目錄表”，它由若干目錄項組成，它由若干目錄項組成。每個目錄項記錄一個要打印輸。每個目錄項記錄一個要打印輸出的文件名以及該文件在磁盤的出的文件名以及該文件在磁盤的存放地址。存放地址。u兩個指針：兩個指針：outout和和inin。u兩個程序：兩個程序：&“井管理寫程序井管理寫程序”根據(jù)根據(jù)inin的指點存放的指點存放要求輸出的文件目錄信息，要求輸出的文件目錄信息，i

3、nin總是指總是指向下一個可用的目錄項位置。向下一個可用的目錄項位置。&“緩輸出程序緩輸出程序”根據(jù)根據(jù)outout的指點進行的指點進行打印，打印，outout總是指向下一個被打印的總是指向下一個被打印的文件。文件。test . cgroup . probit . txt45674out7in輸出井文件目錄表輸出井文件目錄表例：通過雙緩沖區(qū)復制文件例：通過雙緩沖區(qū)復制文件u編寫一個復制n個記錄的程序，它把文件F中的每個記錄依次讀到輸入緩沖區(qū)R，再從R拷貝到輸出緩沖區(qū)T，最后寫到文件G中。假定R和T正好存放一個記錄。u寫3個子程序作為進程來完成整個工作：GET：從文件F按照順序讀出一個記錄，然后

4、送入輸入緩沖區(qū)R；COPY：把輸入緩沖區(qū)R里的記錄拷貝到輸出緩沖區(qū)T里；PUT：從輸出緩沖區(qū)T里讀出一個記錄，然后依照順序?qū)懭胛募礼。記錄記錄1記錄記錄2記錄記錄nGETCOPYPUT文件文件F記錄記錄1記錄記錄2記錄記錄n文件文件G輸入緩沖區(qū)輸入緩沖區(qū)R輸出緩沖區(qū)輸出緩沖區(qū)T例：通過雙緩沖區(qū)復制文件例：通過雙緩沖區(qū)復制文件u在復制過程中，若COPY已把R里的記錄拷貝到了T中，那么GET和PUT就可以并發(fā)執(zhí)行了。即GET從F里讀出下一個記錄送到R中的操作，與PUT從T中取出里面的內(nèi)容寫入G的操作，誰先做誰后做都沒有關(guān)系，不會影響到復制結(jié)果的正確性。由于利用了它們并發(fā)性，工作效率就會提高。u但是

5、，如果不去顧及這三者之間執(zhí)行順序的這種關(guān)系，隨意讓GET、COPY、PUT去并發(fā)執(zhí)行，那么就會產(chǎn)生錯誤。 記錄記錄1記錄記錄2記錄記錄nGETCOPYPUT文件文件F記錄記錄1記錄記錄2記錄記錄n文件文件G輸入緩沖區(qū)輸入緩沖區(qū)R輸出緩沖區(qū)輸出緩沖區(qū)T若不管若不管GET、COPY、PUT的執(zhí)行關(guān)系，那么可有六種執(zhí)行可能：的執(zhí)行關(guān)系，那么可有六種執(zhí)行可能： 1）COPYPUTGET；2）COPYGETPUT；3）PUTCOPYGET 4）PUTGETCOPY；5）GETCOPYPUT；6）GETPUTCOPY.記錄3記錄4記錄n文件F記錄2記錄1文件GRT記錄1GETPUT記錄1記錄1文件GRT記

6、錄3記錄4記錄n文件F記錄1記錄4記錄n文件F記錄3記錄1文件GRT記錄1COPY記錄1記錄4記錄n文件F記錄3記錄3文件GRT記錄1123(2)(3)(1)(4)進程的互斥進程的互斥u共享變量共享變量&在操作系統(tǒng)中，把那些可以被進程共享的資源（如文在操作系統(tǒng)中，把那些可以被進程共享的資源（如文件、隊列、緩沖區(qū)、表格、變量等）統(tǒng)稱為件、隊列、緩沖區(qū)、表格、變量等）統(tǒng)稱為“共享變共享變量量”或或“臨界資源臨界資源”。u互斥互斥&與一個共享變量（或臨界資源）交往的多個進程，為與一個共享變量（或臨界資源）交往的多個進程，為了保證它們各自運行結(jié)果的正確性，當其中的一個進了保證它們各自運行結(jié)果的正確性，

7、當其中的一個進程正在對該變量（或臨界資源）進行操作時，就不允程正在對該變量（或臨界資源）進行操作時，就不允許其他進程同時對它進行操作。進程間的這種制約關(guān)許其他進程同時對它進行操作。進程間的這種制約關(guān)系被稱為系被稱為“互斥互斥”。 u臨界區(qū)臨界區(qū)&把進程程序中把進程程序中“真正需要保證互斥執(zhí)行真正需要保證互斥執(zhí)行”的程序，稱的程序，稱為該進程的為該進程的“臨界區(qū)（或臨界段）臨界區(qū)（或臨界段）”。 一個飛機售票系統(tǒng)，兩個終端，運行兩個進程：一個飛機售票系統(tǒng)，兩個終端，運行兩個進程：臨界區(qū)臨界區(qū)a := a -1 print (a)a := a +1 print (a)P1互斥互斥P2互斥互斥If

8、a 0then a := a +1else a:= a-1P3互斥互斥 進程的互斥進程的互斥（間接作用）（間接作用）程 序 段1程 序 段2程 序 段n共 享 變 量使用臨界區(qū)的原則：使用臨界區(qū)的原則：（一組并發(fā)進程互斥執(zhí)行時應(yīng)滿足的準則，保證使用共享數(shù)據(jù)的進程能夠正確和高效地運行）有空讓進有空讓進：當無進程在臨界區(qū)時，任何有權(quán)使用：當無進程在臨界區(qū)時，任何有權(quán)使用臨界區(qū)的進程之一可進入臨界區(qū)的進程之一可進入無空等待無空等待：已有進程在臨界區(qū)，其它欲進入臨界：已有進程在臨界區(qū)，其它欲進入臨界區(qū)的進程需等待區(qū)的進程需等待有限等待有限等待：任何進入臨界區(qū)的要求應(yīng)在有限的時：任何進入臨界區(qū)的要求應(yīng)在

9、有限的時間內(nèi)得到滿足間內(nèi)得到滿足讓權(quán)等待讓權(quán)等待：處于等待狀態(tài)的進程應(yīng)放棄占用：處于等待狀態(tài)的進程應(yīng)放棄占用CPUCPU，以使其他進程有機會得到，以使其他進程有機會得到CPUCPU的使用權(quán)的使用權(quán)協(xié)同工作協(xié)同工作進程同步進程同步從文件從文件F取出一個記取出一個記錄送至輸入緩沖區(qū)錄送至輸入緩沖區(qū)R向向COPY發(fā)送發(fā)送“可可以拷貝以拷貝” 的消息的消息等待等待COPY發(fā)來的發(fā)來的“拷貝結(jié)束拷貝結(jié)束”的消息的消息等待等待GET發(fā)來發(fā)來“可可以拷貝以拷貝” 的消息的消息將輸入緩沖區(qū)將輸入緩沖區(qū)R里的記錄里的記錄拷貝到輸出緩沖區(qū)拷貝到輸出緩沖區(qū)T里里向向GET發(fā)送發(fā)送“拷拷貝結(jié)束貝結(jié)束”的消的消息息GE

10、TCOPY1.1.2.2.3.3.例：例：GET和和COPY間的協(xié)調(diào)一致間的協(xié)調(diào)一致GET讀記錄到R后，給COPY發(fā)送消息，告訴它R中已有記錄，然后暫停下來，等待COPY發(fā)來 “拷貝結(jié)束”的消息，只有接到這個消息，GET才能去做下一步工作。相對地，COPY也一直處于等待。只有接到GET發(fā)送來 “可以拷貝”的消息才能工作，將R里的記錄拷貝到T里，然后向GET發(fā)“拷貝結(jié)束”的消息，隨之又等待GET發(fā)消息。 同步、同步點、同步條件同步、同步點、同步條件u一組并發(fā)進程因直接制約而互相發(fā)送消息，進一組并發(fā)進程因直接制約而互相發(fā)送消息，進行互相合作，互相等待，使得各進程按一定的行互相合作，互相等待，使得各

11、進程按一定的速度執(zhí)行的過程稱為速度執(zhí)行的過程稱為進程間的同步進程間的同步。u進程暫停等待以取得同步的那一點，稱為進程暫停等待以取得同步的那一點，稱為“同同步點步點”。u一個進程需要等待另一個進程完成的操作或發(fā)一個進程需要等待另一個進程完成的操作或發(fā)送的信息，稱為送的信息，稱為“同步條件同步條件”。實現(xiàn)進程互斥和同步的方法實現(xiàn)進程互斥和同步的方法1 1、進程互斥的軟件方法、進程互斥的軟件方法 通過平等協(xié)商方式實現(xiàn)進程互斥的通過平等協(xié)商方式實現(xiàn)進程互斥的最初方法是軟件方法最初方法是軟件方法 其基本思路是在進入?yún)^(qū)檢查和設(shè)置其基本思路是在進入?yún)^(qū)檢查和設(shè)置一些標志，如果已有進程在臨界區(qū)，一些標志，如果已

12、有進程在臨界區(qū)，則在進入?yún)^(qū)通過循環(huán)檢查進行等待；則在進入?yún)^(qū)通過循環(huán)檢查進行等待；在退出區(qū)修改標志在退出區(qū)修改標志 其中的主要問題是設(shè)置什么標志和其中的主要問題是設(shè)置什么標志和如何檢查標志如何檢查標志軟件解法之一軟件解法之一 free: free: 表示臨界區(qū)標志表示臨界區(qū)標志 true: true: 有進程在臨界區(qū)有進程在臨界區(qū) false:false:無進程在臨界區(qū)無進程在臨界區(qū)( (初值初值) ) . . while (free); while (free); free = true; free = true; 臨界區(qū)臨界區(qū) free = false;free = false;2 2、硬件

13、方法：硬件方法：TSLTSL（“測試并上鎖測試并上鎖”）指令）指令 借助一條硬件指令來實現(xiàn)互斥的同步機構(gòu)。借助一條硬件指令來實現(xiàn)互斥的同步機構(gòu)。 TSL TSL指令：指令： 包括讀數(shù)和寫包括讀數(shù)和寫數(shù)兩個操作。數(shù)兩個操作。 enter_region; enter_region; 臨界區(qū)臨界區(qū) leave_region;leave_region;3 3、信號量及、信號量及P.VP.V操作操作19651965年，由荷蘭學者年，由荷蘭學者DijkstraDijkstra提出（所提出（所以以P P、V V分別是荷蘭語的分別是荷蘭語的test(proberen)test(proberen)和和incre

14、ment(verhogen)increment(verhogen)），是一種卓），是一種卓有成效的進程同步機制。有成效的進程同步機制。1 1、信號量、信號量semphoresemphore（semsem） 操作系統(tǒng)中，信號量操作系統(tǒng)中，信號量semsem是一整是一整數(shù)，大于等于數(shù)，大于等于0 0時代表可供并發(fā)進時代表可供并發(fā)進程使用的資源實體；小于程使用的資源實體；小于0 0時則表時則表示正在等待使用臨界區(qū)的進程數(shù)。示正在等待使用臨界區(qū)的進程數(shù)。信號量的使用：信號量的使用： 通過初始化和兩個標準原語來訪問。通過初始化和兩個標準原語來訪問。 1 1、必須置一次且只能置一次初值；、必須置一次且只能

15、置一次初值； 初值不能為負數(shù)初值不能為負數(shù) 2 2、只能執(zhí)行、只能執(zhí)行P P、V V操作操作2 2、P P、V V原語操作原語操作P(sem)P(sem) sem.value - -;sem.value - -; / /表示申請一個資源表示申請一個資源 if (sem.value 0)if (sem.value 0) / /表示無可用資源表示無可用資源 將該進程狀態(tài)置為等待狀態(tài)并將該進程插入將該進程狀態(tài)置為等待狀態(tài)并將該進程插入與該信號相對應(yīng)的等待隊列中與該信號相對應(yīng)的等待隊列中; ; elseelse / /表示還有可用資源表示還有可用資源 進程繼續(xù)運行進程繼續(xù)運行 V(sem) V(sem

16、) sem.value + +sem.value + +; /; /表示釋放一個資源表示釋放一個資源 if (sem.value = 0) if (sem.value 0 then /sell the ticket count=count-1; 設(shè)置信號量設(shè)置信號量 S， s.value=1（初始值為初始值為 1）P：P(S) if count0 then /sell the ticket count=count-1 V(S)P P( (S S):): S.value-;S.value-;if (S.value 0) if (S.value 0 then /sell the ticket co

17、unt=count-1 V(S)s.value=0P0：P(S) if count0 then /sell the ticket count=count-1 V(S)P0：P(S) if count0 then /sell the ticket count=count-1 V(S)P1：P(S) if count0 then /sell the ticket count=count-1 V(S)s.value=0P P( (S S):): S.value-;S.value-;if (S.value 0) if (S.value 0 then /sell the ticket count=cou

18、nt-1 V(S)P P( (S S):): S.value-;S.value-;if (S.value 0) if (S.value 0 then /sell the ticket count=count-1 V(S)P P( (S S):): S.value-;S.value-;if (S.value 0)if (S.value 0 then /sell the ticket count=count-1 V(S)S.value=-1S.list-P1 P1：P(S) if count0 then /sell the ticket count=count-1 V(S)P P( (S S):)

19、: S.value-;S.value-;if (S.value 0) if (S.value P1 P1：P(S) if count0 then /sell the ticket count=count-1 V(S)P P( (S S):): S.value-;S.value-;if (S.value 0) if (S.value 0 then /sell the ticket count=count-1 V(S)P1：P(S) if count0 then /sell the ticket count=count-1 V(S)S.value=-1S.list-P1 喚醒相應(yīng)等待隊列中等待喚醒

20、相應(yīng)等待隊列中等待 的一個進程；的一個進程； 改變其狀態(tài)為就緒態(tài)，改變其狀態(tài)為就緒態(tài)， 并將其插入就緒隊列中；并將其插入就緒隊列中；P0：P(S) if count0 then /sell the ticket count=count-1 V(S)S.value=-1S.list-P1 喚醒相應(yīng)等待隊列中等待喚醒相應(yīng)等待隊列中等待 的一個進程；的一個進程； 改變其狀態(tài)為就緒態(tài)，改變其狀態(tài)為就緒態(tài)， 并將其插入就緒隊列中；并將其插入就緒隊列中；P0：P(S) if count0 then /sell the ticket count=count-1 V(S)S.value=0S.list-P1 喚醒相應(yīng)等待隊列中等待喚醒相應(yīng)等待隊列中等待 的一個進程；的一個進程； 改變其狀態(tài)為就緒態(tài)，改變其狀態(tài)為就緒態(tài)， 并將其插入就緒隊列中；并將其插入就緒隊列中；P0：P(S) if count0 then /sell the ticket count=count-1 V(S)S.value=0S.list-P1 喚醒相應(yīng)等待隊列中等待喚醒相應(yīng)等待隊列中等待 的一個進程；的一個進程； 改變其狀態(tài)為就緒態(tài)，改變其狀態(tài)為就緒態(tài)， 并將其插入就緒隊列中；并將其插入就緒隊列中；P0：P(S) if count0 then /sell the ticket count=count-1