Deadlock

정의

• 일련의 프로세스들이 서로가 가진 자원을 기다리며 block 되어 더 이상 진행이 될 수 없는 상태.

• 프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우.

deadlock vs starvation

• 상태, 기다리는 대상, 발생 가능성 측면에서 차이가 있음.

자원의 분류

• deadlock은 자원과 매우 밀접한 영향이 있음.

• 일반적으로 HW와 SW로 나누지만 deadlock 관점에서 보는 다른 분류 방법도 존재함.
• 선점 가능 여부에 따른 분류
• Preemption Resources
• “cpu를 뺏어갈 수 있는”.
• 선점 당한 후, 돌아와도 문제가 발생하지 않는 자원.
• Processor(saving, restoring), Memory(swap device) 등.
• Non-preemptible Resources
• (여권에 낙서하면 사용을 할 수 없는 것처럼) 선점 당하면 이후 진행에 문제가 발생하는 자원.
• Rollback, Restart등 특별한 동작이 필요.
• E.g., disk drive 등
• 할당 단위에 따른 분류
• Total Allocation Resources
• 자원 전체를 프로세스에게 할당.
• E.g., Processor, Disk Drive 등 -> 한번에 하나의 프로세스만 사용 가능.
• Partitioned Allocation Resources
• 하나의 자원을 여러 조각으로 나누어, 여러 프로세스들에게 할당.
• E.g., Memory 등



• 동시 사용 가능 여부에 따른 분류
• Exclusive Allocation Resources
• 한 순간에 한 프로세스만 사용 가능한 자원.
• E.g., Processor, Memeory(본인에게 할당된 영역은 본인만 쓸 수 있음), Disk Drive 등.
• Shared Allocation Resource
• 여러 프로세스가 동시에 사용 가능한 자원.
• E.g., Program(sw) - 소스코드, exe 파일 등... , shared data 등
• 재사용 가능 여부에 따른 분류
• SR(Serially-uesable Resources)
• 시스템 내에 항상 존재하는 자원.
• 사용이 끝나면 다른 프로세스가 사용 가능.
• E.g., Processor, Memory, Disk Drive, Program 등.
• CR(Consumable Resources)
• 한 프로세스가 사용한 후에 사라지는 자원.
• E.g., signal, message 등 (받으면 사라짐).

Deadlock과 자원의 종류

• Deadlock을 발생시킬 수 있는 자원의 형태.

• Non-preemptible Resources
• 자원을 한번 할당받으면 게속 쓰기 때문에 다른 프로세스에서 요청을 하면 자원이 계속 할당되지 않으므로.

• Exclusive Allocation Resources
• 같이 사용할 수 없기 때문에.

• Serially Reusable Resources
• 참고) CR 또한 사라진 자원을 기다리고 있는 프로세서가 있었다면 deadlock이 발생 할수도 있지만 복잡하기 때문에 deadlock 모델을 생각할 땐 SR만 고려함.

• 할당 단위는 영향을 미치지 않음
• 혼자 쓴다고 해도 preemptible하다면 문제되지 않음

• 그래서 등장한 deadlock 표현 기법!
• Graph Model
• 그래프 모형으로 표현한 모델
• graph는 node와 edge로 구성됨.



• State Transition Model
• 상태 변화를 표현한 모델

Deadlock 발생 필요 조건

• 상호 배제
• 한 번에 프로세스 하나만 해당 자원을 사용할 수 있음.
• 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 함.

• 점유 대기
• 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 힘.

• 비선점
• 이미 할당된 자원을 강제로 빼앗을 수 없음 (비선점).

• 순환 대기
• 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 함.

• deadlock 필요 조건 중 하나만 없애도 발생시키지 않을 수 있음.

1. 교착 상태 예방 (Deadlock Prevention)
• 확실한 방법이지만 자원 낭비와 비효율이 심해 비현실적임.

2. 교착 상태 회피 (Deadlock Avoidance)
• 시스템 상태를 계속 감시하며 safe state(모든 프로세스가 정상적으로 종료 가능 상태)일 때만 자원 요청을 허용하는 방법.
• 하지만 회피하기 위해 다음과 같은 가정이 필요해 실현이 어려움.

가정

• 프로세스 수가 고정되어 있어야 한다.

• 자원의 종류와 수가 고정되어 있어야 한다.

• 프로세스가 요구하는 자원 및 최대 자원의 수를 알아야 한다.

• 프로세스는 반드시 자원을 사용 후 반납해야 한다.

💡
다만 어떻게 해결하려 했는지 방법을 알고 있는 건 중요함. 어떤 알고리즘을 사용해 safe state를 유지하려 했는지 알아보자.
• (자원이 1 개인 경우) Dijkstra’s algorithm
• (자원이 여러 개인 경우) Banker’s algorithm
• Habermann’s algorithm

3. 탐지 및 복구 (Detection and Recovery)



• 주기적으로 deadlock 발생 확인.
• 확인하기 위한 방법.
• Resource Allocation Graph(RAG) 사용.
• Directed (방향성이 있는 그래프), bipartite Graph (두 개의 파트 p, s로 나눈 그래프)

• 관련 알고리즘
• Graph reduction
• 주어진 RAG에서 edge를 하나씩 지워가는 방법.
• Completely reduced : deadlock에 빠진 프로세스가 없음.
• Irreducible : 하나 이상의 프로세스가 deadlock 상태.



• Unblocked process에 연결된 모든 edge를 제거

• Deadlock recovery
• deadlock을 검출한 후 해결하는 과정에는 2가지가 있음.
• Process termination
• deadlock 상태에 있는 프로세스를 종료시킴.
• 종료시킬 조건을 담은 termination cost model이 있음.
• 랜덤으로 죽이자니 불필요한 프로세스들이 종료될 가능성이 높고 최소 비용으로 선택하려면 모든 경우의 수를 고려해야 하기 때문에 복잡하고 high overhead 발생.
• 강제 종료된 프로세스는 이후 재시작됨.
• Resource preemption
• deadlock 상태 해결을 위해 선점할 자원 선택.
• 선정된 자원을 갖고 있는 프로세스에서 자원을 빼앗음.
• 마찬가지로 preemption cost model이 필요함.
• 자원을 뺏긴 프로세스는 강제종료됨.
• 복구 시 프로세스의 수행 중 특정 지점마다 context를 저장하는 checkpoint-restart method를 통해 비용을 줄일 수 있음.