반효경 교수님의 운영체제 강의를 참고하였습니다.

(https://core.ewha.ac.kr/publicview/C0101020140318134023355997?vmode=f)

일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태

  • Resource
    • 하드웨어, 소프트웨어 등을 포함하는 개념
    • ex) I/O devices, CPU cycle, memory space, semaphore
    • 프로세스가 자원을 사용하는 절차
      • Request, Allocate, Use, Release

데드락이 발생하는 4가지 조건

  1. Mutual exclusion(상호 배제)
    • 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
  2. No preemption(비선점)
    • 프로세스는 자원을 잠깐 내어놓을 뿐 강제로 빼앗기지 않음
  3. Hold and wait(보유대기)
    • 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
  4. Circular wait(순환대기)
    • 자원을 기다리는 process간에 사이클 형성

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

  • Vertex
    • Process Pi
    • Resource Rj
  • Edge
    • Request edge Pi → Rj
    • assignment edge Rj → Pi

https://user-images.githubusercontent.com/28971015/117011018-5e75af00-ad28-11eb-9811-428a302ada87.png

deadlock 발생O

https://user-images.githubusercontent.com/28971015/116878447-57806b00-ac5a-11eb-9bb9-25df0f29589d.png

deadlock 발생

  • 그래프에 cycle이 없으면 deadlock이 아니다.
  • 그래프에 cycle이 있으면
    • 자원당 인스턴스가 하나밖에 없으면 데드락임
    • 자원당 여러인스턴스일때, 데드락이 발생할 수 있음

Deadlock의 처리 방법

  • Deadlock Prevention
    • 자원 할당 시 Deadlock의 4가지 필요조건 중 어느 하나가 만족되지 않도록 하는 것
      • Mutual Exclusion
        • 무조건 성립해야 함
      • Hold and Wait
        • 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 함
        • 방법1 : 프로세스 시작시 모든 필요한 자원을 할당
        • 방법2 : 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청
      • No Preemption
        • 자원을 preemption할 수 있도록 처리
      • Circular Wait
        • 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
    • 이 모든 것은 Utilization 저하, Throughput 감소, Starvation 문제 발생
  • Deadlock Avoidance

    • 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원 할당

    • 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당

    • 2가지 경우의 알고리즘

      • Single instance per resource types
        • Resource Allocation Graph algorithm 사용
        • 점선 : process가 resource를 사용할 가능성

      https://user-images.githubusercontent.com/28971015/116880000-65cf8680-ac5c-11eb-90de-75380d21995a.png

      • Multi instances per resource types
        • Banker’s Algorithm 사용

      https://user-images.githubusercontent.com/28971015/116880428-f60dcb80-ac5c-11eb-9d11-4898c1c16bb5.png

      • 요청할 수 있는 양이 Available 보다 적어야 하고 동시에 Available은 Need보다 커야함
      • 즉 P0가 request(0, 2, 0)을 했을 때 Available에서는 줄 수 있지만 Available이 Need보다 적기 때문에 할당하지 않는다(언제 Need만큼 요청할지 모르니까)

    • 가용 자원을 준다고 deadlock이 되진 않지만 최악의 상황을 피하기 위해 safe한 상태를 유지하는 것

  • Deadlock Detection and recovery
    • Deadlock 발생을 허용하되 그에 대한 detection루틴을 두어 deadlock 발생시 recovery
    • 얼마 일어나지도 않는 deadlock을 위해 자원을 투자하지 않고 발생하면 처리하겠다는 방법

      • Resource Allocation Graph

        • Resource type당 single instance인 경우

          https://user-images.githubusercontent.com/28971015/116883048-1db26300-ac60-11eb-922a-7db38639046c.png

          • 자원할당 그래프에서의 cycle이 곧 deadlock을 의미

      • Corresponding wait-for graph

        https://user-images.githubusercontent.com/28971015/116883093-2a36bb80-ac60-11eb-9897-5887775cc9e2.png

        • Resource type 당 single instance인 경우
        • Wait-for graph
          • 자원할당 그래프의 변형
          • 프로세스만으로 node 구성
          • Pj가 가지고 있는 자원을 Pk가 기다리는 경우 Pk → Pj
        • Algorithm : O(N^2) → Cycle을 찾는 시간

      • Resource type 당 multiple instance인 경우

        https://user-images.githubusercontent.com/28971015/116884107-5272ea00-ac61-11eb-9fe9-57b55097edd3.png

        • P1이 R(2,0,2)를 요청하는데 반납할 자원이 P0 뿐인데 B(1)만 반납을 한다. 그러면 이 때 처리 가능한게 없으므로 deadlock이 발생한다고 본다.

      • Recovery 방법

        • Process termination
          • Process를 전부 죽임
          • Process를 하나씩 죽임(데드락이 풀릴 때 까지)
        • Resource Preemption
          • 비용을 최소화할 victim 선점
          • safe state로 rollback하여 process를 restart
          • Starvation 문제
            • 동일한 프로세스가 계속해서 victim으로 선정
            • cost factor에 rollback 횟수도 같이 고려
  • Deadlock Ignorance
    • 시스템이 deadlock을 책임지지 않음
    • UNIX를 포함한 대부분의 OS가 채택
    • 사용자가 직접 process를 죽이는 등으로 대처