[Operating System] Deadlock, 교착상태

https://namu.wiki/w/Deadlock

 

Deadlock, 교착상태

  - 다중 쓰레드 프로그래밍의 주요 난점 중 하나

  - Example)

    - 시스템 파일이나 다른 프로그램이 공유하는 파일을 건드리기 쉬운 프로그램 설치 과정

       - "프로그램을 설치할 때는 가능하면 다른 프로그램은 모두 꺼주세요"라는 말이 나오는 이유.

    - 차량/항공기 전장 운영체제의 경우, deadlock 발생 시 시스템이 뻗을 경우 대형참사 

    - 휴대폰 정지 → 인터넷을 통한 복구 → 휴대폰 인증 요구

 

발생 조건

  1. Mutual Exclusion

     - 자원 자체를 동시에 쓸 수 없는 경우 

  2. Hold and Wait

     - 자원을 붙잡은 상태에서 다른 자원을 기다리고 있는 경우

  3. No Preemption

     - 다른 프로세스가 자원을 뺏어올 방법이 없는 경우

  4. Circular Wait

     - 대기가 꼬리를 물고 사이클이 된 경우

 

대처 방법

  1. Prevention and Avoidance

     - Prevention

       - 데드락 자체가 일어나지 않도록 예방

     - Avoidance

       - deadlock이 발생할 것 같으면 회피

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

         - 자원 요청 → 안전 여부 체크 → 안전 상태이면 자원 할당, 아닌 경우 할당 거부

  2. Detection and Recovery

     - Detection

       - Resource Allocation Graph Algorithm을 통해 Deadlock 탐지 후 해결

       - 단, 자원 요청시마다 algorithm을 수행하면 overhead 발생

     - Recovery

       - deadlock 상태의 process를 종료하거나, 할당된 자원을 해제(Preemption)