操作系統概念

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

生產者和消費者之間滿足的條件：消費者接收數據時，有界緩沖區中至少有一個是滿的生產者發送數據時，有界緩沖區中至少有一個是空的生產者進程與消費者進程必須互斥OperatingSystemConceptionDavidfuP,V原語實現同步Producer(data)BeginP(available)P(mutex)送數據進入緩沖區某單元V(full)V(mutex)EndConsumer(data)BeginP(full)P(mutex)送數據進入緩沖區某單元V(available)V(mutex)End公用信號量：mutex生產者私用信號量：available,消費者私用信號量：fullOperatingSystemConceptionDavidfu讀者－寫者問題

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

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