[OS] 데드락의 탐지와 해결방법

데드락의 정의

• 두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해 다음 처리를 하지 못하는 상태
• 무한히 다음 자원을 기다리게 되는 상태를 말한다

식사하는 철학자

• 다익스트라가 운영체제의 교착상태(Deadlock)을 설명하기 위해 낸 문제
• 5명의 철학자가 원탁에 앉아서 식사를 한다
  • 왼쪽 포크가 사용가능할때 까지 대기한다. 사용가능하다면 집어든다.
  • 오른쪽 포크가 사용가능할때 까지 대기한다. 사용가능하다면 집어든다
  • 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.
  • 오른쪽 포크를 내려놓는다.
  • 왼쪽 포크를 내려놓는다.
  • 다시 1번으로 돌아간다
• 모든 철학자가 왼쪽의 포크를 집어든 상태에서 오른쪽 포크가 사용가능할때 까지 무한히 대기하는 상황이 연출 된다.

교착상태의 발생 조건

• 상호배제
  • 한 프로세스가 자원을 점유하고 있을때 다른 프로세스가 해당 자원을 점유하지 못하는 것.
• 점유대기
  • 프로세스가 자원을 점유하고 있는 상태에서 다른 자원을 기다린다.
• 비선점
  • 프로세스는 해당 자원을 사용하는 프로세스가 자원을 자발적으로 반환할 때까지 기다린다.
• 순환대기
  • A프로세스가 필요한 자원을 B프로세스가 점유하고있고, B프로세스가 필요한 자원을 A프로세스가 점유하고 잇는 상황

교착 상태의 해결 방법

예방

• 교착 상태 발생조건중 하나를 제거하여 교착상태를 예방할 수 있다.
  • 상호 배제 방지
    • 여러 프로세스가 동시에 자원을 점유하게 되면, 동시성 문제가 발생할 수 있다.
  • 점유 대기 방지
    • 자원을 요구할때 자원을 반납하고 요구한 자원을 사용하기 위해 기다리게 하면 자원에 대한 내용을 저장하고 복원하기 위한 비용이 발생하기 때문에 비효율적이다. 또한 여러자원에 일관성을 보장해야 하는 작업의 경우 여러 자원에 동시에 접근하여 업데이트 해야 하므로, 이방법을 적용할 수 없다.
  • 비선점 방지
    • 만약 선점을 가능하게 할 경우 기아상태가 발생할 수 있으며, 작업의 진행상태를 저장하지 않는 자원의 경우 적용이 어렵다.
  • 순환 대기 방지
    • 자원에 우선순위를 매겨 순차적으로 획득하도록 한다면, 추가로 필요한 자원들이 어떠한 프로세스에게도 점유 되어 있지 않음을 보장할 수 있지만, 우선순위를 매기는데 비용이 크다.
• 시스템 처리량이나 자원 사용의 효율성을 떨어트릴 수 있다.

회피

• 데드락 발생 가능성을 지속적으로 검사해서 데드락을 회피하는 방식.
• 은행원 알고리즘
  • Safe State(안전 상태) : 시스템이 교착상태를 일으키지 않으며, 각 프로세스가 요구한 최대 요구량 만큼 자원을 할당할 수 있는 상태. 안전순서열 존재
  • Unsafe State(불안전 상태) : 안전순서열이 존재하지 않는 상태, 교착상태의 필요조건으로 무조건 교착상태가 발생하는 것은 아니다.
  • 요구사항
    • Max : 각 고객들이 최대로 요구할 돈
    • Allocated : 각 고객들이 빌리고 있는 돈
    • Available : 빌려 줄 수 있는 돈
• 은행원 알고리즘은 해당 프로세스가 시작할때 프로세스가 가져야할 자원의 최대 개수를 미리 알아야 하기 때문에 실제 돌아가는 프로그램에 적용하기 어렵다.

은행이 가지고있는 자원 : 12

최대 요구량 현재 할당량

A	10	5
B	5	2
C	9	2

안전 순서열 : B → A → C

은행은 현재 9달러를 할당하고 있으므로 가용 달러는 3달러이다.

B : 3달러를 B에게 빌려주면, B는 채무를 해결하고 은행은 5달러를 돌려받아 가용 달러는 5달러가 된다.

A : 5달러를 A에게 빌려주면, A는 채무를 해결하고 은행은 10달러를 돌려받아 가용달러는 10달러가 된다.

C : 7달러를 C에게 빌려주면, C는 채무를 해결하고 모든 대출자가 채무를 해결하게 된다.

탐지

• 각 유형의 자원이 한개씩 있는 경우
  • 대기 그래프
    • 자원 할당 그래프에서 자원을 제거한 후 간선들을 결합하여 사이클이 발생하면 교착상태로 판단한다
• 각 유형의 자원이 여러개 있는 경우
  • 대기 그래프 는 사용할 수 없으며, 은행원 알고리즘과 같이 상태정보를 가지는 자료구조를 사용해야 한다.
• 탐지 알고리즘의 실행 시점
  • 교착 상태가 자주 발생할수록 자주 실행시켜야 한다.
  • 자원요청할 때마다 탐지 알고리즘을 호출하면 성능저하가 발생한다.
  • 지정된 시간간격으로 돌리거나 CPU사용률을 기준으로 돌린다.

회복

• 교착상태가 발생한 이후 문제를 해결하는 방법
  • 교착상태의 프로세스를 종료한다. (모두 종료하거나, 하나씩 종료해가며 해결)
  • 교착상태의 프로세스를 선점하여 다른 프로세스에 할당한다.
    • 희생자 선택 : 최소의 피해를 줄 수 있는 프로세스를 선택해야 한다.
    • 롤백 : 선점당한 프로세스를 문제없는 이전 상태로 롤백해야 한다.
    • 기아상태 : 한 프로세스가 계속 자원을 선점하지 못하도록 해야한다.

무시

• 교착상태해결을 위해서도 문맥교환으로 인한 오버헤드가 발생한다. 교착 상태로 인한 오버헤드보다 교착상태 해결을 위한 오버헤드가 큰 경우 무시한다.