Deadlock 1

교착상태. 

일부 자원을 가지고 있으면서 상대방의 자원을 요구. 

Deadlock- 일련의 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태. 

Resource(자원) - 하드웨어, 소프트웨어 등을 포함하는 개념. ex) memory space, semaphore 등. 

프로세스가 자원을 사용하는 절차 Request-> Allocate -> Use ->Release

Deadlock 발생의 4가지 조건. 

- Mutual exclusion (상호 배제) : 매 순간 하나의 프로세스만이 자원을 사용할 수 있음. 

- No preemption (비선점) : 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음

- Hold and Wait(보유 대기) : 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음

- Circular wait(순환대기) : 자원을 기다리는 프로세스 간에 사이클이 형성되어야 한다. 

 

프로세스에서 자원으로 향한 화살표는 해당 자원을 기다리는 것이다. 

그래프에 사이클이 없으면 deadlock이 아니다. 

그래프에 cycle이 있으면, deadlock이다. 하지만 만약 한 자원에 인스턴스가 여러 개이면 deadlock이 아닐 수 있다. 만약 해당 자원의 인스턴스 중에 사이클에 들어가지 않은 것이 있다면 해당 인스턴스 덕에 deadlock이 생기지 않는다. 

 

 

Deaklock의 처리 방법. 

- 미연에 방지 

1) Deadlock Prevention - 자원 할당 시 dealock의 4가지 필요조건 중 어느 하나가 만족되지 않도록 하는 것. - deadlock을 미연에 방지하려 하기 때문에 상당히 비효율적일 수 있다. starvation 문제도 발생 가능성 있음. 

hold and wait - 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법, 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청

no preemption - state를 쉽게 save하고 restore 할 수 있는 자원에서 주로 사용. (cpu, memory) 쉽게 뺏을 수 있으면 deadlock은 생기지 않는다. 

circular wait - 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당하면 deadlock이 생기지 않는다. 

 

2) Deadlock Avoidance - 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당. 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당. 

- 프로세스들이 필요로 하는 각 자원의 최대량을 미리 선언해둔다. 점선으로 평생에 한 번은 프로세스가 해당 자원을 요청할 수 있음을 표현한다.