📑 본 글은 반효경 교수님의 운영체제 강의를 듣고 정리한 글입니다.
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에서 채택
