Deadlock

정의\
프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태로, ‘교착 상태’라고도 하며 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생한다.

Deadlock의 발생조건

• 상호배제
  • 사용중인 자원을 다른 포르세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야한다.
• 점유대기
  • 자원을 최소한 하나보유하고, 다른 프로세스가 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
• 비선점
  • 이미 할당된 자원을 강제로 빼앗을 수 없다.
• 순환대기
  • 대기 프로세스의 집합이 순환형태로 자원을 대기하고 있어야한다.

철학자의 식탁\
1. 일정 시간 생각을 한다.
2. 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
3. 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
4. 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.
5. 오른쪽 포크를 내려놓는다.
6. 왼쪽 포크를 내려놓는다.
7. 다시 1번으로 돌아간다.

만약 모두 동시에 왼쪽 포크를 들면 아무도 밥을 못먹는다. 이럴때는 4가지 발생조건을 만족한다.
1. 상호배제 : 포크를 두개다 들어야 식사가 가능하다.
2. 점유대기 : 오른쪽 철학자가 포크를 들어서 자원을 보유했고, 그 오른쪽 철학자를 또 기다린다.
3. 비선점 : 다른 철학자의 포크를 뺏는건 안된다.
4. 순환대기 : 이 식탁이 원형이라 그림이 원형으로 그려진다.

Deadlock의 해결법

• 데드락이 발생하지 않도록 예방(prevention) 하기
• 데드락 발생 가능성을 인정하면서도 적절하게 회피(avoidance) 하기
• 데드락 발생을 허용하지만 데드락을 탐지(detection)하여, 데드락에서 회복하기

4가지 조건을 다 해결해야 deadlock이 해결될까?\
정답은 ~~~ 아니다!!\
위에 4조건이 모두 만족해야 deadlock상태가 되는 것이기에 하나만 해결한다면 deadlock은 해결된다.

Deadlock 예방

4가지 조건을 부셔야 한다.

• 자원의 상호 배제 조건 방지 : 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 합니다.
  • 그러나 추후 동기화 관련 문제가 발생할 수 있습니다.
• 점유 대기 조건 방지 : 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류해서, 나중에 또다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 합니다.
• 비선점 조건 방지 : 이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 합니다.
• 순환 대기 조건 방지 : 자원을 순환 형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 합니다.

Deadlock 회피

은행가(은행원) 알고리즘은 자원의 할당 허용 여부를 결정하기 전에 미리 결정된 모든 자원의 최대 가능한 할당량을 시뮬레이션하여 안전 여부를 검사한다. 그런 다음 대기 중인 다른 모든 활동의 교착 상태 가능성을 조사하여 “안정 상태” 여부를 검사 확인한다.

대표적인 은행원 알고리즘으로 회피 방법을 설명한다.

은핼원 알고리즘이란 쉽게 말해 자원을 할당하면 데드락에 걸리니? 라고 미리 검사해보는 것이다.
그래서 '안정상태', '불안정상태'로 나눈다.
프로세스가 자원을 요구할때 자원을 할당한 후에도 안정 상태이면 자원을 할당하고, 그렇지 않으면 다른 자원이 해제될때까지 대기했다가 자원을 할당합니다.

은행원 알고리즘의 단점

• 할당할 수 있는 자원수가 일정 해야함
• 항상 불안전 상태를 방지해야 하므로 자원 이용도가 낮다
• 최대 자원 요구량을 미리 알아야 한다.
• 프로세스들은 유한한 시간 안에 자원을 반납해야 한다.

Deadlock Detection & Recovery

Detection

• Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 여부를 탐색합니다. 즉, 은행원 알고리즘에서 했던 방식과 유사하게 현재 시스템의 자원 할당 상태를 가지고 파악합니다.
• 이 외에도 자원 할당 그래프를 통해 탐지하는 방법도 있습니다.

Recovery

• 데드락을 탐지 기법을 통해 발견했다면, 순환 대기에서 벗어나 데드락으로부터 회복하기 위한 방법을 사용합니다.
  • 단순히 프로세스를 1개 이상 중단시키기
    • 교착 상태에 빠진 모든 프로세스를 중단시키는 방법 : 계속 연산중이던 프로세스들도 모두 일시에 중단되어 부분 결과가 폐기될 수 있는 부작용이 발생할 수 있음
    • 프로세스를 하나씩 중단 시킬 때마다 탐지 알고리즘으로 데드락을 탐지하면서 회복시키는 방법 : 매번 탐지 알고리즘을 호출 및 수행해야 하므로 부담이 되는 작업일 수 있음
  • 자원 선점하기
    • 프로세스에 할당된 자원을 선점해서, 교착 상태를 해결할 때까지 그 자원을 다른 프로세스에 할당해 주는 방법