[운영체제] 7. Deadlock

📑 본 글은 반효경 교수님의 운영체제 강의를 듣고 정리한 글입니다.

Deadlock

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

자원

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

Deadlock 발생의 4가지 조건

Mutual exclusion

매 순간 하나의 프로세스만이 자원을 사용할 수 있다.

No preemption

프로세스는 자원을 내어 놓을 뿐 강제로 빼앗기지 않는다.

Hold and wait

자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있다.

Circular wait

자원을 기다리는 프로세스 간에 사이클이 형성되어야 한다.

Deadlock 처리 방법

Deadlock Prevention

자원 할당 시 데드락의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 한다.

Mutual Exclusion

공유해서는 안되는 자원의 경우 반드시 성립해야 한다.

Hold and Wait

프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.

No Preemption

• 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점된다.
• 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.

Circular Wait

모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당한다.

Deadlock Avoidance

• 자원 요청에 대한 부가적인 정보를 이용해서 데드락의 가능성이 없는 경우에만 자원을 할당한다.
• 시스템 상태가 원래 상태로 돌아올 수 있는 경우에만 자원 할당한다.
• 데드락 회피는 시스템이 불안전 상태에 들어가지 않는 것을 보장한다.
  • 자원 할당 알고리즘
    자원 유형 당 1개의 인스턴스만 존재
  • 은행원 알고리즘
    자원 유형 당 여러 개의 인스턴스 존재

자원 할당 알고리즘

• 요청 간선의 할당 간선 변경 시 (점선을 포함하여) 사이클이 생기지 않는 경우에만 요청 자원을 할당한다.
• 사이클 생성 여부 조사시 프로세스의 수가 n일 때 O(n^2) 시간이 걸린다.

은행원 알고리즘

가정

• 모든 프로세스는 자원의 최대 사용량을 미리 명시한다.
• 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 이들 자원을 다시 반납한다.

방법

• 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택한다.
• 할당받은 프로세스가 종료되면 모든 자원을 반납한다.
• 모든 프로세스가 종료될 때까지 이러한 과정을 반복한다.

Deadlock Detection and recovery

데드락 발생은 허용하되, 그에 대한 탐지 루틴을 두어 데드락 발견시 회복한다.

Wait-for 그래프 알고리즘

자원 유형 당 하나의 인스턴스만 존재한다.

• Wait-for 그래프
  • 자원 할당 그래프의 변형이다.
  • 프로세스만으로 node 구성함
  • Pj가 가지고 있는 자원을 Pk가 기다리고 있는 경우 Pk → Pj
• 알고리즘
  • Wait-for 그래프에 cycle이 존재하는지 주기적으로 조사한다.
  • 시간 복잡도는 O(N^2)이다.

Deadlock Ignorance

• 데드락을 시스템이 책임지지 않는다.
• 데드락이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는다.
• 데드락이 매우 드물게 발생하므로 데드락에 대한 조치 자체가 더 큰 오버헤드일 수 있다고 판단함.
• 만약, 시스템에 데드락이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 프로세스를 죽이는 등의 방법으로 대처한다.
• UNIX, Windows 등 대부분의 OS에서 채택