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

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

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

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

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

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

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

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

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

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

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