[운영체제] Dealing with Deadlock & Deadlock Prevention

Deadlock을 다루는 방법과 이를 예방하는 방법을 알아보도록 하자

 

Dealing with Deadlock 

1. The Ostirch Approach: 고립 정책
   • 문제를 무시하고 머리를 모래 속에 파묻는 방식
   • 즉 실제로 문제를 해결하지 않고 무시하는 것이며 교착 상태가 발생하더라도 대처하지 않음
2. Deadlock prevention: 교착 상태 방지
   • 교착 상태가 발생할 수 있는 네 가지 조건 중 하나를 제거하여 교착 상태를 방지하는 방법임. 예를 들어 보유 및 대기 조건을 방지하기 위해 프로세스가 모든 필요한 리소스를 한 번에 요청하도록 요구할 수 있음
3. Deadlock detection algorithms: 교착 상태 검출 알고리즘
   • 교착 상태가 발생했는지 감지하는 알고리즘 사용
   • 주기적으로 시스템을 검사하여 교착 상태를 탐지하고 교착 상태에 빠진 프로세스와 리소스를 식별함
4. Deadlock recovery algorithms: 교착 상태 복구 알고리즘
   • 교착 상태를 해결하기 위한 알고리즘 사용
   • 교착 상태에 있는 프로세스와 리소스를 해제하거나 중지시켜 교착 상태를 해제 함.
5. Deadlock Avoidance algorithms :교착 상태 회피 알고리즘
   • 현재 사용 가능한 리소스 각 스레드에 할당된 리소스, 그리고 가능한 미래 요청 등을 고려하여 교착 상태가 발생하지 않도록 요청을 충족시켜는 알고리즘임.

현재 운영체제는 첫 번째 방법을 사용하여 데드락이 발생되어도 해결하지 않고 무시한다.

이유는 다음과 같다.

1. 데드락 탐지 및 회복 비용때문이다. 데드락을 탐지하고 해결하는 방법은 상당히 복잡하고 비용이 많이 든다. 데드락 탐지 알고리즘을 항상 실행하면 시스템 자원을 많이 소모하게 되어 시스템 성능에 부정적인 영향이 감.
2. 데드락이 자주 발생하지 않기 때문에 이를 처리하기 위해 복잡한 메커니즘을 항상 사용하는 것은 비효율적임

등등 많은 이유들이 있다.

 

Deadlock prevention

데드락 상태의 필요 충분 조건 중 하나가 성립되지 않도록 보장하는 것을 말함

 

Mutual Exclusion

1. 상호 배제
   • 한 프로세스가 리소스를 보유하고 있는경우, 다른 프로세스들이 해당 리소스를 요청할 때까지 대기해야 함. 이 조건을 피하기 위해서는 상호 배제가 필요 없는 리소스를 사용하거나 고유 가능한 리소스를 사용하는 것이 좋음
2. 상호 배제의 어려움
   • 일부 리소스는 상호 배제를 피하기 어려움. 예를 들어 프린터 및 기타 입출력 장치와 같은 비공유 가능한 리소스는 여러 프로세스가 동시에 사용할 수 없음
3. 상호 배제의 회피
   • 많은 리소스는 공유 가능, 에를 들어 읽기 전용 파일은 여러 프로세스가 동시에 접근할 수 있음. 또한 프린터와 같은 공유 가능한 리소스의 경우 상호 배제를 회피함으로써 교착상태를 방지할 수 잇음. 이를 위해 스풀링과 같은 기술을 사용하여 프로세스가 실제 프린터에 대기하지 않고도 리소스를 사용할 수 있도록 함.

Circular wait

⇒ 모든 리소스에 대해 전체 순서를 부과하고 프로세스가 그 순서대로 리소스를 요청하도록 요구함.

1. 전체 순서 부과
   • 대기 순서로 사용되는 모든 리소스에 대해 전체적인 순서를 정의
   • 예를 들어 디스크, 프린터, CD-ROM과 같은 리소스들의 순서를 정의할 수 있음
2. 리소스 요청 순서
   • 각 프로세스는 정의된 순서에 따라 리소스를 요청해야 함.
   • 예를 들어 프로세스 A가 디스크를 요청한 후에 프린터를 요청해야 하며, 프로세스 B도 비슷하게 요청해야 함. 이러한 방식으로 프로세스가 다른 프로세스가 보유한 리소스를 요청하는 순서를 결정하여 circular wait를 방지함.
3. 논리적 순서 설정
   • 리소스의 순서는 일반적으로 리소스가 획득되는 논리적인 순서와 일치해야 함.
4. 추가적인 대응책
   • 프로세스가 모든 리소스를 해제하고 다시 요청 시퀀스를 시작하도록 허용
   • 프로세스가 각 리소스의 전체 수를 단일 요청으로 요청하도록 강제할 수 있음

No preemption

⇒ 사전 방지 조건을 극복하기 위해 선점을 허용

1. 선점 허용
   • 프로세스 A가 사용할 수 없는 리소스를 요청할 때 해당 리소스를 보유하고 있는 프로세스 B가 추가 리소스를 기다리고 있는 경우 프로세스 B가 보유한 리소스를 프로세스 A에게 선점할 수 있음. 이렇게 함으로써 프로세스 A가 기다리지 않고 해당 리소스를 획득할 수 있게 됨
   • 그러나 프로세스 A가 추가 리소스를 기다리지 않는 경우, 프로세스 A는 대기해야 함. 이 때 프로세스 A는 대기하는 동안 현재 보유한 일부 리소스가 선점될 수 있음. 그리고 새로운 리소스와 함께 선점된 리소스를 획득할 수 있는 경우에만 깨어날 수 있음
2. 리소스 요청 처리
   • 프로세스가 요청한 리소스가 할당되지 않을 경우, 해당 프로세스가 보유한 모든 리소스가 선점될 수 있음.
3. 선점 가능한 리소스
   • 이러한 방식은 상태를 저장하고 복원할 있는 리소스에만 적용

⇒ 프로세스가 리소스를 강제로 반환하고 다른 프로세스가 해당 리소스를 사용할 수 있도록 허용하여 방지할 수 있음

 

 

Hold and wait

⇒ 프로세스가 리소스를 보유하고 있을 때 추가 리소스를 요청하지 않도록 보장하는 것

1. 모든 리소스 한 번에 요청
2. 미리 요청하는 어려움
   • 모든 필요한 리소스를 미리 알기 어려울 수 있음
3. 리소스 점유와 낭비
   • 모든 리소스를 한 번에 요청하는 것은 리소스의 낭비를 초래할 수 있음
4. 기아 가능성
   • 리소스를 한꺼번에 요청하는 방법은 일부 프로세스가 리소스를 영구적으로 보유할 수 있고,이로 인해 다른 프로세스가 필요한 리소스를 얻지 못하고 데드락에 빠질 수 있음