교착상태

2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태를 교착상태(dead lock)이라 한다. 교착상태 발생시 운영체제가 강압적으로 해결해야 한다.

아사현상 vs 교착상태
아사현상은 운영체제가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제이고, 교착상태는 여러 프로세스가 작업을 진행다가 보니 자연적으로 일어나는 문제이다.

발생

1. 시스템 자원
   다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생한다. 어떤 프로세스가 임계구역으로 보호되는 프린터, 스캐너, CD 레코더 등 동시에 사용할 수 없는 시스템 자원을 할당받은 후 양보하지 않는 경우를 예로 들 수 있다.

2. 공유 변수(or 파일)
   임계구역 문제를 해결하기 위한 코드로, 무한 대기를 막지 못해 교착상태가 발생한 경우이다. P1은 lock1을 true로 만든 다음 lock2가 flase가 될 때까지 기다리고, P2는 lock2를 true로 만든 다음 lock1이 false가 될 때까지 기다린다. 이처럼 한 변수를 할당받은 상태에서 다른 변수를 기다리면 교착상태가 발생한다.
   

3. 응용 프로그램
   데이터베이스 같은 응용 프로그램에서도 교착상태가 발생한다. 데이터베이스는 데이터의 일관성을 유지하기 위해 잠금을 사용하는데, 이때 교착상태가 발생할 수 있다.

자원 할당 그래프

프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성 있는 그래프로 표현한 것이다.

필요조건

교착상태는 상호 배제, 비선점, 점유와 대기, 원형 대기를 모두 충족해야 발생한다.

1. 상호 배제(mutual exclusion)
   한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이여야 한다. 배타적인 자원은 임계구역으로 보호되기 때문에 다른 프로세스가 동시에 사용할 수 없다.

2. 비선점(non-preemption)
   한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.

3. 점유와 대기(hold and wait)
   프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다. 다른 프로세스의 작업 진행을 방해하는 교착 상태가 발생하려면 다른 프로세스가 필요로 하는 자원을 점유하고 있으면서 또 다른 자원을 기다리는 상태가 되어야 한다.

4. 원형 대기(circular wait)
   점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다. 프로세스가 특정 자원에 대해 점유와 대기를 한다고 해서 모두 교착 상태에 빠지는 것은 아니다. 점유와 대기를 하는 프로세스들이 서로 방해하는 방향이 원을 이루면 프로세스들이 양보하지 않기 때문에 교착상태에 빠진다.

식사하는 철학자 문제

철학자 4명이 둥근 식탁에 앉아 식사를 하는데, 왼쪽에 있는 포크를 잡은 뒤 오른쪽에 있는 포크를 잡아야만 식사가 가능하다는 조건이 있는 문제이다.

해결방법

1. 예방(Prevention)

교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화 한다.

🔹 상호배제 예방
독점적으로 사용할 수 있는 자원을 없애버린다.
🔹 비선점 예방
모든 자원을 빼앗을 수 있도록 만드는 방법이다.
🔹 점유와 대기 예방
전부 할당하거나 아니면 아예 할당하지 않는(all or nothing) 방식을 적용하는 것이다.
🔹 원형 대기 예방
자원을 한 방향으로만 사용하도록 설정함으로써 원형 대기를 예방한다. 즉 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하는 것이다.

💡 자원을 보호하기 위해 상호 배제와 비선점을 예방하기 어려우며 점유와 대기, 원형 대기는 프로세스 작업 방식을 제한하고 자원을 낭비하기 때문에 사용할 수 없다.

2. 회피(avoidance)

자원 할당량을 조절하여 해결한다. 자원을 할당하다가 교착 상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중단하고 지켜보는 것이다.

🔹 은행원 알고리즘(banker's algorithm)
은행이 대출해주는 방식, 즉 대출 금액이 대출 가능한 범위 내이면(안정상태) 허용되지만 그렇지 않으면 거부되는 것과 유사하기 때문에 이렇게 불리게 되었다.
🔻 문제점

• 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다.
• 시스템의 전체 자원 수가 고정적이어야 한다.
• 자원이 낭비된다.

3. 검출(detection)

어떤 제약을 가하지 않고 자원 할당 그래프를 모니터링하면서 교착 상태가 발생하는지 살펴본다.

🔹 타임아웃 이용
일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법이다.
🔻 문제점

• 엉뚱한 프로세스가 강제 종료될 수 있다.
• 모든 시스템에 적용할 수 없다.

🔹 자원 할당 그래프 이용
자원 할당 그래프를 보며 시스템 내의 프로세스가 어떤 자원을 이용하는지 또는 기다리고 있는지 알 수 있다.

4. 회복(recovery)

검출을 통해 교착 상태가 발생하면 교착 상태 회복 단계가 진행된다.

🔹 강제 종료 방법

• 교착 상태를 일으킨 모든 프로세스를 동시에 종료
• 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료