deadlock (교착 상태) :
일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태.
Resource (자원) :
- 하드웨어, 소프트웨어 등을 포함하는 개념
- ex) I/O device, CPU cycle, memory space, semaphore 등
- 프로세스가 자원을 사용하는 절차 : Request, Allocate, Use, Release
Deadlock Example 1
- 시스템에 2개의 tape drive가 있다.
- 프로세스 P1과 P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다.
Deadlock Example 2
- binary semphores A and B (아래 캡처)
--> 즉 P0, P1 모두 A, B 둘 다 필요한 상황에서 P0은 A를, P1은 B를 가지고 있어 서로 아무것도 하고 있지 못한 상태.
Deadlock 발생의 4가지 조건
1. Mutual exclusion (상호 배제) :
매 순간 하나의 프로세스만이 자원을 사용할 수 있음
2. No preemption (비선점) :
프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않기 때문에 본인이 차지한 자원을 내주지 않다가 다른 프로세스사 해당 자원을 필요로 하는 경우에 데드락이 생길 수 있음.
3. Hold and wit (보유 대기) :
자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
4. Circular wait (순환 대기) :
- 자원을 기다리는 프로세스간에 사이클이 형성되어야 함
- ex) P0, P1,,,Pn이 있을 때 P0은 P1이 가진 자원을, P1은 P2가 가진 자원, Pn-1은 Pn이 가진 자원, Pn은 P0이 가진 자원을 기다림.
Resource-Allocation Graph (데드락이 발생했는지 알아보는 방법)
위 그림은 P1이 R2를 가지고 있고, R1을 요청하고 있고, P2는 R2, R1을 가지고 있고 R3을 요청하고 있고, P3는 R3을 가지고 있다.
해당 그래프에서 데드락이 발생하고 있는지 알 수 있는지는 사이클의 유무이다.
만약 그래프에 사이클이 없으면 deadlock이 아니고, 사이클이 있는 경우라면
if only one instance per resource type, then deadlock
if several instances per resource type, possibility of deadlock
아래의 그래프를 보고 따져보자.
결론부터 말하면 왼쪽은 데드락, 오른쪽은 데드락이 아니다.
왼쪽의 경우 R2 -> P1 -> R1 -> P2 -> R3 -> P3 -> R2 로 이어지는 사이클을 볼 수 있다. R1, R3은 하나의 resource들 만을 가지고 있고, R2는 2개의 resource를 가지고 있지만 각각 한개는 P1, 한개는 P2로 사이클을 이루는 프로세스에게 할당되어 있기 때문이다.
오른쪽의 경우에도 R2 -> P1 -> R1 -> P3 -> R2로 이어지는 사이클을 볼 수 있다. 하지만 R1와 R2 각각의 리소스는 사이클을 이루지 않는 P2, P4에게 할당하고 있으므로 P2, P4가 자원을 반납하면 사이클을 사라질 것이다.
Deadlock의 처리 방법
• Deadlock Prevention
- 자원 할당 시 deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것.
• Deadlock Avoidance
- 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당.
- 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당.
• Deadlock Detection and recovery
- deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover
• Deadlock Ignorance
- Deadlock을 시스템이 책임지지 않음
- UNIX를 포함한 대부분의 OS가 채택
하나씩 알아보자.
Deadlock 처리방법 1. Deadlock prevention
Mutual exclusion (상호 배제) :
- 공유해서는 안되는 자원의 경우 반드시 성립해야 함.
Hold and wit (보유 대기) :
- 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
- 방법1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법 <-- 이는 매우 비효율적인 방법이다.
- 방법2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청(hold하고 있는 자원을 모두 내려 놓고 받고 싶은 자원을 받음)
No preemption (비선점) :
- process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
- 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
- State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용(CPU, memory)
Circular wait (순환 대기) :
- 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당.
- 예로 특정 P1이 R5를 이미 가지고 있고, P1이 R1, R3, R5(나열 순서는 우선 순위 순)를 필요로 한다면 R1를 차지하기 위해서는 현재 가 지고 있는 R5를 릴리지 해야 하는 것이다.
➡️➡️➡️ Deadlock prevention의 방법들은 Utilization 저하, throughput 감소, starvation 문제가 발생할 수 있다.
Deadlock 처리방법 2. Deadlock Avoidance
deadlock avoidance :
- 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로 부터 안전(safe)한지를 동적으로 조사해서 안전한 경우에만 할당
- 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법임.
- deadlock prevention과 마찬가지로 사전에 deadlock을 막는 방법.
safe state
- 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
safe sequence
- 프로세스의 sequence <P1, P2,,,,Pn>이 safe하려면 Pi(1 <= i <= n)의 자원 요청이 가용 자원 + 모든 Pj(j < i)의 보유 자원에 의해 충족되어야 함
- 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
--- Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj(j<i)가 종료될 때까지 기다린다.
--- Pi+1이 종료되면 Pi의 자원요청을 만족시켜 수행한다.
시스템이 safe state에 있으면 --> no deadlock
시스템이 unsafe state에 있으면 possibility of deadlock
Deadlock Avoidance는 시스템의 unsafe state에 들어가지 않는 것을 보장한다.
2가지의 경우의 avoidance 알고리즘이 존재함.
• Single instance per resource types (자원 당 인스턴스가 하나만 있는 경우)
- Resource Allocation Graph algorithm 사용
• Multiple instances per resources types (자원 당 인스턴스가 여러 개 있는 경우)
- Banker's Algorithm 사용
• Resource Allocation Graph algorithm
위 그림에서 P1 ---> R2로의 점선은 평생 P1이 R2에게 자원을 요청할 수 있음을 뜻한다.(P2 ---> R2도 마찬가지)
그래서 만약 아래 처럼 P2 ---> R2의 요청이 일어났다고 하면 아래의 그림과 같이 될 것이다.
(P2가 R2의 자원 요청)
이제 R2를 P2에게 할당하면 아래와 같이 될 것이다.
그런데 이제 사이클이 형성되었다. 즉 unsafe한 상태가 된 것이다. 해서 resource allocation graph algorithm에선 2번 그림의 상황에서 P2에게 R2를 주지 않는다. 아예 unsafe한 상태로 가는 것을 사전에 막는 것이다.
• Banker's Algorithm
프로세스가 자원을 요청했을 때 그 요청을 받아들일지, 거부할지를 정하는 알고리즘이다.
• 가정
- 모든 프로세스는 자원의 최대 사용량을 미리 명시
- 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 이들 자원을 다시 반납한다.
• 방법
- 기본 개념: 자원 요청시 safe 상태를 유지할 경우에만 할당
- 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택(그런 프로세스가 없으면 unsafe 상태)
- 그런 프로세스가 있으면 그 프로세스에게 자원을 할당
- 할당받은 프로세스가 종료되면 모든 자원을 반납
- 모든 프로세스가 종료될 때까지 이러한 과정 반복
* 3 resource types : A(10), B(5), C(7)
* Allocation : 현재 각 프로세스들이 배정받은 자원
* Max : 각 프로세스들이 최대로 요청할 수 있는 자원의 수
* Available : 프로세스들에게 할당하고 남은 자원들
* Need : Max - Allocation을 뺀 것. 즉 앞으로 최대 요청할 수 있는 자원의 수
위의 캡처 이미지에서 처럼 Need <= Aailable을 계산하여 true라면 자원을 빌려줘도 되고, false인 경우에는 빌려주지 않으면 된다.
➡️➡️➡️ 하지만 자원이 남아있는데도 데드락을 방지하기 위해 자원을 주지 않으므로 매우 비효율적인 방법이다.
Deadlock 처리방법 3. Deadlock Detection and Recovery
• Deadlock Detection
• Resource type 당 single instance인 경우. <-- 자원할당 그래프에서의 cycle이 곧 deadlock을 의미
• Resource type 당 multiple instance인 경우. <-- Banker's algorithm과 유사한 방법 활용
• Wait-for graph 알고리즘
• Resource type 당 single instance인 경우
• Wait-for graph
---- • 자원 할당 그래프의 변형
---- • 프로세스만으로 node 구성
---- • Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk -> Pj
• Algorithm
---- • Wait-for graph에 사이클이 존재하는지를 주기적으로 조사
---- • O(n^2)
그래프를 그려보면 아래와 같다. 오른쪽 wait for graph를 보면 2개의 사이클이 나타나는 것을 알 수 있다.
아래와 같이 벡터 형태의 표를 그려 표현하는 방법이 그래프를 그리는 것보다 더 좋은 방법이다.
*allocation : 현재 가지고 있는 것. request: 현재 요청 한 것.
만약 P2가 C를 요청하여 이를 할당해준다면 deadlock이 발생할 수 있다.
만약 deadlock이 발생하면 아래의 방법으로 recovery를 해준다.
Recovery
• Process termination(프로세스 강제 종료)
- abort all deadlocked processes (deadllock에 연루된 모든 프로세스 kill)
- abort one process at a time until the deadlock cycle is eliminated (deadlock에 연루된 프로세스들 하나씩 kill)
• Resource Preemption(자원 뺏기)
- 비용을 최소화할 victim의 선정
- safe state로 rollback하여 process를 restart
- starvation 문제
---- 동일한 프로세스가 계속해서 victim으로 선정되는 경우
---- cost factor에 rollback 횟수도 같이 고려
Deadlock 처리방법 4. Deadlock Ignorance
deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는 방법
- Deadlock은 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있음
- 만약 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 등 방법으로 대처
- UNIX, Windows 등 대부분의 범용 OS가 채택
출처 : 이화대학교 반효경 교수님의 운영체제 강의
http://www.kocw.net/home/search/kemView.do?kemId=1046323
'EH 운영체제 강의' 카테고리의 다른 글
| Memory Management (0) | 2022.08.23 |
|---|---|
| Process Synchronization (0) | 2022.07.10 |
| CPU 스케쥴링 (0) | 2022.07.01 |
| 5. 프로세스 - 스레드 (0) | 2022.06.21 |
| 4. 프로세스 (0) | 2022.05.20 |
