[OS] Deadlock

East Silver·2021년 12월 30일
0

Deadlock 교착 상태

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

데드락 발생의 4가지 조건

1. Mutual exclusion (상호 배제)

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

2. No preemption (비선점)

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

3. Hold and wait (보유 대기)

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

4. Circular wait (점유 대기)

자원을 기다리는 프로세스 간에 사이클이 형성되어야 함.

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

데드락인지 판단하는 방법

  • 그래프에 cycle이 없으면 데드락이 아니다.
  • 그래프에 cycle이 있으면
    • 자원 당 하나의 인스턴스만 있는 경우에는 데드락이다. (왼쪽 그래프)
    • 자원 당 여러 인스턴스가 존재하는 경우에는 데드락일 수도 있고 아닐 수도 있다.

데드락의 처리 방법

Deadlock Prevention (데드락 예방)

자원 할당 시 데드락의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
1. Mutual Exclusion (상호 배제)
공유해서는 안되는 자원의 경우 반드시 성립해야 함.

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

  2. No Preemption (비선점)

  • 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
  • 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작됨
  • 상태를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용 (CPU, memory)
    - 쉽게 save하고 restore할 수 없는 것들은 사용하기 어렵다.
  1. Circular Wait (순환 대기)
    모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당
    ex) 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj를 할당 받기 위해서는 우선 Ri를 release해야 함

하지만,
⇒ Utilization(이용률) 저하, throughput(성능) 감소, starvation 문제

Deadlock Avoidance (데드락 회피)

  • 자원 요청에 대한 부가적인 정보(최대로 요청할 자원의 갯수)를 이용해서 데드락의 가능성이 없는 경우에만 자원을 할당
  • 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
safe state (안전 상태): 시스템 내의 프로세스들에 대한 safe sequence(안전 순서열)가 존재하는 상태

시스템이 안전 상태에 있으면 데드락이 아니며, 불안전 상태에 있으면 데드락의 가능성이 있다.

  • 데드락 회피는 시스템이 불안전 상태에 들어가지 않는 것을 보장한다.
  • 2가지 경우의 Avoidance 알고리즘
    1. 자원 유형 당 1개의 인스턴스만 존재 -> 자원 할당 그래프 알고리즘
    2. 자원 유형 당 여러 개의 인스턴스 존재 -> 은행원 알고리즘(추가 정리 필요함!!)

Deadlock Detection and recovery (데드락 탐지 및 회복)

데드락 발생은 허용하되, 그에 대한 탐지 루틴을 두어 데드락 발견시 회복
1. 데드락 탐지

  • Wait-for 그래프
  1. 데드락 회복
  • 프로세스 종료
    • 모든 데드락 상태인 프로세스를 강제 종료
    • 데드락 사이클이 없어질 때까지 하나씩 프로세스를 강제 종료
  • 자원 선점
    • 비용을 최소화할 희생 프로세스를 선정
    • 안전 상태로 롤백하여 프로세스를 재시작
    • Starvation 문제
      - 동일한 프로세스가 계속 희생 프로세스로 선정되는 경우
      - 비용 요소에 롤백 횟수도 같이 고려해야 함 (단순히 비용만 최소화하면 안 된다는 뜻)

Deadlock Ignorance (데드락 무시)

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

  • 데드락이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음
    • 데드락이 매우 드물게 발생하므로 데드락에 대한 조치 자체가 더 큰 오버헤드일 수 있음
    • 만약, 시스템에 데드락이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 프로세스를 죽이는 등의 방법으로 대처함
    • UNIX, Windows 등 대부분의 OS에서 채택하였음
profile
IOS programmer가 되고 싶다

0개의 댓글