Deadlock

deadlock이란 둘 이상의 프로세스가 자원을 점유한 상태에서 다른 프로세스의 자원을 요구하여 무한정 기다리는(blocked) 상태이다.
예를 들어, process1에서 semWait(s1)을 하고 time out이 되고 process2에서 semWait(s2)를 한 후 time out이 됐는데, process1에서 semWait(s2)를 하여 block되고 process2에서 semWait(s1)을 하여 block된 상황이다.

Deadlock의 발생 조건

Deadlock의 발생 조건은 4가지이다.
1. Mutual Exclusion : semaphore처럼 Mutual Exclusion이 지켜져야 하는 상황
2. Hold-and-Wait : 자원을 할당받은 상태에서 다른 자원을 기다리는 상황
3. No Preemption : 어떤 프로세스든 가지고 있는 자원을 뺐을 수 없는 상황
4. Circular Wait : 아래 그림과 같은 상황

Dealing with Deadlock

Deadlock을 다루는 방법은 3가지이다.
1. Prevent deadlock : 자원을 할당하는 규칙을 정해서 deadlock이 걸리지 않게 한다.
2. Avoid deadlock : deadlock이 발생할지 계속 검사를 해서 발생하지 않을 때만 자원을 할당한다.
3. Detect deadlock : 자원을 일단 주고 주기적으로 검사해서 deadlock이 발생했는지 확인한다.
아래에서 이 3가지 방법에 대해서 알아보자.

Prevent deadlock

prevent deadlock은 자원을 할당하는 규칙을 정해서 deadlock이 걸리지 않게 해야하므로 deadlock의 발생 조건을 하나 씩 부정하면 된다.
하지만 mutual exclusion없이는 자원을 할당할 수 없으므로 나머지 3가지 발생조건을 부정할 것이다.

Hold and Wait

필요한 자원을 한 번에 requist해서 한 번에 할당한다.
자원낭비가 심하다는 단점이 있다.

No Preemption

자원을 전부 포기하고 처음부터 다시 할당받는다.

Circular Wait

자원에 번호를 매기고 자원의 할당과 요청을 번호 순으로 한다.

Avoid deadlock

avoid deadlock은 deadlock이 발생할지 계속 검사를 해서 발생하지 않을 때만 자원을 할당하는 것으로 2가지 방법이 있다.

Process Initiation Denial

Process Initiation Denial은 자원을 할당하기 전에 검사를 해서 발생한다면 process를 실행하지 못하게 한다.
그러므로 자원을 할당받기 위해서는 process가 요구하는 자원의 양보다 가진 자원의 양이 더 많아야 한다.

위와 같은 상황이라면, p1의 자원은 resource vector보다 작으니까 p1은 자원 할당을 받고 p2는 p1에서 할당한 자원을 뺀 resource vector보다 작으므로 p2도 자원을 할당 받는다.
하지만 p3는 p1,p2에서 할당한 자원을 뺀 resource vector보다 요청하는 자원이 더 크므로 p3는 자원을 할당하지 않는다.
Process Initiation Denial은 요청하는 자원의 수는 최대치이므로 동시에 필요한게 아니므로 자원의 낭비가 있다는 단점이 있다.

Resource Allocation Denial

Resource Allocation Denial은 banker's algorithm이라고도 불리며 자원을 할당하기 전에 검사를 해서 발생한다면 자원을 할당하지 못하게 한다.

위와 같은 상황이라면, Allocation matrix는 프로세스마다 자원을 할당해준 정도이고 C-A는 앞으로 프로세스마다 이만큼의 자원을 요청할 수도 있다는 의미이다.
현재 이용 가능한 자원인 Available vector의 양보다 작거나 같은 프로세스는 p2이므로 p2에 자원을 할당한 후, 할당해준 모든 자원을 다시 사용한다.

Detect Deadlock

Detect deadlock는 자원을 일단 주고 주기적으로 검사해서 deadlock이 발생했는지 확인한다.
1. Allocation matrix에서 요청하는 자원이 없어보이는 process는 hold-and-wait에서 hold한게 없으므로 mark를 하여 배재한다.
2. Request matrix에서 available vector보다 자원이 양이 같거나 작은 process는 자원을 할당해주고 할당한 자원을 반납하게 하고 hold-and-wait에서 wait할게 없으므로 mark하여 배재한다.
3. 2번 동작을 반복하여 모든 process가 mark되면 deadlock이 아니고 mark되지 않으면 deadlock이 발생한 것이다.

Dining Philosophers Problem

위와 같은 상황은 밥을 먹기위해서는 포크가 2개가 필요하고 포크는 한명만 쓸 수 있는 Dining Philosophers Problem이다.

A first solution using semaphore

semaphore를 이용해도 deadlock이 발생하는 solution이다.

Avoiding deadlock

room이라는 semaphore를 사용하여 room에 4명 이하로 있다면 언젠간 밥을 먹고 포크를 놓을테니 deadlock이 발생하지 않는다.

A solution using a monitor

monitor를 이용하여 구현한 solution으로 monitor가 c.s이므로 fork를 semaphore로 구현하지 않아도 된다.