[Chapter 7. 교착상태] 교착상태와 자원 할당 그래프

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

 

프로세스는 자원을 다음의 순서로만 사용할 수 있다.

 

1. 요청

프로세스는 자원을 사용하기 전에 반드시 요청해야 한다.

 

지정된 태스크를 수행하기 위해 필요한 만큼의 자원을 요청할 수 있으며,

요청된 자원의 수는 시스템에서 사용 가능한 전체 자원의 수를 넘어서서는 안 된다.

 

요청이 즉시 허용되지 않으면 요청 프로세스는 자원을 얻을 때까지 대기해야 한다.

 

2. 사용

프로세스는 자원에 대해 작업을 수행할 수 있다.

 

3. 방출

프로세스는 자원 사용 후에는 해당 자원을 반드시 방출해야 한다.

 

교착상태 (Deadlock)

---

프로세스들이 배타적(상호 배제적)인 접근이 필요한 자원을 하나씩 소유하고 있는 동시에

다른 프로세스가 갖고 있는 자원을 요구하고 있는 상태를 말한다.

 

 

이들은 영원히 대기 상태에서 벗어날 수 없어 결코 실행을 끝낼 수 없고

시스템 자원이 묶여있어 다른 작업을 시작하는 것도 불가능하다.

 

보통 운영체제들은 교착상태 예방 기능을 제공하지 않아, 교착상태가 없는 프로그램을 설계하는 것은 전적으로 프로그래머의 책임이다.

 

교착상태 발생 예시 

두 개의 스레드 T0와 T1이 있으며,

value가 1로 초기화된 세마포어 A와 B를 필요로 한다. (A.value = 1, B.value = 1)

 

이들은 각각 아래의 일들을 차례대로 수행한다.

 

 

T0가 먼저 실행되어 P(A)까지만 실행된 후 스케줄링에 의해 T1이 실행되었다고 하자.

T0는 P(A)를 통해서 자원 A를 얻었고, T1은 P(B)를 통해서 자원 B를 얻었다.

 

 

T1이 P(A)를 실행하려고 했으나, 하나뿐인 자원 A는 이미 T0가 가지고 있다.

따라서 T1은 T0가 A를 방출할 때를 기다리기 위해 대기 상태로 천이되고, T2가 스케줄 되어 실행된다.

 

 

그러나 T0도 P(B)를 실행하려고 했으나, 하나뿐인 자원 B는 이미 T1이 가지고 있는 상황이다.

따라서 T0도 자원 B를 기다려야 하므로 대기 상태로 천이된다.

 

 

서로가 서로의 자원을 기다리고 있으므로 T0, T1 모두 대기 상태에서 영원히 빠져나오지 못하며

아래의 V(A)와 V(B)는 평생 실행되지 못한다.

 

이처럼 대기가 꼬리에 꼬리를 물어 환형을 이루는 상태를 교착상태라고 한다.

 

교착상태가 발생하는 필요충분조건

교착상태는 다음의 4가지 조건이 동시에 만족될 때 발생한다.

 

1. 상호 배제 (Mutual exclusion)

해당 자원은 할당 후 반환까지 한 프로세스만 사용하는 자원이어야 한다.

만약 다른 프로세스가 그 자원을 요청하면, 요청 프로세스는 자원이 방출될 때까지 반드시 대기해야 한다.

 

2. 점유하며 대기 (Hold-and-wait)

프로세스는 적어도 하나의 자원을 점유한 채

현재 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기해야 한다.

 

3. 비선점 (No preemption)

자원은 그 자원을 점유하고 있는 프로세스로부터 강제적으로 방출될 수 없고,

점유하고 있는 프로세스가 작업을 종료한 후 그 프로세스에 의해 자발적으로만 방출될 수 있다.

 

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

대기 프로세스의 집합 {P0, P1, ..., Pn}에 있어서

P0는 P1이 가진 자원을 기다리고, P1은 P2,  ... , Pn-1은 Pn, Pn은 P0가 가진 것을 기다린다.

(꼬리에 꼬리를 물고 대기하고 있는 상태)

 

자원 할당 그래프

위에서 언급했다시피, 자원을 사용하려면 반드시 요청을 해야 하고 사용 후에는 반드시 해체(방출)를 하는 과정을 지켜야 한다.

우리는 교착 상태를 자원 할당 그래프를 통해 분석할 수 있다.

 

 

자원 할당 그래프는 방향 그래프(directed graph)로, 정점 V의 집합과 방향 간선 E의 집합으로 구성된다.

 

정점은 시스템 내의 모든 프로세스의 집합과 시스템 내의 모든 자원 유형의 집합으로 분할된다.

 

1. 프로세스의 집합 P = {P1, P2, ... , Pn}

원으로 표시한다.

 

2. 자원 유형의 집합 R = {R1, R2, ... , Rn}

사각형으로 표시한다.

 

 

방향 간선(directed edge)은 요청 간선과 할당 간선으로 나뉜다.

 

1. 요청 간선 (request edge)

Pi → Rj

프로세스 Pi가 자원 Rj의 인스턴스 하나를 요청하고 있는 상태이다. (현재 프로세스가 해당 자원을 기다림)

 

2. 할당 간선 (assignment edge)

Rj → Pi

자원 Rj의 한 인스턴스가 프로세스 Pi에 할당된 상태이다.

 

 

(예시)

P = {P1, P2, P3}

R = {R1, R2, R3, R4}

V = {(P1, R1), (P2, R3), (R1, P2), (R2, P2), (R2, P1), (R3, P3)}

 

자원 유형 - R1 : 1개 / R2 : 2개 / R3 : 1개 / R4 : 3개

 

 

---

자원 할당 그래프에서 사이클이 없다면 교착상태는 발생하지 않는다.

 

만약 사이클이 존재할 경우

1. 각 자원 유형마다 하나씩의 자원밖에 없다면 교착상태는 반드시 발생한다. (교착상태의 필요충분조건 발생)

2. 각 자원 유형마다 여러 개의 자원이 있다면 교착상태는 발생할 가능성이 있다. (교착상태의 필요조건 발생)

 

 

(예시 1) 사이클이 존재하며, 교착상태가 발생한 경우

 

 

(예시 2) 사이클이 존재하나, 교착상태가 아닌 경우

 

 

P4가 R2를 해제하면 P3 → R2가 R2 → P3이 되어 사이클이 없어지기 때문에 교착상태가 발생한 것이 아니다.