교착 상태(deadlock)는 둘 이상의 프로세스가 서로 상대가 쥔 자원을 기다리며 아무도 나아가지 못하는 상태입니다. 기다림이 원을 이루면 누구도 먼저 놓지 않아 영원히 멈추므로, 운영체제는 원이 생기지 않게 막거나 생긴 원을 찾아 풀어야 합니다.
병행 제어에서 두 트랜잭션이 서로의 락을 기다리며 함께 멈춘 장면이 바로 교착 상태입니다. 프로세스와 프린터·스캐너 같은 장치 사이에서도 똑같이 생깁니다. 아래 그림은 프로세스 둘과 자원 둘 사이에 '쥐고 있음'과 '기다림' 화살표를 하나씩 그어 원이 닫히는 순간을 보이고, 그 원을 막는 법과 푸는 법을 견줍니다.
1교착 상태의 네 조건
그림처럼 프로세스와 자원 사이를 화살표로 이은 그림을 자원 할당 그래프(resource allocation graph)라고 합니다. 교착 상태는 네 조건이 한꺼번에 성립할 때만 생깁니다. 거꾸로 하나만 깨도 생기지 않습니다.
| 조건 | 뜻 | 그림에서 |
|---|---|---|
| 상호 배제(mutual exclusion) | 자원 하나를 한 번에 한 프로세스만 쓴다 | 프린터는 P1만 쓴다 |
| 점유와 대기(hold and wait) | 자원을 쥔 채 다른 자원을 기다린다 | P1이 프린터를 쥔 채 스캐너를 기다린다 |
| 비선점(non-preemption) | 쥔 자원을 남이 빼앗을 수 없다 | P1의 프린터를 빼앗지 못한다 |
| 환형 대기(circular wait) | 기다림이 원을 이룬다 | P1 → 스캐너 → P2 → 프린터 → P1 |
환형 대기는 자료에 따라 순환 대기라고도 부릅니다. 비선점은 스케줄링의 비선점과 같은 '빼앗지 않는다'는 뜻입니다.
2예방과 회피
예방(prevention)은 네 조건 가운데 하나를 미리 깨 두는 방법입니다.
| 깨는 조건 | 방법 | 대가 |
|---|---|---|
| 상호 배제 | 자원을 함께 쓰게 한다 | 프린터처럼 함께 쓸 수 없는 자원이 많다 |
| 점유와 대기 | 필요한 자원을 한꺼번에 받거나, 가진 것이 없을 때만 요청하게 한다 | 받아 둔 자원이 놀고 기아 상태가 생길 수 있다 |
| 비선점 | 더 받지 못하면 가진 자원을 내놓게 한다 | 하던 일을 되돌려야 한다 |
| 환형 대기 | 자원에 번호를 매겨 작은 번호부터 요청하게 한다 | 번호 순서에 맞춰 요청해야 한다 |
회피(avoidance)는 조건을 깨지 않고, 자원을 줄 때마다 준 뒤에도 안전한지 미리 따집니다. 모든 프로세스가 끝날 수 있는 순서(안전 순서)가 있으면 안전 상태(safe state)이고, 없으면 불안전 상태입니다. 불안전 상태가 될 요청은 들어주지 않고 기다리게 합니다. 이렇게 따지는 대표 방법이 다익스트라(Dijkstra)가 내놓은 은행원 알고리즘(banker's algorithm)이고, 프로세스마다 최대로 쓸 자원 수를 미리 알려야 합니다.
3발견과 회복
발견(detection)은 교착 상태가 생기게 두었다가, 자원 할당 그래프에서 원을 찾아 알아내는 방법입니다. 자료에 따라 탐지라고도 부릅니다. 회복(recovery)은 찾은 원을 끊는 일입니다. 원 안의 프로세스를 끝내거나 자원을 빼앗아 다른 프로세스에 주고, 끝낼 프로세스는 되돌릴 일이 적은 쪽을 고릅니다.
예제
자원 10개를 프로세스 셋이 나눠 씁니다. 은행원 알고리즘으로 지금 상태가 안전한지 따집니다.
| 프로세스 | 최대 요구 | 가진 것 | 더 필요한 것 |
|---|---|---|---|
| P1 | 7 | 3 | 4 |
| P2 | 4 | 2 | 2 |
| P3 | 8 | 3 | 5 |
나눠 준 것이 8개라 남은 것은 2개입니다. 남은 것으로 끝낼 수 있는 프로세스를 찾고, 그 프로세스가 끝나면 가졌던 것을 돌려받는다고 셈합니다.
| 차례 | 남은 것 | 끝낼 수 있는 프로세스 | 끝난 뒤 남은 것 |
|---|---|---|---|
| 1 | 2 | P2(2 필요) | 2 + 2 = 4 |
| 2 | 4 | P1(4 필요) | 4 + 3 = 7 |
| 3 | 7 | P3(5 필요) | 7 + 3 = 10 |
안전 순서(P2 → P1 → P3)가 있으니 안전 상태입니다. 그런데 이때 P1이 1개를 더 달라고 하면, 주고 난 뒤 남은 것은 1개이고 더 필요한 것은 P1 3 · P2 2 · P3 5입니다. 어느 것도 끝낼 수 없어 불안전 상태가 되므로 은행원 알고리즘은 P1을 기다리게 합니다.
시험 포인트
- 필기: 교착 상태는 상호 배제·점유와 대기·비선점·환형 대기가 모두 성립할 때 생기고, 하나만 깨도 생기지 않습니다. 해결 방법은 예방(조건 하나를 미리 깸)·회피(안전 상태를 지킴)·발견(원을 찾음)·회복(프로세스를 끝내거나 자원을 빼앗음)입니다. 은행원 알고리즘은 회피 기법이고 최대 요구량을 미리 알아야 합니다. 자원에 번호를 매겨 차례로 요청하게 하는 것은 환형 대기를 깨는 예방입니다.
- 실기: 상호 배제(Mutual Exclusion)·점유와 대기(Hold and Wait)·비선점(Non-preemption)·환형 대기(Circular Wait), 예방(Prevention)·회피(Avoidance)·발견(Detection)·회복(Recovery), 은행원 알고리즘(Banker's Algorithm)으로 씁니다.
확인 문제
1. 교착 상태를 예방하려고 환형 대기를 깨는 규칙을 고르세요.
- ① 작업을 시작하기 전에 쓸 장치를 모두 받아 두게 한다
- ② 장치를 더 받지 못한 프로세스는 쥔 장치를 내놓게 한다
- ③ 장치마다 번호를 붙이고, 번호가 큰 장치를 쥔 채로는 작은 번호의 장치를 요청하지 못하게 한다
- ④ 장치를 줄 때마다 모든 프로세스가 끝날 수 있는 순서가 남는지 따진다
정답
③입니다. 요청이 늘 번호가 커지는 쪽으로만 흐르므로, 기다림이 돌아 처음 자리로 오는 원이 생기지 않습니다.
- ① 장치를 쥔 채로 다른 장치를 기다리는 일을 없애는 규칙입니다. 점유와 대기를 깹니다.
- ② 쥔 장치를 내놓게 해 빼앗을 수 있게 만드는 규칙입니다. 비선점을 깹니다.
- ④ 조건을 깨지 않고 줄 때마다 안전한지 따지는 회피입니다. 예방이 아닙니다.
2. 두 팀이 회의실 하나와 빔 프로젝터 한 대를 써야 합니다. (가)~(라)는 교착 상태의 네 조건 가운데 무엇인지 한글 이름과 영문으로 함께 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.
- (가) 회의실은 한 번에 한 팀만 들어가 쓸 수 있습니다.
- (나) A팀은 회의실을 잡아 둔 채 빔 프로젝터가 비기를 기다립니다.
- (다) B팀이 들고 간 빔 프로젝터를 A팀이 강제로 가져올 수 없습니다.
- (라) A팀은 B팀의 빔 프로젝터를, B팀은 A팀의 회의실을 기다려 기다림이 한 바퀴 돕니다.
정답
받는 답: (가) 상호 배제(Mutual Exclusion) · (나) 점유와 대기(Hold and Wait) · (다) 비선점(Non-preemption) · (라) 환형 대기(Circular Wait) 또는 순환 대기
(가)의 실마리는 '한 번에 한 팀만', (나)는 '잡아 둔 채 기다린다', (다)는 '강제로 가져올 수 없다', (라)는 '기다림이 한 바퀴 돈다'입니다.
- 틀리는 꼴 비선점 — (나)에: 쥔 것을 빼앗을 수 없다는 조건입니다. (나)는 쥔 채 다른 것을 기다리는 모습입니다.
- 틀리는 꼴 상호 배제 — (다)에: 한 번에 하나만 쓴다는 조건입니다. (다)는 이미 가져간 것을 빼앗지 못하는 모습입니다.
- 틀리는 꼴 점유와 대기 — (라)에: 한 팀이 쥔 채 기다리는 모습입니다. (라)는 두 팀의 기다림이 서로 물려 한 바퀴를 이룬 모습입니다.
3. 교착 상태를 다루는 방법 (가)~(라)의 이름을 한글 이름과 영문으로 함께 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.
- (가) 운영체제가 때때로 '누가 누구를 기다리나'를 그래프로 그려 고리가 있는지 살핍니다.
- (나) (가)에서 고리를 찾으면 그 안의 프로세스 하나를 강제로 끝내 자원을 풀어 줍니다.
- (다) 자원을 요청받을 때마다, 줘도 모두가 끝날 수 있는 순서가 남는지 따져 보고 줍니다.
- (라) 처음부터 '자원을 쥔 채로는 다른 자원을 요청할 수 없다'는 규칙을 둡니다.
정답
받는 답: (가) 발견(Detection) 또는 탐지 · (나) 회복(Recovery) · (다) 회피(Avoidance) · (라) 예방(Prevention)
(가)의 실마리는 '고리가 있는지 살핀다', (나)는 '찾은 뒤 끝내 푼다', (다)는 '줄 때마다 순서가 남는지 따진다', (라)는 '처음부터 규칙으로 조건을 없앤다'입니다.
- 틀리는 꼴 회복 — (가)에: 찾은 교착 상태를 끊는 일입니다. (가)는 찾는 데까지입니다.
- 틀리는 꼴 예방 — (다)에: 조건 하나를 미리 깨 두는 방법입니다. (다)는 조건을 그대로 두고 줄 때마다 따집니다.
- 틀리는 꼴 회피 — (라)에: 요청마다 안전한지 따지는 방법입니다. (라)는 규칙으로 점유와 대기를 아예 없앱니다.
4. 자원 12개를 프로세스 셋이 나눠 씁니다. 지금 상태가 다음과 같을 때 (가)~(다)에 답하세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.
| 프로세스 | 최대 요구 | 가진 것 |
|---|---|---|
| P1 | 7 | 2 |
| P2 | 10 | 6 |
| P3 | 4 | 1 |
- (가) 안전 순서를 쓰세요.
- (나) 지금 P1이 1개를 더 달라고 하면 들어주는지 쓰세요.
- (다) 이렇게 자원을 주기 전에 안전한지 따지는 알고리즘의 이름을 한글 이름과 영문으로 쓰세요.
정답
받는 답: (가) P3 → P2 → P1 · (나) 들어주지 않는다(불안전 상태가 된다) · (다) 은행원 알고리즘(Banker's Algorithm)
(가) 나눠 준 것이 9개라 남은 것은 3개이고, 더 필요한 것은 P1 5 · P2 4 · P3 3입니다. 남은 3으로 P3이 끝나 3 + 1 = 4, 그다음 P2가 끝나 4 + 6 = 10, 마지막으로 P1이 끝납니다.
(나) 주고 나면 남은 것이 2개이고 더 필요한 것은 P1 4 · P2 4 · P3 3이라, 어느 것도 끝낼 수 없습니다.
- 틀리는 꼴 '안전 순서가 없다' — (가)에: 최대 요구를 남은 것과 견줬습니다. 남은 것과 견주는 것은 더 필요한 것(최대 요구 − 가진 것)입니다.
- 틀리는 꼴 '들어준다' — (나)에: 남은 자원이 있으니 준다고 봤습니다. 은행원 알고리즘은 준 뒤에도 안전 순서가 남는지를 봅니다.
- 틀리는 꼴 회피 — (다)에: 방법의 갈래 이름입니다. (다)는 그 갈래의 대표 알고리즘 이름을 물었습니다.