데드락: 두개 이상의 프로세스가 제한된 리소스를 경쟁적으로 접근할 경우 발생한다. 어떤 프로세스가 절대 일어나지 않을 이벤트를 기다리는 것을 말한다.
위 그림에서 어느 한 프로세스가 자원을 놔줘야 다른 프로세스가 그 자원을 사용하는데 서로 그러한 상태에 빠져있으니 절대 일이 진행되지 않는다.
deadlock 발생조건
- Mutual Exclusion
상호배제 조건이다. - Hold and Wait
자신은 이미 다른 자원을 사용하고 있으면서 추가로 다른 자원을 요청하여 사용을 기다린다. - Non-Preemptible
일단 할당된 자원은 그 사용을 완료하기 전에는 강제로 회수할 수 없다. - Circular wait
프로세스와 자원들이 원형을 구성하며 상호요청하는 경우이다.
deadlock Prevention - mutual exclusion
데드락의 조건 중 하나라도 유지가 안되면 데드락을 예방할 수 있다.
공유불가 자원은 mutual exclusion이 항상 존재한다. 한 프로세스가 사용하면 다른 프로세스는 사용하지 못하고 기다려야 한다. 예를 들어 프린터가 있다.
공유가 가능한 자원은 상호배제적으로 접근을 요구하지 않아서 데드락이 발생하지 않는다. 예를 들어 read-only 파일이 있다.
일반적으로 자원들은 공유가 불가능하므로 mutual exclusion을 예방하는 것은 불가능하다.
deadlock Prevention - hold and wait
hold and wait 조건 예방하기
: 프로세스가 자원을 요청할 때, 그 프로세스는 어떤 다른 리소스도 점유하고 있으면 안된다.
- 수행전에 필요한 모든 자원들을 할당 받고 수행한다. 점유하고 있을 때 다른 자원을 요청하지 않는다.
- 점유하고 있지 않으면 요청이 가능하도록 한다.
이런식으로 데드락을 예방할 시에 두개의 단점이 존재한다.
하나는 자원 사용률이 낮아질 수 있다는 것이다. 많은 자원들이 오랫동안 프로세스에 할당되었지만 사용되지 않는다. 그리고 기아현상이 일어날 수 있다. 인기 많은 자원들이 필요한 프로세스가 무한정으로 기다릴 수 있기 때문이다. 자원들 중 적어도 하나가 항상 다른 프로세스에 할당되어 있다.
deadlock Prevention - no preemption
강제회수를 허용한다.
이 조건을 만족하지 않는다는 것을 보장하기 위해 다음과 같은 방법을 사용할 수 있다.
- 만약 어떤 자원을 점유하고 있는 프로세스가 즉시 할당될 수 없는 또다른 자원을 요청한다면, 점유하고 있는 모든 리소스들은 회수된다. 그 프로세스는 그것이 점유했던 자원들이 그것에게 할당될 때 재시작될 것이다.
Rj가 즉시 Pi에 할당될 수 없다면 R1, R2, ..., Ri는 강제회수될 것이다.
- 만약 Pi가 Ri를 요청한다면 그것들이 사용가능한지 확인한다.
만약 사용가능하다면 할당한다.
그렇지 않다면 다른 프로세스 Pj에 할당되어 있는지 확인하고 그렇다면 Pj에서 필요로 하는 Ri를 강제회수하고 Pi에게 할당한다.
deadlock Prevention - circular wait
cycle이 형성되지 않도록 한다. 선형 ordering으로 예방할 수 있다.
각 프로세스는 증가하는 열거 순서로 리소스를 요청한다.
리소스는 tape drv, disk drv, printer가 될 수 있다.
F(tape drv) = 1, F(disk drv) = 5, F(printer) = 12
현재 보유하고 있는 정수 값보다 큰 것을 요청한다. --> 선형
