本文是對(duì)進(jìn)程同步機(jī)制的一個(gè)大總結(jié)(9000+字吐血總結(jié))，涵蓋面非常的全，包括了進(jìn)程同步的一些概念、軟件同步機(jī)制、硬件同步機(jī)制、信號(hào)量機(jī)制和管程機(jī)制，對(duì)每種機(jī)制結(jié)合代碼做了詳細(xì)的介紹，并且對(duì)瑣碎的知識(shí)點(diǎn)和概念解釋的非常清晰。

​在前面的博客中講述了進(jìn)程的狀態(tài)及其狀態(tài)的轉(zhuǎn)換，每種狀態(tài)的含義和轉(zhuǎn)換的原因。同樣我們也知道，在OS引入了進(jìn)程后，可以使系統(tǒng)中的多道程序可以并發(fā)的執(zhí)行，進(jìn)程的并發(fā)執(zhí)行一方面極大的提高了系統(tǒng)的資源利用率和吞吐量，但是另一方面卻使系統(tǒng)變得更加復(fù)雜，如果不能采取有效的措施，對(duì)多個(gè)進(jìn)程的并發(fā)執(zhí)行進(jìn)行妥善的管理，必然會(huì)因?yàn)檫@些進(jìn)程對(duì)系統(tǒng)資源的無(wú)序爭(zhēng)奪給系統(tǒng)造成混亂，致使每次的處理結(jié)果顯現(xiàn)出不可再現(xiàn)性。

​對(duì)于上面的問(wèn)題，大家想一想這么一個(gè)場(chǎng)景，如果我們?cè)谫I(mǎi)火車(chē)票(just for 舉栗子)時(shí)，沒(méi)有排隊(duì)這個(gè)機(jī)制，大家亂糟糟的圍在售票員旁邊，手里舉著錢(qián)大叫來(lái)一張到xxx的硬座、來(lái)張到xxx的臥鋪。。。咦，不寒而栗、可怕、腦殼痛。但是如果我們有序的排隊(duì)購(gòu)票，大家就都可以快速的買(mǎi)到自己想要的通往幸福的車(chē)票。

[[283320]]

​進(jìn)程同步機(jī)制就是這么一個(gè)保障OS中多個(gè)進(jìn)程能夠有條不紊的運(yùn)行的“規(guī)則”。本文中，我們將會(huì)詳細(xì)的介紹幾種進(jìn)程同步機(jī)制。(本章中所講的OS是單處理機(jī)系統(tǒng)，多處理機(jī)系統(tǒng)中的情況過(guò)于復(fù)雜，不利于理解)

1、進(jìn)程同步的幾個(gè)重要概念

​進(jìn)程同步機(jī)制的主要任務(wù)，是對(duì)多個(gè)相關(guān)的進(jìn)程在執(zhí)行次序上進(jìn)行協(xié)調(diào)，使并發(fā)執(zhí)行的諸多進(jìn)程之間能夠按照一定的規(guī)則共享系統(tǒng)資源，并能很好的相互合作，從而是程序之間的執(zhí)行具有可再現(xiàn)性。

​進(jìn)程間的兩種制約關(guān)系：

1. 間接相互制約(互斥)：因?yàn)檫M(jìn)程在并發(fā)執(zhí)行的時(shí)候共享臨界資源而形成的相互制約的關(guān)系，需要對(duì)臨界資源互斥地訪問(wèn);
2. 直接制約關(guān)系(同步)：多個(gè)進(jìn)程之間為完成同一任務(wù)而相互合作而形成的制約關(guān)系。

​臨界資源：只同一時(shí)刻只允許一個(gè)進(jìn)程可以訪問(wèn)的資源稱(chēng)之為臨界資源，諸進(jìn)程之間應(yīng)采取互斥方式，實(shí)現(xiàn)對(duì)臨界資源的共享。比如打印機(jī)、磁帶機(jī)等都是臨界資源。我們通過(guò)打印機(jī)來(lái)說(shuō)明為什么臨界資源同一時(shí)刻只允許一個(gè)進(jìn)程使用，假設(shè)同一時(shí)刻A、B進(jìn)程同時(shí)訪問(wèn)打印機(jī)，兩個(gè)進(jìn)程同時(shí)執(zhí)行打印任務(wù)，因?yàn)檫M(jìn)程的并發(fā)性，最后可能導(dǎo)致的就是打印機(jī)打出來(lái)的內(nèi)容就是混雜著兩方的文字，這樣得到的打印結(jié)果既不是A進(jìn)程想要的也不是B進(jìn)程想要的，只會(huì)造成資源的浪費(fèi)。

​臨界區(qū)：進(jìn)程中訪問(wèn)臨界資源的那段代碼。顯然若能保證諸進(jìn)程互斥的進(jìn)入自己的臨界區(qū)，便可實(shí)現(xiàn)進(jìn)程間對(duì)臨界資源的互斥訪問(wèn)。因?yàn)槊總€(gè)進(jìn)程每個(gè)進(jìn)程在進(jìn)入臨界區(qū)之前，應(yīng)先對(duì)欲訪問(wèn)的臨界資源的“大門(mén)”狀態(tài)進(jìn)行檢測(cè)(主要檢查該臨界資源是否有進(jìn)程正在訪問(wèn)，如果此時(shí)臨界資源未被訪問(wèn)，對(duì)應(yīng)的“大門(mén)”是敞開(kāi)的狀態(tài))，如果“大門(mén)”敞開(kāi)，進(jìn)程便可進(jìn)入臨界區(qū)，并將臨界區(qū)的“大門(mén)”關(guān)上;否則就表示有進(jìn)程在臨界區(qū)內(nèi)，當(dāng)前進(jìn)程無(wú)法進(jìn)入臨界區(qū)。

​指令：指令就是機(jī)器語(yǔ)言的一個(gè)語(yǔ)句，它是一組有意義的二進(jìn)制代碼。因?yàn)槭菣C(jī)器語(yǔ)言的一條指令，所以指令就可以等價(jià)于是原子性的，只有在執(zhí)行完一條指令后才會(huì)去響應(yīng)中斷(如果有的話)。

​原語(yǔ)：由若干條指令組成的，用戶完成一定功能的一個(gè)過(guò)程。原語(yǔ)操作的一個(gè)特點(diǎn)就是“原子操作”，因此原語(yǔ)在執(zhí)行的過(guò)程中不允許被中斷。原子操作在系統(tǒng)態(tài)下執(zhí)行，常駐內(nèi)存。

​同步機(jī)制應(yīng)遵循的規(guī)則：

1. 空閑讓進(jìn)：當(dāng)臨界區(qū)的“大門(mén)”敞開(kāi)時(shí)，應(yīng)當(dāng)允許一個(gè)請(qǐng)求的進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入臨界區(qū);
2. 忙則等待：當(dāng)臨界區(qū)的“大門(mén)”關(guān)閉時(shí)，因而其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證對(duì)臨界資源的互斥訪問(wèn);
3. 有限等待：對(duì)要求進(jìn)入臨界區(qū)的進(jìn)程，應(yīng)保證在有限的時(shí)間能進(jìn)入自己的臨界區(qū)，一面陷入“死等”狀態(tài);
4. 讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入“忙等”狀態(tài)。

​在這里解釋一下“死等”和“忙等”兩個(gè)狀態(tài)，因?yàn)檫@兩個(gè)狀態(tài)在我們看來(lái)似乎是沒(méi)有什么區(qū)別的，比如“死等”和“忙等”都是沒(méi)能進(jìn)入臨界區(qū)，那兩者的區(qū)別到底是什么呢?

1. 死等：首先對(duì)于“死等”的進(jìn)程來(lái)說(shuō)，這個(gè)進(jìn)程可能是處于阻塞狀態(tài)，等著別的進(jìn)程將其喚醒(Signal原語(yǔ))，但是喚醒原語(yǔ)一直無(wú)法執(zhí)行，對(duì)于阻塞的進(jìn)程來(lái)說(shuō)，就是一直處于“死等”(睡死了，沒(méi)有人喊你起床)的狀態(tài)了，并且在死等狀態(tài)，是沒(méi)有獲得處理機(jī)的;
2. 忙等：忙等狀態(tài)比較容易理解，處于忙等狀態(tài)的進(jìn)程是一直占有著處理機(jī)去不斷的判斷臨界區(qū)是否可以進(jìn)入，在此期間，進(jìn)程一直在運(yùn)行(忙死了都，但是都是白忙)，這也就是“忙等”狀態(tài)，有一點(diǎn)需要注意的是，在單處理機(jī)系統(tǒng)中，忙等是非常可怕的，因?yàn)樘幱诿Φ鹊倪M(jìn)程會(huì)一直霸占著處理機(jī)(不會(huì)去釋放處理機(jī)，發(fā)生了忙等的單CPU OS，無(wú)法執(zhí)行別的進(jìn)程，除非系統(tǒng)重啟，即忙等的狀態(tài)在單CPU系統(tǒng)中是無(wú)法被打破的)。

​其實(shí)不管是“忙等”還是“死等”，都是對(duì)OS有害的，都是應(yīng)該努力避免的。

​進(jìn)程的同步機(jī)制包含軟件同步機(jī)制、硬件同步機(jī)制、信號(hào)量機(jī)制、管程機(jī)制等，也就是這些機(jī)制，可以保證程序并發(fā)執(zhí)行時(shí)的可再現(xiàn)性。

2、軟件同步機(jī)制

​其實(shí)說(shuō)到使用軟件來(lái)實(shí)現(xiàn)同步機(jī)制，大家想到的最多的應(yīng)該就是Java多線程了，Java通過(guò)鎖、synchronized、信號(hào)量等機(jī)制實(shí)現(xiàn)了線程的同步，但是線程間是共享父進(jìn)程中的所有資源的，就比如多個(gè)職員坐在一間辦公室里，大家可以面對(duì)面的交談，這樣可以方便的解決共享資源的問(wèn)題;但是在線程之間(就像是分布在世界各地的多個(gè)辦公室)，如果需要共享系統(tǒng)資源時(shí)，進(jìn)程之間很難直接通過(guò)軟件來(lái)進(jìn)行交流，對(duì)系統(tǒng)資源的互斥共享就很麻煩了，需要借助硬件資源來(lái)完成同步了，需要在內(nèi)存中單獨(dú)使用一塊區(qū)域來(lái)保存進(jìn)程是否在臨界區(qū)內(nèi)的標(biāo)志。

​ 我們先來(lái)看下面一段代碼： 

//inside1、inside2是進(jìn)程P1和P2在內(nèi)存中保存的標(biāo)志，表示進(jìn)程是否在臨界區(qū)內(nèi)  
inside1 = false;  
inside2 = false;  
//進(jìn)程P1  
process P1  
begin  
while(inside2) ; //循環(huán)測(cè)試  
inside1 := true;  
臨界區(qū);  
inside1 := false;  
end;  
//進(jìn)程P2  
process P2  
begin  
while(inside1) ; //循環(huán)測(cè)試  
inside2 := true;  
臨界區(qū);  
inside2 := false;  
end; 

​代碼邏輯很清晰，就是進(jìn)程P1或者P2想進(jìn)入臨界區(qū)之前，先去判斷對(duì)方是否在臨界區(qū)內(nèi)，如果在的話，就一直循環(huán)等待，否則就進(jìn)入臨界區(qū)，然后“關(guān)門(mén)”(掛鎖)。第一眼看似乎是沒(méi)什么問(wèn)題，但是如果進(jìn)程在執(zhí)行期間，比如P1先執(zhí)行，在執(zhí)行掛鎖(inside1 = true)之前，發(fā)生了中斷，進(jìn)程P2也開(kāi)始了執(zhí)行，此錢(qián)P1的鎖還沒(méi)有掛上，因此進(jìn)程P2可以進(jìn)入臨界區(qū)，在臨界區(qū)內(nèi)執(zhí)行的時(shí)候，P2也發(fā)生了中斷，P1恢復(fù)執(zhí)行，因?yàn)橹耙呀?jīng)執(zhí)行過(guò)判斷是否可以進(jìn)入臨界區(qū)的代碼，因此此時(shí)同樣的可以進(jìn)入臨界區(qū)，在這種情況下，兩個(gè)進(jìn)程同時(shí)的進(jìn)入了臨界區(qū)，進(jìn)程的執(zhí)行就會(huì)出現(xiàn)錯(cuò)誤。

​雖然在上面的進(jìn)程P1和P2執(zhí)行的過(guò)程中發(fā)生了很多恰巧的事(小概率事件)，P1在掛鎖前中斷、P2在臨界區(qū)執(zhí)行時(shí)中斷、P1和P2進(jìn)程能在對(duì)方在中斷時(shí)搶占CPU，這幾個(gè)事件組合在一起，概率就更加的小了，但是仍然的是存在問(wèn)題的。

​這個(gè)時(shí)候你可能會(huì)想，我在判斷之前先掛上鎖呢，我們把代碼的順序調(diào)整一下，大家請(qǐng)看： 

//...  
//進(jìn)程P1  
process P1  
begin  
inside1 := true;  
while(inside2) ; //循環(huán)測(cè)試  
臨界區(qū);  
inside1 := false;  
end;  
//進(jìn)程P2  
process P2  
begin  
inside2 := true;  
while(inside1) ; //循環(huán)測(cè)試  
臨界區(qū);  
inside2 := false;  
end; 

​這樣的話，進(jìn)程P1、P2在并發(fā)執(zhí)行的時(shí)候就沒(méi)有問(wèn)題了么，我們來(lái)看這樣一種情況，P1先執(zhí)行，掛鎖成功，假設(shè)在成功之后，P1發(fā)生了中斷，進(jìn)程P2開(kāi)始執(zhí)行，此時(shí)P2同樣可以掛鎖，但是在判斷是否可以進(jìn)入臨界區(qū)時(shí)，則無(wú)法成功，會(huì)一直在循環(huán)中判斷，當(dāng)P1再次恢復(fù)執(zhí)行時(shí)，尷尬的事情發(fā)生了，P1也無(wú)法進(jìn)入臨界區(qū)了，因?yàn)镻2同樣把鎖給掛上了。

​上面是兩種軟件同步機(jī)制的實(shí)現(xiàn)，第一個(gè)是雙標(biāo)志法先檢查，第二個(gè)是雙標(biāo)志法后檢查，但是兩個(gè)方法都無(wú)法真正的解決進(jìn)程同步問(wèn)題。雙標(biāo)志法先檢查法可能會(huì)讓兩個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)，雙標(biāo)志法后檢查法可能會(huì)讓兩個(gè)進(jìn)程都無(wú)法進(jìn)入臨界區(qū)，形成死鎖問(wèn)題。

​雖然通過(guò)軟件方式也可以實(shí)現(xiàn)諸進(jìn)程互斥的進(jìn)入臨界區(qū)的問(wèn)題，比如Peterson算法，但是有一定的難度，并且存在很大的局限性，因而現(xiàn)在已經(jīng)很少使用了，下面我們來(lái)看下別的幾種方式。

3、硬件同步機(jī)制

​我們?cè)谲浖綑C(jī)制里講的兩個(gè)例子，都是在落鎖和判斷之間發(fā)生中斷，乃至導(dǎo)致無(wú)法實(shí)現(xiàn)互斥的進(jìn)入臨界區(qū)，那么，我們是不是可以在這個(gè)期間不允許發(fā)生中斷呢?這個(gè)就需要用到硬件了，下面我們就一起來(lái)看一下。

3.1 關(guān)中斷

​這個(gè)方法就非常之霸氣了，進(jìn)程在落鎖和判斷之間不是有可能會(huì)發(fā)生中斷么，那么我在開(kāi)始測(cè)試之前關(guān)閉中斷(OS內(nèi)核不響應(yīng)中斷信號(hào))，到測(cè)試并上鎖之后在打開(kāi)中斷。這樣可以保證兩個(gè)操作之間的連續(xù)性，保證臨界資源的互斥訪問(wèn)。

​但是關(guān)中斷也必然會(huì)存在許多缺點(diǎn)：1.濫用關(guān)中斷的權(quán)利可能導(dǎo)致嚴(yán)重后果;2.關(guān)中斷時(shí)間過(guò)長(zhǎng)會(huì)影響系統(tǒng)的并發(fā)性，直接的影響系統(tǒng)的資源利用率;3.關(guān)中斷無(wú)法適應(yīng)多CPU系統(tǒng)(多CPU系統(tǒng)不在本文的討論范圍內(nèi))

3.2 測(cè)試并建立(Test-and-Set, TS)指令

​我們使用關(guān)中斷來(lái)解決落鎖和判斷之間不允許響應(yīng)中斷，但是我們?nèi)绻堰@兩個(gè)執(zhí)行變成一條指令呢，這樣是不是就可以保證中斷不會(huì)再落鎖和判斷之間被響應(yīng)?

​我們可以借助一條硬件指令-----“測(cè)試并建立”指令TS(Test-and-Set)，來(lái)實(shí)現(xiàn)臨界資源的互斥訪問(wèn)。TS指令的一般性描述如下： 

//TS指令  
boolean TS(boolean *lock){  
if(*lock == false){  
*lock = true;  
return true;  
}else{  
return false;  
}  
}  
//內(nèi)存中保存的鎖的值  
boolean lock;  
lock = false; //臨界區(qū)可以進(jìn)入  
//進(jìn)程P1,P2,P3...Pn  
process Pi{  
//...  
while(!TS(&lock));//循環(huán)請(qǐng)求鎖  
臨界區(qū);  
lock = false;//解鎖，歸還臨界資源  
} 

​我們可以把TS指令看成上面的TS函數(shù)的執(zhí)行過(guò)程，其執(zhí)行過(guò)程是不可分割的，即是一條原語(yǔ)。當(dāng)lock的值為false時(shí)，表示臨界資源空閑，當(dāng)lock的值為true時(shí)，表示該資源正在被使用。

​使用TS指令來(lái)管理臨界區(qū)時(shí)，需要為每個(gè)臨界資源設(shè)置一個(gè)布爾變量lock。當(dāng)有進(jìn)程需要進(jìn)入臨界區(qū)時(shí)，需要先用TS指令測(cè)試臨界區(qū)對(duì)應(yīng)的那把“鎖”，如果返回true，臨界區(qū)空閑，可以進(jìn)入，并落鎖，阻止別的進(jìn)程再進(jìn)入臨界區(qū);如果TS返回false，則必須要循環(huán)請(qǐng)求，直到TS返回的值變?yōu)閠rue。

3.3 對(duì)換指令

​該指令也稱(chēng)為swap指令，用于交換兩個(gè)字的內(nèi)容，其處理過(guò)程描述如下： 

void swap(boolean *a, boolean *b){  
boolean tmp;  
tmp = *a;  
*a = *b;  
*b = tmp;  
}  
//內(nèi)存中保存的鎖的值  
boolean lock;  
lock = false; //臨界區(qū)可以進(jìn)入  
//進(jìn)程P1,P2,P3...Pn  
process Pi{  
//...  
boolean key = true;  
do{  
swap(&lock, &key);  
}while(key != false)//循環(huán)請(qǐng)求鎖  
臨界區(qū);  
lock = false;//解鎖，歸還臨界資源  
} 

​Swap指令和TS指令類(lèi)似，也需要為每個(gè)臨界資源設(shè)置一個(gè)布爾變量lock，不同的在進(jìn)程中使用一個(gè)局部變量Key字段去替換出lock中的值，通過(guò)判斷key的值就可以判斷臨界資源是否空閑。

​有一點(diǎn)需要注意的，因?yàn)樵Z(yǔ)是將多個(gè)指令合并成一個(gè)指令，在原語(yǔ)的執(zhí)行過(guò)程中也是不響應(yīng)中斷的，使之成為原子操作，這個(gè)期間，等于是屏蔽中斷，也就等價(jià)于我們講的第一種硬件方式—關(guān)中斷，因此原語(yǔ)操作的指令長(zhǎng)度應(yīng)該是短小精悍的，這樣才能保證系統(tǒng)的效率。

​利用上述的硬件指令能有效的實(shí)現(xiàn)進(jìn)程的互斥，但是當(dāng)資源忙碌時(shí)，其他訪問(wèn)進(jìn)程的必須不斷的進(jìn)程測(cè)試，處于一種“忙等”的狀態(tài)，違背了讓權(quán)等待的原則，造成處理機(jī)時(shí)間的浪費(fèi)，同時(shí)也很難將它們用于解決復(fù)雜的進(jìn)程問(wèn)題。

4、信號(hào)量機(jī)制

​信號(hào)量機(jī)制是1965年迪杰斯特拉(Edsger Wybe Dijkstra)提出的一種卓有成效的進(jìn)程同步工具。信號(hào)量機(jī)制在長(zhǎng)期的應(yīng)用中得到了很大的發(fā)展，從整型信號(hào)量經(jīng)記錄型信號(hào)量，進(jìn)而發(fā)展為“信號(hào)量集”機(jī)制，在目前來(lái)講，信號(hào)量。

​需要著重說(shuō)明的一點(diǎn)是：信號(hào)量除了初始化外，僅能被通過(guò)兩個(gè)標(biāo)準(zhǔn)的原子操作wait(S)和signal(S)來(lái)訪問(wèn)，這兩個(gè)操作也被稱(chēng)為P、V操作，這幾個(gè)操作都是原語(yǔ)操作。

4.1 整型信號(hào)量

​整型信號(hào)量是最開(kāi)始由迪杰斯特拉定義的，整型信號(hào)量也很簡(jiǎn)單，里面只有一個(gè)表示資源的數(shù)量的整形量，一般使用S符號(hào)來(lái)表示，整型信號(hào)量下的wait和signal操作可描述如下： 

//整型信號(hào)量定義  
int S;  
//P操作  
wait(S){  
while(S<=0);  
S--;  
}  
//V操作  
signal(S){  
S++;  
} 

​因?yàn)閣ait和signal操作是原子的，因此他們?cè)趫?zhí)行的過(guò)程中是不可被中斷的。也就是說(shuō)當(dāng)一個(gè)進(jìn)程在修改某個(gè)信號(hào)量時(shí)，沒(méi)有其他的進(jìn)程可以同時(shí)對(duì)該信號(hào)量進(jìn)行修改。

​需要注意的是，整型信號(hào)量的wait操作，只要是信號(hào)量S<=0，就會(huì)不斷的測(cè)試，讓進(jìn)程處于一種“忙等”的狀態(tài)，沒(méi)有遵循讓權(quán)等待的原則。還有就是，把信號(hào)量的初值置為1，表示只允許一個(gè)進(jìn)程訪問(wèn)臨界資源，此時(shí)的信號(hào)量就可以轉(zhuǎn)換為互斥信號(hào)量，用于完成進(jìn)程的互斥(對(duì)所有的信號(hào)量機(jī)制都是一樣)。

4.2 記錄型型號(hào)量

​為了解決整型信號(hào)量存在的忙等問(wèn)題，應(yīng)當(dāng)采取讓權(quán)等待原則。但是又會(huì)出現(xiàn)一個(gè)新的問(wèn)題，如果多個(gè)進(jìn)程并發(fā)請(qǐng)求訪問(wèn)臨界資源，除了第一個(gè)搶到了信號(hào)量外，其余的進(jìn)程都應(yīng)該釋放處理機(jī)，但是這些等待的進(jìn)程要如何保存呢?為此，除了wait操作需要遵循讓權(quán)等待原則，還需在信號(hào)量中增加一個(gè)進(jìn)程的鏈表指針list，用與鏈接上面描述的多個(gè)等待訪問(wèn)臨界資源的進(jìn)程。也因?yàn)橛涗浟说却倪M(jìn)程，這種信號(hào)量集之被稱(chēng)為記錄型信號(hào)量。

​記錄型信號(hào)量具體的描述以及對(duì)應(yīng)的wait和signal操作如下所示： 

//記錄型信號(hào)量定義  
typedef struct{  
int value;  
struct process_control_block *list;  
}semaphore;  
//P操作  
wait(semaphore *S){  
S->value--;  
if(s->value < 0) {  
block(S->list);  
}  
}  
//V操作  
signal(semaphore *S){  
S->value++;  
if(S->value <= 0){  
wakeup(S->list);  
}  
} 

​在記錄型型號(hào)量中，S->value的初值表示系統(tǒng)中某類(lèi)資源的數(shù)目;對(duì)它每次wait操作，意味進(jìn)程請(qǐng)求一個(gè)單位的該類(lèi)資源，使得系統(tǒng)中可分配的該類(lèi)資源數(shù)減少一個(gè)，因此描述為S->value–;當(dāng)S.value<0時(shí)，表示在執(zhí)行此次分配之前，系統(tǒng)中的該類(lèi)資源已經(jīng)全部分配完了，因此該訪問(wèn)進(jìn)程應(yīng)調(diào)用block原語(yǔ)進(jìn)行自我阻塞，放棄處理機(jī)并插入到等待進(jìn)程的隊(duì)列S->list中。我們?cè)賮?lái)分析下signal操作，首先釋放一個(gè)單位資源(S->value++)，然后判斷是否有進(jìn)程在等待申請(qǐng)信號(hào)量，如果有的話，就應(yīng)該調(diào)用wakeup原語(yǔ)從等待隊(duì)列(list所鏈接的進(jìn)程隊(duì)列)中喚醒一個(gè)進(jìn)程。

​通過(guò)上面的描述，我們來(lái)說(shuō)一下在記錄型型號(hào)量中，value值所代表的意義：1.value>0，此時(shí)表示系統(tǒng)中還剩余的該類(lèi)資源的數(shù)量;2.value=0，此時(shí)恰好處于一個(gè)平衡狀態(tài)，系統(tǒng)中的資源分配完了，同樣也沒(méi)有進(jìn)程在等待資源，即list隊(duì)列中是沒(méi)有等待進(jìn)程的;3.value<0，此時(shí)，value的絕對(duì)值表示有多少個(gè)進(jìn)程在等待申請(qǐng)信號(hào)量，也即是list隊(duì)列的長(zhǎng)度。并且P、V操作必須成對(duì)的出現(xiàn)，有一個(gè)P操作就必定有一個(gè)與之配對(duì)的V操作(當(dāng)為互斥操作時(shí)，它們同處于同一進(jìn)程當(dāng)為同步操作時(shí)，則不在同一進(jìn)程中出現(xiàn))。

4.3 AND型信號(hào)量

​AND型號(hào)量正如其名，其基本思想是：將進(jìn)程在整個(gè)運(yùn)行過(guò)程中需要的所有資源，一次性的全部分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。AND型號(hào)量可以滿足某些進(jìn)程需要申請(qǐng)多個(gè)資源后才可以執(zhí)行任務(wù)的場(chǎng)景，并且AND型信號(hào)量可以解決死鎖問(wèn)題，比如哲學(xué)家進(jìn)餐問(wèn)題中，一次給哲學(xué)家分配左右兩支筷子，那么就不會(huì)有哲學(xué)家會(huì)因?yàn)槌圆坏娇招姆鄱I死了。

​AND型信號(hào)量使用的還是記錄型信號(hào)量的數(shù)據(jù)結(jié)構(gòu)，下面是Swait操作和Ssignal操作(此處和下面的信號(hào)量集都用此符號(hào))： 

//記錄型信號(hào)量定義  
...  
//P操作  
Swait(S1, S2, ..., Sn){  
while(true){  
if(S1>=1&&...&&Sn>=1){  
for(i=1;i  
break;  
} else {  
將進(jìn)程插入到第一個(gè)無(wú)法滿足條件(即Si<1)的信號(hào)量對(duì)應(yīng)的等待隊(duì)列中,并且將程序計(jì)數(shù)器放置到  
Swait操作的開(kāi)始處;  
}  
}  
}  
//V操作  
Ssignal(S1, S2, ..., Sn){  
while(true){  
for(i=1;i  
Si++;  
將Si中的等待隊(duì)列中的所有進(jìn)程全部移除，插入到就緒隊(duì)列中;  
}  
break;  
}  
} 

​需要注意的就是，因?yàn)橐淮紊暾?qǐng)多個(gè)資源，所以在申請(qǐng)的過(guò)程中，如果因?yàn)槟囊活?lèi)資源不足而阻塞(請(qǐng)求N多個(gè)資源時(shí)第一個(gè)發(fā)現(xiàn)不滿足的資源，即資源數(shù)<1)，就要將進(jìn)程插入到對(duì)應(yīng)信號(hào)量的list中;與之對(duì)應(yīng)的喚醒操作也有所不同，不再是喚醒阻塞隊(duì)列中的某一個(gè)進(jìn)程，而是將等待隊(duì)列中的所有進(jìn)程全部移除，插入到就緒隊(duì)列中，讓這些進(jìn)程再次執(zhí)行一次資源請(qǐng)求操作(這里因?yàn)槭且淮握?qǐng)求多個(gè)資源，后面可能依舊有資源無(wú)法滿足進(jìn)程的需求)。

4.4 信號(hào)量集

​在前面講的信號(hào)量機(jī)制中，wait、signal操作僅能對(duì)信號(hào)量施以加1或者減1操作，當(dāng)一次需要N個(gè)單位的資源時(shí)，便要執(zhí)行N次的wait(S)操作，這顯然是低效的，并且會(huì)增大發(fā)生死鎖的概率(需要執(zhí)行N次，在這N次執(zhí)行的過(guò)程中可能會(huì)發(fā)生中斷，資源也可能會(huì)被別的進(jìn)程搶占)。此外，在某些情況下，為了確保系統(tǒng)的安全性，當(dāng)所申請(qǐng)的資源數(shù)量低于某一個(gè)下限時(shí)，就不予分配(保證地主家里有余糧)。

​為了滿足上述的兩個(gè)需求，信號(hào)量機(jī)制又升級(jí)了，在AND型信號(hào)量的基礎(chǔ)上進(jìn)行擴(kuò)充，對(duì)進(jìn)程所申請(qǐng)的所有資源，在一次P、V操作中完成申請(qǐng)或釋放。并且進(jìn)程對(duì)每類(lèi)信號(hào)量的測(cè)試值也不在是1，而是該資源的分配下限ti，也就是要求Si≥ti，否則不予分配。因此這里就不在給出具體的Swait和Ssignal的代碼了，而是給出函數(shù)聲明： 

Swait(S1, t1, d1, ... , Sn, tn, dn);  
Ssignal(S1, d1, ... , Sn, dn); 

​這里與記錄性型號(hào)量稍有不同的地方就是判斷每類(lèi)資源是否滿足需求時(shí)，判斷的條件由Si>=1變?yōu)镾i>=ti，并且分配資源由Si--變?yōu)镾i=Si-ti;與之對(duì)應(yīng)的Ssignal操作，不同的一點(diǎn)就是，一次可以歸還多個(gè)資源，相對(duì)應(yīng)的資源釋放代碼由Si++變?yōu)镾i=Si+ti。

​需要注意的是，因?yàn)锳ND型信號(hào)量和信號(hào)量集一次申請(qǐng)進(jìn)程執(zhí)行所需的全部資源，這樣的優(yōu)點(diǎn)就是簡(jiǎn)單、易行且安全，但是缺點(diǎn)也很明顯：1.資源被嚴(yán)重浪費(fèi)，嚴(yán)重的惡化了資源的利用率;2.使進(jìn)程經(jīng)常會(huì)發(fā)生饑餓現(xiàn)象(因?yàn)閭€(gè)別資源被占用的概率很大，會(huì)導(dǎo)致進(jìn)程因?yàn)樯暾?qǐng)不到所有資源遲遲得不到執(zhí)行)。

5.管程機(jī)制

​雖然信號(hào)量機(jī)制是一種既方便、又有效的進(jìn)程同步機(jī)制，但是每個(gè)訪問(wèn)臨界資源的進(jìn)程都需要自備同步操作wait(S)和signal(S)操作，這就使大量的同步操作分散在各個(gè)進(jìn)程中，不利于大家去集中的思考、抽象，使得程序設(shè)計(jì)的時(shí)候難度非常大，容易產(chǎn)生各種各樣的程序設(shè)計(jì)錯(cuò)誤。在這樣的情況下，便產(chǎn)生了一種新的進(jìn)程同步工具----管程(Monitors)。值得一提的是，管程也是迪杰斯特拉提出的。

​hansen對(duì)管程的定義如下：一個(gè)管程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)和能力為并發(fā)進(jìn)程所執(zhí)行(在該數(shù)據(jù)結(jié)構(gòu)上)的一組操作，這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù)。

​由上述的定義可知，管程有四部分組成：1.管程的名稱(chēng);2.共享數(shù)據(jù)結(jié)構(gòu)說(shuō)明;3.對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過(guò)程;4.初始化語(yǔ)句。下面我們來(lái)看下管程的語(yǔ)法描述： 

//管程的描述  
Monitor monitor_name {//管程名  
share variable declarations; //共享變量說(shuō)明  
cond cond_declarationas; //條件變量說(shuō)明  
public: //能被進(jìn)程調(diào)用的過(guò)程  
void P1(...){ //對(duì)數(shù)據(jù)結(jié)構(gòu)操作過(guò)程  
...  
}  
void P2(...){  
...  
}  
...  
void(...){  
...  
}  
...  
{  
initilization code; //初始化代碼  
}  
} 

​通過(guò)上面的代碼描述，你是不是覺(jué)得很熟悉!實(shí)際上，管程中包含了面向?qū)ο蟮乃枷耄鼘⒐蚕碣Y源、對(duì)共享資源的操作抽象成變量和方法，并與同步機(jī)制一同封裝在一個(gè)對(duì)象內(nèi)部，隱藏了實(shí)現(xiàn)細(xì)節(jié)。但是你所不知道的是，在管程出現(xiàn)的時(shí)候，還沒(méi)有面向?qū)ο蟪绦蛟O(shè)計(jì)，是不是很意外。

​封裝于管程內(nèi)部的數(shù)據(jù)結(jié)構(gòu)僅能被管程內(nèi)部的過(guò)程訪問(wèn)(類(lèi)似于Java中的私有變量)，如果想在管程外部訪問(wèn)管程內(nèi)部的數(shù)據(jù)結(jié)構(gòu)，就必須使用內(nèi)部過(guò)程(管程內(nèi)部的public修飾的方法，Java 類(lèi)中的公共方法)。所有的進(jìn)程想要訪問(wèn)臨界資源，都只能通過(guò)管程間接的訪問(wèn)，并且管程每次只允許一個(gè)進(jìn)程進(jìn)入管程，從而實(shí)現(xiàn)了進(jìn)程互斥。

​有一點(diǎn)需要說(shuō)明的是，管程為了實(shí)現(xiàn)更加復(fù)雜的進(jìn)程同步方式，增加了一個(gè)條件變量。通常會(huì)根據(jù)進(jìn)程被阻塞或者掛起的原因，設(shè)置不同的條件變量，每個(gè)條件變量保存一個(gè)鏈表指針，用與鏈接所有因?yàn)樵摋l件變量而阻塞或掛起的所有進(jìn)程，同時(shí)提供兩個(gè)P、V操作也可以表示為x.wait和x.signal，這兩個(gè)操作的含義如下：

1. x.wait：正在調(diào)用管程的進(jìn)程因x條件需要被阻塞或掛起，則調(diào)用x.wait將自己插入到x條件的等待隊(duì)列中，并釋放管程，直至x條件發(fā)生變化。
2. x.signal：正在調(diào)用管程的進(jìn)程因?yàn)閤條件發(fā)生了變化(資源使用完，歸還)，則調(diào)用x.signal，重新啟動(dòng)一個(gè)因x條件而阻塞或掛起的進(jìn)程，如果存在多個(gè)，則選擇其中的一個(gè)，如果沒(méi)有，繼續(xù)執(zhí)行原進(jìn)程，不產(chǎn)生任何喚醒操作。

​對(duì)于上面的操作，其實(shí)是有些問(wèn)題的，我們?cè)O(shè)想一下，如果進(jìn)程P1因x條件處于阻塞狀態(tài)，那么當(dāng)進(jìn)程P2執(zhí)行了x.signal操作喚醒P1后，進(jìn)程P1和P2此時(shí)同時(shí)處于管程中了，這是不被允許的，那么如何確定哪個(gè)執(zhí)行哪個(gè)等待?這個(gè)問(wèn)題也很簡(jiǎn)單，可采用下面的兩種方式之一進(jìn)行處理：

1. P2等待，直至P1離開(kāi)管程或者等待另一個(gè)條件;
2. P1等待，直至P2離開(kāi)管程或者等待另一個(gè)條件。

​采用哪種處理方式，也存在很多爭(zhēng)論。Hoare采用了第一種處理方式，而Hansen采用了兩者的折中，它規(guī)定管程中的所有過(guò)程執(zhí)行的signal操作是過(guò)程體的最后一個(gè)操作，于是，進(jìn)程P2執(zhí)行完signal操作后立即退出管程，因此進(jìn)程P1馬上被恢復(fù)執(zhí)行。

​但是hansen的這種折中的辦法，規(guī)定死了釋放的時(shí)機(jī)，增加了程序設(shè)計(jì)的難度。因此現(xiàn)在的管程普遍采用Hoare的方式，也被稱(chēng)為霍爾管程。霍爾管程相比于管程、漢森管程，他的一個(gè)更大的優(yōu)勢(shì)是可以基于PV操作原語(yǔ)來(lái)實(shí)現(xiàn)，換一句話說(shuō)就是，wait和signal可以是程序過(guò)程而不需要是原語(yǔ)實(shí)現(xiàn)(可以使用語(yǔ)言機(jī)制實(shí)現(xiàn)霍爾管程)。這個(gè)就很厲害了，霍爾管程可以基于操作系統(tǒng)的程序庫(kù)或者是高級(jí)程序設(shè)計(jì)語(yǔ)言，在基礎(chǔ)的P、V操作原語(yǔ)上實(shí)現(xiàn)wait和signal操作，而不用擴(kuò)展操作系統(tǒng)的內(nèi)核。

​管程的示意圖如下，從圖中我們可以看到，每個(gè)條件變量都有一個(gè)對(duì)應(yīng)的等待隊(duì)列，除了等待調(diào)用管程的進(jìn)程隊(duì)列外，還有一個(gè)緊急隊(duì)列(優(yōu)先級(jí)高，由進(jìn)程調(diào)用signal操作后插入)，對(duì)于具體的操作，我們可以結(jié)合霍爾管程中條件變量中的wait、signal操作來(lái)講。

​下面是霍爾管程的條件變量上的wait操作和signal操作的描述： 

//霍爾管程使用的信號(hào)量定義  
//semaphore為本文之前定義的記錄型信號(hào)量  
typedef struct{  
semaphore mutex; //用與管程調(diào)用的互斥信號(hào)量  
semaphore next; //發(fā)出signal的進(jìn)程掛起自己的信號(hào)量，信號(hào)量中記錄著等待調(diào)用管程的進(jìn)程  
int next_count; //在next上等待的進(jìn)程數(shù)  
}interf;  
//霍爾管程中的條件變量  
typedef struct{  
semaphore x_sem; //與資源相關(guān)的信號(hào)量  
int x_count; //在x_sem上等待的進(jìn)程數(shù)  
}cond;  
//條件變量對(duì)應(yīng)的wait操作  
wait(cond declar, interf IM){  
declar->x_count++; //在條件變量declar上等待的進(jìn)程數(shù)量加1  
if(IM->next_count > 0){ //判斷是否有進(jìn)程在高優(yōu)先級(jí)隊(duì)列中  
V(IM->next); //喚醒因調(diào)用signal操作的進(jìn)程  
} else {  
V(IM->mutex); //沒(méi)有的話，喚醒一個(gè)等待進(jìn)入管程的進(jìn)程  
}  
P(declar->x_sem); //釋放資源后，立即把自己掛起  
declar->xcount--; //恢復(fù)執(zhí)行后，重新開(kāi)始執(zhí)行，退出管程，條件變量declar等待的進(jìn)程數(shù)量減1  
}  
//條件變量對(duì)應(yīng)的signal操作  
signal(cond declar, interf IM){  
if(declar->x_count > 0){ //判斷是否有等待條件變量的進(jìn)程  
IM->next_count++; //掛起自己后，因?yàn)檎{(diào)用signal掛起自己的進(jìn)程數(shù)量加1  
V(declar->x_sem); //喚醒一個(gè)等待條件變量的進(jìn)程  
P(IM->next); //釋放資源后，立即把自己掛起,進(jìn)入高優(yōu)先級(jí)隊(duì)列  
IM->next_count--; //恢復(fù)執(zhí)行后，等待調(diào)用的管程的進(jìn)程數(shù)量減1  
}  
} 

​我們看上面的代碼，此時(shí)的wait操作和signal操作與P、V原語(yǔ)是有區(qū)別的，wait和signal是在P、V的基礎(chǔ)上實(shí)現(xiàn)的。首先我們來(lái)看下wait操作，喚醒進(jìn)程(高優(yōu)先級(jí)隊(duì)列或者是等待調(diào)用管程的隊(duì)列)后，立即將自己掛起，并將自己插入到對(duì)應(yīng)的條件變量的等待隊(duì)列中(上圖中左上方的隊(duì)列)，當(dāng)被喚醒再次執(zhí)行時(shí)，將對(duì)應(yīng)的等待數(shù)量減1。我們?cè)趤?lái)看下signal操作，首先判斷是否有等待條件變量的進(jìn)程，如果沒(méi)有的話，就可以什么都不用執(zhí)行;如果有進(jìn)程在條件變量的等待隊(duì)列中，則從隊(duì)列中喚醒一個(gè)，并掛起自己，插入到緊急隊(duì)列中。

霍爾管程中的wait、signal操作比較抽象，可以結(jié)合圖片查看，可以幫助理解。

6.總結(jié)

​本文主要講了OS中為了解決進(jìn)程同步問(wèn)題才采取的措施，進(jìn)程同步機(jī)制也是經(jīng)過(guò)逐步的發(fā)展，慢慢的變得完善，可以滿足復(fù)雜的并發(fā)程序設(shè)計(jì)，本文的內(nèi)容主要是偏理論，也結(jié)合了代碼來(lái)講解各個(gè)操作，能幫助大家理解。通過(guò)本文的學(xué)習(xí)，希望可以讓你在并發(fā)程序設(shè)計(jì)上能獲得理論的依據(jù)，因?yàn)槲覀冏龅母嗟膽?yīng)該是多線程編程，如果你接觸過(guò)并發(fā)編程，我覺(jué)得本文里的許多內(nèi)容能引起你的共鳴。