오늘은 이전 포스팅들에서 간단히 언급되었던 Deadlock에 대해 다뤄보겠습니다.
Deadlock
데드락. 우리는 이 개념을 설명하기 위해 Starvation이라는 개념을 먼저 소개했었습니다.
Starvation은 프로세스가 critical section을 실행하려고 하는데, 다른 프로세스가 이미 critical section을 실행 중이여서 이를 위해 평소보다 오래 기다리는 상태를 의미합니다.
이에 확장 개념인 Deadlock은 Starvation이 영원히 지속되는 것을 의미합니다. 아래의 그림은 Deadlock을 아주 잘 나타내는 그림입니다.
데드락이 발생하는 경우
Reusable Resource 중 하나인 메모리의 할당량이 200Kb라고 해봅시다. P1, P2는 특정 용량만큼의 메모리를 요구하는 프로세스입니다.
P1부터 시작하여 80Kb를 할당 받습니다. 그러고 P2로 프로세스 스위치가 진행됩니다. 이 때, 메모리 잔여량은 120Kb입니다.
이후, P2가 70Kb를 할당받습니다. 메모리 잔여량은 50Kb가 됩니다. P2는 계속해서 자신의 instruction을 수행해나갑니다.
그러다가 80Kb의 메모리 할당을 요구했지만 메모리는 공간이 없으므로 처리할 수 없게 됩니다. 따라서 P2는 block 상태로 들어가게됩니다. 이에 따라 자연스레 P1으로 프로세스 스위치가 진행됩니다.
P1도 instruction을 쭉 수행하다가 60Kb를 요청하게 됩니다. 하지만 50Kb밖에 남지 않은 메모리는 해당 명령을 수행하지 못하게 되고 P1 또한 block 상태가 됩니다.
이렇게 결국 P1과 P2는 수행되지 못하지만 우리는 메모리 공간이 온전한 200Kb가 아닌, 50Kb가 됩니다. 왜냐하면 P1과 P2는 종료된 것이 아니라 Block 상태에 있기 때문이죠. 자신의 critical section을 수행하기를 기다리는 것이지 종료된 것이 아닙니다.
이러한 상태가 지속되면 우리는 메모리를 온전하게 사용하지 못하는 문제를 야기할 수 있습니다.
Deadlock의 발생 조건
우리는 데드락이 생기는 경우를 보다 쉽게 이해할 수 있도록 Resource Allocation Graph를 알아봅시다.
Resource Allocation Graph는 프로세스와 자원, 그 관계를 도식화한 것을 의미합니다. 아래처럼 쓰일 수 있습니다.
왼쪽은 프로세스 P1이 컴퓨팅 자원 R1를 사용하기 위해 request하는 것을 의미합니다.
오른쪽은 Ra의 컴퓨팅 자원을 P1이 사용한다는 것을 뜻합니다.
굉장히 직관적이죠?
이런 식의 시각화 기법을 이용해 Deadlock의 발생 조건을 확인해봅시다.
좌측처럼 Circular 하면서, 프로세스가 자원을 하나만 갖고 있다면 Deadlock이 발생합니다.
하지만 우측과 같이 자원이 여러개라면 Deadlock이 발생하지 않습니다.
따라서 우리는 아래와 같이 Deadlock의 발생 조건을 정리할 수 있습니다.
아래의 4가지 조건을 모두 만족할 때, Deadlock이 발생합니다.
1. Mutual Exclusion
컴퓨팅 자원이 한 개만 존재하고, 이러한 자원을 여러개의 프로세스에게 배정할 수 없을 때.
즉, 한 자원을 꼭 하나의 프로세스만이 사용할 수 있을 때를 의미합니다.
2. Hold-and-wait
프로세스가 하나의 자원을 가지고 있고, 다른 자원을 할당받기를 기다리는 상태를 말합니다.
3. No preemption
프로세스가 사용하려는 자원을 다른 프로세스가 사용 중일 때, 그것을 뺏을 수 없는 것을 의미합니다.
1번 조건과 비슷하다고 느껴질 수 있지만, 1번 조건은 컴퓨팅 자원에서의 권한이고 No preemption은 프로세스에서의 권한을 말합니다.
4. Circular wait
순환적인 구조를 가질 때를 의미합니다.
조금 더 자세하게는 hold-and-wait 성질이 Deadlock에 개입된 모든 프로세스에게 성립될 때를 의미합니다.
아래의 그림은 이러한 4가지 조건을 모두 갖춘 Resource Allocation Graph를 보여줍니다.
이번 글에서는 Deadlock이 발생하는 조건과 Deadlock이 무엇인지를 알아봤습니다. 다음 글에서는 이러한 Deadlock을 어떻게 해결할 수 있는지, 현재는 어떠한 방식으로 처리하고있는 지에 대해서 다뤄보겠습니다.
'CS > OS' 카테고리의 다른 글
| [운영체제] File (0) | 2023.10.28 |
|---|---|
| [운영체제] Deadlock 처리 (1) | 2023.10.21 |
| [운영체제] 6-3. Semaphore의 활용 (4) | 2023.10.12 |
| [운영체제] 6-2. Semaphore (4) | 2023.10.11 |
| [운영체제] 6-1. Testset Instruciton (2) | 2023.10.10 |