교착 상태 처리 기법

교착상태 처리 기법

교착상태의 처리는 아래 세 가지 기법이 존재합니다.

• 예방  : 네 가지 필요조건이 동시에 만족되는 것을 피하며 교착상태 발생 예방 
• 회피 : 프로세스에 필요한 자원의 최대량에 대한 정보를 이용, 교착상태가 발생하지 않도록 함
• 탐지 및 복구 : 사후처리 방법으로 교착상태의 발생 여부 조사, 발생한 경우 적절한 조치를 취해 정상상태로 복구 

한 가지씩 자세히 알아보겠습니다.

 

교착상태의 예방

상호배제 조건 제거 

상호배제 조건을 제거하여 교착상태를 예방하고자 하는 방법입니다.

하지만 읽기 전용파일 등 상호배제가 필요 없는 공유자원이 있는 반면 프린터 등의 자원은 반드시 상호배제가 필요합니다.

해서 해당 조건 제거로 교착상태 예방은 불가능합니다.

 

점유대기 조건 제거 

이 경우는 대기를 제거 혹은 점유를 제거로 나눠 생각해 볼 수 있습니다.

먼저 대기를 제거한다고 가정한다면 자원 점유 시 대기하지 않아야 합니다.

즉 프로세스가 앞으로 필요한 모든 자원을 처음 한꺼번에 요구해 할당받아야 하는데 이런 경우 요구 자원 중 하나만 할당받지 못해도 계속 대기해야 하는 상황이 발생할 수 있습니다.

해서 자원 이용률이 낮아지고 기아상태에 빠질 가능성이 있습니다.

 

두 번째는 대기 시 자원을 점유하고 있지 않아야 합니다.

새로운 자원을 요구할 때 할당받았던 자원을 모두 해제해야 하는데 위에서 예를 든 프린터처럼 점유도중 해제할 수 없는 자원에는 적용 불가합니다.

해서 점유대기 조건 제거 또한 현실적으로 사용은 힘듭니다.

 

비선점 제거 

해당 조건 제거를 위해선 선점이 가능하도록 해야 합니다.

하지만 자원의 특성에 따라 불가능한 경우가 존재합니다.

혹은 다른 프로세스가 대기할 가능성을 줄여야 하는데 이를 위해서는 점유대기 상황 발생 시 할당받았던 자원을 모두 해제해야 합니다.

이 또한 마찬가지로 자원의 특성에 따라 불가능한 경우가 존재합니다.

 

환형대기 조건 제거 

모든 자원에 일련번호를 지정하는 방법입니다.

일련번호를 이용한 방법은 두 가지가 있습니다.

1. 프로세스는 자원 요구 시 일련번호 기준 항상 오름차순이 되도록 요구하도록 함
2. 프로세스가 자원 요구 시 그보다 일련번호가 작은 자원만 점유하도록 함(보유중인 더 큰 일련번호 자원은 해제)

접근 방식은 다르지만 결과적으로는 점유대기 중인 프로세스는 점유중인 자원의 일련번호보다 대기중인 자원의 일련번호가 크도록 하여 환형대기를 막는 방법입니다.

 

하지만 방법 1은 프로세스마다 요구순서가 다를 수 있어 자원의 일련번호 설정이 어렵다는 단점이 존재합니다.

또한 방법 2는 요구순서가 일련번호 오름차순을 못 지키면 점유자원 해제가 필요하지만 적용불가능한 자원이 존재합니다.

 

해서 환형 대기 조건을 완벽하게 해결할 수는 없습니다.

 

교착상태 회피 

프로세스의 자원 사용에 대한 사전정보를 활용해 교착상태가 발생하지 않는 상태에 머물도록 하는 방법입니다.

여기서 사전정보란 아래와 같은 정보를 이야기합니다.

• 현재 할당된 자원 
• 가용상태의 자원 
• 프로세스들의 자원 최대 요구량 

위 세 가지 정보를 안다는 전제 하에 교착상태 회피가 가능합니다.

 

안전상태 

안전상태란 교착상태에 빠지지 않는 상태로 교착상태를 회피하며 각 프로세스에 그들의 최대요구량까지 빠짐없이 자원을 할당할 수 있는 상태를 이야기합니다.

안전상태는 다른 말로 안전순서열이 존재하는 상태라고 볼 수 있는데요.

반대로 불안전 상태는 안전순서열이 존재하지 않는 상태로 불완전 상태에서는 교착상태가 발생할 수 있습니다.

운영체제 입장에서는 교착상태 회피를 위해 안전상태를 유지하는 것이 필요합니다.

 

그럼 안전순서열이란 무엇인지 알아보겠습니다.

 

안전순서열

교착상태를 회피하며 각프로세스의 자원최대요구량만큼 자원을 할당할 때 어떤 순서대로 작업을 진행해야 프로세스들을 마칠 수 있는지 그 순서를 칭합니다.

즉 순서가 있는 프로세스의 집합이라고 볼 수 있습니다.

 

그럼 프로세스의 위치는 어떻게 선정할 수 있을까요?

각프로세스에 대해 프로세스가 추가로 요구할 수 있는 자원의 양이 현재 가용상태의 자원으로 충당되거나, 혹은 앞선 프로세스에 할당된 자원까지 포함하여 충당 가능한 경우에 안전순서열에서 프로세스의 위치가 적절하다고 봅니다.

위와 같은 경우에 안전순서열은 A → C → B 가 될 것입니다.

하지만 프로세스가 가용한 자원을 요구하더라도 교착상태회피를 위해 대기상태가 될 수 있습니다.

 

 

교착상태 회피 알고리즘 

두 가지 경우로 나누어 생각해 볼 수 있습니다.

1. 각 자원의 단위자원이 하나밖에 없는 경우 
2. 단위자원이 여러 개인 경우 

1번의 경우 변형된 자원할당 그래프를, 2번의 경우 은행원 알고리즘을 이용할 수 있습니다.

 

변형된 자원할당 그래프 

자원정점에 표시하던 단위자원 개수를 제거한 그래프입니다.

지난 포스팅에서 자원할당 그래프를 그리는 방법을 알려드렸었죠??

단위자원은 어차피 한 개이니 표시할 필요가 없습니다.

또 선언간선이라는 개념이 추가되는데요.

프로세스에서 자원으로 가는 간선으로 미래에 프로세스가 자원을 요구하게 될 것이라는 것을 표시합니다.

요구간선과 구분하기 위해 점선으로 표시합니다.

자원을 요구받으면 선언간선을 요구간선으로 변경합니다.

 

해당 요구간선을 할당간선으로 변환해도 사이클이 생기지 않는 경우에만 자원을 할당 후 할당간선으로 변환하게 됩니다.

은행원 알고리즘 

자원을 요구받으면 해당 자원 할당 후의 상태를 계산해 그것이 안전한 상태인지 확인한 뒤 안전상태가 보장되는 경우에만 자원을 할당합니다.

 

안전상태를 체크하는 알고리즘은 안전알고리즘이라고 하는데요.

안전 알고리즘에는 아래와 같은 개념이 있습니다.

max : 프로세스의 최대요구 
alloc : 프로세스의 할당 자원 
need : 프로세스의 추가 요구 (need =  max - alloc이라는 식으로 구할 수 있음)
avail : 가용자원 

 

교착상태 탐지 및 복구 

사후처리방법으로 교착상태가 생기면 복구하는 방법입니다.

 

탐지 

주기적으로 상태조사 알고리즘 수행하여 시스템의 교착상태 여부를 조사합니다.

대표적인 알고리즘으로는 Shoshani와 Coffman 알고리즘이 존재합니다.

안전알고리즘은 미래의 교착상태 발생 가능성을 체크했다면 위 알고리즘은 현재 상태가 교착상태인지를 판단합니다.

해서 need, max와 같은 값은 필요 없이  alloc , req , avail 값만 있으면 계산이 가능합니다.

 

탐지 알고리즘은 매 순간 수행하기엔 부담스럽기 때문에 아래와 같은 경우에 수행합니다.

• 즉시 받아들일 수 없는 자원 요구 존재 시 
• 정해진 시간 간격
• CPU 효율이 일정 수준 이하로 떨어질 때 

 

복구 

교착상태가 탐지된 경우 정상상태로 복구합니다.

복구의 주체는 오퍼레이터가 수동으로 복구하는 방법과 운영체제가 자동으로 복구하는 방법 두 가지로 나뉩니다.

 

복구방법

아래 두가지 경우로 나눠 생각할 수 있습니다.

• 교착상태 프로세스를 종료 
• 교착상태 프로세스가 할당받은 자원을 해제 

 

교착상태 프로세스 종료 

첫 번째로는 모든 교착상태 프로세스를 종료할 수 있습니다.

이 방법은 진행했던 내용에 대한 복원비용이 크다는 단점이 있습니다.

 

두 번째로는 사이클이 제거될 때까지 교착프로세스를 하나씩 제거해 볼 수 있습니다.

이 경우는 종료 대상을 선택하기 위한 비용과 매 프로세스 종료 후 교착상태 재확인을 위한 비용이 발생합니다.

 

교착상태 프로세스가 할당받은 자원 해제 

사이클 제거 시까지 할당된 자원을 단계적으로 선점해 다른 프로세스에 할당하는 방법입니다.

프로세스 진척도와 사용 중인 자원의 수 등을 고려해 프로세스와 자원을 선택합니다.

 

프로세스의 복귀 시점도 제반 요소를 고려해 결정해야 하며 기아상태에 빠지지 않도록 프로세스 선택 시 복구 횟수도 고려하여 진행하는 것이 필요합니다.