🌟 본 게시물은 이화여자대학교 반효경 교수님 강의를 참고로 작성한 게시물 입니다. 틀린 내용은 꼬옥 지적 부탁드립니다 ! 🌟
⚠️ Deadlock
✔️ Deadlock
- 이련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
✔️ Resource(자원)
- 하드웨어, 소프트웨어 등을 포함하는 개념
- (예) I/O device. CPU cycle, memory space, semaphore 등
- 프로세스가 자원을 사용하는 절차
- 요청 (Request),획득 (Allocate),사용 (Use), 반납 (Release)
1. Deadlock 발생의 4가지 조건
✔️ Mutual exclusion (상호배제)
- 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
✔️ No Preemption(비선점)
- 프로세스 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
✔️ Hold and wait
- 내가 가진 자원은 양보하지 않으면서 다른 프로세스의 자원을 기다리면서 보유 자원을 내놓지않고 계속 가지고 있는 현상
✔️ Circular wait
- 자원을 기다리는 프로세스간에 사이클이 형성되어야 함
- 프로세스 P0, P1 …… P5 이 있을 때
- P0은 P1에 가진 자원을 기다림
- P1은 P2가 가진 자원을 기다림
- P2는 P3가 가진 자원을 기다림
- P4는 P0이 가진 자원을 기다림
2. Resource-Allocation Graph (자원할당 그래프)
✔️ Graph에서 Deadlock 확인 방법
그래프에 cycle이 없으면 deadlock이 아니다
그래프에 cycle이 있을 때 자원의 인스턴스가 여러개이면 deadlock 일 수도 있고 아닐수도 있다.
1️⃣ Graph - 1
Vertex
- Process P = {P1, P2, …. Pn}
- Resource R = {R1, R2, …. Rn}
Edge
- R2를 보유한 상태로 P1 → R1 자원을 요청
- R2와 R1을 보유한 상태로 P2 → R3 자원을 요청
- P3가 R3를 보유
DeadLock ?
- P3에 할당된 R3가 해제될 수 있기 때문에 Cycle은 있으나 deadlock은 아니다.
2️⃣ Graph - 2
Vertex
- Process P = {P1, P2, …. Pn}
- Resource R = {R1, R2, …. Rn}
Edge
- R2를 보유한 상태로 P1 → R1 자원을 요청
- R2와 R1을 보유한 상태로 P2 → R3 자원을 요청
- P3가 R3를 보유한 상태로 P3 → R2 요청
DeadLock ?
- 프로세스가 서로 가진 자원을 놓지 않고 다른 자원을 기다리고 있기 때문에 Deadlock 발생
3. Deadlock의 처리 방법
✔️ Deadlock Prevention
✔️ Deadlock Avoidance
✔️ Deadlock Detection and recovery
✔️ Deadlock Ignorance
- Deadlock을 시스템이 책임지지 않음
- UNIX를 포함한 대부분의 OS가 채택
3.1 Deadlock Prevention
자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
✔️ Mutual Exclusion
- 공유해서는 안되는 자원의 경우 반드시 성립해야 함
✔️ Hold and Wait
- 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다
- 방법 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 법
- 방법 2. 다른 필요한 자원이 있으면 보유 자원을 내려놓고 다시 요청
✔️ No Preemption(비선점)
- Process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
- 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
- State를 쉽게 저장할 수 있고 복원할 수 있는 자원에서 주로 사용된다 (CPU, Memory)
✔️ Circular Wait
- 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
- 예를 들어 순서가 3인 자원 R1를 보유 중인 프로세스가 순서가 1인 자원 R2를 할당받기 위해서는 우선 R1를 반납해야한다.
⚠️ 하지만 아직 발생할지 안할지도 모르는 Deadlock을 위와같은 방법으로 미리 예방하게 된다면 사용성을 저하시키고 성능을 감소되는 문제가 발생할 수 있다. 추가로 기아현상의 위험도 발생한다 ⚠️
3.2 Deadlock Avoidance
자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로부터 안전(safe)한지 확인하고 할당한다. 시스템이 unsafe state에 들어가지 않는 것을 보장한다.
프로세스들이 필요로 하는 각 자원을 예측하거나 별 최대 사용량을 미리 선언하도록 하는 방법이다.
✔️ safe state
- 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
- 시스템이 safe state에 있으면 deadlock이 발생하지 않음
✔️ unsafe state
- 시스템이 unsafe state에 있으면 deadlock 발생 가능성이 있음
✔️ avoidance 알고리즘
- Resource Allocation Graph alogorithm
- 자원의 인스턴스가 하나일 경우 사용하는 알고리즘
- Banker’s Algorithm
- 자원의 인스턴스가 여러개일 경우 사용하는 알고리즘
1️⃣ Resource Allocoation Graph Alogorithm
이전에 소개한 Resource Allocoation Graph에서 점선(Clain edge)이 추가된 알고리즘
점선은 미래에 사용될 수 있는 자산을 가리킨다.
✔️ Claim edge
- 프로세스가 자원을 미래에 요구할 수 있다는 것을 뜻함 (점선)
- 프로세스가 해당 자원 요청시 Claime edge가 request edge로 바뀜 (실선)
- 요청자원이 해제되면 assignment edge는 다시 claim edge로 변경됨
✔️ request edge가 assignment edge로 변경 시 (점선을 포함하여) cycle이 생기지 않는 경우에만 요청 자원을 할당한다.
✔️ Cycle 생성 여부 조사시 프로세스의 수가 n일 때 O(n2)시간이 걸린다.
✔️ Resource Allocoation Graph Alogorithm 예시
- P1과 P2가 미래에 R2를 요청할 가능성이 있음.
- P2가 R1을 요청한 상태로 R2자원을 요청함.
- P2가 R2을 할당받음 하지만 실제로 Resource Allocoation Graph Alogorithm 점선을 포함하여 cycle이 생성될 경우 자원을 내어주지 않기 때문에 R2를 할당받지 못한다. P2가 R2를 할당받으려면 R1을 소유하고 있는 P1이 R2를 할당받은 후 P1의 작업이 끝나서 R1과 R2가 해제될 때 P2가 할당받을 수 있다.
2️⃣ Banker’s Algorithm
자원의 인스턴스가 여러개일 경우 사용되는 알고리즘
모든 프로세스의 자원의 최대 사용량을 미리 명시하여 최대 사용량이 available 가능한 자원으로 충족 될 경우에만 자원을 내어준다.
✔️ 가정
- 모든 프로세스는 자원의 최대 사용량을 미리 명시한다.
- 프로세스가 요청 자원을 모두 할당받은 경우 유한시간 안에 이들 자원을 다시 반납한다.
✔️ 방법
- 기본 개념 : 자원 요청시 safe 상태를 유지할 경우에만 할당
- 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택함 만약 그런 프로세스가 없다면 unsafe한 상태
- 그런 프로세스가 있으면 그 프로세스에게 자원을 할당
- 할당받은 프로세스가 종료되면 모든 자원을 반납
- 모든 프로세스가 종료될 때까지 이러한 과정을 반복
✔️ Banker’s Algorithm 예시
Allocation
- 현재 소유하고 있는 자원
Max
- 최대로 요청할 수 있는 자원의 수
Available
- 가용 자원의 수
Need
- 앞으로 요청할수도 있는 남은 자원의 수 (Max - Allocation)
✔️ 5개의 프로세스가 존재한다고 가정한다.
✔️ 3개의 자원이 존재한다 A(10), B(5), C(7) 각 자원은 10, 5, 7개의 인스턴스를 가지고 있다.
✔️ 현재 가용 자원보다 Need 자원의 더 클 경우에 해당 프로세스는 자원을 할당받지 못한다. 자원 할당이 가능한 프로세스를 순서대로 나열하면 <P1, P3, P4, P2, P0> 이 된다.
3.3 Deadlock Detection and recovery
Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover한다.
Resource type 당 single instance인 경우 자원할당 그래프에서의 cycle이 곧 deadlock을 의미한다.
Resource type 당 multiple instance인 경우 Banker’s algorithm과 유사한 방법을 활용한다.
1️⃣ Wait-for graph Algorithm
- 자원당 하나의 인스턴스를 가지고 있을 경우 사용됨
- Wait-for graph
- 자원할당 그래프의 변형
- 프로세스만으로 node를 구성함
- P1이 가지고 있는 자원을 P2가 기다리는 경우 P2 → P1
- Avoidance에선 P2 → R1 → P1
- 그래프에 점선이 없음
- Algorithm
- Wait-for graph에 사이클이 존재하는지를 주기적으로 조사함 O(n2)
⚠️ Graph에 Cycle이 존재할 경우 Deadlock Detection ⚠️
2️⃣ Multiple instance인 경우에 사용되는 알고리즘
Banker’s Algorithm 과 비슷하지만 최대 요청가능한 자산을 예측하지 않고 Allocation, Request, Available 만 관리한다.
사용중인 자원을 해제한다는 가정하에 가용자원으로 safe sequence를 확인해보면 <P0, P2, P3, P1, P4> 와 같은 순서가 나타난다.
🌟 Request는 추가요청가능량이 아니라 현재 실제로 요청한 자원량을 나타낸다 🌟
✔️ Recovery
- Process termination
- Deadlock에 연루된 모든 프로세스를 Abork 한다.
- Deadlock에 연루된 프로세스를 하나씩 Abork 해보고 해결되는 지 확인한다.
- Resource Preemption
- Deadlock에 연루된 프로세스 중에 비용을 최소화할 victim을 선점하여 자원을 뺏는다.
- Safe State로 Rollback하여 Process를 재시작한다.
- Stavation 문제 발생 위험
- 동일한 프로세스가 계속해서 victim으로 선점되는 경우
- cost factor에 Rollback횟수도 고려한다.
- 동일한 프로세스가 계속해서 victim으로 선점되는 경우
3.4 Deadlock Ignorance
Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는 방법으로 대부분의 범용 OS가 채택한 방법이다.
Deadlock은 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있다
만약, 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사용자가 느낀 후 직접 process를 죽이는 방법 등으로 대처한다.
Reference
이화여자대학교 반효경 교수님 운영체제 강의