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

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

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

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

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

5、，如果不去顧及這三者之間執(zhí)行順序的這種關(guān)系，隨意讓GET、COPY、PUT去并發(fā)執(zhí)行，那么就會產(chǎn)生錯(cuò)誤。 記錄記錄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)進(jìn)程的互斥進(jìn)程的互斥u共享變量共享變量&在操作系統(tǒng)中，把那些可以被進(jìn)程共享的資源（如文在操作系統(tǒng)中，把那些可以被進(jìn)程共享的資源（如文件、隊(duì)列、緩沖區(qū)、表格、變量等）統(tǒng)稱為件、隊(duì)列、緩沖區(qū)、表格、變量等）統(tǒng)稱為“共享變共享變量量”或或“臨界資源臨界資源”。u互斥互斥&與一個(gè)共享變量（或臨界資源）交往的多個(gè)進(jìn)程，為與一個(gè)共享變量（或臨界資源）交往的多個(gè)進(jìn)程，為了保證它們各自運(yùn)行結(jié)果的正確性，當(dāng)其中的一個(gè)進(jìn)了保證它們各自運(yùn)行結(jié)果的正確性，

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

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

9、有限的時(shí)間內(nèi)得到滿足間內(nèi)得到滿足讓權(quán)等待讓權(quán)等待：處于等待狀態(tài)的進(jìn)程應(yīng)放棄占用：處于等待狀態(tài)的進(jìn)程應(yīng)放棄占用CPUCPU，以使其他進(jìn)程有機(jī)會得到，以使其他進(jìn)程有機(jī)會得到CPUCPU的使用權(quán)的使用權(quán)協(xié)同工作協(xié)同工作進(jìn)程同步進(jìn)程同步從文件從文件F取出一個(gè)記取出一個(gè)記錄送至輸入緩沖區(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é)束”的消息，只有接到這個(gè)消息，GET才能去做下一步工作。相對地，COPY也一直處于等待。只有接到GET發(fā)送來 “可以拷貝”的消息才能工作，將R里的記錄拷貝到T里，然后向GET發(fā)“拷貝結(jié)束”的消息，隨之又等待GET發(fā)消息。 同步、同步點(diǎn)、同步條件同步、同步點(diǎn)、同步條件u一組并發(fā)進(jìn)程因直接制約而互相發(fā)送消息，進(jìn)一組并發(fā)進(jìn)程因直接制約而互相發(fā)送消息，進(jìn)行互相合作，互相等待，使得各進(jìn)程按一定的行互相合作，互相等待，使得各

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

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

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

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

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

16、) sem.value + +sem.value + +; /; /表示釋放一個(gè)資源表示釋放一個(gè)資源 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)等待隊(duì)列中等待喚醒

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