반응형

데드락의 이해

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. 멀티인스턴스일 때 : 뱅커스 알고리즘 적용(조금 변형)
반응형