[문과 코린이의 IT 기록장] 운영체제(OS) - Deadlock(교착상태) (The Deadlock Problem, Deadlock 발생의 4가지 조건, Resource-Allocation Graph (자원할당 그래프), Deadlock의 처리 방법)
[문과 코린이의 IT 기록장] 운영체제(OS) - 운영체제(운영체제(OS)란?, 운영체제(OS)의 기능 및 목표,
[문과 코린이의 IT 기록장] 운영체제(OS) - 운영체제(운영체제(OS)란?, 운영체제(OS)의 기능 및 목표, 운영체제의 분류, 몇 가지 용어, 운영체제의 예, 운영체제의 개괄적인 구조) 운영
vansoft1215.tistory.com
[문과 코린이의 IT 기록장] 운영체제(OS) - System structure & Program execution (컴퓨터 시스템 구조, 동기
[문과 코린이의 IT 기록장] 운영체제(OS) - System structure & Program execution (컴퓨터 시스템 구조, 동기식 입출력과 비동기식 입출력, 서로 다른 입출력 명령어, 저장장치 계층 구..
vansoft1215.tistory.com
[문과 코린이의 IT 기록장] 운영체제(OS) - 프로세스(Process) (프로세스의 개념, 프로세스의 상태 (Pro
[문과 코린이의 IT 기록장] 운영체제(OS) - 프로세스(Process) (프로세스의 개념, 프로세스의 상태 (Process State), PCB, 문맥 교환 (Context Switch), 프로세스를 스케줄링 하기 위한 ..
vansoft1215.tistory.com
[문과 코린이의 IT 기록장] 운영체제(OS) - Process Management (프로세스 생성 (Process Creation), 프로세스
[문과 코린이의 IT 기록장] 운영체제(OS) - Process Management (프로세스 생성 (Process Creation), 프로세스 종료 (Process Termination), fork() 시스템 콜, exec() 시스템 콜, wait(..
vansoft1215.tistory.com
[문과 코린이의 IT 기록장] 운영체제(OS) - CPU 스케줄링 (CPU and I/O Bursts in Program Excution, CPU Scheduler &
[문과 코린이의 IT 기록장] 운영체제(OS) - CPU 스케줄링 (CPU and I/O Bursts in Program Excution, CPU Scheduler & Dispatcher, Scheduling Criteria (성능 척도), Scheduling Algorit..
vansoft1215.tistory.com
[문과 코린이의 IT 기록장] 운영체제(OS) - Process Synchronization(프로세스 동기화) (데이터의 접근, Rac
[문과 코린이의 IT 기록장] 운영체제(OS) - Process Synchronization(프로세스 동기화) (데이터의 접근, Race Condition (경쟁 상태), OS에서의 Race Condition, Process Synchronization(=..
vansoft1215.tistory.com
1. The Deadlock Problem
ex. 각자 일부 자원은 지니고 있으면서, 상대방이 가진 자원을 요구하고 있는데, 상대방도 자신이 가진 자원을 내놓지 않고 다른 자원을 요구할 경우 발생하는 문제
1) Deadlock
: 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
2) Resource (자원)
: 자원은 하드웨어 자원과 소프트웨어 자원을 모두 포함하는 개념이다.
ex. I/O device, CPU cycle, Memory space, Semaphore
* 프로세스가 자원을 사용하는 절차 : Request -> Allocate -> Use -> Release
3) Deadlock Example
a. 시스템에 2개의 tape drive가 있는 경우, 프로세스 P1과 P2 각각이 하나의 tape drive1, tape drive 2를 각각 보유한 채 다른 하나를 기다리게 될 경우 발생
b. semaphore를 사용하는 경우, CPU가 프로세스에게 가더라도 둘 A,B 둘 중 하나는 획득이 안되므로 발생
P0 P1
P(A); P(B);
P(B); P(A);
2. Deadlock 발생의 4가지 조건
# 아래의 네 가지 조건을 모두 만족해야 deadlock이 발생한다.
1) Mutual exclusion (상호 배제)
- 매 순간 하나의 프로세스만이 자원을 사용할 수 있음.
- 즉, 자원을 얻은 후에는 그 프로세스가 독점적으로 쓰게 된다. (공유가 불가능함)
2) No preemption (비선점)
- 프로세스는 자원을 스스로 내어놓을 뿐, 강제로 빼앗기지 않음.
3) Hold and wait (보유 대기)
- 자원을 가진 프로세스가 다른 자원을 기다릴 때, 보유 자원을 놓지 않고 계속 가지고 있음.
- 즉, 자발적으로도 자원을 놓아주지 않아야 함.
4) Circular wiat
- 자원을 기다리는 프로세스간에 사이클이 형성되어야 함.
- 즉, 필요로 하는 자원들이 꼬리에 꼬리를 물고, 서로가 가진 자원을 기다리면서 사이클을 형성해야 한다.
ex.
프로세스 P0, P1, ... Pn이 있을 때
P0는 P1이 가진 자원을 기다림
P1는 P2가 가진 자원을 기다림
Pn-1은 Pn이 가진 자원을 기다림
Pn은 P0가 가진 자원을 기다림
3. Resource-Allocation Graph (자원할당 그래프)
* Deadlock이 발생했는지는, 보통 자원할당 그래프라는 것을 그려서 알아볼 수 있다.
- 화살표의 의미
* 자원 -> 프로세스 : 자원이 프로세스에 속해있다. (이 프로세스가 자원을 가지고 있다.)
* 프로세스 -> 자원 : 프로세스가 이 자원을 요청하고 있다. 그러나, 획득하지는 못한 상태이다.
- 위 그림은 이어지는 사이클이 없기 때문에, Deadlock이 아니다.
| - 그래프에 Cycle이 없으면 Deadlock이 아니다. - 그레프에 Cycle이 있으면 : 만약 자원당 인스턴스가 하나밖에 없다면 사이클은 데드락 걸림 : 만약 자원당 인스턴스가 여러개 있는 상항이면, 데드락일 수도 아닐 수도 있음. |
ex 1 ) 사이클이 두개가 만들어졌으므로, 자원 두개가 있음에도 불구하고 진행이 불가능한 상황이 됨. 따라서 Deadlock 발생
ex 2 ) 사이클이 있음에도 불구하고, P2와 P4가 자원을 반납하면 데드락 문제가 해결됨. 따라서 Deadlock이 아님.
4. Deadlock의 처리 방법
| 1) Deadlock Prevention - 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것 2) Deadlock Avoidance - 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당 - 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당 3) Deadlock Detection and recovery - Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어, deadlock 발견시 recover 4) Deadlock Ignorance - Deadlock을 시스템이 책임지지 않음. 문제가 생긴다면, 사람이 프로세스를 죽이는 등의 방법으로 이를 해결 - UNIX를 포함한 대부분의 OS가 채택 (Deadlock은 빈번하게 발생하는 이벤트가 아니기 때문에 사용할 수 있는 방법, 오히려 미리 방지하는게 오버헤드가 더 큼) |
* 1) ,2)의 방법은 Deadlock이 생기지 않게 미리 방지하는 방법
* 3)의 방법은 Deadlock이 있는지 탐색 후, 발견시 recover하는 방법
* 4)의 방법은 Deadlock에 대해 관여하지 않는 방법
** 위로 갈수록 더 강한 처리방법
1) Deadlock Prevention
- Deadlock이 발생하는 4가지 필요 조건 중, 하나를 원천적으로 차단해서 Deadlock에 들어가지 못하게 하는 방법
(1) Mutual exclusion
- 이는 반드시 성립해야함. 따라서 이를 막을 수는 없음
(2) Hold and Wait
- 프로세스가 자원을 요청할 때, 다른 어떤 자원도 가지고 있지 않아야 한다.
방법 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
* 프로세스가 종료될 때 모든 자원을 반납함. 추가로 필요한 자원이 없음
** 자원을 사용하는데 비효율적인 방법
방법 2. 자원이 필요할 경우, 보유 자원을 모두 놓고 다시 요청
* 자진반납으로 인한 문제해결
(3) No Preemption
- 프로세스가 어떤 자원을 기다려야 하는 경우, 이미 보유한 자원이 선점됨
- 모든 필요한 자원을 얻을 수 있을 때, 그 프로세스는 다시 시작된다.
- State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용 (CPU, Memory)
* 즉 자원을 preemption(선점)할 수 있게 해주면 됨. save와 restore할 수 있는 자원은 선점할 수 있게 해주고, 특정 자원만 선점할 수 없게 하면 됨.
(4) Circular Wait
- 모든 자원 유형에 할당 순서를 정하여, 정해진 순서대로만 자원 할당
ex. 순서가 3인 자원 R3를 보유중인 프로세스가, 순서가 1인 자원 R1를 할당받기 위해서는, 우선 R3를 먼저 보유해야 한다.
# Deadlock Prevention 방법은 deadlock을 원천적으로 막을 수는 있지만, 그 자원에 대한 이용률(Utilization)이 낮아지고, 처리량(Throughput)을 감소시켜 전체 시스템의 성능을 나쁘게 만들며, Starvation이 발생할 수 있다는 단점을 지니고 있다.
# 가끔 발생하는 event인 deadlock을 생각해서, 이와 같이 제약조건을 많이 달아놓는 것은 상당히 비효율적이다.
2) Deadlock Avoidance
- 자원 요청에 대한 부가정보를 이용해서, 자원 할당이 deadlock으로부터 안전(safe)한지를 동적으로 조사해서 안전한 경우에만 할당.
- 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법임.
| 1) safe state : 시스템 내의 프로세스들에 대한 2) safe sequence가 존재하는 상태 2) safe sequence : 프로세스의 sequence <P1, P2, ..., Pn>이 safe하려면, Pi(1<=i<=n)의 자원 요청이 '가용 자원 + 모든 Pi(j<i)의 보유 자원'에 의해 충족되어야 함. : 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장 * Pi의 자원 요청이 즉시 충족될 수 없으면, 모든 Pj(j<i)가 종료될 때까지 기다린다. * Pi-1이 종료되면, Pi의 자원요청을 만족시켜 수행한다. |
- 시스템이 safe state에 있으면 : No deadlock
- 시스템이 unsafe state에 있으면 : possibility of deadlock
# Deadlock Avoidance는 시스템에 unsafe state에 들어가지 않는 것을 보장한다.
(1) Single instance의 경우 알고리즘 : Resource Allocation Graph alogirthm(자원할당 그래프) 사용
* 즉 점선은 적어도 이 자원을 한번은 프로세스에서 사용할 일이 있다는 것.
** avoidance는 프로세스가 시작될 때, 평생에 사용할 자원을 선언하고 deadlock을 피해가는 것.
** deadlock의 가능성이 있는 자원요청에 대해서, 애초부터 받아들이지 않고 놔두는 것.
(2) Multiple instance의 경우 알고리즘 : Banker's Algorithm 사용
[ 가정 ]
- 모든 프로세스는 자원의 최대 사용량을 미리 명시함
- 프로세스가 요청 자원을 모두 할당받은 경우, 유한시간 안에 이들 자원을 다시 반납한다.
[ 방법 ]
- 기본 개념 : 자원 요청시 safe상태를 유지할 경우에만 할당
- 총 요청 자원의 수가, 가용 자원의 수보다 적은 프로세스를 선택 (그런 프로세스가 없으면 unsafe 상태)
- 그런 프로세스가 있으면, 그 프로세스에게 자원을 할당
- 할당받은 프로세스가 종료되면 모든 자원을 반납
- 모든 프로세스가 종료될 때까지 이러한 과정 반복
example )
프로세스 5개 : P0, P1, P2, P3, P4
자원 타입 3개 : A(10), B(5), C(7)
1) P1이 (1,0,2)를 요청하는 경우.
- P1 Need (1,2,2) <= Available (3,3,2) 성립 O
: P1같은 경우는 앞으로 최대 추가 요청을 하더라도, Available의 현재 자원으로 모두 처리할 수 있다. 즉 deadlock으로부터 안전하다.
2) P0가 (0,2,0)을 요청하는 경우
- P0 Need (7,4,3) <= Available(3,3,2) 성립 X
: P0같은 경우는 최대 추가 요청을 할 경우, Available의 현재 자원으로 모두 처리할 수 없다. 즉 만약 이들이 최대요청을 할 경우, 프로세스를 처리하지 못하고 자원이 다시 반납될 때까지 기다려야 할 가능성이 있다. 따라서 자원이 남아있어도, 이들의 요청을 받아들이지 않는다.
3) P1이 (1,0,0)을 요청하는 경우
- P1(1,2,2) <= Available(3,3,2) 성립 O
: 이제 P1은 본인이 최대로 요청할 A자원을 모두 받았기 때문에, 더 요청할 일은 없으며 반납할 일만 남았다. 따라서 무조건 주는 것이 효율적이다,
# 이 알고리즘은 보수적이다. 프로세스들은 항상 본인의 최대요청을 할 것이라고 가정하며, 그 최대요청이 현재 가용자원을 가지고 충족이 되는지를 본다. 충족이 된다면, 그 프로세스의 요청은 어떤 것이든 받아들이고, 만약 안된다면 요청을 받아들이지 않는다.
3) Deadlock Detection and Recovery
- Resource type당 Single instance인 경우 : 자원할당 그래프에서의 cycle이 곧 deadlock을 의미
- Resource type당 Multiple instance인 경우 : Banker's algorithm과 유사한 방법 활용
(1) Single instance의 경우 알고리즘 : Resource Allocation Graph alogirthm(자원할당 그래프) 사용
| # Wait-for graph 알고리즘 - Resource type당 single instance인 경우 - Wait-for graph : 자원할당 그래프의 변형 : 프로세스만으로 node 구성 : Pi가 가지고 있는 자원을 Pk가 기다리는 경우 Pk->Pi - Algorithm : Wait-for graph에 사이클이 존재하는지를 주기적으로 조사 |
[ Resouorce-Allocation Graph ]
[ Corresponding wait-for Graph ]
(2) Multiple instance의 경우 알고리즘
# 프로세스가 요청하면 가용자원을 모두 줌.
* 따라서 최대요청 같은 것을 알 필요가 없음.
example )
프로세스 5개 : P0, P1, P2, P3, P4
자원 타입 3개 : A(7), B(2), C(6)
- P1은 (2,0,2)를 요청했는데 가용자원이 없어서 요청을 받아들일 수 없는 상황임.
- 그러나 이를 deadlock이라고 이야기할 수 없음. 추가 요청을 하지 않은 P2가 반납할 것이라는 아주 낙관적인 가정을 하게 되면, deadlock이 발생하지 않음.
** 만약 P2 또한 (0,0,1)을 요청하게 된다면, deadlock 발생
- 즉 요청을 받아들일 수 있는 시퀀스가 존재한다면 deadlock이 없다고 이야기할 수 있음.
(3) Recovery
- Deadlock을 발견하게 되면, Recovery를 해야함. 그에 대한 방법을 알아보고자 함.
a. Process termination
- deadlock에 연루된 프로세스를 종료시키는 방법
- 연루된 프로세스들을 deadlock이 사라질 때까지 하나씩 죽여본다.
b. Resource Preemption
- 비용을 최소화할 희생될 프로세스를 선정하고, 자원을 뺏은 후 deadlock을 없앤다.
- 동일한 프로세스가 계속해서 희생양으로 선정될 경우, Starvation 문제가 발생할 수 있다. 따라서 희생 프로세스를 정하는 패턴을 바꿔가야 이 문제를 해결할 수 있다.
4) Deadlock Ignorance
- Deadlock이 일어나지 않는다고 생각하고, 아무런 조치도 취하지 않는 것.
: Deadlock은 매우 드물게 발생하므로, deadlock에 대한 조치 자체가 더 큰 overhead일 수 있다.
: 만약, 시스템에 deadlock이 발생한 경우, 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 등의 방법으로 대처한다.
: UNIX, Windows 등 대부분의 범용 OS가 채택한다.
| * 유의사항 - 아직 공부하고 있는 문과생 코린이가, 정리해서 남겨놓은 정리 및 필기노트입니다. - 정확하지 않거나, 틀린 점이 있을 수 있으니, 유의해서 봐주시면 감사하겠습니다. - 혹시 잘못된 점을 발견하셨다면, 댓글로 친절하게 남겨주시면 감사하겠습니다 :) |
