[OS] Process 동기화 (3) Deadlock

[OS] Process 동기화 (3)

Deadlock란, 프로세스에 자원이 잘못 분배되었을 때 일어난다. 간단히 말하자면, 만약 한 프로세스가 자원 A를 가지면서 자원 B를 요구한다고 가정해보자. 이 상태에서 다른 프로세스가 자원 B를 가지고 있으면서 A를 요구하고 있는 상황이라면 이도저도 못하는 상태가 되어 버린다. 이를 deadlock이라고 한다.

교착상태에 빠지는 조건은 총 4가지가 있다. 이 4가지 조건을 모두 만족할때 교착상태에 빠지게 된다.
1. Mutual Exclusion (상호배제) : 한번에 오직 하나의 프로세스가 하나의 자원만 사용
2. Hold and Wait (점유하고 대기): 자원을 할당받은 상태에서 다른 프로세스가 사용중인 자원을 추가로 얻기 위해 기다리는 경우
3. No Preemption (비선점): 자원이 강제적으로 반납될 수 없고, 작업중인 프로세스가 끝난뒤에야 자원을 반납 받음
4. Circular Wait (순환대기): 여러 프로세스 p0, p1, p2... pn이 있을 때, p0는 p1이 사용중인 자원을 요구하고, p1은 p2가 사용중인 자원을 요구,...pn은 p0가 사용중인 자원을 요구하는 경우, 즉 순환 형태를 보이는 경우
위의 4가지 조건을 저번 포스팅에서 언급한 식사하는 철학자 문제에 대입해서 생각해보자.
1. Mutual Exclusion: 한 철학자가 젓가락을 사용하고 있으면 다른 철학자는 이 젓가락을 사용할 수 없다.
2. Hold and Wait: 철학자는 왼쪽 젓가락을 가지고 있는 상태에서 오른쪽 젓가락을 집기 위해 대기한다.
3. No Preemption: 한 철학자가 젓가락을 집은 상태에서 다른 철학자가 이 젓가락을 강제로 뺏을 순 없다.
4. Circular Wait: 모든 철학자는 왼쪽 젓가락부터 집을 수 있다.

간단한 용어를 정의해보자. 자원을 resource라고 하고, 자원 하나하나를 instance라고 하고, process는 instance을 요청(request)하고 사용(use)하고 반납(release)한다.
자원 할당 그래프는 어떤 resource가 어떤 process에 할당되었는지, 또는 어느 process가 어느 resource를 할당 받으려고 기다리는지를 그림으로 나타낸 것이다.
1. Resource: 사각형
2. Instance: 점
3. Process: 원
4. Request, Allocation: 화살표

Deadlock을 방지하는 방법은 위의 4가지 필요조건 중에서 최소 한가지를 만족시키지 않도록 만드는 것이다.
1. Mutual Exclusion: 자원을 공유하게 만듬. 현실적으로 불가능
2. Hold and Wait: 자원을 가지고 있는 상태에서 다른 자원을 기다리지 않도록 만듬. 만약 여러 개의 자원이 필요하면 필요한 모든 자원을 얻을 수 있는 경우에만 해당 자원을 요청. 필요한 자원 중 일부만 가지고 있는 경우 할당받은 자원을 모두 운영체제에 반납. 활용률 저하 및 starvation 현상 발생하는 단점
3. No Preemption: 선점이 가능하게 바꾼다. 현실적으로 불가능.
4. Circular Wait: 자원의 활용률 저하

Deadlock 회피에서는 deadlock을 자원 요청에 대한 잘못된 승인으로 판단한다.
Deadlock 회피에서는 안전한 할당 (Safe allocation)과 불안정한 할당 (Unsafe allocation) 두가지로 나누는데, 불안전한 할당의 경우 교착상태에 빠지게 된다.

방지와 회피는 사전에 교착상태를 일어나지 않게 하는 방법이지만 검출 및 복구는 교착상태가 일어나는 것을 허용하고, 그 대신에 일어났을 때 이를 인지하고 복구를 하는데 집중한다.
교착상태에 일어나는 것을 감지하기 위해 운영체제 내부에서 주기적으로 교착상태 발생 여부를 검사해야 하는데 주기가 짧으면 오버헤드가 크고, 주기가 길면 오버헤드는 줄지만 복구 가능성이 낮아진다.
검출 및 복구는 복구를 제대로 하지 못할 수도 있고, 검출을 위해 추가적인 오버헤드가 발생한다는 단점이 있다.

728x90