교착 상태(Dead Lock)

< 교착 상태(Dead Lock) ? >

컴퓨터 시스템에서 프로세스(일련의 명령어로 구성된 작업)를 실행하려면 여러 가지 리소스(메모리, CPU 시간, 디스크 공간 등)가 필요하다. 시스템은 이러한 리소스를 프로세스에 순차적으로 할당하며, 프로세스가 작업을 완료하면 사용한 리소스는 시스템에 다시 반납된다.

그러나 여러 프로세스가 동시에 실행되는 시스템에서는 복잡한 상황이 발생할 수 있다. 이를 이해하기 위해 간단한 예시로, 세 가지 프로세스 P1, P2, P3와 세 가지 리소스 R1, R2, R3이 있다고 가정해보자. 이 시점에서 각각의 프로세스는 이미 하나의 리소스를 할당 받았다고 가정하자: P1은 R1, P2는 R2, P3는 R3을 갖고 있다고 가정.

그런데 이후에 추가적인 리소스를 필요로 하는 상황이 발생하였다. P1이 R2를 필요로 하고, P2가 R3를 필요로 하며, 마지막으로 P3는 R1을 필요로 하게되었다.

문제는 이제 각 프로세스가 필요로 하는 리소스가 이미 다른 프로세스에게 할당되어 있어서 사용할 수 없는 상황이다. 따라서, 모든 프로세스들은 각자 필요한 리소스가 반납될 때까지 대기 상태에 빠지게 되며, 이는 데드락이라는 현상으로 이어져버린다. 데드락은 프로세스들이 더 이상 진행할 수 없는 상태로, 시스템 성능에 심각한 영향을 미치게 된다.

교착 상태를 표현한 상황, P1 프로세스는 R2자원이 끝나길 기다리고 있고, P2 프로세스는 자원 R2를 할당 받은 채 R3의 자원이 끝나길 기다리는 상황

 

< 데드락 발생 조건 >

데드락이 발생하려면 아래와 같은 네 가지 조건이 만족되어야 한다.

Mutual Exclusion (상호 배제) : 리소스는 한 번에 한 프로세스만 사용할 수 있다.
Hold and Wait (점유와 대기) : 프로세스는 이미 할당된 리소스를 가진 상태에서 다른 리소스를 기다린다.
No Preemption (비선점) : 한 프로세스가 이미 점유하고 있는 리소스를 다른 프로세스가 강제로 빼앗을 수 없다.
Circular Wait (원형 대기) : 프로세스 A, B, C가 있을 때 A는 B가 가진 리소스를, B는 C가 가진 리소스를, C는 A가 가진 리소스를 기다리는 상황을 말한다.

 

프로세스 간의 관계를 그래프로 도식화해 보면 데드락이 발생할지 예상할 수 있다. 이 그래프를 Resource-Allocation Graph(자원 할당 그래프)라고 한다. 예시를 하나 살펴보자.

R은 자원이고 P는 프로세스를 의미한다. 자원 내의 동그라미는 자원(인스턴스)의 개수이다. 

자원 → 프로세스로 향하는 간선은 해당 자원을 프로세스가 보유 중(Allocate)이라는 의미이고, 프로세스 → 자원으로 향하는 간선은 프로세스가 해당 자원을 요청(Request)했다는 의미이다. 

만약 그래프에 사이클(Cycle)이 없다면 Deadlock이 아니다. 반면, 사이클이 있다면 Deadlock이 발생할 '수' 있다. 

정확히 말하면, 자원당 하나의 인스턴스만 있는 경우엔 Deadlock이고, 여러 인스턴스가 존재하는 경우엔 Deadlock일 수도 있고 아닐 수도 있다. 
위의 그림에서는 왼쪽 그래프는 Deadlock이지만, 오른쪽 그래프는 Deadlock이 아니다. 

Deadlock문제를 해결하기 위한 방법으로는 대표적으로 미리 예방하는 방법(Prevention)과 Deadlock이 발생하지 않도록 피하는 방법(Avoidance), 그리고 발생했을 때 처리하는 방법(Detection and Recovery), 무시하는 방법(Ignorance) 총 네 방법으로 나뉜다. 

이 네 가지 조건 중에서 하나라도 만족되지 않으면 데드락은 발생하지 않는다.

< 데드락 해결 방법 >

그렇다면 이러한 데드락을 어떻게 해결할 수 있을까? 데드락을 처리하는 방법에는 크게 세 가지가 있다.

 

1.데드락 예방, 2. 데드락 회피,3. 데드락 복구가 있다.

[데드락 예방]
데드락 예방은 데드락 발생 조건 중 하나를 만족시키지 않도록 하여 데드락이 발생하지 않도록 하는 방법이다. 하지만 이 방법은 장치 효율과 시스템 성능을 떨어트릴 수 있다.

[데드락 회피]
데드락 회피는 데드락이 발생할 것 같을 때는 아예 리소스를 할당하지 않는 방법이다. 이 방법은 시스템 상태를 항상 안전한 상태로 유지하는 것이 중요하며, 리소스 할당 그래프를 통해 데드락 가능성을 판단한다. 만약 리소스 타입이 여러 개라면 은행원 알고리즘(Banker's Algorithm)을 사용한다.

[데드락 복구]
데드락 복구는 데드락이 발생한 후에 어떤 프로세스를 중단시킬지 결정하는 것이. 여기에는 프로세스의 중요도, 실행 시간, 사용 리소스 양, 필요 리소스 양 등 다양한 판단 기준이 있다.

[리소스 선점]
데드락을 해결하기 위해 리소스 선점 방식을 사용할 수도 있다. 하지만 이 경우 어떤 프로세스를 중단시킬지 결정하는 것이 중요하며, 데드락 발생 전 상태로 되돌리는 rollback 과정이 필요하다. 그리고 계속 같은 프로세스가 중단되는 starvation 문제를 피해야 한다.

 

 

Reference : https://www.javatpoint.com/os-deadlocks-introduction

What is Deadlock in Operating System (OS)? - javatpoint

https://parksb.github.io/article/11.html

🦕 공룡책으로 정리하는 운영체제 Ch.7: Deadlocks