오늘은 이어서 교착 상태에 대해서 알아보겠습니다.🧐
1. 교착 상태(Deadlock)란?
✅ 자원이 한정적인 상황에서 두 개 이상의 프로세스가 각자 먼저 확보한 자원을 가진 채 상대방의 자원을 필요로 할 경우 아무 일도 못하고 계속 기다리는 교착 상태(Deadlock)에 빠지게 됩니다.
교착 상태에 빠지면 2가지의 문제점이 발생합니다.
-
해당 프로세스들이 더 이상 실행되지 못하여 사용자들에게 응답을 해주지 못합니다.
-
보유된 자원들이 교착 상태에서 벗어나기 전까지는 전혀 활용되지 못합니다.
➡️ 이는 시스템의 성능 저하로 이어집니다.
다음 내용으로 넘어가기 전 교착 상태와 비슷한 개념인 무한 대기 현상에 대해서 알아보겠습니다.
교착상태 vs 무한대기
- 운영체제가 프로세스들의 다양한 요청을 처리해 주다가 보면 몇몇 프로세스가 매우 오랜 시간 동안 서비스를 받지 못하는 경우를 무한대기라고 합니다.
무한 대기가 교착 상태와 다른 점은 오랜 시간 후에라도 외부적 조치 없이 무한 대기로 부터 벗어나 서비스를 받을 수 있다는 점입니다.
2. 자원이란?
자원은 교착 상태(Deadlock)을 일으키는 원인입니다.
그렇기 때문에 이 자원에 대해서 확실히 알고 넘어가야 할 필요가 있습니다. 앞으로 말하는 모든 자원은 소프트웨어 자원이라고 생각하시면 됩니다.
자원은 여러가지 기준에 따라 분류를 할 수 있습니다.
선점 가능성
➡️ 선점 가능성에 따라 선점 가능 자원(Preemptible)과 선점 불가능 자원(Nonpreemptible)으로 나눌 수 있습니다.
- 선점 가능 자원(Preemptible):
CPU나 메모리와 같은 자원처럼 한 프로세스에 의해 사용 도중 선점되어 다른 프로세스에게 할당해 주어다가 이 후 다시 원래의 프로세스에게 돌려주어도 되는 자원을 의미합니다.
- 선점 불가능 자원(Nonpreemptible):
선점이 될 경우 자원을 뺏긴 프로세스는 정상적인 진행을 포기해야 하는 불이익을 받게 되는 경우의 자원을 의미합니다.
사용 방식
➡️ 사용 방식에 따라 공유 가능 자원(Sharable)과 배타적 사용 자원(Exclusive Use)으로 분류할 수 있습니다.
- 공유가능 자원(Sharable):
한 프로세스에게 할당된 자원을 동시에 다른 프로세스가 할당받아 같이 사용할 수 있는 자원
- 배타적 사용 자원(Exclusive Use):
한 프로세스에게 할당된 자원을 동시에 다른 프로세스가 할당받아 같이 사용할 수 없는 자원
속성
➡️ 자원의 속성에 따라 순차적 재사용 가능 자원(Serially Reusable)과 소모성 자원(Consumable)으로 분류할 수 있습니다.
- 순차적 재사용 가능 자원(Serially Reusable):
할당된 자원이 사용 후 반납되었을 때 자원 자체는 계속 존재하여 또 다른 프로세스에게 할당이 가능한 자원입니다.
- 소모성 자원(Consumable):
사용 후 사라지는 자원입니다.
3. 교착 상태의 원인
✅ 교착 상태의 원인은 총 4가지가 있습니다. 이 4가지의 조건이 다 갖춰질 경우에만 교착 상태가 발생합니다.
1. 자원의 배타적인 사용
만약 자원이 모두 공유가 가능한 자원이라면 교착 상태가 발생하지 않을 것입니다.
결국 배타적으로 사용이 요구되는 자원이 있기 때문에 교착 생태가 발생합니다.
이를 상호배제 조건(Mutual Exclusion Condition)이라고도 합니다.
2. 자원의 부분 할당(Partial Allocation)
프로세스는 자신의 실행 전체 과정에서 필요한 자원을 필요할 때마가 일부분씩 확보하고 실행해 나갑니다.
그러다 어느 시점에 할당이 불가능한 자원 때문에 이미 확보한 자원들을 소유한 채 대기 상태가 되어 버려 교착 상태에 빠질 가능성이 커지게 되는 것입니다.
3. 자원의 선점 불가능성
자원을 선점 당하게 되면 프로세스는 정상적인 실행을 포기해야 합니다. 즉 이럴 경우 교착 상태의 원인이 될 수 있습니다.
이를 비선점(No Preemption) 조건이라고도 합니다.
4. 자원에 대한 환형 대기(Circular-Wait)
출처 : https://www.geeksforgeeks.org/introduction-of-deadlock-in-operating-system/
프로세스들이 자신의 자원은 보유한 채로 서로 상대방의 자원을 요청할 때 환형 대기가 생깁니다.
이렇게 대기 상태가 되어 버리면 교착 상태가 발생할 수 있는 원인이 됩니다.
4. 교착 상태 해결 기법
➡️ 교착 상대의 해결을 위한 기법들은 총 4가지로 분류할 수 있습니다. 예방, 회피, 탐지, 복구 기법입니다.
각각에 대해서 살펴보도록 하겠습니다.
1. 예방 기법
1-1. 자원의 배타적 사용 조건을 배제
모든 자원을 공유 가능 자원으로 하여 교착 상태의 발생을 차단 시키는 방법입니다.
시스템이 보유한 자원 중에는 배타적으로 사용할 수밖에 없는 자원들이 있습니다.
따라서 이 방법으로 교착 상태를 예방하는 것은 불가능합니다.
1-2. 자원의 부분 할당을 배제
각 프로세스들은 각자 자신이 필요한 모든 자원을 미리 할당받아 실행을 시작하도록 하는 방법입니다.
=> all at one, all or none
1-3. 자원의 선점 불가능을 배제
일부 자원을 가지고 실행하던 프로세스가 현재 할당이 불가능한 자원을 요청할 경우 자신이 보유하고 있던 자원을 내 놓게 합니다.
하지만 실행 도중 보유한 자원을 내놓게 되면 비정상적인 종료와 처음부터 다시 시작해야 하는 상황이 발생할 수 있습니다.
1-4. 자원의 환형 대기 상활을 배제
자원들의 순서를 정하고 프로세스들은 이 순서를 지켜 요청하도록 함으로써, 사이클이 발생될 소지를 없애 교착 상태를 없앤 방법입니다.
이 방식은 자원의 낭비와 무한 대기를 발생 시킬 수 있습니다.
2. 회피 기법
✅ 회피 기법의 대표적인 알고리즘의 은행가 알고리즘(Banker's Algorithm)입니다.
-
안전 상태: 모든 프로세스가 유한 시간 내에 정상적으로 종료될 수 있는 상태입니다.
-
불안전 상태: 유한 시간 내에 정상적으로 종료될 수 없는 상태입니다.
[은행가 알고리즘]
다익스트라의 은행가 알고리즘이 제대로 작동하기 위해서는 시스템에 대한 다음과 같은 가정이 요구됩니다.
- 시스템 내의 프로세스 수가 고정되어 있어야 한다.
- 자원의 수 역시 고정되어 있어야 한다.
- 각 프로세스가 요구할 자원의 최대 개수가 알려져야 한다.
- 각 프로세스는 할당받은 자원을 사용 후 반드시 반납하여야 한다.
출처: http://truemind5.blogspot.com/2017/04/12-3.html
3. 탐지 기법
✅ 탐지 기법은 교착 상태를 찾아내는 기법을 말합니다.
탐지를 위해서 자원 할당 그래프(Resource Allocation Graph, RAG)를 통해서 현 시스템 상황을 표현합니다.
그래프 제거 법으로 교착 상태를 탐지합니다.
[상황별 그래프]
➡️ 그림의 (a) 상황에서 P3 같이 자원으로 향하는 에지가 없는 프로세스를 unblocked process 또는 싱크(Sink)라고 부릅니다.
➡️ 한 자원 형에 다수 개의 자원이 있을 경우에는 노트(Knot)라는 자료 구조의 발견이 곧 교착 상태의 발견이 됩니다.
4. 복구 기법
✅ 복구 기법에는 프로세스 종료 방식과 자원의 선점에 의한 방식으로 나눠서 볼 수 있습니다.
1. 프로세스 종료 방식
교착 상태를 형성한 프로세스들 중 몇 개를 강제로 종료시켜 이들로부터 반납된 자원으로 복구를 하는 방식입니다.
2. 자원의 선점에 의한 방식
필요한 자원을 가지고 있는 프로세스로부터 강제로 뺏어(선점하여) 교착 상태에 있는 프로세스들에게 줌으로써 해결하는 방식입니다.
자원이 선점 당하는 프로세스는 강제 종료가 됩니다. 이런 강제 종료 시의 낭비를 줄이기 위한 방법으로는 검사정 지정(Checkpointing)과 재시작(Restart)이 있습니다.
프로세스들은 실행의 중간 중간에 그 시점까지의 실행 결과를 보존하고 표시를 해 두는데 이를 검사점(Checkpoint)라고 합니다.
그리고 나중에 검사점에서 보존된 내용으로 재시작을 할 수 있게 됩니다.
마무리
오늘은 교착 상태에 대해서 알아보았습니다.
다음 시간에는 메모리로 넘어가 어떻게 관리하는지에 대해서 알아보겠습니다.
