Deadlocks

The Deadlock Problem

• 코드 상으로 해결이 불가능한, indefinite blocking 을 deadlock 이라고 한다.

Bridge Crossing Example

• 다리를 건너는 자동차를 프로세스, 다리의 특정 구역을 자원이라고 하자.
• P1 은 R1 을 소유하고 R2 를 요청한다. P2 는 R2 를 소유하고 R1 을 요청한다.
  
• semaphore 의 교차 사용과 유사하게, deadlock 이 발생한다.
• 이 deadlock 을 해결하는 방법은 두 가지가 있다.

1. 차 하나를 다리 밖으로 던져 버린다 : process kill
2. 차 하나를 뒤쪽 넓은 공간으로 미룬다 : preempt resource and roll back

• Deadlock 처리에는 4 가지 요소가 있다.

1. Deadlock Detection : deadlock 이 발생 했음을 감지
2. Deadlock Recovery : detection 이후 해결 과정. 위에 언급된 process kill 과 roll back 이 있다.
3. Deadlock Avoidance : deadlock 발생 지점을 예상하고 deadlock free 상태까지 코드 수행 중단
4. Deadlock Prevention : Deadlock 발생의 4가지 필요조건 중 일부를 차단

System Model

• resource 의 종류에는 physical resource 와 logical device 가 있다.
• instance 는 특정 resource 의 갯수다.
• process 가 resource 에 행하는 연산에는 세 가지가 있다.

1. request : 프로세스가 특정 자원을 요청, semaphore 의 wait() 과 유사
2. use : 프로세스가 자원을 사용
3. release : 자원 사용이 끝남, semaphore 의 signal() 과 유사

• request 와 release 는 semaphore 와 system call 의 형태로 구현 가능하다.

Deadlock Characterization

Necessary Condition

• deadlock 의 4 가지 필요조건에 대해 알아보자.
• deadlock 이 발생하면 필요조건을 모두 만족하지만, 역은 성립하지 않는다.

1. Mutual Exclusion

• 공유 자원은 한 번에 하나의 프로세스만이 접근할 수 있다.

2. Hold and Wait

• 특정 자원을 소유한 프로세스가 다른 자원을 요청할 때, 그 자원이 사용 중이라면 wait 해야 한다.
• 자원을 보유중인 상태에서, 추가적인 자원을 기다리는 상황을 일컫는다.

3. No Preemption

• 자원의 반환은 소유하고 있던 프로세스가 자율적으로만 이루어질 수 있다.
• 즉, 강제적인 자원 반환인 preemption 이 금지된다는 말이다.
• preemption 이 있으면 deadlock 은 없다.

4. Circular Wait

• 위 그림처럼 자원을 사용하기 위한 waiting 관계가 cycle 을 형성하는 경우를 말한다.

Resource Allocation Graph

• RAG 라고도 불리며, 자원이 프로세스에 할당되는 양상을 보여주는 그래프다.
• allocation 양상이 한 눈에 보이기 때문에 deadlock detection 에 유리하다.
• 프로세스는 원, 자원은 사각형으로 나타낸다. 자원 안의 작은 사각형은 instance 를 뜻한다.
  
• 할당 관계는 화살표로 나타낸다.
• request edge 는 프로세스가 자원을 요청한 상태를 나타낸다. 요청이 아직 받아들여지지 않아 자원이 할당되지 않은 상태이기 때문에, 화살표의 끝이 사각형의 외부에 위치한다.
• assignment edge 는 요청이 승인되어, 프로세스에 자원이 할당된 상태다. 이 때 화살표는 사각형 내부의 instance 로 부터 출발해 할당된 프로세스까지 연결된다.
  
• 위 RAG 는 deadlock 이 발생한 경우를 보여준다.
• P2 와 P3 사이에 circular wait 이 있어, 서로를 wait 하기 때문에 deadlock 이 발생한다.
• 하지만, circular wait 이 있다고 무조건 deadlock 이 발생하는 것은 아니다.
  
• P1 과 P3 사이에 circular wait 이 존재하는 상황이다.
• 어느 시점에서, P4 가 자원을 반환한다고 가정해보자.
• P3 의 request edge 가 assignment edge 로 바뀌며 cycle 이 사라지고, 이로 인해 deadlock 이 발생하지 않는다.
• 이 예시로부터 알 수 있는 점은 다음과 같다.

1. RAG 에 cycle 이 없다면 deadlock은 발생하지 않는다.
2. single instance 의 경우, cycle 은 deadlock 의 필요충분조건이다.
3. multiple instance 의 경우, cycle 은 deadlock 의 필요조건이다.

Deadlock Prevention

• deadlock prevention 의 기본 아이디어는 필요조건의 차단이다.
• 필요조건의 차단은 deadlock 을 방지하지만, 차단이 불가하거나 부작용이 있을 수 있다.
• 각 필요조건에 대해 이를 따져보자

1. Mutual Exclusion

• 공유 불가한 자원을 다룰 때, mutual exclusion 을 부정하는 것은 불가능하다.

2. Hold and Wait

• Hold and Wait 을 부정한다는 것은, 자원을 소유중이지 않을 때만 request 를 할 수 있다는 것이다.
• 그러므로, 프로세스가 수행되기 전에 필요한 모든 자원을 미리 할당받아야만 한다.
• 이로 인해 여러 프로세스들이 병렬적으로 자원을 사용할 수 없고, 프로세스가 실행될 수 있는 조건이 까다로워지기 때문에, resource utilization 이 감소하고 starvation 을 일으키는 부작용이 생긴다.

3. No Preemption

• semaphore 처럼, preemption 이 허용되어서는 안 되는 자원들이 있다.

4. Circular Wait

• circular wait 을 부정한다는 것은, 모든 자원에 우선순위를 부여해 그 순서대로만 자원을 요청하도록 허용한다는 의미다.
• 이는 자원의 효과적 사용을 방해해 resource utilization 을 저해한다.

Deadlock Avoidance

• deadlock avoidance 의 기본 아이디어는 deadlock 예상 지점에서 코드 실행을 일시정지시켜 safe state 를 유지시키는 것이다.

Safe State

• 자원의 갯수가 요청의 갯수보다 많아, deadlock 으로부터 자유로운 상태다.
• deadlock avoidance 는 이 상태를 유지시키는 것이다.
• 자원이 충분하지 않다면, 특정 프로세스를 대기시키며 safe state 를 유지한다.
  => 이로 인해 많은 자원을 요하는 프로세스는 늦게 수행될 확률이 높다.
• safe state 를 유지시키는 프로세스 실행 순서를 safe sequence 라고 한다.
  
• 12개의 tape 를 분배하는 상황을 나타낸 그래프다.
• 각 프로세스 별로 최대 요청, 현재 요청, 앞으로 남은 요청이 명시되어 있다.
• 현재 요청 수에 따라 분배하고 남은 tape 의 갯수는 12 - (5 + 2 + 2) = 3 개다.
• safe state 를 유지하기 위해서는, P1 만 실행하고 나머지는 대기시켜야 한다.
• 이후 P1 이 종료되어 할당받았던 4개의 tape 를 반환하면, available tapes 는 5개가 되어 P0 을 safe state 내에서 실행할 수 있게 된다.
• P0 이 반환되어 10개의 tape 를 반환하면, 비로소 P2 를 실행할 수 있게 된다.
• 이 상황에서 safe sequence 는 P1, P0, P2 인 것이다.

Banker's Algorithm

• single instance 의 경우, RAG 를 통해 deadlock avoidance 를 쉽게 할 수 있었다.
  
• RAG 를 그리고 request edge 를 우선 점선으로 표현한 뒤, deadlock 이 예상되면 이를 실선으로 바꾸지 않으면 deadlock 을 피할 수 있다.
• 하지만, multiple instance 에서는 한 눈에 파악이 어려워, 다른 방법이 필요하다.
  => safe sequence 를 찾는 banker's algorithm 을 이용한다.
• banker's algorithm 는 loop 을 돌며, 프로세스 실행 순서를 수정해 safe sequence 를 찾아 나간다.
  
• 자원의 종류는 3가지, instance 는 각각 4, 6, 2개로 총 12개다.
• allocation 은 현재 요청에 의해 할당된 자원을, need 는 실행을 이어나가기 위해 추가로 필요한 자원을 나타낸다.
• banker's algorithm 에서의 loop은, need 를 순회하며 available 과 비교하면서 실행 가능한 프로세스를 찾는 것이다.
• allocation 후 available 은 각각 1, 2, 0 개다.
• need 를 순회해보면, P2 가 실행될 수 있으므로, 나머지는 대기시키고 P2 에 1, 1, 0 을 추가로 할당해 실행을 이어 나간다. 이 때 available 은 0, 1, 0 이다.
• P2 의 이전 과정이 종료됐으므로, 할당되어있던 2, 2, 0 이 반환되어 available 은 2, 3, 0 이 된다.
• 이와 같이 loop 을 반복하면 P2, P3, P4, P1 이라는 safe sequence 를 얻을 수 있다.
• safe sequence 는 여러 개 존재할 수 있으며, available 은 프로세스 반환과 함께 증가한다.

Deadlock Detection

Single Instance

• RAG, wait for graph 에서 cycle 여부를 찾는다.

Multiple Instance

• banker's algorithm 과 유사한 방법을 이용한다.
• need 값을 request 값으로 변환해 safe sequence 의 유무를 판단한다.
• safe sequence 가 없다면, deadlock 이 발생한 것으로 간주한다.

Deadlock Recovery

• deadlock recovery 에는 두 가지 방법이 있다.

1. process termination : deadlock 이 발생한 프로세스들을 종료시키는 방법이다.
2. checkpoint & roll back : context 가 저장된 가장 가까운 checkpoint 로 프로세스를 rollback 시킨다.