一，進(jìn)程同步的幾種方式

1、信號(hào)量

用于進(jìn)程間傳遞信號(hào)的一個(gè)整數(shù)值。在信號(hào)量上只有三種操作可以進(jìn)行：初始化，P操作和V操作，這三種操作都是原子操作。

P操作(遞減操作)可以用于阻塞一個(gè)進(jìn)程，V操作(增加操作)可以用于解除阻塞一個(gè)進(jìn)程。

基本原理是兩個(gè)或多個(gè)進(jìn)程可以通過(guò)簡(jiǎn)單的信號(hào)進(jìn)行合作，一個(gè)進(jìn)程可以被迫在某一位置停止，直到它接收到一個(gè)特定的信號(hào)。該信號(hào)即為信號(hào)量s。

為通過(guò)信號(hào)量s傳送信號(hào)，進(jìn)程可執(zhí)行原語(yǔ)semSignal(s);為通過(guò)信號(hào)量s接收信號(hào)，進(jìn)程可執(zhí)行原語(yǔ)semWait(s);如果相應(yīng)的信號(hào)仍然沒(méi)有發(fā)送，則進(jìn)程會(huì)被阻塞，直到發(fā)送完為止。

可把信號(hào)量視為一個(gè)具有整數(shù)值的變量，在它之上定義三個(gè)操作：

• 一個(gè)信號(hào)量可以初始化為非負(fù)數(shù)

• semWait操作使信號(hào)量s減1.若值為負(fù)數(shù)，則執(zhí)行semWait的進(jìn)程被阻塞。否則進(jìn)程繼續(xù)執(zhí)行。

• semSignal操作使信號(hào)量加1，若值大于或等于零，則被semWait操作阻塞的進(jìn)程被解除阻塞。

2、管程

管程是由一個(gè)或多個(gè)過(guò)程、一個(gè)初始化序列和局部數(shù)據(jù)組成的軟件模塊，其主要特點(diǎn)如下：

• 局部數(shù)據(jù)變量只能被管程的過(guò)程訪問(wèn)，任何外部過(guò)程都不能訪問(wèn)。

• 一個(gè)進(jìn)程通過(guò)調(diào)用管程的一個(gè)過(guò)程進(jìn)入管程。

• 在任何時(shí)候，只能有一個(gè)進(jìn)程在管程中執(zhí)行，調(diào)用管程的任何其他進(jìn)程都被阻塞，以等待管程可用。

管程通過(guò)使用條件變量提供對(duì)同步的支持，這些條件變量包含在管程中，并且只有在管程中才能被訪問(wèn)。有兩個(gè)函數(shù)可以操作條件變量：

• cwait(c)：調(diào)用進(jìn)程的執(zhí)行在條件c上阻塞，管程現(xiàn)在可被另一個(gè)進(jìn)程使用。

• csignal(c)：恢復(fù)執(zhí)行在cwait之后因?yàn)槟承l件而阻塞的進(jìn)程。如果有多個(gè)這樣的進(jìn)程，選擇其中一個(gè)；如果沒(méi)有這樣的進(jìn)程，什么以不做。

3、消息傳遞

消息傳遞的實(shí)際功能以一對(duì)原語(yǔ)的形式提供：

• send(destination,message)

• receive(source,message)

這是進(jìn)程間進(jìn)程消息傳遞所需要的最小操作集。

一個(gè)進(jìn)程以消息的形式給另一個(gè)指定的目標(biāo)進(jìn)程發(fā)送消息；

進(jìn)程通過(guò)執(zhí)行receive原語(yǔ)接收消息，receive原語(yǔ)中指明發(fā)送消息的源進(jìn)程和消息。

二、進(jìn)程互斥

由于進(jìn)程具有獨(dú)立性和異步性等并發(fā)特征，計(jì)算機(jī)的資源有限，導(dǎo)致了進(jìn)程之間的資源競(jìng)爭(zhēng)和共享，也導(dǎo)致了對(duì)進(jìn)程執(zhí)行過(guò)程的制約。

1.臨界區(qū)相關(guān)概念：
臨界資源：也就是一次只允許一個(gè)進(jìn)程操作使用的計(jì)算機(jī)資源，這里的資源可以是物理資源，也可以是邏輯上的變量等。
臨界區(qū)：把不允許多個(gè)并發(fā)進(jìn)程交叉執(zhí)行的一段程序稱為臨界區(qū)（critical region）或臨界部分（critical section）。
當(dāng)一個(gè)進(jìn)程使用該臨界資源時(shí)，其他需要訪問(wèn)該資源的進(jìn)程必須阻塞，直到占用者釋放該資源。

2、間接制約
把這種由于共享某一公有資源而引起的在臨界區(qū)內(nèi)不允許并發(fā)進(jìn)程交叉執(zhí)行的現(xiàn)象，稱為由共享公有資源而造成的對(duì)并發(fā)進(jìn)程執(zhí)行速度的間接制約。這里的“間接”二字主要是指各種并發(fā)進(jìn)程的速度受公有資源的制約，而非進(jìn)程之間的直接制約。

3.進(jìn)程互斥
在并發(fā)進(jìn)程中，一個(gè)或多個(gè)進(jìn)程要對(duì)公用資源進(jìn)行訪問(wèn)時(shí)，必須確保該資源處于空閑狀態(tài)，也就是說(shuō)，在并發(fā)進(jìn)程中，臨界區(qū)只允許一個(gè)進(jìn)程進(jìn)入，而其他進(jìn)程阻塞，等待該共享臨界資源釋放。

4.并發(fā)進(jìn)程之間必須滿足以下特征：

• 平等競(jìng)爭(zhēng)：即各并發(fā)進(jìn)程享有平等地、獨(dú)立地競(jìng)爭(zhēng)共有資源的權(quán)利，且在不采取任何措施的條件下，在臨界區(qū)內(nèi)任意指令結(jié)束時(shí)，其他并發(fā)進(jìn)程可以進(jìn)入臨界區(qū)。

• 互斥使用：當(dāng)并發(fā)進(jìn)程中的時(shí)候 多個(gè)進(jìn)程同時(shí)申請(qǐng)進(jìn)入臨界區(qū)時(shí)，它只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)。

• 不可獨(dú)占：當(dāng)進(jìn)程不在臨界區(qū)后，它不能阻止其他進(jìn)程進(jìn)入臨界區(qū)。

• 有限等待：也就是在就緒隊(duì)列中的進(jìn)程等待資源時(shí)間必須是有限的。并發(fā)進(jìn)程中的某個(gè)進(jìn)程從申請(qǐng)進(jìn)入臨界區(qū)時(shí)開始，應(yīng)在有限時(shí)間內(nèi)得以進(jìn)入臨界區(qū)。

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【865977150】整理了一些個(gè)人覺(jué)得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。?！

內(nèi)核學(xué)習(xí)網(wǎng)站：

Linux內(nèi)核源碼/內(nèi)存調(diào)優(yōu)/文件系統(tǒng)/進(jìn)程管理/設(shè)備驅(qū)動(dòng)/網(wǎng)絡(luò)協(xié)議棧-學(xué)習(xí)視頻教程-騰訊課堂ke.qq.com/course/4032547?flowToken=1040236

三、互斥的實(shí)現(xiàn)

2.1、互斥的加鎖實(shí)現(xiàn)：
對(duì)互斥的臨界區(qū)進(jìn)行加鎖處理，即當(dāng)一個(gè)進(jìn)程進(jìn)入了 臨界區(qū)之后，對(duì)此臨界區(qū)進(jìn)行加鎖，直到該進(jìn)程退出臨界區(qū)為止。而其他并發(fā)進(jìn)程在申請(qǐng)進(jìn)入臨界區(qū)之前，必須測(cè)試該臨界區(qū)是否加鎖，如果是，則阻塞等待！
加鎖實(shí)現(xiàn)是系統(tǒng)的原語(yǔ)：lock(key[S])和Unlock(key([S]))均保持原子操作。系統(tǒng)實(shí)現(xiàn)時(shí)鎖定位key[S]總是設(shè)置在公有資源所對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)中的。

2.2、互斥加鎖實(shí)現(xiàn)的缺點(diǎn)：
1.在進(jìn)行鎖測(cè)試和定位中將耗費(fèi)CPU資源
2、進(jìn)程加鎖實(shí)現(xiàn)可能會(huì)對(duì)進(jìn)程不公平，例如：

進(jìn)程A:lock(key[S])<S>unlock(key[S])Goto A進(jìn)程B：lock(key[S])<S>unlock(key[S])Goto B

如上面所示，進(jìn)程A和B之間的一個(gè)進(jìn)程運(yùn)行到Goto之后，會(huì)使得另一個(gè)進(jìn)程無(wú)法得到處理機(jī)資源運(yùn)行。而處于永久饑餓狀態(tài)（starvation）。

分析可以知道，一個(gè)進(jìn)程能否進(jìn)入臨界區(qū)取決于進(jìn)程自己調(diào)用lock過(guò)程去測(cè)試相應(yīng)的鎖定位。也就是說(shuō)，每個(gè)進(jìn)程能否進(jìn)入臨界區(qū)是依靠進(jìn)程自己的測(cè)試判斷。這樣，沒(méi)有獲得執(zhí)行機(jī)會(huì)的進(jìn)程當(dāng)然無(wú)法判斷，從而出現(xiàn)不公平現(xiàn)象。

那么是否有辦法解決這個(gè)問(wèn)題呢？當(dāng)然，很明顯，辦法是有的，我們可以為臨界區(qū)設(shè)置一個(gè)管理員，由這個(gè)管理員來(lái)管理相應(yīng)臨界區(qū)的公有資源，它代表可用資源的實(shí)體，這個(gè)管理員就是信號(hào)量。

3、信號(hào)量和P、V操作
信號(hào)量和P、V原語(yǔ)是荷蘭科學(xué)家E. W. Dijkstra提出來(lái)的。
P原語(yǔ)：*P是荷蘭語(yǔ)Proberen（測(cè)試*）的首字母。為阻塞原因，負(fù)責(zé)把當(dāng)前進(jìn)程由運(yùn)行狀態(tài)轉(zhuǎn)換為阻塞狀態(tài)，直到另外一個(gè)進(jìn)程喚醒它。操作方法：申請(qǐng)一個(gè)空閑資源（把信號(hào)量減1），若成功，則退出；若失敗，則該進(jìn)程會(huì)被阻塞；

V原語(yǔ)：V是荷蘭語(yǔ)Verhogen（增加）的首字母。為喚醒原語(yǔ)，負(fù)責(zé)把一個(gè)被阻塞的進(jìn)程喚醒，它有一個(gè)參數(shù)表，存放著等待被喚醒的進(jìn)程信息。操作為：釋放一個(gè)被占用的資源（把信號(hào)量加1），如果發(fā)現(xiàn)有被阻塞的進(jìn)程，則選擇一個(gè)喚醒之。

【信號(hào)量semaphore】?在操作系統(tǒng)中，信號(hào)量sem是一個(gè)整數(shù)。

• sem >= 0時(shí)，代表可供并發(fā)進(jìn)程使用的資源實(shí)體數(shù)；

• sem < 0時(shí)，表示正在等待使用臨界區(qū)的進(jìn)程數(shù)。

顯然，用于互斥的信號(hào)量sem的初值應(yīng)該大于0，而建立一個(gè)信號(hào)量必須說(shuō)明所建信號(hào)量代表的意義，賦初值，以及建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，以便指向那些等待使用該臨界區(qū)的進(jìn)程。sem初值為1。

【P、V原語(yǔ)】
信號(hào)量的數(shù)值僅能由P、V原語(yǔ)操作改變。采用P、V原語(yǔ)，可以把類名為S的臨界區(qū)描述為：When S do P(sem) 臨界區(qū) V(sem) od。

• 一次P原語(yǔ)操作使信號(hào)量sem減1

• 一次V原語(yǔ)操作使信號(hào)量sem加1

P原語(yǔ)操作：

sem減1；
若sem減1后仍大于或等于0，則P原語(yǔ)返回，該進(jìn)程繼續(xù)執(zhí)行；
若sem減1后小于0，則該進(jìn)程被阻塞后進(jìn)入與該信號(hào)相對(duì)應(yīng)的隊(duì)列中，然后轉(zhuǎn)進(jìn)程調(diào)度。

V原語(yǔ)操作：

sem加1；
若相加結(jié)果大于0，V原語(yǔ)停止執(zhí)行，該進(jìn)程返回調(diào)用處，繼續(xù)執(zhí)行；
若相加結(jié)果小于或等于0，則從該信號(hào)的等待隊(duì)列中喚醒一個(gè)等待進(jìn)程，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。

這里給出一個(gè)使用加鎖法的軟件實(shí)現(xiàn)方法來(lái)實(shí)現(xiàn)P、V原語(yǔ)：

P(sem): ? ?begin ? ? ? ?封鎖中斷; ? ? ? ?lock(lockbit) ? ? ? ?val[sem]=val[sem]-1 ? ? ? ?if val[sem]<0 ? ? ? ? ? ?保護(hù)當(dāng)前進(jìn)程CPU現(xiàn)場(chǎng) ? ? ? ? ? ?當(dāng)前進(jìn)程狀態(tài)置為“等待” ? ? ? ? ? ?將當(dāng)前進(jìn)程插入信號(hào)sem等待隊(duì)列 ? ? ? ? ? ?轉(zhuǎn)進(jìn)程調(diào)度 ? ? ? ?fi ? ? ? ?unlock(lockbit);開放中斷 ? ?endV(sem): ? ?begin ? ? ? ?封鎖中斷; ? ? ? ?lock(lockbit) ? ? ? ?val[sem]=val[sem]+1 ? ? ? ?if val[sem]<=0 ? ? ? ? ? ?local k ? ? ? ? ? ?從sem等待隊(duì)列中選取一個(gè)等待進(jìn)程，將其指針置入k中 ? ? ? ? ? ?將k插入就緒隊(duì)列 ? ? ? ? ? ?進(jìn)程狀態(tài)置位“就緒” ? ? ? ?fi ? ? ? ?unlock(lockbit);開放中斷 ? ?end

2.3用P、V原語(yǔ)實(shí)現(xiàn)進(jìn)程互斥
設(shè)信號(hào)量sem是用于互斥的信號(hào)量，且其初始值為1表示沒(méi)有并發(fā)進(jìn)程使用該臨界區(qū)。顯然，由前面論述可知，只要把臨界區(qū)置于P(sem)和V(sem)之間，即可實(shí)現(xiàn)進(jìn)程之間的互斥。

用信號(hào)量實(shí)現(xiàn)兩個(gè)并發(fā)進(jìn)程PA和PB互斥的描述如下：
（1）設(shè)sem為互斥信號(hào)量，其取值范圍為（1，0，-1）。其中sem=1表示進(jìn)程PA和PB都未進(jìn)入類名為S的臨界區(qū)，sem=0表示進(jìn)程PA或PB已進(jìn)入類名為S的臨界區(qū)，sem=-1表示進(jìn)程PA和PB中，一個(gè)進(jìn)程已進(jìn)入臨界區(qū)，而另一個(gè)進(jìn)程等待進(jìn)入該臨界區(qū)。
（2）實(shí)現(xiàn)過(guò)程：

Pa: ? ?P(sem) ? ?<S> ? ?V(sem) ? ?. ? ?. ? ?.Pb: ? ?P(sem) ? ?<S> ? ?V(sem) ? ?. ? ?. ? ?.

四，進(jìn)程互斥的軟件實(shí)現(xiàn)方法：

1，單標(biāo)志法

1）在進(jìn)入?yún)^(qū)只檢查，不上鎖

2）在退出區(qū)把臨界資源的使用權(quán)交給另一個(gè)進(jìn)程

3）主要問(wèn)題：不遵循空閑讓進(jìn)的原則

2，雙標(biāo)志先檢查

1）在進(jìn)入?yún)^(qū)先檢查后上鎖，退出區(qū)解鎖

2）主要問(wèn)題：不遵循原則等待原則

3，雙標(biāo)志后檢查

1）在進(jìn)入?yún)^(qū)先

上鎖后檢查，退出區(qū)解鎖

2）主要問(wèn)題：不遵循空閑讓進(jìn)，有限等待原則，可能導(dǎo)致饑餓

4，Peterson算法

1）在進(jìn)入?yún)^(qū)主動(dòng)爭(zhēng)取——》主動(dòng)謙讓——》檢查對(duì)方是否想進(jìn)，己方是否謙讓

2）主要問(wèn)題：不遵循讓則等待原則，會(huì)發(fā)送忙等

五、進(jìn)程同步

【進(jìn)程間的直接制約】：一組在異步環(huán)境下的并發(fā)進(jìn)程，各自的執(zhí)行結(jié)果互為對(duì)方的執(zhí)行條件，從而限制各進(jìn)程的執(zhí)行速度的過(guò)程稱為并發(fā)進(jìn)程間的直接制約。這里的異步環(huán)境主要是指各并發(fā)進(jìn)程的執(zhí)行起始時(shí)間的隨機(jī)性和執(zhí)行速度的獨(dú)立性。

【進(jìn)程間的同步】：把異步環(huán)境下的一組并發(fā)進(jìn)程因直接制約而互相發(fā)送消息而進(jìn)行互相合作、互相等待，使得各進(jìn)程按一定的速度執(zhí)行的過(guò)程稱為進(jìn)程間的同步。具有同步關(guān)系的一組并發(fā)進(jìn)程稱為合作進(jìn)程，合作進(jìn)程間相互發(fā)送的信號(hào)稱為消息或事件。
用消息實(shí)現(xiàn)進(jìn)程同步：

用
wait(消息名)
表示進(jìn)程等待合作進(jìn)程發(fā)來(lái)的消息。
用
signal(消息名)
表示向合作進(jìn)程發(fā)送消息。
過(guò)程wait的功能是等待到消息名為true的進(jìn)程繼續(xù)執(zhí)行，而signal的功能則是向合作進(jìn)程發(fā)送合作進(jìn)程所需要的消息名，并將其值置為true。

進(jìn)程互斥和進(jìn)程同步】：
進(jìn)程同步不同于進(jìn)程互斥，進(jìn)程互斥時(shí)它們的執(zhí)行順序可以是任意的。一般來(lái)說(shuō)，也可以把個(gè)進(jìn)程之間發(fā)送的消息作為信號(hào)量看待。與進(jìn)程互斥時(shí)不同的是，這里的信號(hào)量只與制約進(jìn)程及被制約進(jìn)程有關(guān)，而不是與整租并發(fā)進(jìn)程有關(guān)。因此，稱該信號(hào)量為私用信號(hào)量（private semaphore）。一個(gè)進(jìn)程Pi的私用信號(hào)量semi是從制約進(jìn)程發(fā)送來(lái)的進(jìn)程Pi的執(zhí)行條件所需要的信息。與私用信號(hào)量相對(duì)應(yīng)，稱互斥時(shí)使用的信號(hào)量為公用信號(hào)量。

【用P、V原語(yǔ)實(shí)現(xiàn)進(jìn)程同步】：
首先為各并發(fā)進(jìn)程設(shè)置私用信號(hào)量，然后為私用信號(hào)量賦初值，最后利用P、V原語(yǔ)和私用信號(hào)量規(guī)定各進(jìn)程的執(zhí)行順序。