[운영체제 공룡책] 8. Deadlock

데드락의 이해

8.1 System Model

• deadlock : 동일 집합 내에 프로세스들이 wait 상태에서 빠져나가지 못하는 상태 (해당 스레드가 요청한 리소스가 다른 프로세스나 스레드에 의해 자원이 점유되었기 때문에 wait 상태에서 다시 상태가 변하지 않음)

3.2 Deadlock in Multithreaded Applications

• 스레드가 자원을 사용하는 과정 : Request - use - Release
  • use 단계가 크리티컬 섹션으로 볼 수 있음
  • use 섹션에 여러 개의 자원, 인스턴스가 들어갈 수 있음

3.2 Deadlock Characterization

• Deadlock 발생의 네 가지 조건
  • Mutual Exclusion 상호 배제 : 한 번에 여러 개의 스레드가 자원을 점유할 수 있다면 데드락이 발생하 지 않겠지. 자원 획득을 위해 기다릴 이유가 없어지니꽈!
  • Hold and Wait 점유 대기
  • No preemption 선점 불가 : 중간에 다른 스레드가 자원을 강제로 빼앗을 수 있다면 데드락이 발생하지 않겠지
  • Circular Wait 순환 대기
• Resource-Allocation Graph : 실제로 구현이 어려우니 데드락 상황을 잘 이해하기 위해 만드는 그래프
  • 데드락 발생
  • 순환이 되지만 데드락 발생안함
• 중요한 관찰
  • Resource-allocation 그래프를 보니까 싸이클이 없으면 절대 데드락 상황에 빠지지 않는 다는걸 깨달음!
  • RAG를 통해 싸이클을 어떻게 활용하느냐는 나중에 ㄱㄱ
• 그래서 데드락 어떻게 다뤄야해?
  • 그냥 무시하자
  • 어떤 방법을 쓰던지 아예 방지(prevent, 근데 거의 불가능)하거나 avoid(비싸지만 Banker’s Algorithm으로 이용 가능)
  • 데드락 내버려두고 detect(모니터링)와 recover 진행

8.5 Deadlock Preventiom

• Deadlock Prevention (데드락 방지)
  • 네 가지 조건이 모두 충족되어야 데드락이 발생하니까, 적어도 한 개의 조건이 발생하지 않도록 막아보면 되지 않을까? 라는 관점으로 접근
  • Mutual Exclusion 상호배제를 막아보자 : 모든 자원을 공유 가능하게 하면 어떨까? 불가능데스요
  • Hold and Wait : 쓰레드가 자원을 요청할 때 다른 스레드가 점유하고 있으니 문제가 되는 거니까, 이 부분을 막아보면 어떨까? 내가 어떤 자원에 점유하고 싶을 때에는 갖고 있는 자원을 모두 내려놓는방식으로! 근데 너무 번거롭고 현실적이지 못하다요
  • No preemption 선점불가 : 어떤 스레드가 어떤 리소스 점유하고 있는데 다른 스레드가 강제로 선점 가능하게 만든다면 어떨까? 더 심한 문제가 발생할 수 있어서 현실적으로 좋은 방법이 아님
  • Circular Wait 순환대기 : 떄떄로 practical한 솔루션. 하지만 위 세 개 보다는 현실적이고 실현가능한 아이디어로 순환대기를 막아서 데드락을 방지할 수 있다!
    • 자원에게 순서를 부여하고, 자원 접근에 요청할 때 내가 점유하고 있는 리소스들보다 번호가 높은 것만 요청하도록 함
    • 대신 starvation의 위험은 높아짐
    • 근데 이렇게 grand lock(?)을 사용 데드락을 완전히 방어할 수는 없다
    • Transaction 원자

여튼 Deadlock 을 방지하는 것은 비싸고 비효율적이다. 우리는 피하자! Avoid 하는 유우명 알고리즘 Banker’s 알고리즘에 대해 배우자.

데드락과 뱅커 알고리즘

8.6 Deadlock Avoidance

• 데드락 방지(prevention)은 단점이 더 많았고(사이드 이팩트, CPU 사용률 저하), 그나마 조치 가능한 조건은 순환 대기였음
• Deadlock Avoidance
  • future deadlock : 미래에 발생 가능한 데드락에 대해 생각해보자
  • 각 스레드(프로세스) 어떻게 요청할 지 안다면 그 요청이 데드락 발생 가능성이 있는지 없는지 알 수 있겠지. 만약 데드락 발생 가능성이 있다면 요청을 거절하면 된다
• 선행 지식
  • 어떤 알고리즘으로 데드락 상태에 들어가지 못하게 아예 막아버리자!
  • maximum number of resources : 스레드가 요청할 수 있는 최대의 자원 개수?
  • state of resource allocation
    • number of available resource : 가용한 리소스의 수
    • numbe of allocated resource : 점유되고 있는 리소스의 수
  • maximum demands of the threads : 스레드가 앞으로 요구할 리소스의 최대 수
• Safe State 안전상태
  • 어떤 시스템, 상태가 안전하다는 것(=deadlock free)은 자원을 각 스레드에게 멕시멈까지 제공해줄 수 있다는 것임
  • 안전 상태에 놓일 수 있는 스레드의 실행 순서가 존재함. 그걸 safe sequence라고 칭함
• Basic facts
  • unsafe 상태라 하더라도 데드락이 발생할 수도 있고, 안할 수도 있음
  • 근데 모든 unsafe가 데드락 발생 가능성이 있기 때문에 아예 safe state에만 머무리게 하자!는게 avoidance의 컨셉임
• safe state라면 요청을 granted 해주고, 아니라면 rejected
• 스레드 입장에서는 자원에 접근 요청하기 전에 커널에게 안전한 상태인지 항상 물어보는 거임
• RAG(Resource-allocation graph)
  • 좌측 그래프는 T1, T2가 R2에 자원을 접근해도 되는지 요청한 상태이고, 아직 R2 자원을 할당한 애가 한명도 없기 때문에 T2은 R2에 접근하게 된다.
  • T2가 R2에 접근 허락을 얻어 할당한 모습이 우측 그래프이다. 이 때에는 R2가 T2에게 할당되어 있기 때문에, T1이 R2 자원 요청 시 대기하게 되고 T2가 자원을 릴리즈 하게 되면 그 이후 재요청하여 접근이 허락되게 된다.
• Banker’s Algorihm
  • RAG는 multiple instances일 때에는 사용할 수 없기 때문에 은행원 알고리즘을 사용함
  • 은행원 알고리즘은 RAG보다 효율이 떨어지고 복잡하다
  • 알잘딱 설명 블로그
• 은행원 알고리즘의 데이터 구조
  • n : 스레드의 개수
  • m : 리소스의 타입의 수
  • available : 가용한 리소스 타입의 개수를 가지고 있는 벡터
  • max : 각 스레드가 앞으로 요청할 리소스 인스턴스의 최대 개수
  • allocation : 각 스레드에게 할당된 리소스의 수
  • need : 각 스레드가 앞으로 요청할 리소스의 수
• 데이터 구조의 예시
  • Available[m] : 만약 Available[j] == k 라면, Rj 리소스의 K 개의 인스턴스가 가용하다는 뜻
  • Max[ n x m] : Max[i][j] == k라면, Ti 스레드가 최대 Rj 리소스의 k개의 인스턴스를 요청할 것이라는 뜻
  • Allocation[n x m] : Allocation[i][j] == k라면, Ti 스레드가 현재 Rj 리소스의 k개의 인스턴스를 점유하고 있다는 뜻
  • Need[n x m] : Need[i][j] == k, Ti가 Rj 리소스에게 k개의 인스턴스만큼 더 요청할 수도 있다는 뜻
  • 각 알고리즘은 이해하기 어려우니까 문제를 풀면서 공식을 확인해보면서 공부해라
• Safety Algorithm(== 뱅커스 알고리즘) : 이 시스템 스냅샷이 세이프하냐 안하냐! (2) 할당할 수 있는 조건이 존재하는지 확인, 그리고 (3) 존재한다면 할당하고 (4) 할당이 되었으면 종료 가능하다고 뜨루함! 할당한 그 순서가 safe sequence가 되는 거임
• Resource-Request Alhorithm : (1) 요청이 주어졌을 때, 내가 필요하는 것 보다 같거나 작아야하고 (2)가용한 자원보다 같거나 작아야함! (3) 충족한다면 다시 safety 알고리즘 돌려보고 충족하면 허락해주고 아니면 리젝시킴

8.7 Deadlock Detection

• prevent나 avoid를 해주지 않으면 데드락이 발생할 수 있음
  • 근데 리소스 접근 요청때마다 검증해야함. 그리고 멀쩡한 요청도 거절될 수 있어서 시스템에게 부하가 될 수 있음! 데드락이 걸리면 크리티컬한 시스템일 경우에만 이렇게 방어나 방지를 함
  • 실생활에서는 그냥 데드락을 허용해주고 데드락 상태가 되었는 지를 감시 determine하고, 만약 데드락이 발생했으면 알고리즘을 이용하여 데드락 상태를 recover 해주자!
• 데드락 모니터링 및 회복 - 싱글 인스턴스
  • Signle Instance 일 때에는 wait-for graph(RAG랑 똑같은데 약간 변형된거) : 주기적으로 어떤 알고리즘을 돌려서 싸이클이 생겼는지 확인
  • wait-for graph
    왼쪽 RAP 처럼 자원이 필요없음. 어떤 스레드가 어떤 스레드에게 의존적인지 그리는 것임!
    그래서 싱글인스턴스에서 사이클 이펙션을 그리는 것은 wait for graph를 그리는 것과 똑같다
• 데드락 모니터링 및 회복 - 여러 개의 인스턴스
  • 이 때에는 은행원 알고리즘과 유사한 것을 적용한다!
    • 은행원 알고리즘 때에는 이 요청이 데드락을 유발하냐 안하냐를 봤었는데, 지금은 그냥 내버려두기로 한거잖아! 요청을 그대로 받아들여서 은행원 알고리즘을 돌리면 됨. 그리고 초기화 부분과 판단 부분이 조금 다르다.

8.8 Recovery from Deadlock

• 일단 detection이 prevention, avoidance보다 훨씬 효율적인 것은 알게 됐다
• 얼마나 자주 데드락이 일어나느냐에 따라서 detection algorithm을 자주 수행시킴. 근데 굉장히 자주 일어나면 시스템 호출이 잘못된거라 의심해봐야함
  • 스레드의 개수에 따라서 데드락 발생 확률이 높아질 수 있음.
  • 모든 요청에 detection 알고리즘을 돌린다면 오버헤드가 발생함. 적절한 주기로 돌려야함. 만약 1년에 한번 정도 데드락이 발생할 거 같으면 하루에 한번이나, 1개월애 한 번 정도 돌려서 데드락 싸이클을 발견해주는게 좋다
  • 만약 데드락이 발생하면 알람을 오게 하거나 바로 회복 시켜서 시스템이 문제없이 돌아가게 할 수 있따. 아래처럼 두 가지 방법이 있겠다
• Deadlock Recovery
  • Process and Thread Termination : 데드락을 발생시킨 스레드 집합을 재실행 시키거나 혹은 한 두 개 씩 죽여보고 데드락 싸이클이 해소되는 지 봄
  • Resource Preemption
    • selecting a victim : 제일 최근에 시작된, 저렴한 리소스를 강제로 빼앗아서 요청한 스레드에게 줘버림
    • Rollback : 그리고 프로세스 롤백시켜서 safe state로 오는 걸 확인한 다음에 restart 시킴
    • Starvation : 대신 기아 상태가 발생할 수 있다

교수님 정리

1. Deadlock
   1. prevention 데드락 발생 4가지 조건 중 하나를 막자. 순환대기를 막음
   2. avoidance
      1. 싱글인스턴스일 때 : RAG
      2. 멀티인스턴스일 때 : 뱅커스 알고리즘
   3. Detection
      1. 싱글인스턴스일 때 : RAG 변형하여 자원 제거하고 스레드 간의 의존성을 확인함
      2. 멀티인스턴스일 때 : 뱅커스 알고리즘 적용(조금 변형)