[운영체제(OS)] 데드락(DeadLock), 교착상태 란? - 1

저번 포스팅에서는 동기화 이슈, 임계 구역(critical section)에 대해서 알아보고, 해결할 수 있는 방법들에서 대해서 알아보았습니다.

 

이번 시간에는 동기화 이슈처럼 비슷하게 공유 자원이 한정되어 있을 경우, 이 자원을 사용하고 싶은 프로세스들이 여러 개 있을 때 발생하게 되는 교착 상태, 데드락(Dead lock)에 대해서 정리해보려고 합니다.

 

 

0. 데드락(Dead lock), 교착 상태란?

 

교착 상태를 직관적으로 이해해보면 위 사진처럼 자동차 여러 대가 혼잡한 상황에서 먼저 가겠다고 양보하지 않고 직진만 하고 있는 상황이라고 할 수 있습니다. 생각만 해도 아찔하죠.

 

그렇다면 정의를 한번 볼까요?

 

In an operating system, a deadlock occurs when a process or thread enters a waiting state because a requested system resource is held by another waiting process, which in turn is waiting for another resource held by another waiting process.

 

정리해보면, deadlock 은 하나의 자원을 점유하기 위해 경쟁하는 여러 프로세스로 인해 발생합니다. 

 

운영체제에서 대부분의 교착 상태는 전용 자원 즉, 세마포어를 차지하려는 경쟁에서 발생합니다. 여기서 세마포어는 '일정 시간 동안 여러 프로세스에서 사용할 수는 있지만 한 순간으로만 본다면 한 프로세스만 사용 가능한 자원' 이죠. 특히 멀티 쓰레드를 사용하는 개발자들을 항상 데드락을 염두해야만 합니다. 

 

이제 예시를 보면서 데드락을 이해해보겠습니다.

 

 

R1, R2는 자원이고 P1, P2는 자원을 활용해서 일을 처리하는 프로세스라고 가정해보겠습니다.

 

P1은 R1에 세마포어를 가진 상태에서 인터럽트가 걸립니다. 그럼 P2로 context switch가 발생하겠죠? 그럼 P1은 wait 상태가 됩니다.

P2가 R2에 세마포어를 걸어서 확보한 후, R1을 가지려고 봤더니 P1 이 자원을 놓아줄 때까지 기다려야 하는 상황입니다.

이런 식으로 P2가 실행되려면 R1이 있어야 하는데 또 R1을 가지려니까 P1이 놓아주어야 하고, P1은 P2가 붙잡고 있는 R2가 필요한 악순환이 반복되면 P1, P2는 서로가 가지고 있는 자원만을 기다리게 되는, deadlock에 빠져서 풀리지 않게 됩니다.

 

다시 한번 정리해보면, 데드락(교착상태)이란 여러 개의 프로세스가 더 이상 진행될 수 없는 자원의 할당, 해제 과정을 기다리고 있는 상태입니다. 

 

1. 그렇다면 데드락은 언제 발생할까요?

 

지금까지 데드락이 무엇인지에 대해서 살펴봤습니다. 그렇다면 데드락이 언제 발생하는지 어떤 경우에 발생하는지 알아보도록 하겠습니다.

데드락이 발생하기 위해서는 아래 4가지 조건이 모두 갖춰져야 합니다.(하지만 4가지 조건이 모두 맞았다고 무조건 데드락이 발생하는 것은 아니죠.)

 

 

하나 씩 살펴보겠습니다.

 

1. Mutual Exclusion - 상호 배제

 

상호 배제는 서로를 배제한다! 라는 의미로 남한테 주지 않고 나만 쓴다는 의미입니다. 당연한 얘기겠지만 나만 쓸 거야!라고 해야 데드락이 발생하겠죠? 정리해보면 한 프로세스가 자원을 점유하고 있으면, 다른 프로세스들은 자원 사용이 불가능합니다. 한 번에 한 프로세스만 자원을 사용할 수 있죠.

 

2. Hold and wait - 점유와 대기

 

자신은 이미 자원을 점유하고 있는 상태에서 다른 종류의 자원을 추가적으로 요구한다는 의미입니다.

 

이것도 당연한 얘기겠지만 어떤 프로세스가 공유된 자원을 가지고 있는 상황에서 다른 자원을 또 요구하면 데드락이 발생하겠죠? 

3. No preemption - 비선점

 

preemption? 어디서들어봤는데? 맞습니다. CPU 스케쥴링에서 preemptive, no preemptive의 개념에 대해서 알아봤었는데요.
preemptive는 선점이라는 의미였습니다. 사용권을 빼앗아서 사용할 수 있는 방식이었죠. No preemptive는 말 그대로 '선점이 없다'

즉, 강제로 자원을 사용할 수 있는 권한을 빼앗을 수 없다 라는 의미죠.

 

4. Circular wait - 원형 대기

 

프로세스와 자원들이 Cirular, 원형 모양을 이루고 각 프로세스는 자신에게 할당된 자원을 가지고, 상대방의 프로세스 자원을 양방향으로 요청하는 경우를 의미합니다. 

 

잘 생각해보면 프로세스와 자원들의 관계가 일직선일 때는 당연히 데드락이 발생하지 않습니다.

데드락은 서로가 서로에게 요구하면서 기다리는 상태라고 설명했었는데요, 일직선은 서로라는 단어와는 어울리지 않기 때문이죠.

 

 

 

2.마지막으로 사진 한장으로 데드락 발생 필수조건들을 정리해보겠습니다.

 

 

 

1. Mutual exclusion - 하나의 차량은 그 순간 한 자리에만 있겠죠? 

2. Hold and wait - 서로 구간을 차지하고 직진을 하기 위해서 기다리고 있습니다.

3. No preemption - 여기서 움직일 수도 없으니 당연히 양보를 할 수 없고 선점 또한 할 수없겠죠?

4. Circular wait - 4개의 교차로에서 서로 맞물려있는 Ciycle을 가지고 있습니다.

 

 

3. 정리

 

이번시간에는 데드락이 무엇인지, 데드락이 발생하기 위한 필수 조건들이 무엇인지 살펴봤습니다.

 

다음 포스팅에서는 데드락이 발생했을 때, 아니면 데드락이 발생하지 않기 위해서 어떻게 처리를 해줘야 하는지에 대한 해결방법에 대해서 알아보겠습니다.

 

감사합니다.