본 글은 책 "혼자 공부하는 컴퓨터 구조+운영체제" 의 Chapter 13. 교착상태 부분을 읽고 정리한 내용입니다.
교착 상태(Deadlock)란?
- 일어나지 않을 사건을 기다리며 진행이 멈춰버리는 현상
게임 프로세스는 자원 A를 점유한 채 웹 브라우저 프로세스가 점유하고 있는 자원 B의 사용이 끝나길 기다리고, 웹 브라우저 프로세스는 자원 B를 점유한 채 게임 프로세스의 자원 A 사용이 끝나길 기다리는 상황
교착 상태는 아주 다양한 상황에서 발생하고 뮤텍스 락에서도 발생할 수 있음
lock1 = true;
while (lock2 == true); # wait
//임계 구역 진입
lock1 = false;
lock2 = true;
while (lock1 == true); # wait
//임계 구역 진입
lock2 = false;
- 위 두 코드 모두 while 문에서 교착 상태가 발생
- 교착 상태를 해결하기 위해서는
- 발생한 상황을 정확히 표현하고
- 일어나는 근본적인 이유에 대해서 알아야 함
자원 할당 그래프(Resource-allocation graph)
- 어떤 프로세스가 어떤 자원을 사용하고 있고, 어떤 프로세스가 어떤 자원을 기다리는지 표현하는 간단한 그래프
1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현
2. 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현
3. 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시
4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스→자원 방향으로 화살표를 표시
교착 상태가 발생한 상황은 자원 할당 그래프가 원의 형태를 띄고 있음
교착 상태 발생 조건
상호 배제
- 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
점유와 대기
- 자원을 할당 받은 상태에서 다른 자원을 할당받기를 기다리는 상태
비선점
- 프로세스가 자원을 비선점하고 있기 때문
원형 대기
- 프로세스가 요청 및 할당 받은 자원이 원의 형태를 이루었기 때문 (circular wait)
교착 상태 해결 방법
교착 상태 예방
- 교착 상태 발생 필요 조건 4가지 중 하나를 충족하지 못하게 하는 방법
- 상호 배제
- 점유와 대기
- 비선점
- 원형 대기
자원의 상호 배제 없애기
- 모든 자원을 공유 가능하게 만듦
- 현실가능한 방법은 아님
점유와 대기 없애기
- 특정 프로세스에 자원을 모두 할당하거나 아예 할당하지 않는 방식으로 배분 → 자원의 활용도를 낮출 수 있는 방식임
- 많은 자원을 필요로 하는 프로세스가 무한정 기다리게 되는 기아현상을 야기할 수 있음
비선점 조건 없애기
- 선점이 가능한 자원(ex) CPU)에 한해 효과적이지만 모든 자원이 선점 가능한 것은 아님 (ex) 프린터)
원형 대기 조건 없애기
- 모든 자원에 번호를 붙이고 오름차순으로 자원을 할당
- 하지만 모든 자원에 번호를 붙이고, 어떤 자원에 어떤 번호를 붙이냐에 따라 활용률이 달라짐
교착 상태 회피
- 교착 상태가 발생하지 않을 정도로만 조심히 자원을 할당하는 방식
교착 상태를 회피하는 방법을 학습하기 위해 아래 용어를 알아야 함
안전 순서열(Safe sequence)
- 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서를 의미
안전 상태(Safe state)
- 안전 순서열대로 프로세스들에 자원을 배분하여 교착 상태가 발생하지 않는 상태
불안전 상태(Unsafe state)
- 안전 순서열이 없는 상황으로 교착 상태가 발생할 수 있는 위험이 있는 상태
예시
- 컴퓨터 시스템에 총 12개의 자원이 존재
- 프로세스 P1, P2, P가 실행중
- 각각 5개, 2개, 2개의 자원을 할당받아 사용중
- 운영체제가 프로세스에 배분할 수 있는 자원은 3개 (12-5-2-2) 가 남은 상황
- P1, P2, P3는 각각 10, 4, 9개의 자원을 요구할 수 있음
| 프로세스 | 요구량 | 현재사용량 |
| P1 | 10 | 5 |
| P2 | 4 | 2 |
| P3 | 9 | 2 |
- 할당 가능 자원: 12개
- 할당한 자원: 9개
- 남은 자원: 3개
위의 경우 안전 순서열이 존재: P2→P1→P3
Q. 안전 순서열은 어떻게 알 수 있나? → 은행원 알고리즘 참고
안전 순서열이 존재하지 않는 경우
- 위의 예시에서 모든 프로세스가 최대의 자원을 요구하는 상황에 P3에 선뜻 하나의 자원을 내줌
| 프로세스 | 요구량 | 현재사용량 |
| P1 | 10 | 5 |
| P2 | 4 | 2 |
| P3 | 9 | 2->3 |
- 할당 가능 자원: 12개
- 할당한 자원: 10개
- 남은 자원: 2개
위의 상황에서 남은 자원을 P2에 모두 주면, 남은 자원은 0개
| 프로세스 | 요구량 | 현재사용량 |
| P1 | 10 | 5 |
| P2 | 4 | 4 |
| P3 | 9 | 3 |
- 할당 가능 자원: 12개
- 할당한 자원: 12개
- 남은 자원: 0개
위의 예에서 P2가 모든 자원을 반납해도 P1, P3의 요구량을 모두 채울 수 없으므로 서로가 보유하고 있는 자원만을 바라보며 무한정 기다릴 수 밖에 없음 → 불안전 상태로 교착 상태 발생
교착 상태 검출 후 회복
- 교착 상태가 검출되면
- 선점을 통한 회복
- 프로세스 강제 종료를 통한 회복
선점을 통한 회복
- 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
프로세스 강제 종료를 통한 회복
- 교착 상태에 놓인 프로세스가 모두 강제 종료(→ 작업 내용을 잃음)
- 교착 상태가 해결될 때까지 한 프로세스씩 강제 종료(→오버헤드가 있지만 잃는 작업 내용 최소화)
참고
1. 책 "혼자 공부하는 컴퓨터 구조+운영체제"
2. 유튜브 "혼자 공부하는 컴퓨터 구조 + 운영체제"