데드락과 데드락 해결

1. 데드락이란?

여러 프로세스가 서로 다른 프로세스의 작업이 끝나기를 기다리다가 아무도 작업을 진행하지 못하는 상태를 교착상태, 즉 데드락이라고 한다.

교착상태가 발생하는 이유는 공유자원 때문이다. 만약 어떤 자원을 여러 개의 프로세스가 공유하지 않는다면 교착상태는 발생하지 않는다.

교착상태를 설명하는 가장 유명한 예시는 식사하는 철학자이다.

원형으로 된 탁자에 맛있는 음식이 준비되어 있고 철학자 5명은 각자 의자에 앉아서 음식을 먹으려고 하는데 포크가 5개 밖에 없다. 음식을 먹으려면 포크를 두 개 사용해야 하며 음식을 먹으려는 철학자는 좌우에 있는 포크를 집어서 음식을 먹는다. 그동안 다른 철학자는 음식을 먹지 않고 깊은 생각을 한다. 하지만 우연히 철학자 5명이 동시에 자기 오른쪽에 있는 포크를 집었다고 가정해보자. 모든 철학자가 포크가 하나 더 필요한 상황이고 아무도 양보를 하지 않아서 더이상 식사가 불가능한 교착상태에 빠지게 된다.

교착상태의 필요조건에는 네 가지가 있다. 이 중 하나라도 충족하지 않는다면 교착상태는 발생하지 않는다.

• 첫번째는 상호배제이다. 어떤 프로세스가 한 리소스를 점유했다면 그 리소스는 다른 프로세스에게 공유가 되면 안된다.
• 두번째는 선점이다. 프로세스 A가 리소스를 점유하고 있는데 프로세스 B가 리소스를 빼앗을 수 없어야 한다.
• 세번째는 점유와 대기이다. 어떤 프로세스가 리소스 A를 가지고 있는 상태에서 리소스 B를 원하는 상태여야 한다.
• 네번째는 원형 대기이다. 원형 대기는 대기를 하는 프로세스들의 관계가 원형을 이루고 있다는 것이다.

운영체제를 연구하는 사람들은 교착 상태를 예방하려고 했으나 제약이 많고 굉장히 비효율적이라 다른 방식을 연구해야 했는데, 이는 바로 교착 상태에 빠졌을 때 해결하는 방법이다.

2. 데드락 해결

교착상태 해결 방법으로는 교착상태 회피라는 방법이 있다.

프로세스들에게 자원을 할당할 때 어느정도 자원을 할당해야 교착상태가 발생하는지 파악해서 교착상태가 발생하지 않는 수준의 자원을 할당한다.

교착상태의 회피는 전체 자원의 수와 할당된 자원의 수를 기준으로 안정상태와 불안정상태로 나눈다.

운영체제는 최대한 안정상태를 유지하려고 자원할당을 한다. 불안정상태에 있더라도 무조건 교착상태에 빠지는 것이 아니라 교착상태에 빠질 확률이 높아진다.

교착상태 회피를 표한한 알고리즘으로는 은행원 알고리즘이 있다. 은행원 알고리즘은 은행이 대출해주는 상식적인 방법의 알고리즘이다. 은행에 돈이 천만원있다고 가정해보자. 사업가 A는 은행으로부터 500만원을 빌린다. 사업가 B도 은행으로부터 400만원을 빌린다. 그럼 은행에는 100만원이 남아있다. 시간이 지나서 은행은 사업가 A에게 돈을 갚으라고 말하는데, 사업가 A는 지금은 갚지 못하고 200만원만 더 빌려주면 그걸로 돈을 벌어서 갚는다고 말한다. 은행은 지금 100만원밖에 없기 때문에 사업가 B에게 돈을 받아서 사업가 A에게 돈을 빌려주기로 한다. 그러나 사업가 B도 지금은 갚을 수 없고 200만원을 더 빌려주면 돈을 벌어서 갚는다고 말한다. 은행은 누구에게도 돈을 빌려주지도 못하고 돈을 받지도 못하는 교착상태에 빠지게 된다. 은행은 이러한 상황을 피하기 위해 사업가들에게 돈을 빌려줄 때 은행의 여윳돈과 사업가들에게 빌려준 돈들을 보고 대출 가능한 상황인지 확인하고 빌려주는데 이를 은행원 알고리즘이라고 한다.

그러면 운영체제에서 은행원 알고리즘을 구현하는 방법을 알아보자. 운영체제는 프로세스들에게 자원을 할당하기 전에 자기가 가지고 있는 전체 자원의 수를 알아야 한다. 이를 시스템의 총자원이라고 부르자. 그리고 프로세스들은 각자 자기가 필요한 자원의 최대 수를 운영체제에게 알려줘야 한다. 이를 최대 요구 자원이라고 부르자.

그러면 안정상태를 먼저 살펴보자. 운영체제가 가지고 있는 자원의 수, 즉 시스템의 총 자원은 14개이다.

프로세스	최대 요구 자원	현재 할당된 자원	요청이 예상되는 자원
P1	9	5	4
P2	6	4	2
P3	4	3	1

현재 안정상태인 운영체제는 사용 가능한 자원이 2개가 있고 이 자원들을 가지고 프로세스의 요청이 예상되는 자원을 제공할 수 있다. 만약 P1이 4개를 요청하면 현재 사용 가능한 자원이 2개이기 때문에 P1의 요청을 거부하고 P2의 요청을 받는다. P2가 2개를 요청했기 때문에 사용 가능한 자원 2개를 전부 P2에게 할당하고 P2는 할당된 자원을 가지고 작업을 마치고 6개를 반납한다. 그러면 사용 가능한 자원이 6개로 늘어났기 때문에 P3가 요청한 1개와 P1이 요청한 4개를 전부 할당할 수 있다.

그러면 불안정 상태를 알아보자. 운영체제가 가지고 있는 자원의 수, 즉 시스템의 총 자원은 14개이다.

프로세스	최대 요구 자원	현재 할당된 자원	요청이 예상되는 자원
P1	9	7	2
P2	6	4	2
P3	4	2	2

지금은 운영체제에 사용 가능한 자원이 1개이다. 이 자원으로는 P1, P2, P3가 요청할 수 있는 최대 요청인 2개를 충족하지 못한다. 불안정 상태에 있더라도 모든 프로세스가 최대 자원을 요청하지 않는다면 교착상태에 빠지지 않을 수도 있지만 불안정상태에 빠지지 않도록 유지하는 게 좋다.

은행원 알고리즘은 교착상태를 피하는 좋은 방법이지만 비용이 비싸고 비효율적이다. 그래서 운영체제를 연구하는 사람들은 교착상태의 발생은 허용하지만 교착상태에 빠졌을 때 이를 해결하는 방식을 연구했다.

운영체제를 연구하는 사람들은 어떻게 교착상태를 검출할 수 있을지 고민하게 되었고 그 결과 두가지 방식으로 검출할 수 있다는 것을 알아냈다.

• 첫번째 방식은 가벼운 교착상태 검출이라고 부른다. 이 방식은 타이머를 이용하는 방식인데 프로세스가 일정 시간 동안 작업을 진행하지 않는다면 교착상태가 발생했다고 간주하고 교착상태를 해결한다. 교착상태를 해결하는 방법은 간단하다. 일정 시점마다 체크포인트를 만들어 작업을 저장해두고 타임아웃으로 교착상태가 발생했다면 마지막으로 저장했던 체크포인트로 롤백하는 것이다.
• 두번째 방식은 무거운 교착상태 검출이라고 부른다. 이 방식은 자원 할당 그래프를 이용하는데 현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고 교착상태가 발생했다면 이를 해결한다. 그래프가 순환 구조를 그리고 있다면, 교착상태를 일으킨 프로세스를 강제로 종료시킨다. 그리고 다시 실행시킬 때 체크포인트로 롤백시킨다. 이 방식은 운영체제가 지속적으로 자원 할당 그래프를 유지하고 검사해야 하기 때문에 오버헤드가 발생한다. 하지만 가벼운 교착 상태에서 발생할 수 있는 억울하게 종료되는 프로세스는 발생하지 않는다.

참고

• 그림으로 쉽게 배우는 운영체제