操作系統(tǒng)概念

第四講進程互斥與同步OperatingSystemConceptionDavidfu上章回顧進程與程序的區(qū)別？什么是PCB？與進程上下文的區(qū)別？OperatingSystemConceptionDavidfu本課總體綱要進程互斥（MutualExclusiononProcesses）臨界區(qū)準則（CriticalSectionRule)加鎖實現(xiàn)互斥(MutualExclusion)信號量實現(xiàn)互斥（semaphore）兩種互斥方式的區(qū)別進程同步(Synchronization)P,V原語實現(xiàn)同步生產(chǎn)者消費者問題讀－寫問題哲學家就餐問題OperatingSystemConceptionDavidfu并發(fā)進程互斥協(xié)調(diào)準則不能假設各并發(fā)程序的相對執(zhí)行速度，各并發(fā)進程享有平等、獨立的競爭公共資源的權利并發(fā)進程中某個進程不在臨界區(qū)時，它不阻止其他進程進入臨界區(qū)并發(fā)進程中的若干各進程申請進入臨界區(qū)時，只能允許一個進程進入并發(fā)進程中某個進程申請進入臨界區(qū)，應該在有限的時間內(nèi)進入OperatingSystemConceptionDavidfu本課總體綱要進程互斥（MutualExclusiononProcesses）臨界區(qū)準則（CriticalSectionRule)加鎖實現(xiàn)互斥(MutualExclusion)信號量實現(xiàn)互斥（semaphore）兩種互斥方式的區(qū)別進程同步(Synchronization)P,V原語實現(xiàn)同步生產(chǎn)者消費者問題讀－寫問題哲學家就餐問題OperatingSystemConceptionDavidfu加鎖實現(xiàn)互斥(1)－單標志法P0:Whileturn!=0do{nothing}<臨界區(qū)>Turn:=1P1:Whileturn!=1do{nothing}<臨界區(qū)>Turn:=0OperatingSystemConceptionDavidfu加鎖實現(xiàn)互斥（3）－雙標志法改進版P0:Flag[0]:=true;Whileflag[1]do{nothing}<臨界區(qū)>Flag[0]:=false;P1:Flag[1]:=true;Whileflag[0]do{nothing}<臨界區(qū)>Flag[1]:=false;OperatingSystemConceptionDavidfu加鎖實現(xiàn)互斥（4）－雙標志法改進版P0:Flag[0]:=true;WhileFlag[1]do{Flag[0]:=false;<延遲一段時間>Flag[0]:=true;}<臨界區(qū)>Flag[0]:=false;P1:Flag[1]:=true;WhileFlag[0]do{Flag[1]:=false;<延遲一段時間>Flag[1]:=true;}<臨界區(qū)>Flag[1]:=false;OperatingSystemConceptionDavidfu本課總體綱要進程互斥（MutualExclusiononProcesses）臨界區(qū)準則（CriticalSectionRule)加鎖實現(xiàn)互斥(MutualExclusion)信號量實現(xiàn)互斥（semaphore）兩種互斥方式的區(qū)別進程同步(Synchronization)P,V原語實現(xiàn)同步生產(chǎn)者消費者問題讀－寫問題哲學家就餐問題OperatingSystemConceptionDavidfuP,V原語P原語操作V原語操作入口sem=sem－1sem>=0調(diào)用進程入等待隊列轉進程調(diào)度返回入口sem=sem+1sem<=0喚醒等待隊列中的進程轉進程調(diào)度返回是否是否OperatingSystemConceptionDavidfuP,V原語實現(xiàn)進程互斥描述P0,P1并發(fā)進程互斥：設sem取值（1，0，－1）Sem=1表示p0,p1都未進入臨界區(qū)sem=0表示p0或p1進入臨界區(qū)Sem=－1表示在p0和p1進程中，一個進程已經(jīng)進入臨界區(qū)，另一個處于等待進入臨界區(qū)狀態(tài)。P0:P(sem)<CS>V(sem)P1:P(sem)<CS>V(sem)…OperatingSystemConceptionDavidfu本課總體綱要進程互斥（MutualExclusiononProcesses）臨界區(qū)準則（CriticalSectionRule)加鎖實現(xiàn)互斥(MutualExclusion)信號量實現(xiàn)互斥（semaphore）兩種互斥方式的區(qū)別進程同步(Synchronization)P,V原語實現(xiàn)同步生產(chǎn)者消費者問題讀－寫問題哲學家就餐問題OperatingSystemConceptionDavidfu本課總體綱要進程互斥（MutualExclusiononProcesses）臨界區(qū)準則（CriticalSectionRule)加鎖實現(xiàn)互斥(MutualExclusion)信號量實現(xiàn)互斥（semaphore）兩種互斥方式的區(qū)別進程同步(Synchronization)P,V原語實現(xiàn)同步生產(chǎn)者消費者問題讀－寫問題哲學家就餐問題OperatingSystemConceptionDavidfu進程同步進程同步：把異步環(huán)境下的一組并發(fā)進程，因直接制約并互相發(fā)送消息而進行的相互合作、相互等待，并使進程按照一定的順序和速度執(zhí)行的過程。合作進程：具有同步關系的一組進程消息：合作進程互相發(fā)送的信號。則可使用以下過程：Wait(消息名):表示進程等待合作進程發(fā)來消息Signal(消息名)：表示向合作進程發(fā)送消息。OperatingSystemConceptionDavidfu信號量分類私用信號量：也可以把各進程之間發(fā)送的消息作為信號量看待。公用信號量：互斥時使用的信號量稱為公用信號量OperatingSystemConceptionDavidfu生產(chǎn)者消費者問題

生產(chǎn)者和消費者之間滿足的條件：消費者接收數(shù)據(jù)時，有界緩沖區(qū)中至少有一個是滿的生產(chǎn)者發(fā)送數(shù)據(jù)時，有界緩沖區(qū)中至少有一個是空的生產(chǎn)者進程與消費者進程必須互斥OperatingSystemConceptionDavidfuP,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,消費者私用信號量：fullOperatingSystemConceptionDavidfu讀者－寫者問題

讀者－寫者問題必須保證一個寫者與其他進程互斥的訪問共享數(shù)據(jù)的同步問題。加鎖實現(xiàn)同步信號量實現(xiàn)同步OperatingSystemConceptionDavidfu哲學家就餐問題

就餐條件：哲學家想吃飯，先提出吃飯要求提出吃飯要求后，并拿到兩雙筷子后，方可吃飯。如果筷子被他人獲得，則必須等待此人吃完后，才能獲取筷子對于已經(jīng)申請吃飯的任一個哲學家在自己未拿到兩只筷子吃飯之前，不放下自己的筷子剛開始就餐時，只允許兩個哲學家請求吃飯OperatingSystemConceptionDavidfu不相鄰的哲學家同時要求吃飯信號量S[i]來互斥兩兩相鄰哲學家的吃飯請求。信號量chopstick[i]來互斥筷子的使