本文已收錄至 Github（MD-Notes），若博客中有圖片打不開，可以來(lái)我的 Github 倉(cāng)庫(kù)：https://github.com/HanquanHq/MD-Notes，涵蓋了互聯(lián)網(wǎng)大廠面試必問(wèn)的知識(shí)點(diǎn)，講解透徹，長(zhǎng)期更新中，歡迎一起學(xué)習(xí)探討。
面試必會(huì)系列專欄：https://blog.csdn.net/sinat_42483341/category_10300357.html
操作系統(tǒng)系列專欄：https://blog.csdn.net/sinat_42483341/category_10519484.html

---

第二章 進(jìn)程管理3 - 進(jìn)程同步與互斥

目錄

• 第二章 進(jìn)程管理3 - 進(jìn)程同步與互斥
• • • 什么是進(jìn)程同步
    • 進(jìn)程互斥的原則
    • 進(jìn)程互斥的軟件實(shí)現(xiàn)方法
    • • 1、單標(biāo)志法
      • 2、雙標(biāo)志先檢查法
      • 3、雙標(biāo)志后檢查法
      • 4、Peterson 算法
    • 進(jìn)程互斥的硬件實(shí)現(xiàn)方法
    • • 1、中斷屏蔽方法
      • 2、TestAndSetLock 指令
      • • TSL和中斷屏蔽的區(qū)別
        • 利用TSL完成進(jìn)程間互斥 - 《現(xiàn)代操作系統(tǒng)》P71
      • 3、XCHG 指令
    • 信號(hào)量機(jī)制
    • • 1、整型信號(hào)量
      • 2、記錄型信號(hào)量（默認(rèn)）
      • • 記錄型信號(hào)量定義
        • P 操作（wait 操作）
        • V 操作（signal 操作）
      • 信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程互斥
      • 信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程同步 - 前 V 后 P
      • 信號(hào)量機(jī)制實(shí)現(xiàn)前驅(qū)關(guān)系 - 前 V 后 P
  • 經(jīng)典的 IPC 問(wèn)題
  • • 多生產(chǎn)者 - 多消費(fèi)者問(wèn)題
    • • • 分析同步關(guān)系（一前一后）：
        • 代碼
    • 吸煙者問(wèn)題
    • • 可以生產(chǎn)多個(gè)產(chǎn)品的單生產(chǎn)者問(wèn)題
      • 分析關(guān)系
      • • 三種組合
        • 同步關(guān)系（從事件角度分析）
        • 代碼
    • 讀者寫者問(wèn)題
    • • • 代碼
    • 哲學(xué)家就餐問(wèn)題
    • • • 關(guān)系分析
        • 如何防止死鎖的發(fā)生呢？
        • 代碼
  • 管程
  • • • • 管程的特征
  • 死鎖
  • • • 易混概念辨析
      • 死鎖產(chǎn)生的必要條件
      • • 1、互斥條件
        • 2、不剝奪條件
        • 3、請(qǐng)求和保持條件
        • 4、循環(huán)等待條件
      • 什么時(shí)候會(huì)發(fā)生死鎖
      • • 1、對(duì)系統(tǒng)資源的競(jìng)爭(zhēng)
        • 2、進(jìn)程推進(jìn)順序非法
        • 2、信號(hào)量的使用不當(dāng)
    • 死鎖的處理策略
    • • 1、預(yù)防死鎖
      • • （1）破壞互斥條件
        • • 方案
          • 缺點(diǎn)：
        • （2）破壞不剝奪條件
        • • 不剝奪條件
          • 方案
          • 缺點(diǎn)
        • （3）破壞請(qǐng)求和保持條件
        • • 請(qǐng)求和保持條件
          • 方案
          • 缺點(diǎn)
        • （4）破壞循環(huán)等待條件
        • • 循環(huán)等待條件
          • 方案
          • 原理
          • 缺點(diǎn)：
      • 2、避免死鎖
      • • 銀行家算法
        • • 銀行家算法的步驟：
          • 安全性算法的步驟：
        • 安全序列
      • 3、死鎖的檢測(cè)和解除
      • • 死鎖檢測(cè)思想：
        • 死鎖檢測(cè)算法：
        • 解除死鎖方法：

---

什么是進(jìn)程同步

知識(shí)點(diǎn)回顧：進(jìn)程具有異步性的特征。異步性是指，各并發(fā)執(zhí)行的進(jìn)程以各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)。

由于并發(fā)必然導(dǎo)致異步性。而實(shí)際應(yīng)用中，又必須按照某種順序執(zhí)行，如何解決這種異步問(wèn)題，就是“進(jìn)程同步”所討論的內(nèi)容。

同步 亦稱直接 制約關(guān)系，它是指為完成某種任務(wù)而建立的兩個(gè)或多個(gè)進(jìn)程，這些進(jìn)程因?yàn)樾枰谀承┪恢蒙?協(xié)調(diào)它們的工作次序 而產(chǎn)生的制約關(guān)系。

對(duì)臨界資源的互斥訪問(wèn)，可以在邏輯上分為如下四個(gè)部分：

進(jìn)程互斥的原則

為了實(shí)現(xiàn)對(duì)臨界資源的互斥訪問(wèn)，同時(shí)保證系統(tǒng)整體性能，需要遵循以下原則：

空閑讓進(jìn)。臨界區(qū)空閑時(shí)，可以允許一個(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ì)請(qǐng)求訪問(wèn)的進(jìn)程，應(yīng)保證能在有限時(shí)間內(nèi)進(jìn)入臨界區(qū)（保證不會(huì)饑餓）；

讓權(quán)等待。當(dāng)進(jìn)程不能進(jìn)入臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，防止進(jìn)程忙等待。

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

1、單標(biāo)志法

算法思想：兩個(gè)進(jìn)程在訪問(wèn)完臨界區(qū)后會(huì)把使用臨界區(qū)的權(quán)限轉(zhuǎn)交給另一個(gè)進(jìn)程。也就是說(shuō)，每個(gè)進(jìn)程進(jìn)入臨界區(qū)的權(quán)限只能被另一個(gè)進(jìn)程賦予。

turn 的初值為 0，即剛開始只允許 0 號(hào)進(jìn)程進(jìn)入臨界區(qū)。

該算法可以實(shí)現(xiàn)同一時(shí)刻最多只允許一個(gè)進(jìn)程訪問(wèn)臨界區(qū)，但是兩個(gè)進(jìn)程必須輪流訪問(wèn)。如果 P0 一直不訪問(wèn)臨界區(qū)，雖然臨界區(qū)空閑，但并不允許 P1 訪問(wèn)。違背“空閑讓進(jìn)”原則。

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

算法思想：設(shè)置一個(gè)布爾型數(shù)組flag[]，數(shù)組中各個(gè)元素用來(lái)標(biāo)記各進(jìn)程想進(jìn)入臨界區(qū)的意愿，比如“flag[0] = ture”意味著0 號(hào)進(jìn)程P0 現(xiàn)在想要進(jìn)入臨界區(qū)。每個(gè)進(jìn)程在進(jìn)入臨界區(qū)之前先檢查當(dāng)前有沒有別的進(jìn)程想進(jìn)入臨界區(qū)，如果沒有，則把自身對(duì)應(yīng)的標(biāo)志flag[i] 設(shè)為true，之后開始訪問(wèn)臨界區(qū)。

由于進(jìn)入?yún)^(qū)的“檢查”和“上鎖” 兩個(gè)處理不是一氣呵成的，“檢查”后、“上鎖”前 可能發(fā)生進(jìn)程切換。

主要問(wèn)題是：**違反“忙則等待”**原則，并發(fā)時(shí)可能導(dǎo)致兩個(gè)進(jìn)程同時(shí)訪問(wèn)臨界區(qū)。

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

先“上鎖”后“檢查”的方法，來(lái)避免上述問(wèn)題。

若按照①⑤②⑥的順序執(zhí)行，P0 和 P1 將無(wú)法進(jìn)入臨界區(qū)。

此方法雖然 解決了“忙則等待” 的問(wèn)題，但是又 違背了“空閑讓進(jìn)”、“有限等待”原則。

4、Peterson 算法

算法思想：結(jié)合雙標(biāo)志法、單標(biāo)志法的思想。如果雙方都爭(zhēng)著想進(jìn)入臨界區(qū)，那可以讓進(jìn)程嘗試謙讓

誰(shuí)最后設(shè)置了 turn 的值，誰(shuí)就失去了行動(dòng)的優(yōu)先權(quán)。

Peterson 算法用軟件方法解決了進(jìn)程互斥問(wèn)題，遵循了空閑讓進(jìn)、忙則等待、有限等待三個(gè)原則，但是依然未遵循讓權(quán)等待的原則（進(jìn)程無(wú)法獲得使用權(quán)的時(shí)候，一直while循環(huán)檢測(cè)，消耗CPU資源）。

Peterson 算法相較于之前三種軟件解決方案來(lái)說(shuō)是最好的，但依然不夠好。

進(jìn)程互斥的硬件實(shí)現(xiàn)方法

1、中斷屏蔽方法

與原語(yǔ)的實(shí)現(xiàn)思想相同，即在某進(jìn)程開始訪問(wèn)臨界區(qū)到結(jié)束訪問(wèn)為止，都不允許被中斷。

開中斷; 臨界區(qū); 關(guān)中斷;

優(yōu)點(diǎn)：

• 簡(jiǎn)單，高效

缺點(diǎn)：

• 不適用于多處理機(jī)
• 由于開/關(guān)中斷指令是特權(quán)指令，只能運(yùn)行在內(nèi)核態(tài)，因此只適用于內(nèi)核級(jí)進(jìn)程，不適用于用戶級(jí)進(jìn)程

2、TestAndSetLock 指令

TSL 是 Test and Set Lock 的縮寫。要實(shí)現(xiàn) TSL 需要硬件的支持。

硬件指令：

TSL RX, LOCK # 測(cè)試并加鎖

該指令所做的事情：

• 讀取 Lock 的值，存入寄存器RX中
• 給 Lock 設(shè)置一個(gè)非0值（設(shè)置到LOCK對(duì)應(yīng)的內(nèi)存中）

以上三個(gè)步驟是一個(gè) 不可拆分 的原子操作，執(zhí)行該指令的CPU將會(huì) 鎖住內(nèi)存總線（memory bus），以禁止其他CPU在本指令結(jié)束之前訪問(wèn)內(nèi)存。

TSL和中斷屏蔽的區(qū)別

當(dāng)一個(gè)CPU將中斷屏蔽后，只影響當(dāng)前屏蔽中斷的CPU，其他CPU還是依然可以照樣訪問(wèn)內(nèi)存的（想要中斷）。唯一一個(gè)當(dāng)一個(gè)CPU在訪問(wèn)內(nèi)存時(shí)阻止其他CPU訪問(wèn)內(nèi)存的方法就是將內(nèi)存總線鎖住，這個(gè)需要硬件的支持，TSL可以達(dá)到該目的。

利用TSL完成進(jìn)程間互斥 - 《現(xiàn)代操作系統(tǒng)》P71

enter_region:TSL REGISTER, LOCK /*復(fù)制鎖到寄存器并將鎖置1*/CMP REGISTER, #0 /*判斷寄存器內(nèi)容是否為0*/JNE enter_region /*若不是0，說(shuō)明鎖已經(jīng)被設(shè)置，跳轉(zhuǎn)到enter_region循環(huán)*/RET /*返回調(diào)用者，進(jìn)入臨界區(qū)*/leave_region:MOVE LOCK, #0 /*在鎖中置0*/RET /*返回調(diào)用者*/

如果LOCK的值為0，則將LOCK的值設(shè)置為1，且進(jìn)入臨界區(qū)

如果LOCK的值為1，則一直循環(huán)等待

如果多個(gè)進(jìn)程同時(shí)調(diào)用TSL，利用TSL的特性：只有一個(gè)進(jìn)程訪問(wèn)，其他的會(huì)被block

（下圖圖源王道）

3、XCHG 指令

一個(gè)可替換 TSL 的指令是 XCHG，它原子性地交換了兩個(gè)位置的內(nèi)容。它本質(zhì)上與 TSL 的解決方法一樣。

enter_region:MOVE REGISTER, #1 /*給寄存器中置1*/XCHG REGISTER, LOCK /*交換寄存器與鎖變量的內(nèi)容*/CMP REGISTER, #0 /*判斷寄存器內(nèi)容是否為0？*/JNE enter_region /*若不是0跳轉(zhuǎn)到enter_region*/RET /*返回調(diào)用者，進(jìn)入臨界區(qū)*/ leave_region:MOVE LOCK, #0 /*在鎖中置0*/RET /*返回調(diào)用者*/

優(yōu)點(diǎn)：

• 使用硬件方式實(shí)現(xiàn)簡(jiǎn)單；適用于多處理機(jī)環(huán)境

缺點(diǎn)：

• 不滿足“讓權(quán)等待”原則，暫時(shí)無(wú)法進(jìn)入臨界區(qū)的進(jìn)程會(huì)占用 CPU 資源并循環(huán)執(zhí)行 TSL 指令，導(dǎo)致忙等

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

以上所有方案都無(wú)法實(shí)現(xiàn)讓權(quán)等待，而信號(hào)量機(jī)制實(shí)現(xiàn)了讓權(quán)等待。

用戶進(jìn)程通過(guò)使用操作系統(tǒng)提供的一對(duì)原語(yǔ)來(lái)對(duì)信號(hào)量進(jìn)行操作，實(shí)現(xiàn)了進(jìn)程互斥、進(jìn)程同步。

• P 操作：申請(qǐng) / wait(S) / P(S)

• V 操作：釋放 / signal(S) / V(S)

1、整型信號(hào)量

用一個(gè) 整數(shù)型的變量 作為信號(hào)量，表示系統(tǒng)中某種資源的數(shù)量。對(duì)信號(hào)量的三種操作：

• 初始化
• P 操作（將“檢查”和“上鎖”一氣呵成，避免并發(fā) / 異步導(dǎo)致的問(wèn)題）
• V 操作

存在的問(wèn)題：不滿足“讓權(quán)等待”原則，會(huì)發(fā)生“忙等”，一直 while 占用處理機(jī)

2、記錄型信號(hào)量（默認(rèn)）

記錄型信號(hào)量定義

S.value 表示系統(tǒng)中某種資源的數(shù)目。

P 操作（wait 操作）

對(duì)信號(hào)量 S 執(zhí)行一次 P 操作，即執(zhí)行 S.value–，表示資源數(shù)減 1

若 S.value < 0 時(shí)，該資源已分配完畢，進(jìn)程調(diào)用 block 原語(yǔ)自我阻塞（運(yùn)行態(tài) -> 阻塞態(tài)），主動(dòng)放棄處理機(jī)，并插入該類資源的等待隊(duì)列 S.L 中。遵循了“讓權(quán)等待”原則。

V 操作（signal 操作）

對(duì)信號(hào)量 S 執(zhí)行一次 V 操作，即執(zhí)行 S.value++，表示資源數(shù)加 1

若 S.value <= 0，仍有進(jìn)程在等待資源，則調(diào)用 wakeup 原語(yǔ)喚醒等待隊(duì)列中第一個(gè)進(jìn)程（阻塞態(tài) -> 就緒態(tài)）

信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程互斥

分析并發(fā)進(jìn)程的關(guān)鍵活動(dòng)，劃定臨界區(qū)（如：對(duì)臨界資源打印機(jī)的訪問(wèn)就應(yīng)放在臨界區(qū)）

設(shè)置互斥信號(hào)量 mutex，初值為 1

在進(jìn)入?yún)^(qū) P(mutex)——申請(qǐng)資源

在退出區(qū) V(mutex)——釋放資源

信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程同步 - 前 V 后 P

分析什么地方需要實(shí)現(xiàn)“同步關(guān)系”，即必須保證“一前一后”執(zhí)行的兩個(gè)操作

設(shè)置同步信號(hào)量 S, 初始為 0

在“前操作”之后執(zhí)行 V(S)

在“后操作”之前執(zhí)行 P(S)

P2 需要這種資源，而只有 P1 才能產(chǎn)生這種資源。即，只有執(zhí)行了 V 操作之后，P 操作之后的代碼才會(huì)執(zhí)行。

信號(hào)量機(jī)制實(shí)現(xiàn)前驅(qū)關(guān)系 - 前 V 后 P

進(jìn)程P1 中有句代碼S1，P2 中有句代碼S2 ，P3中有句代碼S3 …… P6 中有句代碼S6。這些代碼要求按如下前驅(qū)圖所示的順序來(lái)執(zhí)行：

其實(shí)每一對(duì)前驅(qū)關(guān)系都是一個(gè)進(jìn)程同步問(wèn)題（需要保證一前一后的操作）因此，

要為每一對(duì)前驅(qū)關(guān)系各設(shè)置一個(gè)同步信號(hào)量

在“前操作”之后對(duì)相應(yīng)的同步信號(hào)量執(zhí)行V 操作

在“后操作”之前對(duì)相應(yīng)的同步信號(hào)量執(zhí)行P 操作

經(jīng)典的 IPC 問(wèn)題

生產(chǎn)者、消費(fèi)者共享一個(gè)初始為空、大小為n的緩沖區(qū)。緩沖區(qū)是臨界資源，各進(jìn)程必須互斥地訪問(wèn)。

• 若緩沖區(qū) 不滿，生產(chǎn)者可以 生產(chǎn) -> V(full) 釋放

• 若緩沖區(qū) 非空，消費(fèi)者可以 消費(fèi) -> P(full) 申請(qǐng)

仍然滿足 前 V 后 P：consumer 需要這種資源，而只有 producer 才能產(chǎn)生這種資源。即，只有執(zhí)行了 V(full) 操作之后，P(full) 操作之后的代碼才會(huì)執(zhí)行。

semaphore mutex = 1; // 互斥信號(hào)量，實(shí)現(xiàn)對(duì)緩沖區(qū)的互斥訪問(wèn) semaphore empty = n; // 同步信號(hào)量，表示空閑緩沖區(qū)的數(shù)量 semaphore full = 0; // 同步信號(hào)量，表示產(chǎn)品的數(shù)量，也即非空緩沖區(qū)的數(shù)量producer (){ // 生產(chǎn)者while(1){生產(chǎn)一個(gè)產(chǎn)品;P(empty); // 實(shí)現(xiàn)互斥的 P 操作必須在實(shí)現(xiàn)同步的 P 操作之后，否則會(huì)導(dǎo)致死鎖P(mutex);把產(chǎn)品放入緩沖區(qū);V(mutex); // 可以改變相鄰 V 操作的順序V(full);} }consumer (){ // 消費(fèi)者while(1){P(full);P(mutex);從緩沖區(qū)取出一個(gè)產(chǎn)品;V(mutex);V(empty);使用產(chǎn)品;} }

多生產(chǎn)者 - 多消費(fèi)者問(wèn)題

桌上有一盤子，每次只能放入一個(gè)水果。爸爸只放蘋果，媽媽只放橘子，兒子只吃橘子，女兒只吃蘋果。

盤子空才能放，盤子有正確的水果才能取。用 PV 操作實(shí)現(xiàn)上述過(guò)程。

生產(chǎn)者生產(chǎn)的產(chǎn)品、消費(fèi)者消費(fèi)的產(chǎn)品類別各不相同。

分析同步關(guān)系（一前一后）：

父親將蘋果放入盤子后，女兒才能取蘋果

母親將橘子放入盤子后，兒子才能取橘子

只有盤子為空時(shí)，父親或母親才能放入水果

總結(jié)：在生產(chǎn)者-消費(fèi)者問(wèn)題中，如果緩沖區(qū)大小為1，那么有可能不需要設(shè)置互斥信號(hào)量就可以實(shí)現(xiàn)互斥訪問(wèn)緩沖區(qū)的功能。這不是絕對(duì)的，要具體問(wèn)題具體分析。

建議：在考試中如果來(lái)不及仔細(xì)分析，可以加上互斥信號(hào)量，保證各進(jìn)程一定會(huì)互斥地訪問(wèn)緩沖區(qū)。但需要注意的是，實(shí)現(xiàn)互斥的 P 操作一定要在實(shí)現(xiàn)同步的 P 操作之后，否則可能引起“死鎖”。

代碼

// semaphore mutex = 1; // 實(shí)現(xiàn)互斥訪問(wèn)盤子（緩沖區(qū)） semaphore apple = 0; // 盤子中有幾個(gè)蘋果 semaphore orange = 0; // 盤子中有幾個(gè)橘子 semaphore plate = 1; // 盤子中還可以放多少個(gè)水果 dad (){while(1){準(zhǔn)備一個(gè)蘋果;P(plate); // P 申請(qǐng)盤子里的一個(gè)空位把蘋果放入盤子;V(apple); // V 釋放一個(gè)蘋果} } mom (){while(1){準(zhǔn)備一個(gè)橘子;P(plate);把橘子放入盤子;V(orange);} } daughter (){while(1){P(apple); // P 申請(qǐng)一個(gè)蘋果從盤中取出蘋果;V(plate); // V 釋放盤子一個(gè)空位吃掉蘋果;} } son(){while(1){P(orange);從盤中取出橘子;V(plate);吃掉橘子;} }

吸煙者問(wèn)題

可以生產(chǎn)多個(gè)產(chǎn)品的單生產(chǎn)者問(wèn)題

系統(tǒng)中有 三個(gè)抽煙者進(jìn)程，每個(gè)抽煙者不斷地卷煙并抽煙。抽煙者卷起并抽掉一顆煙需要有三種材料：煙草、紙、膠水。一個(gè)抽煙者有煙草，一個(gè)有紙，另一個(gè)有膠水。

系統(tǒng)中還有 一個(gè)供應(yīng)者進(jìn)程，它們無(wú)限地供應(yīng)所有三種材料，但每次僅輪流提供三種材料中的兩種。

得到缺失的兩種材料的抽煙者在卷起并抽掉一顆煙后，會(huì)發(fā)信號(hào)通知供應(yīng)者，讓它繼續(xù)提供另外的兩種材料。這一過(guò)程重復(fù)進(jìn)行。

請(qǐng)用以上介紹的 IPC 同步機(jī)制編程，實(shí)現(xiàn)該問(wèn)題要求的功能。

分析關(guān)系

桌子：容量為1的緩沖區(qū)，要互斥訪問(wèn)

三種組合

紙 + 膠水

煙草 + 膠水

煙草 + 紙

同步關(guān)系（從事件角度分析）

桌上有組合 1 -> 第 1 個(gè)抽煙者取走東西

桌上有組合 2 -> 第 2 個(gè)抽煙者取走東西

桌上有組合 3 -> 第 3 個(gè)抽煙者取走東西

發(fā)出完成信號(hào) -> 供應(yīng)者將下一個(gè)組合放到桌上

代碼

不需要設(shè)置一個(gè)專門的同步信號(hào)量。因?yàn)榫彌_區(qū)大小為 1，故同一時(shí)刻，四個(gè)同步信號(hào)量中至多有一個(gè)為 1。

semaphore offer1 = 0; // 桌上組合一的數(shù)量 semaphore offer2 = 0; // 桌上組合二的數(shù)量 semaphore offer3 = 0; // 桌上組合三的數(shù)量 semaphore finish = 0; // 抽煙是否完成 int i = 0; // 用于實(shí)現(xiàn)“三個(gè)抽煙者輪流流抽煙”provider (){while(1){if(i==0) {將組合一放桌上;V(offer1);} else if(i==1){將組合二放桌上;V(offer2);} else if(i==2){將組合三放桌上;V(offer3);}i = (i+1)%3;P(finish);} }smoker1 (){while(1){P(offer1);從桌上拿走組合一；卷煙；抽掉；V(finish);} }smoker2 (){while(1){P(offer2);從桌上拿走組合二；卷煙；抽掉；V(finish);} }smoker3 (){while(1){P(offer3);從桌上拿走組合三；卷煙；抽掉；V(finish);} }

讀者寫者問(wèn)題

有讀者、寫者兩組并發(fā)進(jìn)程，共享一個(gè)文件。規(guī)則：

• 允許 多個(gè)讀者 同時(shí) 讀 文件
• 只允許 一個(gè)寫者 寫文件
• 寫完成 之前 不允許讀
• 讀完成 之前 不允許寫

互斥關(guān)系

• 互斥：寫 - 寫 / 寫 - 讀

• 不互斥：讀 - 讀

代碼

讀寫公平法：即使連續(xù)有 多個(gè)讀者 到來(lái)，也 不會(huì)使寫者一直饑餓，是相對(duì)公平的先來(lái)連服務(wù)原則。

semaphore rw = 1; // 讀寫信號(hào)量，實(shí)現(xiàn)只讀或只寫（互斥訪問(wèn)） int count = 0; // 記錄當(dāng)前有幾個(gè)讀者程在訪問(wèn)文件 semaphore mutex = 1; // 用于保證對(duì)count變量的互斥訪問(wèn) semaphore w = 1; // 用于保證寫者不會(huì)饑餓writer (){ // 寫者while(1){P(w); // 用于保證寫者不會(huì)饑餓P(rw); // 寫者申請(qǐng)一個(gè)讀寫信號(hào)量（意味著只寫）寫文件;V(rw);V(w);} }reader (){ // 讀者while(1){P(w); // 用于保證寫者不會(huì)饑餓P(mutex); // 對(duì)count操作前，需要申請(qǐng)count變量的獨(dú)占if(count == 0){ // 沒有讀者P(rw); // 讀者申請(qǐng)一個(gè)讀寫信號(hào)量（意味著只讀）}count++; // 全局變量增加一個(gè)寫進(jìn)程V(mutex); // 釋放count變量的獨(dú)占V(w);讀文件;P(mutex);count--;if(count == 0){V(rw);}V(mutex);} }

哲學(xué)家就餐問(wèn)題

圓桌坐著 5 名哲學(xué)家，每?jī)蓚€(gè)哲學(xué)家之間有一根筷子，哲學(xué)家交替進(jìn)行思考和進(jìn)餐。進(jìn)餐時(shí)，試圖一根一根拿起左、右兩根筷子，只有同時(shí)拿起兩根筷子才能進(jìn)餐，否則需要等待。進(jìn)餐完畢后，哲學(xué)家放下筷子繼續(xù)思考。

關(guān)系分析

• 5 個(gè)哲學(xué)家進(jìn)程
• 相鄰哲學(xué)家對(duì)中間筷子的訪問(wèn)是互斥關(guān)系

每個(gè)哲學(xué)家進(jìn)程需要同時(shí)持有兩個(gè)臨界資源才能開始吃飯。如何避免死鎖現(xiàn)象，才是哲學(xué)家問(wèn)題的精髓。

定義互斥信號(hào)量數(shù)組 chopstick[5] = {1, 1, 1, 1, 1} 用于實(shí)現(xiàn)對(duì) 5 個(gè)筷子的互斥訪問(wèn)。并對(duì)哲學(xué)家按 0 ~ 4 編號(hào)，哲學(xué)家 i 左邊的筷子編號(hào)為 i，右邊的筷子編號(hào)為 (i + 1) % 5

如何防止死鎖的發(fā)生呢？

有很多種方式，舉幾個(gè)例子：

最多允許四個(gè)哲學(xué)家同時(shí)進(jìn)餐，這樣保證至少有一個(gè)哲學(xué)家能拿到左右兩只筷子.

奇數(shù)號(hào)哲學(xué)家先拿左邊的筷子再拿右邊的筷子，偶數(shù)號(hào)哲學(xué)家相反。這樣保證如果相鄰的兩個(gè)奇偶號(hào)哲學(xué)家都想吃飯，那么只會(huì)有其中一個(gè)可以拿起第一只筷子。

僅當(dāng)一個(gè)哲學(xué)家左右兩支筷子都可用時(shí)，才允許他抓起筷子。

代碼

思想：使用 mutex 來(lái)實(shí)現(xiàn) 只允許一個(gè)哲學(xué)家 處于 只拿起了一只筷子的狀態(tài)

semaphore chopstick[5]={1,1,1,1,1}; semaphore mutex = 1; // 互斥地取筷子 Pi (){ // i 號(hào)哲學(xué)家的進(jìn)程while(1){P(mutex);P(chopstick[i]); // 拿左P(chopstick[(i+1)%5]); // 拿右V(mutex);吃飯;V(chopstick[i]); // 放左V(chopstick[(i+1)%5]); // 放右思考;} }

管程

《現(xiàn)代操作系統(tǒng)》P79

由于使用信號(hào)量時(shí)要非常小心，而且出現(xiàn)的錯(cuò)誤都是競(jìng)爭(zhēng)條件、死鎖以及其它一些不可預(yù)測(cè)或不可再現(xiàn)的行為，而為了更易于編寫正確的程序，提出了一種高級(jí)同步原語(yǔ)，稱為管程（monitor）

一個(gè) 管程 是由一個(gè)過(guò)程、變量及數(shù)據(jù)結(jié)構(gòu)等組成的一個(gè)集合，它們組成一個(gè) 特殊的模塊 或 軟件包。

管程有一個(gè)很重要的特性：任一時(shí)刻，管程中只能有一個(gè)活躍進(jìn)程。

管程是編程語(yǔ)言的組成部分，編譯器知道它們的特殊性，因此可以采用與其它過(guò)程調(diào)用不同的方法來(lái)處理對(duì)管程的調(diào)用。由編譯器而非程序員來(lái)安排互斥，出錯(cuò)的可能性要小很多。

• Java 的 syncronized 就是一個(gè)管程，也可使用 wait() / notify() 實(shí)現(xiàn)進(jìn)程的同步。

• C，Pascal 以及多數(shù)其他語(yǔ)言都沒有管程。

管程的特征

局部于管程的數(shù)據(jù)只能被局部于管程的過(guò)程所訪問(wèn)

一個(gè)進(jìn)程只有通過(guò)調(diào)用管程內(nèi)的過(guò)程，才能進(jìn)入管程訪問(wèn)共享數(shù)據(jù)

每次只允許一個(gè)進(jìn)程在管程內(nèi)執(zhí)行某個(gè)內(nèi)部過(guò)程

死鎖

易混概念辨析

死鎖：各進(jìn)程互相等待對(duì)方手里的資源，導(dǎo)致各進(jìn)程都阻塞，無(wú)法向前推進(jìn)（操作系統(tǒng)考慮）

饑餓：由于長(zhǎng)期得不到想要的資源，某進(jìn)程無(wú)法向前推進(jìn)（操作系統(tǒng)考慮）

死循環(huán)：某進(jìn)程執(zhí)行過(guò)程中一直跳不出某個(gè)循環(huán)，是可以上處理機(jī)運(yùn)行的（開發(fā)人員考慮）

死鎖產(chǎn)生的必要條件

1、互斥條件

只有對(duì)必須互斥使用的資源的爭(zhēng)搶才會(huì)導(dǎo)致死鎖（如哲學(xué)家的筷子、打印機(jī)設(shè)備）。像內(nèi)存、揚(yáng)聲器這樣可以同時(shí)讓多個(gè)進(jìn)程使用的資源是不會(huì)導(dǎo)致死鎖的（因?yàn)檫M(jìn)程不用阻塞等待這種資源）。

2、不剝奪條件

進(jìn)程所獲得的資源在未使用完之前，不能由其他進(jìn)程強(qiáng)行奪走，只能主動(dòng)釋放。

3、請(qǐng)求和保持條件

進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又提出了新的資源請(qǐng)求，而該資源又被其他進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程被阻塞，但又對(duì)自己已有的資源保持不放。

4、循環(huán)等待條件

存在一種進(jìn)程資源的循環(huán)等待鏈，鏈中的每一個(gè)進(jìn)程已獲得的資源同時(shí)被下一個(gè)進(jìn)程所請(qǐng)求。

什么時(shí)候會(huì)發(fā)生死鎖

1、對(duì)系統(tǒng)資源的競(jìng)爭(zhēng)

各進(jìn)程對(duì)不可剝奪的資源（如打印機(jī)）的競(jìng)爭(zhēng)可能引起死鎖，對(duì)可剝奪的資源（CPU）的競(jìng)爭(zhēng)是不會(huì)引起死鎖的。

2、進(jìn)程推進(jìn)順序非法

請(qǐng)求和釋放資源的順序不當(dāng)，也同樣會(huì)導(dǎo)致死鎖。例如，并發(fā)執(zhí)行的進(jìn)程P1、P2 分別申請(qǐng)并占有R1、R2，之后進(jìn)程P1申請(qǐng)R2，進(jìn)程P2申請(qǐng)R1，兩者因?yàn)樯暾?qǐng)的資源被對(duì)方占有而阻塞，發(fā)生死鎖。

2、信號(hào)量的使用不當(dāng)

如生產(chǎn)者-消費(fèi)者問(wèn)題中，如果實(shí)現(xiàn)互斥的P操作在實(shí)現(xiàn)同步的P操作之前，就有可能導(dǎo)致死鎖。（可以把互斥信號(hào)量、同步信號(hào)量也看做是一種抽象的系統(tǒng)資源）

死鎖的處理策略

1、預(yù)防死鎖

破壞死鎖產(chǎn)生的四個(gè)必要條件中的一個(gè)或幾個(gè)。

（1）破壞互斥條件

方案

把只能互斥使用的資源改造為允許共享使用，則系統(tǒng)不會(huì)進(jìn)入死鎖狀態(tài)。比如，操作系統(tǒng)可以采用 SPOOLing 技術(shù)把獨(dú)占設(shè)備在邏輯上改造成共享設(shè)備。

缺點(diǎn)：

并不是所有的資源都可以改造成可共享使用的資源。很多時(shí)候無(wú)法破壞互斥條件。

（2）破壞不剝奪條件

不剝奪條件

進(jìn)程所獲得的資源在未使用完之前，不能由其他進(jìn)程強(qiáng)行奪走，只能主動(dòng)釋放。

方案

• 方案一：當(dāng)某個(gè)進(jìn)程請(qǐng)求新的資源得不到滿足時(shí)，它必須立即釋放保持的所有資源，待以后需要時(shí)再重新申請(qǐng)。也就是說(shuō)，即使某些資源尚未使用完，也需要主動(dòng)釋放，從而破壞了不可剝奪條件。
• 方案二：當(dāng)某個(gè)進(jìn)程需要的資源被其他進(jìn)程所占有的時(shí)候，可以由操作系統(tǒng)協(xié)助，將想要的資源強(qiáng)行剝奪。這種方式一般需要考慮各進(jìn)程的優(yōu)先級(jí)（比如：剝奪調(diào)度方式，就是將處理機(jī)資源強(qiáng)行剝奪給優(yōu)先級(jí)更高的進(jìn)程使用）

缺點(diǎn)

實(shí)現(xiàn)起來(lái)比較復(fù)雜。

釋放已獲得的資源可能造成前一階段工作的失效，因此只適用于易保存和恢復(fù)狀態(tài)的資源，如CPU。

反復(fù)申請(qǐng)釋放資源，增加系統(tǒng)開銷，降低系統(tǒng)吞吐量。

方案一會(huì)導(dǎo)致進(jìn)程饑餓。

（3）破壞請(qǐng)求和保持條件

請(qǐng)求和保持條件

進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又提出了新的資源請(qǐng)求，而該資源又被其他進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程被阻塞，但又對(duì)自己已有的資源保持不放。

方案

采用 靜態(tài)分配 方法，進(jìn)程在運(yùn)行前，一次申請(qǐng)完它需要的全部資源才能投入運(yùn)行。一旦投入運(yùn)行，一直保持資源，且不再請(qǐng)求別的任何資源，直到運(yùn)行結(jié)束，釋放資源。

缺點(diǎn)

進(jìn)程整個(gè)運(yùn)行期間一直保持所有資源，造成資源浪費(fèi)

可能導(dǎo)致某些進(jìn)程饑餓（請(qǐng)求資源多的進(jìn)程難以集齊所有資源）

（4）破壞循環(huán)等待條件

循環(huán)等待條件

存在一種進(jìn)程資源的循環(huán)等待鏈，鏈中的每一個(gè)進(jìn)程已獲得的資源同時(shí)被下一個(gè)進(jìn)程所請(qǐng)求。

方案

順序資源分配法。首先給系統(tǒng)中的資源編號(hào)，規(guī)定每個(gè)進(jìn)程必須按編號(hào)遞增的順序請(qǐng)求資源，同類資源（即編號(hào)相同的資源）一次申請(qǐng)完。

原理

一個(gè)進(jìn)程只有已占有小編號(hào)的資源時(shí)，才有資格申請(qǐng)更大編號(hào)的資源。

• 任一時(shí)刻，總有一進(jìn)程擁有的資源編號(hào)是最大的，此進(jìn)程對(duì)其余資源的獲取必暢通無(wú)阻
• 已持有大編號(hào)資源的進(jìn)程不可能逆向地回來(lái)申請(qǐng)小編號(hào)的資源，從而就不會(huì)產(chǎn)生循環(huán)等待的現(xiàn)象

缺點(diǎn)：

不方便增加新的設(shè)備，因?yàn)榭赡苄枰匦路峙渌械木幪?hào)；

進(jìn)程實(shí)際使用資源的順序可能和編號(hào)遞增順序不一致，會(huì)導(dǎo)致資源浪費(fèi)；

必須按規(guī)定次序申請(qǐng)資源，用戶編程不便。

2、避免死鎖

用某種方法防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免死鎖（銀行家算法）

銀行家算法

一個(gè)小城鎮(zhèn)的銀行家向一群客戶分別承諾了一定的貸款額度，只有當(dāng)借款總數(shù)達(dá)到客戶最大要求時(shí)，客戶才歸還貸款，否則無(wú)論之前借了多少錢，都拿不回來(lái)。

銀行家算法的步驟：

檢查此次申請(qǐng)是否超過(guò)之前聲明的最大需求數(shù)

檢查此時(shí)系統(tǒng)剩余可用資源是否還能滿足此次請(qǐng)求

試探分配，更各個(gè)改數(shù)據(jù)結(jié)構(gòu)

用安全型算法檢查此次分配是否會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)

安全性算法的步驟：

檢查當(dāng)前剩余可用資源是否能滿足某個(gè)資源的最大需求，如果可以，就將該進(jìn)程加入安全序列

等到這個(gè)進(jìn)程執(zhí)行完畢就將它占有的全部資源回收

不斷重復(fù)上述過(guò)程，看看最終是否能讓所有進(jìn)程都加入安全序列

安全序列

所謂的安全序列，就是指系統(tǒng)如果按照這種序列分配資源，則每個(gè)進(jìn)程都能順利完成。只要能找出一個(gè)安全序列，系統(tǒng)就處于安全狀態(tài)。當(dāng)然，安全序列可以有多個(gè)。

一個(gè) 找不到 安全序列的例子：（剩余資源總數(shù) 3 3 2）可以拓展到有 n 個(gè)進(jìn)程，m 種資源

進(jìn)程最大需求已分配最多還需要

P0	8 5 3	0 1 0	8 4 3
P1	3 2 2	2 0 0	1 2 2
P2	9 5 2	3 0 2	6 5 0
P3	2 2 2	2 1 1	0 1 1
P4	4 3 6	0 0 2	4 3 4

3、死鎖的檢測(cè)和解除

允許死鎖的發(fā)生，不過(guò)操作系統(tǒng)會(huì)負(fù)責(zé)檢測(cè)出死鎖的發(fā)生，然后采取某種措施解除死鎖。

• 死鎖檢測(cè)算法：用于檢測(cè)系統(tǒng)狀態(tài)，以確定系統(tǒng)中是否發(fā)生了死鎖。
• 死鎖解除算法：當(dāng)認(rèn)定系統(tǒng)中已經(jīng)發(fā)生了死鎖，利用該算法可將系統(tǒng)從死鎖狀態(tài)中解脫出來(lái)。

死鎖檢測(cè)思想：

依次消除與不阻塞進(jìn)程相連的邊，直到無(wú)邊可消。

• 如果最終 能消除所有邊，就稱這個(gè)圖是可完全簡(jiǎn)化的。此時(shí)一定沒有發(fā)生死鎖（即找到一個(gè) 安全序列）

• 如果最終 不能消除所有邊，那么此時(shí)就是 發(fā)生了死鎖。剩余連著邊的進(jìn)程，就是處于死鎖狀態(tài)的進(jìn)程。

死鎖檢測(cè)算法：

在資源分配圖中，找出既不阻塞又不是孤點(diǎn)的進(jìn)程 Pi，消去它所有的請(qǐng)求邊和分配變，使之稱為孤立的結(jié)點(diǎn)。上圖中的 P1 是滿足這一條件的進(jìn)程結(jié)點(diǎn)，于是將 P1 的所有邊消去。

進(jìn)程 Pi 所釋放的資源，可以喚醒某些等待這些資源的阻塞進(jìn)程，原來(lái)的阻塞進(jìn)程可能變?yōu)榉亲枞M(jìn)程（下圖 P2）。重復(fù)整個(gè)過(guò)程，若能消去途中所有的邊，則稱該圖是可完全簡(jiǎn)化的。

解除死鎖方法：

資源剝奪法。掛起（暫時(shí)放到外存上）某些死鎖進(jìn)程，并搶占它的資源，分配給其他的死鎖進(jìn)程。

撤銷進(jìn)程法（或稱終止進(jìn)程法）。強(qiáng)制撤銷部分、甚至全部死鎖進(jìn)程，并剝奪這些進(jìn)程的資源。

進(jìn)程回退法。讓一個(gè) / 多個(gè)死鎖進(jìn)程回退到足以避免死鎖的地步。要求系統(tǒng)要記錄進(jìn)程的歷史信息，設(shè)置還原點(diǎn)。

總結(jié)

以上是生活随笔為你收集整理的操作系统：第二章 进程管理3 - 进程同步与互斥的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。