### 軟件實現方法 在進入區設置和檢查一些標志來標明是否有進程在臨界區中，如果已有進程在臨界區，則在進入區通過循環檢查進行等待，進程離開臨界區后則在退出區修改標志。 ####1) 算法一：單標志法。 該算法設置一個公用整型變量turn,用于指示被允許進入臨界區的進程編號，即若turn=0，則允許P0進程進入臨界區。該算法可確保每次只允許一個進程進入臨界區。但兩個進程必須交替進入臨界區，如果某個進程不再進入臨界區了，那么另一個進程也將進入臨界區（違背“空閑讓進”）這樣很容易造成資源利用的不充分。 ~~~ // P0進程 while(turn!=0); critical section; turn=1; remainder section; // P1進程 while(turn!=1); // 進入區 critical section; // 臨界區 turn = 0; // 退出區 remainder section; // 剩余區 ~~~ ####2) 算法二：雙標志法先檢查。 該算法的基本思想是在每一個進程訪問臨界區資源之前，先查看一下臨界資源是否正被訪問，若正被訪問，該進程需等待；否則，進程才進入自己的臨界區。為此，設置了一個數據flag[i]，如第i個元素值為FALSE，表示Pi進程未進入臨界區，值為TRUE，表示Pi進程進入臨界區。 ~~~ // Pi 進程 while(flag[j]); // ① flag[i]=TRUE; // ③ critical section; flag[i] = FALSE; remainder section; // Pj 進程 while(flag[i]); // ② 進入區 flag[j] =TRUE; // ④ 進入區 critical section; // 臨界區 flag[j] = FALSE; // 退出區 remainder section; // 剩余區 ~~~ 優點：不用交替進入，可連續使用；缺點：Pi和Pj可能同時進入臨界區。按序列①②③④ 執行時，會同時進入臨界區（違背“忙則等待”)。即在檢查對方flag之后和切換自己flag 之前有一段時間，結果都檢查通過。這里的問題出在檢查和修改操作不能一次進行。 ####3) 算法三：雙標志法后檢查。 算法二是先檢測對方進程狀態標志后，再置自己標志，由于在檢測和放置中可插入另一個進程到達時的檢測操作，會造成兩個進程在分別檢測后，同時進入臨界區。為此，算法三釆用先設置自己標志為TRUE后,再檢測對方狀態標志，若對方標志為TURE，則進程等待；否則進入臨界區。 ~~~ // Pi進程 flag[i] =TRUE; while(flag[j]); critical section; flag[i] =FLASE; remainder section; // Pj進程 flag[j] =TRUE; // 進入區 while(flag[i]); // 進入區 critical section; // 臨界區 flag [j] =FLASE; // 退出區 remainder section; // 剩余區 ~~~ 當兩個進程幾乎同時都想進入臨界區時，它們分別將自己的標志值flag設置為TRUE，并且同時檢測對方的狀態（執行while語句），發現對方也要進入臨界區，于是雙方互相謙讓，結果誰也進不了臨界區，從而導致“饑餓”現象。 ####4)算法四：Peterson’s Algorithm。 為了防止兩個進程為進入臨界區而無限期等待，又設置變量turn，指示不允許進入臨界區的進程編號，每個進程在先設置自己標志后再設置turn 標志，不允許另一個進程進入。這時，再同時檢測另一個進程狀態標志和不允許進入標志，這樣可以保證當兩個進程同時要求進入臨界區，只允許一個進程進入臨界區。 ~~~ // Pi進程 flag[i]=TURE; turn=j; while(flag[j]&&turn==j); critical section; flag[i]=FLASE; remainder section; // Pj進程 flag[j] =TRUE;turn=i; // 進入區 while(flag[i]&&turn==i); // 進入區 critical section; // 臨界區 flag[j]=FLASE; // 退出區 remainder section; // 剩余區 ~~~ 本算法的基本思想是算法一和算法三的結合。利用flag解決臨界資源的互斥訪問，而利用turn解決“饑餓”現象。 ### 硬件實現方法 本節對硬件實現的具體理解對后面的信號量的學習很有幫助。計算機提供了特殊的硬件指令，允許對一個字中的內容進行檢測和修正，或者是對兩個字的內容進行交換等。通過硬件支持實現臨界段問題的低級方法或稱為元方法。 ####1) 中斷屏蔽方法 當一個進程正在使用處理機執行它的臨界區代碼時，要防止其他進程再進入其臨界區訪問的最簡單方法是禁止一切中斷發生，或稱之為屏蔽中斷、關中斷。因為CPU只在發生中斷時引起進程切換，這樣屏蔽中斷就能保證當前運行進程將臨界區代碼順利地執行完，從而保證了互斥的正確實現，然后再執行開中斷。其典型模式為： … 關中斷; 臨界區; 開中斷; … 這種方法限制了處理機交替執行程序的能力，因此執行的效率將會明顯降低。對內核來說，當它執行更新變量或列表的幾條指令期間關中斷是很方便的，但將關中斷的權力交給用戶則很不明智，若一個進程關中斷之后不再開中斷，則系統可能會因此終止。 ####2) 硬件指令方法 TestAndSet指令：這條指令是原子操作，即執行該代碼時不允許被中斷。其功能是讀出指定標志后把該標志設置為真。指令的功能描述如下： ~~~ boolean TestAndSet(boolean *lock){ boolean old; old = *lock; *lock=true; return old; } ~~~ 可以為每個臨界資源設置一個共享布爾變量lock，表示資源的兩種狀態：true表示正被占用，初值為false。在進程訪問臨界資源之前，利用TestAndSet檢查和修改標志lock；若有進程在臨界區，則重復檢查，直到進程退出。利用該指令實現進程互斥的算法描述如下： ~~~ while TestAndSet (& 1 ock); // 進程的臨界區代碼段; lock=false; // 進程的其他代碼 ~~~ Swap指令：該指令的功能是交換兩個字節的內容。其功能描述如下。 ~~~ Swap(boolean *a, boolean *b){ boolean temp; Temp=*a; *a = *b; *b = temp; } ~~~ 注意：以上對TestAndSet和Swap指令的描述僅僅是功能實現，并非軟件實現定義，事實上它們是由硬件邏輯直接實現的，不會被中斷。 應為每個臨界資源設置了一個共享布爾變量lock，初值為false；在每個進程中再設置一個局部布爾變量key，用于與lock交換信息。在進入臨界區之前先利用Swap指令交換lock 與key的內容，然后檢查key的狀態；有進程在臨界區時，重復交換和檢查過程，直到進程退出。利用Swap指令實現進程互斥的算法描述如下： ~~~ key=true; while(key!=false) Swap(&lock, &key); // 進程的臨界區代碼段； lock=false; // 進程的其他代碼； ~~~ 硬件方法的優點：適用于任意數目的進程，不管是單處理機還是多處理機；簡單、容易驗證其正確性。可以支持進程內有多個臨界區，只需為每個臨界區設立一個布爾變量。 硬件方法的缺點：進程等待進入臨界區時要耗費處理機時間，不能實現讓權等待。從等待進程中隨機選擇一個進入臨界區，有的進程可能一直選不上，從而導致“饑餓”現象。