[OS] 교착 상태 (Deadlock)

Deadlock(교착 상태)

두 개 이상의 프로세스가 필요한 자원을 기다리면서 무한정 중지된 상태

Deadlock(교착 상태) 예시

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

Node

• 프로세스 노드(P1, P2), 자원 노드(R1, R2)

Edge

• Rj → Pi : 자원 Rj이 프로세스 Pi에 할당 됨
• Pi → Rj : 프로세스 Pi가 자원 Rj을 요청 중(대기 중)

자원 할당 그래프 예시

• 자원 R2가 프로세스 P1에 할당 되었다.
• 프로세스 P1이 자원 R2를 요청하고 있다.
• 자원 R1이 프로세스 P2에 할당 되었다.
• 프로세스 P2가 자원 R1을 요청하고 있다.

그래프를 생성한 후 Cycle이 생기면 Deadlock이 발생한 것!

Deadlock Prevention(교착 상태 예방)

4개의 deadlock 발생 필요 조건 중 하나를 제거

• Exclusive use of resources (상호 배제)
• Non-preemptible resources (비선점)
• Hold and wait (점유와 대기)
• Circular wait (환형 대기)

Deadlock이 절대 발생하지 않음!

모든 자원 공유 허용

Exclusive use of resources 조건 제거

그러나 현실적으로 불가능

읽기 작업 같은 경우는 모든 자원을 공유해도 상관 없지만, 쓰기 작업을 해야 하는 경우 작업을 공유하면 동기화 문제가 발생할 수 있음

모든 자원에 대해 선점 허용

Non-preemptible resources 조건 제거

이것 또한 현실적으로 불가능

유사한 방법으로 프로세스가 할당 받을 수 없는 자원을 요청한 경우, 기존에 가지고 있던 자원을 모두 반납하고 작업을 취소함으로써 선점과 같은 효과를 줄 수 있지만, 이후 기존에 했던 작업은 모두 날라가고 처음부터 다시 시작해야하므로 매우 비효율적

필요한 자원 한번에 모두 할당(Total allocation)

Hold and wait 조건 제거

자원 낭비 발생(필요하지 않은 순간에도 가지고 있음)

무한 대기 현상 발생 가능

Circular wait 조건 제거

Ciruclar wait 조건 제거 예시

Totally allocation을 일반화 한 방법

자원들에게 순서를 부여

프로세스는 순서의 증가 방향으로만 자원 요청 가능

자원 낭비 발생

정리

• 4개의 deadlock 발생 필요 조건 중 하나를 위배하면 됨
• deadlock이 절대 발생하지 않음
• 자원 낭비가 심한편
• 비현실적

Deadlock Avoidance(교착 상태 회피)

시스템의 상태를 계속 감시

시스템이 deadlock 상태가 될 가능성이 있는 자원 할당 요청 보류

시스템을 항상 safe state로 유지

가정

• 프로세스의 수가 고정됨
• 자원의 종류와 수가 고정됨
• 프로세스가 요구하는 자원 및 최대 수량을 알고있음
• 프로세스는 자원을 사용한 후 반드시 반납

Banker's Algorithm(은행원 알고리즘)

Deadlock avoidance를 위한 간단한 이론적 기법

한 종류(resource type)의 자원이 여러개(unit)라고 가정

시스템을 항상 safe state로 유지

Ra, Rb, Rc 3가지 타입의 자원이 있다고 가정하고, 각각의 자원이 10개, 5개, 7개라고 가정합니다. 프로세스는 P1, P2, P3, P4, P5 5개입니다.

Max. Claim은 자원을 수용할 수 있는 최대 수, Cur. Alloc은 현재 할당된 자원의 수, Additional Need는 필요 자원의 수 입니다.

시나리오 1 - safe state

위의 경우에서 현재 할당된 자원의 수가 (7, 2, 5) 인 것을 확인할 수 있습니다. 따라서 가용 자원의 수는 (10, 5, 7) - (7, 2, 5) = (3, 3, 2) 입니다.

이제 각 프로세스의 Additional Need 값을 비교하여 자원을 할당받을 수 있는지 확인합니다. 먼저 P2 프로세스의 경우 필요한 자원의 수가 (1, 2, 2) 이므로 할당받을 수 있습니다. 이러한 경우를 safe state라고 합니다.

그래서 자원을 할당받고 나면 Cur. Alloc은 (3, 2, 2)가 되고, 가용 자원의 수는 (1, 0 , 0) 이 됩니다. P2의 작업이 끝나고 나면 썼던 자원을 모두 반납하게 되는데, 따라서 가용 자원의 수가 (5, 3, 2) 가 됩니다.

이러한 과정을 반복하면 P2 → P4 →P1 →P3 → P5 순서로 계속 safe state 가 유지되면서 성공적으로 모든 자원을 반납하게 됩니다. (deadlock 발생 X)

시나리오 3 - unsafe state

이번에는 가용 자원의 수가 (10, 5, 7) - (7, 5, 5) = (3, 0, 2) 입니다.

각 프로세스의 Additional Need를 비교했을 때, 자원을 할당받을 수 없는 것을 확인할 수 있습니다. 이러한 경우를 unsafe state라고 합니다.

따라서 deadlock이 발생할 수 있습니다.

정리

• Deadlock의 발생을 막을 수 있음
• High overhead : 항상 시스템을 감시하고 있어야 함
• Low resource utilization : Safe state 유지를 위해 사용되지 않는 자원이 존재
• Not practical : 프로세스의 수가 고정이라던가 자원의 종류와 수가 고정이라던가 등

Deadlock Detection(교착 상태 탐지)

Deadlock 방지를 위한 사전 작업을 하지 않음 : deadlock 발생 가능

주기적으로 Deadlock 발생 확인 : 어떤 시스템인지?, 어떤 프로세스인지?

Resource Allocation Graph Reduction

Graph Reduction

주어진 RAG에서 edge를 하나씩 지워가는 방법 → Unblocked 프로세스에 연결된 edge를 모두 제거!

완전히 제거 된다면, Deadlock X!

완전히 제거가 안되면, Deadlock O!

초기 상태

프로세스 P1의 edge 제거 / 프로세스 P2의 edge 제거(Deadlock X)

초기 상태 / 프로세스 P3의 edge 제거(Deadlock O)

정리

• High overhead : 검사 주기가 짧거나 Node의 수가 많은 경우
• Low overhead deadlock detection methods
  • Single-unit resources : Cycle detection
  • Single-unit request in expedient state : Knot detection

Deadlock Recovery(교착 상태 회복)

Deadlock을 검출한 후 해결하는 과정

Process termination

• Deadlock 상태에 있는 프로세스 중 일부를 종료
• 강제 종료된 프로세스는 이후 재시작 됨

Resource preemption

• Deadlock 상태 해결을 위해 선점할 자원 선택
• 선점된 자원을 가지고 있는 프로세스에서 자원을 빼앗음(뺏긴 프로세스는 강제 종료)
• Checkpoint-restart
  • 프로세스의 수행 중 특정 지점(checkpoint) 마다 context를 저장
  • 프로세스가 강제 종료될 때 가장 최근의 checkpoint에서 재시작할 수 있음

Deadlcok vs Starvation

Difference Between Deadlock and Starvation in OS (with Comparison Chart) - Tech Differences

Difference Between Deadlock and Starvation in OS (with Comparison Chart) - Tech Differences

 

 

 

참고

쉽게 배우는 운영체제

쉽게 배우는 운영체제

[Course] Operating System (CPA310) - 운영체제 강의

[Course] Operating System (CPA310) - 운영체제 강의