一、死鎖

死鎖：一組阻塞的進程（兩個或多個），持有一種資源，等待獲取另一個進程所占有的資源，而導致誰都無法執行。?

可重復使用的資源：

• 在一個時間只能一個進程使用，且不能被刪除。
• OS避免殺死擁有資源的進程；進程使用資源后要釋放，其他進程可重用；
• 有物理資源（cpu， I/O通道，主和副存儲器），也有抽象的資源（設備和數據結構，如文件，數據庫和信號量）；
• 如果每個進程擁有一個資源并請求其他資源，可能導致死鎖

資源分配圖

死鎖的必要條件

• 互斥：任何時刻只能有一個進程使用一個資源實例
• 持有并等待：進程保持至少一個資源，并正在等待獲取其他進程持有的資源
• 無搶占，一個資源只能被進程自愿釋放
• 循環等待，形成閉環

二、死鎖處理方法

1、死鎖預防（dead-lock prevention?）

打破死鎖出現的條件 ，確保系統永遠不會進入死鎖狀態

• 互斥：互斥的共享資源封裝成可同時訪問。占用非共享資源 會增加不確定性 不推薦
• 占用并等待：保證當一個進程請求資源時，不持有任何其他的資源；all or nothing 需要進程請求并分配其所有資源。資源利用率低，可能饑餓
• 無搶占：允許搶占占有某些資源的進程。如進程請求不能立即分配的資源，則釋放已占有資源，只在能夠同時獲得所有需要資源時，才執行分配操作
• 循環等待：對所有資源類型進行排序，并要求每個進程按照資源的順序進行申請，會出現資源利用不夠

2、死鎖避免（ deadlock avoidance?）

當進程運行過程中，根據申請資源的情況判斷會不會死鎖，如果會就不給資源。

最簡單有效就是要求每個進程聲明它需要的每個類型資源的最大數目，資源在分配中根據最大數目限定提供與分配的資源數目，死鎖避免算法要動態檢查資源的分配狀態來避免環形等待。

環形等待不一定會死鎖。分為安全狀態，不安全狀態

3、死鎖檢測和恢復（Deadlock Detection & Recovery）

在檢測到運行系統進入死鎖狀態后，進行恢復

4、由應用程序處理死鎖

通常操作系統忽略死鎖，大多數操作系統（包括UNIX）的做法

三、銀行家算法

1、有多個資源實例?；每個進程必須能最大限度地利用資源?；找到理想執行時序，找到就認為是安全的

類比：銀行家——操作系統；資金——資源；客戶——申請資源的線程

2、銀行家算法：數據結構

• n=線程數量 m=資源類型數量（一個線程可能需要多種資源）
• Max 總需求量：n*m矩陣 max[i, j]=k 進程Pi最多需要資源類型Rj的k個實例
• Available 剩余空閑量：長度為m的向量，如果available[j]=k 則有k個類型Rj的資源實例可用
• Allocation 已分配量：n*m矩陣 allocation[I, j]=k 進程Pi已經分配了資源類型Rj的k個實例
• Need 未來需要量： n*m矩陣 need[i, j]=k 進程Pi可能需要資源類型Rj的k個實例
• Max[i, j]=need[I,j]+allocation[i,j]

3、安全狀態判斷

四、進程通信概念

1、進程通信（ IPC: inter process communication）

• 進程通信：是進程進行通信和同步的機制
• IPC facility 提供2個操作： send(message)、receive (message)
• 進程P和Q想通信，需要： 在它們之間建立通信鏈路 ，通過send/receive交換消息
• 通信鏈路的實現： 物理（例如，共享內存，硬件總線)、 邏輯（如邏輯屬性）

2、直接通信

為了實現直接通信，要有發送和接收的ID ；進程必須正確地命名對方 ；

• send( P, message) - 發送信息到進程P ；receive( P, message) - 接收進程P的信息
• 通信鏈路的屬性 ：自動建立鏈路 ；一條鏈路對應一對通信進程 ；每對進程之間只有一個鏈接存在 ；鏈接可以是單向的，但通常為雙向的

2、間接通信

為了實現間接通信，要發送到共享區，發送方和接收方都不關注具體的另一方是誰

每個消息隊列都有一個唯一的ID；只有共享了相同消息隊列的進程，進程才能通信

• 通信鏈路的屬性：只有共享了相同消息隊列的進程，才建立鏈路；鏈接可以與許多進程相關聯；鏈接可以是單向或雙向
• 通信流程：?Ⅰ、建立一個新的消息隊列?；Ⅱ、通過消息隊列發送和接收消息?；Ⅲ、銷毀消息隊列?
• 基本通信操作：?send(A, message) – 發送消息到隊列A ；receive(A, message) - 從隊列A接受消息

3、阻塞與非阻塞通信

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

• 阻塞通信：阻塞發送、阻塞接收
• 非阻塞通信：非阻塞發送、非阻塞接收

4、通信鏈路緩沖

隊列的消息被附加到鏈路的3種方式?

• 0容量—0 messages 發送方必須等待接收方?
• 有限容量—n messages 的有限長度，發送方在隊列滿的時候要等待?
• 無限容量—理想狀況，不用等

六、信號和管道

1、信號（Signal）

定義：信號是進程間的軟件中斷通知和處理機制，如：SIGKILL,SIGSTOP等

信號的接收處理

1. 捕獲 catch : 指定信號處理函數被調用
2. 忽略 ignore: 依靠操作系統的默認操作 ， 如進程終止、進程掛起
3. 屏蔽 mask:禁止進程接收和處理信號（可能是暫時的，當處理同樣類型的信號）

不足：不能傳輸要交換的任何數據

優點：效率很高，異步。一般處理完后會回到被打斷的進程。

2、管道

管道是進程間基于內存文件的通信機制。子進程從父進程繼承包括文件描述符等的資源。進程不知道另一端：可能從鍵盤、文件、程序讀取；可能寫入終端、文件、程序。

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

與管道相關的系統調用：

• 讀管道：read(fd,buffer,nbytes) 如scanf()是基于它實現的
• 寫管道：write(fd,buffer,nbytes) 如printf()是基于它實現的
• 創建管道：pipe(rgfd) rgfd是2個文件描述符組成的數組。rgfd[0]是讀文件描述符；rgfd[1]是寫文件描述符

管道示例

UNIX想靈活組合小程序，一個的輸出是另一個的輸入，用豎線|來表示把ls的輸出stdout重定向，通過一個類似buffer的管道作為stdin傳輸給more。More以為是從i/o給它的，實際是ls給它的。進程不關心。?

七、消息隊列和共享內存

1、消息隊列

管道必須有父進程，數據是字節流，沒有數據結構。消息隊列可以多個不相干的進程來傳遞數據，而且message作為一個字節序列存儲，message quenues是消息數組。是一個有意義的結構化。?按FIFO/FILO管理?

消息隊列是由操作系統維護的以字節序列為基本單位的間接通信機制。每個消息是一個字節序列；相同標識的消息組成按先進先出順序組成一個消息隊列。

消息隊列的系統調用

• msgget(key,flags)獲取消息隊列標識
• msgsnd(QID,buf,size,flags)發送消息
• msgrcv(QID,buf,size,type,flags)接收消息
• msgctl(...)消息隊列控制

2、共享內存

共享內存是把同一個物理內存區域同時映射到多個進程的內存地址空間的通信機制。

每個進程都有私有內存地址空間；每個進程的內存地址空間需明確設置共享內存段；

同一進程中的線程總是共享相同的內存地址空間

優點：快速、方便地共享數據；

缺點：必須用額外的同步機制來協調數據訪問

共享內存是最快的方法，一個進程寫另一個進程立即可見，沒有系統調用干預，沒有數據復制。

共享內存系統調用

• shmget(key,size,flags)創建共享段
• shmat(shmid,*shmaddr,flags)把共享段映射到進程地址空間
• shmdt(*shmaddr)取消共享段到進程地址空間的映射
• shmctl(...)共享段控制

需要信號量等機制協調共享內存的訪問沖突。
?