목차
📁 Deadlock 발생 조건
Deadlock이란 두 개 이상의 프로세스들이 절대로 발생할 수 없는 이벤트를 무한정 기다리는 상황이다.
위 그림은 deadlock이 발생하지 않는 프로그램이다.
데드락은 어떤 프로세스가 어떤 리소스를 가지고 있는 상태에서 다른 프로세스가 가진 리소스를 요청할 때 발생하는 것인데, 위 프로그램은 리소스 A를 가진 상태에서 A를 다 쓰고 놓은 후 B라는 리소스를 요청하고 다 쓰고 놓는 방식으로 동작한다.
즉 P는 데드락이 발생하지 않는 프로그램이고, Q는 발생할 가능성이 있는 프로그램이다.
하지만 데드락이 발생하려면 P와 Q 둘 다 서로 리소스 하나를 가진 상태에서 다른 프로세스가 가진 것을 요청해야하는데, Q는 그렇게 동작하지만 P는 그렇지 않으므로 P와 Q 사이에는 데드락이 발생하지 않는다.
컴퓨터 시스템 자원은 두 가지 타입으로 분류된다.
1. reusable resources
재사용 가능한 자원.
프로세스가 자원을 사용한다고 해서 없어지는 것이 아니고, 사용 후 반환하면 그 자원을 다른 프로세스가 배정받아 또 사용할 수 있다.
예를 들면 cpu, I/O장치, 메모리 등 대부분의 하드웨어 자원은 reusable resources이다.
이런 자원들에 대해 deadlock이 발생할 가능성이 있다.
2. consumable resources.
소비성 자원.
어느 프로세스가 자원을 한번 사용하면 없어져서 다른 프로세스에 의해서 다시 사용할 수 없는 것.
이런 자원에 대해서도 deadlock이 발생할 수도 있음.
📝 Deadlock Example : Reusable Resources
프로세스 p1, p2가 있고 컴퓨터 시스템에 200Kbytes의 메모리가 있다고 가정하자.
p1이 먼저 실행돼서 200Kbytes중 80Kbytes를 운영체제에게 할당해달라고 요청하여 사용중이다.
이때 남은 메모리는 120Kbytes이다. 이 상태로 cpu가 p2로 넘어갔다.
p2는 70Kbytes를 요청해서 50Kbytes가 남았다.
이후 p2가 80Kbytes를 요청할때, 50Kbytes밖에 남지 않아서 줄 수가 없다.
그러면 운영체제는 p2를 block 상태로 바꾸고 cpu를 뺏어 다른 프로세스에게 준다.
이후 언젠가 p1에게 cpu가 왔을때, p1가 60Kbytes를 요청한다. 하지만 이번에도 줄 수가 없기 때문에 p2가 끝나 70Kbytes를 내놓아야지만 p1이 실행 가능해진다.
하지만 p2가 이미 block상태에 가서 cpu를 뺏겼기 때문에 p2가 실행될 방법이 없다.
결국 p1도 block이 된다.
이렇게 되면 p1의 80Kbytes, p2의 70Kbytes의 컴퓨팅 리소스는 다른 프로세스에 의해 사용되지 못하고 deadlock에 의해 잠겨버린다.
위와 같이 deadlock이 발생하면 두 프로세스뿐만아니라 다른 프로세스도 deadlock에 의해 점유된 컴퓨팅자원을 사용할 수 없기 때문에 영향이 큰 것이다.
📝 Deadlock Example : Consumable Resources
p1과 p2가 메세지를 주고 받는다고 하자.
메세지는 수신하는 프로세스가 receive하면 없어지는 소비성 자원이다.
Receive(P2)란 P2로부터 메세지를 받는다는 뜻이다.
그림을 보면, p1은 p2의 메세지를 기다리며 block상태에서 기다린다.
그런데 p2도 p1의 메세지를 기다리고 있다.
서로 상대방이 먼저 메세지를 보내기를 기다리면서 sleep인 상태인것이다.
위 예시는 비교적 쉽게 오류를 찾아낼 수 있다.
📁 Deadlock 시각적 표현
Resource Allocation Graphs : deadlock을 시각적으로 표현하기 위한 그래프.
프로세스를 원형, 컴퓨팅 자원을 사각형으로 표시하고, 사각형 내의 검은 점은 Ra라고하는 타입의 자원의 개수를 나타낸다.
프로세스에서 자원쪽으로 향하는 화살표는 자원을 요청한다는 뜻이고, 자원으로부터 프로세스로 향하는 화살표는 자원이 할당되었다는 뜻이다.
즉 위와 같은 그래프는 Ra 자원이 p1에게 할당되어서 p1이 사용중이라는 뜻이다.
위 그래프에서 왼쪽은 deadlock이 발생하는 경우이고 오른쪽은 발생하지 않는 경우이다.
만약 오른쪽 그래프에서 Rb가 하나밖에 없다고 하더라도 deadlock은 발생하지 않는다.
p2는 Ra를 가진 상태에서 Rb를 요청했는데, Rb는 하나밖에 없고 p1이 사용중이므로 p2는 block상태가 된다.
하지만 p1은 실행가능하므로 Ra, Rb 자원을 갖고 실행하면서 언젠가는 실행을 끝내고 Ra와 Rb 자원을 놓을 것이다.
이후 block에서 p2가 깨어나게되면 Rb를 사용할 수 있는 것이다.
📁 Deadlock이 생기는 네가지 조건
1. Mutal exclusion
deadlock이 발생하는 상황에서 자원을 할당받은 프로세스는 그 자원을 독점적으로 사용해야한다.
만약 자원을 다른 프로세스와 함께 사용한다면 deadlock이 발생하지 않을 것이다.
2. Hold and wait
deadlock에 개입된 프로세스가 어떤 자원을 가진 상태에서 다른 자원을 요청해야 한다.
3. No preemption
preemption이란 자신이 원하는 자원이 다른 프로세스에 의해 이미 할당된 경우 자신에게 우선권이 있다고 주장하면서 강제로 뺏어오는 것을 말한다.
즉 deadlock이 발생하기 위해서는 만약 p1이 Ra자원을 사용하고 있으면 p2가 강제로 뺏어올 수 없고 기다려야한다.
4. Circular wait
hold and wait 성질이 deadlock에 개입된 모든 프로세스에게 전부 성립될 때 circular wait가 생긴다.
다음 그림과 같이 프로세스들이 꼬리를 물듯 서로 다른 프로세스의 자원을 기다리는 상황을 말한다.
위 그림은 네가지 성질을 모두 만족하고 있다.
p1, p2, p3, p4가 모두 hold and wait를 하고있어 circular wait 성질이 있다.
각자 ra는 p1, rb는 p2 등 각 자원이 프로세스 하나씩에만 사용되므로 mutual exclusion 성질이 있다.
모든 프로세스가 요청한 자원에 대해 wait중이기 때문에 no preemption 성질이 있다.
