Deadlock: Deadlock Conditions

Coffman conditions

데드락에는 4개의 필요충분조건이 있습니다. 이 조건들은 Coffman conditions라고 알려져 있습니다.

• Mutual Exclusion
• Circular Wait
• Hold and Wait
• No Pre-emption

만약 위의 4개 중 하나라도 어긴다면, deadlock은 발생하지 않습니다.

이러한 모든 조건들은 deadlock을 위해 필요한 조건들입니다. 하나하나씩 살펴봅시다.

• Mutual Exclusion - resource가 공유될 수 없다.
• Circular Wait - Resource Allocation Graph에 cycle이 존재한다. process의 집합 {P1, P2,...}이 존재할 때, P1은 P2가 사용하는 리소스를 기다리고 있고, P2는 P3가 사용하는 리소스를 기다리고 있고, ...은 P1이 사용하는 리소스를 기다리고 있는 경우.
• Hold and Wait - 프로세스가 리소스를 완전하게 가져오지 못해 다른 리소스를 가져오는 동안 기다리고 있습니다.
• No pre-emption: 일단 프로세스가 리소스를 취득하고 나면, 그 리소스를 빼앗는 것이 불가능하고 프로세스가 자발적으로 리소스를 포기해야 합니다.

Breaking the Coffman Conditions

두 학생이 펜과 종이가 필요하다고 생각해 봅시다.

• 두 학생이 펜과 종이를 공유합니다. Mutual Exclusion이 필요하지 않기 때문에 Deadlock은 발생하지 않습니다.
• 두 학생이 종이를 집기 전에 펜을 먼저 잡기로 합의합니다. circular wait이 발생하지 않으므로 deadlock이 발생하지 않습니다.
• 두 학생은 한 명령 안에서 펜과 종이를 잡습니다.(둘 다 잡거나 둘 다 잡지 않습니다). Hold and Wait이 발생하지 않으므로 deadlock이 발생하지 않습니다.
• 두 학생은 친구여서 서로의 리소스를 양보하라고 요청할 수 있습니다. pre-emption이 허락되므로 deadlock은 발생하지 않습니다.

Livelock

livelock은 deadlock이 아닙니다.

다음과 같은 해결책을 생각해 봅시다.

학생들은 10초 안에 집어들 다른 resource가 없다면 점유한 리소스를 내려놓습니다. 이 해결책은 deadlock을 회피할 수 있지만 livelock이 발생합니다.

livelock은 프로세스가 계속해서 실행되지만 진행은 되지 않는 경우 발생합니다. 사실 livelock은 프로그래머가 데드락을 피하기 위한 조치를 취했을 때 발생할 수 있습니다. 위의 예에서 busy system이라면 학생은 두 번째 리소스를 취할 수 없어 계속해서 처음 취한 리소스를 계속 내려놓을 것입니다.  이 시스템은 deadlock이 아니지만(학생의 process가 계속 실행중이므로), 어떠한 진행도 발생하지 않습니다.

Deadlock Prevention/Avoidace vs Deadlock Detection

데드락 예방은 데드락이 발생할 수 없도록 만드는 것입니다. 즉, coffman condition을 어기는 것입니다. 이 작업은 하나의 프로그램에서 가장 좋은 방법이고, 프로그래머는 특정한 coffman condition을 어길 조건을 선택할 수 있습니다.

Banker's Algorithm을  생각해봅시다. 이 알고리즘은 데드락을 회피하는 알고리즘입니다. 전체적인 구현은 이 수업의 범위를 벗어나므로, 운영체제에 더 일반화된 알고리즘이 존재한다는 것만 알고 있으면 될 것 같습니다.

반면 데드락 탐지는 시스템이 데드락 상태에 진입하는 것을 허락합니다. 데드락 상태에 진입한 후, 시스템은 정보를 이용해 데드락을 해결합니다. 예를 들어, 여러개의 프로세스가 파일에 접근한다고 생각해봅시다. OS는 파일 디스크립터를 통해 모든 파일과 리소스를 추적하는 것이 가능합니다. 만약 OS가 파일 디스크립터 테이블에서 cycle을 발견한다면, 하나의 프로세스를 중단하고(예를 들면 스케쥴링을 통해) 시스템이 진행되도록 할 수 있습니다.

Dining Philosophers

Dining Philosophers 문제는 고전적인 동기화 문제입니다. N명의 철학자를 식사에 초대했다고 생각해 봅시다(아래의 예에서 N=5). 

이 철학자들을 앉히고 각각의 철학자들 사이에 5개의 젓가락을 놓습니다. 철학자들은 생각하거나 먹을 수 있습니다. 먹을 철학자는 자신 양쪽의 2개의 젓가락을 집어야만 합니다. 하지만 이 젓가락들은 이웃과 공유하고 있습니다. 

이 때 모든 철학자들이 먹을 수 있는 효율적인 해결책이 있을까요? 또는 계속 두 번째 젓가락을 집지 못해 굶는 철학자가 있을까요? 아니면 모두 데드락이 될까요? 예를 들어, 모든 철학자들이 자신 왼쪽의 젓가락을 집고 오른쪽 젓가락을 사용할 수 있을때까지 기다린다고 생각해 봅시다. 그 경우 데드락에 걸리게 됩니다.