OS - Deadlock

Deadlock

자원 관리 문제로 둘 이상의 프로세스가 요구하는 자원을 얻을 수 없는 상태(교착 상태)

 

ex. 식사하는 철학자 문제

1. 일정 시간 생각을 한다.
2. 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
3. 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
4. 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.
5. 오른쪽 포크를 내려놓는다.
6. 왼쪽 포크를 내려놓는다.
7. 다시 1번으로 돌아간다.

이 때, 모든 철학자가 왼쪽 포크를 들게 되면, 모든 철학자들은 오른쪽 포크가 사용 가능할 때까지 무기한 대기하게 된다. (출처 : 나무위키)

 

Deadlock 발생 조건

- 다음 4가지 조건을 모두 만족하지 않으면 deadlock이 발생하지 않는다.

• 상호 배제(Mutual Exclusion) : 자원은 하나의 프로세스만 점유 가능하다.
• 점유 대기(Hold and Wait) : 프로세스가 어떤 자원을 점유하면서, 다른 자원을 요구하는 상태여야 한다.
• 비선점(No Preemption) : 자원을 가지고 있는 프로세스가 작업을 완료하기 전에 자원 점유는 해제되지 않는다.
• 순환 대기(Circular Wait) : 프로세스들의 자원 점유 & 자원 요구가 서로 맞물려 cycle을 구성해야한다.

 

 

Deadlock 해결 방법

• 데드락 예방(Prevention) : 데드락 발생이 불가능하게 설계한다.(deadlock 발생 조건을 부정하는 방식) → 대형 프로그램에는 힘들것.
• 데드락 회피(Avoidance) : 운영체제가 데드락이 발생할 가능성이 있는지 미리 검사하고 할당하는 방법.(은행원 알고리즘) → 너무 비용이 크다...
• 데드락 탐지 및 회복 : 데드락이 발생하게 두고, 발생하면 해결한다.
  • 주기적인 교착 상태 검사(자원 할당 그래프)
  • 데드록 탐지시, 우선순위에 따라 자원을 선점할 수 있게 해주거나, 프로세스 자체를 하나씩 중지시킴

자원 할당 그래프 예시

 

 

 

 

 

 

 

 

 

 

 

출처

https://jwprogramming.tistory.com/12

https://jwprogramming.tistory.com/12