[혼자 공부하는 컴퓨터구조+운영체제] "chapter13. 교착 상태"

13-1 교착상태란

식사하는 철학자 문제

교착상태를 설명하기 위한 문제 상황.
동그란 원탁에 다섯명의 철학자 앉아 있음. 앞에 식사가 있고 철학자 사이사이에 식사에 필요한 포크 있음. 식사는 두개의 포크로 먹을 수 있는 음식.
 
식사하는 순서

 
모든 철학자가 동시에 포크를 집어 식사했을 시, 어떤 철학자도 식사 x. 다른 철학자가 포크를 내려 놓을 때까지 기다려야 함.
 
교착상태: 일어나지 않을 사건을 기다리며 진행이 멈춰버리는 현상. 상대방이 가진 자원을 기다리기만 하다가 결국 실행 한번 못하는 상황.
철학자 = 프로세스, 스레드
포크 = 자원 (임계구역)
생각하는 행위 = 자원을 기다리는 것

 
교착 상태는 아주 다양한 상화에서 발생 (뮤텍스 락 등)
 
교착상태 해결 방법
1. 교착상태 상황 정확히 표현.
2. 교착 상태 일어나는 근본적인 이유 알기.
 

자원 할당 그래프

어떤 프로세스가 어떤 자원 사용, 어떤 자원 기다리는지 표현하는 그래프.
 
자원할당그래프 그리는 규칙
1. 프로세스 = 원, 자원종류 = 사각형
2. 사용할 수 있는 자원 개수 = 자원 사각형 내 점(.)
3. 프로세스가 어떤 자원 할당 받아 사용중, 자원 -> 프로세스 표시
4. 프로세스가 어떤 자원 기다림, 프로세스 -> 자원 표시

 
철학자 문제, 자원할당 그래프 표현

 
다른 교착 상태

 
교착 상태 일어난 그래프 특징: 자원할당 그래프 원의 형태
 

교착 상태 발생 조건

1. 상호배제
해당 자원을 한번에 하나의 프로세스만 이용 가능. (포크를 여러명 동시에 사용한다면 문제 x)
한 프로세스가 사용하는 자원 다른 프로세스 사용 불가능일 때.
 
2. 점유와 대기
(왼쪽 포크를 들고 다른 철학자 포크 기다렸기 때문)
자원을 보유한 채 다른 자원을 기다렸기 때문에 문제 발생.
자원 할당받은 상태에 다른 자원을 할당받기 기다리는 상태.
 
3. 비선점
(포크를 강제로 빼앗을 수 있다면 문제 x)
자원을 이용하는 프로세스의 작업이 끝나야만 이용 가능. 어떤 프로세스도 다른 프로세스의 자원 강제로 뺏지 못했기 때문에.
 
4. 원형 대기
자원할당그래프가 원의 형태면 교착상태 발생. 프로세스들이 원의 형태로 자원 대기하는 것.
 
 
 

---

 
 
 

13-2 교착 상태 해결 방법

교착 상태 예방

교착 상태 발생 필요 조건 4가지 중 하나를 충족하지 못하게 하는 방법.
 
자원 상호 배제 제거
• 모든 자원 공유.
• 동기화를 할 때 큰 문제.
• 현실적으로 어려움.
점유 대기 제거
• 운영체제는 특정 프로세스에 자원 모두 할당, 아예 할당 x.
 
- 단점
• 한 프로세스에 필요한 자원 몰아줌, 다른 프로세스 필요한 자원 몰아줌
• 자원 활용률 낮아짐: 당장 자원이 필요해도 기다릴 수밖에 없는 프로세스, 사용되지 않으면서 오랫동안 할당되는 자원 다수 양산
• 자원을 많이 필요로 하는 프로세스가 무한정 기다리게 되므로 기아 현상을 야기할 우려
 
비선점 조건 제거
• 자원을 이용 중인 프로세스로부터 해당 자원 뺏을 수 있음
• 선점이 가능한 일부 자원 효과적(CPU)
• 모든 자원 선점 가능한 것 아님(프린터)
• 범용성 떨어짐
 
원형 대기 조건 제거
• 모든 자원에 번호 붙여, 오름차순 자원 할당
• 모든 컴퓨터 시스템 내 존재하는 수많은 자원에 번호 붙이는 작업 복잡
• 어떤 번호를 붙이는지에 따라 특정 자원 활용률 떨어짐
 

 
철학자들 원형식탁 아닌 사각형 식탁에서 일렬로 앉아 식사하는 상황 유사.
 

교착상태 회피

교착상태 발생하지 않을 정도로만 할당하는 방식
교착상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주.
 
교착상태 회피: 프로세스들에 배분할 수 있는 자원의 양 고려, 교착상태 발생하지 않을 정도의 양만큼만 자원을 배분하는 방법
 
안전상태: 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원 할당받고 종료될 수 있는 상태. 안전 순서열대로 프로세스들에 자원 배분하여 교착 상태 발생하지 않는 상태.
불안전 상태: 교착 상태가 발생할 수도 있는 상황. 안전 순서열 없는 상태.
안전 순서열: 교차 상태 없이 안전하게 프로세스들에 자원 할당할 수 있는 순서
 
 
컴퓨터 시스템에 총 12개 자원 존재.
p1(5개), p2(2개), p3(2개) 할당받아 사용 중
p1(10개), p2(4개), p3(9개) 각각 최대 개수 자원 요구.
 
프로세스와 스레드는 자원 사용위해 자원 운영체제 요청 -> 운영체제로 부터 자원 할당 받아 사용 -> 자원 사용 끝나면 자원 반환
 
안전상태
p2 -> p1 -> p3 안전 순서열

 
불안전 상태
p3(2개) 자원을 쓰고있는 상태x,  (3개) 자원을 쓰고 있는 상태
안전 순서열 없음

 

교착 상태 검출 후 회복

교착 상태 발생 인정 후 사후 조치 방식
 
선점을 통한 회복
교착 상태가 해결될 때 까지 한 프로세스씩 자원 몰아주는(다른 프로세스로부터 자원 강제로 빼앗고 한 프로세스 할당)방식.
 
프로세스 강제 종료를 통한 회복
교착 상태에 놓인 프로세스 모두 강제 종료. (한방에 교착 상태 해결 가능, 많은 프로세스 들 작업 내역 잃을 가능성)
교착 상태가 없어 질 때까지 한 프로세스씩 강제 종료. (작업 내역 잃는 프로세스 최대한 줄일 수 있음, 교착 상태 없어졌는지 여부 확인하는 과정에 오버헤드 야기)
 
타조 알고리즘: 교착상태 아예 무시하는 방법.
 

---

출처
https://hongong.hanbit.co.kr/%ec%bb%b4%ed%93%a8%ed%84%b0-%ea%b5%ac%ec%a1%b0-%ec%9a%b4%ec%98%81%ec%b2%b4%ec%a0%9c/

[한빛미디어] 혼자 공부하는 컴퓨터 구조+운영체제