데드락(Deadlock, 교착상태)의 개념과 해결 방법

데드락(DeadlocK)

시스템 자원에 대한 요구가 뒤엉켜서, 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다리며 무한 대기에 빠지는 상황

 

 

데드락 발생 조건

상호 배제

• 한 번에 하나의 프로세스만 자원을 사용할 수 있음
• 사용중인 자원을 다른 프로세스가 사용하려면 해제될때까지 기다려야 함

점유 대기

• 다른 프로세스에 할당된 자원을 점유하기위해 대기하는 프로세스가 존재해야함

비선점

• 이미 할당된 자원을 강제로 뺏을 수 없음

순환 대기

• 대기 프로세스의 집합이 순환 형태로 자원을 기다리고 있어야함

 

 

해결 방법

예방(Prevention)

• 데드락이 발생하지 않도록 예방

회피(Avoidance)

• 데드락 발생 가능성을 인정하면서 적절하게 회피

탐지 및 회복(Detection & Recovery)

• 데드락 발생을 허용하나 이를 탐지하여 회복

---

 

데드락 예방

• 데드락 발생 조건 4가지 중 한 조건이라도 발생하지 않도록 방지(부정)하여 발생 가능성을 차단하는 것
• 시스템의 처리량이나 효율성을 떨어트리는 단점
• 상호 배제 조건 방지
  • 한 번에 여러 프로세스가 공유자원을 사용할 수 있도록 허용
  • 자원 동기화 문제가 발생할 수 있음
• 점유 대기 조건 방지
  • 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할때까지 작업을 보류
  • 점유 대기 상황 자체가 발생하지 않도록 막아버림
• 비선점 조건 방지
  • 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 함
• 순환 대기 조건 방지
  • 순환형태가 아닌 일정한 방향으로 자원을 요구할 수 있도록 함

 

데드락 회피

• 예방보다 덜 제한적인 방법
• 자원을 할당한 후에도 시스템이 항상 안정 상태에 있도록 할당하는 방법
• 안정 상태(Safe state)
  • 프로세스 들이 요청하는 모든 자원을, 데드락을 일으키지 않고 모두에게 차례로 할당할 수 있는 상태
• 안전 순서(Safe sequence)
  • 데드락이 발생하지 않는 순서
• 불안정 상태
  • 안전 상태가 아닌 상황
  • 교착 상태(데드락)는 불안정 상태의 부분 집합

 

은행원 알고리즘(Banker's algorithm)

• 미리 결정된 모든 자원들의 최대 가능한 할당량을 바탕으로 시뮬레이션하여, Safe state에 들 수 있는지 검사
• 교착 상태 가능성을 미리 조사하는 것

 

e.g) 시스템이 총 12개의 자원을 가지고 있는 경우

프로세스	최대 자원 요청량	현재 할당중인 자원의 양	필요한 자원의 양
P0	10	5	5
P1	4	2	2
P2	9	2	7

12개의 자원 중 9개(5 + 2 + 2)의 자원을 현재 사용중이므로, 남은 사용가능한 자원은 3개

 

이때의 안전 순서(Safe sequence)는 <P1, P0, P2>

1. 남은 3개의 자원 중 2개를 P1 프로세스에게 할당, 남은 사용가능한 자원은 1개
2. P1이 작업을 마친 후 4개의 자원을 반납
3. 5개의 자원(P1이 반납한 4개의 자원 + 남아있던 사용가능한 자원 1개)을 P0에게 할당
4. P0이 작업을 마친후 10개의 자원을 반납
5. P2에게 7개의 자원을 할당, 남은 사용 가능한 자원은 3개
6. P2가 작업을 마친후  9개의 자원을 반납, 모든 프로세스가 작업을 마치고 사용 가능한 자원은 12개

 

만일 P2가 1개의 자원을 더 요청한다면?

1. P2에게 총 3개의 자원(기존 할당된 자원 2개 + 새롭게 할당한 자원 1개)을 할당, 현재 남은 사용가능한 자원은 2개
2. 2개의 자원을 P1에게 할당, 남은 사용가능한 자원은 0개
3. P1이 작업을 마친 후 4개의 자원을 반납
4. 사용 가능한 자원 4개를 P0에게 먼저 주든, P2에게 먼저 주든 작업을 마칠 수 없음
   👉 P0, P2는 자원을 할당받기를 기다리며 교착상태에 빠지게됨

 

P2 한개의 자원을 더 요청했을때,

운영체제가 자원할당량을 사전에 파악하여 P2에게 할당하지 않고, P1이 먼저 끝나게 한다면 데드락이 발생하지 않음

👉 자원할당량을 사전에 파악하고 데드락을 회피

 

은행원 알고리즘을 사용할 때에는 미리 최대 자원 요구량을 알고, 할당할 수 있는 자원 수가 일정해야한다는 제약 조건이 있음

 

 

 

데드락 탐지 및 회복

데드락 예방이나 회피를 사용하지 않고, 데드락이 발생할 경우 이를 탐지하고 회복

• 탐지
  • Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 탐색
  • 현재 시스템의 자원할당상태를 가지고 파악
• 회복
  • 순환 대기 에서 벗어나 데드락으로부터 회복
    • 단순 프로세스 중단
      • 교착 상태에 빠진 모든 프로세스를 중단
        1. 연산중이던 프로세스들이 모두 동시에 중단되어 결과가 폐기될 수 있음
      • 프로세스를 하나씩 중단시키며, 탐지 알고리즘으로 데드락을 탐지하고 회복
        1. 매번 탐지 알고리즘을 호출 및 수행한다는 부담이 존재
    • 자원 선점
      • 프로세스에 할당된 자원을 선점해서, 교착 상태를 해결할 때까지 그 자원을 다른 프로세스에게 할당

 

---

출처

• https://chanhuiseok.github.io/posts/cs-2/#-%EB%8D%B0%EB%93%9C%EB%9D%BD-%ED%9A%8C%ED%94%BCavoidance