교착상태(deadlock)
사거리가 완전히 막혀있는 상태.
- 방법이 없음.
SW
- 모든 프로세스가 자신이 가진 자원을 놓치 않고, 필요한 자원을 기다리는 상태
The Deadlock Problem
여기서 자원은,
- 하드웨어
- ex) tape drive가 2개 필요한데 각자 1씩 가지고 양보 안함.
- 소프트웨어
- ex) semaphore나 공유 data도 자원이라고 할 수 있음.
두개의 process가 lock을 거는 semaphore를 획득해서 일을 하고 싶음.
- process 0번은 A를 획득한 다음에 B를 획득하려는 상황
- process 1번은 B를 획득한 다음에 A를 획득하려는 상황
=> CPU가 어떤 process에 가더라도 진행이 안됨
=>Deadlock
process가 자원을 사용하는 4단계 절차
01. 자원 요청 (Request)
02. 자원 획득 (Allocate)
03. 자원 사용 (Use)
04. 자원 반납 (Release)
Deadlock 발생의 4가지 조건
01. Mutual exclusion(상호 배제)
- 이 자원을 나만 독점적으로 쓸 수 있음.
02. No preemtion(비선점)
- 빼앗기지 않음
03. Hold and wait(보유 및 대기)
- 내가 가진 자원을 내어놓지 않으면서 자원 기다림.
04. Circular wait(순환 대기)
- 사이클을 형성하는 대기
Resource-Allocation Graph(자원할당그래프)
데드락이 발생했는지 자원할당그래프를 통해서 알아본다.
1) P는 프로세스
2) R은 자원
3) 화살표
- P => R : 이 프로세스가 해당 자원을 요청 but 아직 획득 못함.
- R => P : 이 자원이 해당 process한테 속해있다.
왼쪽 그래프는, - 사이클 큰거 하나
- 사이클 작은거 하나
오른쪽 그래프는,
- 사이클 큰거 하나
이 그래프는,
사이클이 없음.
사이클이 있다면 무조건 deadlock인가?
그건 아니다. 해당 자원의 개수 (여기서 점의 개수)가 하나밖에 없다면 deadlock임.
즉, 자원에 instance가 하나씩밖에 없다면 그건 deadlock을 의미.
만약, 자원의 instance가 여러개라면 deadlock일 수도 아닐 수도 있음.
Deadlock 상황인지 따져보자.
자원의 instance가 2개여서 deadlock 이 아닐 수 있음.
어떤 프로세스가 할 거 다하고 자원 내놓을 가능성이 있으니까.
하지만, instance 두개가 사이클이 두개에 걸쳐있음.
여기도 사이클이 하나 있음.
근데 자원의 instance가 두개씩 있네.
두개가 다 할당이 되어있긴하지만 deadlock이 아님.
여분의 r1과 r2를 가지고 있는게 p2, p4이다. 이 프로세스는 deadlock에 연루되지 않은 프로세스임.
그래서, 4번 process가 다 쓰고 나서 반납할 가능성 있음.
자원이 available
그래프로 deadlock인지 따져보려 하니, 어렵다 ~
뒤에 table 형태로 따지는 것을 다루려고 한다. !
Deadlock의 처리 방법 4가지
deadlock이 생기지 않게 미연에 방지
- deadlock prevention
- deadlock avoidance
-
deadlock 탐지 후 recovery
-
deadlock ignorance
- 현대 os의 선택
- 사람이 알아서 process 죽이든지 해결~
- 빈번히 발생하지 않기 때문에 미연에 방지하는 것이 더 overhead 발생시킴.
01. Deadlock Prevention
: deadlock 이 발생하는 4가지 조건 중 어느 하나 원천적으로 차단하는 방법
01) Mutual Exclusion
- 공유할 수 있는 자원으로 만든다는 건 애초에 deadlock이 안생김. 이건 deadlock prevention의 방법이 안됨
02) Hold and Wait
- 자원을 기다리는 상황에서는 자원을 보유하고 있지 않도록 만든다.
방법1은 비효율적이다=> 자원이 동시에 필요하진 않은데 처음부터 다 가지고 있으면 비효율적임
03) No Preemption
- 자원을 preemption 할 수 있게 한다.
- cpu는 preemption 할 수 있는 자원이다. 영원히 process가 잡고 놓지 않으면 안되기 때문에, timer interrupt 같은 장치 설정. 이런 자원은 deadlock이 생기지 않음.
- 그런데 아무때나 뺏어버리면 문제가 생김
=> state를 쉽게 save하고, restore할 수 있는 자원에서 주로 사용 (cpu, memory)
04) Circular Wait
ex) 자원 1,3,5가 필요하다.
=> 항상 낮은 번호부터 획득할 수 있게 한다. => 1번 자원을 획득해야지만 3번 자원 획득 할 수 있음.
생기지도 않을 deadlock을 미리 생각해서 제약조건을 많이 달아두면 상당히 비효율적이다...
02. Deadlock Avoidance
process가 시작되고 종료될 때까지, 때에 따라 쓰려고 하는 자원의 수나 종류가 다 다르다.
Deadlock Avoidance는 프로세스가 시작될 때, 이 process가 쓸 평생 자원의 최대량을 미리 알고 있다고 가정하고, deadlock을 피해간다.
deadlock이 발생할 가능성이 있으면 자원이 있어도 그 process한테 안줌.
자원에 instance가 하나밖에 없을 때,
=> 1) 자원 할당 그래프 알고리즘 사용.
자원에 instance가 여러개가 있을 때,
=> 2) banker's 알고리즘 사용.
1) Resource Allocation Graph algorithm
자원당 instance가 하나밖에 없을 때)
이 process가 평생에 적어도 한번은 R2를 사용할 일이 있다는 뜻. (점선: 지금 요청한건 아니지만 언젠가 요청할 것이라는 뜻.)
1번 => 2번 => 3번 상황임.
현재 Deadlock 상황 아님. 언젠가 요청이지, 지금 요청한건 아님 (P1 => R2);
주의)
무조건 자원이 있다고 요청한 Process한테 자원을 할당하지 않는다.
만약, deadlock이 생길 가능성이 있다면 안줌.
2) Banker's Algorithm
자원당 instance가 여러개 있을 때)
- Allocation : 각 프로세스마다 자원 A,B,C 에 대하여 필요한 개수
- Max : 평생에 걸쳐서 각 프로세스가 필요할 자원의 개수
- Available: 자원의 현재 개수에서 자원을 요청한 프로세스한테 자원 할당해주고 남은 자원 A,B,C 개수
- Need: 추가로 요청할 수 있는 양 (최대 요청 가능 양 Max - 할당된 양 Allocation)
Example of Banker's Algorithm
