7. 운영체제 교착상태

- 프로세스 관리(8) : 교착상태(Deadlock) -

 

프로세스는 실행을 위해 여러 자원을 필요로 한다. CPU, 메모리, 파일 등등 여러 자원을 사용하여 프로세스가 실행된다. 그런데 어떤 자원은 갖고 있으나 다른 자원을 갖지 못할 경우 대기 상태에 들어가서 기다려야한다. 자원은 한정되어 있는데 여러 프로세스가 같이 동작하는 상황이여서 이러한 상황이 발생하게 된다. 그러므로 운영체제는 이러한 자원을 프로세스들에게 잘 할당을 해주어야한다. 만약 잘 할당을 해주지 못하면 앞의 식사하는 철학자의 문제와 같이 모든 프로세스가 자원을 가지려고 대기하는 교착상태에 빠질 수 있다.

교착상태가 일어나는 필요조건은 4가지가 존재한다.

첫 번째는 상호배타(Mutual exclusion)이다. 상호배타는 동기화를 만족시키기 위한 조건과 같다. 하나의 프로세스가 자원을 사용할 경우 다른 프로세스는 그 자원을 사용할 수 없는 것을 의미한다.

두 번째는 보유 및 대기(Hold and wait)이다. 프로세스가 자신이 가질 수 있는 자원은 가지고 있으면서 다른 자원이 오기를 기다리고 있는 것이다.

세 번째는 비선점(No Preemption)이다. 비선점은 프로세스 스케줄링에서 배운 단어 같은 의미이다. 대신 여기서는 CPU할당뿐만 아니라 모든 자원에 의해서 비선점이 된다는 것이다. 임의의 프로세스가 자원을 할당 받은 상태에서 다른 프로세스는 이 자원을 뺏어서 사용할 수 없는 형태가 비선점이다.

마지막은 환형대기(Circular wait)이다. 선형이 아니고 원형을 이루게 되어 프로세스의 자원 할당에서 첫 번째 프로세스와 마지막 프로세스의 자원할당이 겹치게 되어 원형에 있는 모든 프로세스가 자원 할당을 받고자 기다리는 형태가 만들어지는 것을 말한다.

식사하는 철학자를 예시로 들어보면 젓가락에 대한 상호배타가 존재한다. 한 명의 철학자가 젓가락을 가지고 있으면 다른 철학자는 가질 수 없다. 보유 및 대기는 한 짝의 젓가락을 가지고 있는 상태에서 다른 젓가락을 기다리고 있는 경우와 같다. 철학자가 젓가락을 가지고 있으면 다른 철학자가 젓가락을 뺏을 수 없으므로 비선점도 만족된다. 또한 원형 테이블에서 이루어지는 형태로 환형대기도 만족되어 결국 식사하는 철학자들은 교착상태에 빠지게 되는 것이다.

교착상태가 발생하는 원인은 바로 자원인데 자원은 어떻게 할당되는가? 프로세스가 메모리에서 동작할 때 자원에 대한 요청을 운영체제에 전달하게 된다. 그러면 운영체제는 이러한 요청을 받아 누구도 자원을 사용하고 있지 않을 경우 사용을 할 수 있게 할당을 해준다. 그 후 프로세스가 자원을 다 사용하고 나면 반납을 하게 되는 형태를 가진다.

자원 할당도는 어떤 자원이 어떤 프로세스에게 할당되었는가? 또는 어떤 프로세스가 어떤 자원을 할당 받으려고 기다리고 있는가? 에 대한 정보를 가르쳐 주는 지표이다. 자원은 사각형으로 표시되고 프로세스는 원으로 할당은 화살표를 통해 나타나게 된다. 자원의 경우 동일한 형식의 자원을 가질 수 있는데 이를 동일 자원이라고 한다. 이런 경우 사각형 안의 점으로 표시하게 된다. 점이 하나이면 동일한 형식의 자원이 하나만 있다는 의미이고 여러 개일 경우 그 개수만큼 동일 자원이 존재한다는 것이다. 프로세스가 화살표로 자원을 가리키면 프로세스가 자원을 요청한 것이고 자원이 화살표로 프로세스를 가리키면 자원이 프로세스에 할당되어 사용 중이라는 것을 의미한다.

자원 할당도를 통해 교착상태의 필요조건을 적용시키면 자원 할당도 상에 원이 만들어져야 한다. 이런 상태는 교착상태의 조건인 환형대기를 만족시키게 되어 교착상태에 빠질 수 있는 것을 의미한다. 물론 항상 교착상태에 빠지는 것은 아니다. 필요조건이기 때문이다.

그림을 살펴보게 되면 프로세스1은 R1에 자원을 요청하고 R2의 자원을 보유하고 있다. 프로세스2는 R3에 자원 요청을 하고 R1과 R2의 자원을 가지고 있다. 프로세스3의 경우는 R3의 자원을 가지고 있고 R2에 자원을 요청했다. 이렇게 원의 형태를 가지고 있는 자원 할당도를 보게 되면 교착상태에 빠졌다는 것을 알 수 있다. 모든 프로세스는 자원을 가지고도 있지만 자원을 요청하고 기다리고 있는 상태이다. 따라서 모든 프로세스는 동작을 할 수 없게 된다.

오른쪽의 경우에는 프로세스2의 경우 R1을 사용 중이다. 따라서 이 작업이 끝나면 R1에 대한 자원을 반납할 것이다. 그 자원을 프로세스1이 사용할 수 있다. 프로세스4 또한 R2의 자원을 사용하고 반납을 할 수 있다. 그러면 프로세스3이 사용하여 모든 프로세스가 작업을 수행할 수 있으므로 교착상태가 아니다.

---

- 프로세스 관리(9) : 교착상태 처리 -

교착상태는 모든 프로세스들이 필요한 자원을 할당 받지 못해 대기를 하고 있는 상태를 말한다. 프로세스는 실행을 위해 여러 자원이 필요한데 어떤 자원은 갖고 있으나 다른 자원은 할당을 받기 위해 대기해야한다. 하지만 다른 프로세스 역시 다른 자원을 가지려고 대기를 하고 있어 모든 프로세스들이 자원을 할당받지 못한다. 위와 같은 교착상태에 빠지는 필요조건은 상호배타, 보유 및 대기, 비선점, 환형대기가 있다. 이에 대해서는 앞장인 교착상태 장에서 설명하였으니 생략하도록 한다. 또한 이를 자원 할당도로 확인하는 방법을 알아보았다.

교착상태가 발생하면 모든 프로세스가 중지하는 현상이 생기므로 큰 문제가 생긴다. 일반 PC의 경우에는 컴퓨터를 껐다가 켜면 되지만 항공이나 군사적 요소와 같이 실시간으로 문제를 처리하는 부분에서는 교착상태가 발생하면 매우 위험한 상황에 빠질 수 있다. 그러므로 교착상태를 해결하는 일은 매우 중요하다.

교착상태를 처리하는 방법은 크게 4가지 방식이 있다.

(1) 교착상태 방지 방식은 교착상태 4가지 필요조건 중 한 가지 이상을 불만족 시키는 방법이다. 앞의 상호배타, 보유 및 대기, 비선점, 환형 대기 중 하나만이라도 만족하지 못하는 상태가 되면 교착상태가 발생하지 않기 때문이다.

먼저 상호배타를 불만족하게 하는 방법으로는 자원을 공유 가능하게 만드는 것이다. 하나의 프로세스가 자원을 사용하고 있을 때 다른 프로세스도 자원을 사용가능하게 만드는 방식이다. 하지만 이런 방식은 동기화의 문제를 만들 수 있어 원천적으로 불가능한 방식이다. 교착상태를 없애려다가 더 큰 문제를 발생시킬 수도 있기 때문이다.

보유 및 대기를 불만족 시키기 위해서는 자원을 가지고 있으면 다른 자원을 기다리지 않게 처리하는 방식이 있다. 일부 자원만 잡고 있는 경우를 없애는 것이다. 따라서 프로세스들은 모든 자원을 가지고 있거나 아니면 자원을 아예 가지고 있지 않는 상태로만 존재하게 만드는 것이다. 하지만 이런 경우 자원 활용률이 매우 저하되고 더 심각하게는 starvation을 만들 수 있다.

비선점을 불만족 시키는 것은 반대로 선점으로 만들어 주는 것이다. 자원이 할당되어 있다고 하더라도 다른 프로세스가 자원을 뺏어올 수 있게 하는 것이다. 하지만 이런 경우는 프로세스를 처리할 때 문제가 발생할 확률이 더 높아진다. 예를 들어 프린터라는 자원이 있는데 프로세스1이 처리 도중 프로세스2가 뺏어오게 되면 프린트에 출력되는 내용이 섞이게 될 것이다. 따라서 원천적으로 불가능한 방식이다.

마지막은 환형대기를 깨는 방법은 자원에 번호를 부여하여 번호 오름차순으로 자원을 요청하는 방식이다. 프로세스가 자원을 할당 받는 부분에 순서를 부여하여 원형의 모양을 깨는 방식이다. 식사하는 철학자의 예시를 사용하게 되면 철학자 프로세스1은 자원1을 먼저 할당받아야하고 프로세스2는 자원2를 이렇게 해서 프로세스4는 자원4를 먼저 할당 받는다. 하지만 프로세스5의 경우에는 양 옆에 자원1과 자원5가 있으므로 먼저 자원 할당을 받아야하는 자원은 1번 자원이다. 따라서 프로세스4는 자원4와 자원5를 먼저 할당 받을 수 있게 되어 원형의 모양이 깨어지게 된다. 이 방법이 교착상태를 방지하는 가장 좋은 방법이라고 할 수 있다.

(2) 교착상태 회피는 운영체제가 자원을 나누어 주는 과정에 대한 문제를 고려하는 방식이다. 자원을 어떻게 잘 할당하여 줄 것인가에 대한 방식을 생각하는 것이다.  따라서 자원을 추가 할당하기 전에, 미래에 교착상태가 발생할것인 지에 대한 예측이 필요하다. 예를 들어서 한 번 보도록 해보자. 현재 자원이 12개가 있고 프로세스가 3개가 동작한다고 생각을 하자.

 

표를 보게 되면 프로세스에 따라 각자 모든 처리를 위해 필요한 양과 현재 할당한 양을 나타내고 있다. 현재 할당한 양은 운영체제 의해 자원이 할당된 것을 의미한다. 따라서 12개 중에서 5개, 2개, 2개를 할당한다. 그러면 자원은 3개가 남게 된다. 그러면 이 프로그램은 안전한가? 그걸 판단하기 위해서는 프로세스를 모두 처리할 수 있는지를 생각해보면 된다. 우선 프로세스1이 남은 자원 3개 중 2개를 더 사용하면 프로세스 처리를 끝낼 수 있다. 처리가 끝나고 나면 자원을 다시 반납하므로 총 7개의 자원이 생기게 된다. 7개의 자원을 가지고 있으면 프로세스0이나 프로세스2 중 우선순위가 있는 프로세스에 자원을 할당에 프로세스를 끝내고 자원 반납 후 다른 프로세스도 종료 시킬 수 있다. 그러면 자원을 활용해서 모든 프로세스가 사용할 수 있게 된다. 이렇게 되면 자원 할당이 안전한 할당이 되었다고 한다.

그러면 다른 경우를 보도록 하자. 위와 똑같이 12개의 자원과 3개의 프로세스가 있다고 하자. 그런데 바뀐 점을 보면 프로세스2에 현재 할당된 양이 3개가 되었다. 그러면 남는 자원은 2개가 된다. 자원 할당을 통해 프로세스들이 모두 종료가 될 수 있는지 살펴보자. 우선 프로세스1은 앞의 경우와 같이 프로세스를 처리 가능하다. 그러면 프로세스1이 종료되고 자원 4개가 반납이 되었다. 그런데 자원 4개를 가지고 처리를 할 수 있는 프로세스가 존재하지 않는다. 따라서 이러한 할당은 모든 프로세스를 종료시킬 수 없다. 이런 경우를 불안전한 할당이라고 하고 교착상태에 빠졌다고 한다. 따라서 교착상태 회피는 자원을 할당할 때 안전한 할당을 하게 하는 것을 의미한다.

(3) 교착상태 검출 및 복구 방법은 교착상태가 일어나는 것을 허용하고 주기적인 검사를 통해 교착상태 발생 시 복구를 하는 방식이다. 검사에 대해서는 계산이나 메모리 사용과 같은 추가적인 부담이 필요하고 복구에 대해서는 프로세스를 일부 강제 종료하거나 자원을 선점하여 일부 프로세스에게 할당하는 방식이 사용된다.

(4) 교착상태 무시는 말 그대로 교착상태가 발생하는 것에 준비를 하지 않는 것이다. 교착상태는 실제로 잘 일어나지 않는다. 필요조건인 4가지의 조건이 모두 만족하더라도 실제로 교착상태는 잘 일어나지 않는다. 만약 일어난다면 모두 꺼버리고 재시동을 하는 방법으로 교착상태를 벗어난다.

출처: http://copycode.tistory.com/78?category=740133 [ITstory]