Deadlock

Deadlock

1.   System model

·       Resource R1,R2,R3….(CPU 주기, 메모리 공간, I/O 장치…)

·       각 Ri는 instances Wi를 가진다.(각 instance들은 서로 동등한 관계, 프로세스는 이를 구분하지 않는다.)

·       프로세스가 자원을 사용하는 순서

o   Request  -> use -> release

2.   Deadlock(교착 상태의 특징)

·       교착상태는 다음 4가지 조건이 모두 만족될 때 발생한다.

o   Mutual exclusion : 한 resource는 한 순간에 한 프로세스만 사용한다.

o   No preemption : 한 프로세스가 자발적으로 방출해야만 다른 프로세스가 사용할 수 있다.

o   Hold and wait : 최소한 하나의 자원을 점유한 채, 다른 프로세스에게 점유된 자원을 위해 대기하는 프로세스가

                      반드시 존재해야 한다.

o   Circular wait : 원형 대기.

3.   Resource-allocation graph

·       그래프는 vertex set과 edge set의 pair.

o   Vertex set : 각 프로세스들 P1, P2, P3… + Resource type R1, R2, R3…

o   Edge set : request edge(Pi -> Ri) + assignment edge(Wi -> Pi)

·       각 프로세스는 원, 자원은 사각형, 인스턴스는 점으로 표시.

·       프로세스가 자원을 요청하면, request edge 추가. 할당 가능하면 즉시 assignment edge 생성.

·       그래프에 cycle이 없다면, deadlock x.

·       그래프에 cycle이 있다면, 각 자원 타입마다 오직 1개의 instance만 있다면, deadlock.

·       각 자원 타입마다 여러 개의 instance가 있다면, deadlock 일수도 아닐 수도.

4.   Deadlock handling 방법에는 3가지가 있다.

a.   Deadlock이 발생하지 않도록 보장.(prevention, avoidance)

b.   Deadlock이 발생하지만, 탐지, 회복할 수 있도록 함.(detection, recover)

c.    Deadlock이 발생하지 않는 것처럼 행동.(대부분의 운영체제가 채택)

                       i.        Deadlock을 예방, 처리 하는 과정이 너무 큰 오버헤드

                      ii.        Deadlock 발생 빈도가 아주 낮다.

5.   Deadlock prevention

·       Deadlock 의 조건 성립을 막아서, deadlock이 발생하지 않도록 보장.

o   Mutual exclusion : 공유가 불가능한 자원들이 존재하므로 방지 불가.

o   Hold and wait : all or nothing

·       1) 각 프로세스가 실행되기 전에 필요한 자원을 모두 요청하고, 모두 할당 받은 후에 실행되게 한다.

·       2) 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있다.

-> 자원 이용도 저하, starvation 가능.

o   No preemption : 만일, 어떤 자원을 점유하고 있는 프로세스가 즉시 할당할 수 없는 자원을 요청하여 대기해야 하면, 그 프로세스가 점유하고 있는 모든 자원이 선점된다. 선점된 자원들은 이 프로세스가 기다리는 자원들의 리스트에 추가되며, 이 자원들을 모두 획득할 수 있을 때에 재 시작 된다.

o   Circular wait : 모든 자원 타입에 순서를 부여하여, 오름차순으로만 요청할 수 있도록 한다.

                   (상위 자원을 점유하고 있으면, 하위 자원 요청 불가.-> 그래프에서 back edge가 만들어지지 않는다.)

6.   Deadlock avoidance

·       Deadlock 발생 가능성이 존재하면, 자원 할당 요청을 받아 들이지 않는다.

·       Unsafe state로는 절대 진입하지 않는다.

·       자원 할당 요청을 들어주었을 때, 발생할 수 있는 worst case를 찾아서 safe한지(circular wait 발생하지 않는지) 검사한다.

 (각 자원 타입 별 최대 자원 요구량 정보 필요)

·       Resource allocation state는 현재 남아있는 자원, 할당된 자원, 최대 자원 요구량에 의해 결정된다.

o   Safe state : 프로세스들이 모두 자원의 최대치를 요구하더라도, deadlock을 야기하지 않고 할당해 줄 수 있는 safe sequence가 존재한다면 safe. 비록 당장 할당이 불가해도, 다른 프로세스의 수행이 끝나고 할당하여 모든 프로세스를 마칠 수 있는 sequence가 존재해야 한다.

o   Unsafe state : deadlock 의 가능성이 존재하는 상태. 반드시 deadlock이 발생하는 것은 아님.

·       Avoidance algorithm

o   Resource allocation graph (각 자원 별 instance가 1개씩 있을 때)

·       Claim edge(Pi -> Rj) : Pi가 미래에 Rj를 요청할 가능성이 있음을 의미

·       프로세스가 실행되기 전에 모든 Claim edge들이 추가되어야 한다.

·       판단 방법: 자원 할당을 가정했을 때 , claim edge를 포함하여 cycle이 만들어 진다면 unsafe 하므로 할당 x.

(해당 request edge -> assignment edge가 cycle을 형성하지 않는다면 할당.)

o   Banker's algorithm(각 자원 별 여러 개의 instance가 있을 때)

·   프로세스 별 필요한 자원의 최대 개수 정보 필요.

·   추가 자료구조 필요.( # of process : n, # of resource : m)

• Available : m 1차원 배열, 각 종류의 자원이 현재 몇 개가 남아있나. Available[j] = k.
• Max : n*m 2차원 배열, 각 프로세스가 최대로 필요로 하는 각 자원의 개수. Max[i][j] = k.
• Allocation : n*m 2차원 배열, 각 프로세스에게 현재 할당된 각 자원의 개수. Allocation[i][j] = k.
• Need : n*m 2차원 배열, 각 프로세스가 추가적으로 필요한 자원의 수. Need[i][j] = Max[i][j] - allocation[i][j]

·   Safety algorithm.

• 시스템이 safety 한지 판단하는 방법.
• work : m 1차원 배열, finish : n 1차원 배열.

·       Work = available, finish[i] = false로 초기화.

·        a) finish[i] == false ,b) need[i] <= work 를 모두 만족하는 i 찾는다.

 (아직 끝나지 않은 프로세스 들 중, 현재 자원을 몰빵하면 끝날 애들을 찾는다. 끝나면 전부 회수.)

·        i를 찾았다면, work = work + allocation[i], finish[i] = true 후 다시 위 조건을 만족하는 i를 찾는다.

·        i가 없다면, 모든 i값에 대해 finish[i] == true 라면 safe. 단 하나라도 false라면 unsafe 이다.

·       Resource-request algorithm.

§  Pi가 자원을 요청했을 때, 줄지 말지 결정하는 방법.

§  Request-i : n 1차원 배열, Pi의 자원 요구량 의미.

·       Request-i <= need-i 이 아니라면 error

·       Request-i <=  available-I 이 아니라면 Pi는 wait.

·       제대로 요청했고, 할당해줄 수 있는 자원이 있다면, 자원을 할당해 준 것처럼 자료구조만 변경해본다.

·       Available = available - request-I, allocation-I = allocation + request-I, need-I = need-I - request-I

·       이 상태에서 safety 알고리즘을 적용하여, safe하다면 자원을 실제로 할당한다. Unsafe하다면 자료구조를 복구 후 Pi는 wait한다.

6.   Deadlock detection

·       Deadlock에 들어갔을 때, 탐지 및 회복하기 위한 방법 필요.

·       Detection algorithm.

o   Wait-for graph(각 자원 별 1개의 instance 존재 시)

·       노드는 process Pi만 존재, Pi -> Pj (Pi는 Pj가 현재 점유중인 자원을 기다리는 상태.)

(노드의 개수를 줄여 complexity 줄이기 위함.)

·       Cycle의 존재 여부를 검사, 존재한다면 deadlock.

§  Reduction of resource graph(cycle 탐지에 사용)

·       각 프로세스가 dormant state에 있다고 가정.(추가적인 자원 요청을 하지 않는다.)

·       각 프로세스는 자원을 얻고, 작업 완료 후, 전부 반납한다고 가정.

·       자원을 요청하지 않는 프로세스와 edge를 같이 지우고, 연쇄적으로 reduce한다. Irreducible == deadlock!

·       Reduction order는 무관하다.

o   Deadlock detection algorithm.

·       Work = available // allocation[i] = 0 이면 finish[i] = true, 아니면 false.

·       a)  finish[i] == false && b) request[i] <= work (안 끝난 애들 중, 요청 량이 현재 남은 것으로 해결 가능하다면)

·       Work = work + allocation, finish[i] = true 후 위 조건 만족하는 프로세스 계속 탐색.

·       만족하는 프로세스가 없다면, finish[i] 가 모두 true라면 deadlock x, 하나라도 false라면 deadlock o.

-> banker's algorithm과 다르게 프로세스들이 dormant state라고 가정 + 현재 상태만 고려.

8.   Recovery from deadlock.

·       Process termination(둘 중 하나)

o   Deadlock에 빠진 프로세스를 모두 중지. -> 모든 프로세스의 연산 결과들이 모두 소실되므로 비용이 크다.

o   Deadlock이 제거될 때까지 하나씩 중지. -> 계속해서 detection 수행해야 하므로 오버헤드가 크다.

·       Resource preemption(세가지를 모두 고려)

o   Selecting of a victim - victim process를 선정해서, 자원을 선점하는 방식.

o   Rollback - 그 process를 safe state로 후퇴시키고, 그 상태부터 재 시작. -> 이전 정보를 갖고 있어야 함.

o   Starvation - 같은 process가 반복적으로 victim이 되지 않도록 보장해야 함.(# of rollback을 카운트)

9.   Avoidance : worst case( 모든 프로세스가 동시에 maximum 자원 요구) 시에도 safe sequence가 존재할 때만 할당.

Detection : best case(모든 프로세스가 추가 자원 요구 x), 현재 자원 요구량 만 고려.