[운영 체제] Deadlock

• Process1은 Resource1을 사용 중
• Process2는 Resource2를 사용 중
• Process1은 Resource2를 요청하고 Process2는 Resource1을 요청
• 서로 원하는 자원이 상대방에게 할당되어 있기 때문에 무한정 wait 상태에 들어감 → Deadlock 상태
• 데드락이란 교착상태라고도 불리며 상호 배제에 의해 나타나는 문제점이다.
• 2개 이상의 프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우

⬛ Starvation vs deadlock

출처 : High Performance, Heterogeneous Parallel Computing Lab, KOREATECH

• Starvation은 Ready 상태에서 발생하고 운이 없어 오래 기다릴 뿐 언젠가는 자원을 할당받을 확률이 있는 상태
• deadlock은 Asleep 상태에서 발생하고 오래 기다려도 절때 발생할 확률이 없는 상태

⬛ Deadlock 발생 필요 조건 

◼ 상호 배제(Mutual exclusion)

• 프로세스는 동시에 사용할 수 없는 자원을 사용해야한다. 즉, 한번에 한 프로세스만 사용할 수 있는 자원이여야한다.

◼ 점유 대기(Hold and wait)

• 최소 하나의 자원을 hold하고 있으면서 다른 자원을 기다리는 상태여야한다.

◼ 비선점(Non-preemptible)

• 하나의 프로세스에 할당된 자원을 다른 프로세스가 중간에 강제로 빼앗을 수 없어야한다.

◼ 순환 대기(Circular wait)

• 프로세스 집합{P0, P1, P2,…Pn}에서 P0은 P1에 할당된 자원을 기다리고, P1은 P2에 할당된 자원을 기다리고, ………Pn-1은 Pn에 할당된 자원을 기다리고, Pn은 P0에 할당된 자원을 기다리는 순환 형태로 자원을 기다리고 있어야 한다.

⬛ Deadlock 해결 방법 

◼ 예방(Deadlock prevention)

• 4개의 Deadlock 발생 필요 조건 중 하나를 제거하며 해결
• 필요 조건이기 때문에 하나를 제거하면 절대 Deadlock이 발생하지 않음

 

1. 상호배제 부정 : 모든 자원을 동시에 사용할 수 있게 한다. → 비현실적
2. 점유대기 부정 : 프로세스에게 필요한 자원을 한번에 모두 할당해준다. → 심각한 자원 낭비
3. 비선점 부정 : 프로세스가 사용하고 있는 자원을 강제로 빼앗을 수 있게 한다. → 자원 낭비 & 비현실적
4. 순환대기 부정 : 자원에 순서를 부여하고 프로세스는 순서가 증가하는 방향으로만 자원을 요청할 수 있게 한다. → 자원 낭비

 

• 자원 낭비가 심하고 비현실적인 방법

◼ 회피(Deadlock Avoidance)

• 자원 할당 상태를 계속 검사하여 Deadlock의 가능성을 미리 판단한 후 Deadlock을 원천적으로 막는 방법
• 시스템을 항상 Safe state로 유지하는 방법이다. Safe state란 시스템이 모든 프로세스에게 Deadlock을 피할 수 있음을 보장하는 Safe sequence로 자원을 배분할 수 있는 상태를 말한다.

 

• 은행원 알고리즘(Banker’s Algorithm)
  • 자원을 할당하기 전에 미리 모든 자원들의 최대 가능한 할당량을 가지고 시뮬레이션해보며 Safe state가 유지될 수 있는 지 검사하는 알고리즘
  • 가정
    1. 프로세스의 수가 고정되어야 한다.
    2. 할당할 수 있는 자원의 수가 고정되어야 한다.
    3. 미리 프로세스가 요구하는 자원 및 최대 수량을 알고있어야 한다.
    4. 프로세스는 자원을 사용한 후 반드시 반납
  • 예시 ) 한 종류의 자원이 10개 있는 상태

• 현재 남은 자원은 (10-1-5-2) = 2개이고 P1→P3→P2순서로 자원을 할당해주면 Safe state를 유지할 수 있다. Safe state를 유지할 수 있는 순서(Safe sequence)가 존재
• 미리 최대 자원 요구량을 알아야하고, 할당할 수 있는 자원의 수가 일정해야 한다. → not practical

◼ 탐지(Deadlock Detection)

• Resource Allocation Graph(RAG)를 통해 데드락이 발생했는 지 여부를 탐지
• 자원을 요청할 때마다 탐지 알고리즘을 실행하여 데드락 발생 여부 판단 → 오버헤드

◼ 회복 (Deadlock Recovery)

• Deadlock를 검출하면 회복하는 과정이 필요
• Deadlock Recovery Methods
  1. Process termination
     • 교착 상태의 프로세스를 모두 종료시키거나 교착 상태가 제거될 때까지 하나씩 종료시킴
  2. Resource preemption
     • 교착 상태를 해결할 수 있는 자원을 선점하여 다른 프로세스에게 할당해준다
     • 자원을 빼앗긴 프로세스는 종료시킨다.
     • 교착 상태가 아닌 프로세스가 종료될 수도 있다.

 

 

 

 

참고자료. (90) [OS] Lecture 1. Computer System Overview / 운영체제 강의 - YouTube