[OS] 교착상태(Deadlock)

deadlock

deadlock이란 프로세스가 자원을 얻지 못하고 상대방의 자원을 요구하면서 기다리는 상태를 의미한다.

모든 프로세스가 자원을 대기하고 있고, 어느 프로세스도 자원을 제공하려고 하지 않을 때 일어난다.

예를 들어 semaphore 간에 deadlock은 다음과 같이 일어날 수 있다

 

deadlock의 발생 조건

상호 배제(Mutual Exclusion) : 하나의 프로세스는 한 번에 하나의 자원을 사용한다.

비선점(No preemtion) : 한번 자원을 얻으면 중간에 방출되지 않는다.

점유 대기(Hold and Wait) : 최소 하나의 자원을 점유하고 있는 프로세스는 다른 프로세스가 점유하고 있는 다른 자원을 얻기 위해 대기해야 한다.

순환 대기(Circular Wait) : 프로세스들이 서로가 꼬리를 물며 원의 형태로 자원을 요구해야 한다.

 

deadlock 예방방법

No mutual exclusion

• 공유 자원에 대한 독점적인 접근을 허락하지 않는다 -> 하지만 이는 많은 자원의 특성상 합리적이지 않다.

No preemption

• 어떤 자원을 할당하고 있는 프로세스가 다른 프로세스가 할당받고 있는 자원을 원할경우, 그 자원을 할당받을 수 있다.  -> 잘못하면 live lock에 빠질 수 있다.

No hold and wait

• 필요한 자원을 순차적으로 하나씩 획득하게 하지 말고 필요한 모든 자원을 한 번에 얻게 한다. -> 어떤 자원을 원하는지 예측하기 어렵다.

No circular wait

• 모든 자원 타입에 대한 순서를 부여하고, 프로세스가 열거된 순서대로 오름차순으로 자원을 요청하게 한다.

 

은행원 알고리즘(Banker's Algorithm)

대표적인 deadlock 회피 방법에는 은행원 알고리즘이 있다.

교착상태에 빠질 가능성이 있는지를 판단하기 위해 안전 상태(Sate state)와 불안전 상태(Unsafe sate)로 나눈다. 

은행원 알고리즘에서는 안전상태를 유지할 수 있는 요청만 받아들이고, 불안전 상태를 유발할 수 있는 요청은 받아들이지 않는다.

은행원 알고리즘을 수행하기 위해서는 4가지 자료구조가 필요하다.

n = 프로세스의 수, m = 자원 타입의 수

Available[1:m] : 각 이용 가능한 자원 타입의 수

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

Allocation[1:n, 1:m] : 각 프로세스가 현재 할당받는 자원의 수

Need[1:n, 1:m]  : 현재 프로세스가 할당받기를 원하는 자원의 수

 

하나의 예시를 살펴보면 현재 Available 한 자원은 (3,3,2)이다.

각 프로세스에 대해서 Need의 수가 모든 자원의 타입에 대해서 Available보다 같거나 작은 프로세스는 P1이다.

따라서 P1이 자원을 할당받게 된다.

P1이 자원을 할당 받고 작업을 완료한 뒤에 종료되면 할당받은 자원을 반납하게 되어 Available은 (5,3,2)가 된다.