교착 상태 (Deadlock)

교착 상태 정의

• 한 Process (Thread) 가 자원을 점유하고 다른 Process (Thread) 들이 기다리고 있는 상태.
• 대부분 운영체제들이 교착 상태를 완전히 막는 것은 아직 불가능하다.
  • 하지만 이를 최소화 하기 위해 고유 알고리즘을 사용하여 최소화하고 있다.

교착 상태의 시스템 모델

교착 상태 메카니즘에서 다루는 시스템 모델은 아래와 같이 정리할 수 있다.

• 시스템 모델은 크게 자원 (Resource), 쓰레드 (Thread) 2 가지로 구성된다.
• 동기화 도구 (Mutex, Semaphore) 들도 시스템 자원 중의 하나로 생각한다.
• 쓰레드들은 다른 프로세스의 자원들을 사용할 수 있다. (교착 상태의 주 원인.)
  • 단, 커널 프로세스의 자원은 영향이 없다. OS 측에서 감시를 대신 한다.
• 쓰레드의 자원 사용 단계는 3단계로 나뉜다.
  • 요청 (Request) : 쓰레드가 자원 이용 허용을 받을 때까지 기다린다.
  • 사용 (Use) : 쓰레드가 자원에 접근한다.
  • 방출 (Release) : 자원을 사용한 이후에 다른 쓰레드들에게 방출한다.
• 교착 상태의 기본적인 구상은 배고픈 철학자 문제를 참고할 것.
• 자원 할당 그래프
  • T (Thread), R (Resource) 로 구성이 된다.
  • 순환 경로가 있는 경우에는 교착 상태가 발생 할 수도 있다.
    (반드시 발생한다 라는 의미로 생각하면 안 된다.)
• 교착 상태 처리 방법 : 예방 (Prevention), 회피 (Avoidance), 탐지 (Detection), 복구 (Recovery)

교착 상태 발생 조건

• 상호 배제 (Mutex Exclusion) : 여러 프로세스 중 하나만 진입 가능한 경우.
• 점유 및 대기 (Hold & Wait) : 프로세스가 자원을 점유하고, 다른 프로세스들이 사용 완료되길 기다리고 있을 때.
• 선점 불가 (No Preemption) : 프로세스를 종료 하더라도 임의로 중단이 되지 않을 때.
• 순환 대기 (Circular Wait) : 프로세스가 순환적으로 기다리고 있을 때.

배고픈 철학자 문제

1. 철학자 5 명이 각자 식사를 하는데 양 옆에 젓가락이 있다.
2. 갑자기 한 철학자가 젓가락을 양 옆에 있는 젓가락을 들게 된다.
3. 2 번 과정에서 한 철학자는 분명 식사를 못 하게 된다. 이러한 과정에서 교착 상태가 발생하게 된다.

이 문제는 동기화 도구 (세마포어, 모니터) 를 사용하더라도 완전히 해결할 수 없다. 다만 교착 상태는 방지할 수 있어도, 기아 문제는 분명 발생한다.

교착 상태 조건과의 대입

• 상호 배제 : 식사를 할 땐, 젓가락을 옆 사람과 동시에 사용할 수 없다.
• 점유 상태 대기 : 스윙스가 식사를 끝 마치는 동안 기다린다.
• 선점 불가 : 식사 중에 왼쪽에 있는 사람의 젓가락을 뺏을 수 없다.
• 순환 대기 : 팔로알토부터 왼쪽에 있는 젓가락을 집게 되면, 결국 수퍼비는 젓가락을 못 집게 된다.
• 양쪽에 젓가락이 있는 경우에만 스스로 식사를 하는 방법이 있다. (상호 배제를 해결)
• 4 명의 철학자만 앉아서 식사하는 방법도 있다. (선점 해결)
• 비대칭적으로 순서를 결정하여 식사하는 방법이 있다. (순환 대기 해결)

교착 상태 예방

• 교착 상태 발생 조건 4 가지 중 하나를 없애면 된다.
• 상호 배제
  • 자원 하나에 대하여 읽기 전용으로 전환 시킨다.
  • 자원 동시 접근을 가능케 하기 위한 상호 배제를 처리하기는 이론적으로 어렵다.
• 점유 및 대기
  • 자원 요청 시, 다른 자원을 가지고 있으면 안 된다.
  • 모든 자원에 대한 할당 혹은 할당하지 않는 방법도 있다.
  • 자원 사용 방식을 변화 시켜서 교착 상태를 해결하는 것에 의의를 둬야 한다.
  • 단점 : 자원 이용률 저하, 자원 정보 파악 어려움, 일괄 작업 방식으로 작동 및 기아 현상 발생.
• 선점 불가
  • 모든 자원을 선점할 수 있도록 만드는 방법이 있다.
  • 프로세스의 우선 순위가 닞은 경우 기아 현상 발생 가능성 있음.
  • CPU 레지스터, DB 트랜젝션 원리와 비슷하다.
• 순환 대기
  • 점유와 대기를 하는 프로세스들이 원형을 유지하지 않도록 하는 방법.
  • 각 프로세스 요청 별로 인덱스를 붙이는 방법이 있다.
  • 단점 : 프로세스 작업 유연성 저하, 자원 인덱스 번호 알고리즘 필요.
• 어떻게 보면 점유 및 대기, 순환 대기는 해결을 해도 자원을 낭비할 수 밖에 없다.

교착 상태 회피

• 교착 상태가 발생하지 않는 범위 내에서 자원을 할당한다.
  • 단, 교착 상태가 발생할 것으로 판단 된다면 대기로 보낸다.
• 순환 대기 상태가 발생하지 않도록 향시에 검사를 하게 된다.
• 안정 상태 : 프로세스들이 순조롭게 순서대로 자원을 요청할 수 있는 상태.
  • 할당된 자원 개수가 적을수록 안정 상태에 가까워진다.
  • 안정 상태를 유지하는 것이 교착 상태 회피의 핵심이다.
• 불안정 상태 : 모든 프로세스 중 분명히 문제가 발생할 수 있는 상태.
  • 할당된 자원 개수가 많을수록 불안정 상태에 가까워진다.
  • 교착 상태도 불안정 상태의 일부이기도 하다.
• 은행원 알고리즘 : 교착 상태를 대표로 하는 알고리즘.
  • 은행은 고객들이 각종 금융 서비스를 사용해도 일정하게 유지되어야 한다는 점에서 각안을 했다.
  • 가용 자원 (Available), 최대 자원 (Max), 할당 자원 (Allocation) 등의 변수로 구성되어 있다.
  • 자원을 할당 할 때의 교착 상태 발생의 여부를 시각화 할 수 있다.
  • https://en.wikipedia.org/wiki/Banker's_algorithm

교착 상태 탐지

• 교착 상태 예방 및 회피를 안 하게 되면 반드시 탐지 및 회복은 진행해야 한다.
• 교착 상태 발생 여부를 계속 탐색을 하는 방식이다.
  • 여기서 교착 상태가 발견되면 즉시 회복 시켜야 한다.
• 타임 아웃 기법을 사용하여 교착 상태를 검출한다.
  • 일정 시간동안 작업이 진행되지 않은 프로세스를 교착 상태로 간주한다.
  • 타임 아웃이 발생하면 프로세스를 종료한다.
• 대부분 운영체제 (윈도우, 유닉스 등) 가 이 기법을 사용하고 있다.
  • 물론 교착 상태 회복도 일부 포함된다.

교착 상태 회복

• 교착 상태 검출 이후 말 그대로 회복을 진행하는 기법이다.
  • 시스템이 자동으로 교착 상태로부터 회복하는 원리이다.
• 교착 상태를 일으킨 프로세스들에 한해서 아래와 같이 해결한다.
  • 전체 책임 : 교착 상태에 문제가 되었던 프로세스들을 종료한다.
  • 일부 책임 : 우선 순위, 작업 시간, 자원 활용도 등을 따진 뒤 최저 등급을 맞은 프로세스를 종료한다.
• 교착 상태 탐지, 희생자 선정 알고리즘을 계속 실행하여 해결해야 하기 때문에 오버헤드를 감수해야 한다.

데이터베이스의 교착 상태 관리

• 데이터베이스 업데이트 (INSERT, UPDATE, DELETE 등 포함) 는 트랜젝션으로 처리된다.
• 데이터 무결성을 해결하기 위해 Lock 을 사용한다.
• 트랜젝션도 교착 상태가 발생할 수 밖에 없다.
  • 대개 교착 상태 탐지, 회복 기법을 사용한다.
  • 교착 상태가 감지된 트랜젝션 중 일부를 중단 시켜 롤백을 한다.
• 물론 데이터베이스 엔진에 따라 달라질 수도 있다.