[OS] Deadlock 과 Resource allocation graph

Deadlock

Deadlock : 아무것도 하지 못하고 서로 대기하는 상황

Livelock : 뭔가 하고는 있는데(busy wait) 의미가 없는것

 

Resource 의 종류

CPU cycles, memory space, I/O devices, mutex lock, semaphore 등

유형

• Single instance : 리소스에 가용한 인스턴스가 1개 뿐인 것

• Multiple instance

Deadlock 특성

• Mutual exclusion : 어떤 리소스에 대해 한 순간에 하나의 프로세스만 접근할 수 있음

• Hold and wait : 프로세스가 어떤 리소스를 갖고 있는데 다른 리소스를 추가로 요청

• No preemption : 리소스들이 선점을 허용하지 않음

• Circular wait : 위 세 가지 상황이 사이클을 이룸

 

위 네 가지 특성을 모두 만족시켰을 때 Deadlock 이 발생할 확률이 있음. 하나라도 만족하지 않으면 Deadlock 발생 가능성은 0

Resource-Allocation 그래프

P = {P1, P2, … Pn} : 프로세스 집합

R = {R1, R2, ... , Rn} : 리소스 집합

P → R = 프로세스가 리소스를 요청

R → P = 프로세스에 리소스를 할당

 

사이클 없으므로 Deadlock 발생 안함

 

Cycle 이 없으면 데드락은 절대 생기지 않음

Cycle 이 있는경우

• 모든 리소스가 signel instance 인 경우 : Deadlock 100%

• Serveral(mutliple) instance 리소스 타입인 경우 : Deadlock 의 확률이 존재