操作系統中的死鎖

1.1究竟什么是僵局？ (1.1 What exactly is a deadlock?)

In a multiprogramming environment, there may be several processes with a finite number of resources. A process may request another resource while still holding some of the other resources with itself. If these requested resources are not available at the time, the process may enter into a waiting state. This waiting state may never end if the resources requested by this process are held by other waiting processes. This situation is called "Deadlock" where none of the processes are ready to release their resources and are also waiting indefinitely for other waiting processes to release their resources.

在多程序環境中，可能會有幾個進程使用有限數量的資源。 一個進程可能會請求另一個資源，同時仍然保留其他一些資源。 如果這些請求的資源當時不可用，則過程可能會進入等待狀態。 如果此進程請求的資源由其他等待進程持有，則此等待狀態可能永遠不會結束。 這種情況稱為“死鎖” ，其中沒有一個進程準備釋放它們的資源，并且也無限期地等待其他等待的進程釋放它們的資源。

1.2系統模型 (1.2 System Model)

1. A system consists of a finite number of resources and these resources are partitioned into several types, each consisting of some number of identical instances.

   一個系統由有限數量的資源組成，并且這些資源被分為幾種類型，每種類型都由一定數量的相同實例組成。

2. Resource types include the printer, DVD drives, CPU cycles, files, etc. For example, if a system has two printers then the resource type Printer has two instances.

   資源類型包括打印機，DVD驅動器，CPU周期，文件等。例如，如果系統有兩臺打印機，則資源類型“打印機”有兩個實例。

3. These instances may be identical or different. If the instances are similar, any instance can be assigned to the process, and if not, then the two printers need to be defined as separate resource classes.

   這些實例可以相同或不同。 如果實例相似，則可以將任何實例分配給該流程，否則，則需要將兩個打印機定義為單獨的資源類。

4. A process must request the resource before using it and must release it after use.

   進程必須在使用資源之前請求資源，并且在使用之后必須釋放資源。

5. A process may request as many resources as it requires for the completion of its task but it should not exceed the total number of resources present in the system.

   進程可以請求完成任務所需的資源，但是它不應超過系統中存在的資源總數。

6. To summarize, a process must utilize a resource in the following manner,

   總而言之，流程必須以以下方式利用資源：

   • Request: The process must request for the resource. If the request can't be granted immediately, it must wait to acquire the resource.請求 ：進程必須請求資源。 如果無法立即批準該請求，則它必須等待獲取資源。
   • Use: The process must use the resource after acquiring it.使用 ：流程必須在獲取資源后使用它。
   • Release: The process must release the resource after using it.釋放 ：進程必須在使用后釋放資源。

1.3死鎖特征 (1.3 Deadlock Characterization)

There are four necessary conditions for a deadlock to occur. If any of the four conditions fail, then the condition is not called a deadlock and maybe recovered easily. The following are the necessary conditions,

發生死鎖有四個必要條件。 如果這四個條件中的任何一個失敗，則該條件不稱為死鎖，并且可能容易恢復。 以下是必要條件，

1.3.1 Mutual Exclusion

1.3.1互斥

At least one resource must be held in a non-sharable mode. This means that only one process can use the resource at a particular time. If any other process requests this non-sharable resource, then, it must wait for the process which is holding the resource to release it.

至少一種資源必須處于不可共享的模式。 這意味著在特定時間只有一個進程可以使用資源。 如果任何其他進程請求此不可共享資源，則它必須等待持有該資源的進程釋放它。

If we think clearly, this is a necessary condition for deadlock because if more than one process is allowed to use a resource at the same time, the deadlock will never occur and all the resources will carry out their tasks easily.

如果我們想清楚，這是死鎖的必要條件，因為如果允許多個進程同時使用一個資源，則死鎖將永遠不會發生，所有資源將輕松執行其任務。

1.3.2 Hold and Wait

1.3.2保持并等待

A process must be holding at least one resource and waiting to acquire other resources that are currently being held by other processes.

一個進程必須至少持有一種資源，并等待獲取其他進程當前正在持有的其他資源。

1.3.3 No preemption

1.3.3無搶占

The resources cannot be preempted. What this means is that one process cannot snatch a resource from another process that currently holds it. It can only be released voluntarily by the process holding it after its execution.

資源不能被搶占。 這意味著一個進程無法從當前擁有該進程的另一進程中搶奪資源。 它只能在執行后由持有它的進程自動釋放。

1.3.4 Circular Wait

1.3.4循環等待

A set {P0, P1, ..., Pn} of waiting process must exist such that P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, …, Pn-1 is waiting for a resource held by Pn, and Pn is waiting for a resource held by P0.

必須存在一組{P0，P1，...，Pn}等待過程，這樣P0正在等待P1擁有的資源，P1正在等待P2擁有的資源，...，Pn-1正在等待資源Pn持有，而Pn正在等待P0持有的資源。

The circular wait condition implies the hold and waits for condition, so these four conditions are not independent as we shall see in the next article.

循環等待條件暗含保持和等待條件，因此這四個條件不是獨立的，我們將在下一篇文章中看到。

1.4資源分配圖 (1.4 Resource Allocation Graph)

Resource allocation graphs are mainly used as methods for the detection of a deadlock. We will discuss this feature when we read about Deadlock Handling mechanisms.

資源分配圖主要用作檢測死鎖的方法。 當我們閱讀有關死鎖處理機制時，我們將討論此功能。

1. Deadlock can be best represented in the terms of a directed graph called a system resource-allocation graph. The graph consists of a set of vertices V and a set of edges E.

   死鎖最好用稱為系統資源分配圖的有向圖來表示 。 該圖由一組頂點V和一組邊E組成 。

2. The edges can be of two types, represented as Pi for a process i and Rj for a resource type j, where i, j are the integer values representing the number of processes and resource types respectively.

   邊緣可以是兩種類型，分別表示為進程i的 Pi和資源類型j的 Rj ，其中i，j是分別表示進程數和資源類型的整數值。

3. The vertices V are partitioned into two different types of nodes: P = {P1, P2, ..., Pn}, the set consisting of all the active processes in the system, and R = {R1, R2, ..., Rm}, the set consisting of all the resource types in the system.

   頂點V分為兩個不同類型的節點： P = {P1，P2，...，Pn} ，該集合由系統中所有活動進程組成， R = {R1，R2，...， Rm} ，由系統中所有資源類型組成的集合。

4. A directed edge from process Pi to resource type Rj is denoted by Pi → Rj. It shows that process Pi is requesting an instance of resource type Rj and is called a request edge.

   從Pi到資源類型Rj的有向邊用Pi → Rj表示。 它顯示進程Pi正在請求資源類型Rj的實例，并且被稱為請求邊緣。

5. A directed edge from resource type Rj to process Pi is denoted by Rj → Pi. It shows that an instance of resource type Rj is allocated to process Pi and is called an assignment edge.

   從資源類型Rj到進程Pi的有向邊用Rj → Pi表示。 它顯示資源類型Rj的實例已分配給進程Pi ，稱為分配邊緣。

6. Pictorially, each process Pi is represented as a circle and each resource type Rj as a rectangle. Since there may be more than one instance of a resource, the instances are denoted by a dot within the rectangle.

   如圖所示，每個進程Pi表示為一個圓形，每個資源類型Rj表示為一個矩形。 由于資源的實例可能不止一個，因此實例在矩形內用一個點表示。

7. When process Pi requests and instance of a resource type Rj, a request edge is inserted in the graph. When the request is fulfilled, the request edge is instantaneously transformed into an assignment edge. When the process completes its work, it releases the resource; as a result, the assignment edge is deleted.

   當進程Pi請求資源類型為Rj的實例時，請求邊將插入圖中。 當請求被滿足時，請求邊被立即轉換為分配邊。 流程完成工作后，將釋放資源。 結果，分配邊被刪除。

Consider a few examples,

考慮幾個例子，

• The sets P, R, and E:

  集合P，R和E：

  • P = {P1, P2, P3}
  • R = {R1, R2, R3, R4}
  • E = {P1 → R1, P2 → R3, R1 → P2, R2 → P2, R2 → P1, R3 → P3}

• Resource instances:

  資源實例：

  • One instance of resource type R1
  • Two instances of resource type R2
  • One instance of resource type R3
  • Three instance of resource type R4
  • 
    
    
    
    
    
    Fig 1.1 Resource Allocation Graph圖1.1資源分配圖

• Process states:

  流程狀態：

  • Process P1 is holding an instance of resource type R2 and is waiting for an instance of resource type R1.
  • Process P2 is holding an instance of R1 and an instance of R2 and is waiting for an instance of R3.
  • Process P3 is holding an instance of R3.

• This resource allocation graph shows that there is no cycle in the graph. Therefore, no process in the system is deadlocked. If the graph does contain a cycle, then a deadlock may exist. This depends on two situations as follows.

  此資源分配圖顯示圖中沒有循環。 因此，系統中的任何進程都不會陷入僵局。 如果圖形確實包含一個循環，則可能存在死鎖。 這取決于以下兩種情況。

IMPORTANT POINTS TO NOTE:

注意要點：

1. If each resource type has exactly one instance, then a cycle implies that a deadlock has occurred. Each process in the cycle is deadlocked. In this case, a cycle in the graph is both a necessary and sufficient condition for the existence of deadlock.

   如果每種資源類型僅具有一個實例，則循環表示發生了死鎖。 循環中的每個進程都處于死鎖狀態。 在這種情況下，圖中的循環既是存在死鎖的必要條件，也是充分條件。

2. If each resource has several instances, then a cycle is not the necessary condition to determine that deadlock has occurred.

   如果每個資源都有多個實例，則循環不是確定發生死鎖的必要條件。

3. To illustrate this concept, we include a request edge from P3 → R2.

   為了說明這個概念，我們包括一個從P3→R2的請求邊。

Fig 1.2 Resource Allocation Graph (Cycle with deadlock)

圖1.2資源分配圖(帶有死鎖的周期)

Here, there are two cycles present in the system:

在這里，系統中存在兩個周期：

    P1 → R1 → P2 → R3 → P3 → R2 → P1
P2 → R3 → P3 → R2 → P2

CONCLUSION: Processes P1, P2, and P3 are deadlocked.

結論：進程P1，P2和P3處于死鎖狀態。

Now, consider another graph where the following cycle exists:

現在，考慮存在以下循環的另一個圖：

    P1 → R1 → P3 → R2 → P1

CONCLUSION: There is no deadlock. The process P4 may release its instance of resource type R2. That resource can then be allocated to P3, breaking the cycle.

結論：沒有死鎖。 過程P4可以釋放其資源類型R2的實例。 然后可以將該資源分配給P3，從而中斷周期。

Fig 1.3 Cycle but no deadlock

圖1.3循環但無死鎖

To summarize: If a resource allocation graph does not have a cycle, then the system is not in a deadlocked state. If there is a cycle, then the system may or may not be in a deadlocked state. When there are multiple instances of a resource type, the presence of a deadlock is determined using Banker's Algorithm. We will study that in further articles.

總結一下：如果資源分配圖沒有周期，則系統不會處于死鎖狀態。 如果存在周期，則系統可能處于死鎖狀態，也可能未處于死鎖狀態。 當資源類型有多個實例時，使用Banker算法確定死鎖的存在。 我們將在后續文章中對此進行研究。

References:

參考文獻：

• Operating System Concepts, 8th edition, by author: Silberschatz Galvin Gagne.

  操作系統概念，第8版，作者：Silberschatz Galvin Gagne。

• Operating System Design/Concurrency/Deadlock

  操作系統設計/并發/死鎖

• Deadlock

  僵局

• Hold and wait a process must be holding at least one

  保持并等待一個進程必須至少持有一個

• Chapter 6 Deadlocks

  第六章僵局

翻譯自: https://www.includehelp.com/operating-systems/introduction-of-deadlock.aspx

操作系統中的死鎖