Deadlock

 

이 포스트는 서울대학교의 '운영체제의 기초' 강의를 개인 학습용으로 작성한 포스트입니다.

 

 

 

Deadlock

여러 프로세스가 일어나지 않는 일을 하염없이 기다리는 상태

자원을 공유하는 프로세스들이 서로가 원하는 자원을 분점하고 있기 때문에 어느 프로세스도 진행하지 못하는 상태

 

Livelock : 자원을 계속 사용하지만 아무 의미있는 일을 하지 못하는 상황

     -> 해결 : Interrupt Coalescing (여러 입력을 모아서 한번에 인터럽트 처리)

Indefinite Postponement : 절대 일어날 수 없는 이벤트를 기다리는 상황

 

 

Resource Allocation Graph

자원 -> 프로세스 : 할당되었다

프로세스 -> 자원 : 해당 자원을 원한다

Binary semaphore에서 cycle이 존재하는 경우 반드시 deadlock 발생

 

 

Deadlock 조건

Mutual exclusion

No preemption

Hold and wait

Circular wait

 

 

Deadlock Prevention

No mutual exclusion : exclusive access 허용 X, 사실상 불가

Preemption : 모두 강제할 수 없음, 사실상 불가

No hold and wait : 자원을 얼마나 쓰는지 예측하고 미리 할당, 구현 어려움

No circular waiting : 자원에 번호를 부여하여 한 방향응로 할당 받도록 함

 

 

Banker's Algorithm

각 프로세스마다 maximum resource needs를 정의하여 safe state에 있는지 확인

자원을 부여할 때, safe state를 유지하는지 확인

 

* Safe state는 deadlock 절대 발생 X, Unsafe state는 발생할 수 있음

 

 

Notation

Available[1:m] : 각 자원의 부여가능한 자원 개수

Max[1:n, 1:m] : 각 프로세스의 자원 최대 수요

Allocation[1:n, 1:m] : 각 프로세스의 현재 할당되어 있는 자원 개수

Need[1:n, 1:m] : 각 프로세스가 추가로 원하는 최대 자원 개수

 

->  Max[i, j] = Allocation[i, j] + Need[i, j]

 

 

Safety check

Work[1:m] = Available, Finish[1:n] = false;

Find i such that

    Finish[i] = false & Need[i] <= Work

Work = Work + Allocation[i]

Finish[i] = true

반복

 

-> Finish가 모두 true이면 safe state, 하나라도 false이면 unsafe state

 

 

Resource request

Request[i] <= Need[i] 확인        -> 그렇지 않으면, error

Request[i] <= Available 확인      -> 그렇지 않으면, wait

Available = Available - Request[i]

Allocation[i] = Allocation[i] + Request[i]

Need[i] = Need[i] - Request[i]

Safety check

-> safe state이면 할당, unsafe state이면 transaction 취소하고 request 기다림

 

 

Deadlock termination

프로세스 response timed을 모니터링하다가 Deadlock 프로세스를 abort함

 

* CPR (Checkpoint and Resume) : 일정 시간 간격으로 모든 상태를 디스크에 저장하고 문제 발생되었을시 저장된 상태를 이용해 수행을 재개함

 

* Watchdog timer : 일정 시간동안 kernel이 반응하지 않으면 kernel 재시작 시킴