[운영체제/OS] Deadlock Detection

Deadlock Detection 교착상태 탐지

Detection Algorithm

시스템이 deadlock state인지 detect하는 알고리즘 

1. Work = Available

Allocation[i]가 0이 아니면, Finish[i] = false. (안전한지 detection 검사)

그 외는 Finish[i] = true

 

2. (a) Finish[i] == false

   (b) Request[i] <= Work

 

3. Work = Work + Allocation[i]

Finish[i] = true

2단계로 이동

 

4. Finish[i] == false라면, 어떤 시스템들은 deadlock state에 있다.

 

O(mn^2)의 시간 복잡도 가지는 알고리즘

 

Detection Algorithm 예시

 

 

둘다 멈춰있는 상태

deadlock: 프로세스가 아무 작업도 안함

livelock: 의미없는 작업만 반복함.(CPU util로 판단하기 어렵다.)

 

detection algorithm 호출하기 좋은 시점

-자원 요청시마다 호출하면 오버헤드가 너무 크다.

-어떤 프로세스가 자원을 요청했는데 그것이 즉시 할당되지 못하는 시점: dead lock관련 프로세스와 누가 유발했는지 정보를 알 수 있다.

-지정된 시간 간격으로 호출한다. 

 

deadlock restore

-운영자에 의한 해결(수작업)->오늘날은 사실상 불가능..

-process termination(프로세스 종료):

  모두 중지: 구현은 쉽지만 오버헤드와 비용이 크다.

  제거될 때까지 하나씩 중지: n^2의 복잡도

-resource preemption(자원 선점): deadlock으로 인해 멈춘 프로세스들로부터 자원을 뺏어옴.

  자원 선점의 3가지 요소: 

    1. 희생자 선택(selection of a victim): 비용 최소화 고려

    2. rollback: 프로세스를 안전한 상태까지 되돌리고 그 상태로부터 재시작(뺏어온 자원을 다시 돌림)

    3. starvation: 같은 프로세스가 반복해서 희생자로 선택될 수 있다. 그래서 해결책으로 rollback 횟수 고려, 횟수에 가중치 두기 등 

 

 

 

설계자가 종료해야 하는 프로세스는 다음을 고려해야한다.

-프로세스 우선순위

-프로세스 (시간따라) 얼마나 계산되고 종료까지 남았는지.

-프로세스가 사용한 자원

-프로세스가 완료까지 필요한 자원

-얼마나 많은 프로세스들이 종료되어야하는지

-프로세스가 대화형인지 배치(일괄)형인지