操作系統(tǒng)第4講

1、操作系統(tǒng)概念第四講 進程互斥與同步上章回顧進程與程序的區(qū)別？什么是PCB？與進程上下文的區(qū)別？本課總體綱要進程互斥（ Mutual Exclusion on Processes）臨界區(qū)準(zhǔn)則（Critical Section Rule)加鎖實現(xiàn)互斥(Mutual Exclusion)信號量實現(xiàn)互斥（semaphore）兩種互斥方式的區(qū)別進程同步(Synchronization)P,V原語實現(xiàn)同步生產(chǎn)者消費者問題讀寫問題哲學(xué)家就餐問題進程互斥互斥：一組并發(fā)進程中的一個或多個程序段，因共享某一公有資源而導(dǎo)致它們必須以一個不允許交叉執(zhí)行的單位執(zhí)行。不允許兩個以上的共享該資源的進程同時進入臨界區(qū)臨界區(qū)：

2、 （Critical Section)把不允許多個并發(fā)進程交叉執(zhí)行的一段程序稱作臨界區(qū)。并發(fā)進程互斥協(xié)調(diào)準(zhǔn)則不能假設(shè)各并發(fā)程序的相對執(zhí)行速度，各并發(fā)進程享有平等、獨立的競爭公共資源的權(quán)利并發(fā)進程中某個進程不在臨界區(qū)時，它不阻止其他進程進入臨界區(qū)并發(fā)進程中的若干各進程申請進入臨界區(qū)時，只能允許一個進程進入并發(fā)進程中某個進程申請進入臨界區(qū)，應(yīng)該在有限的時間內(nèi)進入本課總體綱要進程互斥（ Mutual Exclusion on Processes）臨界區(qū)準(zhǔn)則（Critical Section Rule)加鎖實現(xiàn)互斥(Mutual Exclusion)信號量實現(xiàn)互斥（semaphore）兩種互斥方式的區(qū)

3、別進程同步(Synchronization)P,V原語實現(xiàn)同步生產(chǎn)者消費者問題讀寫問題哲學(xué)家就餐問題加鎖實現(xiàn)互斥(1)單標(biāo)志法P0:While turn!=0 donothingTurn:=1P1:While turn!=1 donothingTurn:=0加鎖實現(xiàn)互斥（2）雙標(biāo)志法P0:While flag1 donothingFlag0:=true;Flag0:=false;P1:While flag0 donothingFlag1:=true;Flag1:=false;加鎖實現(xiàn)互斥（3）雙標(biāo)志法改進版P0:Flag0:=true;While flag1 donothingFlag0:=f

4、alse;P1:Flag1:=true;While flag0 donothingFlag1:=false;加鎖實現(xiàn)互斥（4）雙標(biāo)志法改進版P0:Flag0:=true;While Flag1 doFlag0:=false;Flag0:=true;Flag0:=false;P1:Flag1:=true;While Flag0 doFlag1:=false;Flag1:=true;Flag1:=false;本課總體綱要進程互斥（ Mutual Exclusion on Processes）臨界區(qū)準(zhǔn)則（Critical Section Rule)加鎖實現(xiàn)互斥(Mutual Exclusion)信號

5、量實現(xiàn)互斥（semaphore）兩種互斥方式的區(qū)別進程同步(Synchronization)P,V原語實現(xiàn)同步生產(chǎn)者消費者問題讀寫問題哲學(xué)家就餐問題信號量（semaphore)P0:A:lock(w)Unlock(w)Goto AP1:A:lock(w)Unlock(w)Goto A信號量(sem):在操作系統(tǒng)中，信號量一般是一整數(shù)，當(dāng)sem=0:可供并發(fā)進程使用的資源實體數(shù)。當(dāng)sem=0調(diào)用進程入等待隊列轉(zhuǎn)進程調(diào)度返回入口sem=sem+1sem=0喚醒等待隊列中的進程轉(zhuǎn)進程調(diào)度返回是否是否P,V原語實現(xiàn)進程互斥描述P0,P1并發(fā)進程互斥：設(shè)sem取值（1，0，1）Sem=1表示p0,p1都

6、未進入臨界區(qū)sem=0表示p0或p1進入臨界區(qū)Sem=1表示在p0和p1進程中，一個進程已經(jīng)進入臨界區(qū)，另一個處于等待進入臨界區(qū)狀態(tài)。P0:P(sem)V(sem)P1:P(sem)V(sem)本課總體綱要進程互斥（ Mutual Exclusion on Processes）臨界區(qū)準(zhǔn)則（Critical Section Rule)加鎖實現(xiàn)互斥(Mutual Exclusion)信號量實現(xiàn)互斥（semaphore）兩種互斥方式的區(qū)別進程同步(Synchronization)P,V原語實現(xiàn)同步生產(chǎn)者消費者問題讀寫問題哲學(xué)家就餐問題加鎖法與信號量法的區(qū)別加鎖法信號量法1、加鎖過程可以中斷采用P、V

7、原語2、循環(huán)檢測鎖，系統(tǒng)開銷大，系統(tǒng)開銷小3、未進入臨界區(qū)的進程無排隊等待機制未進入臨界區(qū)的進程必須在等待隊列中等待本課總體綱要進程互斥（ Mutual Exclusion on Processes）臨界區(qū)準(zhǔn)則（Critical Section Rule)加鎖實現(xiàn)互斥(Mutual Exclusion)信號量實現(xiàn)互斥（semaphore）兩種互斥方式的區(qū)別進程同步(Synchronization)P,V原語實現(xiàn)同步生產(chǎn)者消費者問題讀寫問題哲學(xué)家就餐問題進程同步進程同步：把異步環(huán)境下的一組并發(fā)進程，因直接制約并互相發(fā)送消息而進行的相互合作、相互等待，并使進程按照一定的順序和速度執(zhí)行的過程。合作進

8、程：具有同步關(guān)系的一組進程消息：合作進程互相發(fā)送的信號。則可使用以下過程：Wait(消息名):表示進程等待合作進程發(fā)來消息Signal(消息名)：表示向合作進程發(fā)送消息。信號量分類私用信號量：也可以把各進程之間發(fā)送的消息作為信號量看待。公用信號量：互斥時使用的信號量稱為公用信號量本課總體綱要進程互斥（ Mutual Exclusion on Processes）臨界區(qū)準(zhǔn)則（Critical Section Rule)加鎖實現(xiàn)互斥(Mutual Exclusion)信號量實現(xiàn)互斥（semaphore）兩種互斥方式的區(qū)別進程同步(Synchronization)P,V原語實現(xiàn)同步生產(chǎn)者消費者問題讀

9、寫問題哲學(xué)家就餐問題生產(chǎn)者消費者問題生產(chǎn)者和消費者之間滿足的條件：消費者接收數(shù)據(jù)時，有界緩沖區(qū)中至少有一個是滿的生產(chǎn)者發(fā)送數(shù)據(jù)時，有界緩沖區(qū)中至少有一個是空的生產(chǎn)者進程與消費者進程必須互斥P,V原語實現(xiàn)同步Producer(data)BeginP(available)P(mutex)送數(shù)據(jù)進入緩沖區(qū)某單元V(full)V(mutex)EndConsumer(data)BeginP(full)P(mutex)送數(shù)據(jù)進入緩沖區(qū)某單元V(available)V(mutex)End公用信號量：mutex生產(chǎn)者私用信號量：available,消費者私用信號量：full讀者寫者問題讀者寫者問題必須保證一個

10、寫者與其他進程互斥的訪問共享數(shù)據(jù)的同步問題。加鎖實現(xiàn)同步信號量實現(xiàn)同步同步問題有一個50座的閱覽室，讀者進入閱覽室時，必須在登記簿上查找是否有空座，如果有，則登記姓名并進入閱讀，當(dāng)讀者離開閱覽室時，需要注銷座位和姓名。采用P、V操作完成讀者操作的同步算法。哲學(xué)家就餐問題就餐條件：哲學(xué)家想吃飯，先提出吃飯要求提出吃飯要求后，并拿到兩雙筷子后，方可吃飯。如果筷子被他人獲得，則必須等待此人吃完后，才能獲取筷子對于已經(jīng)申請吃飯的任一個哲學(xué)家在自己未拿到兩只筷子吃飯之前，不放下自己的筷子剛開始就餐時，只允許兩個哲學(xué)家請求吃飯不相鄰的哲學(xué)家同時要求吃飯信號量Si來互斥兩兩相鄰哲學(xué)家的吃飯請求。信號量chopsticki來互斥筷子的使用 i (i+4)%5 (i+1)%5 (i+3)%5 (i+2)%5總結(jié)進程互斥（ Mutual Exclusion on Proce