* The Deadlock Problem
- 리소스를 갖고 있으면서, 다른 Process가 갖고 있는 리소스를 원하는 프로세스
이런 프로세스들의 집합으로 집합 내에서 서로의 리소스를 원하는 것
- Resource Type = Rn
- Resource Instance = Wn
ex) 3개의 모니터가 연결된 컴퓨터에 대한 모니터 타입 R1은 3개의 instance W1,W2,W3를 갖고 있다.
- 모든 process는 resource를 요청하고, 사용하고, 해제하는 과정을 갖는다.
* Deadlock이 생기는 겅우
- 다음 4가지의 상태를 모두 만족해야 한다.
ⓐ Mutual Exclusion : 오직 하나의 process만 instance에 접근
ⓑ Hold and wait : resource를 갖고 있는 process가 다른 process가 가지고 있는 resource를 기다리고 있다.
ⓒ No preemption : process가 자동적으로 resource를 해제한다. 강압적으로 resource를 빼앗을 수 없다.
ⓓ Circular wait : 순환되는 관계로 서로 물고 물리는 관계, 서로의 resource를 원함.
Block 될 가능성이 있는 process 끼리 순환 회로에 포함.
* Deadlock Handling method
ⓐ Prevention & avoidance deadlock : System control
ⓑ Deadlock detection : deadlock이 발생하면, 그 대 해결을 시도
ⓒ Ignore deadlock : deadlock을 방관함
* Deadlock Prevention
- Deadlock을 발생시키는 4가지 조건중 하나를 불충분하게 하면된다.
ⓐ Mutual Exclusion
- 공유 가능한 리소스의 요청을 하지 않는다.
- System이 공유가능성이 있는 리소스에 대해서는 사용을 요청하지 않는다.(비효율)
ⓑ Hold and wait
- resource request시에는 잡고 있던 resource를 놓는다.
- 여러개의 resource를 "순차적"으로 잡는 것이 불가능하다.
여러개의 resource를 잡기 위해서는 비어 있는 resource들을 "동시"에 잡아야한다.
> starvation이 발생할 수 있다. resource utilization이 떨어진다.
ⓒ No Preemption
- 여러개의 resource를 "순차적"으로 잡는 것이 가능하게 해준다.
- 하지만 다른 프로세스가 자신이 소유한 resource를 요청하면, resource를 양보한다.
(가장 최근에 소유한 resource에 대해서는 예외!!)
ⓓ Circular wait
- resource에 순서를 준다. 화살표를 한쪽 방향으로만 뻗는다. 이로서 Circular방지.
- Process가 가지고 있는 resource 보다 높은 우선순위를 가진 resource만 요청 가능하다.
* Deadlock Avoidance
- Deadlock 발생 가능성을 지속적을 check한다.
- 프로세스가 실행할 대 사용할 전체 resource의 최대 수를 알려준다.
이를 이용해 resource allocation scheduling을 실시
- resource allocation state를 check후 위험한 assign은 하지 않는다.
※ resource allocation state
> Number of available resource : 사용 가능한 resource의 수
> allocated resource : 현재 누가 어떤 resource를 가지고 있는지를 알려준다.
> Number of maximum demand : 최대로 요구하는 resource의 양
* Safe State
- Deadlock avoidance는 process에게 resource를 할당하기 전에 deadlock이 발생 가능한지 유무를 판단.
(Safe State여부를 판단)
- 어떤 프로세스가 종료되면 가지고 있는 resource를 반납할 때, 이를 이용해 다른 process가 실행 가능해야 하며,
이 chain이 끝나는 시점에서 모든 process가 종료되야 한다.
( 종료된 process의 존재가 전제조건이다.)
ex)
* Avoidance Algorithms
ⓐ Single instance
- resource allocation graph를 사용해 deadlock 가능성을 check한다. resource 요청에 대해 승인한
allocation graph를 그린 후 발생 가능한 모든 요청을 고려, Deadlock발생 가능성이 있다면 주지 않는다.
ⓑ Banker's algorithm
- resource allocation state를 표로 작성하여 문제를 해결한다. 각 process가 원하는 resource의 양을 파악후
해결 가능한 process부터 실행, 종료를 한다.
ex)
Resource A have 10 instances.
Resource B have 5 instances.
Resource C have 7 instances.
1) 현재 해결 가능한 Process는 P2와 P4가 존재한다.(프로세스 번호가 빠른 것을 우선 처리한다고 가정)
Select P2, P2 process end > available A,B,C value change / available(A,B,C) = (5,3,4)
2) 현재 해결 가능한 Process는 P4가 존재한다.
Select P4, P4 process end > available A,B,C value change / available(A,B,C) = (7,4,5)
3) 현재 해결 가능한 process는 P1과 P3가 존재한다.
Select P1, P1 process end > available A,B,C value change / available(A,B,C) = (7,5,5)
4) finally process P4 select, P4 process end > available A,B,C value change / available(A,B,C) = (10,5,7)
> 현재 요청은 안전하다고 판단됨! 승인!
* Safety Algorithm
- 현재 상태가 Safe인지 Unsafe인지 판단하는 Algorithm
> 현재 사용 가능한 resource를 복사한 후, Banker's Algorithm을 돌려본다.
> 현재 사용 가능한 resource를 복사하는 이유 > real data는 변하면 안되기 때문에
* Resource-Request Algorithm
- Process가 resource를 요청했을 때, 안전한지 판단하는 알고리즘
1) request resource <= need resource
프로세스가 필요한 최대 요구량보다 많이 요청하면 error, reject request
2) request resource <= available resource
요구량이 보유한 resource양보다 많이 요청하면 error, Make process to wait state
3) Simulation
Resource를 할당했다고 가정후 Safety Algorithm을 돌려본다.