[운영체제] Deadlock

Deadlock

# Deadlock
# Deadlock 발생의 4가지 조건
# 자원 할당 그래프
# Deadlock의 처리 방법

---

✍️ 본 포스팅은 이화여자대학교 반효경 교수님의 "운영체제" 강의를 들으며 정리한 내용입니다.

 

---

＊Deadlock (교착상태)

• 각 차들이 보유한 자원(공간)을 서로 내놓지 않고, 내놓으라고 요구만 하고 있는 상태
• 어느 누구도 양보를 하지 않으면 더이상 진행이 안됨

---

 

- Deadlock

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

- Resource (자원)

• 하드웨어, 소프트웨어 등을 포함하는 개념
• ex) I/O device, CPU cycle, memory space, semaphore 등
• 프로세스가 자원을 사용하는 절차
  1. Request (자원 요청)
  2. Allocate (자원 획득)
  3. Use (자원 사용)
  4. Release (자원 반납)

- Deadlock 예시 1

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

- Deadlock 예시 2

• Binary semaphores A and B
• P0가 A를 가지고 있고 B를 요구하는 상황에, P1이 이미 B를 가지고 있어 Deadlock에 빠진 상태

---

＊Deadlock 발생의 4가지 조건

- Mutual exclusion (상호 배제)

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

- No preemption (비선점)

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

- Hold and wait (보유 대기)

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

- Circular wait (순환 대기)

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

---

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

Deadlock 상태인지 판단하기 위해서는 "자원 할당 그래프"라는 것을 주로 사용한다고 합니다.

- Vertex

• Process P = {P1, P2, .... , Pn)
• Resource R = {R1, R2, .... , Rm)

- Edge

• request edge(자원 요청 상황) Pi -> Rj
• assignment edge(자원 보유 상황) Rj -> Pi

- 그래프에 cycle이 없으면 dealock이 아니다.

- 그래프에 cycle이 있으면

• 자원 R에 인스턴스(그림에서는 점 하나)가 하나뿐이면 Deadlock
• R에 인스턴스가 여러개이면 Deadlock일 수도 아닐수도
  • 왼쪽 그림의 경우 Deadlock : Cycle 마지막에 아직 내놓여지지 않은 자원을 P3가 요구하고 있음
  • 오른쪽 그림의 경우 Deadlock 아님

---

＊Deadlock의 처리 방법

- Deadlock Prevention

• 자원 할당 시 Deadlock의 4가지 필요조건 중 어느 하나를 불만족시키는 것

- Deadlock Avoidance

• 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원 할당
• 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당

- Deadlock Detection and recovery

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

- Deadlock Ignorance

• Deadlock을 시스템이 책임지지 않음
• UNIX를 포함한 대부분의 OS가 채택

동시에 두 개 이상의 작업 처리

• 예) UNIX, MS Windows 등에서는 한 명령의 수행이 끝나기 전에 다른 명령이나 프로그램 수행 가능

---

＊Deadlock Prevention

- Mutual Exclusion (상호 배제)

• 공유해서는 안되는 자원의 경우 반드시 성립해야함

- Hold and Wait (보유 대기)

• 프로세스가 자원을 요청 시 다른 어떤 자원도 가지고 있지 않아야 한다.
• 방법 1
  • 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
• 방법 2
  • 자원이 필요할 경우, 보유 자원을 모두 놓고 다시 요청

- No Preemption (비선점)

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

- Circular Wait

• 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
• ex) 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj를 할당받기 위해서는
  우선 Ri를 release(반납)해야 한다.
• -> 자원 이용률 저하, 시스템 성능이 감소, starvation 문제
  등 의 문제가 생길 수 있다.

---

＊Deadlock Avoidance

• 프로세스가 시작될 때, 해당 프로세스가 평생 쓸 자원의 최대량을 미리  알고있다고 가정하고 deadlock을 피해감
• 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로부터 안전한지를 동적으로 조사해서
  안전한 경우에만 자원 할당
• 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원 별 최대 사용량을 미리 선언하도록 하는 방법임

- 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의 자원요청을 만족시켜 수행한다.
• 방법 2
  • 자원이 필요할 경우, 보유 자원을 모두 놓고 다시 요청

• 시스템이 safe state에 있으면 -> no deadlock
• 시스템이 unsafe state에 있으면 -> possibility of deadlock

- Deadlock Avoidance

• 시스템이 unsafe state에 들어가지 않는 것을 보장
• 2가지 경우의 avoidance 알고리즘
  • 자원의 인스턴스가 1개씩만 존재하면 자원 할당 그래프 사용
  • 자원의 인스턴스가 자원 당 여러개 존재하면 Banker's Algorithm 사용

1. 자원 할당 그래프를 사용한 방법

- Claim edge (점선 화살표)  Pi -> Rj

• 프로세스 Pi 가 자원  Rj 를 미래에 요청할 수 있음을 뜻함
• 프로세스가 해당 자원 요청 시 request edge로 바뀜 (실선)
• Rj 가 반납되면 자원할당 실선은 다시 점선으로 바뀐다.
• 위 그림은 점점 오른쪽 단계로 바뀌게 되는데, 맨 오른쪽 상황에서
  현재 deadlock은 아니지만 P1이 R2를 요청하게 되면 (실선으로 바뀌면) deadlock 상황에 놓일 수 있다.
• 요청 edge의 자원할당 edge 변경 시 (점선 포함) cycle이 생기지 않는 경우에만 요청 자원을 할당한다.
• Cycle 생성 여부 조사시 프로세스 수가 n일 때 시간복잡도 O(n^2)이 걸린다.

2. Banker's Algorithm을 사용한 방법

- 가정

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

- 방법

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

- 사용 예시

• 총 자원 수 A 10개, B 5개, C 7개
• Allocation : 각 프로세스 별로 자원을 할당한 수를 행렬로 나타냄
• Available : 가용 가능 수 = 자원의 총 수 - 할당 수
• Max : 각 프로세스가 실행될 때 각 자원을 사용할 수 있는 최대 수 (미래까지 생각한)
• Need : 미래에 더 필요한 자원의 수
• P0를 예로들면
  • 자원 B를 1개 할당 중
  • P0 ~ P4 모두 확인해보니 가용 가능한 자원이 A 3개, B 3개 C 2개임
  • 그런데 P0는 실행 중 최대 A 7개, B 5개, C 3개까지 요청할 가능성이 있음
  • 따라서 A 7개, B 4개 C 3개가 더 필요함
  • Banker's Algorithm에 의하면 가용 자원 (현재 A 3개, B 3개, C2개)이
    미래까지 생각한 필요 자원 (현재 A 7개, B 4개, C 3개) 이상이 안되면
    P0가 자원을 달라고 요청해도 주지 않는 방식이다.
  • 가용 자원이 충족될 때까지 기다리며 모든 프로세스가 작업이 완료 가능한
    시퀀스 P1 -> P3 -> P4 -> P2 -> P0 가 존재하므로 이 시스템인 safe state(안전 상태)에 있다고 
    정의하고 이 safe state를 항상 유지하게 된다.

---

＊Deadlock Detection and Recovery

• 기존의 자원할당 그래프에서 자원 모형을 빼버림
• 예시) 우측 그림에서 P4는 P1이 가진 자원을 요청하고 있음

- Deadlock Detection

• 자원 타입 별로 인스턴스가 각각 하나만 존재하는 경우
  • 자원할당 그래프에서의 cycle이 곧 deadlock을 의미
• 자원 타입 별로 인스턴스가 각각 여러개 존재하는 경우
  • Banker's algorithm과 유사한 방법 활용

- Wait-for graph 알고리즘

• 자원 타입 별로 인스턴스가 각각 하나만 존재하는 경우 사용
• Wait-for graph
  • 자원 할당 그래프의 변형 (위 그림 중 우측에 해당)
  • 프로세스만으로 node 구성
  • Pj가 갖고 있는 자원을 Pk가 기다리는 경우 Pk -> Pj 로 표시
• Algorithm
  • Wait-for-graph에 사이클이 존재하는지를 주기적으로 조사함
  • 조사 시, 시간복잡도 O(n^2)

---

자원 타입 별로 인스턴스가 각각 여러개 존재하는 경우

- Deadlock Detection

• 프로세스는 P0 ~ P4 까지 5개
• 자원은 A, B, C 3가지로 각각 7개, 2개, 6개의 인스턴스를 가짐
• Allocation : 현재 할당중인 자원
• Request : 현재 실제로 요청한 자원
• Available : 총 자원에서 각 프로세스들의 할당된 자원을 빼고 남은 자원
  -> 현재 위 그림에서는 A, B, C 모두 프로세스들에 자원들을 할당한 상태라서 가용 자원이 없다.
• 현재는 P0 -> P2 -> P3 -> P1 -> P4 로 모두 작업 완료 가능하므로 Deadlock 상태가 아니다.
• 위 그림에서 P2가 자원 C 1개를 추가로 요청하고 있다면 P2는 작업완료를 못하고, 자원 반납 X
  -> P0를 제외한 P1, P3, P4 모두 작업 완료를 하지 못하게 되고 요청만 하는 상태가 됨
  -> Deadlock

---

- Recovery

• Process termination (프로세스 중지)
  • 1. 데드락에 연루된 모든 프로세스를 중지시킴
  • 2. 데드락 사이클이 제거될 때까지 한 턴에 한 프로세스씩 중지시켜 나감
• Resource Preemption (자원 선점)
  • 데드락에 연루된 프로세스의 자원을 뺏는 방법
  • 자원을 뺏을 프로세스를 찾는다 (비용을 최소화할)
  • safe state로 rollback 하여 process를 restart 한다.
  • Starvation 문제
    1. 동일한 프로세스가 계속해서 희생양으로 선정되는 경우
    2. 희생양마다 rollback 횟수도 고려해서 희생양을 선정한다.

---

＊Deadlock Ignorance

- Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는다.

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