↓Skip to main content

[OS] Chapter 8. 데드락

Table of Contents

운영체제와 정보기술의 원리 강의를 듣고 공부한 노트입니다.



데드락 #

  • 교착상태(deadlock)
    • 둘 이상의 프로세스가 서로 상대방이 가진 자원을 얻기 위해 무한히 기다리며 block된 상태이다.
    • 여기서 자원이란 하드웨어, 소프트웨어 등을 포함하는 개념이다. (예: I/O device, CPU cycle, memory space, semaphore 등)
    • 프로세스가 자원을 사용하는 절차: Request → Allocate → Use → Release



데드락 발생의 4가지 조건 #

조건 설명
상호 배제
(Mutual exclusion)		 매 순간 하나의 프로세스만 자원을 획득할 수 있다.
보유 대기
(Hold and wait)		 자원을 가진 프로세스가 다른 자원을 기다릴 때,
보유 자원을 놓지 않고 계속 가지고 있다.
비선점
(No preemption)		 프로세스의 자원을 강제로 빼앗을 수 없다.
순환 대기
(Circular wait)		 자원을 기다리는 프로세스 간에 사이클이 형성되어 있다.



데드락 해결 방법 #

예방 #

  • Deadlock Prevention
  • 자원 할당 시 데드락 발생의 4가지 조건 중 어느 하나가 만족되지 않도록 하는 것이다.

  • 만족되지 않도록 배제 할 수 있는 조건 살펴보기
조건 설명
상호 배제
(Mutual exclusion)		 공유하면 안 되는 자원은 이 조건을 반드시 성립해야 해서 배제 불가능.
보유 대기
(Hold and wait)		 자원을 요청할 때 자원을 가지지 않도록 하면 된다.
방법1. 프로세스 시작 시 모든 필요한 자원을 할당받게 한다.
방법2. 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청한다.
비선점
(No preemption)		 다른 자원을 요청할 때 자원을 보유한 자원을 빼앗을 수 있도록 한다. (선점)
상태를 쉽게 저장하고 복구할 수 있는 자원에서 주로 사용한다. (CPU, memory)
순환 대기
(Circular wait)		 모든 자원 유형에 할당 순서를 정해서 정해진 순서대로만 자원을 할당한다.
예를 들어, 1번, 3번 자원을 획득해야지만 5번 자원을 획득할 수 있는 것이다.
자원 A(순서 3)을 보유 중인데 자원 B(순서 1)을 할당받으려면 우선 자원 A를 해제해야한다.
하지만, 자원에 대한 이용률(Utilization)이 낮아지고, Throughput 감소, Starvation이 발생할 수 있다.



회피 #

  • Deadlock Avoidance
  • 자원 요청에 대한 부가적인 정보를 이용해서 자원 할당을 하면 데드락의 가능성이 없는지를 동적으로 검사해서 안전한 경우에만 자원을 할당하는 것이다.
  • 가장 단순하고 일반적인 모델은, 프로세스들이 시작될 때, 평생 필요로 하는 자원별 최대 사용량을 미리 선언하도록 하는 것이다.

safe, unsaafe, deadlock
Image Source

  • safe state
    • 데드락이 없는 안전한 상태이다.
  • safe sequence
    • 특정한 순서로 자원의 할당, 실행, 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서를 찾을 수 있다면, 그것을 안전 순서라고 부른다.
  • unsafe state
    • 데드락이 있을 가능성이 있는 상태이다.

  • 2가지 회피 알고리즘
    상황 알고리즘
    자원의 인스턴스가 1개일 때 자원 할당 그래프 알고리즘
    (Resource Allocation Grapeh algorithm)
    자원의 인스턴스가 여러개 일 때 은행원 알고리즘
    (Banker’s algorithm)

(1) 자원 할당 그래프 알고리즘 #

자원 할당 그래프
Image Source

  • $P_2$가 $R_2$자원을 할당받으면 사이클이 생기므로, $P_1$이 먼저 할당받는다.

(2) 은행원 알고리즘 #

  • 가정
    • 모든 프로세스는 자원의 최대 사용량을 미리 명시한다.
    • 그리고 자원을 최대 사용량만큼 할당 받은 프로세스는 작업이 끝나면 자원을 반납한다.
  • 방법
    • 현재 가용 자원(Available) 과 각 프로세스들이 작업을 완료하기 위해 필요한 자원(Need) 을 비교하여, 당장 작업을 마칠 수있는 프로세스부터 자원을 할당하여, 프로세스가 작업을 완료하고 반환하는 자원을 다른 프로세스에게 다시 할당하는 것이다.
프로세스명 Max Allocation Need
P0 10 5 5
P1 4 2 2
P2 9 2 7
  • 여기서 총 자원의 양이 12라고 한다면, 현재 Allocation은 9이므로, Available은 3이다.
    • 이 때, Need가 Available을 넘지 않는 P1이 2만큼 할당 받을 수 있겠다.
    • P1의 작업이 끝나고, 자원이 해제되어서 Available이 5가 되면, P0이 할당 받을 수 있다.
    • P0의 작업이 끝나고, 자원이 해제되어서 Available이 10이 되면, P2가 할당 받을 수 있다.



탐지 및 회복 #

  • Deadlock Detection and Recovery
  • 데드락 발생은 허용하되, 그에 대한 detection 루틴을 두어 데드락 발생 시 recover하는 것이다.

  • 2가지 탐지 및 회복 알고리즘
    상황 알고리즘
    자원의 인스턴스가 1개일 때 자원 할당 그래프의 변형인 대기 그래프(Wait-for graph)
    자원의 인스턴스가 여러개 일 때 은행원 알고리즘과 유사한 방법

(1) 대기 그래프(Wait-for graph) #

대기 그래프
Image Source

  • 자원 타입의 노드를 제거하고 프로세스만으로 노드를 구성해서 사이클이 존재하는지 조사한다. ($n^2$)

(2) 은행원 알고리즘과 유사한 방법 #

  • 은행원 알고리즘과 다른 것
    • 각 프로세스가 실제로 요청한 자원(Request) 개수를 사용한다. 이것은 추가적으로 요청할 수 있는 것(Need)과 다르다.
    • 현재 상태가 안전 상태(safe state)인지 확인하고, 불안정 상태(unsafe state)라면 데드락이라고 판단한 후 recovery 한다.

  • Recovery
    • 방법 1. Process Termination
      • 데드락과 연루된 프로세스를 모두 종료시킨다.
      • 혹은 데드락과 연루된 프로세스를 하나씩 종료시킨다.
    • 방법 2. Resource Preemption
      • 비용을 최소화하는 프로세스 희생양을 하나 찾아서, 자원을 뺏는다. (safe state로 rollback해서 프로세스를 다시 시작한다. )
      • 동일한 프로세스가 희생양이 되는 starvation 문제가 발생할 수 있다. 따라서 rollback 횟수도 고려해서 선정해야 한다.



무시 #

  • Deadlock Ignorance
  • 데드락을 시스템이 책임지지 않는 것이다. 데드락이 일어나지 않는다고 생각하고 아무런 조취도 취하지 않는다.
  • 만약 데드락이 발생하면, 시스템이 비정상적으로 작동한다는 것을 사람이 느끼고 직접 프로세스를 죽이도록 한다.
  • UNIX, Windows 등의 대부분의 운영체제가 채택한 방법이다.



↑