[혼공컴운] Ch13. 교착상태
강민철 - 혼자 공부하는 컴퓨터구조 운영체제
책을 읽으며 개인적으로 정리한 내용입니다.
목차
- 교착 상태란
- 식사하는 철학자 문제
- 자원할당 그래프
- 교착 상태 발생 조건
- 교착 상태 해결 방법
- 교착 상태 예방
- 교착 상태 회피
- 교착 상태 검출 후 회복
✅ 교착 상태란
2개 이상의 프로세스가 서로 갖고 있는 자원을 서로 기다리는 상황이 될 수 있다.
이때 어떤 프로세스도 더 이상 진행할 수 없는 상태가 되고, 이것이 교착상태이다.
⏺ 식사하는 철학자 문제
- 철학자 5명이 동그란 식탁에 앉아있다.
- 식사는 두개의 포크를 이용해야 먹을 수 있다.
철학자의 식사 순서
- 왼쪽 포크가 사용가능하면 집어든다.
- 오른쪽 포크가 사용가능하면 집어든다
- 두 포크를 모두 집어들면 특정시간동안 식사를 한다.
- 식사가 끝나면 오른쪽 포크를 내려놓는다.
- 오른쪽 포크가 내려놓은뒤 왼쪽 포크를 내려놓는다.
모든 철학자가 동시에 식사를 시작했다고 가정하자.
모든 철학자는 왼쪽 포크를 집어들것이다.
그리고 2번 오른쪽 포크는 아무도 사용할 수 없게 된다.
진행이 모두 멈춰버리는 현상, 바로 교착상태이다.
✔️ 교착상태는 다양한 상황에서 발생한다.
✍️ 뮤텍스 락에서의 교착상태 예시
프로세스 A가 임계구역 진입 전에 lock1을 잠궜다.
프로세스 B가 임계구역 진입 전 lock2를 잠궜다.
이때 프로세스 A는 lock2가 False가 되길 기다리고, 프로세스 B는 lock1이 False가 되길 기다리면
교착상태가 발생한다.
🤔 교착상태를 해결하려면?
1. 교착상태 발생 상황을 정확히 알아야한다.
2. 교착상태가 일어나는 근본적인 이유를 알아야한다.
상황파악을 위해 자원할당 그래프를 함께 보자.
⏺ 자원할당 그래프
교착상태를 단순하게 표현 가능한 그래프이다.
규칙
1. 프로세스 == 원, 자원의 종류 == 사각형
2. 사용가능한 자원의 개수는 사각형 내에 점으로 표현
3. 프로세스가 어떤 자원을 할당 받아 사용중일 때, 자원에서 프로세스를 향해 화살표를 그린다.
4. 프로세스가 어떤 자원을 기다리고 있다면, 프로세스에서 자원으로 화살표를 그린다.
- SSD는 프로세스 A가 사용하고 있다.
- CPU는 프로세스 B와 C가 사용하고 있다.
- 프로세스 F가 CPU를 기다리고 있다.
- 프린터는 프로세스 D가 사용하고 있다.
- 프로세스 E가 프린터를 기다리고 있다.
교착상태가 일어난 그래프는 자원할당 그래프가 원의 형태를 띄고 있다.
⏺ 교착 상태 발생 조건
교착상태가 발생하는 조건에는 4가지가 있고,
이 4가지가 모두 만족할 때 교착상태가 발생할 가능성이 생긴다.
상호 배제, 점유와 대기, 비선점, 원형 대기
1. 상호 배제
자원은 한번에 하나의 프로세스만 이용가능하다.
상호배제 상황 : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
2. 점유와 대기
어떤 자원을 보유한 채 다른 자원을 기다렸기 때문에 발생한다.
3. 비선점
누군가 자원을 마음대로 선점할 수 있으면 교착상태는 발생하지 않는다.
프로세스가 자원을 비선점(자원을 이용하는 프로세스의 작업이 끝나기를 기다림) 하고 있었기 때문에 발생한다.
4. 원형 대기
프로세스가 요청/ 할당 받은 자원의 형태가 원형이다
자원할당 그래프가 원의 형태로 그려지며 대기하는 것을 의미하며, 이때 교착상태가 발생할 수 있다.
* 원의 형태를 띈다고 해서 반드시 교착상태가 발생하는 것은 아니다.
✅ 교착 상태 해결 방법
교착상태는 예방/회피/회복하는 방법으로 해결한다.
⏺ 교착 상태 예방
교착상태 발생 4가지 조건 중 하나를 충족하지 못하게 한다.
1. 상호배제 없애기 (불가능)
모든 자원을 공유하게 만든다는 의미가 되는데, 이론적으로는 교착상태가 없어지겠지만
현실적으로 불가능하다.
2. 점유대기 없애기
포크를 두개 동시에 들거나, 아예 들지 못하게 하는 방법이다.
OS는 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분한다.
😿 단점
- 자원의 활용률이 낮아질 우려가 있다.
- 한 프로세스에 필요한 자원들을 몰아줘야하므로.. 자원이 필요해도 사용하지 못하는 프로세스와, 사용되지 않으면서 오랫동안 할당되는 자원을 다수 양산한다.
- 많은 자원을 사용하는 프로세스는 불리해진다.
- 동시에 자원을 사용할 타이밍을 확보하기 어렵다. (무한정 기다리게 되는 기아현상이 야기됨)
3. 비선점 조건 없애기
자원을 이용중인 프로세스로부터 자원을 빼앗을 수 있는데
- 일부 자원에 대해선 효과적이다. (CPU는 프로세스가 선점가능한 대표적인 자원이다.)
- 모든 자원이 선점 가능한건 아니다 (프린터)
* 범용성이 떨어지는 방안
4. 원형대기 조건 없애기
모든 자원에 번호를 붙히고, 오름차순으로 자원을 할당하면 원형대기는 발생하지 않는다 .
- 포크에 1~5번까지 번호를 붙힌다.
- 철학자는 번호가 낮은 포크에서 높은 포크 순으로 집어들게한다.
- 5번 포크를 들고 1번 포크를 집을 수 없다.
* 수많은 자원에 번호를 붙이는 건 간단한 작업이 아니다.
* 어떤 번호를 붙이냐에 따라 특정 자원의 활용률이 떨어질 수 있다.
예방 방식은 교착상태가 발생하지 않음을 보장할 수 있지만, 여러가지 부작용이 존재한다.
⏺ 교착 상태 회피
교착상태가 발생하지 않을 정도로만 조심스럽게 자원을 할당하는 방식
교착 상태 회피 방식은
교착상태를
"한정된 자원의 무분별한 할당으로 발생하는 문제라고 간주한다."
자원이 충분한 상황에서 프로세스들이 한 두개의 적은 자원만을 요구한다면 교착상태는 발생하지 않는다.
자원이 한정된 상황에서 모든 프로세스들이 한번에 많은 자원을 요구하면 교착상태가 발생할 가능성이 증가한다.
📖 용어 사전
- 안전 상태
- 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
- 불안전 상태
- 교착 상태가 발생할 수도 있는 상황
- 안전 순서열
- 교착상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미 함
Example 01 ( 용어 )
웹브라우저, 메모장, 게임 프로세스가 동시에 운영체제에 자원을 요청한 상황이다.
웹브라우저 → 메모장 → 게임 프로세스 순서대로 자원을 할당하면 교착상태가 발생하지 않는다고 가정하면, 이를 안전상태라고 한다.
* 안전순서열
* 안전 순서열이 없는 상태가 불안정 상태
Example 02 ( 안전 상태 )
[ 가정 ]
- P1, P2, P3 실행중
- 시스템에 총 12개의 특정 자원이 있으며, 각각 5개, 2개, 2개의 자원을 할당받아 사용중이다.
- P1, P2,P3는 각각 최대 10개, 4개, 9개의 자원을 요구할 수 있다.
| Process | 최대 요구량) | 현재 사용량 |
| P1 | 10 | 5 |
| P2 | 4 | 2 |
| P3 | 9 | 2 |
남은 자원은 3개이다.
여기에서
P2→ P1 → P3 순서대로 자원을 할당해주면, 안전 상태이다.
- P2에게 자원 2개 할당 → P2 프로세스 종료 (자원 4개 반환)
- 사용가능한 자원 5개남음
- P1에게 자원 5개 할당 → P1 프로세스 종료 (자원 10개 반환)
- P3에게 자원 7개 할당 → P3프로세스 종료
Example 03 ( 불안전 상태 )
[ 가정 ]
- P1, P2, P3 실행중
- 시스템에 총 12개의 특정 자원이 있으며, 각각 5개, 2개, 3개의 자원을 할당받아 사용중이다.
- P1, P2,P3는 각각 최대 10개, 4개, 9개의 자원을 요구할 수 있다.
전체적인 상황은 똑같지만,
운영체제가 P3에 자원을 하나 내주었다고 가정을 하나 추가 되었다.
| Process | 최대 요구량) | 현재 사용량 |
| P1 | 10 | 5 |
| P2 | 4 | 2 |
| P3 | 9 | 3 |
남은 자원은 2개이다.
- P2에게 자원 2개 할당 → P2 프로세스 종료 (자원 4개 반환)
- 사용가능한 자원 4개남음
- P1, P3모두 5개 이상의 자원을 요청하고 있으므로 어떤 요구도 들어줄 수 있다.
- 교착 상태 발생
회피 방식은 안전 상태로 움직이는 경우에만 자원을 할당하는 방식이다
⏺ 교착 상태 검출 후 회복
교착상태 발생을 인정하고 사후 조치하는 방식
- 운영체제는 프로세스들이 자원을 요구할 때마다 그때그때 바로 할당하고,
- 교착 상태 발생 여부를 주기적으로 검사한다.
- 교착상태가 검출되면 회복 방식을 이용한다.
선점을 통한 회복
교착상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
> 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당한다.
프로세스 강제 종료를 통한 회복
가장 단순하면서 확실한 방법
- 교착상태에 놓인 프로세스를 모두 강제 종료
- 많은 프로세스들이 작업내역을 잃게될 가능성이 있다.
- 교착상태가 없어질때까지 한 프로세스씩 강제 종료
- 작업 내역을 잃는 프로세스는 최대한 줄일 수 있음
- 교착상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드가 야기됨
references
혼자 공부하는 컴퓨터구조 운영체제 (강민철)