06. Deadlocks

Deadlock Problem

Deadlock

Deadlock

• 일련의 프로세스들이 서로가 가진 자원(Resource)을 기다리며 block된 상태

Resource

• 하드웨어, 소프트웨어를 모두 포함하는 개념
• 프로세스가 자원을 이용하는 절차: Request -> Allocate -> Use -> Release

 

Deadlock 발생 조건

(1) Mutual exclusion

• 매 순간 하나의 프로세스만이 자원을 사용할 수 있음

(2) No preemption

• 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않는다.

(3) Hold and wait

• 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 갖고 있음

(4) Circular wait

• 자원을 기다리는 프로세스간에 사이클이 형성되어야 함
• P0은 P1의 자원을 기다리고, P1은 P2의 자원을 기다리고 , ... Pn-1은 Pn의 자원을 기다리고, Pn은 P0의 자원을 기다림

 

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

Vertex

• Process P
• Resource R

Edge

• request edge Pi -> Ri
• assignment edge Ri -> Pi

• 그래프에 cycle이 없으면 deadlock이 아니다.
• 그래프에 cycle이 있을 때,
  • if only one instance per resource type(자원의 인스턴스가 하나밖에 없으면), then deadlock
  • if several instances per resource type, possibility of deadlock

---

Deadlock 처리방법

Deadlock Prevention

Deadlock Prevention

• 자원 할당 시 Deadlock의 필요 조건 4가지 중 어느 하나가 만족되지 않도록 하는 것

(1) Mutual Exclusion

• 공유해서는 안되는 자원의 경우 반드시 성립해야 하므로 막을 수 없음

(2) No Preemption

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

(3) Hold and Wait

• 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
  • 프로세스 시작 시 모든 필요한 자원을 할당하는 방법 -> 비효율적
  • 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청하는 방법

(4) Circular Wait

• 모든 자원에 할당 순서를 정하여 정해진 순서대로만 자원 할당
  • ex. 순서가 3인 자원 Ri을 보유중인 프로세스가 순서가 1인 자원 Rj을 할당받기 위해서는 우선 Ri를 release 해야 한다.

👉 Deadlock Prevention 방법은 deadlock을 원천적으로 막을 수는 있지만, 그 자원에 대한 이용률(Utilization)이 낮아지고, 처리량(Throughput)을 감소시켜 전체 시스템의 성능을 나쁘게 만들며, Starvation이 발생할 수 있다는 단점을 지니고 있다.

 

👉 가끔 발생하는 event인 deadlock을 생각해서, 이와 같이 제약조건을 많이 달아놓는 것은 상당히 비효율적

 

Deadlock Avoidance

Deadlock Avoidance

• 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당 -> 동적으로 조사
• 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하는 방법
• 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당

safe state

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

safe sequence

• Pi의 자원 요청이 "가용 자원 + 모든 Pj(j<i)의 보유자원"에 의해 충족되어야 함
• 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
  • Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj(j<i)가 종료될 때까지 기다린다.
  • Pi-1이 종료되면 Pi의 자원요청을 만족시켜 수행

👉 시스템이 safe state에 있으면 no deadlock, 시스템이 unsafe state에 있으면 possibility of deadlock

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

 

Avoidance Algorithm

(1) Resource Allocation Graph Algorithm

• Single instance per resource types 일 때 사용
• Claim edge Pi -> Rj
  • 프로세스 Pi가 자원 Rj를 미래에 요청할 수 있음을 뜻함 (점선으로 표시)
  • 프로세스가 해당 자원 요청 시 request edge 로 바뀜 (실선)
  • Rj가 release되면 assignment edge는 다시 claim edge로 바뀐다
• request edge의 assignment edge 변경 시 (점선을 포함하여) cycle이 생기지 않는 경우에만 요청 자원 할당
• Cycle 생성 여부 조사 시 프로세스 수가 n일 때 O(N^2) 시간이 걸린다.

 

(2) Banker's Algorithm

• Multiple instances per resource types 일 때 사용
• 가정: 모든 프로세스는 자원의 최대 사용량을 미리 명시하고 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 자원을 다시 반납한다.
• 방법: 자원 요청 시 safe 상태를 유지할 경우에만 할당
  • 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택해서 자원 할당 (그런 프로세스가 없으면 unsafe 상태)
  • 자원을 할당받은 프로세스가 종료되면 모든 자원을 반납
  • 모든 프로세스가 종료될 때까지 위의 과정 반복

Deadlock Detection and Recovery

Deadlock Detection and Recovery

• Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견 시 recover

Deadlock Detection

• Resource type 당 single instance인 경우: 자원할당그래프의 cycle이 곧 deadlock을 의미
  • Wait-for-graph 알고리즘: 자원할당 그래프를 변형해서 프로세스만으로 node를 구성
    • Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk -> Pj
    • Wait-for-graph에 사이클이 존재하는 지 주기적으로 조사: O(n^2)

 

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

 

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이 발생하지 않는다고 생각하고 아무런 조치도 취하지 않음
  • Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있음
  • 만약 deadlock이 발생한 경우 사람이 직접 process를 죽이는 등의 방법으로 대처
• UNIX, Windows 등 대부분의 범용 OS가 채택하고 있는 방법