操作系统 进程管理（三）——进程同步方法简述
目錄
進(jìn)程同步的基本概念
1）兩種形式的制約關(guān)系
2）Critical section（臨界區(qū)）
3）Mutual exclusion（互斥）
4）Dead lock（死鎖）
5）Starvation（饑餓）
6）面包問(wèn)題（鎖的概念）
同步機(jī)制原則
實(shí)現(xiàn)進(jìn)程互斥的方法
方法一 基于軟件的解決方案
算法一 x
算法二 x
算法三 x
算法四——Peterson算法 1981 √
算法五——Backery算法作為補(bǔ)充
方法二? 禁用硬件中斷
（一）鎖方法 TS互斥
（二）交換指令Swap方法
方法三? 信號(hào)量機(jī)制
1）整型信號(hào)量
2).記錄型信號(hào)量
3）AND型信號(hào)量集機(jī)制
?3）一般信號(hào)量集機(jī)制
在多道系統(tǒng)中，并發(fā)執(zhí)行的諸進(jìn)程之間，既有獨(dú)立性，又有制約性。
獨(dú)立性是指各進(jìn)程都可獨(dú)立地向前推進(jìn)；
制約性是指由于資源共享和進(jìn)程合作所引起的進(jìn)程之間的相互依賴(lài)和相互制約的關(guān)系。進(jìn)程之間的相互制約關(guān)系有兩種：互斥和同步，互斥也可看作是一種同步，一種特殊的同步。
進(jìn)程同步的基本概念
1）兩種形式的制約關(guān)系
(1)間接相互制約關(guān)系。
(2) 直接相互制約關(guān)系。
2）Critical section（臨界區(qū)）
臨界區(qū)是指進(jìn)程中的一段需要訪問(wèn)共享資源并且當(dāng)一個(gè)進(jìn)程處于響應(yīng)代碼區(qū)域時(shí)編不會(huì)被執(zhí)行的代碼區(qū)域。
3）Mutual exclusion（互斥）
當(dāng)一個(gè)進(jìn)程處于臨界區(qū)并訪問(wèn)共享資源時(shí)，沒(méi)有其他進(jìn)程會(huì)處于臨界區(qū)并且訪問(wèn)任何相同的共享資源。
4）Dead lock（死鎖）
兩個(gè)或以上的進(jìn)程，在相互等待完成特定任務(wù)，而最終沒(méi)法將自身任務(wù)進(jìn)行下去。
5）Starvation（饑餓）
一個(gè)可執(zhí)行的進(jìn)程，被調(diào)度器持續(xù)忽略，以至于雖然處于可執(zhí)行狀態(tài)卻不被執(zhí)行。
6）面包問(wèn)題（鎖的概念）
-Lock (鎖)∶在門(mén)、抽屜等物體上加上保護(hù)性裝置，使得外人無(wú)法訪問(wèn)物體內(nèi)的東西,只能等待解鎖后才能訪問(wèn)。
-Unlock(解鎖):打開(kāi)保護(hù)性裝置，使得可以訪問(wèn)之前被鎖保護(hù)的物體類(lèi)的東西。
-Deadlock (死鎖)∶A拿到鎖1，B拿到鎖2，A想繼續(xù)拿到鎖2后再繼續(xù)執(zhí)行，B想繼續(xù)拿到鎖1后再繼續(xù)執(zhí)行。導(dǎo)致A和B誰(shuí)也無(wú)法繼續(xù)執(zhí)行。
同步機(jī)制原則：
空閑讓進(jìn)：當(dāng)無(wú)進(jìn)程處于臨界區(qū)時(shí)，表明臨界資源處于空閑狀態(tài)，應(yīng)允許一個(gè)請(qǐng)求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)，以有效利用臨界資源
忙則等待：當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時(shí)，表明臨界資源正在被占用，因而其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證對(duì)臨界資源的互斥使用
有限等待：對(duì)要求訪問(wèn)臨界資源的進(jìn)程，應(yīng)保證在有限時(shí)間內(nèi)能進(jìn)入到自己的臨界區(qū)，以免陷入死等的狀態(tài)
讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以避免進(jìn)程陷入忙等狀態(tài)
實(shí)現(xiàn)進(jìn)程互斥的方法
解決臨界區(qū)問(wèn)題的三個(gè)必須標(biāo)準(zhǔn)：互斥訪問(wèn), 進(jìn)入（即不死鎖）, 有限等待（即不餓死）
方法一 基于軟件的解決方案
?算法一 x
缺點(diǎn)：滿(mǎn)足互斥，但是Starvation。必須輪流使用臨界區(qū)，不能同一進(jìn)程使用兩次
? ? ? ? ? ?一個(gè)進(jìn)程失敗，另一個(gè)將被永久阻塞。
算法二 x
缺點(diǎn)：不能互斥，若起初設(shè)置flag[i]和flag[j]都為false，那么可以先執(zhí)行?1再執(zhí)行2，這樣就同時(shí)進(jìn)入臨界區(qū)了。
算法三 x
缺點(diǎn)：? 滿(mǎn)足互斥，但是死鎖先執(zhí)行1再執(zhí)行2，兩者都無(wú)法進(jìn)入臨界區(qū)
算法四——Peterson算法 1981 √
這個(gè)佬講得很好：Peterson‘s Algorithm皮特森算法詳解_我知道你是高手的博客-CSDN博客_皮特森算法
flag數(shù)組：為了判定是否有其他進(jìn)程想要進(jìn)入臨界區(qū)（避免如果沒(méi)有其他進(jìn)程想要進(jìn)入，當(dāng)前進(jìn)程一直空等）
turn變量：為想要進(jìn)入臨界區(qū)的進(jìn)程進(jìn)行排序（turn==i則Pj在前，turn==j則Pi在前），先提出申請(qǐng)的進(jìn)程優(yōu)先進(jìn)入臨界區(qū)，其他進(jìn)程等待，就這樣實(shí)現(xiàn)了對(duì)臨界區(qū)訪問(wèn)的互斥。
若Pi和Pj都想進(jìn)入臨界區(qū)，i先提出申請(qǐng)，j后提出申請(qǐng)，進(jìn)入while循環(huán)判定時(shí)turn==i（Pi執(zhí)行turn=j在前，Pj執(zhí)行turn=i在后，所以while循環(huán)中的turn==i）；先提出申請(qǐng)的進(jìn)程先進(jìn)入臨界區(qū)；Pi走到while循環(huán)，此時(shí)flag[j]==true，turn==i，不滿(mǎn)足循環(huán)條件，跳出（若是Pj不想進(jìn)入臨界區(qū)壓根就沒(méi)有提出申請(qǐng)，那么flag[j]==false，更不滿(mǎn)足循環(huán)條件），Pi就可以繼續(xù)進(jìn)入critical section；Pj走到while循環(huán)，但是因?yàn)榇藭r(shí)flag[i]==ture且turn==i，Pj陷入while循環(huán)中無(wú)法進(jìn)入critical section，Pj需要一直等到Pi退出臨界區(qū)時(shí)置flag[i]==false才能跳出循環(huán)，進(jìn)入臨界區(qū)；
算法五——Backery算法作為補(bǔ)充
方法二? 禁用硬件中斷
?沒(méi)有中斷，沒(méi)有上下文切換，因此沒(méi)有并發(fā)
? ? ? ? >硬件將中斷處理延遲到中斷被啟用之后
? ? ? ? >大多數(shù)現(xiàn)代計(jì)算機(jī)體系結(jié)構(gòu)都提供指令來(lái)完成
（一）鎖方法 TS互斥
進(jìn)入臨界區(qū) >禁用中斷
離開(kāi)臨界區(qū) >開(kāi)啟中斷
（二）交換指令Swap方法
缺點(diǎn)：一旦中斷被禁用，線程無(wú)法被停止，整個(gè)系統(tǒng)都會(huì)停下，可能導(dǎo)致其他線程starvation
? ? ? ? ???臨界區(qū)若可以任意長(zhǎng)，無(wú)法限制響應(yīng)中斷所需時(shí)間：忙等
方法三? 信號(hào)量機(jī)制
1）整型信號(hào)量
抽象數(shù)據(jù)類(lèi)型：一個(gè)整形(sem)，兩個(gè)原子操作
- P(): sem減1，如果sem<0，等待，否則繼續(xù)(wait(S))
- v(): sem加1，如果sem<=0,喚醒一個(gè)等待的P(signal(S))
ps:
- Sem表示空閑資源數(shù)（鎖方法中僅為一個(gè)，或一個(gè)進(jìn)程使用）
- P操作申請(qǐng)一個(gè)資源，V操作釋放一個(gè)資源。
- 缺點(diǎn): “忙等”，故把這種PV操作稱(chēng)為“忙等”PV操作。
- P.V操作必須為原子操作，對(duì)于單處理機(jī)，可用禁止中斷實(shí)現(xiàn), 對(duì)于多處理機(jī)，要用軟件協(xié)助解決。
- P.V操作必須成對(duì)出現(xiàn)。
e.g.計(jì)算機(jī)系統(tǒng)的打印機(jī)? 圖from:信號(hào)量機(jī)制_fFee-ops的博客-CSDN博客_信號(hào)量機(jī)制
2).記錄型信號(hào)量
——為克服“忙等”，重新對(duì)信號(hào)量和P.V操定義
圖from:?信號(hào)量機(jī)制_fFee-ops的博客-CSDN博客_信號(hào)量機(jī)制
注意：
??? S.Value? >0? 表示某類(lèi)可用資源的數(shù)量
? ? ? ? ? ? ? ? ??<0? 其絕對(duì)值為因請(qǐng)求該資源而被阻塞的進(jìn)程數(shù)
??? S.Value的初值為1時(shí)，表示只允許一個(gè)進(jìn)程訪問(wèn)臨界資源，此時(shí)的信號(hào)量轉(zhuǎn)化為互斥信號(hào)量。
3）AND型信號(hào)量集機(jī)制
基本思想：
- 將進(jìn)程在整個(gè)運(yùn)行過(guò)程中需要的所有資源，一次性全部地分配給進(jìn)程，待進(jìn)程使用完后再一起釋放；（類(lèi)似于數(shù)據(jù)庫(kù)中的事務(wù)）
- 對(duì)若干個(gè)臨界資源的分配，采取原子操作方式要么全部分配到進(jìn)程，要么一個(gè)也不分配；
- 為此，在wait操作中，增加了一個(gè)“AND”條件，故稱(chēng)為AND同步；
定義如下：
?3）一般信號(hào)量集機(jī)制
每次只能獲得或釋放一個(gè)單位的臨界資源太低效；
當(dāng)資源數(shù)量低于某一下限值時(shí)，便不予分配；
基于以上兩點(diǎn)對(duì)And信號(hào)進(jìn)行擴(kuò)充。
?特殊情況討論：
(1)Swait(S,d,d)。
??? 此時(shí)在信號(hào)量集中只有一個(gè)信號(hào)量，但它允許每次申請(qǐng)d個(gè)資源，當(dāng)現(xiàn)有資源數(shù)少于d時(shí)，不予分配。
(2)Swait(S,1,1)。
??? 此時(shí)的信號(hào)量集蛻化為一般的記錄型信號(hào)量(S＞1時(shí))或互斥信號(hào)量(S = 1 時(shí))。
(3)Swait(S,1,0)。??? 相當(dāng)于一個(gè)可控開(kāi)關(guān)
??? 這是一種很特殊且很有用的信號(hào)量，不分配資源。
??? 當(dāng)S>=1時(shí)，允許多個(gè)進(jìn)程進(jìn)入某特定區(qū)；
??? 當(dāng)S=0時(shí)，將阻止任何進(jìn)程進(jìn)入特定區(qū)。
總結(jié)
以上是生活随笔為你收集整理的操作系统 进程管理（三）——进程同步方法简述的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： android没有无线显示器,手机的无线
- 下一篇： HTTP请求的TCP瓶颈分析