교착 상태와 기아 상태

교착상태란?

프로세스가 결코 일어나지 않을 사건을 기다리는 상태를 말한다.

교착 상태는 시스템 자원에 요구가 뒤엉킨 상태로, 두 프로세스가 사용하는 자원(비공유)를 서로 기다리고 있을 때 발생한다.

즉, 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 기다릴 때 발생한다.

 

교착 상태 발생 조건

교착상태는 다음 4 가지 조건을 모두 만족해야 발생한다.

1. 상호 배제 : 자원을 최소 하나 이상 비공유 해야 한다. 즉, 한 번에 한 프로세스만 사용 가능하다.

2. 점유와 대기. 자원을 최소 하나는 보유하고 있고, 그러한 자원을 얻으려고 대기하는 프로세스가 있어야 한다.

3. 비선점 : 자원을 선점할 수 없다. 즉, 자원을 강제로 빼앗을 수 없다

4. 순환 대기 : 자원을 서로 각각 얻으려 대기하는 것을 말한다. 즉, 사이클이 있어야 한다.

 

교착상태 해결 방법

교착상태는 크게 예방, 회피, 회복 하는 방법으로 해결 가능하다.

 

교착 상태 예방

다음 네 가지 방법으로 예방 가능하다.

1. 상호배제 조건 방지

읽기 권한만 허용한다.

2. 점유 및 대기 조건 방지

작업을 수행하기 전에 필요한 자원을 모두 요청하고 획득한다.

애초에 대기 조건이 성립하지 않도록 하는 것이다.

또 다른 방법은 프로세스가 저원은 전혀 갖고 있지 않을 때만 자원을 요청할 수 있도록 허용하는 것이다.

근데 이러면 자원의 효율성이 너무 낮고, 본인이 사용해야 하는 자원이 너무 많으면 기아 상태에 빠질 수 있따. 

3. 비선점 조건 방지

비선점 조건을 방지하는 방법은 다양한데, 전제 조건은 이미 할당한 자원에 선점권이 없어야 한다는 것이다.

본인이 대기시 현재 가진 자원을 모두 해제하는 방식이다.

작업 상태를 쉽게 저장 및 복구 할 수 있을 때 가능하지, 안그러면 효율성이 바닥이다.

 

아니면, 어떤 자원을 요청할 때 요청 자원이 사용 가능 여부를 검사하는 것이다.

사용할수 없다면, 대기 프로세스가 요청한 자원을 점유하고 있는지 검사한다.

만약 대기 프로세스가 점유하고 있다면, 자원을 해제하고 요청 프로세스에 할당하는 방식이다.

 

또 다른 방법은, 프로세스에 우선순위를 부여하고, 높은 우선순위의 프로세스가 자원을 선점하는 방식으로 해결할 수 있다.

4. 순환 대기 조건 방지

모든 자원에 일련의 순서를 부여하고, 오름차순으로만 자원을 요청할 수 있게 하는 방법이다.

즉, 자원을 계층화 해서 교착 상태를 예방할 수 있으나,

자원 요청 순서를 예상하는 것도 어려울 뿐더러, 예상과 다르게 요청하면 상당한 자원 낭비를 초래한다.

 

교착 상태 회피

위에 예방을 보면 거의 외계인 침공을 대비하기 위해 국가 예산의 80퍼센트를 투자하는 격이다.

이에 비해 교착 상태 회피 방법은 덜 엄격한 조건을 요구해서 자원을 좀 더 효율적으로 사용하는 것이 목적이다. 

 

회피 방법은 두 가지로 설명할 수 있다.

1. 프로세스의 시작 중단 : 교착 상태를 발생시킬 수 있다면 프로세스 시작을 중단한다. - 요청과 해제를 미리 알고 있어야 결정할 수 있다.

2. 자원 할당 거부 : 요청한 자원을 할당했을 때 교착 상태가 발생할 수 있따면 요청 자원을 할당하지 않는다(은행가 알고리즘)

 

안정 상태와 불안정 상태

최대 사용량을 만족해야 자원을 반환 할 수 있다.

a는 P2 -> P0 -> P1 -> P3 순으로 동작하면 모든 프로세스를 완료할 수 있다.

b는 현재 여분 자원을 가지고 어떤 프로세스에 할당하던 만족할 수가 없다.

즉, 자원을 할당한 후에도 시스템이 항상 안정 상태에 있을 때만 허용하면 된다.

 

 

교착상태 회복

교착상태를 회복하려면 다음 알고리즘이 필요하다

1. 교착 상태 탐지

2. 교착 상태에서 회복

 

교착 상태 탐지 알고리즘을 자주 실행하면 성능은 떨어지나, 교착 상태를 빨리 감지하여 자원의 유휴 상태를 방지할 수 있다.

 

교착 상태를 회복하는 방법은 프로세스를 중단하거나 교착 상태 프로세스들에서 자원을 선점하는 방법이 있다

 

프로세스 중단

교착 상태인 프로세스를 모두 중단하거나, 교착 상태를 확인한 후 한 프로세스씩 중단하는 방법을 택하면 된다.

보통 프로세스의 우선순위다, 종료 예상 시간, 필요 자원 수 등을 통해 중단한 프로세스를 선정한다.

자원 선점

쉽게 말해서 프로세스 자원을 뺏어서 교착 상태인 다른 프로세스에게 할당하는 것을 말한다. 근데 이렇게 하려면 선점 자원을 선택하는 알고리즘과, 복귀 방식, 기아 상태 방지를 해결해야 한다.

 

기아상태

기아상태란 사용할 수 없는 자원을 계속 기다리는 것을 말한다.

보통 식사하는 철학자를 통해 설명한다.

 

식사하는 철학자 문제는 다섯 명의 철학자가 원탁에 앉아 식사하는 상황에서 발생하는 동기화 문제를 나타냅니다. 각 철학자는 생각하는 시간과 식사하는 시간을 번갈아 가며 가지고 있습니다. 문제는 한정된 자원(포크)을 공유하는 상황에서 동기화를 어떻게 구현할 것인가입니다.

철학자들은 원탁에 앉아 있으며 각자 앞에는 식사를 하기 위한 접시가 있습니다. 인접한 두 명의 철학자는 하나의 포크를 공유하고 있습니다. 철학자는 생각하다가 배고프면 식사를 시작하고, 포크를 양 옆의 접시에 꽂아 식사를 합니다.

문제는 다음과 같은 상황에서 발생할 수 있습니다:

모든 철학자가 동시에 배고프게 되어 자신의 왼쪽과 오른쪽에 위치한 포크를 모두 집으려고 할 때, 포크를 공유하는 두 철학자가 서로의 포크를 기다리는 상황이 발생할 수 있습니다.

모든 철학자가 자기 왼쪽의 포크를 집어, 오른쪽의 포크를 기다리는 상태에서, 포크를 공유하는 두 철학자가 모두 왼쪽 포크를 계속 가지고 있어 교착 상태에 빠질 수 있습니다.

 

철학자가 동시에 포크를 하나씩 잡으니까 문제가 발생하는 것이다. 이를 해결하기 위해서 다음과 같은 해결책이 있다.

1. 철학자 한 명을 뺀다

2. 철학자가 양쪽 포크를 잡을 수 있을 때 포크를 할당한다.

3. 짝수번째 앉은 철학자 먼저 먹인 후에, 다 먹고 나서 다른 사람에게 할당한다.

등등....

 

교착상태의 해결책은 기아 상태의 가능성을 제거하지 못한다.

즉, 기아상태를 검사하고 추적해야 한다. 

 

참조 : 한빛아카데미 - 그림으로 배우는 구조와 원리 운영체제 - 구현회 저