[운영체제] DeadLock

Deadlock Problem (교착상태의 문제)

여러 프로세스가 서로 자원이 풀리기를 기다리며 무한히 대기하는 상태를 말한다.

e.g.

• 시스템에 2개의 디스크가 있다.
• P1과 P2가 각각 1개씩 보유하고 있고, 서로 상대방의 디스크가 필요하다. -> 둘다 멈췄다. -> 교착 상태에 빠졌다.

프로세스는 리소스를 request(요청), use(사용), release(반납)한다.

Deadlock Characterization (데드락 발생조건)

데드락은 네 가지 조건이 동시에 유지되면 발생할 수 있다.

AKA 데드락의 4가지 필요조건

• Mutual exclusion (상호 배제): 한 번에 하나의 프로세스만 리소스를 사용할 수 있다. (동시에 여러개를 쓸 수 없다.)

• Hold and wait (점유 대기): 하나 이상의 리소스를 보유한 프로세스는 다른 프로세스가 보유한 추가 리소스를 확보하기 위해 대기 중이다.

• No preempition (비선점): 이미 할당된 자원을 강제로 뺏을 수 없다. (자발적으로 릴리즈할때까지 뺏을 수 없다.)

• Circular wait (순환 대기): 순환구조로 프로세스들이 서로 자원을 기다린다. (대기 집합 {P0, P1, …, Pn}이 존재한다. P0가 P1이 보유한 리소스를 대기하도록 처리한다, P1은 P2가 보유한 리소스를 기다리고 있으며, …, Pn–1은 기다리고 있다. Pn이 보유하고 있고 Pn이 리소스를 기다리고 있는 리소스의 경우 P0이 보유하고 있다.)

P0가 P1을 기다리는 이유는: P0가 원하는 리소스를 P1이 갖고 있어서

Resource-Allocation Graph (자원 할당 그래프)

만약 프로세스P가 자원R을 요청하면?

• request edge (요청 엣지) - directed edge Pi -> Pj
• assignment edge (할당 엣지) - directed edge Rj -> Pi

Cycle이 생기면 Deadlock이 가능하다.

자원당 인스턴스가 1개일 경우 사이클이 발생하면 데드락이 생긴다.

자원 할당 그래프 예제1

• Cycle이 없어서 무조건 Deadlock이 없다.
• P3,P2,P1 순으로 종료된다.
• 프로세스가 언젠가 작업이 끌날 것이기 때문에 데드락이 발생하지 않는다.

자원 할당 그래프 예제2

• Cycle이 있어서 Deadlock이 발생할 수 있다.
• P1 -> P2 -> P3 상태의 Cycle
• P2 -> P3 상태의 Cycle

자원 할당 그래프 예제3

• P1 -> R1 -> P3 -> R2 Cycle이 존재한다.
• 하지만 P2, P4가 원하는 리소스를 가지고 있어 언제든지 끝낼 수 있다.
• P2와 P4가 끝나고 R2와 R1을 릴리즈 되면서 P1과 P3도 원하는 자원을 가질 수 있다.
• 이때 모두가 원하는 자원을 갖고 언젠가 끝날 수 있다.

Basic Facts : 사이클과 데드락의 관계

1. 그래프에 사이클이 없으면 데드락이 아니다.
2. 그래프에 사이클이 있으면 다음과 같은 조건을 따져봐야 한다.
   • 만약 리소스 타입마다 하나의 인스턴스가 존재하면 데드락이다.
   • 사이클이 존재하면 그 순간 교착 상태에 빠진다.
   • 자원이 1개이기 때문에 서로가 서로의 자원을 기다리는 상황에서 아무도 양보할 수 없다. - 만약 리소스 타입마다 여러개의 인스턴스가 존재하면 데드락이 발생할 수 있다.(무조건은 아니다.)
   • 자원이 충분하여 누군가 먼저 필요한 자원을 받고 실행한 뒤에 반환할 수 있다면 교착 상태에 빠지지 않는다.
   • 사이클이 존재한다고 무조건 데드락에 걸리지는 않는다.