운영체제(5) - 교착 상태와 기아 상태

교착 상태 Deadlock

교착상태란?

교착상태Deadlock란, 다중 프로그래밍 시스템에서 프로세스가 결코 일어나지 않을 사건을 기다리는 상태를  말한다. 프로세스는 자원을  요청 -> 사용 -> 해제 순으로 사용한다. 이러한 프로세스가 두 개 있다고 가정해보자. 교착상태는 두 프로세스가 하나의 자원을 서로 요청하여 기다릴 때 발생한다. 교착상태에 빠지면 작업이 정지되어 명령 실행이 불가해진다.  따라서 운영자나 사용자는 작업을 교체하거나 종료하는 등의 외부 간섭으로만 해결할 수 있다. 

 

교착상태의 간단한 예를 들 수 있다. 스풀링이 있다.  스풀링은 버퍼링보다 빠른 디스크를 이용한 임시저장공간이다.이러한 스풀 공간에서 출력을 하나도 완료하지 않은 상태에서 입력만 받으면 공간이 모두 차버려서 교착상태가 발생할 수 있다.

 

교착상태의 조건

상기한 조건이 모두 충족돼야 발생한다. 다만 일부 상황에서는 1-3번 조건만을 만족해도 발생할 수 있다.

1. 상호배제 : 한 번에 프로세스 하나만 해당 자원을 사용할  수 있어야 한다. 사용 중인 자원을 다른 프로세스가 사용하려면 해당 자원을 해제할 때까지 기다려야 한다.
2. 점유와 대기 : 자원을 최소 하나 정도 보유했으며 다른 프로세스에 할당된 자원을 자원을 기다리는 프로세스가 있어야 한다.
3. 비선점 : 자원을 강제로 빼앗을 수 없고, 자원을 점유한 프로세스가 끝나야 해제된다.
4. 순환 대기 : 프로세스 집합이 다수 있다고 가정할 때 집합 내 프로세스들이  서로의 자원을 요청하는 상태다. 

 

교착상태의 표현

자원할당 그래프

이 그래프의 상태는 교착상태가 아니다. P3는 언젠가 종료되기에 P3->P2->P1 순으로 작업을 끝마칠 수 있다.

 

교착상태에 있는 할당 그래프

위의 그래프는 교착상태에 있다. p1의 요청은 이뤄질 수 없기에 '일어날 수 없는 이벤트를 기다리는 상태'로 있게 된다.

 

 

교착상태의 해결 방법

예방 prevention, 회피 avoidance, 탐지 detection와 회복, 세 가지가 있다.

---

예방

• 하벤더의 교착상태 예방 방법 

상호배제를 제외한 교착상태 예방방법은 다음과 같다.

1. 프로세스는 필요한 자원을 한 번에 모두 요청해야 하며, 모두 받기 전에는 작업 진행이 불가하다.

2. 자원 점유한 프로세스의 요청을 더 이상 허용하지 않을 때 점유한 자원을 모두 반납하고 필요할 때 다시 자원을 요청한다.

3. 모든 프로세스에 자원을 순서대로 할당한다.

 

• 자원의 상호배제 조건방지, 점유와 대기 조건 방지, 비선점 조건 방지, 순환 대기 조건 방지

---

회피 : 교착상태가 발생할 가능성을 인정하고 발생하기 전에 적절하게 회피하는 것이다. 회피 방법으로는 시작을 중단하거나, 은행가 알고리즘처럼 교착상태가 발생할 가능성이 있는 요청이 있을 때는 자원할당을 하지 않는 것이다.

 

• 안정상태와 불안정상태

사용자가 현재 작업을 일정기간 안에 끝낼 수 있다면 그 운영체제의 현재 시스템 상태는 안정이라 할 수 있다. 그렇지 않다면 불안정상태인 것이다. 

시스템 안정상태와 불안정 상태

위의 표에서 안정과 불안정의 구분은 남은 자원 수를 할당할 때 프로세스 작업을 끝낼 수 있는가가 결정한다.

• 자원 할당 거부(은행가 알고리즘)

자원할당 여부를 결정하기 전, 모든 자원의 최대 할당량을 시뮬레이션하여 안전여부를 검사한 후 교착상태 가능성을 조사한다. 불안정상태에서 할당할 수 있다고 하면 요청을 연기하거나 거부한다.

• Available : 각 형태별로 사용 가능한 자원 수(사용 가능량) 표시하는 길이가 m인 벡터 Available[j]=k이면, 자원을 k개 사용할 수 있다는 의미

• Max : 각 프로세스 자원의 최대 요청량(최대 요구량)을 표시하는 n×m 행렬. Max[i, j ] =k이면, 프로세스 Pi는 자원이 Rj인 자원을 최대 k개까지 요청할 수 있다는 의미

• Allocation : 현재 각 프로세스에 할당되어 있는 각 형태의 자원 수(현재 할당량) 정의하는 n×m 행렬. Allocation[i, j ]=k이면, 프로세스 Pi는 자원이 Rj인 자원을 최대 k개 할당받고 있다는 의미

• Need : 각 프로세스에 남아 있는 자원 요청(추가 요구량) 표시하는 n×m 행렬. Need[i, j ] =k이면, 프로세스 Pi는 자신의 작업을 종료하려고 자원 Rj를 k개 더 요청한다는 의미 ( Need=max-allocation )

은행가 알고리즘의 동작 단계

안전 알고리즘

은행가 알고리즘 실행을 위해서는 사용자 수가 항상 일정해야 하지만 다중 프로그래밍 시스템에서는 사용자 수가 항상 변한다.

---

탐지 및 회복

 

탐지 알고리즘과 회복 알고리즘으로 나뉜다. 교착 상태가 자주 발생하면 그만큼 탐지 알고리즘을 자주 호출한다. 이는 연산 시간이 부담스럽기에 경제적으로 호출 빈도를 줄이는 것이 좋다.

 

 

 

기아 상태

교착상태를 예방하기 위해 자원을 할당할 때 발생하는 결과다. 

식사하는 철학자의 예로, 세마포로 해결한다.