[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. ④