目錄
一、臨界區的引出
二、臨界區的軟體實作
1.輪換法
2.标記法
3.Lamport面包店算法
三、臨界區的硬體實作
總結
一、臨界區的引出
從上一篇文章中，我們了解到了信号量的概念。信号量的數值表達的語義用來控制程序的走和停，是以，信号量的數值是非常重要的，信号量的數值吧必須和信号量的語義相一緻，才能正确地決定程序的同步。比如信号量的數值為0，但此時實際上有一個程序阻塞在該信号量，那麼即使對該信号量執行V操作也不會喚醒被阻塞的程序。
但是信号量是一個會被多個程序操作的共享變量，各個并發程序競争使用CPU會導緻各種各樣的排程問題，部分排程順序可能會導緻信号量出現語義錯誤。
以生産者——消費者問題為例，初始情況empty=-1，P1、P2都應當阻塞在該信号量上，empty=-3，但是由于P2在P1完成empty=P1.register之前，就開始對empty進行操作，導緻最後empty=-2，出現了語義錯誤。
為了對信号量進行保護，就要使一個程序在對信号量進行修改操作時，其他的程序必須處于等待狀态，當該程序修改完成以後，才能接着對信号量進行操作。即程序對信号量的修改要麼是一點不做，要麼是全部做完，對信号量的修改必須是一次原子操作。
那麼引入什麼樣的機制可以使程序對信号量的操作變成原子操作？
在軟體系統中，無論增加什麼機制，都表現為增加了代碼，是以對信号量的保護就是在對信号量操作代碼的基礎上“包裹”其他代碼來讓信号量的修改操作成為原子操作。
如圖所示，當P1進入臨界區修改信号量數值的時候，即empty--，P2就不能進入臨界區執行empty--了。
臨界區就是程序中一段代碼，這段代碼與其他相關程序中的相關代碼是對應的，一次隻允許一個程序進入，就是互斥進入。一旦進入這段代碼，作業系統的狀态就發生了改變，不能随意地切換程序，而在執行程序中的其他代碼時是可以切換的，是以這一段代碼稱為臨界區。
了解了臨界區的概念，我們發現問題就轉變為如何将修改信号量的代碼轉變為臨界區代碼。那麼就需要在修改代碼的前後加上進入區代碼和退出區代碼，如何實作進入區和退出區就成了核心問題。
二、臨界區的軟體實作
1.輪換法
臨界區要求互斥進入，那麼可以采用輪換法。
如上圖所示，P0和P1同時隻能有一個進入臨界區去修改信号量的大小。但也存在問題，P0隻有當turn=0的時候才能進入臨界區，假設P0進入過一次臨界區後，turn=1，那麼隻有當）P1執行一次後，turn才會重新變成0，那如果P1不執行的話P0也始終無法得到執行。
是以，臨界區的實作不僅僅要考慮互斥進入一個因素：
1.互斥進入。一次隻允許一個程序進入臨界區。
2.有空讓進。如果沒有程序在臨界區執行，并且有程序請求進入臨界區，那麼就應當讓請求程序的一個進入臨界區，防止資源死鎖。
3.有限等待。任何人一個程序在提出進入臨界區的請求後，在等待有限的時間後就能夠進入臨界區。
2.标記法
标記法即給每一程序加一個标記flag[i]，當該程序要進入臨界區時，就把flag置1，再掃描是否有其他程序想要進入臨界區，即其他程序的flag為true，如果有的話就進入自循環等待。
标記法雖然能做到互斥進入，但當P0和P1都想進入臨界區，flag都為true的時候，兩個程序都會進行自循環，這就無法滿足有空讓進的原則。
對标記法進行改進：
1.用标記法判斷程序是否想進入臨界區；
2.如果程序想進入臨界區，就用輪換法給出一個明确的優先順序；
3.将輪換法和标記法結合在一起，這就是Peterson算法。
如果P0和P1都進入了臨界區，說明flag[0]=flag[1]=ture，而turn=1=0，這是不可能的，是以滿足互斥進入；如果P0想進入臨界區而P1不想，則flag[0]=1、flag[1]=0，那麼P0就不滿足自循環條件，會進行信号量的修改，而如果兩個程序都想進入臨界區，那麼輪到的那個程序就能夠進入臨界區，另一個自循環等待，滿足有空讓進；當一個程序進入臨界區以後，執行完成後就會将flag置0，那麼在等待的另一個程序就可以不再進入自循環，轉而修改信号量數值，滿足有限等待原則。
3.Lamport面包店算法
Peterson算法雖然能實作對臨界區的保護，但是它隻能處理兩個程序的臨界區，是以就誕生Lamport面包店算法來對多程序臨界區進行保護。
該算法将在面包店購買面包的例子與對臨界區的保護進行類比，面包店同時隻能接待一位顧客買單，其餘顧客處在隊列中等待買單。面包店會給每一個進店的顧客一個号碼，顧客按照由小到大的順序進行買單，而買完單的顧客的序号就變成了0，想要再次購買就必須重新取号。
do
{
choosing[i] = true;
number[i] = maxnumber[0],number[1],···,number[n-1] + 1;//号碼選取
choosing[i] = false;
for(j = 0; j < n; j++)
{
while(choosing[j]);
while((number[j] != 0) && (number[j],j) < (number[i],i));
}
···//臨界區代碼
number[i] = 0;
}while(true);
1.由于每一個程序都有自己的序号，相同序号的程序再按照名字順序排列，選出進入臨界區的程序一定是唯一的；
2.沒有競争時想要進入的程序直接進入，由競争的時候一定會選出一個程序進入臨界區；
3.一旦程序獲得一個号碼後，後面的程序獲得的号碼一定會大于這個号碼，程序的等待時間也是有限的。
三、臨界區的硬體實作
Lamport面包店算法雖然實作了多程序的臨界區通路問題，但是效率比較低下，号碼選取、号碼維護、号碼判斷的代價都不小，并且選取的号碼數值不斷變大，可能會發生溢出的情況。既然軟體實作可能會存在一定問題，那麼就考慮使用硬體方法實作多程序對臨界區的通路。
對于隻有一個CPU的計算機，當P0進入臨界區之後，意味着CPU正在執行P0臨界區中的代碼，而當P1進入臨界區後，CPU轉而去執行P1臨界區中的代碼，那麼CPU在這個過程中進行了程序的排程和切換。而對于單CPU計算機來說，如果能阻斷排程，就不會發生在CPU在執行一個程序臨界區代碼的時候切換去執行其他程序，進入另一個臨界區的情況。
程序切換需要調用schedule()函數，而調用schedule()函數需要進入核心，而進入核心需要中斷，如果能禁止中斷就可以防止CPU的切換。
cli()的工作原理是将CPU标志寄存器中的中斷允許标志寄存位IF設定為0，這樣CPU就不會在執行完指令後去檢查并進行中斷了。但對于多CPU計算機而言，其他的CPU仍然可以執行其他的想要進入臨界區的程序。
換一種思路，這個問題有點像生産者——消費者問題中為了保證共享緩存區中信号量語義的正确性，一次隻能有一個程序進行通路，我們用一個互斥信号量mutex=1來實作互斥通路的控制，那麼是否可以用這個信号量來保護臨界區了？
但是臨界區本身是用來保證信号量操作的原子性，又要在臨界區中使用信号量，mutex=1本身作為一個信号量就需要其他手段來保證其操作的原子性，這是一個無法實作的循環問題。
那麼我們可以通過硬體的方式來實作mutex操作的原子性，再用mutex實作臨界區，再用臨界區去保證其他任意信号量操作的原子性。
保護臨界區的互斥信号量隻有0和1兩個數值，這個信号量的P、V操作簡單規整，可以用硬體方法實作，而由于信号量隻有兩個數值，很像一個鎖，是以常被命名為lock。
lock=0時，說明沒有上鎖，程序可以進入到臨界區，同時将lock修改為1，這個指令要做成一條硬體指令，一條硬體指令的執行是不會被打斷的，是以實作了指令的原子操作。如果lock=1，則程序自旋等待。計算機中有一條硬體指令：TestAndSet。這條指令的操作數存放一個布爾變量的位址，如果該記憶體中的變量為false，指令會傳回false，并将記憶體中的變量置為true，如果變量為true，則傳回true。
function TestAndSet(boolean &lock)
{
boolean initial = *lock;
*lock = true;
return initial;
}
有了這樣一條指令來處理lock，我們就可以利用lock來保護臨界區。
一旦有程序在lock=false的情況下跳過循環進入臨界區，lock就被置為true了，其他程序就處于自旋狀态，而當該程序完成信号量操作後，lock=false，其他處于自旋狀态的程序才能進入臨界區。
即使多個程序執行在多個CPU上，由于大家共享記憶體，TestAndSet指令操作的lock變量是相同的，對同一個lock變量的TestAndSet可以保證隻有一個程序傳回false，其他程序傳回true。
總結
1.介紹了臨界區的概念；
2.說明了臨界區使用軟體實作的方法；
3.介紹了用硬體方法實作臨界區并對信号量進行保護。