[오퍼레이팅 시스템] Deadlock

Deadlock

 

[ Deadlock ]

  : 둘 이상의 Process 또는 Thread가 서로 상호 배제(Mutual Exclusion)된 자원에 대해 접근하려고 할 때 생기는 문제.

  : 서로의 Lock이 걸린 자원을 사용하기 위해 무한히 대기하는 상황을 나타냄.

Deadlock의 직관적 예시

 

[ Deadlock Conditions ]

  1) Mutual Exclusion

    : 상호 배제. 하나의 Critical Section에는 하나의 Process 또는 Thread만 접근해야 된다는 법칙.

    : Deadlock의 근본적인 원인.

  2) Hold and Wait

    : 하나의 자원을 점유한 상태에서 상호 배제에 있는 다른 자원을 요청하는 상황을 상호적으로 겪고 있는 경우.

Hold and Wait 상황

  3) No Preemption

    : Process 또는 Thread가 점유하고 있는 자원은 다른 Process 또는 Thread에게 강제로 빼앗기지 않는다는 법칙.

  4) Circular Wait

    : Hold and Wait가 순환적으로 발생하는 상태.

    : Dining Philosophers Problem이 대표적인 예시이다.

 

[ Resource Allocation Graph ]

  : Process와 Resource, Instance의 관계를 나타낸 Graph.

  : Graph를 그렸을 때 Cycle이 있으면 Deadlock이 존재할 가능성이 존재.

  : 모든 Resource의 Instance가 1개라고 한다면, Cycle이 있을 시 무조건 Deadlock 발생.

  : Resource의 Instance가 2개 이상이면 Deadlock이 발생하지 않을 수도 있음.

Resource Allocation Graph

 

[ Deadlock Prevention ]

  1) Mutual Exclusion

    : 사실상 Mutual Exclusion을 방지할 수 있는 방법은 없다. → Infeasible

       ( 이를 막게 되면 본래 방지하려고 했던 Race Condition이 발생하게 되므로 )

  2) Hold and Wait

    : Process 수행에 필요한 자원을 초기에 한 번에 요청하는 방법으로 방지할 수 있음.

       → 해당 방법은 한 번에 많은 자원을 들고있으므로 자원 효율성이 줄어들고, Starvation을 유발할 수 있다.

  3) No Preemption

    : Process가 필요한 Resource를 가진 Process로부터 우선순위에 따라 자원을 뺏어갈 수 있도록 지정.

       → 해당 방법은 우선 순위가 높은 Process에게만 자원이 몰리게 되므로 Starvation을 유발할 수 있다.

  4) Circular Wait

    : 모든 Resource에 번호를 달고 순서에 따라서만 요청할 수 있도록 지정.

       → 자원 사용에 제약이 생기고, 할당이 복잡해지며 자원 효율성이 줄어든다.

 

[ Deadlock Avoidance ]

   : Deadlock이 발생할지 안할지를 미리 검사하여 Deadlock이 발생할 가능성이 있으면 해당 동작을 피하는 방법.

   : Safe State와 Unsafe State로 나누어져 있으며 Unsafe State는 Deadlock이 발생할 확률이 있는 State를 말한다.

Safe / Unsafe State

  · Single Instance의 경우 → Resource Allocation Graph 이용

    : P1과 P2가 R2를 Wait하고 있는 상황에서 P2 - R2 Request에 대해 허용하게 되면 Cycle이 형성되므로 이를 방지.

 

  · Multiple Instance의 경우 → Banker's Algorithm 이용

    : 은행이 최소 한명에게는 자원을 빌려줘 상환받을 수 있는 상황을 보장하도록 하는 알고리즘.

       1) Available : 은행이 빌려줄 수 있는 현재 자원량.

       2) Max : 고객이 요청할 수 있는 최대 자원량.

       3) Allocation : 현재까지 고객에게 지원해준 자원량.

       4) Need : 고객이 현재 필요로 하는 자원량.

    : Safe State는 고객에게 자원을 내주고 모두 상환받을 수 있을 만큼의 자원량을 가진 상태.

    : Unsafe State는 현재 고객에게 남은 자원을 모두 내줘도 상환받을 수 없는 자원 상태.

    : Unsafe State로 들어가지 않도록 미리 관리하는 알고리즘.

    : 알고리즘이 매우 복잡하고, 자원 효율성이 많이 떨어져 실제로는 사용되지 않는다.

       ( ⊕ 해당 내용은 https://jhnyang.tistory.com/102 게시글에서 매우 잘 설명하고 있으니, 추가 설명이 필요하시면 참고하세요! )

 

[ Deadlock Detection ]

  : 시스템 내에서 Deadlock이 발생한지 확인하는 방법.

  · Single Instance의 경우 → Wait-for Graph 이용

    : Resource Allocation Graph에서 Resource 부분을 제외하고 자원 반납 관계만을 표현.

Resource Allocation Graph와 Wait-for Graph

  · Multiple Instance의 경우 → Similar to Banker's Algorithm 이용

    : Banker's Algorithm에서 Need 대신 Request로 바꿔 표시.

    : Request는 현재 상황에서 요청된 자원의 양을 나타냄.

 

[ Deadlock Recovery ]

  · Process Termination : Deadlock이 발생한 Process를 강제 종료. → 데이터 무결성 보장 불가

  · Process Rollback : Deadlock이 발생하기 이전으로 되돌림. → 체크포인트 정보를 별도로 저장해야 함.