第3章進(jìn)程管理(互斥及同步)

1、2022-1-1813.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步一、研究進(jìn)程互斥與同步目的一、研究進(jìn)程互斥與同步目的 分析一組并發(fā)進(jìn)程在執(zhí)行過程中，因資源競爭，資源共享引起的對其執(zhí)行速度的影響，并找出消除其負(fù)面影響的條件與方法。二、認(rèn)識進(jìn)程互斥與同步相關(guān)的重要概念與術(shù)語二、認(rèn)識進(jìn)程互斥與同步相關(guān)的重要概念與術(shù)語 1. 臨界區(qū)臨界區(qū) 引入背景引入背景：為保證并發(fā)進(jìn)程執(zhí)行結(jié)果的正確性。為保證并發(fā)進(jìn)程執(zhí)行結(jié)果的正確性。 定義：定義：不允許多個并發(fā)進(jìn)程交叉執(zhí)行的一段程序稱為臨界區(qū)。不允許多個并發(fā)進(jìn)程交叉執(zhí)行的一段程序稱為臨界區(qū)。 臨界區(qū)是由屬于不同并發(fā)進(jìn)程的程序段共享公用數(shù)據(jù)或公用臨界區(qū)是由屬于不同并

2、發(fā)進(jìn)程的程序段共享公用數(shù)據(jù)或公用數(shù)據(jù)變量而引起的，臨界區(qū)不可能用增加硬件的方法來解決。因數(shù)據(jù)變量而引起的，臨界區(qū)不可能用增加硬件的方法來解決。因此，此，臨界區(qū)被稱為訪問公用數(shù)據(jù)的那段程序臨界區(qū)被稱為訪問公用數(shù)據(jù)的那段程序。 2022-1-1823.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步二、認(rèn)識進(jìn)程互斥與同步相關(guān)的重要概念與術(shù)語（二、認(rèn)識進(jìn)程互斥與同步相關(guān)的重要概念與術(shù)語（2 2）2間接制約間接制約該概念的討論，是面向互斥而言，面向共享資源（如公用數(shù)據(jù)和變量），是面向一組并發(fā)進(jìn)程（2個以上）而言，面向其因資源競爭而對其速度影響問題。定義：指一組并發(fā)進(jìn)程因資源共享（如公用數(shù)據(jù)及變量）對其執(zhí)行速度

3、的影響（制約）的過程。3. 進(jìn)程互斥的定義：進(jìn)程互斥的定義：一組并發(fā)進(jìn)程因間接制約互相合作，互相等待的過程，稱為進(jìn)程的互斥。 注釋1:是多個進(jìn)程和一個進(jìn)程之間的關(guān)系，即1對多的關(guān)系。 注釋2:目的是禁止兩個以上共享同一資源的并發(fā)進(jìn)程同時進(jìn)入臨界區(qū)。PA（慢）是因?yàn)镻B占用了PA的資源而不得不等待，所以進(jìn)程PA的慢是因?yàn)镻B的間接制約而引起的2022-1-1833.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步二、認(rèn)識進(jìn)程互斥與同步相關(guān)的重要概念與術(shù)語二、認(rèn)識進(jìn)程互斥與同步相關(guān)的重要概念與術(shù)語(3)(3) 4.4. 直接制約（與同步相關(guān)的概念）直接制約（與同步相關(guān)的概念） 該概念的討論是面向同步而言，

4、是面向該概念的討論是面向同步而言，是面向2 2個進(jìn)程而言，是面向個進(jìn)程而言，是面向 2 2 個進(jìn)程因資源競爭而對其速度影響問題。個進(jìn)程因資源競爭而對其速度影響問題。定義：定義：2 2個在個在異步環(huán)境異步環(huán)境下的并發(fā)進(jìn)程，各自執(zhí)行的結(jié)果互為對方下的并發(fā)進(jìn)程，各自執(zhí)行的結(jié)果互為對方繼續(xù)執(zhí)行的條件，因而引起的對其執(zhí)行速度限制（影響）的過程，繼續(xù)執(zhí)行的條件，因而引起的對其執(zhí)行速度限制（影響）的過程，稱之為直接制約稱之為直接制約。 注釋注釋1 1：是對兩個進(jìn)程而言，即：是對兩個進(jìn)程而言，即1 1對對1 1問題。問題。 注釋注釋2 2：目的是禁止因直接制約而引發(fā)的死鎖現(xiàn)象：目的是禁止因直接制約而引發(fā)的死鎖

5、現(xiàn)象。 2022-1-1843.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步二、認(rèn)識進(jìn)程互斥與同步相關(guān)的重要概念與術(shù)語（二、認(rèn)識進(jìn)程互斥與同步相關(guān)的重要概念與術(shù)語（4 4）5 5進(jìn)程同步定義：進(jìn)程同步定義： 2 2個并發(fā)進(jìn)程，因直接制約，互相發(fā)送消息，而進(jìn)行的相互合作、個并發(fā)進(jìn)程，因直接制約，互相發(fā)送消息，而進(jìn)行的相互合作、相互等待，使其按照一定的速度執(zhí)行的過程叫做進(jìn)程的同步。相互等待，使其按照一定的速度執(zhí)行的過程叫做進(jìn)程的同步。6 6異步環(huán)境：異步環(huán)境： 在同一段時間內(nèi)，一組并發(fā)進(jìn)程，各自以不可預(yù)知的速度獨(dú)立地在同一段時間內(nèi)，一組并發(fā)進(jìn)程，各自以不可預(yù)知的速度獨(dú)立地向前推進(jìn)，稱為進(jìn)程的異步性或異

6、步環(huán)境。（起始時間的隨機(jī)性向前推進(jìn)，稱為進(jìn)程的異步性或異步環(huán)境。（起始時間的隨機(jī)性 ) )2022-1-1853.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步三、原語及其類型三、原語及其類型1 1原語定義：原語定義：在系統(tǒng)態(tài)下，執(zhí)行某些具有特定功能的程序段稱之為原語。在系統(tǒng)態(tài)下，執(zhí)行某些具有特定功能的程序段稱之為原語。（調(diào)用核心層子程序的指令）（調(diào)用核心層子程序的指令）微軟微軟19991999年第年第3 3版版(239(239頁頁) )之計(jì)算機(jī)詞典解釋之計(jì)算機(jī)詞典解釋: :在在OSOS中，調(diào)用核中，調(diào)用核心層子程序的指令，它好像是一條擴(kuò)充了的機(jī)器指令心層子程序的指令，它好像是一條擴(kuò)充了的機(jī)器指令。

7、2 2原語類別：原語類別：（semaphorsemaphor）簡稱）簡稱semsem指令級原語指令級原語該程序段（或擴(kuò)充了的指令）在其執(zhí)行期該程序段（或擴(kuò)充了的指令）在其執(zhí)行期 間不允許中斷，間不允許中斷，是一個不可再分的指令單位。是一個不可再分的指令單位。功能級原語功能級原語該程序段在執(zhí)行期間不允許并發(fā)執(zhí)行。該程序段在執(zhí)行期間不允許并發(fā)執(zhí)行。 2022-1-1863.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步四、信號量四、信號量1. 1. 是用于控制進(jìn)程執(zhí)行過程的是用于控制進(jìn)程執(zhí)行過程的信號式標(biāo)志型變量信號式標(biāo)志型變量。2 2定義：定義：在程序設(shè)計(jì)中，一種用來對共享系統(tǒng)資源進(jìn)行控制的信在程序設(shè)

8、計(jì)中，一種用來對共享系統(tǒng)資源進(jìn)行控制的信號，即一種標(biāo)志變量，信標(biāo)向潛在的用戶（進(jìn)程）指明，某個號，即一種標(biāo)志變量，信標(biāo)向潛在的用戶（進(jìn)程）指明，某個文件或資源正在使用中，以防止除此之外的其它用戶來訪問它。文件或資源正在使用中，以防止除此之外的其它用戶來訪問它。引入信號量的目的，是為了服務(wù)于引入信號量的目的，是為了服務(wù)于PVPV原語。原語。 (744(744頁中的英頁中的英漢雙解詞典解釋漢雙解詞典解釋) )3 3說明說明: : 與互斥相關(guān)的信號量叫與互斥相關(guān)的信號量叫公用信號量公用信號量，與多個進(jìn)程有關(guān)。，與多個進(jìn)程有關(guān)。與同步相關(guān)的信號量叫與同步相關(guān)的信號量叫私有信號量私有信號量，與，與2 2

9、個進(jìn)程有關(guān)個進(jìn)程有關(guān) 。2022-1-1873.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步五、五、P.VP.V原語原語1 1是是19651965年荷蘭學(xué)者年荷蘭學(xué)者DijkstraDijkstra根據(jù)火車信號原理，提出來用于解決根據(jù)火車信號原理，提出來用于解決進(jìn)程互斥和同步存在問題的模型。進(jìn)程互斥和同步存在問題的模型。 P P（荷文（荷文 PasserenPasseren，英文，英文Pass Pass 簡稱簡稱P P原語）調(diào)度原語）調(diào)度 ；V V（荷文（荷文VenhoogVenhoog，英文，英文incremane incremane 簡稱簡稱V V原語）增量。原語）增量。Tannibaum提出

10、相對應(yīng)的提出相對應(yīng)的 Down(sleep) P 和和 Up(wekeup) V。 2 2P.VP.V原語原語是基于對信號量的操作，是兩個不可中斷的是基于對信號量的操作，是兩個不可中斷的指令級原語指令級原語操作操作，是用于解決進(jìn)程的同步與互斥問題，是用于解決進(jìn)程的同步與互斥問題。 2022-1-1883.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步3 3用用PVPV原語實(shí)現(xiàn)兩個進(jìn)程原語實(shí)現(xiàn)兩個進(jìn)程P PA A與與P PB B的描述的描述 設(shè)設(shè)SemSem的初值為的初值為1 1，取值范圍為（，取值范圍為（0 0，1 1，-1-1） 設(shè)設(shè)Sem=1 Sem=1 初值初值 臨界區(qū)為空，臨界區(qū)為空，P P

11、A A、P PB B都未進(jìn)入都未進(jìn)入當(dāng)一個進(jìn)程執(zhí)行P原語減1操作，Sem=0，表示該進(jìn)程可以進(jìn)入臨界區(qū)。另一個進(jìn)程也要進(jìn)入臨界區(qū)，也必需先進(jìn)行P操作，若 Sem=-1Sem=-1 說明已有一個進(jìn)程進(jìn)入臨界區(qū)，另一個進(jìn)程則進(jìn)入在等待狀態(tài)。Sem=0 ，允許，允許P PA A 、 P PB B有一個進(jìn)入臨界區(qū)有一個進(jìn)入臨界區(qū)2022-1-1893.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步 4 4P P(sem)(sem)原語操作原語操作（減法操作）減法操作）進(jìn)程進(jìn)入臨界區(qū)首先必須進(jìn)行的操作，即進(jìn)程進(jìn)入臨界區(qū)首先必須進(jìn)行的操作，即減減1 1操作。操作。 設(shè)設(shè) SemSem初值為初值為1 1Sem=

12、Sem-1Sem= Sem-1， SemSem的結(jié)果只可能是的結(jié)果只可能是0 0，或，或-1-1若若 0 0，則進(jìn)程調(diào)入進(jìn)占臨界區(qū)，訪問共享資源。第一次，則進(jìn)程調(diào)入進(jìn)占臨界區(qū)，訪問共享資源。第一次 進(jìn)程進(jìn)行進(jìn)程進(jìn)行P P操作操作之后，之后， Sem= Sem= ，說明臨界區(qū)未占用，則該進(jìn)程可以進(jìn)占臨界區(qū)。，說明臨界區(qū)未占用，則該進(jìn)程可以進(jìn)占臨界區(qū)。第第2 2個進(jìn)程欲進(jìn)入，也要先進(jìn)行個進(jìn)程欲進(jìn)入，也要先進(jìn)行P P操作，操作，Sem =Sem =1 1 ，則說明臨界區(qū)已占，則說明臨界區(qū)已占用，則該進(jìn)程不能進(jìn)占臨界區(qū)，而后轉(zhuǎn)入阻塞隊(duì)列。用，則該進(jìn)程不能進(jìn)占臨界區(qū)，而后轉(zhuǎn)入阻塞隊(duì)列。 第第3 3個個.

13、 . .第第n n個欲進(jìn)入的進(jìn)程操作，也要先進(jìn)行個欲進(jìn)入的進(jìn)程操作，也要先進(jìn)行P P操作！操作！ 2022-1-1810N N3.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步 Sem=0入口Sem= Sem-1轉(zhuǎn)進(jìn)程調(diào)度，該進(jìn)程進(jìn)入臨界區(qū)，進(jìn)占相應(yīng)資源返 回 到 進(jìn) 程的下一步將該進(jìn)程阻塞轉(zhuǎn)進(jìn)程調(diào) 度 執(zhí)行其它進(jìn)程Y Y圖圖3.11 3.11 原語操作流程原語操作流程2022-1-18113.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步5 5V V(sem)(sem)原語操作原語操作（加加法操作）法操作）進(jìn)程退出臨界區(qū)必須進(jìn)行的操作，即進(jìn)程退出臨界區(qū)必須進(jìn)行的操作，即Sem= Sem= Sem+1Se

14、m+1操作。操作。若若Sem =0Sem =0，則從阻塞隊(duì)列中喚醒一進(jìn)程，返回到，則從阻塞隊(duì)列中喚醒一進(jìn)程，返回到原進(jìn)程中斷處繼續(xù)執(zhí)行或原進(jìn)程中斷處繼續(xù)執(zhí)行或轉(zhuǎn)入進(jìn)程調(diào)度。轉(zhuǎn)入進(jìn)程調(diào)度。 若無后續(xù)進(jìn)程繼續(xù)進(jìn)行，系統(tǒng)則令若無后續(xù)進(jìn)程繼續(xù)進(jìn)行，系統(tǒng)則令Sem =1Sem =1 有無有無Sem=Sem+1=Sem=Sem+1=1 1，2 2，3 3，4 4，5 5之可能？之可能？2022-1-18123.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步圖圖 3.12 3.12 原語操作流程原語操作流程 sem=sem+1是從阻塞隊(duì)列中喚醒等待隊(duì)列中的一個進(jìn)程返回或轉(zhuǎn)進(jìn)程調(diào)度s0入口返回否2022-1-181

15、33.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步七、互斥實(shí)現(xiàn)的條件（籃球競爭問題）七、互斥實(shí)現(xiàn)的條件（籃球競爭問題） 如果一個進(jìn)程在執(zhí)行期間，訪問公用資源，若允許發(fā)生如果一個進(jìn)程在執(zhí)行期間，訪問公用資源，若允許發(fā)生中斷，則有可能導(dǎo)致前后計(jì)算出現(xiàn)不一致，為防止問題中斷，則有可能導(dǎo)致前后計(jì)算出現(xiàn)不一致，為防止問題出現(xiàn)，需滿足如下條件：出現(xiàn)，需滿足如下條件：1. 1. 空則讓進(jìn)，只允進(jìn)空則讓進(jìn)，只允進(jìn)1 1指臨界區(qū)空閑，允許一個進(jìn)程進(jìn)入。指臨界區(qū)空閑，允許一個進(jìn)程進(jìn)入。2. 2. 內(nèi)可阻外，外不相擾內(nèi)可阻外，外不相擾臨界區(qū)只允許一個進(jìn)程訪問公用資源，臨界區(qū)只允許一個進(jìn)程訪問公用資源，臨界區(qū)之外的其它進(jìn)

16、程互相之間不發(fā)生阻撓。臨界區(qū)之外的其它進(jìn)程互相之間不發(fā)生阻撓。3. 3. 限時等待限時等待在限定時間內(nèi)，必須進(jìn)入臨界區(qū)，以防止死鎖發(fā)在限定時間內(nèi)，必須進(jìn)入臨界區(qū)，以防止死鎖發(fā)生。死鎖是生。死鎖是 指各并發(fā)進(jìn)程彼此相互等待對方所擁有的資源，且指各并發(fā)進(jìn)程彼此相互等待對方所擁有的資源，且在得到對方資源之前，不會釋放自己所擁有資源之現(xiàn)象。在得到對方資源之前，不會釋放自己所擁有資源之現(xiàn)象。4. 4. 讓權(quán)等待讓權(quán)等待當(dāng)進(jìn)程不能進(jìn)入臨界區(qū)時，應(yīng)即通知當(dāng)進(jìn)程不能進(jìn)入臨界區(qū)時，應(yīng)即通知CPUCPU，以免陷入盲等。2022-1-18143.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步 八、互斥的負(fù)面影響，解決的途

17、徑與方法八、互斥的負(fù)面影響，解決的途徑與方法目的在于避免因進(jìn)程并發(fā)可能導(dǎo)致結(jié)果不可再現(xiàn)目的在于避免因進(jìn)程并發(fā)可能導(dǎo)致結(jié)果不可再現(xiàn)1 1軟件的方法軟件的方法公用變量整型法公用變量整型法 數(shù)組法數(shù)組法 變量與數(shù)組混合算法變量與數(shù)組混合算法 軟件的方法從理論上行的通，在方法上也有解決的途徑，但軟件的方法從理論上行的通，在方法上也有解決的途徑，但卻難以實(shí)現(xiàn)，因?yàn)橐ＷC下一個并發(fā)進(jìn)程的連續(xù)性，不被別卻難以實(shí)現(xiàn)，因?yàn)橐ＷC下一個并發(fā)進(jìn)程的連續(xù)性，不被別的進(jìn)程中斷，需要對執(zhí)行的下一步進(jìn)行判斷，從而導(dǎo)致計(jì)算的進(jìn)程中斷，需要對執(zhí)行的下一步進(jìn)行判斷，從而導(dǎo)致計(jì)算機(jī)系統(tǒng)的整體性能下降，因而軟件的方法是不可取的。機(jī)系

18、統(tǒng)的整體性能下降，因而軟件的方法是不可取的。2.2.硬件的方法硬件的方法為全局和每個硬件設(shè)置一個布爾變量（即邏輯值的真假）2022-1-18153.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步 九、實(shí)現(xiàn)進(jìn)程互斥的九、實(shí)現(xiàn)進(jìn)程互斥的PVPV原語操作原語操作1. 1. 解決方案，使用解決方案，使用PVPV原語加信號量的方法原語加信號量的方法2. 2. 任一進(jìn)程要獲取某一共享資源，必須通過臨界區(qū)來判定是否具有任一進(jìn)程要獲取某一共享資源，必須通過臨界區(qū)來判定是否具有獲取獨(dú)占共享資源的資格。獲取獨(dú)占共享資源的資格。3. 3. 任一進(jìn)程在申請某一共享資源時，必須首先進(jìn)行任一進(jìn)程在申請某一共享資源時，必須首先進(jìn)

19、行P P操作。操作。4. Sem4. Sem初值為初值為1 1。5. P5. P操作步驟操作步驟: : 設(shè)設(shè)P P為某一組進(jìn)程為某一組進(jìn)程P1P1、 P2P2、 P3P3、 P4 P4 ，申請某一共享資源，依序，申請某一共享資源，依序進(jìn)行進(jìn)行P1P1操作：操作：2022-1-18163.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步5. P5. P操作步驟（續(xù)）操作步驟（續(xù)） （1 1） SemSem =Sem-1=0=Sem-1=0（2 2）P1P1進(jìn)占臨界區(qū)，即進(jìn)占申請的某一共享資源，進(jìn)占臨界區(qū)，即進(jìn)占申請的某一共享資源，在在P1P1未退出占未退出占有的資源時，依序進(jìn)行有的資源時，依序進(jìn)行P2P

20、2、 P3P3、 P4P4操作操作，依次對依次對SemSem進(jìn)行減一進(jìn)行減一操作，則操作，則SemSem0 0，P 2P 2、 P3P3、 P4P4被阻塞。被阻塞。請問請問1：的値會否出現(xiàn)的値會否出現(xiàn)-1，-2，-3，-4的問題？的問題？請問請問2：P P操作如何設(shè)計(jì)，才能避免交叉使用同一資源而引起操作如何設(shè)計(jì)，才能避免交叉使用同一資源而引起結(jié)果不可再現(xiàn)性。結(jié)果不可再現(xiàn)性。請問請問3：此時強(qiáng)行置此時強(qiáng)行置 Sem =-1，結(jié)果如何？，結(jié)果如何？2022-1-18173.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步九、實(shí)現(xiàn)進(jìn)程互斥的九、實(shí)現(xiàn)進(jìn)程互斥的PV原語操作原語操作(2)6. V6. V操作步驟

21、操作步驟（1）任一進(jìn)程完成）任一進(jìn)程完成P操作，獨(dú)占某一共享資源，使用完畢后，操作，獨(dú)占某一共享資源，使用完畢后，必須立即退出，退出時必須進(jìn)行必須立即退出，退出時必須進(jìn)行V操作，即操作，即Sem+1操作。操作。Sem = Sem+1 = 0（2）若）若Sem=0，則進(jìn)程調(diào)度從就緒隊(duì)列選一進(jìn)程進(jìn)占，則進(jìn)程調(diào)度從就緒隊(duì)列選一進(jìn)程進(jìn)占CPU。（3）V V操作完成之后操作完成之后, ,不會出現(xiàn)不會出現(xiàn)SemSem0 0的情的情況況？2022-1-18183.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步 十、實(shí)現(xiàn)進(jìn)程同步的十、實(shí)現(xiàn)進(jìn)程同步的PV PV 原語操作（原語操作（1 1） 面向面向2個進(jìn)程，即乒乓問

22、題）個進(jìn)程，即乒乓問題）1 1條件（以計(jì)算進(jìn)程條件（以計(jì)算進(jìn)程P PA A和輸出進(jìn)程和輸出進(jìn)程P PB B為例）為例）(1) P(1) PA A必須向緩沖區(qū)發(fā)送一個數(shù)據(jù)，必須向緩沖區(qū)發(fā)送一個數(shù)據(jù)，P PB B才能從中取才能從中取 出一個數(shù)據(jù)，取須有之，無則不取。出一個數(shù)據(jù)，取須有之，無則不取。(2) (2) 空則可發(fā)，滿則停止?？談t可發(fā)，滿則停止。(3) FIFO(3) FIFO算法。（先進(jìn)先出算法）算法。（先進(jìn)先出算法）2022-1-18193.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步十、實(shí)現(xiàn)進(jìn)程同步的十、實(shí)現(xiàn)進(jìn)程同步的PV PV 原語操作（原語操作（2 2） 2用用PV原語實(shí)現(xiàn)進(jìn)程同步原語

23、實(shí)現(xiàn)進(jìn)程同步 同步是解決兩個進(jìn)程（同步是解決兩個進(jìn)程（P PA A、P PB B）因共享同一資源因直接）因共享同一資源因直接制約產(chǎn)生的死鎖問題，所謂同步，是兩個進(jìn)程各自執(zhí)行制約產(chǎn)生的死鎖問題，所謂同步，是兩個進(jìn)程各自執(zhí)行的結(jié)果互為對方執(zhí)行條件。的結(jié)果互為對方執(zhí)行條件。 同步所討論的是進(jìn)程同步所討論的是進(jìn)程1 1對對1 1問題，使用的信號量稱為私用問題，使用的信號量稱為私用信號量信號量。 雖然通過每一步操作可以解決問題，但會浪費(fèi)大量雖然通過每一步操作可以解決問題，但會浪費(fèi)大量的的CPUCPU資源，因此而引起系統(tǒng)效率的大幅度降資源，因此而引起系統(tǒng)效率的大幅度降低低。?2022-1-18202020

24、3.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步十、實(shí)現(xiàn)進(jìn)程同步的十、實(shí)現(xiàn)進(jìn)程同步的PV PV 原語操作（原語操作（3)3)(3)(3)解決步驟解決步驟 設(shè)置私用信號量設(shè)置私用信號量SemSem，并為其賦初值，并為其賦初值 用同步原語（發(fā)送和接收）用同步原語（發(fā)送和接收）+ +信號量（私用）解決問題信號量（私用）解決問題(4)(4)例例 : P: PA A（計(jì)算進(jìn)程）（計(jì)算進(jìn)程） P PB B（打印進(jìn)程）（打印進(jìn)程）計(jì)算進(jìn)程為計(jì)算進(jìn)程為Sem(A)=nSem(A)=n，n n 表示有表示有n n個緩沖區(qū)個緩沖區(qū)打印進(jìn)程為打印進(jìn)程為Sem(B)=0Sem(B)=0，表示無數(shù)據(jù)可取，表示無數(shù)據(jù)可取P

25、PA A向緩沖區(qū)發(fā)送一個數(shù)據(jù)，則向緩沖區(qū)發(fā)送一個數(shù)據(jù)，則Sem(A)= Sem(A)-1Sem(A)= Sem(A)-1， Sem(A)=0Sem(A)=0，緩沖區(qū)滿。緩沖區(qū)滿。 P PA A同步原語向同步原語向P PB B發(fā)送一個消息發(fā)送一個消息 Sem(B)Sem(B)進(jìn)行進(jìn)行n n次次V V操作，當(dāng)操作，當(dāng)Sem=nSem=n，說明緩沖區(qū)空，向，說明緩沖區(qū)空，向P PA A發(fā)送消發(fā)送消息，息， P PA A可繼續(xù)向緩沖區(qū)發(fā)送數(shù)據(jù)，直到發(fā)送與接收完畢。可繼續(xù)向緩沖區(qū)發(fā)送數(shù)據(jù)，直到發(fā)送與接收完畢。2022-1-18213.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步十一、互斥的加鎖實(shí)現(xiàn)十一、互斥

26、的加鎖實(shí)現(xiàn)1. 1. 實(shí)現(xiàn)并發(fā)進(jìn)程的互斥。只需把臨界區(qū)中的各個過程按不同的實(shí)現(xiàn)并發(fā)進(jìn)程的互斥。只需把臨界區(qū)中的各個過程按不同的時間排列調(diào)用就可以實(shí)現(xiàn)并發(fā)進(jìn)程的互斥。但事實(shí)上這是不時間排列調(diào)用就可以實(shí)現(xiàn)并發(fā)進(jìn)程的互斥。但事實(shí)上這是不可能的。因?yàn)檫@要求該組并發(fā)進(jìn)程中的每個進(jìn)程事先知道其可能的。因?yàn)檫@要求該組并發(fā)進(jìn)程中的每個進(jìn)程事先知道其他并發(fā)進(jìn)程與系統(tǒng)的動作，由用戶程序執(zhí)行開始的隨機(jī)性可他并發(fā)進(jìn)程與系統(tǒng)的動作，由用戶程序執(zhí)行開始的隨機(jī)性可知，這是不可能的知，這是不可能的。2.2.一種可能的辦法是對臨界區(qū)加鎖以實(shí)現(xiàn)互斥。當(dāng)某個進(jìn)程進(jìn)一種可能的辦法是對臨界區(qū)加鎖以實(shí)現(xiàn)互斥。當(dāng)某個進(jìn)程進(jìn)入臨界區(qū)之后，它將鎖上臨界區(qū)，直到它退出臨界區(qū)時為止。入臨界區(qū)之后，它將鎖上臨界區(qū)，直到它退出臨界區(qū)時為止。并發(fā)進(jìn)程在申請進(jìn)入臨界區(qū)時，首先測試該臨界區(qū)是否是上并發(fā)進(jìn)程在申請進(jìn)入臨界區(qū)時，首先測試該臨界區(qū)是否是上鎖的。如果該臨界區(qū)已被鎖住，則該進(jìn)程要等到該臨界區(qū)開鎖的。如果該臨界區(qū)已被鎖住，則該進(jìn)程要等到該臨界區(qū)開鎖之后才有可能獲得臨界區(qū)鎖之后才有可能獲得臨界區(qū)。2022-1-18223.5 3.5 進(jìn)程互斥與同步進(jìn)程互斥與同步十一、互斥的加鎖實(shí)現(xiàn)十一、互