第11章：死鎖和進(jìn)程通信

• 死鎖概念
• 死鎖處理方法
• 死鎖預(yù)防（Deadlock Prevention）
• 死鎖避免（Deadlock Avoidance）
• 死鎖檢測(cè)和恢復(fù)（Deadlock Detection & Recovery）
• 死鎖檢測(cè)和恢復(fù)（Deadlock Detection & Recovery）
• 由應(yīng)用進(jìn)程處理死鎖
• 銀行家算法
• 死鎖檢測(cè)
• 進(jìn)程和通信概念
• 信號(hào)和管道
• 消息隊(duì)列和共享內(nèi)存

11.1 死鎖概念

• defs：死鎖是進(jìn)程之間由于共享資源所導(dǎo)致的一種無(wú)限期等待的情況

  • 由于競(jìng)爭(zhēng)資源或者通信關(guān)系，兩個(gè)或更多線程在執(zhí)行中出現(xiàn)永遠(yuǎn)相互等待售滤，只能由其他進(jìn)程引發(fā)的事件

進(jìn)程訪問(wèn)資源的流程

• 資源類型R1,R2,…,Rm

  • CPU執(zhí)行時(shí)間，內(nèi)存空間龄减，I/O設(shè)備等

• 每類資源Ri有Wi個(gè)實(shí)例

• 進(jìn)程訪問(wèn)資源的流程

  • 請(qǐng)求/獲取

    • 申請(qǐng)空閑資源

  • 使用/占用

    • 進(jìn)程占用資源

  • 釋放

    • 資源狀態(tài)由占用變成空閑

資源分類

• 可重用資源（Reusable Resource）

  • 資源不能被刪除且在任何時(shí)刻只能有一個(gè)進(jìn)程使用

  • 進(jìn)程釋放資源后甜无，其他進(jìn)程可重用

  • 可重用資源示例

    • 硬件：處理器、I/O通道、主和副存儲(chǔ)器碗旅、設(shè)備等
    • 軟件：文件渡处、數(shù)據(jù)庫(kù)和信號(hào)量等數(shù)據(jù)結(jié)構(gòu)

  • 可能出現(xiàn)死鎖

    • 每個(gè)進(jìn)程應(yīng)用一部分資源并請(qǐng)求其他資源

• 消耗資源（Consumable resource）

  • 資源創(chuàng)建和銷毀

  • 資源消耗示例

    • 在I/O緩沖區(qū)的中斷、信號(hào)和消息等

  • 可能會(huì)出現(xiàn)死鎖

    • 進(jìn)程間相互等待接收對(duì)方的消息

出現(xiàn)死鎖的必要條件

• 互斥

  • 任何時(shí)刻只能有一個(gè)進(jìn)程使用一個(gè)資源實(shí)例

• 持有并等待

  • 進(jìn)程保持至少一個(gè)資源祟辟，并正在等待獲取其他進(jìn)程特有的資源

• 非搶占

  • 資源只能在進(jìn)程使用后自愿釋放

• 循環(huán)等待

11.2 死鎖處理方法

• 死鎖預(yù)防（Deadlock Prevention）

  • 確保系統(tǒng)永遠(yuǎn)不會(huì)進(jìn)入死鎖狀態(tài)

• 死鎖避免（Deadlock Avoidance）

  • 在使用前進(jìn)行判斷医瘫，只允許不會(huì)出現(xiàn)死鎖的進(jìn)程請(qǐng)求資源

• 死鎖檢測(cè)和恢復(fù)（Deadlock Detection & Recovery）

  • 在檢測(cè)到運(yùn)行系統(tǒng)進(jìn)入死鎖狀態(tài)后，進(jìn)行恢復(fù)

• 由應(yīng)用進(jìn)程處理死鎖

  • 通常操作系統(tǒng)忽略死鎖

    • 大多數(shù)操作系統(tǒng)（包括UNIX）的做法

（一）死鎖預(yù)防：限制申請(qǐng)方式

• 預(yù)防是采用某種策略旧困，限制并發(fā)進(jìn)程對(duì)資源的請(qǐng)求醇份，使系統(tǒng)在任何時(shí)刻都不滿足死鎖的必要條件

• 互斥

  • 把互斥的共享資源封裝成可同時(shí)訪問(wèn)

• 持有并等待

  • 進(jìn)程請(qǐng)求資源時(shí)，要求它不持有任何其他資源
  • 僅允許進(jìn)程在開(kāi)始執(zhí)行時(shí)吼具，一次請(qǐng)求所有需要的資源
  • 資源利用率低

• 非搶占

  • 如進(jìn)程請(qǐng)求不能立即分配的資源僚纷，則釋放已有資源
  • 只在能夠同時(shí)獲得所有需要資源時(shí)，才執(zhí)行分配操作

• 循環(huán)等待

  • 對(duì)資源排序馍悟，要求進(jìn)程按順序請(qǐng)求資源

（二）死鎖避免

• 利用額外的先驗(yàn)信息畔濒，在分配資源時(shí)判斷是否會(huì)出現(xiàn)死鎖，只在不會(huì)死鎖時(shí)分配資源

  • 要求進(jìn)程聲明需要資源的最大數(shù)目
  • 限定提供與分配的資源數(shù)量锣咒，確保滿足進(jìn)程的最大需求
  • 動(dòng)態(tài)檢查資源分配狀態(tài)侵状，確保不會(huì)出現(xiàn)環(huán)形等待

系統(tǒng)資源分配的安全狀態(tài)

• 當(dāng)進(jìn)程請(qǐng)求資源時(shí)，系統(tǒng)判斷分配后是否處于安全狀態(tài)

• 系統(tǒng)處于安全狀態(tài)

  • 針對(duì)所有已占用進(jìn)程毅整，存在安全序列

• 序列

安全狀態(tài)與死鎖的關(guān)系

• 系統(tǒng)處于安全狀態(tài)趣兄，一定沒(méi)有死鎖

• 系統(tǒng)處于不安全狀態(tài)，可能出現(xiàn)死鎖

  • 避免死鎖就是確保系統(tǒng)不會(huì)進(jìn)入不安全狀態(tài)

11.3 銀行家算法

• 銀行家算法是一個(gè)避免死鎖產(chǎn)生的算法悼嫉，以銀行借貸發(fā)配策略為基礎(chǔ)艇潭，判斷并保證系統(tǒng)處于安全狀態(tài)

銀行家算法：數(shù)據(jù)結(jié)構(gòu)

• n = 線程數(shù)量， m = 資源類型數(shù)量

• Max（總需求量）：n×m矩陣

  • 線程Ti最多請(qǐng)求類型Rj的資源 Max[i,j]個(gè)實(shí)例

• Available（剩余空閑量）：長(zhǎng)度為m的向量

  • 當(dāng)前有Available[i]個(gè)類型Rj的資源實(shí)例可用

• Allocation（已分配量）：n×m矩陣

  • 線程Ti當(dāng)前分配了 Allocation[i,j]個(gè)Rj的實(shí)例

• Need（未來(lái)需要量）：n×m矩陣

  • 線程Ti未來(lái)需要Need[i,j]個(gè)Rj資源實(shí)例

• Need[i,j] = Max[i,j] - Allocation[i,j]

銀行家算法：安全狀態(tài)判斷

1. Work 和 Finish 分別是長(zhǎng)度為m和n的向量初始化：
    Work = Available //當(dāng)前資源剩余空閑量
    Finish[i] = false for i:1,2,...,n //線程i沒(méi)結(jié)束
2. 尋找線程Ti：
    (a)Finish[i] = false //接下來(lái)找出Need比Work小的線程i 
    (b) Need[i] <= Work
    沒(méi)有找到滿足的條件Ti戏蔑，轉(zhuǎn)4
3. Work = Work + Allocation[i] //線程i的資源需求量小于當(dāng)前剩余空閑資源量蹋凝，所以配置給它再回收
    Finish[i] = true
    轉(zhuǎn)2
4. 如所有線程Ti滿足Finish[i] == true，則系統(tǒng)處于安全狀態(tài) //所有線程的Finish為True总棵，表明系統(tǒng)處于安全狀態(tài)

銀行家算法

初始化：Requesti 線程Ti的資源請(qǐng)求向量
        Requesti [j] 線程Ti請(qǐng)求資源Rj的實(shí)例

循環(huán)：
1\. 如果Requesti <= Need[i]鳍寂，轉(zhuǎn)到2。否則拒絕資源申請(qǐng)情龄，因?yàn)榫€程已經(jīng)超過(guò)了其最大要求
2\. 如果Requesti <= Available迄汛，轉(zhuǎn)到3。否則骤视，Ti必須等待鞍爱，因?yàn)橘Y源不可用
3\. 通過(guò)安全狀態(tài)來(lái)確定是否分配資源給Ti：
    生成一個(gè)需要判斷狀態(tài)是否安全的資源分配環(huán)境
        Available = Available - Requesti;
        Allocation[i] = Allocation[i] + Requesti;
        Need[i] = Need[i] - Requesti;
    調(diào)用安全狀態(tài)判斷
        如果返回結(jié)果是安全，將資源分配給Ti
        如果返回結(jié)果不安全专酗，系統(tǒng)會(huì)拒絕Ti的資源請(qǐng)求

11.4 死鎖檢測(cè)

• 允許系統(tǒng)進(jìn)入死鎖狀態(tài)
• 維護(hù)系統(tǒng)的資源分配圖
• 定期調(diào)用死鎖檢測(cè)算法來(lái)搜索圖中是否存在死鎖
• 出現(xiàn)死鎖時(shí)睹逃，用死鎖恢復(fù)機(jī)制進(jìn)行恢復(fù)

死鎖檢測(cè)：數(shù)據(jù)結(jié)構(gòu)

• Available：長(zhǎng)度為m的向量

  • 每種類型可用資源的數(shù)量

• Allocation：一個(gè) n×m矩陣

  • 當(dāng)前分配給各個(gè)進(jìn)程每種類型資源的數(shù)量
  • 進(jìn)程Pi擁有資源Rj的Allocation[i,j]個(gè)實(shí)例

死鎖檢測(cè)算法

1. Work 和 Finish 分別是長(zhǎng)度為m和n的向量初始化：
    Work = Available //Work為當(dāng)前資源剩余空閑量
    Allocation[i] > 0 時(shí)，F(xiàn)inish[i] = false //finish為線程是否結(jié)束
    否則祷肯，F(xiàn)inish[i] = true
2. 尋找線程Ti滿足：
    (a)Finish[i] = false //尋找沒(méi)有結(jié)束的線程唯卖，且此線程將需要的資源量小于當(dāng)前空閑資源量
    (b) Requesti <= Work
    沒(méi)有找到滿足的條件Ti粱玲，轉(zhuǎn)4
3. Work = Work + Allocation[i] //把找到的線程擁有的資源釋放回當(dāng)前空閑資源中
    Finish[i] = true
    轉(zhuǎn)2
4. 如某個(gè) Finish[i] == false，則系統(tǒng)處于死鎖狀態(tài) //如果有Finish為false拜轨，表明系統(tǒng)處于死鎖狀態(tài)

• 算法需要O(m×n^2)操作檢測(cè)是否系統(tǒng)處于死鎖狀態(tài)

死鎖檢測(cè)算法的使用

• 死鎖檢測(cè)的時(shí)間和周期選擇依據(jù)

  • 死鎖多久可能會(huì)發(fā)生
  • 多少進(jìn)程需要回滾

• 資源可能有多個(gè)循環(huán)

  • 難于分辨“造成”死鎖的關(guān)鍵進(jìn)程

死鎖恢復(fù)：進(jìn)程終止

• 終止所有的死鎖進(jìn)程

• 一次只終止一個(gè)進(jìn)程直到死鎖消除

• 終止進(jìn)程的順序應(yīng)該是

  • 進(jìn)程的優(yōu)先級(jí)（由低到高）
  • 進(jìn)程已運(yùn)行時(shí)間以及還需運(yùn)行時(shí)間（保留運(yùn)行時(shí)間較長(zhǎng)者）
  • 進(jìn)程已占用資源
  • 進(jìn)程完成需要的資源
  • 終止進(jìn)程數(shù)目（越少越好）
  • 進(jìn)程是交互還是批處理（優(yōu)先讓用戶交互的進(jìn)程執(zhí)行下去）

死鎖恢復(fù)：資源搶占

• 選擇被搶占進(jìn)程

  • 最小成本目標(biāo)

• 進(jìn)程回退

  • 返回到一些安全狀態(tài)抽减，重啟進(jìn)程到安全狀態(tài)

• 可能出現(xiàn)饑餓

  • 同一進(jìn)程可能一直被選擇被搶占者

11.5 進(jìn)程通信概念

進(jìn)程通信（IPC, Inter-Process Communication）

• 進(jìn)程通信是進(jìn)程進(jìn)行通信和同步的機(jī)制

• IPC提供兩個(gè)基本操作

  • 發(fā)送操作：send(message)
  • 接收操作：receive(message)

• 進(jìn)程通信流程

  • 在通信進(jìn)程間建立通信鏈路
  • 通過(guò)send/receive交換信息

• 進(jìn)程鏈路特征

  • 物理（如，共享內(nèi)存橄碾、硬件總線）
  • 邏輯（如卵沉，邏輯屬性）

直接通信

• 進(jìn)程必須正確的命名對(duì)方

  • send(P, message) - 發(fā)送信息到進(jìn)程P
  • receive(Q, message) - 從進(jìn)程Q接收信息

• 通信鏈路屬性

  • 自動(dòng)建立鏈路
  • 一條鏈路恰好對(duì)應(yīng)一對(duì)通信進(jìn)程
  • 每對(duì)進(jìn)程之間只有一個(gè)鏈接存在
  • 鏈接可以是單向的，但通常是雙向的

間接通信

• 通過(guò)操作系統(tǒng)維護(hù)的消息隊(duì)列實(shí)現(xiàn)進(jìn)程間的消息接收和發(fā)送

  • 每個(gè)消息隊(duì)列都有一個(gè)唯一的標(biāo)識(shí)
  • 只有共享了相同的消息隊(duì)列的進(jìn)程法牲，才能夠通信

• 通信鏈路的屬性

  • 只有共享了相同的消息隊(duì)列的進(jìn)程史汗，才建立連接
  • 連接可以是單向或雙向
  • 消息隊(duì)列可以與多個(gè)進(jìn)程相關(guān)聯(lián)
  • 每對(duì)進(jìn)程可以共享多個(gè)消息隊(duì)列

• 通信流程

  • 創(chuàng)建一個(gè)新的消息隊(duì)列
  • 通過(guò)消息隊(duì)列發(fā)送和接收消息
  • 銷毀消息隊(duì)列

• 基本通信操作

  • send(A, message) - 發(fā)送消息到隊(duì)列A
  • receive(A, message) - 從隊(duì)列A接收消息

阻塞與非阻塞通信

• 進(jìn)程通信可劃分為阻塞（同步）或非阻塞（異步）

• 阻塞通信

  • 阻塞發(fā)送

    • 發(fā)送者在發(fā)送消息后進(jìn)入等待，直到接收者成功收到

  • 阻塞接收

    • 接收者在請(qǐng)求接收消息后進(jìn)入等待拒垃，直到成功收到一個(gè)消息

• 非阻塞通信

  • 非阻塞發(fā)送

    • 發(fā)送者在消息發(fā)送后停撞，可立即進(jìn)行其他操作

  • 非阻塞接收

    • 沒(méi)有消息發(fā)送時(shí)，接收者在請(qǐng)求接收消息后悼瓮，接收不到任何消息

通信鏈路緩沖

• 進(jìn)程發(fā)送的消息在鏈路上可能有3種緩沖方式

  • 0容量

    • 發(fā)送方必須等待接收方

  • 有限容量

    • 通信鏈路緩沖隊(duì)列滿時(shí)戈毒，發(fā)送方必須等待

  • 無(wú)限容量

    • 發(fā)送方不需要等待

11.6 信號(hào)量和管道

（一）信號(hào)

信號(hào)

• 進(jìn)程間的軟件中斷通知和處理機(jī)制
• 如，SIGKILL, SIGSTOP, SIGCONT等

信號(hào)的接收處理

• 捕獲（Catch）

  • 執(zhí)行進(jìn)程指定的信號(hào)處理函數(shù)被調(diào)用

• 忽略（Ignore）

  • 執(zhí)行操作系統(tǒng)指定的缺省處理

    • 例如：進(jìn)程終止横堡、進(jìn)程掛起等

• 屏蔽（Mask）

  • 禁止進(jìn)程接收和處理信號(hào)

    • 可能是暫時(shí)的（處理同種類型的信號(hào)）

不足

• 傳送的信息量小埋市，只有一個(gè)信號(hào)類型

（二）管道

管道（pipe）

• 進(jìn)程間基于內(nèi)存文件的通信機(jī)制

  • 子進(jìn)程從父進(jìn)程繼承文件描述符
  • 缺省文件描述符：0 stdin , 1 stdout, 2 strerr

• 進(jìn)程不知道（或不關(guān)心）另一端

• 可能從鍵盤(pán)、文件命贴、程序讀取

• 可能寫(xiě)入到終端道宅、文件、程序

與管道相關(guān)的系統(tǒng)調(diào)用

• 讀管道：read(fd, buffer, nbytes)

  • scanf()是基于它實(shí)現(xiàn)的

• 創(chuàng)建管道：pipe(rgfd)

  • rgfd是2個(gè)文件描述符組成的數(shù)組

    • rgfd[0]是讀文件描述符
    • rgfd[1]是寫(xiě)文件描述符

11.7 消息隊(duì)列和共享內(nèi)存

（一）消息隊(duì)列

• 消息隊(duì)列是由操作系統(tǒng)維護(hù)的以字節(jié)序列為基本單位的間接通信機(jī)制

  • 每個(gè)消息（message）是一個(gè)字節(jié)序列
  • 相同標(biāo)識(shí)的消息按先進(jìn)先出順序組成一個(gè)消息隊(duì)列（Message Queues）

消息隊(duì)列的系統(tǒng)調(diào)用

• msgget(QID, buf, size, flags)

  • 發(fā)送消息

• msgrcv(QID, buf, size, type, flags)

  • 接收消息

• msgctl(…)

  • 消息隊(duì)列控制

（二）共享內(nèi)存

• 共享內(nèi)存是把同一個(gè)物理內(nèi)存區(qū)域同時(shí)映射到多個(gè)進(jìn)程的內(nèi)存地址空間的通信機(jī)制

進(jìn)程

• 每個(gè)進(jìn)程都有私有地址內(nèi)存空間
• 每個(gè)進(jìn)程的內(nèi)存地址空間需要明確設(shè)置于共享內(nèi)存段

線程

• 同一進(jìn)程中的線程總是共享相同的內(nèi)存地址空間

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

• 快速胸蛛、方便的共享數(shù)據(jù)

不足

• 必須用額外的同步機(jī)制來(lái)協(xié)調(diào)數(shù)據(jù)訪問(wèn)

特點(diǎn)

• 最快的方法

• 一個(gè)進(jìn)程寫(xiě)另一個(gè)進(jìn)程立即可見(jiàn)

• 沒(méi)有系統(tǒng)調(diào)用干預(yù)

• 沒(méi)有數(shù)據(jù)復(fù)制

• 不提供同步

  • 由程序員提供同步

共享內(nèi)存的系統(tǒng)調(diào)用

• shmget(key, size, flags)

  • 創(chuàng)建共享段

• shmat(shmid, *shmaddr, flags)

  • 把共享段映射到進(jìn)程地址空間

• shmdt(*shmaddr)

  • 取消共享段到進(jìn)程地址空間的映射

• shmctl(…)

  • 共享段控制

• 完成共享關(guān)系的建立污茵，而正常共享數(shù)據(jù)的訪問(wèn)只需讀寫(xiě)指令，不需要專門的系統(tǒng)調(diào)用

• 需要信號(hào)量等機(jī)制協(xié)調(diào)共享內(nèi)存的訪問(wèn)沖突