(42) Deadlocks Algorithm

### Algorithm ###

< Resource allocation graph algorithm >

: Deadlock avoidance(교착 방지)로 사용된다.

​

: 각 자원 유형의 instance(리소스)가 하나만 있는 시스템에서 사용할 수 있다.

​

: Request edge: thread 가 리소스(여러개 가능)를 요청하고 대기하는 상황)

​

: Assignment edge: 구체적인 리소스가 요청 thread에게 실제 할당되는 연결성)

​

: Claim edge(thread가 해당 리소스에게 요청을 할 것이다)

​

: 사이클이 없으면 Deadlock이 없다

 

출처: Operating System Concepts 10th Ed (John Wiley & Sons, Inc. 2018)

 

< Banker's Algorithm >

: Deadlock avoidance(교착 방지)로 사용된다.

​

: 각 리소스 유형의 instance가 여러 개인 시스템에서 사용할 수 있다.

​

: 각 thread는 사전에 최대한의 사용을 요구해야 한다.

​

: thread가 생성 된 후 작업 시작 전에 자신이 어떤 리소스를 얼마나 할당 받을 지 정보를 받아야 한다(전제조건)

​

: thread가 리소스 집합을 요청하면 시스템은 이러한 리소스 할당이 시스템을 안전한 상태로 유지할 지 여부를 결정해야 한다.

​

: 원한다면 리소스가 할당 된다 그러나 그렇지 않으면 thread는 다른 thread가 충분한 자원을 릴리스 할 때 까지 기다려야 한다.

 

: Available - 가용할 자원이 얼마나 남아 있는가

: Max - thread가 요구하는 리소스의 최대 개수

: Allocation - thread에 현재 할당된 리소스(instance)의 개수

: Need - thread가 현재 할당된 리소스 이외에 필요한 리소스(잔여 리소스, remain instance)

 

 

 

< Safety Algorithm >

: 시스템이 safe state인가를 판별해 주는 알고리즘

 

출처: Operating System Concepts 10th Ed (John Wiley & Sons, Inc. 2018)

- work - 사용가능한 instance의 개수(임시 누적 변수)

- finish - thread가 완료가 되는지의 여부 파악해주는 변수

 

 

 

< Resource Request Algorithm >

: safety algorithm을 기반으로 현재 thread에 리소스 할당 여부를 결정하는 알고리즘

: thread가 리소스를 요청할 때마다 triggering 된다.

(thread가 요청할때 리소스를 요청할때 safe state상태여부를 예측하여 할당여부 결정)

출처: Operating System Concepts 10th Ed (John Wiley & Sons, Inc. 2018)