OS - 7. Deadlocks

1. System Model

  

  교착 상태란 프로세스에게 한정된 자원이 분배됬을 때, 프로세스들이 자원의 부족으로 더이상 실행을 할 수 없어 끝낼 수 없으며, 자원이 프로세스에게 묶여 다른 작업을  시작하는 것도 불가능한 상태를 말한다. 한정된 자원에 대해 정상적으로 시스템이 운영되기 위해 프로세스는 요청, 사용, 방출 순서로만 자원을 사용할 수 있다.

 

 

2. Necessary Conditions

  

  교착상태는 다음 네 가지 조건이 동시에 성립될 때 발생한다.

▪ mutual exclustion(상호 배제) : 최소한 하나의 자원이 비공유 모드로 점유되어야 한다. 비공유 모드에서는 한 번에 한 프로세스만이 그 자원을 사용할 수 있다. 

▪ hold-and wait(점유하며 대기) : 프로세스는 최소한 하나의 자원을 점유한 채, 다른 프로세스가 점유하고 있는 자원을 얻기 위해 대기하고 있다.

▪ no preemption(비선점) : 자원들을 선점할 수 없어야 한다.

▪ circular wait(순환 대기) : 프로세스가 선점, 대기 관계가 원형 구도를 만든다.

 

 

3. Resourcr-Allocation Graph

  

   프로세스에서 자원 화살표는 요청 대기 화살표이고 자원에서 프로세스 화살표는 자원 할당에 대한 표시이다.

 

 

4. 교착상태 처리 방법

  

1. 시스템이 결코 교착상태가 되지 않도록 보장하기 위해 예방 또는 회피하는 프로토콜을 이용한다.

2. 교착상태가 되도록 허용한 후 회복 시킨다.

3. 문제를 무시하고 교착상태가 발생해도 발생 안한 척 한다.

 

세 번째 해결안은 UNIX와 Windows를 포함한 대부분의 운영체제가 사용하는 방법이다. 이경우 교착상태를 처리하는 프로그램을 작성하는 것은 응용 개발자의 몫이다.

 

 

5. Deadloc Prevention

  

  교착상태는 2. Necessary Conditions에서 말한 4가지 조건이 모두 성립되어야 발생한다. 따라서 적어도 하나의 조건이 성립되지 않도록 보장하는 방법으로 예방한다.

 

1. mutual exclustion(상호 배제) : 상호 배제 조건은 공유가 불가능한 자원에 대해서는 반드시 성립해야 한다. 반대로 공유 가능한 자원은 교착 상태와 관련이 없다. 결론적으로는 상호 배제는 프로세스의 진행에 꼭 필요하다.

 

2. hold-and wait(점유하며 대기) : 시스템에서 점유하며 대기 조건이 발생하지 않는 것을 보장하려면 프로세스가 자원을 요청할 때는 다른 자원들을 가지고 있지 않아야 한다.

첫번째 방법으로는 프로세스 실행 시 자원을 요청할 때 필요한 모든 자원을 한번에 요청하여 할당 받는 것이다.

두번째 방법으로는 프로세스가 자원을 가지고 있지 않을 때만 자원을 요청할 수 있도록 한다.

 

위 두 방법은 모두 자원을 처음부터 다시 요청해야 하는 단점과 한번에 많은 자원이 할당되었는데 사용을 안해 자원의 낭비가 발생할수도 있다. 또 여러개의 자원을 필요로 하는 프로세스가 있을 때 하나의 자원이 부족해서 기아상태에 빠질 수도 있다.

 

3. No Preemption(비선점) : 특정한 자원이 필요한 상태가 왔을 때 해당 자원을 할당 받을 수 없다면 가지고 있는 자원들을 선점 상태로 변경시킨다. 그리고 가지고 있던 자원들이 선점 되었다 사용이 끝나면 다시 해당 프로세스로 반환한다. 자원의 요청이 왔을 때 할당 받을 수 있는지 없는 지 확인을 할 때, 대기하고 있는 프로세스의 자원과 시스템의 남아 있는 자원을 체크하여 할당 여부를 정한다.

 

4. circular wait(순환대기) : 각 자원에 번호를 붙인다. 자원 요청시 작은 번호의 자원을 모두 요청후 큰 번호의 자원을 요청한다. 다른 방법으로는 특정 번호의 자원을 요청시 해당 번호보다 큰 번호의 자원들은 모두 반환한다. 이 두 방법으로 순한 대기 조건을 막을 수 있다.

 

 

 

6. Deadlock Avoidance

  

   교착 상태 예방은 요청 방법을 제약하며 교착상태를 예방한다. 그러나 이러한 방식으로 교착상태를  예방하면 장치의 이용률이 저하되고 시스템 처리율이 감소되는 단점이 발생한다.

  교착 상태 회피는 프로세스에게 자원이 어떻게 요청될지에 대한 추가 정보를 요구하고 이를 바탕으로 자원의 할당 여부를 결정한다.

 

 시스템은 모든 프로세스가 요청하는 최대 자원을 교착상태를 야기시키지 않고 차례로 모두 할당해 줄 수 있다면 안전하다고 말한다. 만약 모든 프로세스들이 무사히 마칠 수 있는 순서를 찾을 수 없다면 불안전한다고 한다.

 

 시스템의 상태가 안전하면 교착상태가 아니다. 불안전 상태라고 해도 항상 교착상태인것도 아니다. 시스템을 안전 상태로 유지한다면 불안전 상태와 교착 상태를 예방할 수 있다.

 

 위 방식은 안전 상태에서 안전 상태일 때만 자원을 할당하기 떄문에 프로세스의 요청 자원보다 시스템이 보유한 자원량이 많을 지라도 프로세스가 기다리는 경우가 발생한다. 이러한 이유로 자원의 이용률은 회피를 사용하지 않을 떄보다 낮아질 수 밖에 없다.

 

 

7. Deadlock Avoidance Algorithm

  

  1. Resource-Allocation Graph Algorithm

 

자원 -> 프로세스 : 할당

프로세스 -> 자원 : 요청

-----------------> : 예약

 프로세스는 실행되기 전에 프로세스의 모든 예약 간선들이 자원 할당 그래프에 그려진다. 이후 자원 요청이 있을 때 점선을 실선으로 바꿔도 싸이클이 발생하지 않는지 확인하고 실질적으로 실선으로 변경, 즉 자원을 할당한다.

 단 자원이 하나의 프로세스에게만 할당할 수 있을 때 사용할 수 있다.

 

 

 2. Banker's Algorithm

 

 

  자원 요청 -> 남아있는 자원 확인 -> 안전성 알고리즘 검사 -> 할당 or 대기로 진행된다. 자원이 여러 프로세스에게 할당 될 수 있을 때 사용된다.

 남아 있는 자원 확인할 시 요청이 필요 자원보다 작은 지 확인하고, 시스템에서 사용할 수 있는 자원이 요청 자원보다 많은 지 확인한다.

 안정성 알고리즘은 자원을 할당했다고 가정한 후 남아 있는 자원을 가지고 프로세스 모두를 실행 시킬 수 있는지 확인한다. 여기에서 모든 경우의 수를 생각해야하기 때문에 개의 연산이 필요하다. 여기서 m은 자원 종류의 수이며 n은 프로세스의 수이다.

 위 그림의 상태에서는 <p1, p3, p4, p0, p2> 순서로 수행될 수 있기 때문에 안전하다.

 

 

8. Deadlock Detection

  

  만약 시스템이 교착상태 예방이나 교착상태 방지 알고리즘을 사용하지 않는다면, 교착상태 여부를 확인하는 알고리즘과 교착상태로부터 회복하는 알고리즘이 반드시 지원해야한다.

 

1. 각 지원 타입이 한 개씩 있는 경우, 자원 할당 그래프의 변형인 대기 그래프를 이용해 deadlock을 확인한다.

 

 대기 그래프는 기존 자원 할당 그래프에서 자원 노드를 제거하여 만든 그래프이다. 여기에서 사이클이 완성되면 현재 상태가 데드락이라는 것을 알 수 있다.

 

2. 각 자원이 복수의 자원을 할당할 때는 7.2의 Banker's Algorithm에서 설명한 안전성 검사 알고리즘을 이용한다.

 

데드락을 찾는 알고리즘을 사용할 시기는 교착상태가 얼마나 자주 발생하는지, 그리고 교착상태가 일어나면 몇개의 프로세스가 연루되는가에 따라 결정된다. 교착상태가 발생하고 시간이 흐르면 교찾상태에 연루되는 프로세스 수도 증가하게 된다.

 

자원을 할당할 때마다 탐지 알고리즘을 사용하면 어디서 데드락이 발생했느지 알수있지만 이에 대한 오버해드가 너무 크다. 그래서 어느정도 시가을 정해 탐지 알고리즘을 사용한다.

 

 

9. Recovery from Deadlock

  

  1. 프로세스 종료 : 교착상태가 발생 시 프로세스를 종료함으로서 교착상태를 해결한다. 종료 방법에는 교착상태에 연루되어 있는 모든 프로세스를 종료하거나 교착상태가 없어질 때까지 하나씩 종료하는 방법이 있다. 후자일 경우 다음과 같은 요인을 고려해야한다.

• 프로세스의 우선순위

• 프로세스의 남은 시간과 수행된 시간

• 프로세스가 사용한 자원 타입과 수

• 프로세스가 종료까지 필요한 자원 수

• 종료되어야 할 프로세스 수

• 프로세스의 종류 - 독립적으로 돌아가는 것인지 아닌

 

 

 2. 자원 선점 : 다른 프로세스의 자원을 뺏어 자신의 일을 한다. 선점에 대한 고려 요인은 다음과 같다.

• 희생자 선택 : 어떤 프로세스를 희생할지 정해야 한다.

• 롤백 : 희생된 프로세스는 더 이상 실행 할 수 없으므로 재실행 될때 안전하게 실행될 수 있는 지점으로 되돌아 가야한다.

• 기아 상태 : 계속 된 희생으로 기아 상태가 빠지는 프로세스가 있을 수 있다.