[OS] DeadLock

두개 이상의 프로세스(작업)이 자신의 자원을 놓지 않고 다른 자원을 대기하며 멈춰있는 상황을 교착상태(DeadLock) 이라고 한다.

교착상태 발생조건

1. Mutual Exclusion(상호배제): 매 순간 하나의 프로세스만이 자원을 사용하게 된다면 다른 프로세스는 사용하지 못하여 교착상태 발생

2. Non-preemption(비선점): 프로세스는 다른 자원을 강제로 뺏지 않기 때문에 자원을 얻지 못함

3. Hold and Wait(점유와 대기): 프로세스가 자신의 자원을 놓지 않고 다른 자원을 기다리는 상황

4. Circular Wait(원형대기): 자원을 기다리는 프로세스간의 사이클이 형성(자원 할당그래프가 원의 형태) 하지만 무조건 교착상태는 아님

교착상태 해결

1. Deadlock Prevention(예방): 교착상태 발생의 조건 4가지 중 한가지라도 만족하지 못하게 만들면 교착상태를 해결할 수 있다.

• 상호배제: 모든 자원을 공유 가능하게 함...
• 점유와 대기: 1. 프로세스가 시작할 때 모든 자원을 할당하기 2. 자원이 필요할 때 보유 자원을 모두 놓고 요청하기. 자원 사용률이 비효율적임
• 비선점: 자원을 선점할 수 있게 한다. (자원의 상태를 저장할 수 있는 자원에 한해)
• 원형대기: 자원에 할당 순서를 정해서 순서대로 자원을 할당받을 수 있게 한다

2. Deadlock Avoidance(회피): 교착상태가 발생하지 않게 조심스럽게 자원을 할당하는 방식. Deadlock의 가능성이 낮을 때만 할당.

• 안전상태: 안전 순서열이 존재하여 교착상태가 발생하지 않음
• 불안전상태: 교착상태가 발생하 수 있음
• 은행가의 알고리즘. 미리 프로세스들은 자신이 평생 쓸 자원을 파악함. 안전상태일 때만 자원을 할당

하지만 은행가의 알고리즘은 프로세스가 시작 될 때 프로세스가 필요로 하는 자원을 미리 알아야한다는 점, 사용자의 수가 일정해야한다는 점 등 비효율적임.
데드락의 발생 가능성은 낮지만 그만큼 자원의 이용률도 낮다.

3. Deadlock Recovery and Detection(회복과 검출): 교착상태가 일어난 이후 조치하는 방법

• 교착상태를 검출하고 회복한다.
• 선점을 통한 회복: 교착상태가 해결 될 때까지 다른 프로세스들의 자원을 하나씩 뺏어서 하나의 프로세스에게 몰아서 할당
• 강제종료를 통한 회복: 교착상태가 발생한 프로세스를 하나씩 강제 종료하거나 모두 종료한다. 작업 내용을 잃을 수 있다.