프로세스 교착상태
시스템은 자원으로 구성된다.
프로세스는 자원을 사용하기 전에 반드시 요청해야하고, 사용 후에 반드시 방출해야한다.
프로세스는 지정된 태스크를 실행하기 위해 필요한 만큼의 자원을 요청할 수 있다. 명백히 요청된 자원의 수는 시스템에서 사용 가능한 전체 자원수를 초과 할 수 없다.
- 요청 :프로세스는 자원요청 , 즉시 허용하지 않으면 대기
- 사용 : 자원에 대해 작업을 실행
- 방출 : 자원 방출
어느 프로세스에게 할당되었는지 기록
Deadlock Characterization
- ->상호 배제 : 최소한 하나의 자원이 비공유 모드로 점유되어야 한다. 다른 자원이 요청하면 방출될 때까지 기다려야한다.
- ->점유하며 대기 : 프로세스는 최소한 하나의 자원을 점유한 채 현재 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기해야한다.
- ->비선점 : 자원들을 선점할 수 없어야 한다. 자원 강제 방출 할 수 없고 점유하고 있는 태스크가 종류 후에 그 프로세스에 의해 자발적으로 방출
- -> 순환 대기 : 대기하고 있는 프로세스 집합에서 p0은 p1이 점유한 자원을 대기하고, P1은 P2가 점유한 자원을 대기한다.
Resource-Allocation Graph
- 정점 V 모든 활성 프로세스 집합 P와 자원 타입 R
- P->R 은 자원의 요청간선 R->P 는 자원이 할당된 할당간선
- 그래프가 싸이클을 포함하면 교착상태가 존재할 수 있다.
P1->R1->P2->R3->P3->R2->P1
Methods for Handling Deadlocks
- 시스템이 결코 교착상태가 되지 않도록 보장하기 위하여 교착상태 예방하거나 회피하는 프로토콜을 사용한다.
- 시스템이 교착상태가 되도록 허용한 다음에 회복시키는 방법이 있다.
- 문제를 무시하고, 교착상태가 시스템에서 발생하지 않는 척한다.
- 예방이나 회피 기법중 사용가능
Deadlock Prevention
1. 상호 배제(Mutual exclusion)
공유가 불가능한 자원에 대해서 반드시 성립해야한다.
2. 점유하며 대기(Hold and Wait)
- 점유하며 대기가 시스템에서 발생하지 않는다는 것을 보장하기 위해서는 프로세스가 자원을 요청할 때 다른 자원들을 가지고 있지 않다는 것을 보장해야 한다. 각 프로세스가 실행되기 전에 반드시 자신의 모든 자원을 요청하여 할당받게 하는 것이다.
- 한 대안은 프로세스가 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있도록 허용한다.
- 두 번째 방법은 프로세스가 처음에는 단지 DVD 드라이버와 디스크 파일만 요청하도록 허용하는 것이다. 모두 방출하고 다시 요청해야 한다.
단점
- 첫째 많은 자원들이 할당된 후 오래 동안 사용되지 않기 때문에 자원의 이용율이 낮을 수 있다. 남아 있으리라는 것을 확신할 수 없다면, 두 프로토콜 모두에서 모든 자원을 처음부터 반드시 요청해야한다.
- 두 번째, 기아 상태가 가능하다. 인기자원들을 여러 개 필요로 하는 프로세스는 자신이 필요로 하는 자원 중에서 최소한 하나가 항상 다른 프로세스에게 할당되어 무기한 기다릴 수도 있다.
3. 비선점(No Preemption)
- 이미 할당된 자원이 선점되지 않아야 한다. 어떤 자원이 선점되어 현재 사용하고 있는 프로세스가 뺏기면서 할당해주고 옛 다른 자원들을 다시 획득할 수 있을 때에만 다시 시작한다.
- 대안으로, 한 프로세스가 어떤 자원들을 요청하면, 이들이 사용 가능한지 검사한다. 가능하면 할당한다. 불가능하다면 추가 자원을 기다리고 있는 다른 프로세스에게 할당되었는지 검사한다. 대기중 인 프로세스로부터 필요로 하는 자원을 선점해 요청 프로세스에게 할당.
4. 순환 대기(Circular Wait)
순환대기 조건이 성립하지 않도록 하는 한 가지 방법은 모든 자원 타입들에게 전체적인 순서를 부여하여 각 프로세스가 열거된 순서대로 오름차순으로 자원을 요청하도록 요구하는 것이다.
Deadlock Avoidance
- 교착상태 회피하는 다른 대안은 자원이 어떻게 요청될 지에 대한 추가정보를 제공하도록 요구하는 것이다. 교착상태가 일어날 것 같은 프로세스들에 대해 대기 여부를 결정할 수 있다.
- 각 요청에 위와 같은 결정을 하려면 시스템은 현재 가용 자원, 현재 각 프로세스에 할당된 자원, 그리고 각 프로세스가 앞으로 요청하거나 방출할 자원을 고려해야 한다.
- 가장 간단하고 단순하고 제일 유용한 모델은 각 프로세스가 자신이 필요로 하는 각 타입의 자원마다 최대 개수를 선언하도록 요구하는 것이다. -> 교착 상태 회피 접근 방법
Safe Sate
- 시스템이 안전하다는 말은 시스템이 어떤 순서로든 프로세스들이 요청하는 모든 자원을 교착상태를 야기시키지 않고 차례대로 모두 할당해 줄 수 있다는 것을 뜻한다.
- 자원을 줄 수 없으면 순서에 따라 다른 프로세스가 끝낼 때까지 대기하여 할당함
- 시스템이 불안하다고 해서 반드시 교착상태로 나가지 않음 교착상태로 될 가능성이 있다는 뜻이다.
Resource-Allocation Graph Scheme
- 예약간선(claim edge) Pi->Rj는 pi가 미래에 자원 Rj를 요청할 것이라는 의미이다.
- 점선으로 표시. Pi가 Rj를 요청하면 요청 간선으로 변환된다.
- Pi 가 Rj를 방출하면 Rj->Pi 되있는 것이 예약간선인 Pi->Rj로 다시 변환된다.
- ! 시스템에서 자원이 반드시 미리 예약되어야 함에 유의해야 한다.
- 만약 사이클이 없다면 자원을 할당해도 시스템은 안전 상태가 된다.
은행원 알고리즘
Deadlock Detection
- 교착상태가 발생했는지 결정하기 위해 시스템의 상태를 검사하는 알고리즘
- 교착상태로부터 회복하는 알고리즘
Single Instance of Each Resource Type 각 자원의 타입이 한 개씩만 있는 경우
- 모든 자원들이 한 개의 인스턴스만 있다면 대기 그래프 라고 하는 자원 할당 그래프의 변형을 사용해 교착 상태 탐지 알고리즘을 정의할 수 있다.
- 자원 할당 그래프로부터 자원 타입의 노드를 제거하고 적절한 간선들을 결합함으로써 대기 그래프를 얻을 수 있다.
- 여러 자원타입이 있는 경우 사용할 수 없음
Detection-Algorithm Usage
교착상태가 얼마나 자주 일어나는가, 일어나면 통상 몇 개의 프로세스가 연루되는가
Recovery from Deadlock
- 교착상태 깨뜨리기
- 단순히 한 개 이상의 프로세스를 중지 시킨다.
- 교착상태에 있는 하나 이상의 프로세스들로부터 자원을 선점하는 것이다.
프로세스 종료
- 교착상태 프로세스를 모두 중지 : 교착상태 깨뜨리지만 비용이 크다. 계산한 것을 나중에 다시 계산해야 하기 때문
- 교착상태가 제거될 때까지 한 프로세스 씩 중지 : 계속 교착상태 있는지 확인해야 하기 때문에 오버헤드를 유발한다.
- 프로세스의 우선순위가 무엇인지
- 지금까지 프로세스가 실행된 시간과 지정된 일을 종료하는데 더 필요한 시간
- 프로세스가 사용한 자원 타입과 수
- 프로세스가 종료하기 위해 더 필요한 자원의 수
- 얼마나 많은 수의 프로세스가 종료되어야 하는지
- 프로세스가 대화형인지 일괄처리인지 여부
Resouce Preemption 자원 선점.
- 희생자 선택 : 종료에서와 같이 비용을 최소화 하기 위해 선점 순서를 결정해야 한다.
- 롤백 : 안정 상태로 롤백시키고 그 상태로부터 다시 시작해야 한다.
- 기아 : 희생자 선택이 주로 비용 요인에 근거한 시스템에서는 동일한 프로세스가 항상 희생자로 선택될 수도 있다. 비용요소에 롤백의 횟수를 포함시킨다.