1. 교착상태 (Deadlock)
다중프로그래밍 시스템에서 아무리 기다려도 결코 일어나지 않을 사건을 기다리고 있는 하나 또는 그 이상의 프로세스들이 있는 상태
- 자원이 다수의 사용자 프로세스에 의해 공유되고
- 이들 각 프로세스가 자신에게 할당된 자원에 대해 독점적인 통제권을 가지고 있을때 발생
- 서로가 원하는 자원을 서로가 독점이용중인 상태
자원할당그래프
- 자원은 차원, 프로세스는 사각형
교착상태의 발생
상호배제, 점유와 대기, 비선점, 순환대기의 조건을 모두 만족했을때 교착상태 발생
- 상호배제 : 자원의 배타적인 제어권
- 점유와 대기 : 프로세스들은 다른 자원을 요구하면서 이미 어떤 자원 소유
- 비선점 : 자원이 자원을 점유하고 있는 프로세스로부터 도중에 벗어나지 못함
- 환형대기 : 프로세스 간 닫힌 체인 존재 (loop)
교착상태 해결방법
1) 교착상태 예방
사전에 교착상태의 가능성을 없애는 것 / 발생 필요조건을 만족하지 않게
- 상호배제예방 : 비공유자원에 대해서만 상호배제 하도록
- 점유와 대기 예방 : 필요한 자원을 한꺼번에 요청하여, 전부 할당해주던지 하나라도 없으면 아예 하나도 안해주던지 (all or nothing)
- 비선점예방 : 자원을 가지고 있던 프로세스가 더이상 자원 할당 요구가 받아들여지지 않으면 원래 가지고 있던 자원 일단 반납 후, 필요하면 다른 자원을 요구하는 방법 (선점을 가능케함)
- 환형대기 예방 : 각 자원의 할당 순서를 부여, 프로세스들이 자원을 요청 할때 번호 순서대로 요청
2) 교착상태의 회피 (avoidance)
교착상태 발생 가능성을 미리 제거하는 것이 아니라, 발생가능성을 인정하고 교착상태가 발생하려고 할때 이를 적절히 피해가는 방법
- 시스템의 운영 상황을 보아가면서 교착상태 가능성을 피해가는 것
- 은행가 알고리즘 : 프로세스가 현재 가용한 자원들을 요청할 때마다, 시스템은 자원이 즉시 할당될 수 있는지 또는 대기해야하는 지 결정 (안전상태를 유지)
- 자원할당상태 : 가용한 자원의 수, 할당된 자원의 수, 최대 자원요구수
- 은행가 알고리즘에서 자원은 동일한 유형의 자원을 의미
상태
- 안전상태 : os가 현재 모든 사용자에게 그들의 작업이 일정기간내에 끝나도록 할 수 있는 상태
- 불안전상태 : os가 현재모든 사용자에게 그들의 모든 작업을 일정기간내에 끝낼 수 없는 상태
- 교착상태 발생 가능한 상태 (불안전 = 교착상태를 의미하는 것은 아니다. 포함관계)
- 은행가 알고리즘의 단점
- 할당할 자원이 일정량 존재해야함
- 각 프로세스의 최대 자원 요구량을 미리 알아야한다.
- 일정한 수의 사용자 프로세스가 있을때만 적용 가능
- 프로세스들은 유한한 시간내에 할당된 자원을 반납해야함
- 시스템이 안전할 때만 자원을 할당, 자원의 할당 순서를 부여하여 제공
3) 교착상태의 발견 (detection)
여러시스템에서 사용되는 방법으로서, 원하는 것이든지 아니든지 일단 교착상태가 발생하도록 허용
- 교착상태가 발생하면 교착상태가 일어났는지 판단하고, 그 교착상태에 관련된 프로세스와 자원을 조사하여 결정해내는 방법
- 자원할당그래프 혹은 대기 그래프를 사용하여 사이클을 탐지하면서 교착상태 검출
- 프로세스와 자원간에 순환적 요구와 할당 관계에 있는 것을 규명
4) 교착상태의 회복 (recovery)
시스템으로부터 교착상태를 제거하여, 이후로는 시스템이 교착상태에 빠지지않고 잘 진행되게 함
- 교착상태에 빠진 프로세스가 완료되고, 그 프로세스에 할당된 자원을 회수할 수 있도록 함
- 교착상태 사이클이 없어질 때까지 프로세스들을 종료시키거나 할당된 자원을 중단시킴
- 회복은 몇개의 프로세스들이 수행한 작업이 일부 또는 전부를 잃게됨
