[운영체제] Ch13. 교착 상태(데드락)에 대응하는 방법

교착 상태에 대하여

1. 교착 상태(데드락)란? ft.식사하는 철학자 문제
2. 교착 상태 발생 조건 4가지
3. 교착 상태 해결 방법 - 예방, 회피, 회복

 

---

 

1.  교착 상태(데드락)란? ft. 식사하는 철학자 문제

프로세스 실행 과정에서 발생하는 문제 중 교착 상태 또는 데드락(Dead Lock)이라고 불리는 문제가 있다.

◈  식사하는 철학자 문제

식사하는 철학자 문제는 교착 상태를 설명하기 위한 고전적인 문제이다. 동그란 원탁에는 다섯 명의 철학자가 앉아있고, 모든 철학자의 앞에는 각각 음식 접시가 놓여있다. 그리고 식사를 하기 위한 포크는 철학자 사이에 하나씩 총 5개의 포크가 놓여있다.

https://velog.io/@oeckikek/Deadlock

만약 포크 두 개가 있어야 먹을 수 있는 식사이고, 철학자들은 아래와 같이 식사를 한다고 하자.

① 철학자들은 계속 생각을 하다가 왼쪽 포크가 사용 가능하면 집어든다.
② 철학자들은 계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어든다.
③ 양쪽 포크를 모두 집어 들면 정해진 시간 동안 식사를 한다.
④ 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.
⑤ 오른쪽 포크를 내려놓았다면 왼쪽 포크도 내려놓는다.
⑥ 다시 ①로 돌아간다.

①번을 모든 철학자가 동시에 실행하여 각자 자신의 왼쪽에 있는 포크를 집어 들었다면, 오른쪽에 포크가 남아있는 철학자는 아무도 남지 않는다. 그러면 모든 철학자는 자신의 오른쪽 철학자가 포크를 내려놓을 때까지 집어든 왼쪽 포크를 내려놓지 않을 것이고, 그렇게 일어나지 않을 사건을 기다리면서 진행이 멈춘 현상을 교착 상태라고 한다.

 

◈  교착 상태를 표현하는 자원 할당 그래프

교착 상태는 자원 할당 그래프(resource-allocation graph)를 통해 단순하게 표현할 수 있다.

① 프로세스는 원으로, 자원의 종류는 사각형으로 표현한다.

② 사용할 수 있는 자원의 개수는 사각형 안에 점의 개수로 표현한다.

③ 프로세스가 어떤 자원을 할당받아 사용 중이라면, 자원에서 프로세스를 향해 화살표로 표시한다.

④ 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표로 표시한다.

 

이 방법으로 '식사하는 철학자 문제'를 표현하면 아래와 같다.

 

 

 

2.  교착 상태 발생 조건 4가지

상호 배제, 점유와 대기, 비선점 및 원형 대기의 4가지 조건이 모두 만족되면 교착 상태가 발생할 가능성이 생긴다.

[1] 상호 배제

공유하는 한 자원을 한 번에 하나의 프로세스만 사용할 수 있었기 때문에 교착 상태가 발생했다고 할 수 있다. 즉, 상호 배제 상황에서 교착 상태가 발생할 수 있다.

[2] 점유와 대기

포크라는 자원을 들고 내려놓지 않은(점유) 상태에서 무작정 기다렸기 때문에 누구도 식사를 이어나갈 수 없었다. 다시 말해 자원을 할당받은 상태에서 다른 자원을 할당받기 기다리는 상태가 교착 상태의 원인이라고 볼 수 있다.

[3] 비선점

만약 철학자 중 누군가가 다른 철학자의 포크를 강제로 빼앗았다면 교착 상태가 발생하지 않을 수 있었을 것이다. 이렇게 자원을 비선점(nonpreemptive)하고 누구도 빼앗지 않았기 때문에 교착 상태가 발생한 것이라고 볼 수 있다.

[4] 원형 대기

프로세스와 프로세스가 요청하거나 할당받은 자원이 원의 형태를 이루었기 때문에 교착 상태가 발생했다고 볼 수 있다. 이렇게 원의 형태로 자원을 대기하는 것을 원형 대기라고 한다.

 

3.  교착 상태 해결 방법 - 예방, 회피, 회복

[1] 교착 상태 예방

상호 배제, 점유와 대기, 비선점, 원형 대기 중 하나라도 없애서 교착 상태를 예방하는 방법을 생각해 볼 수 있다.

① 우선 상호 배제는 현실적으로 없애기 어렵다.

② 점유와 대기를 없애면 특정 프로세스에 자원을 모두 할당하거나 아예 할당하지 않는 식으로 배분할 수 있는데, 이때 자원 활용률이 낮아질 수 있고, 기아 현상이 발생할 우려가 있다. 

③ 만약 비선점 조건을 없애면 이용 중인 프로세스로부터 자원을 빼앗아 교착 상태로부터 벗어날 수 있지만, 자원을 선점한 프로세스가 끝날 때까지 다른 프로세스가 기다려줘야 하는 경우가 있기 때문에 범용성이 떨어진다.

④ 마지막으로 원형 대기 조건을 없애는 방법은 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하는 방식처럼 간단하다. 하지만 수많은 자원을 모두 이러한 방식으로 관리하는 것은 간단하지 않고, 자원에 번호를 붙이는 방식에 따라 자원 활용률이 떨어질 수 있다.

결론적으로 교착 상태를 예방하는 간단하고 문제가 없는 좋은 방법은 없다.

[2] 교착 상태 회피

두 번째 방법은 교착 상태를 회피하는 것으로, 무분별한 자원 할당이 문제의 원인으로 보고 자원을 조금씩만 할당하는 방법이다. 교착 상태가 발생하지 않는 수준의 상태를 안전 상태(safe state)라고 하고, 교착 상태가 발생할 수도 있는 상황을 불안전 상태(unsafe state)라고 한다. 이 기준은 안전 순서열(safe sequence)라고 부르는 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서가 있는지에 따라 판단한다.

[3] 교착 상태 검출 후 회복

만약 이미 교착 상태가 벌어졌다면, 이를 해결하는 방법이 있다.

① 선점을 통한 회복

교착 상태가 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗아 한 프로세스씩 자원을 몰아주어(선점) 해결하는 방법이 있다.

② 프로세스 강제 종료를 통한 회복

가장 단순하면서 확실한 방법으로는 교착 상태가 없어질 때까지 교착 상태에 놓인 모든 프로세스 전체 또는 하나씩 강제로 종료하는 방법이다. 단, 전체를 종료할 경우엔 많은 작업 내역을 잃는다는 단점이, 하나씩 종료할 경우엔 교착 상태가 없어졌는지 확인하는 과정에서 오버헤드를 야기한다는 단점이 있다.

③ 타조 알고리즘 

교착 상태를 완전히 무시하는 방법으로 타조 알고리즘(orstrich algorithm)이 있다. 문제의 발생 빈도나 심각성에 따라 최대 효율을 추구하는 엔지니어 입장에서는 이 방법이 적합할 때도 많다.