교착상태 deadlock

프로세스나 스레드가 결코 일어날 수 없는 특정 이벤트를 기다린다면 해당 프로세스나 스레드가 "교착 상태에 빠졌다"고 한다. (프로세스에 초점을 맞춰 논의하겠지만 대부분은 스레드에도 적용된다).

 

교착 상태의 문제, 교착 상태에 관한 네 가지 교착 상태 방지(deadlock prevention), 회피(avoidance), 탐지 (detection), 복구(recovery), 또한 교착 상태와 연관이 많은 무기한 연기(기아 indefinite postponement(starvation)에 관해서도 알아보자

 

무기한 연기 - 기아 : 교착 상태에 빠지지 않은 프로세스가 시스템의 자원 스케줄링 정책 때문에 아주 먼 미래에 일어나나거나 전혀 일어나지 않을 이벤트를 대기하는 상황을 말한다. 

교착 상태의 예)

- 도로에서 발행하는 교착 상태

- 간단한 자원 교착 상태

- 스풀링 시스템에서의 교착 상태

- 철학자들의 만찬 : 5명의 둥근 식탁, 5개의 포크, 스파게티를 먹는데 먹을 때 두 가지 포크를 써서 먹어야 한다. 

 

교착 상태가 성립되기 위한 네 가지 필요충분조건

1. 자원은 한 번에 한 프로세스에서만 배타적으로 점유할 수 있다(상호배제)

2. 배타적으로 자원을 획득한 프로세스가 해당 자원을 점유한 채 다른 자원을 얻드려고 대기할 수 있다(대기조건, 보유 후 대기 조건)

 

3. 일단 프로세스가 자원을 확보하면 해당 프로세스가 자원을 모두 사용할 때까지 시스템이 프로세스의 제어를 빼앗을 수 없다(비선점 조건)

 

4. 두 프로세스 이상이 '순환 고리'에 갇혀 있다. 즉 각 프로세스는 고리 안에 있는 다음 프로세스가 점유하고 있는 자원을 대기한다. (순환 대기 조건)

 

교착 상태 해결책 

 

- 교착 상태 방지(deadlock prevention) : 시스템을 조절해 교착 상태가 발생할 만한 모든 가능성을 제거하는 것. 하지만 방지하려다 보면 자원 활용도가 떨어지는 결과를 초래할 수도 있다.

 

- 교착 상태 회피(deadlock avoidance) : 교착 상태의 가능성이 어느 정도 있을 수 있지만 교착 상태가 발생하려는 조짐이 보일 때마다 조심스럽게 비켜서는 전략을 취한다.

 

- 교착 상태 탐지(deadlock detection) : 교착 상태가 발생할 수 있는 시스템에서 사용한다. 교착 상태 탐지의 목적은 교착 상태 발생 여부와 관련 프로세스 및 자원을 밝히는 것이다.

 

- 교착 상태 복구(deadlock recovery) : 시스템에서 교착 상태를 없애서 교착 상태에 빠진 프로세스들이 실행은 완료하고 정상적으로 자원을 반납하게 하는 것이다. 복구는 잘 해봐야 아주 까다로운 문제다. 시스템에서 교착 상태에 빠진 프로세들이 한꺼번에 쏟아져 나올 수도 있다. 이런 프로세스들은 자원들 다시 사용할 수 있을 때 일반적으로 처음부터 재시작한다. 이때 이전에 수행한 작업의 상당 부분 또는 모두를 손실한다.

 

교착 상태 방지 기법

하벤더라는 분은 시스템이 네가지 조건 중 하나라도 거부하면 교착 상태가 발생할 수 없음을 발견하고, 다음과 같은 교착 상태 방지 전략을 제안했다. 근데 하덴더가 제안한 전략은 네 가지가 아닌 세 가지임이다.

 

- 각 프로세스는 필요한 모든 자원을 한꺼번에 요청해야 하고, 요청한 자원을 모두 제공받기 전까지는 작업을 진행할 수 없다.

 

- 프로세스가 어떤 자원을 보유하고 있다면, 해당 프로세스는 자원을 더 요청할 때 거부된다. 먼저 보유한 자원을 내놓고 추가로 필요한 자원과 함께 다시 요청해야 한다.

 

- 모든 프로세스에 자원을 순서대로 할당해야 한다. 즉 프로세스가 어떤 자원을 할당받았다면, 해당 프로세스가 뒤이어 요청하는 자원은 순서가 뒤에 있어야 한다.

 

'대기' 조건 거부

'비선점' 조건 거부

'순환 대기' 조건 거부

 

 

 

다익스트라의 은행원 알고리즘을 사용한 교착 상태 회피

 

• 운영체제는 고정된 수(n)의 프로세스 간에 고정된 수(t)의 자원을 공유하게 한다.
• 각 프로세스는 작업을 완료하는 데 필요한 최대 자원 수를 미리 결정한다.
• 운영체제는 프로세스의 최대필요치(maximum need)가 시스템에서 사용 가능한 최대 가원 수 t를 초과하지 않을 때 프로세스의 요청을 받아 들인다. (즉, 프로세스들은 시스템의 가용 자원 수의 총합을 초과해 요청할 수 없다.)
• 때때로 프로세스가 추가 자원을 획득하려고 대기해야 할 수도 있지만, 운영체제는 제한된 대기 시간 안에 자원을 얻을 수 있음을 보장한다.
• 만일 운영체제가 특정 프로세스의 최대 필요치를 들어준다면, 해당 프로세스는 자원을 제한된 시간 안에 사용하고 운영체제에 반납함을 보장한다.

만일 운영체제에서 현재 실행 중인 모든 프로세스가 제한 시간 안에 작업을 마칠 수 있음을 보장한다면 해당 시스템이 안전 상태에 있다고 말한다. 그렇지 않으면 시스템이 불안전 상태에 있다고 말한다.

 

그래서 무슨 계산법들이 나온다.

 

교착 상태 탐지

자원 할당 그래프 - 자원 할당 그래프 소거

 

교착 상태 복구

- 체크포인트/롤백 checkpoint/rollback