[운영체제(OS)] 데드락(DeadLock), 교착상태 해결방법 -2

저번 시간에는 데드락이 무엇인지, 데드락이 왜 발생하는지, 데드락이 발생하기 위해서는 어떤 조건들이 갖춰져야 하는지에 대해 살펴봤습니다. 이번 시간에는 데드락이 발생했을 때 해결할 수 있는 방법들을 알아보려고 합니다.

 

0. 데드락 처리 방법

 

데드락 처리 방법은 약 3가지로 분류할 수 있습니다. 

 

1. Ignore - 무시하자

 

말 그대로 다 무시해!입니다. 운영체제가 데드락을 전혀 신경 쓰지 않는 방법이죠. 따라서 개발자가 프로그램을 개발할 때 데드락이 걸릴 가능성을 하나부터 열까지 다 신경 써서 차단해야 하죠.

 

 

2. Deadlock Prevention - 데드락이 절대 발생하지 않게 해야지!

 

말 그대로 데드락이 발생될 가능성을 아예 예방하자!라는 의미입니다. 어떻게 예방할까요? 바로 데드락이 발생될 가능성이 없게 알고리즘을 짜면 됩니다. 어떤 알고리즘일까요? 데드락 발생 필수조건 4가지(상호 배제, 점유와 대기, 비선점, 원형 대기) 중 하나 이상을 만족시키지 않으면 됩니다.

 

상호 배제를 만족시키지 않으려면 자원이 프로세스의 개수보다 많으면 됩니다. 자원이 넘쳐나는데 프로세스가 할당받을 수 없는 자원이 있지는 않겠죠?

 

하지만 생각해보면 어떤 자원은 여러 프로세스에서 동시에 쓸 수 있고, 어떤 자원을 못 쓰고 이런 부분은 우리가 컨트롤할 수 있는 부분이 아닙니다. 컨트롤을 못하면 당연히 상호 배제 조건을 깨는 건 쉽지 않겠죠?

 

점유와 대기를 만족시키지 않으려면 프로세스가 자원을 바로바로 할당을 받아서 기다리는 상황을 만들지 않으면 됩니다. 그리고 자원이 한정되어 있을 경우에는 나는 필요 없지만 다른 프로세스가 자원이 필요하다면 자원을 놓아주면 되겠죠?

 

비선점을 만족시키지 않으려면 프로세스가 다른 자원을 기다리고 있고 할당받지는 못하는 상황에서 가지고 있던 자원을 release 하고 롤백하면 됩니다. 이러한 방법은 프로세스를 쉽게 저장 가능하고 다시 복구하기에 편리한 곳에서 사용 가능합니다.

 

원형 대기를 만족시키지 않는 방법은 유일하게 우리가 컨트롤해서 데드락을 막을 수 있다는 점입니다. 자원에 순서를 부여하고 프로세스/쓰레드에도 순서를 부여해서 직렬화 시키면 Circular 상태를 막을 수 있죠. 

 

3. Deadlock Avoidance - 데드락을 최대한 방지해볼게!

 

데드락을 피한다!라는 의미죠. 데드락이 발생할 가능성이 있는지 없는지 운영체제가 검사를 해주고, 데드락 발생 가능성이 없을 경우에만 자원을 요청했을 때 할당해주는 방법입니다.

 

이 방법에서는 프로세스와 자원의 상태를 런타임에 계속 확인을 하면서 데드락이 일어나지 않는 Safe State를 유지하려 합니다. 현재 이용 가능한 자원, 현재 각각의 프로세스에게 할당되어 있는 자원 그리고 각각의 프로세스들이 사용하고 반납할 자원들의 정보를 바탕으로 잠재적 데드락의 유무를 판단하죠.

 

프로세스 간 자원 할당 순서 중 Safe State Sequence가 하나라도 존재한다면 Safe State라고 판단을 합니다.

 

먼저 Safe State Sequence란 일종의 자원을 필요로 하는 프로세스들에게 자원을 할당해주는 순서인데 바로 이전 프로세스가 수행을 마치고 반납한 자원과 현재 할당 가능한 자원을 이용해 현재 프로세스에게 할당이 가능한 프로세스의 자원 할당 순서를 Safe State Sequence라고 합니다. 

 

Safe State Sequence를 기준으로 Safe State를 유지하고 데드락을 예방하는 것이죠.

 

그럼 이번에는 위와 같은 데드락 방지를 위한 방법으로 사용되는 Banker's Algorithm에 대해서 살펴보려고 합니다.

 

3-1. Banker's Algorithm 이란?

Banker's Algorithm은 자원을 할당했을 때 Safe State 가 될까? 를 시뮬레이션하면서 Safe State를 유지할 수 있는 요구만을 수락하고 나머지는 거절하는 알고리즘입니다. 

 

Banker's Algorithm이 제대로 수행되기 위해서는 몇 가지 자료 구조가 필요합니다.

 

여기서 n은 프로세스의 개수, m은 자원 타입의 개수

1. Available[m]: 길이가 m인 벡터로, 만약 available[j] = k라는 것은 Rj자원을 현재 k개 사용 가능하다는 뜻
2. Max[n*m]: n*m matrix로, Max[i][j] = k라는 것은 프로세스 i가 Rj자원을 k개 요청할 수 있다는 뜻
3. Allocation[n*m]: n*m matrix로, Allocation[i][j] = k라는 것은 프로세스 i가 Rj자원을 현재 k개 할당받음
4. Need[n*m]: n*m matrix로, Need[i][j] = k라는 것은 프로세스 i가 현재 Rj자원을 k개 더 필요로 함.

 

위 내용을 종합해보면, Need [i][j] = Max [i][j] - Allocation [i][j]라는 것을 알 수 있습니다.

 

즉, Available을 이용해서 만만한 Need를 골라 프로세스가 작업을 끝내게 하고 자원을 돌려받는 것이죠.

 

 

3-2.  Safety Algorithm

 

이번에는 Safety Algorithm에 대해서 알아보겠습니다. Safety Algorithm은 위에서 공부한 Safe State를 판별할 수 있는 알고리즘입니다.

 

 

각 프로세스들이 종료가 됐는지에 대한 여부를 False로 초기화하고, Work는 Available 정보 즉, 현재 사용 가능한 자원들의 정보로 초기화합니다.

 

그리고 반복문을 수행하면서 아직 종료되지 않은 프로세스 중, 필요한 자원이 할당 가능한 자원보다 적은 프로세스/쓰레드를 골라서 자원을 할당해주고 이 프로세스를 종료시키는 동시에 가지고 있던 모든 자원을 반납시킵니다. 그러면 사용 가능한 자원(Work)의 양은 늘어나서 이를 바탕으로 또 다른 프로세스에게 자원을 할당할 수 있겠죠?

 

위 과정을 모두 마치고 모든 프로세스가 종료 상태가 되면, Safe state 상태를 만족하게 되는 것이죠.

 

3-3. Resource-Request Algorithm

 

Resource-Requset Algorithm를 정리해보겠습니다.

 

 어느 프로세스/쓰레드로부터 운영체제에게 자원 할당의 요청이 들어오면, 운영체제는 해당 프로세스가 요청한 자원에 대해 할당이 가능한지를 판단하고 할당이 가능하다면 할당을 해주었다고 가정한 이후에 프로세스들 간의 데드락이 발생활 지를 검사합니다. 검사 이후 만약 데드락이 발생한다고 판단되면 자원을 할당하지 않고, 데드락이 발생하지 않는다면 자원을 할당해주는 알고리즘입니다.

 

 

1. 먼저 하나의 프로세스 P가 자원을 요청을 하면 요청한 자원의 양이 현재 P가 필요로 하는 자원의 양과 비교를 합니다.

2. 만약 필요한 양보다 많은 양을 요청을 하게 된다면 에러 처리를 합니다.

3. 그리고 요청한 자원의 양이 현재 할당 가능한 자원의 양보다 크다면, 즉 당장 요청한 자원에 대해 할당해줄 자원이 부족하다면 

다른 프로세스들이 반납할 때까지 기다립니다.

4.두 조건을 모두 만족하면 할당해주었다 가정하고 다음과 같은 값의 상태(가정)로 Safe State를 검사합니다.

 

4. Detection and recovery

 

데드락 상태의 프로세스들을 모두 중지하거나 데드락이 해결될 때까지 프로세스 하나씩 중지하는 방법입니다. 어떤 프로세스를 중지할까요? 당연히 가장 효율적으로 처리하기 위해 최소 비용으로 데드락이 해결될 수 있게 프로세스를 선택해서 중지하겠죠?

 

일단 운영체제는 프로세스/쓰레드가 자원을 요청하는 족족 다 할당을 해준다는 점입니다. 할당을 모두 해준 뒤, 주기적으로 '이 프로세스/쓰레드가 데드락이 걸렸나 안 걸렸나'를 확인합니다. 확인을 하다가 데드락이 걸린 프로세스/쓰레드를 발견하면 (Detection) 데드락이 걸리기 전 상태로 복구(revoery) 하는 방법이죠.

 

그렇다면 복구를 어떻게 해줄까요? 위에서 언급했듯이 여러 개의 프로세스/쓰레드에서 최소 비용으로 데드락을 해결할 수 있게 프로세스를 선택해서 강제로 자원을 내려놓게 합니다. 어떻게 최소 비용인걸 알까요? (이 부분은 저도 아직까지는 모르겠습니다..)

 

이 방법도 장점만 있는 건 아닙니다. 데드락이 발생했는지 확인을 해주는 과정을 거쳐야 하는데 운영체제가 주기적으로 검사만 할 수는 없으니까요. 즉 Detection and recovery 방법도 큰 overhead를 가지게 됩니다.

 

 

5. 정리

 

저번 포스팅과 이번 시간까지 데드락의 개념, 발생 조건, 마지막으로 해결 방안까지 살펴보았습니다.

데드락이 발생하지 않기 위해서는 필수조건을 깨야하고, 알고리즘 등을 사용해서 데드락을 방지할 수 있다는 점도 알게 되었죠.

이상으로 데드락에 대한 설명을 마치겠습니다.

 

감사합니다.