[OS] 데드락

기초

• 정의: 일련의 프로레스( or 스레드)들이 서로가 가진 자원을 기다리며 block되어 더 이상 진행이 될 수 없는 상태

 

데드락 4가지 발생 조건

아래 4가지 조건이 모두 만족해야만 데드락 발생

• Mutual Exclusion(상호 배제): 매 순간 하나의 프로세스만이 자원을 사용 가능
• Hold & Wait(보유 대기): 한 스레드가 자원을 점유(hold)하고 있는 상황에서, 다른 자원을 얻기 위해 대기(wait)를 하고 있는 상황
• No Preemption(비선점): 프로세스는 OS에 의해 강제로 자원을 빼앗기지 않는다.
• Circular wait(순환 대기): 자원을 기다리는 프로세스 간에 사이클이 형성되어야 한다.

 

RAG

데드락을 시각적으로 더 잘 이해하기 위해서 관계를 그래프로 표현해보자!

• Resource-Allocation Graph: 자원과 스레드에 대한 방향 그래프
  • T1..n: 스레드들의 집합
  • R1..n: 자원들의 집합
  • T -> R : 스레드가 자원을 요청하는 edge
  • R -> T: 스레드에게 자원을 할당하는 edge

 

RAG 특징

• 사이클이 없다면, 무조건 데드락이 없음
• 사이클이 있다면, 데드락이 있을수도 있고 없을 수도 있음
  • 자원당 하나의 인스턴스만 접근할 수 있다면 Deadlock이고,
  • 여러 인스턴스가 존재하는 경우에는 Deadlock일 수도 있고 아닐 수 있다.

 

데드락 문제를 다루는 방법

• 완전 예방(prevention): 데드락이 아예 발생하지 않도록 처리 -> 아주 비싼 시스템 아니면 적용하지 않음
• 회피(avoidance): 데드락이 발생할 가능성이 있는 경우 아예 자원을 할당하지 않는 방식
• 탐지 및 회복(Detection & recover): 데드락이 발생했는지 주기적으로 감지하고, 발생 시 이를 회복하는 방법
• 무시(ignorance): 데드락이 일어나지 않는다고 생각하고 아무런 조치를 취하지 않는 방식

 

Ignorance 방법

• 정의: 데드락이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는 방식
  • 현대의 OS(windox, unix 등..)에서 채택하는 방식
• 목적:
  • 데드락이 매우 드물기 발생하는 문제이기에,
  • 데드락에 대한 조치 자체가 큰 오버헤드일 수 있기 때문이다.

 

Prevention 방법

데드락을 발생시키는 4가지 요인을 막아보자

• 상호배제: Critical Section 문제를 해결하기 위해서는 해당 조건을 반드시 만족
  • 해당 조건을 건들 수 없음
• 점유 & 대기: 점유하고 있는 상태에서 대기하지말고, 대기상태로 들어갈때 점유하고 있는것을 다 포기
  • 성능 상의 이유로 추천하지 않음
• 선점 불가: 다른 자원을 요청하고 있는데 다른 프로세스가 자원을 가지고 있으면 뺏자
  • 하지만 그러면 어떤 문제가 발생할지 모름
• 순환 대기: 자원의 타입에 따라 프로세스마다 할당 순서를 정하여 정해진 순서대로만 자원을 할당
  • 얘는 할만은 한데 그래도 어려움

데드락을 방지하는 방식은 효율성과 처리량을 감소시키고 기아(starvation)이 발생할 수 있음.

 

Avoid 방법

• 정의: 데드락이 발생할 가능성이 있는 경우 아예 자원을 할당하지 않는 방식
• 핵심: 데드락이 발생할 수 있는 unsafe state를 피하는 것
  • 자원에 request 할때마다 safe state인지 아닌지 파악
  • safe state가 안되면 자원 요청을 거절하는 방법으로 avoid하는 것

• 방법:
  • 자원 할당 그래프(RAG) 알고리즘: 각 자원마다 하나의 인스턴스만 존재하는 경우
    • RAG 그래프에서 사이클이 발생하지 않는 경우에만 자원을 할당하는 방법
  • 뱅커(Banker's) 알고리즘

 

Detection & Recovery 방법

• 정의: 주기적인 사이클로 데드락이 발생했는지 여부를 파악하고, 발생했다면 Recovery 작업을 하는 방법
• 목적:
  • 만약 시스템이 데드락을 예방 or 회피하지 않는다면, 데드락이 발생할 수 있음
  • 하지만 성능상 보통의 시스템은 예방 or 회피하지 않음
  • 그래서 데드락 상태를 허용하고, 데드락이 발생했는지 확인하는 장치를 만들자
• 탐지 방법은 Avoid 방법과 동일함
  • 자원 할당 그래프(RAG) 알고리즘: 각 자원마다 하나의 인스턴스만 존재하는 경우
  • 뱅커(Banker's) 알고리즘: 각 자원에 여러 인스턴스가 존재할 수 있는 경우
• Recovery 방법: 데드락을 해결하기 위해 특정 프로세스를 선정해서 종료시켜야함
  • 관련된 모든 스레드(or 프로세스)를 재시작하는 방법
  • 한번에 하나씩 관련된 스레드를 재시작해보는 방법