[운영체제] Chapter 7. Deadlock (1), (2)

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

 

교착상태(deadlock), The Deadlock Problem, Deadlock 발생의 4가지 조건, Resource-Allocation Graph(자원할당그래프), Deadlock Prevention, Deadlock의 처리 방법, Deadlock Avoidance, Resource Allocation Graph algorithm, Banker's Algorithm, Example of Banker's Algorithm, Deadlock Detection and Recovery, Deadlock Ignorance

 

1. Deadlock(교착 상태)

• 일련의 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태
• Resource(자원)
  • 하드웨어, 소프트웨어 등을 포함하는 개념
  • 프로세스가 자원을 사용하는 절차: Request(요청)→ Allocate(획득) → Use(사용) → Release(반납)
• 하드웨어 자원을 기다리며 deadlock
  • 시스템에 2개의 tape driver가 있고, 하나의 tape driver를 읽어 다른 tape driver에 copy 하려는 상황
    • 프로세스 P1과 P2가 각각 2개의 tape driver를 점유해야 copy 해서 paste 하는데
    • 프로세스 P1과 P2가 각각 하나의 tape driver를 보유한 채 다른 하나를 기다리며 교착상태 발생
• 소프트웨어 자원을 기다리며 deadlock
  • lock을 거는 세마포어 2개를 획득하여 일을 하고 싶은 상황
    • P0는 세마포어 A를 얻고 B를 얻으려 하는데 P1이 이미 B를 점유함
    • P1는 세마포어 B를 얻고 A를 얻으려 하는데 P0가 이미 A를 점유함
    • CPU가 P0나 P1에게 할당되어도 세마포어 A 또는 B 하나를 획득할 수 없어 교착 상태 발생

 

2. Deadlock 발생의 4가지 조건

• Mutual exclusion(상호 배제): 매 순간 하나의 프로세스만이 자원을 사용할 수 있다.
• No preemption(비선점): 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않는다.
• Hold and wait(보유대기): 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있다.
• Circular wait(순환대기): 서로가 가진 자원을 기다리는 프로세스들 간에 사이클이 형성되어야 한다.
  • 프로세스 P0, P1, P2, … , Pn이 있을 때 P0는 P1이 가진 자원을, P1은 P2가 가진 자원을 … 기다림
• 4가지 조건을 모두 만족해야 deadlock이 발생한다. 어느 한 가지 조건이 풀리면 deadlock은 발생하지 않는다.

 

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

• deadlock이 발생했는지를 알아보기 위해서 사용한다.

• 그래프에 사이클이 없으면 → deadlock이 아니다.
• 그래프에 사이클이 있으면
  • 자원의 각 인스턴스가 1개라면 → deadlock이다.
  • 자원의 각 인스턴스에 여유가 있다면 → deadlock이 발생할 가능성은 있다.

 

4. Deadlock의 처리 방법

4-1. Deadlock Prevention(교착 상태 예방)

• 자원 할당 시 deadlock의 4가지 필요조건 중 어느 하나가 만족되지 않도록 하는 것으로 가장 강력한 deadlock 미연 방지 방법
• Mutual Exclusion(상호 배제)
  • 적어도 하나의 자원은 공유가 불가능한 자원이어야 한다. 어떤 자원은 근본적으로 공유가 불가능
    - mutex 락은 동시에 여러 스레드가 공유할 수 없다.
  • 그러나 일반적으로 상호 배제 조건을 거부함으로써 교착 상태를 예방하는 것은 불가능하다. 막을 수 있는 조건이 아니다.
• Hold and Wait(점유하며 대기)
  • 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
  • 방법 1) 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
    • 모든 자원을 Hold 하고 시작해서 Wait 할 일이 없다.
    • 하지만 비효율적이다.
  • 방법 2) 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청하는 방법
    • 그때그때마다 필요한 자원을 할당받는다.
    • 이미 Hold 한 자원도 다 놓고 기다려야 한다.
• No Preemption(비선점)
  • 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점되어 스레드는 자신이 요청하고 있는 새로운 자원은 물론 이미 점유하였던 옛 자원들을 다시 획득할 수 있을 때만 다시 시작될 것이다.
  • CPU 레지스터나 데이터베이스 트랜잭션처럼 그 상태가 쉽게 저장되고 후에 복원될 수 있는 자원에 종종 적용된다.
    • 교착 상태가 가장 흔하게 발생하는 자원 유형인 mutex 락과 세마포어 같은 자원에는 적용될 수 없다. 작업을 하는 도중에 빼앗으면 현재까지 한 작업이 엉망이 되거나, 또는 이때까지 했던 작업들이 무산되고 처음부터 다시 시작해야 하는 경우
  • 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
• Circular Wait(순환 대기)
  • 모든 자원 유형에 전체적인 순서를 부여하여, 각 프로세스가 열거된 순서대로 오름차순으로 자원을 요청하도록 요구하는 것
  • 예) 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj를 할당받기 위해서는 우선 Ri를 release 해야 한다.

→ deadlock preventation은 원천적으로 deadlock을 막을 수 있지만 발생하지도 않은 deadlock을 미리 생각해서 제약 조건을 걸어 놓기 때문에 상당히 비효율적이다.

⇒ Utilization 저하(자원에 대한 이용률), throughput 감소(전체 시스템 성능 저하), starvation 문제가 발생한다.

4-2. Deadlock Avoidance(교착 상태 회피)

• 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로부터 안전(safe)한 지를 동적으로 조사해서 안전한 경우에만 할당
  • safe state: 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
  • 시스템이 safe state에 있으면 → deadlock 아님
  • 시스템이 unsafe state에 있으면 → deadlock의 가능성이 있음, 가용 자원만으로 충족되지 않는 프로세스에게 자원을 할당했다고 해서 deadlock은 아님
• 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법이다.
• 2가지 경우의 avoidance 알고리즘

4-2-1. Resource Allocation Graph Algorithm

• Resource Allocation Graph Algorithm - 자원의 인스턴스가 하나밖에 없을 경우

  

  • Claim edge(예약 간선) Pi → Rj : 프로세스 Pi가 자원 Rj를 미래에 요청할 수 있음을 뜻함(점선)
  • 프로세스가 해당 자원 요청 시 request edge(실선)로 바뀜
  • Rj가 release 되면 assignment edge(자원을 할당 받은 상태)는 다시 claim edge로 바뀐다.
  • request edge의 assignment edge 변경 시 (점선을 포함하여) cycle이 생기지 않는 경우에만 요청자원을 할당한다. 
    즉, deadlock의 가능성이 있는 자원 요청에 대해서는 애초부터 받아들이지 않고 그냥 둔다.(자원할당을 하지 않지만 deadlock도 발생하지 않음)
    • 언제 P1이 R2를 요청할 수 있는가? P1이 R1을 다 쓰고 반납해서 P2가 R1을 가질 수 있을 때

4-2-2. Banker’s Algorithm

• Banker’s Algorithm - 자원의 인스턴스가 여러 개인 경우
  • 자원 요청 시(총 요청 자원의 수 < 가용 자원의 수) 충족하는 safe 상태를 유지할 경우에만 할당한다.
    • 전제) 자원을 요청하고 요청한 자원을 받고, 추가 요청 없이 일이 다 끝났을 때에만 자원을 내놓음 
    • 미래의 상태도 함께 고려해야함
  • 가용 자원만 가지고 그 프로세스의 최대 자원 요청을 처리할 수 있는 프로세스의 요청만 받아들이면 언제나 safe 한 상태를 유지해서 deadlock에 빠지지 않는다.

    

  • P1의 요청은 추가 요청 가능량(1, 2, 2) < 가용 자원(3, 3, 2) : 할당 가능
  • P0의 요청은 추가 요청 가능량(7, 4, 3) > 가용 자원(3, 3, 2) : 할당 불가능, 최대 요청을 하면 가용자원만으로 처리할 수 없기 때문에 다른 프로세스가 반납할 때까지 그냥 기다리게 두기 때문에 deadlock은 잘 발생하지 않는다.
  • sequence <P1, P3, P4, P2, P0>가 존재하므로 시스템은 safe state
    • sequence <P1, P2, …, Pn>이 safe 하려면 Pi(1≤ i ≤ n)의 자원 요청이 “가용 자원 + 모든 Pj(j < i)의 보유 자원”에 의해 충족되어야 한다.
  • 최대 요청을 하더라도 deadlock이 생기지 않는 요청에 대해서만 자원을 할당한다. → 비효율적

4-3. Deadlock Detection and Recovery(교착 상태 탐지와 회복)

• deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견 시 recover
  • deadlock이 발생했는지 결정하기 위해 시스템의 상태를 검사하는 알고리즘
  • deadlock으로부터 회복하는 알고리즘
• deadlock은 빈번히 발생하는 이벤트가 아니기 때문에 미연에 방지하기 위해서는 훨씬 더 많은 오버헤드가 발생하기 때문에 현대적 시스템에서 deadlock을 미연에 방지하는 방법은 비효율적이다.

4-3-1. Deadlock Detection

• Resource type 당 single instance인 경우 - 자원할당 그래프에서의 사이클이 곧 deadlock을 의미 

  

  • wait-for graph(대기 그래프): 자원할당 그래프의 변형, 프로세스만으로 node를 구성
  • Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk → Pj
  • wait-for graph에 사이클(= deadlock)이 존재하는지를 주기적으로 조사하는데 드는 오버헤드 O(n^2)
    : 프로세스가 n개 있다고 가정할 때 화살표는 최대 n(n-1) 개가 존재할 수 있다. 화살표를 다 따라가는 데 걸리는 시간 O(n^2)
• Resource type 당 multiple instance인 경우 - 테이블을 그려서 현재 상태가 deadlock인지 탐지
  (Banker’s algorithm과 유사한 방법 활용 - 가능한 모든 할당 순서를 조사해 보는 방식)

  

  • 프로세스가 요청하면 자원을 다 할당하기 때문에 최대 사용량(Max)을 미리 알 필요 없다.
  • 가용 자원 (0, 0, 0)은 지금 현재 요청 P1 (2, 0, 0), P3 (1, 0, 0), P4 (0, 0, 2)을 받아들일 수 없다.
  • 그렇지만 deadlock은 발생하지 않는다!
    → Allocation이 반납할 것이다를 가정하면 sequence <P0, P2, P3, P1, P4>가 존재한다.
    • P0 반납 - 가용 자원 (0, 1, 0)
    • P2 반납 - 가용 자원 (3, 1, 3)
    • P3 (1, 0, 0) 할당 후 반납 - 가용 자원 (5, 2, 4)
    • P1 (2, 0, 2) 할당 후 반납 - 가용 자원 (7, 2, 4)
    • P4 (0, 0, 2) 할당 후 반납 - 가용 자원 (7, 2, 6)
    • <Deadlock 발생 확인하는 방법>
      1. 가용 자원으로 처리 가능한 요청이 있는지 확인하기
      2. 요청하지 않는 프로세스의 할당받은 자원은 가용 자원에 합치고
      3. 합친 값으로 처리 가능한 요청이 있는지 봐서 있으면 그 프로세스에게 할당
      4. 계속 합쳐나가면서 끝까지 갈 수 있는지를 확인한다.
  • 만약 P2의 request가 (0, 0, 0)이 아니라 (0, 0, 1)이었다면?
    • 프로세스는 본인이 가진 자원은 가지고 있으면서 요청한 자원이 만족될 때까지는 가진 자원을 내놓지 않는다.
    • P0 반납 - 가용 자원 (0, 1, 0)이 되었을 때 P2의 (0, 0, 1)을 충족하지 못하기 때문에 P2의 자원을 내놓지 않게 되고 결과적으로 가용 자원 (0, 1, 0)으로 다른 프로세스들의 요청을 충족하지 못하기 때문에 Deadlock이 존재한다.
  • 실제로는 프로세스들이 최대 자원을 받았거나 or 현재 요청 자원량이 없다고해서 그 프로세스가 종료되어서 자원을 반납할 때까지 기다리는 것은 아니고, 자원을 쓰다가 중간에 반납할 수도 있고 더 가져갈 수도 있다.

4-3-2. Recovery

• Process termination: Deadlock에 연루되었던 프로세스들을 차단하는 방법
  • Abort all deadlocked process: 교착 상태 프로세스를 모두 중지
  • Abort one process at a time until the deadlock cycle is eliminated: 교착 상태가 제거될 때까지 한 프로세스 씩 중지
• Resource Preemption: Deadlock에 연루되었던 프로세스들로부터 자원을 뺏는 방법
  • 비용을 최소화할 희생자를 선정: 비용을 최소화하기 위해 자원과 프로세스의 선점 순서를 결정해야 한다.
  • 희생자 프로세스를 안전한 상태로 후퇴(rollback)시키고, 그 상태로부터 다시 시작해야 한다.
  • starvation 문제: 동일한 프로세스가 계속해서 희생자로 선정되어 선점되는 경우 발생한다.
    → 비용 요소에 후퇴(roll back)의 횟수도 같이 고려해서 해결한다.

4-4. Deadlock Ignorance(교착 상태 무시)

• deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음
• deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 오버헤드일 수 있다.
• 만약 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 방법 등으로 대처한다.
• UNIX, Windows 등 대부분의 범용 OS가 채택

 

[복습]

1. deadlock(교착 상태): 일련의 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태
2. 프로세스가 자원을 사용하는 절차: Request(요청) → Allocation(획득) → Use(사용) → Release(반납)
3. Deadlock 발생의 4가지 조건
   
   • Mutual exclusion(상호 배제)
   • No preemption(비선점)
   • Hold and wait(보유대기)
   • Circular wait(순환대기)
4. deadlock이 발생했는지를 알아보기 위해 자원할당그래프(resource-allocation graph)를 사용한다.
5. Deadlock 처리 방법
   
   • Deadlock Prevention - deadlock의 4가지 필요조건 중 어느 하나가 만족되지 않도록 하는 것
   • Deadlock Avoidance - 부가 정보를 이용해서 자원 할당이 deadlock으로부터 안전한지 파악하고 안전한 경우에만 할당
     
     • Resource Allocation Graph Algorithm: 점선을 포함하여 사이클이 생기지 않는 경우에만 자원 할당
     • Banker's Algorithm: 가용 자원으로 최대 자원 요청을 처리할 수 있는 요청에만 자원 할당
   • Deadlock Detection and Recovery - deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 발견 시 recover
     • Detection - single instance: 자원 할당 그래프에서 사이클이 곧 deadlock을 의미, wait-for-graph
     • Detection - multiple instance: 테이블을 그려서 현재 상태가 deadlock인지 탐지, 자원을 모두 할당하고 시작
     • Recovery - Process termination: 차단하는 방법(모두 중지, 한 프로세스 씩 중지)
     • Recovery - Process Preemption: 자원을 뺏는 방법(victim, rollback, restart, starvation)
   • Deadlock Ignorance - deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음

 

 

 

 

---

이화여자대학교 반효경 교수님의 [2014년 1학기 운영체제], [2017년 1학기 운영체제] 강의 정리입니다.

 [Operating System Concepts] 교재를 참고하였습니다. 감사합니다.

https://core.ewha.ac.kr/publicview/C0101020140411151510275738?vmode=f 

반효경 [운영체제] 16. Deadlock 1

https://core.ewha.ac.kr/publicview/C0101020140415131030840772?vmode=f 

반효경 [운영체제] 17. Deadlocks 2