一、進(jìn)程同步
1、 定義
（1） 臨界資源：把一個(gè)時(shí)間段內(nèi)只允許一個(gè)進(jìn)程使用的資源稱為臨界資源。許多物理設(shè)備（攝像頭、打印機(jī)）和許多變量、數(shù)據(jù)、內(nèi)存緩沖區(qū)都屬于臨界資源。
對臨界資源的訪問必須互斥地進(jìn)行。
① 進(jìn)入?yún)^(qū)：為了進(jìn)入臨界區(qū)使用臨界資源，在進(jìn)入?yún)^(qū)檢查可否進(jìn)入臨界區(qū)，如果可以進(jìn)入臨界區(qū)，則應(yīng)設(shè)置正在訪問臨界區(qū)的標(biāo)志，以阻止其他進(jìn)程同時(shí)進(jìn)入臨界區(qū)
② 臨界區(qū)：進(jìn)程中訪問臨界資源的那段代碼，又稱臨界段
③ 退出區(qū)：將正在訪問臨界區(qū)的標(biāo)志清除
④ 剩余區(qū)：代碼中其余的部分
（2） 互斥：亦稱間接制約關(guān)系，進(jìn)程互斥是指當(dāng)一個(gè)進(jìn)程訪問某臨界資源時(shí)，另一個(gè)想要訪問該臨界資源的進(jìn)程必須等待。當(dāng)前訪問臨界資源的進(jìn)程訪問結(jié)束，釋放該資源之后，另一個(gè)進(jìn)程才能去訪問臨界資源
為了實(shí)現(xiàn)對臨界資源的互斥訪問，同時(shí)保證系統(tǒng)整體性能，需要遵循以下原則：
① 空閑讓進(jìn)。臨界區(qū)空閑時(shí)，可以允許一個(gè)請求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入臨界區(qū)
② 忙則等待。當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時(shí)，其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待
③ 有限等待。對請求訪問的進(jìn)程，應(yīng)保證能在有限時(shí)間內(nèi)進(jìn)入臨界區(qū)（保證不會饑餓）
④ 讓權(quán)等待。當(dāng)進(jìn)程不能進(jìn)入臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，防止進(jìn)程忙等待
（3） 同步：亦稱直接制約關(guān)系，它是指為完成某種任務(wù)而建立的兩個(gè)或多個(gè)進(jìn)程，這些進(jìn)程因?yàn)樾枰谀承┪恢蒙蠀f(xié)調(diào)它們的工作次序而產(chǎn)生的制約關(guān)系。進(jìn)程間的直接制約關(guān)系就是源于它們之間的相互合作
二、進(jìn)程互斥的軟件實(shí)現(xiàn)方法
1、 單標(biāo)志法
? 算法思想：兩個(gè)進(jìn)程在訪問完臨界區(qū)后會把使用臨界區(qū)的權(quán)限轉(zhuǎn)交給另一個(gè)進(jìn)程。也就是說每個(gè)進(jìn)程進(jìn)入臨界區(qū)的權(quán)限只能被另一個(gè)進(jìn)程賦予
turn 表示當(dāng)前允許進(jìn)入臨界區(qū)的進(jìn)程號，而只有當(dāng)前允許進(jìn)入臨界區(qū)的進(jìn)程在訪問了臨界區(qū)之后，才會修改 turn 的值。也就是說，對于臨界區(qū)的訪問，一定是按P0→P1→P0→P1……這樣輪流訪問。這種必須“輪流訪問”帶來的問題是，如果此時(shí)允許進(jìn)入臨界區(qū)的進(jìn)程是 P0，而 P0 一直不訪問臨界區(qū)，那么雖然此時(shí)臨界區(qū)空閑，但是并不允許 P1 訪問。
因此，單標(biāo)志法存在的主要問題是：違背“空閑讓進(jìn)”原則
2、 雙標(biāo)志先檢查
? 算法思想：設(shè)置一個(gè)布爾型數(shù)組 flag[]，數(shù)組中各個(gè)元素用來標(biāo)記各進(jìn)程想進(jìn)入臨界區(qū)的意愿，比如“flag[0]=ture”意味著 0 號進(jìn)程 P0 現(xiàn)在想要進(jìn)入臨界區(qū)。每個(gè)進(jìn)程在進(jìn)入臨界區(qū)之前先檢查當(dāng)前有沒有別的進(jìn)程想進(jìn)入臨界區(qū)，如果沒有，則把自身對應(yīng)的標(biāo)志 flag[i]設(shè)為 true，之后開始訪問臨界區(qū)
3、 雙標(biāo)志后檢查
? 雙標(biāo)志先檢查法的改版。前一個(gè)算法的問題是先“檢查”后“上鎖“，但是這兩個(gè)操作又無法一氣呵成，因此導(dǎo)致了兩個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)的問題。因此，人們又想到先”上鎖“后”檢查“的方法來避免上述問題
4、 Peterson 算法
? 算法思想：雙標(biāo)志后檢查法中，兩個(gè)進(jìn)程都爭著想進(jìn)入臨界區(qū)，但是誰也不讓誰，最后誰都無法進(jìn)入臨界區(qū)，Peterson 提出：如果雙方都爭著想進(jìn)入臨界區(qū)，那可以讓進(jìn)程嘗試“孔融讓梨“，主動讓對方先使用臨界區(qū)
Peterson 算法用軟件方法解決了進(jìn)程互斥問題，遵循了空閑讓進(jìn)、忙則等待、有限等待三個(gè)原則，但是依然未遵循讓權(quán)等待的原則
三、進(jìn)程互斥的硬件實(shí)現(xiàn)方法
1、 中斷屏蔽方法
? 利用“開/關(guān)中斷指令“實(shí)現(xiàn)（與原語的實(shí)現(xiàn)思想相同，即在某進(jìn)程開始訪問臨界區(qū)到結(jié)束訪問為止都不允許被中斷，也就不能發(fā)生進(jìn)程切換，因此也不可能發(fā)生兩個(gè)同時(shí)訪問臨界區(qū)的情況）
? 優(yōu)點(diǎn)：簡單、高效
? 缺點(diǎn)：不適用于多處理機(jī)；只適用于操作系統(tǒng)內(nèi)核進(jìn)程，不適用于用戶進(jìn)程（因?yàn)殚_/關(guān)中斷指令只能運(yùn)行在內(nèi)核態(tài)，這組指令如果能讓用戶隨意使用會很危險(xiǎn)）
2、 TestAndSet（TS 指令/TSL 指令）
TSL 指令是用硬件實(shí)現(xiàn)的，執(zhí)行的過程不允許被中斷，只能一氣呵成
? 若剛開始 lock 是 false，則 TSL 返回的 old 值為 false，while 循環(huán)條件不滿足，直接跳過循環(huán)，進(jìn)入臨界區(qū)。若剛開始 lock 是 true，則執(zhí)行 TLS 后 old 返回的值為 true，while 循環(huán)條件滿足，會一直循環(huán)，直到當(dāng)前訪問臨界區(qū)的進(jìn)程在退出區(qū)進(jìn)行“解鎖
? 相比軟件實(shí)現(xiàn)方法，TSL 指令把“上鎖“和”檢查“操作用硬件的方式變成了一氣呵成的原子操作
? 優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，無需像軟件實(shí)現(xiàn)方法那樣嚴(yán)格檢查是否會有邏輯漏洞；適用于多處理機(jī)環(huán)境
? 缺點(diǎn)：不滿足“讓權(quán)等待“原則，暫時(shí)無法進(jìn)入臨界區(qū)的進(jìn)程會占用 CPU 并循環(huán)執(zhí)行TSL 指令，從而導(dǎo)致”忙等“
3、 Swap 指令（XCHG 指令）
Swap 指令是用硬件實(shí)現(xiàn)的，執(zhí)行的過程不允許被中斷，只能一氣呵成
四、信號量機(jī)制
1、 定義
? 用戶進(jìn)程可以通過使用操作系統(tǒng)提供的一對原語來對信號量進(jìn)行操作，從而很方便的實(shí)現(xiàn)了進(jìn)程互斥、進(jìn)程同步
? 信號量其實(shí)就是一個(gè)變量（可以是一個(gè)整數(shù)，也可以是更復(fù)雜的記錄型變量），可以用一個(gè)信號量來表示系統(tǒng)中某種資源的數(shù)量，比如：系統(tǒng)中只有一臺打印機(jī)，就可以設(shè)置一個(gè)初值為 1 的信號量
? 原語是一種特殊的程序段，其執(zhí)行只能一氣呵成，不可被中斷。原語是由關(guān)中斷/開中斷指令實(shí)現(xiàn)的。軟件解決方案的主要問題是由“進(jìn)入?yún)^(qū)的各種操作無法一氣呵成”，因此如果能把進(jìn)入?yún)^(qū)、退出區(qū)的操作都用“原語”實(shí)現(xiàn)，使這些操作能“一氣呵成”就能避免問題
? 一對原語：wait（）原語和 signal（）原語，可以把原語理解為自己寫的函數(shù)，函數(shù)名分別為 wait 和 signal。
?
wait、signal 原語常稱為 P、V 操作
2、 整型信號量
用一個(gè)整數(shù)型的變量作為信號量，用來表示系統(tǒng)中某種資源的數(shù)量
與普通整數(shù)變量的區(qū)別：對信號量的操作只有三種——初始化、P 操作、V 操作
3、 記錄型信號量
整型信號量的缺陷是存在“忙等”問題，因此人們又提出了“記錄型信號量”，即用記錄型數(shù)據(jù)結(jié)構(gòu)表示的信號量
五、用信號量實(shí)現(xiàn)進(jìn)程互斥、同步和前驅(qū)關(guān)系
1、 實(shí)現(xiàn)進(jìn)程互斥
① 分析并發(fā)進(jìn)程的關(guān)鍵活動，劃定臨界區(qū)（如：對臨界資源打印機(jī)的訪問就應(yīng)放在臨界區(qū)）
② 設(shè)置互斥信號量 mutex，初值為 1
③ 在臨界區(qū)之前執(zhí)行 P(mutex)
④ 在臨界區(qū)之后執(zhí)行 V(mutex)
注意：對不同的臨界資源需要設(shè)置不同的互斥信號量。
P、V 操作必須成對出現(xiàn)。缺少 P 操作就不能保證臨界資源的互斥訪問。缺少 V 操作會導(dǎo)致資源永不被釋放，等待進(jìn)程永不被喚醒
2、 實(shí)現(xiàn)進(jìn)程同步
① 分析什么地方需要實(shí)現(xiàn)“同步關(guān)系”，即必須保證“一前一后”執(zhí)行的兩個(gè)操作（或兩句代碼）
② 設(shè)置同步信號量 S，初始為 0
③ 在“前操作”之后執(zhí)行 V(S)
④ 在“后操作”之前執(zhí)行 P(S)
3、 實(shí)現(xiàn)進(jìn)程的前驅(qū)關(guān)系
六、管程
1、 定義
管程是一種特殊的軟件模塊，有這些部分組成：
① 局部于管程的共享數(shù)據(jù)結(jié)構(gòu)說明；
② 對該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程；
③ 對局部于管程的共享數(shù)據(jù)設(shè)置初始值的語句；
④ 管程有一個(gè)名字。
2、 基本特征
① 局部于管程的數(shù)據(jù)只能被局部于管程的過程所訪問；
② 一個(gè)進(jìn)程只有通過調(diào)用管程內(nèi)的過程才能進(jìn)入管程訪問共享數(shù)據(jù)
③ 每次僅允許一個(gè)進(jìn)程在管程內(nèi)執(zhí)行某個(gè)內(nèi)部過程。
3、 管程的使用注意
引入管程的目的無非就是要更方便地實(shí)現(xiàn)進(jìn)程互斥和同步
① 需要在管程中定義共享數(shù)據(jù)（如生產(chǎn)者消費(fèi)者問題的緩沖區(qū)）
② 需要在管程中定義用于訪問這些共享數(shù)據(jù)的“入口”——其實(shí)就是一些函數(shù)（如生產(chǎn)者消費(fèi)者問題中，可以定義一個(gè)函數(shù)用于將產(chǎn)品放入緩沖區(qū)，再定義一個(gè)函數(shù)用于從緩沖區(qū)取出產(chǎn)品）
③ 只有通過這些特定的“入口”才能訪問共享數(shù)據(jù)
④ 管程中有很多“入口”，但是每次只能開放其中一個(gè)“入口”，并且只能讓一個(gè)進(jìn)程或線程進(jìn)入（如生產(chǎn)者消費(fèi)者問題中，各進(jìn)程需要互斥地訪問共享緩沖區(qū)。管程的這種特性即可保證一個(gè)時(shí)間段內(nèi)最多只會有一個(gè)進(jìn)程在訪問緩沖區(qū)。注意：這種互斥特性是由編譯器負(fù)責(zé)實(shí)現(xiàn)的，程序員不用擔(dān)心）
⑤ 可在管程中設(shè)置條件變量及等待/喚醒操作以解決同步問題?？梢宰屢粋€(gè)進(jìn)程或線程在條件變量上等待（此時(shí)，該進(jìn)程應(yīng)先釋放管程的使用權(quán)，也就是讓出“入口”）；可以通過喚醒操作將等待在條件變量上的進(jìn)程或線程喚醒程序員可以用某種特殊的語法定義一個(gè)管程，之后其他程序員就可以使用這個(gè)管程提供的特定的“入口”很方便地使用實(shí)現(xiàn)進(jìn)程同步/互斥了
七、死鎖
1、 概念
- （1） 在多道程序系統(tǒng)中，由于多個(gè)進(jìn)程的并發(fā)執(zhí)行，改善了系統(tǒng)資源的利用率并提高了
系統(tǒng)的處理能力。然而，多個(gè)進(jìn)程的并發(fā)執(zhí)行也帶來了新的問題——死鎖。死鎖是
指多個(gè)進(jìn)程因競爭資源而造成的一種僵局（互相等待），若無外力作用，這些進(jìn)程都
將無法向前推進(jìn)。 - （2） 區(qū)別饑餓、死循環(huán)
? 饑餓：由于長期得不到想要的資源，某進(jìn)程無法向前推進(jìn)的現(xiàn)象
? 死循環(huán)：某進(jìn)程執(zhí)行過程中一直跳不出某個(gè)循環(huán)的現(xiàn)象
2、 死鎖產(chǎn)生的原因
① 對系統(tǒng)資源的競爭。各進(jìn)程對不可剝奪的資源（如打印機(jī)）的競爭可能引起死鎖，對可剝奪的資源（如 CPU）的競爭不會引起死鎖
② 進(jìn)程推進(jìn)順序非法。請求和釋放資源的順尋不當(dāng)，也會導(dǎo)致死鎖
③ 信號量的使用不當(dāng)。如生產(chǎn)者-消費(fèi)者問題中，如果實(shí)現(xiàn)互斥的 P 操作在實(shí)現(xiàn)同步的 P 操作之前，就有可能導(dǎo)致死鎖
3、 死鎖產(chǎn)生的必要條件
產(chǎn)生死鎖必須同時(shí)滿足四個(gè)條件，只要一條不成立，死鎖就不會發(fā)生
① 互斥條件：只有對必須互斥使用的資源的爭搶才會導(dǎo)致死鎖
② 不剝奪條件：進(jìn)程所獲得的資源在未使用完之前，不能由其他進(jìn)程強(qiáng)行奪走，只能主動釋放。
③ 請求和保持條件：進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又提出了新的資源請求，而該資源又被其他進(jìn)程占有，此時(shí)請求進(jìn)程被阻塞，但又對自己已有的資源保持不放。
④ 循環(huán)等待條件：存在一種進(jìn)程資源的循環(huán)等待鏈，鏈中的每一個(gè)進(jìn)程已獲得的資源同時(shí)被下一個(gè)進(jìn)程所請求
注意：發(fā)生死鎖一定循環(huán)等待，但循環(huán)等待不一定死鎖
4、 死鎖的預(yù)防
- （1） 破壞互斥條件（不太可行）
將系統(tǒng)資源都共享使用，但有些資源根本不能共享使用 - （2） 破壞不剝奪條件
當(dāng)某個(gè)進(jìn)程請求新的資源得不到滿足時(shí)，它必須立即釋放保存的所有資源，待以后需要時(shí)再重新申請。也就是說，即使某些資源尚未使用完，也需要主動釋放，從而破壞了不可剝奪條件
缺點(diǎn)：
① 實(shí)現(xiàn)起來比較復(fù)雜；
② 釋放已獲得的資源可能造成前一階段工作的失效。因此這種方法只適用于易保存和恢復(fù)狀態(tài)的資源，如 CPU；
③ 反復(fù)地申請和釋放資源會增加系統(tǒng)開銷，降低系統(tǒng)吞吐量
④ 如果暫時(shí)得不到某個(gè)資源就要放棄所有資源，以后再重新申請，就有可能發(fā)生饑餓 - （3） 破壞請求和保持條件
可以采用靜態(tài)分配法，即進(jìn)程在運(yùn)行前一次申請完它所需要的全部資源，在它的資源未滿足前，不讓它投入運(yùn)行。一旦投入運(yùn)行后，這些資源就一直歸它所有，該進(jìn)程就不會再請求別的任何資源了
缺點(diǎn)：有些資源可能只需要用很短的時(shí)間，因此如果進(jìn)程的整個(gè)運(yùn)行期間都一直保持著所有資源，就會造成資源浪費(fèi)，資源利用率極低。另外，該策略也有可能導(dǎo)致某些進(jìn)程饑餓。 - （4） 破壞循環(huán)等待條件
可采用順序資源分配法。首先給系統(tǒng)中的資源編號，規(guī)定每個(gè)進(jìn)程必須按編號遞增的順序請求資源，同類資源（即編號相同的資源）一次申請完。一個(gè)進(jìn)程只有已占有小編號的資源時(shí)，才有資格申請更大編號的資源。按此規(guī)則，已持有更大編號資源的進(jìn)程不可能逆向地回來申請小編號的資源，從而就不會產(chǎn)生循環(huán)等待的現(xiàn)象
缺點(diǎn)：
新的設(shè)備，因?yàn)榭赡苄枰匦路峙渌械木幪?br> ① 進(jìn)程實(shí)際使用資源的順序可能和編號遞增順序不一致，會導(dǎo)致資源浪費(fèi)
② 必須按規(guī)定次序申請資源，用戶編程麻煩
5、 死鎖的避免
- （1） 什么是安全序列
? 所謂安全序列，就是指如果系統(tǒng)按照這種序列分配資源，則每個(gè)進(jìn)程都能順利完成。
只要能找出一個(gè)安全序列，系統(tǒng)就是安全狀態(tài)。當(dāng)然，安全序列可能有多個(gè)。
? 如果分配了資源之后，系統(tǒng)找不出任何一個(gè)安全序列，系統(tǒng)就進(jìn)入了不安全狀態(tài)。
這就意味著之后可能所有進(jìn)程都無法順利的執(zhí)行下去。當(dāng)然，如果有進(jìn)程提前歸還了一些資源，那系統(tǒng)也有可能重新回到安全狀態(tài)，不過我們在分配資源之前總是要考慮到最壞的情況
? 如果系統(tǒng)處于安全狀態(tài)，就一定不會發(fā)生死鎖。如果系統(tǒng)進(jìn)入不安全狀態(tài)，就可能發(fā)生死鎖（處于不安全狀態(tài)未必就是發(fā)生了死鎖，但發(fā)生死鎖一定是不安全狀態(tài)）
? 因此可以在資源分配之前預(yù)先判斷這次分配是否會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，以此決定是否答應(yīng)資源分配請求。這也是“銀行家算法”的核心思想
- （2） 銀行家算法
數(shù)據(jù)結(jié)構(gòu)：
? 長度為 m 的一維數(shù)組 Available 表示還有多少可用資源
? nm 矩陣 Max 表示各進(jìn)程對資源的最大需求數(shù)
? nm矩陣 Allocation 表示已經(jīng)給各進(jìn)程分配了多少資源
? Max-Allocation=Need 矩陣表示各進(jìn)程最多還需要多少資源 ?
用長度為 m 的一維數(shù)組 Request 表示進(jìn)程此次申請的各種資源數(shù)文章來源：http://www.zghlxwxcb.cn/news/detail-437827.html
銀行家算法步驟：
① 檢查此次申請是否超過了之前聲明的最大需求數(shù)
② 檢查此時(shí)系統(tǒng)剩余的可用資源是否還能滿足這次請求
③ 試探著分配，更改各數(shù)據(jù)結(jié)構(gòu)
④ 用安全性算法檢查此次分配是否會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)
安全性算法步驟：
檢查當(dāng)前的剩余可用資源是否能滿足某個(gè) 進(jìn)程的最大需求，如果可以，就把該進(jìn)程加入安全序列，并把該進(jìn)程持有的資源全部回收不斷重復(fù)上述過程，看最終是否能讓所有進(jìn)程都加入安全序列文章來源地址http://www.zghlxwxcb.cn/news/detail-437827.html
6、 死鎖檢測和解除
- （1） 死鎖的檢測
為了能對系統(tǒng)是否已發(fā)生了死鎖進(jìn)行檢測，必須：
① 用某種數(shù)據(jù)結(jié)構(gòu)來保存資源的請求和分配信息；
② 提供一種算法，利用上述信息來檢測系統(tǒng)是否已進(jìn)入死鎖狀態(tài)
- （2） 死鎖的解除
一旦檢測出死鎖的發(fā)生，就應(yīng)該立即解除死鎖。并不是系統(tǒng)中所有的進(jìn)程都是死鎖狀態(tài)，用死鎖檢測算法化簡資源分配圖后，還連著邊的那些進(jìn)程就是死鎖進(jìn)程
解除死鎖的主要方法：
① 資源剝奪法。掛起（暫時(shí)放到外存上）某些死鎖進(jìn)程，并搶占它的資源，將這些資源分配給其他的死鎖進(jìn)程。但是應(yīng)防止被掛起的進(jìn)程長時(shí)間得不到資源而饑餓
② 撤銷進(jìn)程法（或稱終止進(jìn)程法）。強(qiáng)制撤銷部分、甚至全部死鎖進(jìn)程，并剝奪這些進(jìn)程的資源。這種方式的有點(diǎn)是實(shí)現(xiàn)簡單，但付出的代價(jià)可能會很大
③ 進(jìn)程回退法。讓一個(gè)或多個(gè)死鎖進(jìn)程回退到足以避免死鎖的地步。這就要求系統(tǒng)要記錄進(jìn)程的歷史信息，設(shè)置還原點(diǎn) - （3） 如何選擇回退或撤銷哪個(gè)進(jìn)程
① 進(jìn)程優(yōu)先級
② 已執(zhí)行時(shí)間
③ 還有多久能完成
④ 進(jìn)程已經(jīng)使用了多少資源
⑤ 進(jìn)程是交互式的還是批處理式的，優(yōu)先回退或撤銷批處理進(jìn)程
到了這里，關(guān)于【操作系統(tǒng)】第2章進(jìn)程同步、PV操作、死鎖的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
