首先我們要知道進(jìn)程同步分哪兩種
同步：進(jìn)程A向B提供數(shù)據(jù)，當(dāng)輸入緩沖空時(shí)，B不能得到數(shù)據(jù)而阻塞；反之，當(dāng)緩沖滿時(shí)，A無法寫入而阻塞。
互斥：A、B共享打印機(jī)，若A申請打印時(shí)，打印機(jī)已分配給B，則A只能阻塞，等B釋放后再改為就緒。
進(jìn)程同步有四個(gè)原則，為了理解這四個(gè)原則，我們首先要了解臨界資源的概念
臨界資源：一次僅允許一個(gè)進(jìn)程使用的資源，系統(tǒng)中許多硬件如打印機(jī)等，諸多進(jìn)程之間只能用互斥的方式進(jìn)行訪問。
同步機(jī)制四原則
1.空閑讓進(jìn)：臨界區(qū)空閑時(shí)，可以允許一個(gè)請求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入臨界區(qū)。
2.忙則等待：當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時(shí)，其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待。
3.有限等待：對請求訪問的進(jìn)程，應(yīng)保證能在有限時(shí)間內(nèi)進(jìn)入臨界區(qū)。
4.讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入臨界區(qū)時(shí)，應(yīng)立即釋放處理器，防止進(jìn)程忙等待。
舉一個(gè)例子來形容這四個(gè)原則：當(dāng)我們?nèi)ゲ蛷d吃飯時(shí)，餐廳里的座位就相當(dāng)于臨界區(qū)，我們每一個(gè)人相當(dāng)于訪問臨界區(qū)的代碼，當(dāng)餐廳有空桌時(shí)，我們可以進(jìn)入，也就是空閑讓進(jìn)。當(dāng)餐廳沒有空桌時(shí)，我們必須等待，也就是忙則等待。當(dāng)沒有空桌的時(shí)候服務(wù)員會給我們一個(gè)號碼，讓我們在一邊等著，而不是時(shí)刻去問服務(wù)員有沒有空桌，這就是讓權(quán)等待。每次發(fā)號碼的時(shí)候服務(wù)員都會估計(jì)一下排隊(duì)時(shí)間，確保每一個(gè)排隊(duì)的人都能在有限的時(shí)間內(nèi)吃到飯（假設(shè)24小時(shí)營業(yè)），這個(gè)也就是有限等待。
接下來我們就要了解計(jì)算機(jī)是如何實(shí)現(xiàn)臨界區(qū)的互斥方法了，分軟件實(shí)現(xiàn)和硬件實(shí)現(xiàn)
軟件實(shí)現(xiàn)方法
算法一、單標(biāo)志法
設(shè)置一個(gè)公用變量turn(相當(dāng)于鑰匙)，最開始的時(shí)候P1有鑰匙，進(jìn)入的時(shí)候拿鑰匙開門，訪問臨界資源，訪問結(jié)束后把鑰匙給P0。P0再拿鑰匙進(jìn)去，就實(shí)現(xiàn)了交替進(jìn)入。
但是問題在于，當(dāng)P0把鑰匙給P1后，如果P1不進(jìn)去，這時(shí)候如果P0想再進(jìn)去，手里就沒有鑰匙，無法進(jìn)入，違背空閑讓進(jìn)原則。
代碼實(shí)現(xiàn)
P0進(jìn)程：? ? ? ? ? ? ? ? ?P1進(jìn)程：
while(turn!=0);? ? ? ? ?while(turn!=1) ???? //進(jìn)入?yún)^(qū)
訪問臨界區(qū);? ? ? ? ? ? ?訪問臨界區(qū);? ? ? ? ?//臨界區(qū)
turn=1;? ? ? ? ? ? ? ? ? ? ?turn=0;? ? ? ? ? ? ?????//退出區(qū)
算法二、雙標(biāo)志先檢查
設(shè)置一個(gè)數(shù)據(jù)flag[i]，表示第i個(gè)元素是否正在訪問臨界區(qū)。
在每一個(gè)進(jìn)程訪問臨界資源之前，先查看一下臨界資源是否正在被訪問，若正在被訪問，則等待；否則，進(jìn)程進(jìn)入臨界區(qū)，之后修改flag[i]，表明其正在訪問臨界區(qū)。
但是問題在于，當(dāng)Pi和Pj同時(shí)訪問臨界區(qū)時(shí)，因?yàn)槲覀冎挥性谶M(jìn)入臨界區(qū)后才會修改flag，所以同一時(shí)刻，可能會同時(shí)進(jìn)入臨界區(qū)，違背忙則等待原則。
完整代碼
Pi進(jìn)程：????????????????Pj進(jìn)程：
while(flag[j])? ? ? ? ? ?while(flag[i])
;? ? ? ? ? ? ? ? ? ? ? ? ? ? ?; ???????????????????????? //判斷是否有進(jìn)程在臨界區(qū)
flag[i]=TRUE;? ? ? ? flag[j]=TRUE; ????//修改flag
訪問臨界區(qū);? ? ? ? ? 訪問臨界區(qū); ????????//臨界區(qū)
flag[i]=FALSE;? ? ? ?flag[j]=FALSE; ????//退出區(qū)
算法三、雙標(biāo)志法后檢查
與算法二不同，算法三先修改flag[i]（表示想進(jìn)去的意圖），表明其想要進(jìn)去（并沒有進(jìn)去），然后檢測對方是否想要進(jìn)去，如果對方?jīng)]有想要進(jìn)去，則進(jìn)入，反之，則等待。
這個(gè)問題就很顯而易見了，當(dāng)兩個(gè)進(jìn)程都想進(jìn)入，同時(shí)都修改了各自的flag[i]，這樣兩個(gè)人都會陷入等待，導(dǎo)致了饑餓狀態(tài)。
完整代碼
Pi進(jìn)程： ???????????????? Pj進(jìn)程：
flag[i]=TRUE;? ? ? ? ?flag[j]=TRUE;? ? ? ? //修改flag
while(flag[j])? ? ? ? ? ? while(flag[i])
;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?; ???????????????????????? //判斷是否有進(jìn)程在臨界區(qū)
訪問臨界區(qū);? ? ? ? ? ? ?訪問臨界區(qū); ????????//臨界區(qū)
flag[i]=FALSE;? ? ? ? ?flag[j]=FALSE;? ? ? //退出區(qū)
這里涉及到了饑餓問題，就先講一下饑餓和死鎖的概念了
饑餓：一個(gè)就緒進(jìn)程所申請的資源總是被優(yōu)先于自己的其他進(jìn)程所占有，而始終不能被調(diào)度執(zhí)行的狀態(tài)，稱為”饑餓”
死鎖：有可能出現(xiàn)某些進(jìn)程相互之間都在等在對方的資源且都無法運(yùn)行的局面，即在進(jìn)程集合中的這些進(jìn)程處于永遠(yuǎn)的阻塞狀態(tài)，稱為”死鎖”
算法四、Peterson’s Algorithm
我們綜合前面三種方法，設(shè)置變量turn(鑰匙)，flag[i]（表示想進(jìn)去的意圖），當(dāng)一個(gè)進(jìn)程到來時(shí)，將鑰匙放到另外一個(gè)人的口袋里，同時(shí)修改flag[i]，表面自身想要進(jìn)入，如果同時(shí)滿足，鑰匙在對方口袋里，并且對方也想要進(jìn)去，那么就在外面等待。如果有一項(xiàng)不滿足（鑰匙在我口袋里或者對方不想進(jìn)去或者兩者都具備）那么我就可以進(jìn)去。
也就是用flag解決互斥問題，用turn解決饑餓問題。
思考一下：假如兩個(gè)進(jìn)程同時(shí)到達(dá)，兩個(gè)人都有進(jìn)去的意圖，但是無論如何，鑰匙最終都會落在一個(gè)人手里，最后想進(jìn)去并且擁有鑰匙的人就進(jìn)去了，不會導(dǎo)致饑餓。進(jìn)去的人出來后，修改flag[i]，表面其自身并不想進(jìn)去，則另一個(gè)進(jìn)行跳出循環(huán)，進(jìn)入臨界區(qū)（雖然鑰匙不在身上:D）
具體代碼
Pi進(jìn)程：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Pj進(jìn)程：
flag[i]=TURE;? ? ? ? ? ? ? ? ? ? ? ?turn=j;flag[j]=ture;turn=i;????????//修改flag，改變turn
while(flag[j]&&turn==j)? ? ? ? ? while(flag[i]&&turn=i)
;????????????????????????????????????????????;????????????????????????????????????????????//滿足兩個(gè)條件則循環(huán)
訪問臨界區(qū);? ? ? ? ? ? ? ? ? ? ? ? ? ?訪問臨界區(qū);? ? ? ? ? ? ? ? ? ? ? ? ?//臨界區(qū)
flag[i]-FALSE;????????????????????????flag[i]=FLASE;????????????????????//退出區(qū)
接下來是硬件實(shí)現(xiàn)方法
方法一、中斷屏蔽法（效率很低，不好）
進(jìn)程在進(jìn)入臨界區(qū)之前先執(zhí)行”關(guān)中斷”質(zhì)量來屏蔽掉所有中斷。進(jìn)程完成臨界區(qū)的任務(wù)后，在執(zhí)行”開中斷”執(zhí)行將中斷打開。
方法二、硬件指令方法（TestAndSet指令）
為每個(gè)臨界資源設(shè)置一個(gè)s，看成一把鎖。
若s值為0(開鎖狀態(tài))，則表示每頁進(jìn)程訪問該鎖對應(yīng)的臨界資源;
若s的值為1(關(guān)鎖狀態(tài))，則表示該鎖對應(yīng)的臨界資源已被某個(gè)進(jìn)程占用。
具體代碼
while TS (&lock) ????????//只要處在關(guān)鎖狀態(tài)就不斷循環(huán)等待，違反讓權(quán)等待
;
訪問臨界區(qū);? ? ? ? ? ? ? ? ?//臨界區(qū)
lock=FALSE;? ? ? ? ? ? ? ? //退出區(qū)
方法三、swap指令
設(shè)置一個(gè)全局變量lock，lock=0時(shí)，空閑，反之，有進(jìn)程。
每個(gè)進(jìn)程設(shè)置一個(gè)局部變量key，只有當(dāng)lock==0并且key==1時(shí)，進(jìn)程才能進(jìn)入臨界區(qū)。
進(jìn)入臨界區(qū)后，執(zhí)行swap指令，lock=1,key=0。
退出臨界區(qū)時(shí)，將lock的執(zhí)行置為0。
具體代碼
key = true; //初始化key
do{
swqp(&lock,&key);
}while(&key); ???????? ???????? //執(zhí)行完了swap之后才能進(jìn)入
進(jìn)入臨界區(qū);
lock = FALSE;? ? ? ? ? ? ? ? ? //退出的時(shí)候?qū)ock置為0
