7. 데드락

솔·2022년 4월 18일

OS

목록 보기

7/12

Deadlock
- 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
Resource
- 하드웨어, 소프트웨어 등을 포함하는 개념
- (예) i/o device, cpu cycle, memory space, semaphore 등
- 프로세스가 자원을 사용하는 절차
  - Request, Allocate, Use, Release
ex1
- 시스템에 2개의 tape drive가 있다
- 프로세스 P1과 P2각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다
ex2
- Binary semaphores A and B
  P0 P1
  P(A); P(B);
  P(B); P(A);

P0	P1
P(A);	P(B);
P(B);	P(A);

Mutual exclusion (상호 배제)
- 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
No preemption
- 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
Hold and wait
- 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
Circular wait
- 자원을 기다리는 프로세스간 사이클이 형성되어야 함
- 프로세스 P0,P1,....,Pn이 있을 때 P0은P1이 가진 자원을 기다리고 ... Pn은 P0이 가진 자원을 기다리는 사이클 형성

위 예시 1은 그래프에 cycle이 없으므로 deadlock이 아니다

위 예시 2의 두 그림은 cycle이 존재하지만

왼쪽그림은 자원이 모두 사이클을 형성 하고있어 데드락 상태지만

오른쪽 그림은 모든 자원이 사이클을 형성 하는 것은 아니라 데드락 상태가 아니다.

Deadlock Prevention
- 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
Deadlock Avoidance
- 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당
- 시스템 State가 원래 state로 돌아올 수 있는 경우에만 자원 할당
Deadlock Detection and recovery
- Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover
Deadlock Ignorance
- Deadlock을 시스템이 책임지지 않음
- UNIX를 포함한 대부분의 OS가 채택

1,2 예방

3,4 발생하게 놔둠

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의 자원요청을 만족시켜 수행한다
시스템이 safe state에 있으면 → No deadlock
시스템이 unsafe state에 있으면 → possibility of deadlock
Deadlock Avoidance
- 시스템이 unsafe state에 들어가지 않는 것을 보장
- 2가지 경우의 avoidance 알고리즘
  - Single instance per resource types → Resource Allocation Graph Algorithm
  - Multiple instances per resource types → Banker’s 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) 시간이 걸린다

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

Deadlock Detection
- Resource type 당 single instance 인 경우
  - 자원할당 그래프에서의 cycle이 곧 deadlock을 의미
- Resource type 당 multiple instance인 경우
  - Banker’s algorithm과 유사한 방법 활용
Wait-for graph 알고리즘
- Resource type 당 single instance인 경우
- Wait-for graph
  - 자원할당 그래프의 변형
  - 프로세스만으로 node 구성
  - Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk→Pj
- Algorithm
  - Wait-for graph에 사이클이 존재하는지를 주기적으로 조사
  - O(n^2)

Graph를 활용한 Detection 방법

Banker’s Algorithm과 유사하게 Detection

Deadlock이 일어나지 않는다고 생각하고 아무런 조치를 취하지 않음
- Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있음
- 만약, 시스템에 deadlock 이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 등의 방법으로 대처
- UNIX, Windows 등 대부분의 범용 OS가 채택