logo
Published on

OS : 교착상태 DeadLock

Authors
  • avatar
    Name
    Bora Choi
    Twitter

DeadLock의 개념

  • Blocked/ Asleep state

    • 프로세스가 특정 이벤트를 기다리는 상태
    • 프로세스가 필요한 자원을 기다리는 상태
  • Deadlock state

    • 프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우 : 프로세스가 deadlock 상태에 있음
    • 시스탬 내에 deadlock에 빠진 프로세스가 있는 경우 : 시스템이 deadlock 상태에 있음
  • Deadlock vs Starvation

    • starvation: ready 상태
    • daedlock : asleep 상태, transition impossible

자원의 분류

  • 일반적 분류
    • HW resources vs SW resources
  • 다른 분류법
    • 선점 가능 여부에 따른 분류
    • 할당 단위에 따른 분류
    • 동시 사용 가능 여부에 따른 분류
    • 재사용 가능 여부에 따른 분류

선점 가능 여부에 따른 분류

  • Preemptible resources
    • 선점당한 후, 돌아와도 문제가 발생하지 않는 자원
    • Processor,memory 등
  • Non-preemptible resources
    • 선점 당하면, 이후 진행에 문제가 발생하는 자원 : Rollback, restart 등 특별한 동작이 필요
    • disk drive 등

할당 단위에 따른 분류

  • Total allocation resources

    • 자원 전체를 프로세스에게 할당
    • Processor,disk drive등
  • Partitioned allocation resources

    • 하나의 자원을 여러 조각으로 나누어, 여러 프로세스들에게 할당
    • memory 등

동시 사용 가능 여부에 따른 분류

  • Exclusive allocation resources

    • 한순간에 한 프로세스만 사용 가능한 자원
    • Processor,memory, disk drive 등
  • Shared allocation resource

    • 여러 프로세스가 동시에 사용 가능한 자원
    • Programs(sw), shared data 등

재사용 가능 여부에 따른 분류

  • SR (serially-reusable resources)
    • 시스템 내에 항상 존재하는 자원
    • 사용이 끝나면, 다른 프로세스가 사용 가능
    • Processor, memory, disk drive, program 등
  • CR (Consumable Resources)
    • 한 프로세스가 사용한 후에 사라지는 자원
    • signal, message 등

Deadlock과 자원의 종류

  • deadlock을 발생시킬 수 있는 자원의 형태
    • Non-preemptible resources
    • Exclusive allocation resources
    • Serially reusable resources
  • CR을 대상으로 하는 deadlock model
    • 너무 복잡

Deadlock 발생으 필요조건

  • 자원의 특성
    • Exclusive use of resources
    • Non-preemptible resources
  • 프로세스의 특성
    • Hold and wait(Partial allocation)
      • 자원 하나 hold 하고 다른 자원 요청
    • Circular wait

Deadlock 해결 방법

  • Deadlock prevention methods
  • Deadlock avoidance method
  • Deadlock detection and deadlock recovery methods

Deadlock Prevention

  • 4개의 deadlock 발생 필요 조건 중 하나를 제거
  • Deadlock이 절대 발생하지 않음

모든 자원의 공유 허용

  • Exclusive use of resources 조건 제거
  • 현실적을 불가능

모든 자원에 대한 선점 허용

  • Non-preemptible resources 조건 제거
  • 현실적으로 불가능
  • 유사한 방법
    • 프로세스가 할당받을 수 없는 자원을 요청한 경우, 기존에 가지고 있던 자원을 모두 반납하고 작업 취소
      • 이후 처음(또는 check-point) 부터 다시 시작
    • 심각한 자원 낭비 발생 ➡️ 비현실적

필요 자원 한번에 모두 할당(total allocation)

  • Hold and wait 조건 제거
  • 자원 낭비 발생 : 필요하지 않은 순간에도 가지고 있음
  • 무한 대기현상 발생 가능

circular wait 조건 제거

  • Totally allocation을 일반화 한 방법
  • 자원들에게 순서를 부여
  • 프로세스는 순서의 증가 방향으로만 자원 요청 가능
  • 자원 낭비 발생

❇️ Deadlock Prevention

  • 4개의 deadlock 발생 필요 조건 중 하나를 제거
  • Deadlock 이 절대 발생하지 않음
  • 심각한 자원 낭비 발생
    • low device utilization
    • reduced system throughput
  • 비현실적

Deadlock Avoidance

  • 시스템의 상태를 계속 감시
  • 시스템이 deadlock 상태가 가능성이 있는 자원 할당 요청 보류
  • 시스템을 항상 safe state로 유지

Safe state

  • 모든 프로세스가 정상적 종류 가능한 상태
  • Safe sequence가 존재 : Deadlock 상태가 되지 않을 수 있음을 보장

Unsafe state

  • Deadlock 상태가 될 가능성이 있음
  • 반드시 발생한다는 의미는 아님

가정

  • 프로세스의 수가 고정됨
  • 자원의 종류와 수가 고정됨
  • 프로세스가 요구하는 자원 및 최대 수량을 알고 있음
  • 프로세스는 자원을 사용후 반드시 반납한다

➡️ Not practical!

Deadlock Avoidance Algorithm

  • Banker's algorithm
  • Habermann's algorithm

Dijkstra's banker's algorithm

  • Deadlock avoidance를 위한 간단한 이론적 기법
  • 한 종류(resource type)의 자원 여러 개 (unit)
  • 시스템을 항상 safe state로 유지

Habermann's algorithm

  • Dijkstra's algorithm의 확장
  • 여러 종류의 자원 고려
    • multiple resource types
    • multiple resource units for each resource type
  • 시스템을 항상 safe state로 유지

✳️ Deadlock Avoidance

  • Deadlock의 발생을 막을 수 있음
  • High overhead : 항상 시스템을 감시하고 있어야한다
  • Low resource utilization : safe state유지를 위해, 사용되지 않는 자원이 존재
  • Not practical
    • 가정 : 프로세스 수, 자원수 고정/ 필요한 최대 자원 수를 알 수 있음

Deadlock Detection

  • Deadlock 방지를 위한 사전 작업을 하지 않음

    • Deadlock이 발생 가능
  • 주기적으로 deadlock 발생 확인

    • 시스템이 deadlock 상태인가?
    • 어떤 프로세스가 deadlock 상태인가?
  • Resource Allocation Graph (RAG) 사용

    Resource Allocation Graph (RAG)

    • Deadlock 검출을 위해 사용
    • Directed, bipartite Graph

Deadlock Detection Method

Graph reduction

  • 주어진 RAG에서 edge를 하나씩 지워가는 방법

  • Completely reduced

    • 모든 edge가 제거 됨
    • Deadlock에 빠진 프로세스가 없음
  • Irreducible

    • 지울 수 없는 edge가 존재
    • 하나 이상의 프로세스가 deadlock 상태
  • Unblocked process

    • 필요한 자원을 모두 할당 받을 수 있는 프로세스

Graph reduction procedure

  1. Unblocked process에 연결 된 모든 edge를 제거
  2. 더 이상 unblocked process가 없을 때까지 1 반복
  • 최종 Graph에서
    • 모든 edge가 제거 됨 (Completely reduced)
      • 현재 상태에서 deadlock이 없음
  • 일부 edge가 남음 (irreducible)
    • 현재 deadlock이 존재

Graph Reduction

  • High overhead
    • 검사 주기에 영향을 받음
    • Node의 수가 많은 경우

Deadlock Recovery

  • Deadlock을 검출 한 후 해결 하는 과정

  • Deadlock recovery methods

    • Process termination
      • Deadlock 상태에 있는 프로세스를 종료 시킴
      • 강제 종료 된 프로세스는 이후 재시작 됨
  • Resource preemption

    • Deadlock 상태 해결 위해 선점할 자원 선택
    • 선정 된 자원을 가지고 있는 프로세스에서 자원을 빼앗음
      • 자원을 빼앗긴 프로세스는 강제 종료 됨

Process termination

  • Deadlock 상태인 프로세스 중 일부 종료

  • Termination cost model

    • 종료 시킬 deadlock 상태의 프로세스 선택
    • Termination cost - 우선순위 / Process priority - 종류 / Process type - 총 수행 시간 / Accumulated execution time of the process - 남은 수행 시간 / Remaining time of the process - 종료 비용 / Accounting cost
  • 종료 프로세스 선택

  • Lowest-termination cost process first

    • Simple
    • Low overhead
    • 불필요한 프로세스들이 종료 될 가능성이 높음
  • Minimum cost recovery

    • 최소 비용으로 deadlock 상태를 해소 할 수 있는 process 선택
      • 모든 경우의 수를 고려 해야 함
    • Complex
    • High overhead
      • O(2k)

Resource preemption

  • Deadlock 상태 해결을 위해 선점할 자원 선택
  • 해당 자원을 가지고 있는 프로세스를 종료 시킴
    • Deadlock 상태가 아닌 프로세스가 종료 될 수도 있음
    • 해당 프로세스는 이후 재시작 됨
  • 선점할 자원 선택
    • Preemption cost model 이 필요
    • Minimum cost recovery method 사용
      • O(r)

Checkpoint-restart method

  • 프로세스의 수행 중 특정 지점(checkpoint) 마다 context를 저장
  • Rollback을 위해 사용
    • 프로세스 강제 종료 후, 가장 최근의 checkpoint에서 재시작