#DAY4 교착상태

이 글은 운영체제 스터디를 진행하면서 본인이 이해하기 위해 작성하는 글입니다.
참고 도서는 '쉽게 배우는 운영체제(한빛아카데미)'입니다.

---

dead lock (교착상태) : 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태를 교착 상태라고 한다.

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

 

resource allocation grap (자원 할당 그래프) : 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것이다. 자원 할당 그래프를 사용하면 어떤 프로세스에 자원이 할당되어 있는지 혹은 어떤 프로세스가 자원을 기다리고 있는지를 한눈에 파악할 수 있다.

 

자원이 2개 이상의 프로세스를 동시에 허용하는 경우가 있다. 여러 프로세스가 하나의 자원을 동시에 사용하면 이를 "multiple resource (다중 자원)" 이라고 부른다.

 

*(교착 상태 발생) 식사하는 철학자 문제

철학자 4명이 둥그런 식탁에 둘러앉아 식사를 하는데,
왼쪽에 있는 포크를 잡은 뒤 오른쪽에 있는 포크를 잡아야만 식사가 가능하다는 조건이 있다.
철학자들은 음식을 먹기 위해 왼쪽의 포크를 잡은 뒤 오른쪽 포크를 잡으려고 옆을 볼 것이다. 
그런데 옆에는 이미 왼손에 포크를 들고 있는 다른 철학자가 앉아 있다.
결과: 식사하는 철학자 문제의 결과는 오른쪽 포크를 잡지 못해 모두 굶어 죽는다는 것이다.

1. 철학자들은 서로 포크를 공유할 수 없다. - 자원을 공유하지 못하면 교착 상태가 발생한다.
2. 각 철학자는 다른 철학자의 포크를 빼앗을 수 없다. - 자원을 빼앗을 수 없다면, 놓을때 까지 기다려야 하므로 교착 상태 발생.
3. 각 철학자는 왼쪽 포크를 잡은 채 오른쪽 포크를 기다린다. - 자원 하나를 잡은 상태에서 다른 자원을 기다리면 교착 상태가 발생.
4. 자원 할당 그래프가 원형이다. - 자원을 요구하는 방향이 원을 이루면 양보를 하지 않기 때문에 교착 상태가 발생.

 

교착 상태 필요조건

• 상호 배제: 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다.
• 비선점: 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점자원이야 한다. 자원을 빼앗을 수 없으면 공유할 수도 없다.
• 점유와 대기: 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다. 다른 프로세스가 필요로 하는 자원을 점유하고 있으면서 또 다른 자원을 기다리는 상태
• 원형 대기: 점유와 대기를 하는 프로세스 간의 관계가 원을 이우어야 한다. 점유와 대기를 하는 프로세스들이 서로 방해하는 방향이 원을 이루면 프로세스들이 서로 양보하지 않기 때문에 교착 상태에 빠진다.

 

교착 상태 해결 방법

해결 방법	특징
교착 상태 예방	교착 상태를 유발하는 네 가지  조건을 무력화한다.
교착 상태 회피	교착 상태가 발생하지 않는 수준으로 자원을 할당한다.
교착 상태 검출	자원 할당 그래프를 사용하여 교착 상태를 발견한다.
교착 상태 회복	교착 상태를 검출한 후 해결한다.

 

교착 상태 예방. 4가지 방법

• 상호 배제 예방: 독점적으로 사용할 수 있는 자원을 없애버리는 방법이다. 시스템 내외 모든 자원을 공유할 수 있다면 교착 상태가 발생하지 않는다. 
• 비선점 예방: 모든 자원을 빼앗을 수 있도록 만드는 방법이다. 하지만 임계구역을 보호하기 위해 잠금을 사용하면 자원을 빼앗을 수 없을 뿐만 아니라 상호 배제도 보장할 수 없다.
• 점유와 대기 예방: 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법이다. 다시 말해 '전부 할당하거나 아니면 아예 할당하지 않는' 방식을 저용하는 것이다.
• 원형 대기 예방: 자원을 한 방향으로만 사용하도록 설정함으로써 원형 대기를 예방할 수 있다. 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하는 것이다.

교착 상태 회피

banker's alogorithm (은행원 알고리즘)

• 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당한다. 가용 자원이 기대 자원보다 크다는 것은 그 자원을 사용하여 작업을 끝낼 수 있는 프로세스가 있다는 의미이므로 '안정 상태' 이다.
• 가용 자원이 어떤 기대 자원보다 크지 않으면 할당하지 않는다. 가용 자원을 사용하여 작업을 마칠 수 있는 프로세스가 없다는 의미이므로 '불안정 상태' 이다.