[Computer Science] 교착상태(deadlock), 발생 조건과 방지 방법

학습목표

 · 교착상태(deadlock)란?

 · 교착상태의 조건

 · 교착상태 방지 방법

   - 교착 상태 예방

   - 교착 상태 회피

---

교착상태(deadlock)란?

· 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태

· 다중프로그래밍(multiprogramming) 환경에서 흔히 발생하는 문제

   - 여러 프로그램을 단일 프로세서에서 동시에 실행하는 것

 

교착상태의 조건

· 교착상태가 일어나려면 네 가지 필요조건을 충족해야 함

   1. 상호배제(Multual exclusion): 프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구

   2. 점유대기(Hold and wait): 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다림 

   3. 비선점(No preemption): 프로세스가 어떤 자원의 사용을 끝날 때까지 그 자원을 뺏을 수 없음 

   4. 순환대기(Circular wait): 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있음

https://snoop-study.tistory.com/118

 

· 위 조건 중 한 가지라도 만족하지 않으면 교착 상태 발생 x

· 순환대기 조건은 점유대기 조건과 비선점 조건을 만족해야 성립하는 조건 (네 가지 조건이 서로 완전히 독립적인 것은 x)

 

교착상태 방지 방법

교착 상태 예방

1. 상호배제 조건 제거

   - 교창 상태는 두 개 이상의 프로세스가 공유가능한 자원을 사용할 때 발생하므로 공유 불가능 하도록 변경

2. 점유대기 조건 제거

   - 한 프로세스에 수행되지 전에 모든 자원을 할당시키고 나서 점유하지 않을 때에는 다른 프로세스가 자원을 요구하도록 하는 방법

   - 문제점: 자원 과다 사용으로 효율성↓, 프로세스가 요구하는 자원을 파악하는 비용, 자원에 대한 내용을 저장 및 복원하는 비용,

      기아 상태, 무한 대기

3. 비선점 조건 제거

   - 비선점 프로세스에 대해 선점 가능한 프로토콜 만들기 

4. 순환대기 조건 제거

   - 자원 유형에 따라 순서 매기기

 

· 위 해결 방법들의 문제점: 자원 사용의 효율성이 떨어지고, 비용이 많이 듦

 

교착 상태 회피

· 자원이 어떻게 요청될지에 대한 추가정보를 제공하도록 요구

· 시스템에 순환대기가 발생하지 않도록 자원 할당 상태를 검사

· 교착 상태 회피를 피하기 위한 알고리즘

   1. 자원 할당 그래프 알고리즘(Resource Allocation Graph Algorithm)

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

 

 

출처

https://ko.wikipedia.org/wiki/교착_상태

https://han.gl/52kIq