반효경 운영체제 - 6. DeadLock

이 포스팅은 반효경 교수님의 운영체제 강의를 수강 후 내용을 정리한 글입니다.

 

Deadlock

Deadlock이란? 일련의 프로세스들이 서로가 가진 자원(Resource)을 기다리며 block된 상태이다.

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

Deadlock 발생의 4가지 조건

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

자원 할당 그래프

Deadlock의 처리 방법

• Deadlock Prevention
  • 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
• Deadlock Avoidance
  • 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당
  • 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
• Deadlock Detection and recovery
  • Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견 시 recover
• Deadlock ignorance
  • 운영체제 대부분에서 채택
  • Deadlock 발생해도 무시

Deadlock Prevention

생기지도 않을 수 있는 deadlock 때문에 많은 제약조건이 생겨 Utilization 저하, throughput 감소, starvation 문제가 발생할 수 있다.

• Mutex Exclusion
  • 공유해서는 안되는 자원의 경우 성립해야함
• Hold and Wait
  • 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
  • 방법 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
  • 방법 2. 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청
• No Preemption
  • process가 어떤 자원을 기다려야하는 경우 이미 보유한 자원이 선점됨
  • 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
  • State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용(CPU, memory)
• Circular Wait
  • 모든 자원 유형에 할당 순서(우선 순위)를 정하여 정해진 순서대로만 자원 할당
    • 예를 들어 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj을 할당 받기 위해서는 우선 Ri를 release해야한다.
    • 1번을 획득해야 3번을 획득할 수 있고, 1번이 없으면 3번을 얻을 수 없다.

Deadlock Avoidance

• 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로부터 안전한지를 동적으로 조사해서 안전한 경우에만 할당
• 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법

• 데드락이 생길 수 있는 경우 자원을 할당하지 않음

Safe state

시스템 내 프로세스들에 대한 safe sequence가 존재하는 상태

Safe sequence

• 프로세스들의 sequence <P1, P2, ..., Pn>이 safe하려면 Pi의 자원 요청이 "가용 자원 + 모든 Pj의 보유 자원"에 의해 충족되어야 한다.
• 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
  • Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj(j < i)가 종료될 때까지 기다린다.
  • Pi-1이 종료되면 Pi의 자원요청을 만족시켜 수행한다.

 

 

Deadlock Detection and Recovery

• DFS, BFS 등 알고리즘으로 모든 노드를 순회하면서 데드락을 확인할 수 있음
• 발견이 되면 Recovery를 한다.
  • Process Termination
    • 데드락에 연루된 모든 프로세스를 중단시킨다.
    • 하나씩 프로세스를 중단시키면서 데드락이 사라지는지 확인한다.
  • Resource Preemption
    • 비용을 최소화할 victim의 선정
    • safe state로 rollback하여 restart
    • Starvation 문제
      • 동일한 프로세스가 계속해서 viction으로 선정되는 경우
      • cost factor에 rollback 횟수도 고려

Deadlock Ignorance

• Deadlock이 매우 드물게 발생하므로 탐지에 대한 overhead가 크다.
• Deadlock이 발생한 경우 시스템이 비정상적으로 작동한 것을 사람이 느낀 후 직접 process를 죽이는 등의 방법으로 대처