進程管理4--Deadlock and Starvation

Concurrency:

Deadlock and Starvation

內容提要

>產生死鎖與饑餓的原因

>解決死鎖的方法

>死鎖/同步的經典問題：哲學家進餐問題

?

Deadlock ?系統的一種隨機性錯誤

·Permanent blocking of a set of processes that either compete for system resources or?communicate with each other.

·No efficient solution

·Involve conflicting needs for resources by two or more processes.

E.g. Process P and Q compete two resources. Their general forms are:

死鎖與進程的推進順序有關。

若修改P的代碼，則不會產生死鎖。

Process P

...

Get A

...

Release A

...

Get B

...

Release B

...

?

Reusable Resources 可重用資源

·Used by one process at a time and not depleted(耗盡) by that use.

·Processes obtain resources that they later release for reuse by other processes.

·processor ???main and secondary memory ???IO channels ???databases ???files ???semaphores

·Deadlock occurs if each process holds one resource and requests the other.

Example of Deadlock

?

Example of Two process competing for Reusable Resources.

?

Another Example of Deadlock

·Space is available for allocation of 200k bytes, and the following sequence of events occur.

·Deadlock occurs if both processes progress to their second request.

?

Consumable Resources 可消耗資源

·Created(produced) and destroyed(consumed) by a process.

·Interrupts, signals, messages and information in IO buffers.

?

Example of Deadlock

·Deadlock occurs if receive is blocking.

此類死鎖是由于設計失誤造成的，很難發現，且潛伏期長。

?

?

Condition for Deadlock

必要條件

·Mutual exclusion(互斥)

---Only one process may use a resource at a time.

·Hold-and-wait(保持并等待)

---A process may hold allocated resources while awaiting assignment of other resources.

·No preemptive(不剝奪)

---No resource can be forcibly removed from a process holding it.

?

??Circular Wait

充分條件

·Circular wait(環路等待)

---A closed chain of process exists, such that each process holds at least one resource needed by the next process in the chain.

?

條件Mutual exclusion、Hold-and-wait、No preemption是死鎖產生的必要條件；

條件Circular Wait是前3個條件產生的結果。

?

?

Deadlock Prevention 預防死鎖

預防死鎖是不可行的，只能盡量避免

·間接方法，禁止前3個條件之一的發生：（工程上不實用）

1、互斥：是某些系統資源的固有屬性，不能禁止；

2、禁止“保持等待”條件：

要求進程一次性地申請其所需的全部資源。若系統中沒有足夠的資源可分配給它，則進程阻塞。

3、禁止“不剝奪”條件：

（1）若一個進程占用了某些系統資源，又申請新的資源，則不能立即分配給它。必須讓它首先釋放出已占用資源，然后再重新申請；

（2）若一個進程申請的資源被另一個進程占有，OS可以剝奪低優先權進程的資源分配給高優先權進程(要求此類可剝奪資源的狀態易于保存和恢復，否則不能剝奪)。

·直接方法，禁止條件4（環路等待）的發生

即禁止“環路等待”條件：可以將系統的所有資源按類型不同進行線性排隊，并賦予不同的序號。進程對某類資源的申請只能按照序號遞增的方式進行。

顯然，此方法是低效的，它將影響進程執行的速度，甚至阻礙資源的正常分配。

?

Deadlock Avoidance 避免死鎖 ???用于服務器中，PC機中無

·預防死鎖通過實施較強的限制條件實現，降低了系統性能。

·避免死鎖的關鍵在于為進程分配資源之前，首先通過計算，判斷此次分配是否會導致死鎖，只有不會導致死鎖的分配才可實行。

·A decision is made dynamically whether the current resource allocation request will, if granted, potentially lead to a deadlock.

·Requires knowledge of future process request.

?

Approaches to Deadlock Avoidance

·Do not start a process if its demands might lead to deadlock.

·Do not grant an incremental resource request to a process if this allocation might lead to deadlock.

?

Resource Allocation Denial

·Referred to as the banker’s algorithm.

·State of the system is the current allocation of resources to process.

·Safe state is where there is at least one sequence that does not result in deadlock.

·Unsafe state is a state that is not safe.

?

Safe State

·指系統能按某種順序，如<P1, P2, ..., Pn>來為每個進程分配其所需資源，直至最大需求，使每個進程都可以順序完成，則系統處于safe state。

稱<P1, P2, ..., Pn>為安全序列。

?

Determination of a Safe State

???Claim Matrix

??

?Allocation Matrix

?

???Need Matrix

?

Resource Vector

?

Available Vector

?

Determination of a Unsafe State

???Claim Matrix

??

?Allocation Matrix

?

???Need Matrix

?

Resource Vector

?

Available Vector

?

?

Safe State V.S. Unsafe State

·并非所有不安全狀態都是死鎖狀態。

·當系統進入不安全狀態后，便可能進入死鎖狀態。

·只要系統處于安全狀態，則可避免死鎖狀態。

?

Sate State to Unsafe State

例，假設系統中有3個進程P1,P2,P3，共有12臺磁帶機。進程P1共需10臺，P2、P3分別需要4臺和9臺。設T0時刻，進程P1、P2、P3已分別獲得5臺、2臺、2臺，尚有3臺未分配，即圖示：

?

·T0時刻是安全的，因為存在一個安全序列<P2,P1,P3>，即只要系統按此進程序列分配資源，每個進程都可順利完成。

·但是，如果不按照安全序列分配資源，則系統可能會由安全狀態進入不安全狀態。

例如，T0時刻以后，P3又申請1臺磁帶機。若系統將剩余3臺中的1臺分配給P3，則系統進入不安全狀態。

?

?

?

————————————————————————————————————————————————————————————————————————————?

銀行家算法

·該算法可用于銀行發放一筆貸款錢，預測該筆貸款是否會引起銀行資金周轉問題。

·這里，銀行的資金就類似于計算機系統的資源，貸款業務類似于計算機的資源分配。

銀行家算法能預測一筆貸款業務對銀行是否是安全的，也能預測一次資源分配對計算機系統是否是安全的。

·為實現銀行家算法，系統中必須設置若干數據結構。

?

數據結構

1、可利用資源向量Available：

是一個具有m個元素的數組，其中的每一個元素代表一類可利用資源的數目，其初始值為系統中該類資源的最大可用數目，其值將隨著該類資源的分配與回收而動態改變。

Available[j]=k，表示系統中現有Rj類資源k個。

2、最大需求矩陣Max：

是一個n*m的矩陣，定義了系統中n個進程中的每一個進程對m類資源的最大需求。

Max(i,j)=k，表示進程i對Rj類資源的最大需求數目為k個。

3、分配矩陣Allocation：

是一個n*m的矩陣，定義了進程中每一類資源的數量。

Allocation(i,j)=k，表示進程i當前已分得Rj類資源的數目為k個。

4、需求矩陣Need:=Max-Allocation

Need(i,j)=k，表示進程i還需要Rj類資源k個，方能完成任務。

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

?

設Requesti是進程Pi的請求向量。

Requesti[j] = k，表示進程Pi需要k個Rj類資源。當進程Pi放出資源請求后，系統按下述步驟進行檢查：

1、如果，Requesti <= Needi，則轉向步驟2；否則，出錯。

2、如果，Requesti <= Available，則轉向步驟3；否則，表示尚無足夠資源可供分配，進程Pi必須阻塞等待。

3、系統試探性的將Pi申請的資源分配給它，并修改下列數據結構中的值：

Available := Available - Requesti;

Allocation := Allocation + Requesti;

Needi := Needi - Requesti;

4、系統利用安全性算法，檢查此次資源分配后，系統是否處于安全狀態。若安全，才正式將資源分配給進程Pi，完成本次資源分配；否則，試探分配失效，讓進程Pi阻塞等待。

?

?

安全性算法

1、設置兩個工作向量

a)設置一個數組Finish[n]。當Finish[i] = True (0 <= i <= n, n為系統中的進程數)時，表示進程Pi獲得其所需的全部資源，而順利執行完成。

b)設置一個臨時向量work，表示系統可提供給進程繼續運行的資源的集合。安全性算法剛開始執行時，work := Available。

2、從進程集合中找到一個滿足下列條件的進程

Finish[i] = false ?and ?Need <= Work; 若找到，執行步驟3，否則，執行步驟4。

3、當進程Pi獲得資源后，將順利執行直至完成，并釋放其所擁有的全部資源，故應執行以下操作

Work := work + Allocationi ?and ?Finish[i] = True；轉向步驟2；

4、如果所有進程的Finish[i] = True，則表示系統處于安全狀態，否則系統處于不安全狀態。

————————————————————————————————————————————————————————————————————————

舉例

T0時刻的資源分配情況

·假定系統中有四個進程P1,P2,P3,P4和三種類型的資源R1,R2,R3，每一種資源的數量分別為9,3,6。

T0時刻的資源分配情況如下表所示：

???Claim Matrix

??

?Allocation Matrix

?

???Need Matrix

?

Available Vector

?

T0時刻的安全性

·從T0時刻的安全性分析可知，T0時刻存在著一個安全序列<P2,P1,P4,P3>，故，T0時刻系統是安全的。

·假設T0時刻，進程P1申請資源，其請求向量為Request1(0,0,1)，系統按銀行家算法進行檢查：

Request1(0,0,1) <= Need1(2,2,2)

Request1(0,0,1)<=Available(0,1,1)

·故，系統試探性地為P1分配資源，并修改Available1，Allocation1，Need1向量。

?

Allocation Matrix

?

??Need Matrix

?

Available Vector

?

·利用安全性算法檢查此時系統是否安全：

>此時系統的可用資源向量為Available(0,1,0)。比較進程的需求向量Need，系統不能滿足任何進程的資源請求。系統進入不安全狀態。

>所以，P1請求的資源不能分配，只能讓P1阻塞等待。

·假設T0時刻，進程P4申請資源，其請求向量為Request4(1,2,0)，系統按銀行家算法進行檢查：

Request4(1,2,0) <= Need1(4,2,0)

Request1(1,2,0) ?> Available(0,1,1)

·P4的請求向量超過系統的可用資源向量，故P4的請求不能滿足，進程P4阻塞等待。

Deadlock Avoidance

·Maximum resource requirement must be stated in advance 必須預先申明每個進程需要的資源總量。

·Process under consideration must be independent; no synchronization requirements

進程之間相互獨立，其執行順序取決于系統安全，而非進程間的同步要求。

·There must be a fixed number of resources to allocate 系統必須提供固定數量的資源供分配。

·No process may exit while holding resources 若進程占有資源，則不能讓其退出系統。

---Collection of programs, data, stack and attributes

——————————————————————————————————————————————————————————————————————

若系統不提供任何措施保證不進入死鎖狀態，則必須提供檢測和解除死鎖的手段。?

Deadlock Detection 檢測死鎖

·檢測死鎖不同于預防死鎖，不限制資源訪問方式和資源申請。

·OS周期性的執行死鎖檢測例程，檢測系統中是否出現“環路等待”。

?

Strategies once Deadlock Detected

·Abort all deadlock processes.

·Back up each deadlock process to some previously defined checkpoint , and restart all process.

? ? ---Original deadlock may occur.

·Successively abort deadlocked processes until deadlock no longer exists.

·Successively preempt resources until deadlock no longer exists.

?

Selection Criteria Deadlock Processes

·Least amount of processor time consumed so far.

·Least number of lines of output produced so far.

·Most estimated time remaining.

·Least total resources allocated so far.

·Lowest priority.

?

?

Dining Philosophers Problem

·描述

有5個哲學家，它們的生活方式是交替地進行思考和進餐。哲學家們共用一張圓桌，分別坐在周圍的5把椅子上。

圓桌中間放有一大碗面條，每個哲學家分別有一個盤子和一支叉子。

如果哲學家想吃面條，則必須拿到靠其最近的左右兩支叉子。進餐完畢，放下叉子繼續思考。

?

·要求

設計一個合理的算法，使全部哲學家都能進餐(非同時)，算法必須避免死鎖和饑餓，哲學家互斥共享叉子。

By Semaphores