교착 상태
1. 교착 상태 (Deadlock)
1.1 교착 상태란?
-
교착상태는 둘 이상의 작업들이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 어떠한 작업도 이루어지지 않고 진행이 멈춰버리는 현상을 말한다.
-
보통 상호 배제에 의해 나타나는 문제이다.
1.2. 교착 상태 예시
식사하는 철학자 문제
동그란 원탁에 다섯 명의 철학자가 앉아 있다고 해보자. 이 철학자들은 아래와 같은 순서로 식사를 한다.
1. 계속 생각을 하다가 왼쪽 포크가 사용 가능하면 집어든다.
2. 계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어든다.
3. 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사를 한다.
4. 식사 시간이 끝나면 오른쪽 포크를 내려놓는다.
5. 오른쪽 포크를 내려놓은 뒤 왼쪽 포크를 내려놓는다.
6. 다시 1번부터 반복한다.
과연 이 철학자들이 식사를 무사히 마칠 수 있을까?
-> X
만약 모든 철학자가 동시에 왼쪽 포크를 집어들었다면 어떠한 철학자도 다음 단계인 오른쪽 포크를 집어들 수 없을 것이다. 모든 철학자들이 오른쪽 포크를 집어들 수 있을 때까지 기다리고 있기 때문에 이들은 영원히 식사를 할 수 없는 상태에 빠져들게 된다.
이러한 상태를 교착 상태라고 한다.
1.3. 교착 상태의 발생 조건
- 교착상태의 발생에는 4가지 조건이 있다.
- 상호 배제
- 점유와 대기
- 비선점
- 원형대기
1.3.1. 상호 배제
교착 상태가 발생한 근본적인 원인은 해당 자원을 한 번에 하나의 프로세스만 이용 가능하기 때문이다.
위 예시에서 하나의 포크를 동시에 여러 명이 동시에 사용할 수 있다면 교착 상태는 발생하지 않을 것이다.
따라서 하나의 자원에 대해 하나의 프로세스만 허용하는 상호 배제 상황에서 교착 상태가 발생할 수 있다.
1.3.2 점유와 대기
교착 상태가 발생하는 다른 원인은 프로세스가 특정 자원을 보유(점유)한 채 다른 자원을 기다리기(대기) 때문이다.
위 예시에서 '왼쪽 포크'를 집어들고 '오른쪽 포크'가 사용 가능할 때까지 기다렸기 때문에 교착상태가 발생한 것이다.
따라서 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 점유와 대기 상황에서 교착 상태가 발생할 수 있다.
1.3.3. 비선점
교착 상태가 발생하는 또 다른 원인은 프로세스가 다른 프로세스가 점유중인 자원을 뺏을 수 없는, 즉 자원을 비선점하고 있기 때문이다.
위 예시에서 철학자가 다른 철학자의 포크를 뺏을 수 있었다면 교착 상태가 발생하지 않았을 것이다.
따라서 어떤 프로세스도 다른 프로세스의 자원을 강제로 뺏지 못하고 자원을 비선점하는 상황에서 교착 상태가 발생할 수 있다.
1.3.4. 원형 대기
교착 상태가 발생하는 마지막 원인은 프로세스들과 자원의 요청 및 할당이 원 형태를 이루었기 때문이다.
위 예시에서 철학자들이 원형 테이블에 앉아 있었기 때문에 교착 상태가 발생하였다.
따라서 프로세스들이 원의 형태로 자원을 대기하는 원형 대기 상황에서 교착 상태가 발생할 수 있다.
2. 교착 상태 해결 방법
- 운영체제는 교착 상태를 해결하기 위해 크게 예방, 회피, 검출 후 회복 이렇게 3가지 방법을 사용한다.
2.1. 예방
-
운영체제는 애초에 교착 상태가 발생하지 않도록 교착 상태 발생 조건에 부합하지 않게 자원을 분배하여 교착 상태를 예방한다.
-
교착 상태 발생 조건인 상호 배제, 점유와 대기, 비선점, 원형 대기가 발생하지 않게 할당한다면 교착 상태가 발생하지 않을 것이다.
-
각 방법에는 장단점이 존재하지 때문에 상황에 맞게 잘 판단하여 사용하는 것이 좋다.
2.1.1. 상호 배제 예방
-
자원의 상호 배제를 없앤다는 말은 모든 자원을 공유 가능하게 만든다는 의미이다.
-
하지만 모든 자원을 공유한다면 이론상 교착 상태를 없앨 수는 있지만, 현실적으로 모든 자원의 상호 배제를 없애기는 어렵기 때문에 이를 현실에 적용하기에는 무리가 있다.
2.1.2. 점유와 대기 예방
-
점유와 대기를 없애기 위해서는 운영체제가 특정 프로세스에 필요한 자원을 모두 할당하거나, 아예 할당하지 않아야 한다.
-
이 방식 또한 이론적으로는 교착 상태를 예방할 수 있지만, 자원 활용률이 낮다는 단점이 존재한다.
-
하나의 프로세스씩 자원을 몰아주어야 하기 때문에 자원이 필요해도 기다려야하는 프로세스와 사용되지 않으면서 오랫동안 할당되는 자원을 다수 양산하기 때문에 자원의 활용률이 낮아지게 된다.
-
또한 많은 자원을 필요로 하는 프로세스는 모든 자원들을 동시에 사용할 타이밍을 확보하기 어렵기 때문에 무한정 기다리게 되는 기아 상태에 빠질 우려가 있다.
2.1.3. 비선점 예방
-
비선점 조건을 없애면 자원을 이용중인 프로세스로부터 필요한 자원을 빼앗을 수 있다.
-
이 방식은 CPU와 같이 선점하여 사용할 수 있는 일부 자원에 대해서는 효과적이다.
-
하지만 프린트와 같이 이전 프로세스의 작업이 끝날 때까지 다른 프로세스가 기다려야만 하는 자원도 존재하기 때문에 이를 모든 상황에 적용하기는 어렵다.
2.1.4. 원형 대기 예방
-
모든 자원에 번호를 붙이고, 순서대로 자원을 할당한다면 원형 대기가 발생하지 않을 것이다.
-
만약 모든 포크에 번호를 붙이고, 철학자들로 하여금 번호가 낮은 포크 순으로 집어들게 한다면 원형대기가 발생하지 않을 것이다.
- 하지만 이 방법에도 단점이 존재하는데, 컴퓨터 시스템 내에 존재하는 모든 자원에 번호를 붙이는 일이 쉽지 않고, 각 자원에 어떤 번호를 붙이는지에 따라 자원의 활용률이 떨어질 수도 있다.
2.2. 교착 상태 회피
-
교착 상태 회피에서는 한정된 자원의 무분별한 할당으로 인해 교착 상태가 발생한다고 간주한다.
-
따라서 프로세스에 할당할 수 있는 자원이 충분한 상황에서 교착 상태가 발생하지 않을 정도로 적은 자원만을 할당하여 교착 상태를 회피한다.
-
만약 철학자가 사용할 수 있는 포크가 1000개 10000개 있었다면 교착 상태는 발생하지 않았을 것이다.
-
안전 순서열 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
-
안전 상태: 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태, 즉 안전 순서열이 있는 상황
-
불안전 상태: 교착 상태가 발생할 수도 있는 상황, 즉 안전 순서열이 없는 상황
2.2.1. 교착 상태 회피 예시
- 현재 컴퓨터 시스템에 총 12개의 자원 존재
- P1, P2, P3 3개의 프로세스가 실행 중
- P1은 5개, P2는 2개, P3는 2개의 자원을 할당 받아 사용 중
- P1은 10개, P2는 4개, P3는 9개의 자원 요구
- 프로세스와 스레드는 자원을 사용하기 위해 1. 운영체제에 자원 요청 -> 2. 운영체제로부터 자원 할당 받음 -> 3. 자원 사용 후 반환
현재 상황
| 프로세스 | 최대 요구량 | 현재 사용량 |
|---|---|---|
| P1 | 10 | 5 |
| P2 | 4 | 2 |
| P3 | 9 | 2 |
- 할당 가능 자원: 12
- 할당된 자원: 9
- 남은 자원: 3
현재 상황에서의 안전 순서열은 P2 -> P1 -> P3가 된다. (남은 자원으로 완료할 수 있는 순서대로 할당)
P2에 자원 할당
| 프로세스 | 최대 요구량 | 현재 사용량 |
|---|---|---|
| P1 | 10 | 5 |
| P2 | 4 | 2 + 2 |
| P3 | 9 | 2 |
- 할당 가능 자원: 12
- 할당된 자원: 9 + 2 = 11
- 남은 자원: 3 - 2 = 1
P2가 정상적으로 작업을 완료하고 가지고 있던 자원을 반환
| 프로세스 | 최대 요구량 | 현재 사용량 |
|---|---|---|
| P1 | 10 | 5 |
| P3 | 9 | 2 |
- 할당 가능 자원: 12
- 할당된 자원: 11 - 4 = 7
- 남은 자원: 1 + 4 = 5
P1에 자원 할당
| 프로세스 | 최대 요구량 | 현재 사용량 |
|---|---|---|
| P1 | 10 | 5 + 5 |
| P3 | 9 | 2 |
- 할당 가능 자원: 12
- 할당된 자원: 7 + 5 = 12
- 남은 자원: 5 - 5 = 0
P1이 정상적으로 작업을 완료하고 가지고 있던 자원 반환
| 프로세스 | 최대 요구량 | 현재 사용량 |
|---|---|---|
| P3 | 9 | 2 |
- 할당 가능 자원: 12
- 할당된 자원: 12 - 10 = 2
- 남은 자원: 0 + 10 = 10
P3에 자원 할당
P1이 정상적으로 작업을 완료하고 가지고 있던 자원 반환
| 프로세스 | 최대 요구량 | 현재 사용량 |
|---|---|---|
| P3 | 9 | 2 + 7 |
- 할당 가능 자원: 12
- 할당된 자원: 2 + 7 = 9
- 남은 자원: 10 - 7 = 3
마무리
-
이렇게 P2 -> P1 -> P3 라는 안전 순서열 대로 자원을 분배한다면 P1, P2, P3 모두 자원을 할당 받고 교착 상태 없이 작업을 마칠 수 있다.
-
하지만 만약 P3의 초기 사용량이 3이었다면 P1에 자원을 할당할 수 없었을 것이다. 즉, 교착 상태가 발생한다.
-
따라서 교착 상태 회피는 안전 상태를 유지하도록 자원을 할당해야 한다.
3. 교착 상태 검출 후 회복
-
교착 상태 검출 후 회복은 교착 상태 발생을 인정하고 사후에 조치하는 방법
-
검출 후 회복 방식에서 운영체제는 교착 상태 발생 여부를 주기적으로 검사한다.
-
교착 상태가 검출되면 선점, 프로세스 강제 종료와 같은 방식으로 회복한다.
3.1. 선점을 통한 회복
-
교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
-
교착 상태가 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗아 한 프로세스에 할당한다.
3.2. 프로세스 강제 종료를 통한 회복
- 운영체제가 교착 상태에 놓인 프로세스를 모두 강제 종료 or 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료
