[OS] Solution of Dining Philosophers

deadlock을 해결하는 방법 중 Deadlock prevention을 통해 식사하는 철학자 문제 해결법을 알아보고, Deadlock Avoidance 기법을 얕게 알아본다.

데드락을 발생하는 주요 원인 네 가지 기법을 알아보자

• Deadlock Prevetion: 데드락을 발생시키는 네 가지 조건 중 하나를 배제함으로써 데드락을 예방할 수 있다. 사전에 배제히는 것이다.
  그러나 이 방법은 device 활용률을 떨어뜨리고, 자원 사용률을 떨어뜨린다. 당연히 concurrency도 저하되며 구현이 복잡하다.
• Deadlock Avoidance: 시스템적인 state 하나를 설정하여 이를 기준으로 deadlock을 회피할 수 있다.
  미래에 deadlock 발생할지 말지에 대한 정보가 필요하다.
• Deadlock detection and recovery: deadlock 발생을 아예 배제하지 않고 발생 시 종료하거나 자원을 회수하는 방법을 사용한다.
• Just ignore the problem: deadlock이 발생하던 말던 무시한다. 잘 발생하지 않기 때문이다. 위의 세 가지 방법은 오버헤드가 크다.

Deadlock Prevention

교착상태 예방은 데드락을 유발하는 네 가지 조건 중 하나를 배제하는 것이다.
이들은 Mutual Exclusion, No preemption, Hold and wait, Circular Wait이다.
그러나 Mutual Exclusion과 No preemption은 제약하기 어렵다. shared resource에 접근하기 위해서, 모두 필요하다.

• Hold and wait: 자원을 한 번에 잡는다. A -> B 순서로 잡지 않고 한 번에 잡는다.
  동시성이 감소하여 비효율적이다.
• Circual Wait: cycle이 발생하는 그래프 형태가 나타나지 않게 Resource에 번호를 매기고 resource를 사용할 때, 오름차순으로 사용한다.
  구혀니 힘들고 복잡하다. B를 잡고 A를 잡는 행위를 하지 않는다. 여전히 B를잡고 A를 잡아 순차적으로 수행해야 더 효율적인 방법이 제약되어 동시성이 떨어진다.

fork 두 개를 한 번에 잡는다. 하나의 guard를 쳐서 구현하면 된다. 점진적인 resource 접근이 안돼 동시성이 떨어진다.

RO~R4까지 증가하는 순서로 fork를 잡는다. R4의 경우 R0 $\rightarrow$ R4 순서로 잡으면 된다.
실제 상황에선 굉장히 큰 동시성 감소로 인한 성능 저하가 발생한다.

Deadlock Avoidance

resource 접근 자체에 제약을 걸어 접근 request를 피하거나 허용하는 방법이다.
(질문)하드웨어의 경우, I/O device는 타격이 크다.
device 사용률이 떨어지고 동시성이 저하된다. 자원의 사용률이 떨어진다고 보는 것이 맞다.

동적으로 회피할지, 허용할지 결정해야한다. 이는 오른쪽의 그래프와 같이 실선과 점선으로 모델링하여 결정할 수 있다.
T1의 경우 R1을 할당받은 상태에서 T2가 R2 할당을 요청했을 때, 이는 당연히 미래에 cycle이 발생하기 때문에 요청을 거부해야한다.
이를 위해 unsafe, safe와 같은 state가 필요하다. deadlock이 일어나지 않게 접근조차 하지 못하게 하는 것이다.

예시와 같이 unsafe, safe state를 만들고 이를 기준으로 회피에 대한 결정을 내려한다.

safe의 경우 deadlock 아예 발생하지 않는다고 가정하고 모델링하기 때문에 자원 할당 요청을 허용한다.
unsafe의 경우 무조건 deadlock이 발생하지 않지만, 가능성마저 없애버린다. 회피한다.

Resource-Allocation-Graph Algorithm

state를 알기 위해 자원 할당 그래프 알고리즘을 사용할 수 있다.
digraph이다.

• Claim edge: 자원 요청 간선(점선)으로 방향이 존재한다. 이는 쓰레드/프로세스가 자원 요청을 표시하는 간선이며 미래에 대한 정보이다.
• Assignment edge: 자원 할당을 표시하는 간선(실선)으로 이미 쓰레드/프로세스에 자원이 할다된 것을 표시한다. 정확히 Claim edge가 Assignment edge로 바뀌었을 때 cycle이 없어야 safe, 있으면 unsafe이다.

하지만 이 알고리즘은 instance가 2개 이상인 resource type, 즉 resource에 두 개 이상의 쓰레드/프로세스가 접근 가능할 때, 사용할 수 없다.

이를 처리할 수 있는 Process Initiation Denial과 Resource Allocation Denial을 알아보자.

Process Initiation Denial

이 방법은 새로운 프로세스/쓰레드의 시작 자체를 거부한다. 이를 위한 기준이 존재하며 safe, unsafe를 결정하기 위해 위와 같은 데이터가 필요하며 이를 벡터와 행렬로 표현할 수 있다.

• Resource = R = $(R_1, R_2, ..,R_n)$: 자원 R에 대해, 각각의 쓰레드/프로세스에게 할당될 수 있는 수를 벡터의 형태로 저장한다.
• Available = V = $(V_1, V_2, .., V_n)$: 현재 시점에 쓰레드/프로세스에게 할당될 수 있는 자원의 남은 수이다.
• V: 쓰레드/프로세스에 할당된 것을 제외하고 할당할 수 있는 남은 자원의 수이다.
• Claim = C: 각각의 쓰레드/프로세스가 처리되기 위해 필요한 자원의 수이다.
• Allocation = A: 각각의 쓰레드/프로세스에게 현재 시점에 할당된 자원의 수이다.

그렇다면 다음과 같은 조건을 만족한다.
$R_j \geq C_{ij} \geq A_{ij}$

그리고 새로운 쓰레드/프로세스가 시작할 때 마다 다음과 같은 조건을 만족해야 시작을 허용한다.
$R_i \geq C_{(n+1)j} + \sum_{i=1}^{n}C{ij}$ for all $j$

Resource Allocation Denial

이 방법은 자원 할당 요청을 거부하는 방법이다. 새로운 쓰레드가 시작될 때, C를 선언해야한다.
그리고 시점마다 자원 할당을 요청할 때, 이게 safe인지 unsafe인지 확인해야한다.
정확하게 말해 $C_i-A{i} \leq V$를 만족해야 한다는 것이다.

만약 현재 시점에서 어떤 쓰레드/프로세스에게 할당이 가능하더라도, 할당 이후 시점에서 다른 쓰레드/프로세스가 요구할 수 있는 최악의 개수보다 모자르다면 unsafe로 결정하고 할당하지 않는다.

현재에 시점에 당연히 최악의 개수보다 모자르면 unsafe로 결정한다.

맨 마지막 P3은 예외로 정하고 보자.

이미 할당되어 있고, C-A 값이 이렇다 했을 때, V값은 3일 것이다.