데드락
교착 상태 라고도 하며 한정된 자원을 여러 곳에서 사용하려고 할 때 발생할 수 있습니다.
멀티 프로그래밍 환경에서 한정된 자원을 사용하려고 서로 경쟁하는 상황이 발생할 수 있습니다.(race condition)
어떤 프로세스가 자원을 요청했을때 이미 디른 프로세스에 의해 사용되고 있다면 요청을 한 프로세스는 대기 상태 로 전환됩니다. 이렇게 대기 상태로 전환된 프로세스들이 실행 상태로 변경 될 수 없는 상황을 교착 상태 라고 합니다.
데드락의 발생 조건
교착 상태 는 4가지 조건 이 동시에 성립 할 때 발생합니다.
따라서 4가지 조건 중 하나라도 성립하지 않는다면 교착 상태를 해결할 수 있습니다.
1. 상호 배제 (Mutual exclusion)
- 자원은 한번에 한 프로세스만이 사용할 수 있어야 한다.
2. 점유 대기 (Hold and wait)
- 최소한 하나의 자원을 점유하고 있으면서, 다른 프로세스가 사용중인 자원을 추가로 점유 하기 위해 대기하는 프로세스가 있어야 한다.
3. 비선점 (No preemption)
- 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 뺏을 수 없어야 한다.
4. 순환 대기 (Circular wait)
- 프로세스의 집합
{P0, P1, ,…Pn}에서P0는P1이 점유한 자원을 대기하고P1은P2가 점유한 자원을 대기하고P2…Pn-1은Pn이 점유한 자원을 대기하며Pn은P0가 점유한 자원을 요구해야 한다.
데드락 처리
교착 상태 를 해결하기 위한 세가지 방법이 존재합니다.
1. 교착 상태 예방 및 회피
교착 상태가 되지 않도록 보장하기 위하여 교착 상태를예방하거나회피하는 프로토콜을 이용하는 방법
2. 교착 상태 탐지 및 회복
- 교착 상태가 되도록 허용한 다음 회복시키는 방법
3. 교착 상태 무시
- 대부분의 시스템에서 교착 상태는 잘 발생하지 않고, 교착 상태를
예방,회피,탐지,복구하는것은 비용이 많이들기 때문에 무시
데드락 처리 - 교착 상태 예방 (Prevention)
교착 상태 발생 조건 중 하나를 제거 함으로서 해결하는 방법입니다.
1. 상호 배제 (Mutual exclusion) 부정
자원은 한번에 한 프로세스만이 사용할 수 있어야 한다.
->
여러개의 프로세스 가 공유 자원을 사용할 수 있도록 한다.
2. 점유 대기 (Hold and wait) 부정
최소한 하나의 자원을 점유하고 있으면서, 다른 프로세스가 사용중인 자원을 추가로 점유 하기 위해 대기하는 프로세스가 있어야 한다.
->
프로세스가 실행되기 전 필요한 모든 자원을 할당한다.
3. 비선점 (No preemption) 부정
프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 뺏을 수 없어야 한다.
->
자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때점유하고 있는 자원 을 반납 하고, 요구한 자원을 사용하기 위해 기다린다.
4. 순환 대기 (Circular wait) 부정
프로세스의 집합 {P0, P1, ,…Pn} 에서 P0 는 P1 이 점유한 자원을 대기하고 P1 은 P2 가 점유한 자원을 대기하고 P2…Pn-1 은 Pn 이 점유한 자원을 대기하며 Pn 은 P0 가 점유한 자원을 요구해야 한다.
->
자원에 고유한 번호 를 할당하고, 번호 순서대로 자원을 요구하도록 한다.
데드락 처리 - 교착 상태 회피
교착 상태가 발생하면 피해나가는 방법.
- 프로세스가
자원을 요구할 때 시스템은 자원을 할당한 후에도안정 상태로 남아있게 되는지를 사전에 검사하여 교착 상태를회피하는 기법 - 프로세스가
안정 상태라면 자원을 할당, 그렇지 않다면 다른 프로세스들이 자원을 해지할 때까지 대기
데드락 처리 - 교착 상태 탐지
자원 할당 크래프를 통해 교착 상태를 탐지한다. 자원을 요청할 때마다 탐지 알고리즘을 실행하면 오버헤드가 발생한다.
-
Pi->Rj:프로세스 Pi가자원 Rj를 요청하는것으로 현재 이 자원을 할당받길 기다리는 상태 -
Rj->Pi:자원 Rj가프로세스 Pi에 할당된 것을 의미
데드락 처리 - 교착 상태로부터 회복
교착 상태를 일으킨 프로세스를 종료하거나, 할당한 자원을 해제함으로서 교착 상태에서 회복하는 것을 의미한다.
1. 프로세스를 종료하는 방법
-
교착 상태의 프로세스들을 모두 중지
-
교착 상태가 제거될 때 까지 한 프로세스씩 중지
2. 자원 할당 해제하는 방법
-
교착 상태의 프로세스 가 점유하고 있는
자원을 할당 해제하여 다른 프로세스에게 할당하고,
해당 프로세스는 일시 정지시키는 방법 -
우선 순위가 낮은 프로세스,수행된 횟수가 적은 프로세스등을 위주로프로세스의 자원을 할당 해제한다.
