교착 상태 해결 방법

1. 시스템에 절대 교착 상태가 발생하지 않도록 보장 : 교착 상태 예방, 회피

1.1) 교착 상태 예방 : 교착 상태 필수 조건 4가지 중 하나라도 성립하지 않게끔 보장하여 발생을 예방

- 상호 배제 : 공유 가능한 자원은 배타적인 접근을 요구하지 않으므로 교착 상태가 발생하지 않음
  이 조건은 자원의 비공유를 전제로 하는데, 어떤 자원은 본질적으로 공유가 불가능하므로 상호 배제를 거부하여 
  예방하는 것은 불가능하다. ex) 워드랑 한글에서 한 줄씩 프린터로 출력 불가

- 점유와 대기 : 프로세스가 자원을 요청할 때, 다른 어떤 자원도 갖고 있지 않도록 보장

  실행 전에 필요한 모든 자원을 할당받도록 하거나 어떤 자원도 갖고 있지 않을 때만 요청 가능하도록 허용하여 구현
  근데 낮은 자원 이용률과 기아 문제가 발생할 수 있다.

- 비선점 : 어떤 자원을 점유하고 있는 프로세스가 당장 얻을 수 없는 다른 자원을 요청하면, 현재 점유하고 있는 자원들을 선점시키고 선점된 자원들은 대기 중인 프로세스를 위해 resource list에 추가함으로써 구현.(탭 어떻게 하는 거야ㅜ)

근데 프로세스가 예전에 점유했던 자원과 새롭게 필요한 자원을 다시 확보해야 재시작이 가능하다는 단점이 있다.

- 순환 대기 : 시스템 자원의 정의된 이용 순서에 따라 요청하도록 하여 구현

 

1.2) 교착 상태 회피 : 교착 상태 필수 조건 최소 1개가 발생하지 않도록 제한

- 장치 이용율 저하와 시스템 처리율이 감소되는 단점이 있고, 사전에 프로세스의 리퀘스트 정보를 활용하여 최대 요청 정보를 미리 파악하여야 한다. Deadlock이 발생하지 않도록 delay/allocate 해서 구현

- 각 프로세스가 필요한 각 형태의 자원마다 최대 요구 수를 선언해놓고 시스템이 순환-대기 조건이 되지 않도록 자원 할당 상태를 검사한다.

- 안전상태, 안전 순서라는 것을 정의해놓는데, 안전 상태는 어떤 순서로든 프로세스들이 요청하는 모든 자원을 교착상태를 야기시키지 않고 차례로 모두 할당해줄 수 있는 상태를 의미하고, 안전 순서는 해당 상태에서의 프로세스들의 순서를 이야기하는 것으로, ㅍ2이 필요한 자원을 즉시 없을 수 없으면 ㅍ2는 모든 ㅍ1이 마칠 때까지 대기하다가 ㅍ1이 끝나면 ㅍ2가 필요한 모든 자원을 얻게 되고, ㅍ2가 끝나면 ㅍ3이 필요한 모든 자원을 얻게 되는 형태

=> 안전 순서를 찾을 수 있으면 시스템은 안전한 상태이다. => 교착 상태 발생 X

- 회피 알고리즘에는 자원 할당 그래프 알고리즘, 은행원 알고리즘이 있다.

 

 

2. 교착 상태는 허용하고, 추후 회복 : 교착 상태 탐지 알고리즘, 교착상태로부터의 회복 알고리즘

2.1) 교착 상태 탐지 알고리즘(대부분의 프로그램에서 사용)

- 문제가 생기면 해결하는 시스템으로, 교착상태가 날 때까지 기다렸다가 해결한다.

- 시스템이 교착 상태 예방이나 교착 상태 회피 알고리즘을 사용하지 않을 경우 교착 상태 발생 가능

- 예방은 하나를 깨기 위해서 들어가는 투자가 크고, 회피는 하나 할 때마다 체크해야하니까 부하가 큰데(이건 처음부터 끝까지 체크) 이건 가만히 있다가 간헐적으로 체크하니까(이건 현재 문제가 있는지만 체크) 효율적이어서 많은 프로그램에서 사용하는 방법이다.

- 교착 상태가 발생했는지 결정하기 위해 시스템의 상태를 검사(대기 그래프, 은행원 알고리즘 같은 거)해서 교착 상태로부터 회복하는 알고리즘으로 해결한다.

 

2.2) 교착 상태로부터의 회복 알고리즘

- 순환 대기를 탈피하기 위해 한 개 이상의 프로세스를 중지시키고, 교착 상태의 프로세스들로부터 자원을 선점하여 교착상태를 해결한다.

- 프로세스 종료 방식은 교착 상태 프로세스들을 모두 중지하는 것과 교착 상태가 해결될 때까지 한 프로세스씩 부분 종료하여 중지하는 두 가지 방법이 있는데, 첫 번째는 비용이 많이 들고 두 번째는 매번 탐지 알고리즘을 호출하여야 해서 부담이 많이 된다.

- 자원을 선점하는 방식은 관리자나 시스템이 수행하는데, 비용을 최소화하기 위해 '희생자의 선택', 자원을 선점 당한 프로세스가 다시 정상적으로 수행할 수 있도록 하기 위해 교착 상태에서 벗어날 정도로만 '롤백', '기아' 문제를 고려한 viction으로 선정되는 횟수 제한 등을 고려해야 한다.

 

3. 교착 상태를 무시하고 발생하지 않는다고 가정(대부분의 운영체제에서 적용)
Deadlock 발생 -> 시스템 or Process 중단 -> Restart