20.1死鎖概念

由于競爭資源或者通信關系，兩個或更多線程在執(zhí)行中出現(xiàn)玷室，永遠相互等待只能由其他進程引發(fā)的事件

進程訪問資源的流程

■資源類型R1, R2, . . .,Rm

CPU執(zhí)行時間桃煎、內(nèi)存空間篮幢、I/O設備等

■每類資源Ri有Wi個實例

■進程訪問資源的流程

·請求/獲取

申請空閑資源

·使用/占用

進程占用資源

·釋放

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

資源分類

可重用資源（Reusable Resource）

■資源不能被刪除且在任何時刻只能有一個進程使用

■進程釋放資源后，其他進程可重用

■可重用資源示例

硬件：處理器为迈、I / O通道三椿、主和副存儲器、設備等

軟件：文件葫辐、數(shù)據(jù)庫和信號量等數(shù)據(jù)結構

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

每個進程占用一部分資源并請求其它資源

消耗資源(Consumable resource)

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

■消耗資源示例

在I/O緩沖區(qū)的中斷搜锰、信號、消息等

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

進程間相互等待接收對方的消息

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

■互斥

任何時刻只能有一個進程使用一個資源實例

■持有并等待

進程保持至少一個資源耿战，并正在等待獲取其他進程持有的資源

■非搶占

資源只能在進程使用后自愿釋放

■循環(huán)等待

存在等待進程集合{P0蛋叼，P1，...，PN}狈涮，

P0正在等待P1所占用的資源狐胎，

P1正在等待P2占用的資源，...歌馍，

PN-1在等待PN所占用資源握巢，

PN正在等待P0所占用的資源

20.2死鎖處理方法

■死鎖預防(Deadlock Prevention)

確保系統(tǒng)永遠不會進入死鎖狀態(tài)

■死鎖避免(Deadlock Avoidance)

在使用前進行判斷，只允許不會出現(xiàn)死鎖的進程請求資源

■死鎖檢測和恢復(Deadlock Detection & Recovery)

在檢測到運行系統(tǒng)進入死鎖狀態(tài)后松却，進行恢復

■由應用進程處理死鎖

通常操作系統(tǒng)(大多數(shù)操作系統(tǒng)（包括UNIX）的做法)忽略死鎖

死鎖預防：限制申請方式

預防是采用某種策略暴浦，限制并發(fā)進程對資源的請求，使系統(tǒng)在任何時刻都不滿足死鎖的必要條件晓锻。

■互斥

把互斥的共享資源封裝成可同時訪問

■持有并等待

進程請求資源時歌焦，要求它不持有任何其他資源

僅允許進程在開始執(zhí)行時，一次請求所有需要的資源

缺點：資源利用率低带射，可能發(fā)生等待

■非搶占

如進程請求不能立即分配的資源同规，則釋放已占有資源

只在能夠同時獲得所有需要資源時，才執(zhí)行分配操作

■循環(huán)等待

對資源排序窟社，要求進程按順序請求資源

死鎖避免

■利用額外的先驗信息券勺，在分配資源時判斷是否會出現(xiàn)死鎖，只在不會死鎖時分配資源

要求進程聲明需要資源的最大數(shù)目

限定提供與分配的資源數(shù)量灿里，確保滿足進程的最大需求

動態(tài)檢查的資源分配狀態(tài)关炼，確保不會出現(xiàn)環(huán)形等待

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

■當進程請求資源時，系統(tǒng)判斷分配后是否處于安全狀態(tài)

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

針對所有已占用進程匣吊，存在安全序列（這個序列執(zhí)行保證我已有的資源能夠滿足這個序列執(zhí)行到結束）

■序列是安全的

Pi要求的資源≤當前可用資源+所有Pj持有資源

其中j

如Pi的資源請求不能立即分配儒拂，則Pi等待所有Pj（j

Pi完成后，Pi +1可得到所需資源色鸳，執(zhí)行并釋放所分配的資源

最終整個序列的所有Pi都能獲得所需資源

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

■系統(tǒng)處于安全狀態(tài)社痛，一定沒有死鎖

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

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

銀行家算法（Banker's Algorithm）

■銀行家算法是一個避免死鎖產(chǎn)生的算法命雀。以銀行借貸分配策略為基礎蒜哀，判斷并保證系統(tǒng)處于安全狀態(tài)

`客戶在第一次申請貸款時，聲明所需最大資金量吏砂，在滿足所有貸款要求并完成項目時撵儿，及時歸還

`在客戶貸款數(shù)量不超過銀行擁有的最大值時，銀行家盡量滿足客戶需要

`類比

銀行家-操作系統(tǒng)

資金-資源

客戶-申請資源的線程

銀行家算法：數(shù)據(jù)結構

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

基本的思路就是當前的剩余資源可以滿足某一個線程的未來需要,并且這種迭代循環(huán)到最后能夠滿足所有的線程的需要,也就相當于找到了一個安全序列

銀行家算法

精髓：

死鎖避免的優(yōu)點是它不需要死鎖預防中的搶占和回滾進程狐血，并且比死鎖預防的限制少淀歇。但是，它在使用中也有許多限制:

.必須事先聲明每個進程請求的最大資源匈织。

.考慮的進程必須是無關的浪默，也就是說，它們執(zhí)行的順序必須沒有任何同步要求的限制。

.分配的資源數(shù)目必須是固定的浴鸿。

.在占有資源時井氢，進程不能退出。

20.4死鎖檢測

■允許系統(tǒng)進入死鎖狀態(tài)

■維護系統(tǒng)的資源分配圖

■定期調(diào)用死鎖檢測算法來搜索圖中是否存在死鎖

■出現(xiàn)死鎖時岳链，用死鎖恢復機制進行恢復

死鎖檢測算法：數(shù)據(jù)結構

死鎖檢測算法

資源分配結束后花竞，根據(jù)剩下的資源去尋找能夠讓它執(zhí)行完的進程。如果找不到掸哑，說明是不安全的约急，會出現(xiàn)死鎖。找到了就執(zhí)行能夠完成的進程苗分，并回收其資源厌蔽，再去尋找下一個執(zhí)行完成的進程。

死鎖檢測算法的使用

■死鎖檢測的時間和周期選擇依據(jù)（要考慮的因素）

死鎖多久可能會發(fā)生

多少進程需要被回滾

■資源圖可能有多個循環(huán)

難于分辨“造成”死鎖的關鍵進程

死鎖恢復:進程終止

■終止所有的死鎖進程（進程如果計算了很長時間摔癣，終止的話必須舍棄這部分結果）

■一次只終止一個進程直到死鎖消除（沒終止一個進程奴饮，就要檢測一遍死鎖狀態(tài)）

■終止進程的順序應該是

進程的優(yōu)先級（低的先終止）

進程已運行時間以及還需運行時間

進程已占用資源

進程完成需要的資源

終止進程數(shù)目（越小越好）

進程是交互還是批處理

死鎖恢復：資源搶占

■選擇被搶占進程

最小成本目標

■進程回退

返回到一些安全狀態(tài),重啟進程到安全狀態(tài)

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

同一進程可能一直被選作被搶占者

20.5進程通信（IPC, Inter-Process Communication）

■進程通信是進程進行通信和同步的機制

■IPC提供2個基本操作

發(fā)送操作：send(message)

接收操作：receive(message)

■進程通信流程

在通信進程間建立通信鏈路

通過send/receive交換消息

■進程鏈路特征

物理(如，共享內(nèi)存择浊，硬件總線）

邏輯(如戴卜，邏輯屬性）

直接通信

直接通訊是在兩個進程之間建立一個通訊信道，這就是這里的共享信道琢岩，兩個進程必須同時存在才能夠進行通訊投剥。

■進程必須正確的命名對方

send (P, message)– 發(fā)送信息到進程P

receive(Q, message)– 從進程Q接受消息

■通信鏈路的屬性

自動建立鏈路

一條鏈路恰好對應一對通信進程

每對進程之間只有一個鏈接存在

鏈接可以是單向的，但通常為雙向的

間接通信

間接通訊依賴于操作系統(tǒng)內(nèi)核完成的進程間的通訊担孔，首先它在通訊進程和內(nèi)核之間建立相應的機構能夠支持這種通訊江锨，比如說建立消息隊列，然后一個進程可以把信息發(fā)送到內(nèi)核的消息隊列上糕篇，然后另一個進程從消息隊列里讀出來

生命周期還可以不一樣啄育，A發(fā)信息時B可以未創(chuàng)建

■通過操作系統(tǒng)維護的消息隊列實現(xiàn)進程間的消息接收和發(fā)送

每個消息隊列都有一個唯一的標識

只有共享了相同消息隊列的進程，才能夠通信

■通信鏈路的屬性

只有共享了相同消息隊列的進程拌消，才建立連接

連接可以是單向或雙向

消息隊列可以與多個進程相關聯(lián)

每對進程可以共享多個消息隊列

■通信流程

創(chuàng)建一個新的消息隊列

通過消息隊列發(fā)送和接收消息

銷毀消息隊列

■基本通信操作

send(A, message)– 發(fā)送消息到隊列A

receive(A, message)– 從隊列A接受消息

阻塞與非阻塞通信

■進程通信可劃分為阻塞（同步）或非阻塞（異步）

■阻塞通信

·阻塞發(fā)送

發(fā)送者在發(fā)送消息后進入等待灸撰，直到接收者成功收到

·阻塞接收

接收者在請求接收消息后進入等待，直到成功收到一個消息

■非阻塞通信

·非阻塞發(fā)送

發(fā)送者在消息發(fā)送后拼坎，可立即進行其他操作

·非阻塞接收

沒有消息發(fā)送時，接收者在請求接收消息后完疫，接收不到任何消息

通信鏈路緩沖

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

·0容量

發(fā)送方必須等待接收方（必須阻塞發(fā)送）

·有限容量

通信鏈路緩沖隊列滿時泰鸡，發(fā)送方必須等待（隊列滿，必須阻塞發(fā)送）

·無限容量

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

20.6信號與管道

20.6.1信號（Signal）

■信號

·進程間的軟件中斷通知和處理機制

·如：SIGKILL, SIGSTOP, SIGCONT等

■信號的接收處理

·捕獲(catch)：執(zhí)行進程指定的信號處理函數(shù)被調(diào)用

·忽略(Ignore)：執(zhí)行操作系統(tǒng)指定的缺省處理

例如：進程終止壳鹤、進程掛起等

·屏蔽（Mask）：禁止進程接收和處理信號

可能是暫時的(當處理同樣類型的信號)

■不足

傳送的信息量小盛龄，只有一個信號類型（不能傳輸其他的，做一種快速反應機制）

信號的實現(xiàn)

首先進程在啟動的時候，需要注冊相應的信號處理例程給操作系統(tǒng)內(nèi)核余舶，以便于操作系統(tǒng)內(nèi)核在有相應的信號送過來的時候能夠知道去執(zhí)行哪一個處理函數(shù)啊鸭，這是注冊。然后是有其他進程或者其他設備發(fā)出信號的時候匿值，操作系統(tǒng)內(nèi)核負責把這個信號送給指定的進程并且啟動其中的信號處理函數(shù)然后執(zhí)行信號處理函數(shù)赠制，完成相應的處理。

信號使用示例

20.6.2管道(pipe)

■進程間基于內(nèi)存文件的通信機制

子進程從父進程繼承文件描述符

缺省文件描述符：0 stdin, 1 stdout, 2 stderr

■進程不知道（或不關心Ｐ尽）的另一端

可能從鍵盤钟些、文件、程序讀取

可能寫入到終端绊谭、文件政恍、程序

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

管道示例

20.7消息隊列和共享內(nèi)存

20.7.1消息隊列

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

每個消息(Message)是一個字節(jié)序列

相同標識的消息組成按先進先出順序組成一個消息隊列（Message Queues）

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

20.7.2共享內(nèi)存

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

■進程

每個進程都有私有內(nèi)存地址空間

每個進程的內(nèi)存地址空間需明確設置共享內(nèi)存段

■線程

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

■優(yōu)點

快速、方便地共享數(shù)據(jù)

■不足

必須用額外的同步機制來協(xié)調(diào)數(shù)據(jù)訪問

共享內(nèi)存的實現(xiàn)

共享內(nèi)存實現(xiàn)機制如圖所示达传，兩個進程的地址空間各自不同篙耗，中間是物理內(nèi)存把一塊物理內(nèi)存區(qū)域，映射到兩個進程宪赶。怎么映射宗弯？通過兩個進程的表項，不同的頁表項逊朽，在進程地址空間里可以有相同或者不同的邏輯地址罕伯，但是它們映射過來的時候，這一頁對應的物理內(nèi)存的地址是相同的叽讳。兩個進程就映射到同一頁了

■最快的方法

■一個進程寫另外一個進程立即可見

■沒有系統(tǒng)調(diào)用干預

■沒有數(shù)據(jù)復制

■不提供同步

由程序員提供同步

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