[운영체제] 7. Deadlocks

kocw 반효경 교수님의 운영체제 강의를 수강 후 작성한 글입니다.

1. Deadlock (교착상태)

Deadlock: 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태

Resource(자원): 하드웨어, 소프트웨어 등을 모두 포함하는 개념. ex) I/O device, CPU cycle, memory space, semaphore 등.

프로세스가 자원을 사용하는 절차: Request -> Allocate -> Use -> Release

 

Deadlock example 1) 하드웨어 자원에 대한 deadlock

- 시스템에 2개의 tape drive가 있고, 프로세스 P1과 P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있는 경우

Deadlock example 2) 소프트웨어 자원에 대한 deadlock

- Binary semaphores A and B

           P0            P1

           P(A)         P(B)

           P(B)         P(A)

Deadlock의 4가지 발생 조건

- Mutual exclusion(상호 배제): 매 순간 하나의 프로세스만이 자원을 사용할 수 있음

- No preemption(비선점): 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음 

- Hold and wait(보유 대기): 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음

- Circular wait(환형 대기): 자원을 기다리는 프로세스간에 사이클이 형성되어야 함

Resource-Allocation Graph (자원 할당 그래프)

- Vertex: Process P = {P1, P2, P3, ..., Pn}, Resource R = {R1, R2, R3, ..., Rm}

- Edge: request edge Pi->Rj, assignment edge Rj->Pi

 

 

P1이 R2, P2가 R1을 요청하고 있으며, P1이 R1을, P2가 R2를 점유하고 있다.

 

자원 할당 그래프에서, 그래프에 cycle이 없으면 dealock이 아니다.

그래프에 cycle이 있으면, deadlock일 수도, 아닐 수도 있다.

- if only one instance per resource type, then deadlock (자원 인스턴스가 한개밖에 없고 cycle이 존재하면 deadlock임)

- if several instances per resource type, possibility of deadlock (자원 인스턴스가 여러개이고 cycle이 존재하면 deadlock의 가능성이 있음)

 

이 경우 사이클이 존재하지만, 자원 모두가 cycle에 기여하고 있지 않으므로 deadlock이 아니다. P3가 R2를 반납하면 되기 때문이다.

 

 

하지만 이 경우, R2의 인스턴스 2개가 모두 cycle에 기여하고 있기 때문에 deadlock이다. 

Deadlock의 처리 방법

Deadlock Prevention (적극적, 예방): 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것

Deadlock Avoidance (소극적, 예방): 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당. 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당.

Deadlock Detection and recovery: Deadlock 발생은 허용하되, 그에 대한 detection 루틴을 두어 deadlock 발견 시 recover

Deadlock Ignorance: Deadlock을 시스템이 책임지지 않음. UNIX를 포함한 대부분의 OS가 채택하는 방법

Deadlock Prevention

Mutual Exclusion: 공유해서 안되는 자원의 경우 반드시 성립해야 함! -> 방지 불가능

Hold and wait: 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다. -> 보유 한 상태로 대기하지 않도로 한다!

방법 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법 -> 모든 자원을 균일하게 사용하는 것이 아니기 때문에 자원 낭비임

방법 2. 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청

No preemption: process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨. 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작되며, state를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용한다.(CPU, memory)

Circular wait: 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당. 예를 들어, 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj를 할당받기 위해서는 Ri를 release해야 한다. 

 

→ utilization 저하, throughput 감소, starvation 문제

Deadlock Avoidance

자원 요청에 대한 부가 정보를 이용해서 자원 할당이 deadlock으로부터 safe한 지를 동적으로 조사, 안전한 경우에만 할당.

가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법이다.

 

safe state: 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태

safe sequence

- 프로세스의 sequence <P1, P2, ..., Pn>이 safe하려면 Pi(1<=i<=n)의 자원 요청이 가용 자원 + 모든 Pj(j<i) 의 보유 자원에 의해 충족되어야 함.

- 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장

• Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj(j<i)가 종료될 때까지 기다린다.
• Pi-1이 종료되면 Pi의 자원요청을 만족시켜 수행한다.

Deadlock Avoidance

- 시스템이 unsafe state에 들어가지 않는 것을 보장

- 2가지 경우의 avoidance 알고리즘이 존재

• Single instance per resource types: Resource-Allocation Graph algorithm 사용
• Multiple instances per resource types: Banker's algorithm 사용

Resource-Allocation Graph algorithm

Claim edge Pi->Rj

• 프로세스 Pi가 자원 Rj를 미래에 요청할 수 있는 경우를 의미하며, 점선으로 표시
• 프로세스가 해당 자원 요청 시 request edge인 실선으로 바뀜
• Rj가 release되면 assignment edge는 다시 claim edge로 바뀐다.

- Request edge의 assignment edge 변경 시 점선을 포함하여 cycle이 생기지 않는 경우에만 요청 자원을 할당한다.

- Cycle 생성 여부 조사 시, 프로세스의 수가 n일 때 O(n^2) 시간이 걸린다.

 

위의 그림에서 P2가 R2를 요청해도 자원을 내어놓지 않는다. 만약 P2가 R2를 할당 받으면 P1->R2의 점선을 포함하여 cycle이 존재하게 되고, 이는 곧 P1이 R2를 요청할 경우 deadlock이 발생할 가능성이 있음을 의미하기 때문이다.

Banker's algorithm

- 가정

• 모든 프로세스는 자원의 최대 사용량을 미리 명시
• 프로세스가 요청 자원을 모두 할당받은 경우, 유한 시간 안에 이들 자원을 다시 반납한다.

- 방법

• 기본 개념: 자원 요청 시, safe 상태를 유지할 경우에만 할당
• 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택 (그런 프로세스가 없으면 unsafe 상태)
• 그런 프로세스가 있으면 그 프로세스에게 자원을 할당
• 할당받은 프로세스가 종료되면 모든 자원을 반납
• 모든 프로세스가 종료될 때까지 이러한 과정을 반복

example

3 resource types: A(10), B(5), C(7) instances.

 

 

Q) 처음, P0가 A 자원 1개를 요청한다면 이 요청을 받아들이는가?

A) No. P0의 최대 자원 요청량은 A(7), B(4), C(3)으로 현재의 가용 자원만으로 충족이 불가능하다. 따라서 현 시점에서 A 자원 한개만 요청하더라도 이 요청을 받아들이지 않는다. 

 

safe sequence <P1, P3, P4, P2, P0> 가 존재하므로 시스템은 safe state.

P1의 Need A(1), B(2), C(2)를 현재 가용 자원 A(3), B(3), C(2)로 처리 가능하므로 할당

P1 자원 반납 후 가용 자원 5, 3, 2

P3(0, 1, 1) 할당 가능. 할당 -> 반납 후 가용 자원 7, 4, 3

P4(4, 3, 1) 할당 가능. 할당 -> 반납 후 가용 자원 7, 4, 5

P2(6, 0, 0) 할당 가능. 할당 -> 반납 후 가용 자원 10, 4, 7

P0(7, 4, 3) 할당 가능. 할당 -> 반납 후 가용 자원 10, 5, 7

Deadlock Detection and Recovery

Deadlock Detection

- Resource type 당 single instance인 경우: 자원할당 그래프에서의 cycle이 곧 deadlock을 의미

- Resource type 당 multiple instance인 경우: Banker's algorithm과 유사한 방법 활용

 

Wait-for graph 알고리즘

- Resource type 당 single instance인 경우

- 자원할당 그래프의 변형으로 프로세스만으로 node가 구성되어 있다.

- Pi가 가지고 있는 자원을 Pj가 기다리는 경우, Pj->Pi

- algorithm: wait-for graph에 사이클이 존재하는지 주기적으로 조사. O(n^2)의 시간복잡도.

 

 

 

 

example

3 resource types: A(7), B(2), C(6) instances

 

 

No Deadlock: sequence <P0, P2, P3, P1, P4> will work! -> 현재에 대해 deadlock이 아니라고 판단.

(Request는 추가 요청 가능량이 아니라 현재 실제로 요청한 자원량을 나타냄)

 

P2의 request가 (0, 0, 1) 이라고 가정하자.

P0가 요청 후 자원을 반납해도 (0, 1, 0)으로 현재의 Request를 충족 가능한 Process가 존재하지 않는다. -> deadlock detect!

 

Recovery

• Process termination
  
  • Abort all deadlocked processes
  • Abort one process at a time until the deadlock cycle is eliminated
• Resource Preemption
  • 비용을 최소화할 victim의 선정
  • safe state로 rollback하여 process를 restart
  • Starvation 문제
    • 동일한 프로세스가 계속해서 victim으로 선정되는 경우
    • cost factor에 rollback 횟수도 같이 고려 (희생자로 선택되는 횟수를 고려)

Deadlock Ignorance

Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음 -> Unix, Windows 등 대부분의 범용 OS가 채택하는 방법

Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있음.

만약 시스템에 deadlock이 발생한 경우, 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 등의 방법으로 대처