데드락(Deadlock)
프로세스 실행과정에 발생할 수 있는 정체상황
프로세스들은 순서를 기다리다 기다리는 대상이 꼬꼬물(꼬리에꼬리물기)해서 아무도 작업을 진행하지 못하는 상태가 종종 발생하는데 이것을 데드락이라고 함.
데드락이 발생하는 이유는 공유자원 때문 !
<데드락의 네 가지 조건>
데드락은 다음 네 가지 조건이 모두 만족되는 경우에만 발생할 수 있음.
but 모두 만족한다고 무조건 발생하는 것이 아니라 발생할 수도 있다 라는 것임.
-
상호배제(Mutual exclusion)
어떤 프로세스가 공유자원을 사용중이라면 해당 공유자원은 다른 프로세스가 접근 할 수 없어야 함 -
비선점(No preemption)
어떤 프로세스가 공유자원을 가지고 있을 때 다른 프로세스가 그 공유자원을 빼앗을 수 없어야 함(선점 X) -
점유 및 대기(Hold and wait)
어떤 프로세스가 공유자원을 가지고 있는 상태일 때 다른 프로세스가 그 공유자원을 사용하기 위해 기다리고 있는 상태에 있어야함 -
원형 대기(Circular waite)
점유 및 대기를 하는 프로세스들의 관계가 꼬꼬물해서 둥글게 형성되어있는 상황이어야 발생 할 수 있음일일과제
데드락, 즉 교착상태에 대해서 비유적으로 설명할 때 주로 사용되는 예시로
'식사하는 철학자 문제'라는 것이 있다.
이에 대해 조사하고 정리하는 글을 써보자.식사하는 철학자 문제
5명의 철학자가 원탁에 앉아서 식사를 한다. 철학자들 사이에는 젓가락이 하나씩 놓여 있고, 철학자들은 다음의 과정을 통해 식사를 한다.
- 일정 시간 생각을 한다.
- 왼쪽 전가락이 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
- 오른쪽 젓가락이 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
- 젓가락 한 쌍을 얻었다면 일정 시간만큼 식사를 한다.
- 오른쪽 젓가락을 내려놓는다.
- 왼쪽 젓가락을 내려놓는다.
- 다시 1번으로 돌아간다.
간단하게 생각해, 만약 모든 철학자들이 동시에 자신의 왼쪽 젓가락을 잡는다면, 모든 철학자들이 자기 오른쪽의 젓가락이 사용 가능해질 때까지 기다려야 한다. 그런데 모든 철학자들이 그러고 있다. 이 상태에서는 모든 철학자가 영원히 3번 상태에 머물러있어 아무것도 진행할 수가 없게 되는데, 이것이 교착(Deadlock)상태이다.
- 교착상태(Deadlock) - 모두 식사를 하지 못하기 때문에 젓가락을 내려놓을 일이 없고, 3번 과정으로 넘어가지 못하기 때문이다.
- 기아현상(starvation) - 이러한 상황이 지속된다면 철학자들 모두 굶어죽고 말 것이다.
해당 문제는 OS의 Deadlock, Starvation을 설명하기 위한 상황으로 비유한 대상은 아래와 같다.
- 젓가락 -> 자원(Resource)
- 철학자 -> Process(or Thread)
- 젓가락 한 쌍(2개) -> Process가 필요한 자원의 수
*[데드락 발생 규칙 4가지]
- Mutual exclusion : 다른 철학자가 사용 중인 젓가락을 서로 공유하며 사용할 수 없습니다.
- Hold and wait : 철학자가 젓가락(자원) 1개를 가지고 있는 상태에서, 다른 철학자가 사용 중인 젓가락을 요청합니다.
- No preemtion : 규칙상 다른 철학자가 가지고 있는 젓가락을 함부로 빼앗거나 선점할 수 없습니다.
- Circular wait : 철학자들이 서로 꼬리에 꼬리를 무는 형태로 젓가락을 기다리고 있습니다.
=> 따라서, 철학자들은 현재 Deadlock에 걸린 상황이며 더 이상 식사를 진행하지 못하고 있고
뿐만 아니라, 젓가락(자원)을 요청하고 있으나, 계속해서 할당받지 못하는 상황인 Starvation까지 발생한 상황이다.
문제 해결 방법
방법1. 젓가락 개수 늘리기
젓가락 개수를 5개에서 6개로 늘려 최악의 경우 5명이 젓가락을 하나씩 집어도 1명은 2개의 젓가락으로 식사를 마치고 이 과정을 반복한다.
방법2. 철학자 위치 구분(홀짝)
- 홀수 번 철학자, 짝수 번 철학자를 구분한다.
- 홀수 번 철학자 인 경우는 젓가락을 왼쪽, 오른쪽 순으로 집어서 밥을 먹고 젓가락을 왼쪽, 오른쪽 순으로 놓는다.
- 짝수 번 철학자인 경우는 젓가락을 오른쪽, 왼쪽 순으로 집어서 밥을 먹고 젓가락을 오른쪽, 왼쪽 순으로 놓는다.
- 교착상태의 4가지 필요조건 중 '원형대기'를 해결하여 이 문제를 해결한다.
방법3. 철학자 5명이 앉을 수 있는 테이블에 최대 4명만 앉을 수 있도록 허용한다.
만약 5좌석에서 4명만 앉힐 수 있도록 허용한다면, 3명이 젓가락을 한 개씩 가지고 있다고 하더라도 최소한 나머지 1명은 젓가락을 2개 얻을 수 있으므로 식사가 가능하다.
따라서 1명이 식사를 마치면, 언젠가는 다른 철학자들도 식사를 할 수 있으므로 Deadlock 발생 상황을 배제할 수 있다.
