Deadlock_Deadlock의 발생 조건

Deadlock

 

여러 개의 프로세스들이 공유자원에 동시에 접근할 때 비의도적으로 공유자원의 값이 변경되거나 오염될 수 있는데, 이러한 상태를 Race condition 이라고 부릅니다. Race condition을 방지하기 위해 동기화(Synchronization)를 사용하고, 어떠한 프로세스가 Critical section을 사용하고 있다면 다른 프로세스는 사용하지 못하도록 차단합니다. 

 

그런데, 동기화를 사용하다보면 Deadlock의 상황이 발생될 수 있습니다. Deadlock 이란, 2개 이상의 프로세스들이 서로의 작업이 끝나기만을 기다려 결과적으로 모든 프로세스가 무한히 대기하게 되는 현상을 말합니다. 

 

예를 들어 상황을 설명해보겠습니다. 

Semaphore 변수 S = 1 과 Q = 1이 존재하고, 프로세스 P0과 프로세스 P1이 다음과 같이 이루어져 있습니다.

 

 

먼저 P0가 스케줄링 되면, wait(S)를 수행하여 Semaphore 변수 S는 0으로 변경됩니다. 이후 바로 context switching이 일어나 P1이 스케줄링 되면, wait(Q)를 수행하여 Semaphore 변수 Q도 0으로 변경됩니다. 다시 P0가 스케줄링이 되어 wait(Q)를 실행할 때, Q는 P1에 의해 점유 되었으므로 P0는 P1의 시그널을 대기하다가 context switching이 일어나게 될 것 입니다. 다시 P1이 스케줄링 되어 wait(S)를 실행할 때, S는 P0에 의해 점유 되었으므로 P1은 P0의 시그널을 대기하다가 context switching이 일어나게 됩니다. 결국에는 서로가 서로의 자원을 대기하고 있는 상황이 지속되어 무한정 대기 상태인 Deadlock에 빠지게 됩니다.

 

 

Deadlock의 발생 조건 4가지

 

데드락은 다음의 4가지 조건이 동시에 만족할 때 발생합니다.

 

1) Mutual Exclustion(상호 배제): 어떠한 프로세스가 자원을 사용하고 있을 때 다른 프로세스는 사용할 수 없도록 차단 하는 것

2) Hold and Wait(점유 대기): 프로세스가 최소 하나 이상의 자원을 점유하면서 다른 프로세스가 사용하고 있는 다른 자원을 대기 하는 것

3) No preemtive(비선점): 자원은 프로세스가 작업을 모두 끝내고 자발적으로 내려놓을 때까지 강제적으로 해제될 수 없는 것

4) Circular wait(순환 대기): 프로세스 { P0, P1, ..., Pn }에 대하여 P0은 P1이 사용하고 있는 자원을 대기하고, P1은 P2가 사용하고 있는 자원을 대기하고, ..., Pn은 P0가 사용하고 있는 자원을 대기하고 있는 것