System Model

• System consists of resources
• Resource types $R_1$, $R_2$, . . ., $R_m$
  • CPU cycles, memory space, I/O devices
• Each resource type $R_i$ has $W_i$ instances.
• Each process utilizes a resource as follows:
  • request
  • use
  • release

• 시스템은 리소스로 구성된다.
• 리소스 유형 $R_1$, $R_2$, ., $R_m$
  • CPU 주기, 메모리 공간, I/O 디바이스
• 각 리소스 유형 $R_i$에는 $W_i$ 인스턴스가 있다.
• 각 프로세스는 다음과 같은 리소스를 활용한다.
  • request
  • use
  • release

Deadlock in Multithreaded Applications

• Two mutex locks are created an initialized:
  

• Deadlock is possible if thread 1 acquires first_mutex and thread 2 acquires second_mutex. Thread 1 then waits for second_mutex and thread 2 waits for first_mutex.
• Can be illustrated with a resource allocation graph:

• 교착 상태는 스레드 1이 first_mutex를 획득하고 스레드 2가 second_mutex를 획득하는 경우에 가능하다. 그런 다음 스레드 1은 second_mutex를 기다리고 스레드 2는 first_mutex를 기다린다.
• 리소스 할당 그래프로 설명할 수 있다:

Deadlock Characterization

• Deadlock can arise if four conditions hold simultaneously
  • Mutual exclusion: only one process at a time can use a resource
  • Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes
  • No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task
  • Circular wait: there exists a set {P0, P1, …, Pn} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by P0.

• 네 가지 조건이 동시에 유지되면 교착 상태가 발생할 수 있다.
  • 상호 제외: 한 번에 하나의 프로세스만 리소스를 사용할 수 있다.
  • 보류 및 대기: 하나 이상의 리소스를 보유한 프로세스가 다른 프로세스에서 보유한 추가 리소스를 획득하기 위해 대기 중이다.
  • 선점 없음: 리소스를 보유하는 프로세스에서만 해당 프로세스가 작업을 완료한 후 리소스를 자발적으로 해제할 수 있다.
  • Circular wait: 대기 프로세스 집합 {P0, P1, …, Pn}이 존재하며, P0은 P1에 의해 보유되는 리소스를 기다리고, P1은 P2에 의해 보유되는 리소스를 기다리고, Pn-1은 P0에 의해 보유되는 리소스를 기다린다.

Resource-Allocation Graph

A set of vertices V and a set of edges E.

• V is partitioned into two types:
  • P = {P1, P2, …, Pn}, the set consisting of all the processes in the system
  • R = {R1, R2, …, Rm}, the set consisting of all resource types in the system
• request edge – directed edge Pi -> Rj
• assignment edge – directed edge Rj -> Pi

꼭짓점(V)의 집합과 모서리(E)의 집합이다.

• V는 두 가지 유형으로 분할된다.
  • P = {P1, P2, …, Pn}, 시스템의 모든 프로세스로 구성된 집합
  • R = {R1, R2, …, Rm}, 시스템의 모든 리소스 유형으로 구성된 집합
• request edge – directed edge Pi->Rj
• assignment edge – directed edge Rj->Pi

Resource Allocation Graph Example

• One instance of R1
• Two instances of R2
• One instance of R3
• Three instance of R4
• T1 holds one instance of R2 and is waiting for an instance of R1
• T2 holds one instance of R1, one instance of R2, and is waiting for an instance of R3
• T3 is holds one instance of R3

Resource Allocation Graph With A Deadlock

Resource With A Cycle But No Deadlock

Basic Facts

• If graph contains no cycles -> no deadlock
• If graph contains a cycle ->
  • if only one instance per resource type, then deadlock
  • if several instances per resource type, possibility of deadlock

Methods for Handling Deadlocks

• Ensure that the system will never enter a deadlock state:
  • Deadlock prevention
  • Deadlock avoidance
• Allow the system to enter a deadlock state and then recover
• Ignore the problem and pretend that deadlocks never occur in the system.

Deadlock Prevention

Invalidate one of the four necessary conditions for deadlock:

• Mutual Exclusion – not required for sharable resources (e.g., read-only files); must hold for non-sharable resources
• Hold and Wait – must guarantee that whenever a process requests a resource, it does not hold any other resources
  • Require process to request and be allocated all its resources before it begins execution, or allow process to request resources only when the process has none allocated to it.
  • Low resource utilization; starvation possible

교착 상태에 필요한 네 가지 조건 중 하나를 비활성화한다.

• 상호 제외 – 공유 가능한 리소스(예: 읽기 전용 파일)에는 필요하지 않다. 공유 불가능한 리소스에는 유지되어야 한다.
• 보류 및 대기 – 프로세스가 리소스를 요청할 때마다 다른 리소스를 보유하지 않도록 보장해야 한다.
• 실행을 시작하기 전에 프로세스가 모든 리소스를 요청하고 할당하도록 요구하거나 프로세스가 리소스를 할당하지 않은 경우에만 프로세스가 리소스를 요청하도록 허용한다.
• 낮은 리소스 활용률, 굶주림 가능성

---

• No Preemption –
  • If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released
  • Preempted resources are added to the list of resources for which the process is waiting
  • Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting
• Circular Wait – impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration

• 선점 없음 –
  • 일부 리소스를 보유 중인 프로세스가 즉시 할당할 수 없는 다른 리소스를 요청하면 현재 보유 중인 모든 리소스가 해제된다.
  • 프로세스가 대기 중인 리소스 목록에 미리 설정된 리소스가 추가된다.
  • 이전 리소스와 요청한 새 리소스를 되찾을 수 있는 경우에만 프로세스가 다시 시작된다.
• Circular Wait – 모든 리소스 유형의 총 주문을 부과하고 각 프로세스에서 열거 순서를 늘려 리소스를 요청하도록 요구한다.

Cirecular Wait

• Invalidating the circular wait condition is most common.
• Simply assign each resource (i.e. mutex locks) a unique number.
• Resources must be acquired in order.

• 순환 대기 조건을 무효화하는 것이 가장 일반적이다.
• 각 리소스(예: mutex 잠금)에 고유 번호를 할당하기만 하면 된다.
• 리소스를 순서대로 획득해야 한다.

Deadlock Avoidance

Requires that the system has some additional a priori information available

• Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need
• The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition
• Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes

시스템에 사용 가능한 a priori 정보가 추가로 있어야 한다.

• 가장 간단하고 유용한 모델은 각 프로세스가 필요할 수 있는 각 유형의 최대 리소스 수를 선언해야 한다.
• 교착 상태 회피 알고리즘은 리소스 할당 상태를 동적으로 검사하여 순환 대기 상태가 있을 수 없도록 한다.
• 리소스 할당 상태는 사용 가능한 리소스 및 할당된 리소스의 수와 프로세스의 최대 요구량에 따라 정의된다.

Safe State

• When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state
• System is in safe state if there exists a sequence <P1, P2, …, Pn> of ALL the processes in the systems such that for each Pi, the resources that Pi can still request can be satisfied by currently available resources + resources held by all the Pj, with j < I
• That is:
  • If Pi resource needs are not immediately available, then Pi can wait until all Pj have finished
  • When Pj is finished, Pi can obtain needed resources, execute, return allocated resources, and terminate
  • When Pi terminates, Pi +1 can obtain its needed resources, and so on

• 프로세스가 사용 가능한 리소스를 요청할 때 시스템은 즉시 할당하면 시스템이 안전한 상태로 유지되는지 여부를 결정해야 한다.
• 시스템에 있는 모든 프로세스의 시퀀스 <P1, P2, …, Pn>이 존재한다면, 각 Pi에 대해 Pi가 여전히 요청할 수 있는 리소스는 현재 사용 가능한 리소스 + 모든 Pj가 보유하고 있는 리소스(j < I)로 충족될 수 있다.
• 즉:
  • Pi 리소스 요구를 즉시 사용할 수 없는 경우, Pi는 모든 Pj가 완료될 때까지 기다릴 수 있다.
  • Pj가 완료되면, Pi는 필요한 자원을 획득하고, 실행하고, 할당된 자원을 반환하고, 종료할 수 있다.
  • Pi가 종료되면 Pi +1은 필요한 리소스를 얻을 수 있다.

Basic Facts

• If a system is in safe state -> no deadlocks
• If a system is in unsafe state -> possibility of deadlock
• Avoidance -> ensure that a system will never enter an unsafe state.

• 시스템이 안전한 상태일 경우 -> 교착 상태 없음
• 시스템이 안전하지 않은 상태일 경우 -> 교착 상태일 가능성
• 회피 -> 시스템이 안전하지 않은 상태로 전환되지 않도록 보장함.

Safe, Unsafe, Deadlock State

Avoidance Algorithms

• Single instance of a resource type
  • Use a resource-allocation graph
• Multiple instances of a resource type
  • Use the Banker’s Algorithm

• 리소스 유형의 단일 인스턴스
  • 리소스 할당 그래프 사용
• 리소스 유형의 여러 인스턴스
  • 은행원 알고리즘 사용

Resource-Allocation Graph Scheme

• Claim edge Pi -> Rj indicated that process Pj may request resource Rj; represented by a dashed line
• Claim edge converts to request edge when a process requests a resource
• Request edge converted to an assignment edge when the resource is allocated to the process
• When a resource is released by a process, assignment edge reconverts to a claim edge
• Resources must be claimed a priori in the system

• Claim edge Pi -> Rj는 프로세스 Pj가 리소스 Rj를 요청할 수 있음을 나타낸다. (점선으로 나타남)
• 프로세스가 리소스를 요청할 때 claim edge가 request edge로 변환된다.
• request edge는 리소스가 프로세스에 할당될 때 assignment edge로 변환된다.
• 프로세스가 리소스를 release하면 assignment edge가 claim edge로 다시 변환됩니다.
• 시스템에서 리소스를 우선 할당해야 합니다.

Resource-Allocation Graph

Unsafe State In Resource-Allocation Graph

Resource-Allocation Graph Alogorithm

• Suppose that process Pi requests a resource Rj
• The request can be granted only if converting the request edge to an assignment edge does not result in the formation of a cycle in the resource allocation graph

• 프로세스 Pi가 리소스 Rj를 요청한다고 가정한다.
• request edge를 assignment edge로 변환하면 리소스 할당 그래프에 주기가 형성되지 않는 경우에만 요청을 부여할 수 있습니다.

Banker's Algorithm

• Multiple instances of resources
• Each process must a priori claim maximum use
• When a process requests a resource it may have to wait
• When a process gets all its resources it must return them in a finite amount of time

• 여러 리소스 인스턴스
• 각 프로세스는 우선 최대 사용을 주장해야 한다.
• 프로세스가 리소스를 요청할 때 기다려야 할 수 있다.
• 프로세스가 모든 리소스를 확보하면 한정된 시간 내에 리소스를 반환해야 한다.

Data Structures for the Banker's Algorithm

Let n = number of processes, and m = number of resources types.

• Available: Vector of length m. If available [j] = k, there are k instances of resource type Rj available
• Max: n x m matrix. If Max [i,j] = k, then process Pi may request at most k instances of resource type Rj
• Allocation: n x m matrix. If Allocation[i,j] = k then Pi is currently allocated k instances of Rj
• Need: n x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj to complete its task

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

n = 프로세스 수, m = 리소스 유형 수이다.

• 사용 가능: 길이 m의 벡터. [j] = k를 사용할 수 있는 경우 리소스 유형 Rj의 k개의 인스턴스를 사용할 수 있다.
• 최대: n x m 행렬. Max [i,j] = k일 경우 프로세스 Pi는 리소스 유형 Rj의 최대 k개의 인스턴스를 요청할 수 있다.
• 할당: n x m 행렬. 할당 [i,j] = k이면 파이는 현재 Rj의 k개의 인스턴스가 할당된다.
• 필요: n x m 행렬. 만약 [i,j] = k가 필요하다면, Pi는 작업을 완료하기 위해 Rj의 인스턴스가 더 필요할 수 있다.

[i,j] 필요 = Max[i,j] – Allocation[i,j]

Safety Algorithm

1. Let Work and Finish be vectors of length m and n, respectively. Initialize:
   Work = Available
   Finish [i] = false for i = 0, 1, …, n- 1

2. Find an i such that both:
   (a) Finish [i] = false
   (b) Need_i <= Work
   If no such i exists, go to step 4

3. Work = Work + Allocation_i
   Finish[i] = true
   go to step 2

4. If Finish [i] == true for all i, then the system is in a safe state

1. Work와 Finish를 각각 길이 m과 n의 벡터로 하자. 초기화:
   Work = Available
   Finish[i] = i = 0, 1, …, n-1에 대해 거짓이다.

2. 다음 두 가지 모두와 같은 i를 찾는다.
   (a) Finish [i] = false
   (b) Need_i <= Work
   해당 i가 없으면 4단계로 이동한다.

3. Work = Work + Allocation_i
   Finish[i] = true
   2단계로 이동한다.

4. i 모두에 대해 Finish [i] == true인 경우 시스템은 안전한 상태이다.

Resource-Request Algorithm for Process P_i

Request_i = request vector for process P_i. If Request_i[j] = k then process P_i wants k instances of resource type R_j

1. If Request_i <= Need_i go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim
2. If Request_i <= Available, go to step 3. Otherwise P_i must wait, since resources are not available
3. Pretend to allocate requested resources to P_i by modifying the state as follows:
   Available = Available – Request_i;
   Allocation_i = Allocation_i + Request_i;
   Need_i = Need_i – Request_i;

• If safe -> the resources are allocated to P_i
• If unsafe -> P_i must wait, and the old resource-allocation state is restored

Request_i = 프로세스 P_i에 대한 요청 벡터이다. Request_i[j] = k인 경우 P_i 프로세스에서 리소스 유형 R_j의 k 인스턴스를 원한다.

1. Request_i <=Need_i인 경우 2단계로 이동한다. 그렇지 않으면 프로세스가 최대 클레임을 초과했기 때문에 오류 조건을 제기한다.
2. Request_i <= Available인 경우 3단계로 이동한다. 그렇지 않으면 리소스를 사용할 수 없으므로 P_i는 기다려야 한다.
3. 다음과 같이 상태를 수정하여 요청된 리소스를 P_i에 할당하는 척한다.
   Available = Available – Request_i;
   Allocation_i = Allocation_i + Request_i;
   Need_i = Need_i – Request_i;

• 안전한 경우 -> 리소스가 P_i에 할당된다.
• 안전하지 않은 경우 -> P_i를 기다려야 하며 이전 리소스 할당 상태가 복원된다.

Example of Banker's Algorithm

Example : P_1 Request (1,0,2)

Deadlock Detection

• Allow system to enter deadlock state
• Detection algorithm
• Recovery scheme

• 시스템이 교착 상태로 전환되도록 허용
• 검출 알고리즘
• 복구 계획

Single Instance of Each Resource Type

• Maintain wait-for graph
  • Nodes are processes
  • P_i -> P_j if P_i is waiting for P_j
• Periodically invoke an algorithm that searches for a cycle in the graph. If there is a cycle, there exists a deadlock
• An algorithm to detect a cycle in a graph requires an order of n^2 operations, where n is the number of vertices in the graph

• 대기 시간 그래프 유지 관리
  • 노드는 프로세스이다.
  • P_i가 P_j를 기다리는 경우 P_i -> P_j
• 그래프에서 주기를 검색하는 알고리즘을 주기적으로 호출한다. 주기가 있는 경우 deadlock 상태가 있다.
• 그래프에서 주기를 감지하기 위한 알고리즘에는 n^2 연산의 순서가 필요하다. 여기서 n은 그래프의 꼭짓점 수이다.

Resource-Allocation Graph and Wait-for Graph

Several Instances of a Resource Type

• Available: A vector of length m indicates the number of available resources of each type
• Allocation: An n x m matrix defines the number of resources of each type currently allocated to each process
• Request: An n x m matrix indicates the current request of each process. If Request[i][j] = k, then process P_i is requesting k more instances of resource type R_j.

• 사용가능: 길이 m의 벡터는 각 유형의 사용 가능한 리소스 수를 나타낸다.
• 할당: n x m 행렬은 각 프로세스에 현재 할당된 각 유형의 리소스 수를 정의한다.
• Request: n x m 행렬은 각 프로세스의 현재 요청을 나타낸다. Request[i][j] = k인 경우 P_i 프로세스가 리소스 유형 R_j의 인스턴스를 더 요청한다.

Detection Algorithm

1. Let Work and Finish be vectors of length m and n, respectively Initialize:
   (a) Work = Available
   (b) For i = 1,2, …, n, if Allocation_i != 0, then Finish[i] = false; otherwise, Finish[i] = true

2. Find an index i such that both:
   (a) Finish[i] == false
   (b) Request_i <= Work
   If no such i exists, go to step 4

3. Work = Work + Allocation_i
   Finish[i] = true
   go to step 2

4. If Finish[i] == false, for some i, 1<=i<=n, then the system is in deadlock state. Moreover, if Finish[i] == false, then P_i is deadlocked

Algorithm requires an order of O(m x n2) operations to detect whether the system is in deadlocked state

1. Work와 Finish를 각각 길이 m와 n의 벡터로 하자. 초기화:
   (a) Work = Available
   (b) i = 1,2, …, n의 경우, Allocation_i!= 0인 경우 Finish[i] = false, 그렇지 않은 경우 Finish[i] = true

2. 다음 두 가지 모두와 같은 index i를 구한다.
   (a) Finish[i] == false
   (b) Request_i <= Work
   해당 i가 없으면 4단계로 이동한다.

3. Work = Work + Allocation_i
   Finish[i] = true
   2단계로 이동하다

4. Finish [i] == false인 일부 i에 대해 1<=i<=n인 경우 시스템이 교착 상태에 있다. 또한 Finish[i] == false인 경우 P_i는 교착 상태가 된다.

알고리즘은 시스템이 교착 상태에 있는지 여부를 감지하기 위해 O(m x n^2) 연산 순서가 필요하다.

Example of Detection Algorithm

Detection-Algorithm Usage

• When, and how often, to invoke depends on:
  • How often a deadlock is likely to occur?
  • How many processes will need to be rolled back?
    • one for each disjoint cycle
• If detection algorithm is invoked arbitrarily, there may be many cycles in the resource graph and so we would not be able to tell which of the many deadlocked processes “caused” the deadlock.

• 언제, 얼마나 자주 호출할지는 다음에 따라 달라진다.
  • 교착 상태가 얼마나 자주 발생할 것 같는가?
  • 롤백해야 하는 프로세스는 몇 개인가?
    • 각 분리 주기에 하나씩
• 탐지 알고리즘이 임의로 호출될 경우 리소스 그래프에 많은 주기가 있을 수 있으므로 교착 상태를 초래한 많은 프로세스 중 어떤 것이 교착 상태를 초래했는지 알 수 없다.

Recovery from Deadlock

Recovery from Deadlock: Process Termination

• Abort all deadlocked processes
• Abort one process at a time until the deadlock cycle is eliminated
• In which order should we choose to abort?
  • 1. Priority of the process
  • 2. How long process has computed, and how much longer to completion
  • 3. Resources the process has used
  • 4. Resources process needs to complete
  • 5. How many processes will need to be terminated
  • 6. Is process interactive or batch?

• 교착 상태에 빠진 모든 프로세스 중단
• 교착 상태가 해소될 때까지 한 번에 하나의 프로세스 중단
• 우리는 어떤 순서로 abort를 선택해야 하는가?
  • 1. 프로세스의 우선순위
  • 2. 프로세스가 계산한 시간 및 완료까지 걸리는 시간
  • 3. 프로세스가 사용한 리소스
  • 4. 리소스 프로세스를 완료해야 함
  • 5. 종료해야 하는 프로세스 수
  • 6. 프로세스는 대화형입니까, 배치형입니까?

Recovery from Deadlock: Resource Preemption

• Selecting a victim – minimize cost
• Rollback – return to some safe state, restart process for that state
• Starvation – same process may always be picked as victim, include number of rollback in cost factor

• 피해자 선정 – 비용 최소화
• 롤백 – 안전한 상태로 돌아가 해당 상태에 대한 프로세스를 다시 시작한다.
• 기아 – 동일한 프로세스를 항상 피해자로 선택할 수 있으며, 비용 요소에 롤백 횟수를 포함할 수 있다.