교착 상태

2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태

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

교착 상태 필요 조건
다음 4가지 조건이 모두 발생해야만 교착상태 발생

1. 상호 배제: 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 함
2. 비선점: 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 함
3. 점유와 대기: 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 함
4. 원형 대기: 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 함

자원 할당 그래프
프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것
(프로세스: 원, 자원: 직사각형, 할당을 받은 상태: 실선, 기다리는 상태: 점선)

식사하는 철학자 문제
왼쪽에 있는 포크를 잡은 뒤 오른쪽에 있는 포크를 잡아야만 식사 가능

식사하는 철학자 문제에서 교착 상태가 발생하는 조건

1. 철학자들은 서로 포크를 공유할 수 없음 (자원을 공유하지 못하면 교착 상태가 발생 – 상호 배제)
2. 각 철학자는 다른 철학자의 포크를 빼앗을 수 없음 (자원을 빼앗을 수 없으면 자원을 놓을 때까지 기다려야 하므로 교착 상태가 발생 – 비선점)
3. 각 철학자는 왼쪽 포크를 잡은 채 오른쪽 포크를 기다림 (자원 하나를 잡은 상태에서 다른 자원을 기다리면 교착 상태가 발생 – 점유와 대기)
4. 자원 할당 그래프가 원형 (자원을 요구하는 방향이 원을 이루면 양보를 하지 않기 때문에 교착 상태가 발생 – 원형 대기)

교착 상태 해결 방법
교착 상태 예방, 교착 상태 회피, 교착 상태 검출, 회복

1. 교착 상태 예방

– 상호 배제 예방: 시스템 내에 있는 상호 배타적인 모든 자원, 즉 독점적으로 사용할 수 있는 자원을 없애버리는 방법, 현실적으로는 모든 자원을 공유할 수 없으며 상호 배제를 적용하여 보호해야 하는 자원이 있음

– 비선점 예방: 모든 자원을 빼앗을 수 있도록 만드는 방법, 아사 현상을 일으켜 비선점 조건을 무력화하기는 어려움

– 점유와 대기 예방: 전부 할당하거나 아니면 아예 할당하지 않는 방식을 적용, 자원이 아닌 프로세스의 자원 사용 방식을 변화시켜 교착 상태를 처리한다는 점에서 의미가 있음
단점: 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어려움, 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리함

– 원형 대기 예방: 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하는 것
예) 마우스를 할당받은 상태에서 프린터를 할당받을 수는 있지만 프린터를 할당받은 상태에서는 마우스나 하드디스크를 할당받을 수 없음

단점: 프로세스 작업 진행에 유연성이 떨어짐

2. 교착 상태 회피

프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 할당을 함

– 은행원 알고리즘: 교착 상태 회피를 구현하는 대표적인 알고리즘
-> 은행이 대출을 해주는 방식, 즉 대출 금액이 대출 가능한 범위 내이면 허용하지만 그렇지 않으면 거부되는 것과 유사한 방식

– 은행원 알고리즘 예제

1. A B C가 10 5 7개에서 p0~p4가 모두 일정 부분 가져가서 3 3 2개 남음
2. p1의 Need가 1 2 2니까 p1 작업 가능
3. P1 작업 끝남 -> Available 5 3 2 -> P3 작업 가능
4. P3 작업 끝남 -> Available 7 4 3 -> P4 작업 가능
5. P4 작업 끝남 -> Available 7 4 5 -> P2 작업 가능
6. P2 작업 끝남 -> Available 10 4 7 -> P0 작업 가능
7. P0 작업 끝남 -> Available 10 5 7 

안정 상태 순서는 상관없다.
모든 작업을 끝낼 수 있으면 안정 상태에 있다고 표현

– 불안정 상태의 예

Need(Expect)가 4,2,4인데 available이 1이면 할 수 있는 것이 없음

교착 상태 회피의 문제점

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

3. 교착 상태 검출

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

데이터베이스에서 타임아웃의 문제: 데이터베이스에서 타임아웃으로 프로세스가 종료되면 일부 데이터의 일관성이 깨질 수 있음
-> 데이터의 일관성이 깨지는 문제를 해결하기 위해 체크포인트와 롤백 사용

2. 자원 할당 그래프 이용: 단일 자원을 사용하는 경우 자원 할당 그래프에 사이클 있으면 교착 상태

4. 교착 상태 회복

교착 상태를 유발한 프로세스를 강제로 종료

강제로 종료하는 방법

1. 교착 상태를 일으킨 모든 프로세스를 동시에 종료

2. 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
– 우선 순위가 낮은 프로세스를 먼저 종료
– 우선 순위가 같은 경우 작업시간이 짧은 프로세스를 먼저 종료
– 우선 순위와 작업 순위가 같으면 자원을 많이 사용하는 프로세스를 먼저 종료