[5주차] Chapter 13. 교착 상태, 교착 상태 해결

Chapter 13 교착 상태

---

13-1 교착 상태란

1. 식사하는 철학자 문제

① 식사하는 철학자 문제(dining philosophers problem)

 -교착 상태가 어떤 상황에서, 왜 발생하는지와 해결 방법을 알아낼 수 있는 가상의 시나리오

동그란 원탁에 5명의 철학자가 앉아있고, 철학자들 사이사이에는 포크가 있다. 
철학자들의 앞에는 각자 식사가 있고, 포크가 2개여야만 식사가 가능하다. 
이때 철학자들은 아래와 같은 규칙으로 식사를 진행한다.
① 계속 생각을 하다가 왼쪽 포크가 사용 가능하면 집어든다.
② 계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어든다.
③ 왼쪽과 오른쪽 포크를 모두 집어 들면 정해진 시간 동안 식사를 한다.
④ 식사가 끝나면 오른쪽 포크를 내려 놓는다.
⑤ 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.
⑥ 다시 ①부터 반복한다.

-철학자 모두가 생각만 하거나, 각자 왼쪽 포크를 집어서 아무도 오른쪽 포크를 집지 못하는 상황이 발생할 수 있다.

 

② 교착 상태(dead lock)

 -일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상

 -식사하는 철학자 문제에서 철학자=프로세스 또는 스레드, 포크=자원(임계 구역), 생각하는 행위=자원을 기다리는 것

 -다양한 상황에서 발생하며, 뮤텍스 락에서도 교착 상태가 발생할 수 있다.

 

2. 자원 할당 그래프

① 자원 할당 그래프(resource-allocation graph)

 -자원을 사용 중인 프로세스와 대기 중인 프로세스를 표현하는 간단한 그래프

 

② 자원 할당 그래프를 그리는 규칙

 -프로세스는 원으로, 자원의 종류는 사각형으로 표현한다.

 -사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현한다.

 -프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시한다.

 -프로세스가 어떤 자원을 기다리는 중이라면 프로세스에서 자원을 향해 화살표를 표시한다.

 

③ 교착 상태가 발생한 자원 할당 그래프

 -교착 상태가 발생한 상황에 자원 할당 그래프는 원(순환하는)의 형태를 보인다.

 -자원 할당 그래프가 원의 형태라고 반드시 교착 상태가 발생하는 것은 아니다.

 

3. 교착 상태 발생 조건

 아래 조건 중 하나라도 만족하지 않는다면 교착 상태가 발생하지 않지만, 아래 조건을 모두 만족할 때 교착 상태가 발생할 가능성이 생긴다.

① 상호 배제(mutual exclusion) 

 -한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태

 ex)식사하는 철학자 문제에서 하나의 포크를 한 명이 사용하는 것

 

② 점유와 대기(hold and wait)

 -자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태

ex)식사하는 철학자 문제에서 '왼쪽 포크를 들고' 다른 철학자의 포크를 기다리는 것

 

③ 비선점(nonpreemptive)

 -한 프로세스가 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태

ex)식사하는 철학자 문제에서 다른 철학자가 쥐고 있는 포크를 강제고 빼앗지 못하는 것

 

④ 원형 대기(circular wait)

 -자원 할당 그래프에서 프로세스들이 원의 형태로 자원을 대기하는 상태

---

확인문제

1. ④

2. 상호 배제, 점유와 대기, 비선점, 원형 대기

3. ②

---

13-2 교착 상태 해결 방법

1. 교착 상태 예방

① 교착 상태 예방

-교착 상태 필요조건 네 가지 중 하나를 만족하지 못하도록 하여 교착 상태를 예방하는 방식

 

② 상호 배제 제거

 -모든 자원을 공유 가능한 자원으로 만드는 것

 -현실에서 사용하기 어렵다.

 

③ 점유와 대기 제거

 -운영체제가 특정 프로세스에 모든 자원을 할당하거나 아예 할당하지 않는 방식으로 배분하는 것

 -단점 : 자원의 활용률이 낮아진다, 많은 자원을 사용하는 프로세스에게 기아 현상이 발생할 수 있다

 

④ 비선점 제거

 -이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있게 하는 것

 -단점 : 일부 자원(CPU 등)에 한해서는 모든 자원을 선점할 수 있게 할 수 없으므로(프린터 등) 범용성이 떨어진다

 

⑤ 원형 대기 제거

 -모든 자원에 번호를 붙이고 오름차순으로 자원을 할당하도록 하는 것

 -단점 : 모든 자원에 번호를 붙이는 작업이 어렵다, 자원의 번호에 따라 자원의 활용률이 떨어질 수 있다

 

2. 교착 상태 회피

① 교착 상태 회피

 -교착 상태가 발생하지 않을 정도로만 조심스럽게 자원을 할당하는 방식

 

② 안전 상태(safe state)

 -교착 상태가 발생하지 않고 모든 프로세스가 자원을 할당받아 정상적으로 실행하고 종료될 수 있는 상태

 -안전 순서열(safe sequence, 교착 상태 없이 안전하게 프로세스들에게 자원을 할당할 수 있는 순서)이 있는 상태

 

③ 불안전 상태(unsafe state)

 -안전 순서열이 없는 상태

 

3. 교착 상태 검출 후 회복

① 교착 상태 검출 후 회복

-교착 상태 발생을 인정하고 사후에 조치하는 방식

 

② 선점을 통한 회복

 -교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식

 

 

③ 프로세스 강제 종료를 통한 회복

 -교착 상태에 놓인 프로세스를 모두 강제 종료 : 교착 상태를 빠르게 해결할 수 있으나, 많은 프로세스들이 작업 상황을 잃을 수 있다.

 -교착 상태가 해소될 때까지 한 프로세스씩 강제 종료 : 작업 상황을 잃는 프로세스를 줄일 수 있으나, 교착 상태 해소 여부를 확인하는 과정에서 오버헤드를 야기한다.

 

④ 타조 알고리즘(ostrich algorithm)

 -드물게 발생하는 교착 상태를 아예 무시하는 방식

---

확인문제

1. ②

2. 5개, 3-2+4=5

3. ②

4. ④