OS | 교착상태, 데드락

 

 

교착상태(데드락: dead lock)

 

 

교통체증인 모습

 

 

아침 8시, 9시와 저녁 6시 7시의 서울의 도로를 경험해 본 사람이라면 누구나 교통체증을 느꼈을 것입니다. 차가 빼곡히 줄지어가고, 기어가듯이 몇십분을 도로에서 시간을 허비하고 난 후에야 조금 뻥 뚫립니다. 심지어, 앞에 사고가 났을 경우에는 더 답이 없죠.

이와 같은 상황이 운영체제 내에서도 일어납니다.

 

여러 프로세스(2개 이상의 프로세스)가 서로 다른 프로세스의  작업의 종료만 기다리다가 아무도 아무것도 작업 진행을 못하는 상태를 교착상태라고 부릅니다. 교착상태는 공유자원 때문에 발생합니다.도로에서 왜  교통체증이 일어나는 것일까요? 바로 '도로를 차지하기 위해서'입니다. 집으로 가는 길에는 도로를 통해서 가야하고, 그 도로는 많은 차량들(프로세스들)이 원하고 써야만 하기에 막히는 것이죠. 프로세스도 마찬가지입니다. 여러 프로세스가 작업을 진행하다 보니 자연적으로 발생하는 일이지요. 

 

이 교착상태를 설명하는 유명한 예시가 있습니다. 바로 '식사하는 철학자'입니다.

 

원형탁자에 음식 3개가 있고, 자리도 3개, 식사를 할 철학자도 3명이 있습니다. 음식을 먹기 위해서는 각자 포크 2개씩(총 6개의 포크)을 써야 먹을 수 있는데 포크 마저도 3개 밖에 없죠. 모든 철학자가 식사를 하기 위해서는 한명이 먼저 먹고 다른 철학자는 고뇌하다가 먹고 난 후에 다음 철학자가 먹고 나머지는 고뇌, 마지막 철학자가 먹어야 합니다. 하지만 철학자 두명 혹은 세명이 자신의 포크를 양보하지 않는다면, 이 때 공유자원이던 '포크'가 사라지게 되어 교착상태가 일어납니다.

 

여기서 교착 상태가 발생하는 조건이 4가지가 있습니다. 이는 교착상태의 필요조건과 연관하여 서술하겠습니다.

 

---

 

교착상태의 조건 

 

교착상태의 필요조건은 4가지가 있습니다. 이 4가지 조건 중 단 하나도 성립하지 않으면 교착상태는 일어나지 않습니다. 

상호배제, 비선점, 점유&대기, 원형대기가 이 4가지 조건입니다. 

 

1.상호배제

 

한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 자원입니다. 자원은 임계구역으로 보호되기에 다른 프로세스가 동시에 사용할 수 없습니다. 즉, 자원은 공유가 되어야 하는데, 공유가 되지 않는 배타적인 자원을 사용하면 교착상태가 발생하는 것입니다.

 

 

식사하는 철학자) 철학자들이 서로 포크를 공유할 수 없는 상태입니다. 포크를 공유하지 못하면 영원히 밥은 못먹게 됩니다. 

 

2. 비선점

 

한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없어야 합니다. 빼앗을 수 없으면 공유도 안되므로 교착 상태가 발생합니다.

 

식사하는 철학자) 갹 철학자는 다른 철학자의 포크를 빼앗을 수 없습니다. 포크를 빼앗을 수 없으면 언제까지나 양보될 때 까지 기다려야 하므로 밥을 못먹습니다.

 

 

3. 점유&대기

 

프로세스가 자원을 할당받은 상태에서 다른 자원을 기다리는 상태에 문제가 생깁니다. 이러면 진행의 방향이 겹치거나 방해가 되므로 교착 상태가 발생합니다.

 

식사하는 철학자) 각 철학자는 왼쪽 포크를 잡은 채 오른쪽 포크를 기다립니다. 그러면 영원히 포크는 공유가 되지 않고 기다리는 상태만 반복되겠죠?

 

4. 원형 대기

 

점유와 대기를 하는 프로세스 관계가 원이 되는 상태. 특정 자원에 대한 점유아 대기는 자연스러운 일이지만, 점유와 대기가 원형이라면 서로 양보를 하지 않기 때문에 교착 상태가 됩니다.

 

식사하는 철학자) 포크를 원하는 방향이 원이라면 아무도 양보하지 않습니다. 철학자a는 포크 달라고 하고, b도 달라고 하고, c도 달라고 하는 상황인 것입니다.

 

 

 

이 네가지 조건이 지켜져야만, 교착 상태가 일어남에도 불구하고 교착 상태는 빈번하게 일어납니다. 교착 상태는 컴퓨터 자원에서 시스템 자원, 공유변수, 응용 프로그램 등에서 일어납니다. 운영체제가 상호 배제를 보장하기 위해 잠금을 사용하기 때문에 이런 상태로 빠지는 경우가 종종 생기는 것입니다.

그렇다면 이런 교착 상태들은 어떻게 해결해야 할까요?

 

---

 

교착 상태를 해결하는 방법

 

 

교착 상태를 해결하는 방법으로 예방, 회피, 검출, 회복이 있습니다.

 

해결하는 방법1. 예방

 

교착 상태의 문제점을 찾아 (상호배제, 비선점, 점유&대기, 원형대기) 이 문제점이 하나만 없어도 교착 상태가 일어나지 않기 때문에 하나라도 문제가 발생하지 않기 위해 예방하려 했으나 모두 효과가 없었습니다. 그래서 나온 것이 회피, 검출, 회복입니다.

 

먼저 교착 상태를 회피하는 것을 알아보겠습니다.

 

해결하는 방법2.회피

 

교착 상태를 회피하는 것은 할당되는 자원의 수를 조절하여 교착 상태를 아예 피하는 것입니다. 이는 유명한 은행원 알고리즘의 기본 개념입니다. 

 

은행원 알고리즘

 

 

은행원 알고리즘은 은행이 대출해주는 방식, 대출 금액이 안정상태이면 대출 승인이 나지만 그렇지 않다면 거부되는 것과 유사한 방식입니다. 

은행은 '돈'을 아무나한테 빌려주지 않습니다. 만약 아무에게나 빌려준다면, 갚아야 할 사람이 못갚는 상태에 갔을 때 손해가 이만저만이 아니며 [교착상태]에 빠질 수 있습니다. 꼼꼼한 대출 심사를 거쳐 은행은 돈을 빌려줍니다. 이런 꼼꼼한 대출 심사또한 운영체제도 행하게 됩니다.

먼저 운영체제는 프로세스에게 자원을 할당하기 전에 총 자원이 몇 개있는 지 시스템의 총 자원을 파악하고, 프로세스들은 각자 자기가 필요한 자원의 최대숫자를 운영체제에게 알려줘야 합니다. 그래야 정확한 대출심사가 가능하니까요.

 

예시로 운영체제에게 총 자원이 14개 있다고 칩니다.

 

p1, p2, p3가 운영체제에게 자원을 달라 요청을 했다고 칩시다.

 

총자원 14				이용가능 자원: 2
process	최대 요구 자원	할당된 자원	요청 예상 자원
p1	7	2	3	1개모자람
p2	6	4	2	딱 맞음!
p3	10	6	4	2개모자람

 

 총 자원이 14개인데 현재 할당된 자원은 12개입니다. 2개의 자원이 남아 있습니다. p2의 요청 예상 지원이 2개기에 p2에게 자원을 다 할당해주고 p2는 총 6개의 자원을 다 쓰고 돌려줄 수 있습니다. 그리고 p1, p3에서 다시 나눠 줄 수 있습니다. 

 

이렇게 자원 문제가 유기적이로 해결되는 것을 안정 상태라고 부릅니다. 딱딱 맞아 떨어집니다!

 

하지만 항상 총자원과 최대요구자원, 이용가능한 자원이 다 맞을 수는 없습니다. 

 

총자원 14				이용가능 자원: 1
process	최대 요구 자원	할당된 자원	요청 예상 자원
p1	7	3	3	2개모자람!
p2	6	4	2	1개모자람!
p3	10	6	4	3개모자람

 

이렇게 이용가능한 자원이 1개고 요청예상 자원이 2~4개라면 어떤 프로세스도 끝낼 수 없는 상태가 옵니다. 이를 불안정 상태라고 부릅니다. 은행원 알고리즘은 이론적으로는 완벽하지만, 비용이 비싸고 비효율적입니다. 프로세스가 모든 자원을 미리 선언하고, 전체 자원 수도 고정적이여야하며, 자원이 낭비된다는 큰 단점이 있습니다. 

 

 

해결하는방법3.검출

 

위에 서술했던 해결 방법인 예방과 회피는 각각 실제로 구현하기 어려움과, 자원을 낭비하는 문제가 있습니다. 해결방법 '검출'은 해결방법 중 가장 현실적이다라는 평을 듣습니다.

교착 상태 검출은 운영체제가 프로세스의 작업을 관찰하며 교착 상태 발생 여부를 계속 주시하는 방식입니다. 교착 상태가 발견되면 해결을 위한 회복 단계를 거치지요..

 

교착 상태  검출은 두가지 방법으로 나눠지는데, 이 방법들은 가벼운 교착 상태 검출과 무거운 교착 상태 검출입니다. 

가벼운 교착 상태의 검출은 타임 아웃을 이용하며 무거운 교착 상태 검출은 자원 할당 이용 그래프를 이용합니다.

 

먼저 가벼운 교착 상태의 검출을 살펴보겠습니다.

 

타임아웃을 이용한 교착 상태 검출

 

컴퓨터를 쓰면서 '프로그램이 응답이 없어 종료합니다'를 본 적이 한 번쯤은 있을 것입니다. 이 메세지가 바로 타임아웃을 이용하는 방법입니다. 작업이 여러 개일 때, 잠금도 여러개를 얻는데 이 작업 도중 타임아웃으로 프로세스가 종료되면 데이터에 문제가 생길 수 있습니다. 이 문제를 해결하기 위해서 체크포인트와 롤백을 사용합니다. 체크포인트는 문제가 발생하면 저장된 상태로 되돌아오기 위한 표시입니다. 이 체크포인트 설정과 함께 현재 시스템 상태는 하드디스크에 저장되며 이 저장 데이터를 스냅쇽이라고 하죠. 롤백은 말 그대로, 작업을 하다가 문제가 발생되면 체크포인트로 돌아가는 것입니다. 

타이머를 이용하여 프로세스가 일정시간동안 진행되지 않는다면 교착상태가 발생했다고 간주하고, 일정시점마다 만든 체크포인트로 작업을 저장하여 프로세스 진행이 안된다면 그 저장된 시간으로 롤백시키는 것입니다. 

롤백이 일어나면 스냅숏을 복원해 다시 체크포인트 시점으로 돌아가는 것이죠. 

 

 

 

타임아웃을 이용하면 두 가지 단점이 있습니다. 문제가 있는 프로세스 뿐만이 아니라 다른 프로세스까지 강제종료 당하는 것이 가장 큰 단점입니다. 어떤 앱을 이용하다가 렉이 걸렸는데, 그 렉 때문에 함께 사용하던 다른 앱들도 강제 종료된 경험이 있을 것입니다. 그럴 때 너무 억울한 상황이 벌어지기도 하죠!! 또, 모든 시스템에 적용이 힘들다는 것도 문제가 됩니다.

 

하지만, 자원 할당 그래프를 이용하는 방법보다 더 효율적으로 쓰일 때가 많으므로 자주 쓰이는 방식이며, 자원 할당 그래프는 좀 더 구현하기가 힘들기 때문에 비교적 구현하기 쉬운 타임아웃을 '가벼운 교착 상태의 검출'이라고 부릅니다.

 

 

자원 할당 그래프를 이용한 교착 상태 검출

 

자원 할당 그래프를 운영체제가 지켜보며 교착 상태가 발생하면 해결하는 방식입니다. 

 

 

그림에서 a는 p1은 p2의 자원을 기다리고, p2는 p3의 자원을 기다리고 있습니다. 철학자의 탁자에서 철학자 한명이 포크를 사용하는 것을 기다리며 사색을 하는 것이죠. 이러면 자원이 교착상태가 되는 일이 없습니다.

 

하지만 b에서 p1->p2->p3->p2->p1 ... 의 사이클이 생깁니다. 철학자들 한명씩 포크를 들고 계속 옆에 포크를 요구하는 상황이나 다름 없습니다. 이를 교착상태로 포착하여 문제를 해결하는데, 정확한 문제를 파악할 수 있는 장점이 있지만 이 그래프를 지켜보며 유지, 갱신, 검사하는 추가 작업으로 오버헤드가 발생할 수 있습니다. 그래서 무거운 교착 상태의 검출이라 부르며, 오버헤드의 문제로 가벼운 교착 상태의 검출의 단점이 있어도 타임아웃을 주로 사용하는 이유입니다.

 

 

해결하는방법4.회복

 

교착 상태 검출 후에 교착 상태를 푸는 방법이 있어야겠죠? 회복 단계에서는 교착 상태를 유발한 프로세스를 강제 종료하며, 강제 종료된 프로세스가 실행되기 전 시스템을 복구해야 합니다.

 

 

 

---

 

이번 포스트에서는 교착 상태 dead lock을 알아보았습니다.

교착 상태는 그냥 일어나는 것이 아니라 4가지의 필요조건에 의해 야기 되며, 프로세스끼리의 통신을 위한 임계구역의 존재로 인한 상호배제 문제가 원인입니다. 임계구역을 해결 방법은 그 구역을 lock하는 것이였고, lock에 대한 오류로 인해 교착 상태가 일어나므로 lock은 죽은 상태, 반응을 하지 않는 상태이기에 dead lock이라고도 부릅니다. 이를 해결하기 위해 4가지의 해결방법이 있으며, 주로 검출의 타임아웃 방법을 사용하여 교착상태를 해결을 합니다.