운영체제가 하는 핵심적인 일은 프로세스 관리이고, 그 중에서도 CPU 스케줄링과 동기화(Synchronization)를 가장 중요하게 다루어야 한다. 동기화를 하다 보면 간혹 데드락에 빠지는 일이 있는데 데드락에 대해 알아보자.

1. 교착상태(Deadlock)

프로세스는 실행을 위해 여러 자원을 필요로 한다. (e.g. CPU, 메모리, 파일, 프린터, …)
그러나 프로세스가 필요로 하는 자원은 보통 하나이고, 프로세스들은 공통된 자원을 나누어 써야 하는 상황인 것이다. 이때 운영체제가 이 프로세스들에게 자원을 제대로 나누어 주지 못하면 교착상태(Deadlock)에 빠지게 된다.

e.g. 어떤 자원은 갖고 있으나 다른 자원은 갖지 못할 때(e.g. 다른 프로세스가 사용 중) 대기해야 할 때 교착상태에 빠지게 된다.

교착상태에 빠진다는 것은 다음의 네 가지 필요 조건을 모두 만족해야 일어날 수 있다.

• Mutual exclusion(상호배타): 하나의 프로세스가 자원을 점유 중일 때, 다른 프로세스는 해당 자원을 점유하지 못하는 것
• Hold and wait(보유 및 대기): 본인이 다른 자원을 보유하고 있으면서 다른 자원이 올 떄까지 대기하는 것
• No Preemption(비선점): 다른 프로세스가 점유하고 있는 자원을 빼앗지 못하는 것
• Circular wait(환형대기): 프로세스들이 자원을 기다리는 관계가 원형으로 연결된 상태
  • 프로세스 A → 프로세스 B가 점유한 자원 대기, 프로세스 B → 프로세스 C가 점유한 자원 대기, 프로세스 C → 프로세스 A가 점유한 자원 대기

정리하자면 교착상태는 결국 하드웨어 자원이 한정적으로 존재하기 때문에 발생한다고 볼 수 있다.

2. 자원(Resources)

프로세스가 자원을 사용하기 위해서는 OS에 요청(request)을 한다. OS는 요청이 올바를 경우 프로세스가 이를 사용(use)하게 한다. 자원을 다 쓰고 나면 OS에 해당 자원을 반납(release)한다.

2.1. 자원 할당도(Resource Allocation Graph)

자원 할당도는 컴퓨터에 어떤 자원이 있고 그 자원이 어떤 프로세스에 할당되었는지, 어떤 프로세스가 어떤 자원을 할당 받으려고 기다리고 있는지 시각적으로 표현하는 도구이다. 이를 통해 교착상태의 발생 여부를 판단할 수 있다.

동일 자원이 여러 개 있을 수 있다. 각각을 instance라고 한다.

자원은 사각형, 프로세스는 원, 할당은 화살표로 표시한다.

• 환형대기 x, 교착상태 x

• 식사하는 철학자 문제. 환형대기 o, 교착상태 가능성 o

3. 교착상태 처리

교착상태는 위에서 언급한 필요 조건들을 전부 만족했을 때 일어날 ‘수’ 있다.
즉, 컴퓨터에서 교착상태는 잘 일어나지 않는다. 하지만 그럼에도 발생하는 경우에는 어떻게 처리해야 할까?

3.1. 교착상태 방지(Deadlock Prevention)

교착상태는 필요 조건 4가지를 만족해야 일어날 가능성이 있다고 했다. 그렇다면 교착상태를 방지하기 위해서는 4가지 조건 중 한 가지 이상을 불만족하도록 만들면 된다.

3.1.1. 상호배타(Mutual exclusion)

위의 그림에서 자원은 2개의 instance를 가지고 있고, 각각 $P_1$, $P_2$에 할당되어 있다. 이때 $P_3$는 해당 자원을 가지지 못한다.

이를 해결하기 위해서는 해당 자원을 공유 가능하게 만드는 방법이 있다. 하지만 이는 원천적으로 불가능한 이야기이다. 식사하는 철학자 문제에서도 같은 오른쪽 젓가락을 두 명의 철학자가 동시에 사용하는 것이 불가능한 것을 생각해볼 수 있다.

3.1.2. 보유 및 대기(Hold & Wait)

보유 및 대기 조건을 불만족하기 위해서는 자원을 가지고 있으면서 다른 자원을 기다리지 않게 하면 된다.
예를 들어 일부 자원만이 사용 가능할 경우에는 보유하는 자원을 모두 놓아준다. 즉, 자원을 보유하지 않은 상태에서 필요한 모든 자원을 대기한다.

이는 starvation을 야기하고 자원 활용률이 저하되나, 3.1.1과 비교했을 때 현실적으로 사용할 수 있는 방법이다.

3.1.3. 비선점(No preemption)

다른 프로세스가 사용 중인 자원을 선점 가능하도록 하면 교착상태에 빠지지 않을 수 있다. 하지만 이 방법 또한 원천적으로 불가능하다. 예를 들어 다른 프로세스가 프린터를 사용 중인데 이를 강제로 빼앗아 사용하면 자료가 꼬일 수 있다.

CPU에서는 컨텍스트 스위칭을 강제로 하는 등 일부 가능은 하겠으나, 대부분의 경우 빼앗아 오는 것은 일반적으로 불가능하다.

3.1.4. 환형대기(Circular wait)

일반적으로 환형대기를 깨는 방법은 자원에 번호를 부여하고, 번호 오름차순으로 자원을 요청하는 것이다.

이는 대부분의 상황에 적용이 가능은 하겠으나, 실제 자원이 매우 많은 컴퓨터에 적용을 해보았을 때 자원 활용률이 굉장히 떨어지게 된다.

실제로 사용 가능한 방법은 3.1.2, 3.1.4 정도가 되겠다. 컴퓨터의 경우 교착상태가 발생하면 재부팅을 시도해볼 수 있지만, 항공선의 경우 재부팅 자체가 불가하다. 따라서 부득이하게 자원 활용률 및 기타 단점을 감수하고서라도 교착상태를 방지해야 하는 상황이 발생할 수 있다.

3.2. 교착상태 회피(Deadlock Avoidance)

데드락 발생 이유를 자원 요청에 대한 잘못된 승인이라고 생각한다. 아래 예제를 살펴 보자.

12개의 magnetic tape와 3개의 프로세스가 있다.

Current needs에 따라 자원을 나누어 주면 $12-(5+2+2)=3$이 된다. 이때 $P_0$는 Max needs에 따라 $5$만큼을 더 필요로 하지만 자원이 없어 실행되지 못한다. $P_2$는 $2$만큼을 더 필요로 하여 자원을 가져간 뒤, 프로세스를 종료하여 $4$만큼을 반납한다. ($3-2+4=5$)

$P_0$이 필요한 자원 $5$를 만족하게 되어 $P_0$는 $5$만큼 가져다가 쓰고 프로세스를 종료하고 $10$을 반납한다. ($5-5+10=10$) $P_2$역시 $7$만큼 가져다가 쓰고 프로세스를 종료하고 $9$를 반납한다.($10-7+9=12$)

이처럼 자원이 적절히 배분되어 프로세스가 전체적으로 돌아갈 수 있도록 자원 요청을 승인하는 것을 안전한 할당(safe allocation)이라고 한다. 여기서 $P_2$의 current needs가 $2$에서 $3$으로만 바뀌어도 교착상태에 빠지게 되며, 이를 불안전한 할당(Unsafe allocation)이라고 한다.

불안전한 할당은 곧 교착상태로 이어지기 때문에, OS는 자원을 요청받을 때 데드락이 일어나지 않도록 승인을 잘 해주어야 한다. 이는 마치 대출 전문 은행과 유사하다고 하여, Banker’s Algorithm이라고 한다.

3.3. 교착상태 검출 및 복구(Deadlock Detection & Recovery)

데드락이 일어나는 것을 허용은 하되, 이를 복구하도록 하는 방법이다.

운영체제가 처음부터 데드락이 일어나지 않도록 신경 쓰는 게 아니라, 프로세스가 필요한 대로 자원을 전부 나누어 준다. 이렇게 막 나누어 주다 보면 어쩌다 한 번 데드락이 일어날 수 있다.

이를 감지하기 위해 OS는 주기적으로 검사를 실행한다. 검사를 자주 실행해 혹시 모를 데드락을 대비하는 것도 좋겠으나, 검사를 위한 오버헤드가 크다는 문제가 있다.

데드락을 한 번 발견했다면, 복구를 위해 주기적으로 현재 상태를 기억해 두어야 한다. 데드락이 발생하기 이전 상태로 상황을 되돌려야 하기 때문이다. 이 방법이 불가능할 때에는 한 프로세스를 강제로 종료시키거나, 자원을 강제로 빼앗아(선점) 일부 프로세스에 할당한다.

3.4. 교착상태 무시(Don’t Care)

교착상태는 실제로 잘 일어나지 않는다. 앞서 언급한 바와 같이 4가지 필요 조건을 모두 만족하더라도 일어나지 않을 수 있다. 공연히 일어나지도 않을 일 때문에 detection하는 등의 방법은 오히려 컴퓨터 성능을 떨어뜨린다. 따라서 교착상태가 일어나도 아무런 조치를 하지 않는 것도 하나의 방법이라 할 수 있겠다.

Reference

• KOCW 양희재 운영체제
• 11: 교착 상태: Deadlock