교착상태(Deadlock)

시스템 내에 임계구역(critical section)이 존재하면 프로세스 간 상호배제 를 보장해야 한다. OS가 상호배제를 보장하기 위해 잠금을 사용하다보면, 작업이 더 이상 진행되지 않는 교착상태 에 빠질 수 있다.

• 상호배제(mutual exclusion): 임계구역 내에는 한 번에 하나의 프로세스만 있어야 한다는 것

교착상태란?

2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만을 기다리면서 작업을 더 이상 진행하지 못하는 상태를 말한다. 이에 운영체제는 감시를 하다 교착상태가 발생하면 강제로 해결해야 한다.
다른 프로세스와 공유할 수 없는 시스템 자원을 사용할 때(프린터 등), 공유 변수를 사용할 때, 데이터베이스 같은 응용 프로그램을 사용할 때 교착상태가 발생할 수 있다.

교착상태 필요 조건

교착상태는 아래 4가지를 모두 충족해야 발생한다.

1. 상호 배제(Mutual exclusion): 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다는 것. 배타적인 자원은 임계구역으로 보호되기 때문에 이를 사용하면 교착상태가 발생한다.

2. 비선점(Non-preemption): 한 프로세스가 사용중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 자원이어야 한다. 자원을 뺏을 수 없다면 공유할 수도 없으므로 교착상태가 발생한다.

3. 점유와 대기(Hold and wait): 교착상태가 발생하려면 다른 프로세스가 필요로 하는 자원을 점유하고 있으면서, 또 다른 자원을 기다리는 상태여야 한다.

4. 순환성 대기(Circular wait): 3번의 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다. 이 프로세스들이 서로 방해하는 방향이 원을 이루면 프로세스들이 서로 양보하지 않기 때문에 교착상태가 발생한다.

식사하는 철학자 문제

철학자 5명이 둥그런 식탁에 앉아 식사를 하는데, 왼쪽에 있는 포크를 잡은 뒤 오른쪽에 있는 포크를 집어야 식사 가능하다는 조건이 있다.

이 문제에서 철학자는 프로세스를, 포크는 자원을 상징한다.

• 교착상태의 필요 조건
  1. 상호배제: 철학자들은 서로 포크를 공유할 수 없다.
  2. 비선점: 각 철학자는 다른 철학자의 포크를 빼앗을 수 없다.
  3. 점유와 대기: 각 철학자는 왼쪽 포크를 잡은 채 오른쪽 포크를 기다린다.
  4. 순환성 대기: 모든 철학자들이 자신의 오른쪽에 앉은 철학자가 포크를 놓기를 기다린다.

교착상태 해결 방법

교착상태를 해결하는 방법에는 예방, 회피, 검출이 있고, 추가적으로 교착상태가 발견된 후에 자원을 회복하는 방법도 있다.

1. 교착상태 예방

사전에 교착상태를 발생시키는 4가지 조건 중 하나라도 발생하지 않도록 제약을 가하는 방법이다. 그러나 자원을 보호하기 위해 상호 배젝와 비선점을 예방하기 어렵다. 또한 점유와 대기, 순환성 대기는 작업 방식을 제한하고 자원을 낭비하기 때문에 사용할 수 없다.

2. 교착상태 회피

프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하고, 그 수준 이하로 자원을 나누어주는 방식이다. 교착상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 발생하는 범위에서는 프로세스를 대기시킨다. 자원의 총 수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나누고, 시스템이 안정상태를 유지하도록 자원을 할당한다.

Banker’s algorithm(은행가 알고리즘)

은행에서 대출 금액이 대출이 가능한 범위 내이면 허용되지만 그렇지 않으면 거부되는 것과 유사하여 은행가 알고리즘이라 불린다. 이 알고리즘에서 각 프로세스는 자신이 사용할 자원의 최대 수(Max)를 운영체제에 알려준다.

안정상태는 각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한 번 이상인 경우로 정의한다.

• 예시

Total: 14, Available: 2

=> 현재 가용자원이 2개 인데 P2가 필요로 하는 자원이 2개이기 때문에(가용 자원이 기대 자원보다 크거나 같음) 안정 상태이다.

교착상태 회피의 문제점

• 프로세스가 자신이 사용할 모든 자원을 미리 선언해두어야 하는데, 이것이 정확하지 않으면 교착 상태가 발생할 수 있다.
• 은행가 알고리즘에서 안정상태/불안정상태를 파악하려면 시스템의 전체 자원 수가 고정적이어야 하는데, 실제 시스템의 자원 수는 유동적이다.
• 교착상태 회피는 실제로 교착 상태가 발생하지 않는데도 발생할 것이라고 예상하고 프로세스에 자원을 할당하는 데 제약을 두므로, 자원이 낭비된다.

=> 따라서 사용하지 않는다.

3. 교착상태 검출

교착상태 해결방법 중 가장 현실적인 방법이다. 교착 상태 검출은 운영체제가 프로세스의 작업을 관찰하면서 교착상태 발생 여부를 계속 주시하는 방식이다. 교착상태가 발견되면 이를 해결하기 위해 교착상태 회복 단계를 밟는다. 교착상태 검출에는 타임아웃을 이용하는 것과 자원할당 그래프를 이용하는 것이 있다.

• 타임아웃을 이용한 교착상태 검출: 일정시간 동안 작업이 진행되지 않은 프로세스를 교착상태가 발생한 것으로 간주하여 처리하는 방법이다. 윈도우에서 ‘프로그램이 응답이 없어 종료합니다’라는 메시지가 뜨는 것이 대표적인 예이다. 엉뚱한 프로세스가 강제 종료될 수 있다는 문제가 있지만, 대부분의 데이터베이스와 운영체제에서 많이 선호한다.

4. 교착상태 회복

교착상태가 검출되면 교착상태를 푸는 작업을 말한다. 회복 단계에서는 교착상태를 유발한 프로세스를 강제로 종료한다. 프로세스를 종료할 때는 1. 교착상태를 일으킨 모든 프로세스를 동시에 종료하는 방식과 2. 교착상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료하는 방식이 있다.