[8-2] Deadlocks - 2

[ Deadlocks ]

 

 

8-1에서 Deadlock Prevention에 대해서 알아봤으나, 부작용 또는 성능 저하가 있었기 때문에 현실적으로 불가능했다.

 

[ Deadlock Avoidance ]

reqeust가 왔을 때, future deadlock이 존재할 수 있다면 잠시 대기해보자는 것.

여기에는 추가적인 정보가 필요하다.

- 리소스가 어떻게 요청되었는지

→ 사전에 알고있는 정보를 통해 deadlocked state에 진입하지 못하게 알고리즘을 통해 해보자

리소스들의 각 상태, 즉 사용가능한 개수와 할당된 개수, 앞으로 요구할 최대 개수를 알고 있다면 avoidance에 활용할 수 있게 된다.

 

[ Safe state ]

어떤 state가 safe하다고 하는 것은, 특정 순서로 각 쓰레드에 리소스를 최대 개수까지 할당할 수 있는 상태

→ 그렇기 때문에 safe sequence를 찾아내는 것이 중요하다.

 

[ Basic facts ]

A safe state is not a deadlocked state.

이전에 Resource Allocation Graph에서 살펴봤듯이, cycle이 생긴다고 해서 반드시 deadlock이 발생하는 것은 아니다.

그렇듯이 unsafe한 상태에 있다고 해서 deadlock이 반드시 발생하는 것은 아니다.

하지만, safe 상태에만 존재한다면 적어도 deadlock이 무조건 발생하지는 않는다.

 

그러므로 Deadlock Avoidance의 핵심 아이디어는, 시스템이 항상 safe state에 머물도록 해보자는 것.

 

1) 최초의 시스템은 safe state이다.

2) 쓰레드가 사용가능한 리소스를 요청할 때 마다, 리소스가 할당 가능 여부를 결정한다.

3) 할당된 리소스가 시스템을 safe state로 남아있게 할 때만 request가 승인되도록 한다.

 

[ Remind Resource-Allocation Graph ]

시스템은 각 리소스 타입에 해당하는 오직 하나의 인스턴스만 존재한다고 가정.

Claim Edge : Ti → Rj, 쓰레드가 리소스를 미래에 요청할 것이라고 나타낼 가상의 edge를 생성.

유향 그래프에서 cycle을 감지하는 알고리즘을 사용함으로써 safe state를 확인할 수 있게 되는 것!

 

만약 cycle이 존재하지 않는 경우, 해당 쓰레드가 리소스를 잡더라도 safe state이므로 요청은 즉시 승인된다.

반대로 cycle이 감지된다면, 해당 쓰레드가 리소스를 잡으면 unsafe state이므로 요청은 거부되는 것.

8.9는 T2가 R2를 요청하더라도 cycle이 발생하지 않으므로 R2를 잡을 수 있지만, 이후 T1이 R2를 요청하는 것은 cycle이 발생하므로 거부된다.

 

[ Banker's Algorithm ]

각 리소스의 타입이 multple instances로 이루어진 시스템인 경우, RAG를 적용할 수 없게 된다.

Banker's algorithm은 이런 multple instances 시스템에도 적용가능하지만, RAG보다 비효율적이고 더욱 복잡하다.

 

[ Data structures ]

쓰레드가 N개, 리소스 타입이 M개라고 해보자.

 

Available : 사용가능한 리소스의 개수를 가리키는 vector

- Available[j] == k라면, Rj에서 k개의 인스턴스가 사용가능하다는 뜻.

 

Max : 각 쓰레드가 앞으로 요청할 리소스의 최대 개수

- Max[i][j] == k라면, Ti가 Rj의 최대 k개의 인스턴스를 요청할 것이라는 뜻.

 

Allocation : 각 쓰레드에 현재 할당된 리소스의 개수

- Allocation[i][j] == k라면, Ti는 현재 Rj의 k개의 인스턴스를 할당받았다는 뜻.

 

Need : 각 쓰레드가 앞으로 요청할 리소스의 개수

- Need[i][j] == k라면, Ti는 Rj의 k개의 인스턴스를 추가로 필요로할 것이라는 뜼.

 

[ Safety Alogirthm ]

 

[ Resource-Request Algorithm ]