교착 상태의 개념과 발생 원인
교착 상태의 해결 방법
기아 상태
- 식사하는 철학자

5. 교착 상태와 기아 상태

IT COOK BOOK 운영체제 (개정 3판, 구현회 저, 한빛 아카데미) IT COOK BOOK 운영체제 (개정 3판, 구현회 저, 한빛 아카데미) 보안 확인 : 외부링크
"https://www.hanbit.co.kr/store..."로 ? 를 정리한 내용입니다.

교착 상태의 개념과 발생 원인

1 교착 상태(deadlock)의 개념

교착 상태 정의

시스템 자원에 요구가 뒤엉킨 상태로 여러 프로세스가 작업을 멈추고 사용하는 비공유 자원을 서로 기다리고 있는 상태
프로세스들이 임계 영역으로 진행할 수 있음을 나타내는 신호 같은 결코 일어나지 않을 사건을 서로 기다리는 상태

교착 상태의 해악

교착 상태에 빠지면 작업이 정지되어 더 이상 진행하지 못하게 되며, 무한 대기, 기아 상태와 그 이상의 문제를 일으킨다.

이를 해결하기 위해 운영자나 사용자가 작업을 교체하거나 종료하는 외부 간섭으로 해결해야 한다.

교착 상태의 대두

일괄 처리 시스템에서는 없었지만 대화식 시스템에서 동적 자원을 공유하여 자원의 사용률을 높이기 위해 병행 처리와 자원 공유를 하면서 생기는 부작용이다.

프로세스는 자원 요청, 자원 사용, 자원 해제 순서로 자원을 사용하고 반납하는데, 자원의 요청과 해제는 시스템 호출로 하며 이때 운영체제가 관여할 수 있으며, 이 두 가지를 잘 관리하면 교착 상태를 막을 수 있다.

교착 상태의 그림 예시

교차로에서 교통 마비의 예시, 일부 자동차를 후진하거나 네 줄의 차량 줄 중 한 줄을 없애야 한다.

2 교착 상태의 예

스풀링 시스템에서 발생하는 교착 상태

할당된 스풀 공간의 출력을 완료하지 않은 상태에서 다른 작업이 스풀 공간을 모두 차지하면 교착 상태가 발생한다.
스풀링 파일의 일정 포화 임계치(saturation threshold)를 설정하여 교착 상태를 예방할 수 있다. 대신 그만큼 시스템의 처리량은 줄어들 것이다.
디스크를 공유할 때 발생하는 교착 상태

디스크 사용에 제어가 없으면 프로세스들이 서로 충돌하는 명령을 요청할 때 교착 상태가 발생한다.
예를 들어
1. 프로세스 A가 디스크의 실린더 A를 읽으려하고, 프로세스가 실린더 B를 읽으려는 상황
2. 프로세스 A가 디스크 헤더를 실린더 A로 옮기고 일시 정지한 뒤, 다음 프로세스 B에 넘겨준다.
3. 프로세스 B에 의해 디스크 헤더가 실린더 B로 옮겨지고, 프로세스를 넘겨준다.
4. 프로세스 A는 실린더 A의 내용을 읽으려 했으나 디스크 헤더가 옮겨졌으므로, 다시 한번 2번~3번 과정을 무한하게 반복하게 된다.
네트워크에서 발생하는 교착 상태

입출력 버퍼 공간이 부족한 네트워크 시스템에 메시지 흐름을 제어하는 적절한 프로토콜이 필요하다.

3 교착 상태의 발생 조건

교착 상태는 다음과 같은 네가지 조건을 만족할 때 반드시 발생한다. 정확히는 순환 대기를 제외한 나머지 조건을 만족하면, 순환 대기가 생길 가능성이 생기고, 순환 대기는 점유와 대기 조건을 포함한 교착 상태이다.

상호 배제(Mutual exclusion)

한 번에 프로세스 하나만 해당 자원을 사용할 수 있음. 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 함.

점유와 대기(Hold and wait)

자원을 최소한 하나 정도는 보유하고, 다른 프로세스에 할당된 자원을 얻으려고 기다리는 프로세스가 있음.

비선점(No preemption)

자원은 선점, 즉 강제로 빼앗을 수 없고, 자원을 점유하고 있는 프로세스가 끝나야 해제된다.

순환(환형) 대기(Circular wait)

그림 5-3과 같이 프로세스들이 각자 다른 프로세스가 점유하고 있는 자원을 얻으려 기다리는 것을 의미한다.

돌 하나에 한 사람만 디딜 수 있는 징검 다리 위를 두 사람이 마주친다면, 서로 상대방이 딛고 있는 돌에 발을 디딜 수 없으므로, 교착상태가 발생할 것이다.

이 상황을 앞서 배운 교착 상태의 조건에 비유해보자면,

돌 하나를 한 사람만 디딜 수 잇음 👉 상호 배제
각자 돌 하나를 딛고 상대 방의 돌을 요구하고 있음 👉 점유와 대기
사람이 딛고 있는 발을 강제로 들어올리게 할 수 없음 👉 비선점
왼쪽에 오는 사람은 오른쪽 사람의 디딤돌을 요구하고, 오른쪽의 사람은 왼쪽 사람의 디딤돌을 요구함 👉 순환 대기 조건

이때의 해결 방법은 세가지가 있을 것이다.

둘 중 한 사람이 뒤로 돌아 되돌아 간다.
징검다리를 가기 전에 먼저 반대편에 사람이 있는지 확인하고 출발
한쪽에 먼저 갈 수 있는 우선순위를 둔다.

선점 자원 : 부작용 없이 소유한 프로세스에서 빼앗을 수 있는 자원. 메모리, 버퍼, 프로세서 등이 있다.

비선점 자원: 부작용 없이 다른 프로세스에 할당할 수 없는 자원. 프린터, CD 드라이브, 스캐너, 디스크 드라이브, 임계 영역 등이 있다.

교착 상태는 비선점 자원이 발생 시킨다.

4 교착 상태의 표현

교착 상태는 방향 그래프로 표현된 시스템 자원 할당 그래프으로 쉽게 파악할 수 있다.

정집 집합는 프로세스 집합과 자원 집합으로 나뉘며, 간선 집합은 자원 할당선으로 나타낸다.그래프는 그림 5-4와 같이 표현된다.

프로세스 집합	자원 집합	할당 간선 집합
$P_{1}, P_{2}, P_{3}$	$R_{1}, R_{2}, R_{3}, R_{4}$	$P_{1} \to R_{1}, P_{2} \to R_{3}, R_{1} \to P_{2}, R_{2} \to P_{2}, R_{2} \to P_{2}, R_{3} \to P_{3}$

프로세스 상태

프로세스 $P_{1}$ 은 자원 $R_{2}$ 의 자원을 하나 점유하고, 자원 $R_{1}$ 을 기다린다.
프로세스 $P_{2}$ 는 자원 $R_{1}$ 과 $R_{2}$ 의 자원을 각각 하나씩 점유하고, 자원 $R_{3}$ 을 기다린다.
프로세스 $P_{3}$ 은 자원 $R_{3}$ 의 자원 하나를 점유 중이다.

자원 할당 그래프에서는 그래프에 사이클이 없다면 교착 상태가 발생하지 않으며, 사이클이 있다면 발생할 가능성이 존재할 수 있다. 만약 사이클이 존재하고 각 자원에는 단 하나의 자원만 존재한다면 교착상태가 발생한다.

예를 들어 위의 그림 5-6에서는 총 2개의 사이클이 있다.

① : $P_{1} \to R_{1} \to P_{2} \to R_{3} \to P_{3} \to R_{2} \to P_{1}$
② : $P_{2} \to R_{3} \to P_{3} \to R_{2} \to P_{2}$

이 두 사이클 모두 서로의 자원 얻으려고 기다리는 교착 상태이다.

$P_{1} \to R_{1} \to P_{3} \to R_{2} \to P_{1}$

위 그림은 사이클이 존재하지만 프로세스 $P_{4}$ 가 작업이 끝나면 $P_{3}$ 가 자원을 할당받아 차례대로 대기 상태를 벗어나므로 교착상태가 아니다.

교착 상태의 해결 방법

교착 상태의 해결 방법은 크게 3가지로 나눈다.

교착 상태가 발생하지 않도록 예방(prevention)하는 방법
교착 상태의 발생 가능성을 배제하지 않고 이를 적절히 회피(avoidance)하는 방법
교착 상태를 허용하되 교착 상태를 탐지(detection)하여 다시 회복하는 방법

1 교착 상태 예방

앞서 설명한 교착 상태의 네가지 조건이 하나라도 발생하지 않는다면 교착 상태는 예방된다.
다만, 상호배제를 제외할 경우 자원을 효율적으로 쓰는게 불가능하므로, 다음 세가지 교착 상태 예방 방법이 있다.

각 프로세스는 필요한 자원을 한 번에 모두 요청해야하며, 요청한 자원을 모두 제공받기 전까지는 작업을 진행할 수 없다.
어떤 자원을 점유하고 있는 프로세스의 요청을 더 이상 허용하지 않으면 점유한 자원을 모두 반납하고 필요할 때 다시 자원을 요청해야 한다.
모든 프로세스에 자원을 순서대로 할당해야 한다. 모든 프로세스에 각 자원 유형별로 할당 순서를 부여한 후 순서에 따라 자원을 요청하게 한다.

먼저, 상호배제를 포함해 모든 교착 상태 조건을 예방하는 방법을 하나씩 알아보겠다.

1.1 자원의 상호배제 조건 방지

상호배제는 프린터, 디스크 같은 동시에 사용 불가능한 비공유 자원을 대상으로 한다.

파일 읽기 같은 공유 자원의 경우 배타적인 접근이 필요없고 동시에 사용 가능하므로 교착 상태가 발생하지 않는다.

하지만 상호배제의 완벽한 예방은 사실상 불가능한데, 파일 쓰기 처럼 배타적인 접근을 허용하지 않고 공유하면 교착 상태가 발생하는 경우도 있다. 즉, 상호배제는 일부 자원에만 교착 상태를 유발하며, 일부 자원의 경우 오히려 상호배제가 없으면 교착 상태가 생긴다.

1.2 점유와 대기 조건 방지

점유와 대기 조건을 방지하려면 두 가지 방법이 있는데 이를 DVD 드라이브에서 디스크 파일을 데이터를 복사, 정렬, 인쇄 후 테이프 드라이브에 복사하는 프로세스의 경우를 예시로 들어 보자.

프로세스가 작업을 수행하기 전에 필요한 자원을 모두 요청하고 시스템이 허용될 때 모두 획득하게(이를 최대 자원 할당 상태라고 한다.) 하여 프로세스가 대기 상태에 자원을 점유할 수 없게 한다.
- 프로세스가 시작할 때, DVD 드라이브와 디스크 파일, 프린터, 테이프 드라이브를 모두 요청하고 작업이 끝날 때까지 가지고 있는다.
프로세스가 자원을 전혀 갖고 있지 않을 때, 혹은 자원을 완전히 반납했을 때만 자원을 요청할 수 있도록 허용한다.
1. 프로세스가 처음에 DVD 드라이브와 디스크 파일을 요청해서 데이터를 복사 및 정렬
2. 프로세스가 작업이 끝나고 DVD 드라이브와 디스크 파일을 모두 해제한다.
3. 프로세스가 다시 DVD 드라이브와 프린터를 요청한 뒤, 데이터를 인쇄
4. DVD 드라이브와 프린터를 모두 해제
5. 디스크 파일과 테이프 드라이브를 요청해서 파일을 테이프에 복사
6. 디스크 파일과 테이프 드라이브를 모두 해제

위 두 방법은 모두 동일한 단점을 가지고 있다.

자원 효율성이 매우 낮음, 첫번째 방법은 테이프 드라이브 같은 처음부터 사용하지 않는 자원을 모든 작업 기간동안 점유한다. 두번째 방법은 계속 사용하는 DVD 드라이브를 계속 해제 및 요청하면서 대기 상태와 오버헤드를 유발한다.
기아 상태가 발생할 수 있다. 다른 프로세스가 하나라도 자원을 점유하고 있으면, 당장 작업이 가능한 다른 자원들을 확보해도 대기 상태를 유지한다. 또 적은 수의 자원을 요청한 프로세스가 지나치게 우선순위가 높아져, 대화식 시스템에서는 사용할 수 없다.

1.3 비선점 조건 방지

비선점 조건 방지를 위한 3가지 방법이다.

다른 자원을 요청할 때 요청한 자원을 즉시 받을 수 없다면, 가진 모든 자원을 해제하고 필요한 모든 자원을 요청할 수 있을 때까지 대기 후 요청.
- 실행한 작업의 상태를 잃을 수 있으며, 작업 상태를 쉽게 저장, 복구 할 수 있는 상황에만 좋다.
프로세스가 어떤 자원을 요청시 자원의 상태 검사
- 1-1. 만약 요청 자원이 사용 가능시 바로 할당
- 1-2. 자원이 사용 불가능하면 해당 자원을 가지고 있는 프로세스의 상태 확인
  - 1-2-1. 점유 프로세스가 대기 상태라면, 점유를 해제하고 요구 프로세스에게 할당
  - 1-2-2. 점유 프로세스가 실행 상태거나 기타 오류 등의 이유라면 요청 프로세스가 대기
    - 1-2-2-1. 대기 상태 요청 프로세스가 점유한 자원을 누가 요청하면 자원을 해제
두 프로세스에 우선순위를 부여 후, 높은 우선순위 프로세스가 비교적 낮은 우선순위 프로세스의 점유 자원을 선점
- 레지스터같이 복원과 저장이 쉬운 자원에 적용하기 좋다.

1.4 순환(환형) 대기 조건 방지

모든 자원에 일련의 순서를 부여하고 각 프로세스가 오름차순으로만 자원을 요청하게 함

순환 대기 조건 방지의 규칙은 다음과 같다.

각 프로세스는 오름차순으로만 자원들을 요청
프로세스가 자원 R_j를 요청할 때마다 점유하고 있는 j보다 높은 자원들 i > j을 모두 해제해야 한다.

단점으로

순서와 맞지않는 작업 순으로 할당해야할 때 자원 낭비가 심해진다.
작업의 순서를 실제 자원 순서를 반영해야 낭비가 적어지는데, 예측이 힘들다
최신 운영체제는 사용자를 위해 편리한 작업환경을 위해 제약이 적어야 하는데, 작업 순서가 제약이 됨

자원 집합 $R = R_{1}, R_{2}, \dots, R_{n}$ 에 자연수 결과 함수를 이용해 다음과 같은 예시로 정의한다.

F(CD 드라이브) = 2,
F(디스크 드라이브) = 4,
F(프린터) = 7

만약 CD 드라이브와 프린터를 요청하려면, CD 드라이브를 먼저 요청해 할당 받고, 프린터를 요청해 할당받아야 한다.

2 교착 상태 회피

앞서 배운 예방 방법들은 효율성이 크게 떨어지는 문제점이 있었고, 교착 상태 회피는 덜 엄격한 조건을 요구하여 자원을 좀 더 효율적으로 사용하는 것이 목적이다.

예방보다는 회피가 좀더 병행성을 허용하며, 조건을 느슨하게 허용하여 효율적인 편이다.

프로세스의 시작 중단

프로세스의 요구가 교착 상태를 발생시킬 수 있다면 프로세스 시작을 중단하는 방법

현재 수행 중인 모든 프로세스의 최대 자원 요청량과 새로운 프로세스의 최대 요청량을 합한 자원 요청량을 수용할 수 있으면 수용하는 방식.
자원 할당 거부

프로세스가 요청한 자원을 할당 시 교착 상태가 예상된다면 할당 취소, 은행원 알고리즘이라고도 한다.

2.1 프로세스의 시작 중단

교착 상태를 회피할 수 있는 자원 할당의 이상적인 방법은 앞으로 할당된 자원의 순서와 사용가능한 자원, 사용하고 있는 자원등을 미리 파악하고 있는 것이다.

이를 위한 가장 간단한 알고리즘은 각 프로세스가 필요한 자원의 최대치(할당 가능한 자원 수)를 미리 선언하여 시스템이 미리 파악하고, 교착 상태가 되지 않도록 할당하는 것이다.

시스템은 자원 할당 사태를 사용 가능 자원 수, 할당된 자원 수, 프로세스들의 최대 요청 수로 정의하여 순환 대기 조건이 발생하지 않도록 검사하고 할당한다.

자원 할당 상태

안정 상태 : 각 프로세스에 최대치까지 자원을 할당할 수 있고, 안정 순서에 따라 할당할 수 있어 교착 상태를 예방할 수 있는 상태

안정 순서 : 프로세스들이 요청한 작업 할당 순서에 맞추어 모든 자원 요구를 충족할 수 있는 상태
- 정확히는 프로세스 순서 $< P_{1}, P_{2}, \dots, P_{n} >$ 이 안정순서라면, 모든 $P_{i}$ 가 요청하는 자원이 현재 사용 가능한 자원과 $j > i$ 인 모든 $P_{j}$ 가 점유한 자원들로 충족할 수 있는 상태이다.
- 만약 현재 사용 가능한 자원으로 부족하다면, $P_{i}$ 는 자신의 턴을 넘기고 다음 프로세스로 넘기며 순서대로 작업을 처리하고 자원을 해제하게 하다가 충분한 자원이 확보되면 작업을 처리한다.

불안정 상태 : 안정 순서가 없는 상태, 교착 상태가 발생할 가능성이 있는 상태.

시스템 상태 변화 예시

동일한 자원 10개와 $P_{0}, P_{1}, P_{2}, P_{3}$ 을 가진 시스템의 예시를 들어보자.

프로세스	현재 사용량( $t_{0}$ 시간)	최대 사용량
$P_{0}$	2	7
$P_{1}$	1	8
$P_{2}$	2	4
$P_{3}$	2	10
여분 자원 수		3

먼저 안정 상태에서 위 그래프와 같은 상태의 시스템의 예시를 보자면 $< P_{2}, P_{0}, P_{1}, P_{3} >$ 순서의 안정 조건을 만족한다.

$P_{2}$ 의 자원 2개를 추가로 할당 받으면 $P_{2}$ 의 최대 사용량을 만족하므로 작업 실행 후 반납
여분 자원 수가 5개가 되므로, $P_{0}$ 가 자원 5개를 받아 실행한 후 자원 7개를 반납
$P_{1}$ 이 자원 7개를 할당 받고 실행하여 자원 8개를 반납
$P_{3}$ 도 자원 8개를 받아 실행한 후 자원 10개를 반납, 모든 작업 완료

프로세스	현재 사용량( $t_{0}$ 시간)	최대 사용량
$P_{0}$	5	7
$P_{1}$	1	8
$P_{2}$	2	4
$P_{3}$	2	7
여분 자원 수		1

$P_{0}$ 의 요청에 따라 사용량을 3개를 추가해 불안정 상태 시스템을 만들어 보자.

이제 여분 자원 수 1개를 어디에 할당해도 최대 사용량에 도달하는게 불가능하므로, 작업이 끝나지 않는다. 즉, 모두 대기하는 교착 상태가 유지된다.

위의 두 예시를 보았듯이 자원 요청을 어떻게 들어주냐에 따라 시스템 상태가 바뀌므로, 시스템은 언제나 자원 상태를 검사하고 확인하여 할당을 허용해야 한다.

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

은행원 알고리즘은 자원의 할당 여부를 결정하기 전에 미리 모든 자원의 최대 가능한 할당량을 시뮬레이션해 할당 시, 교착 상태, 안정 상태를 검사한다.

각 프로세스는 얼마큼 자원 요청이 가능하고, 얼마큼 자원을 보유하고 있으며, 얼만큼 각 자원을 사용할 수 있는지 등 정보를 얻고, 이를 여러 자료 구조에 저장한다.

은행원 알고리즘 구현에 필요한 자료구조

자료 구조는 자원 할당 시스템의 상태를 나타내며, $n$ 을 시스템의 프로세스 수, $m$ 을 자원 수라 하면 다음과 같은 자료구조가 필요하다.

Available : 각 형태별로 사용 가능한 자원(사용 가능량)을 표시하는 길이가 m인 벡터
- 예를 들어 $A v a i l a b l e [j] = k$ 는 자원을 최대 k개 사용할 수 있다는 의미
Max : 각 프로세스 자원의 최대 요청량(최대 요구량)을 표시하는 $n \times m$ 행렬이다.
- $M a x [i, j] = k$ 이면 프로세스 $P_{i}$ 는 자원이 $R_{j}$ 인 자원을 최대 k개까지 요청할 수 잇다는 의미
Allocation : 각 프로세스에 할당되어 있는 각 형태의 자원 수(현재 할당량)을 정의하는 $n \times m$ 행렬이다.
- $A l l o c a t i o n [i, j] = k$ 이면, 프로세스 $P_{i}$ 는 자원이 $R_{j}$ 인 자원을 최대 k개 점유 중
Need : 각 프로세스에 남아 있는 자원 요청(추가 요구량)을 표시하는 $n \times m$ 행렬이다.
- $N e e d [i, j] = k$ 이면, 프로세스 $P_{i}$ 는 자신의 작업을 종료하려고 자원 $R_{j}$ 를 k개 더 요청한다는 의미,
- $N e e d [i, j] = M a x [i, j] - A l l o c a t i o n [i, j]$
Request : 프로세스 $P_{i}$ 가 작업을 위한 자원 $R_{j}$ 를 요청하는 $n \times m$ 벡터

은행원 알고리즘 구현에 필요한 제약 조건

시간이 흐르면서 벡터의 크기와 값이 변함 $\to$ 자료구조가 수정 가능
X와 Y는 길이가 n인 벡터이다.
$X [i] \leq Y [i]$ 이고, $i = 1, 2, \dots, n 일 때 만 X \leq Y$
$X = (0, 3, 2, 1)$ 이고 $Y = (1, 7, 3, 2)$ 이면 $X \leq Y$ $\to$ 자료구조 크기 비교 정의
$X \leq Y$ 이고 $X \neq Y$ 이면 $X < Y$

은행원 알고리즘 동작

프로세스 $P_{i}$ 가 자원을 요청했을 시 아래와 같이 동작한다.

Request[i] <= Need[i]이면 2단계로 이동하고, 아니면 프로세스가 최대 요청치를 초과하기 때문에 오류상태이다.
Request[i] <= Available이면 3단계로 이동하고, 아니면 자원이 부족하므로 $P_{i}$ 는 대기한다.
시스템은 상태를 다음과 같이 수정하여 요청된 자원을 프로세스 $P_{i}$ 에 할당
- 이때, 안전 알고리즘에 의해 할당 여부를 결정한다.

Available = Available - Request[i];
Allocation[i] = Allocation[i] + Request[i];
Need[i] = Need[i] - Request[i]; 

즉, 할당 시, 자원 할당이 안정 상태라면 프로세스 $P_{i}$ 는 자원을 할당 받고, 불안정 상태라면 $P_{i}$ 는 $R e q u e s t [i]$ 를 대기하고 이전 자원 할당 상태로 복귀한다.

이를 흐름 차트로 나타내면 아래 그림 5-8과 같다.

안전 알고리즘은 시스템이 안정 상태인지, 불안정 상태인지 검사하며 다음과 같은 과정을 거친다.(그림 5-9)

Work와 Finish를 각각 길이가 m과 n인 벡터라고 하자. Work = Available, Finish[i]=false, i=1, 2, ..., n이 되도록 초기화
조건 Finish[i]==false, Need[i] <= Work을 만족하는 i 값을 찾고 없으면 4단계로 이동
Work = Work + Allocation[i], Finish[i]=true를 수행하고 2단계로 이동
모든 i에 대하여 Finish[i]==true이면 시스템은 안정상태이며, 아닐 경우 불안정 상태이다.

안정 알고리즘의 예시

프로세스가 $P_{0} \sim P_{4}$ 까지 5개 존재하며, 자원 4 종류(A,B,C,D)가 있을 때, 다음과 같은 상태의 예시를 알아보자.

프로세스	Allocation	Max	Need	Available
$P_{0}$	2011	3214	1203	1222
$P_{1}$	0121	0252	0131
$P_{2}$	4003	3105	1102
$P_{3}$	0210	1530	1320
$P_{4}$	1030	3033	2003
할당량	7375

이 시스템은 $< P_{2}, P_{0}, P_{4}, P_{1}, P_{3} >$ 순서를 통해 안정 조건을 가질 수 있다.

$P_{2}$ 를 실행한 후 할당된 자원을 해제하면 Available은 5225가 되고 해당 자원으로 다음 프로세서 $P_{0}$ 의 작업을 처리할 수 있다.
이런 식으로 마지막 순서까지 문제없이 실행 가능

하지만 만약 프로세스 $P_{1}$ 이 자원을 0101만큼 추가로 요청했고, 이를 시스템에서 받아들였을 경우, 어떠한 순서로도 프로세스들이 작업을 마칠 수 없게 되며 불안정 상태가 되게 된다.

따라서 이를 막기 위해 안정 알고리즘으로 미리 상태를 시뮬레이션 해야한다.

은행원 알고리즘의 단점

할당할 수 있는 총 자원을 파악하고 일정량을 요청한다. 자원은 수시로 바뀌므로 파악하기가 매우 어렵다.
사용자 수가 일정해야 하지만 다중 프로그래밍 시스템에서는 사용자 수가 항상 변한다.
교착 상태 회피 알고리즘을 실행하면 시스템 과부하가 증가한다.
프로세스는 자원을 보유한 상태로 끝낼 수 없다.
작업에 필요한 최대 필요량을 파악하기 힘들다. 최근 프로그램들은 최대 작업량을 정해놓지 않아 사용자의 편의성을 확보한다.
불안정 상태를 방지해야 하므로 자원 이용도가 낮다.

3 교착 상태 회복

교착 상태 회복에는 교착 상태 탐지 알고리즘과 교착 상태 회복 알고리즘이 필요하다.

탐지와 회복 방법은 필요한 정보를 유지하고 탐지와 회복에 비용이 많이든다. 하지만 탐지 알고리즘을 자주 실행하면 시스템 성능은 떨어지지만, 반대로 자주 실행하지 않으면 자원의 유휴 상태가 오래 남을 수 있다.

3.1 교착 상태 탐지 알고리즘

은행원 알고리즘과 비슷한 자료구조를 사용한다.

Available : 자원마다 사용 가능한 자원 수를 표시하는 길이가 m인 벡터
Allocation : 각 프로세스에 현재 할당된 각 행태들의 자원 수를 표시하는 $n \times m$ 행렬
Request : 각 프로세스의 현재 요청을 표시하는 $n \times m$ 행렬

Work와 Finish는 각각 길이가 m과 n인 벡터이며, Work=Available로 초기화하며, (i=1,2,...,n)일 때 Allocation[i] != 0이면 Finish[i]=false, 아니면 Finish[i]=true이다.
Finish[i]==false, Request[i]<=Work 조건에 맞는 i를 찾고, 조건에 맞는 i가 없으면 4단계로 이동한다.
Work=Work+Allocation[i], Finish[i]=true 조건과 일치하는지 여부를 판단해 2단계로 이동한다.
Finish[i]==false라면, 1<=i<=n인 범위에서 시스템 전체와 프로세스 $P_{i}$ 은 교착 상태이다.

이를 의사 흐름 차트로 표현하면 그림 5-10과 같이 표현된다

아래 차트는 for loop를 모두 표현하면 지나치게 복잡해져서 간략하게 표현되었다.

시스템을 아래 표와 같이 가정하여 알아보자.

프로세스	Allocation	Request	Available
$P_{0}$	010	000	000
$P_{1}$	200	202
$P_{2}$	303	000
$P_{3}$	211	100
$P_{4}$	002	002
total			726

위 상황에서 안전 순서 $< P_{0}, P_{2}, P_{3}, P_{1}, P_{4} >$ 를 통해 모든 i에 대해 Finish[i]=true인 안정 상태를 이룩할 수 있다.

교착 상태 탐지 알고리즘은 교착 상태가 자주 발생할 수록 자주 호출해야 줘야 자원들의 유휴 상태를 막을 수 있지만, 너무 자주 부르면 연산 시간 부담이 크며, 특히 객체 수가 증가하면 기하급수적으로 증가하므로 보통 1시간 마다 또는 CPU 이용률이 40%로 떨어질 때마다 호출한다.

3.2 교착 상태 회복 방법

교착 상태에서 회복한다는 것은 순환 대기에서 벗어난다는 것이며, 단순하게 프로세스를 중단하는 방법과 교착 상태 프로세스들에게 자원을 선점하게 하는 방법이 있다.

프로세스 중단

중단 방법 또한 두 가지로 나뉘며, 둘다 시스템이 정지된 프로세스에 할당되어 있는 모든 자원의 해제를 요청하는 방법이다.

교착 상태 프로세스를 모두 중단 : 교착 상태의 순환 대기를 확실히 해결하지만 자원 사용과 시간 면에 비용이 많이 들며, 프로세스의 부분 작업물들이 날아간다.
한 프로세스씩 중단 : 한 프로세스를 중단할 때마다 교착 상태 탐지 알고리즘을 호출해 교착상태를 확인해가며 중단, 탐지 알고리즘을 호출하는 부담이 크다.

프로세스를 중간에 중단하는 것은 진행 중이던 작업이 취소되거나 날아가는 문제가 생길 수 있다. 또한 한 프로세스 씩이나 부분 중단 하는 방식은 어떤 프로세스를 중단 시킬지 결정하는데 비용이 든다.

중단의 기준으로 프로세스의 우선 순위, 수행 시간과 필요 시간, 사용한 자원 형태, 필요한 자원 수, 대화식, 일괄식 여부 등의 정보를 기준으로 한다.

자원 선점

프로세스의 자원을 선점해서 교착 상태를 해결할 때까지 선점한 자원을 다른 프로세스에 할당하는 방법, 다음과 같은 세가지 사항을 해결해야 한다.

선점 자원 선택 : 프로세스를 종료할 때 비용을 최소화하려면 적절한 선점 순서를 결정, 중단 때와 같이 점유 자원 수, 실행 시간 등이 기준이다.
복귀 : 자원을 잃은 프로세스는 안정 상태로 복귀시키고 다시 시작해야하며, 보통 완전 중단시키고 재시작하며, 가능하면 교착 상태에서 벗어날 정도만 복귀 시킨다. 프로세스의 상태 정보를 유지해야 하는 부담이 있다.
기아 : 동일한 프로세스가 자원들을 항상 선점하지 않도록 비용 기반으로 희생자를 선택한다. 하지만 오랫동안 희생자가 되면 기아 상태가 되므로, 복귀 횟수를 따져가며 기아 상태로 만든다.

실제 운영체제는 앞서 배웠던 모든 방법을 결합하여 시스템 자원 형태마다 최적의 접근 방법을 채택한다.

예를 들어 PCB 내부 자원은 자원 순서화, 메인 메모리 자원은 선점, 작업 파일 등은 회피 방법을 이용한다.

기아 상태

교착 상태는 자유로운 자원 할당에 의한 자원 부족 상태가 원인이라면, 기아 상태는 교착 상태를 예방을 하기 위한 조치들을 원인으로 프로세스가 자원을 영원히 혹은 아주 오랫동안 기다리는 상태이다.

식사하는 철학자

철학자(프로세스) 다섯명이 식사(작업)하거나 생각(대기)하는데 양 손에 두개의 포크(자원)이 필요하다. 자신의 양옆의 포크만 집을 수 있으며, 이는 모두 공유(경쟁 상태)한다. 그림 5-11 처럼 음식을 중앙으로 두개씩 배치되어있으므로, 최대 2명만 식사를 하고, 식사를 마치거나 중단하면 내려놓을 수 있다.

모든 철학자가 동시에 왼쪽 포크를 집은 뒤, 오른쪽 포크를 집으려면, 모두 왼손에 하나만 들게되므로 모두 식사를 하지 못한다.(교착 상태) 이 상태를 해결하기 위한 방법은

포크를 더 많이 사던가(자원 증량)
최대 4명만 동시에 앉게 하거나 (교착 상태 예방)
철학자가 양쪽 포크를 조사해 둘다 사용 가능할 때만 집을 수 있도록 허용
비대칭 해결법 : 홀수 철학자는 왼쪽을 집은 뒤 오른쪽 포크 사용, 짝수는 반대로 사용
각 포크를 세마포로 표시하는 것이다.

semaphore fork[5]; // 1로 초기

철학자는l P(wait) 연산 이후 포크를 집고, 사용한 뒤 V(signal) 연산 이후 내려놓는다.

이를 코드로 표현하면 아래와 같다.

while (true) {
    wait(fork[i]);        // 왼쪽 포크를 집음
    wait(fork[(i+1)%5]);  // 오른쪽 포크를 집음
    ...
    // 식사한다.
    ...
    signal(fork[i]);      // 왼쪽 포크를 내려놓음
    signal(fork[(i+1)%5]);// 오른쪽 포크를 내려놓음
    ...
    // 생각한다.
    ...
}

아래는 최대 4명만 동시에 앉게 하는 방법의 코드다.

semaphore fork[5] = {1};
semaphore room = {4};
int i;
while (true){
    wait(room); // 최대 4명의 자리를 얻을 수 있는지 확인하는 P 연산
    wait(fork[i]);
    wait(fork[(i+1)%5]);
    ...
    // 식사한다.
    ...
    signal(fork[(i+1)%5]);
    signal(fork[i]);
    signal(room);
    ...
    // 생각한다.
    ...
}

교착 상태의 해결책은 기아 상태의 해결책이 아니므로, 기아 상태를 해결하기 위해 프로세스의 기다리는 시간을 조사 추적하고, 조치해야 한다. 하지만 이 또한 시스템 대기로 처리량이 감소할 수 있다.

_articles/computer_science/OS/IT_COOK_BOOK_OS_정리/OS 정리-Chap 5-교착 상태와 기아 상태.md

ROADVIRUSHN

▶ COMPUTER_SCIENCE

▶ WEB

▶ ETC

▶ AI

Recent views

5. 교착 상태와 기아 상태

교착 상태의 개념과 발생 원인

1 교착 상태(deadlock)의 개념

교착 상태 정의

교착 상태의 해악

교착 상태의 대두

교착 상태의 그림 예시

2 교착 상태의 예

3 교착 상태의 발생 조건

상호 배제(Mutual exclusion)

점유와 대기(Hold and wait)

비선점(No preemption)

순환(환형) 대기(Circular wait)

4 교착 상태의 표현

교착 상태의 해결 방법

1 교착 상태 예방

1.1 자원의 상호배제 조건 방지

1.2 점유와 대기 조건 방지

1.3 비선점 조건 방지

1.4 순환(환형) 대기 조건 방지

2 교착 상태 회피

2.1 프로세스의 시작 중단

자원 할당 상태

시스템 상태 변화 예시

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

은행원 알고리즘 구현에 필요한 자료구조

은행원 알고리즘 구현에 필요한 제약 조건

은행원 알고리즘 동작

안정 알고리즘의 예시

은행원 알고리즘의 단점

3 교착 상태 회복

3.1 교착 상태 탐지 알고리즘

3.2 교착 상태 회복 방법

프로세스 중단

자원 선점

기아 상태

식사하는 철학자