728x90
1. Deadlock
- 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
- 여기서 자원이란 하드웨어, 소프트웨어 등을 포함하는 개념이다.
- 프로세스가 자원을 사용하는 절차는 request, allocate, use, release로 이루어진다.
2. Deadlock 발생의 4가지 조건
- Mutual Exclusion : 매 순간 하나의 프로세스만이 자원을 사용할 수 있다.
- No Preemption : 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않는다.
- Hold and Wait : 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있다.
- Circular Wait : 자원을 기다리는 프로세스 간에 사이클이 형성되어야 한다.
3. resource-allocation graph(자원 할당 그래프)
- vertex가 process와 resource이고, edge가 request edge(process → resource)와 assignment edge(resource → process)인 그래프
- 그래프 안에 사이클이 없으면 deadlock이 아니고, 사이클이 있으면 자원 당 인스턴스가 하나만 있으면 deadlock이 발생하고, 여러 개가 있으면 deadlock일 수도, 아닐 수도 있다.
4. Deadlock의 처리 방법
- Deadlock Prevention
- 자원 할당 시 deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
- mutual exclusion은 만족되지 않도록 바꾸기 쉽지 않다.
- hold and wait의 경우 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법이나 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청하는 방법이 있다.
- no preemption의 경우 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원을 선점할 수 있게 한다. state를 쉽게 save하고 restore할 수 있는 CPU, memory같은 자원에서 사용한다.
- circular wait의 경우 모든 자원 유형에 할당 순서를 정해 정해진 순서대로만 자원을 할당한다. 즉, 특정 자원을 얻어야지 다른 자원을 얻을 수 있도록 한다.
- 하지만 utilization이 저하되고, throughput이 감소하며, starvation이 발생할 수 있다.
- Deadlock Avoidance
- 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원 할당
- 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
- 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법이다.
- safe state : 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
- safe sequence : sequence 내 각 프로세스의 자원 요청이 가용 자원 + 프로세스의 모든 보유 자원에 의해 충족되는 sequence
- 시스템이 safe state에 있으면 deadlock이 확실히 발생하지 않고, unsafe state에 있으면 deadlock이 발생할 가능성이 있다. 그래서 deadlock avoidance는 시스템이 unsafe state에 들어가지 않는 것을 보장한다.
- resource allocation graph algorithm
- 자원 유형 당 하나의 인스턴스만 있는 경우에 사용하는 알고리즘
- resource allocation graph에 claim edge(프로세스가 자원을 미래에 요청할 수 있는 경우)를 점선으로 표시하고, 프로세스가 해당 자원을 요청하면 request edge로 바뀐다. 자원이 release되면 assignment edge는 다시 claim edge로 바뀐다.
- 이때 request edge의 assignment edge 변경시 (점선을 포함하여) 사이클이 생기지 않는 경우에만 요청 자원을 할당한다.
- Banker's algorithm
- 자원 유형 당 여러 개의 인스턴스가 있는 경우에 사용하는 알고리즘
- 각 프로세스마다 사용하는 자원의 개수의 최댓값에서 현재 할당된 자원의 개수를 빼서 필요한 자원의 개수의 최댓값를 계산한 뒤, 어떤 프로세스가 자원을 요청하는 경우 해당 자원이 가용 자원에서 줄 수 있는 경우여도 앞에서 계산한 결과만큼을 더 줄 수 있는지를 판별해서 자원 할당을 할지 결정한다.
- Deadlock Detection and Recovery
- deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover
- deadlock detection은 resource-allocation graph에서 사이클이 존재하는지를 확인하거나, banker's algorithm과 유사한 방법을 활용한다.
- 특히 자원 유형 당 인스턴스가 하나만 있는 경우 resource-allocation graph를 변형해 wait-for graph를 만들 수 있다. wait-for graph는 프로세스만으로 node를 구성해 P가 가지고 있는 자원을 Q가 기다리고 있는 경우에 P → Q edge를 추가한다.
- wait-for graph도 사이클이 있는지를 조사함으로써 deadlock을 탐지한다.
- deadlock recovery
- process termination : 모든 deadlock process를 끝내거나, deadlock이 끝날 때까지 하나씩 process를 끝낸다.
- resource preemption : 비용을 최소화할 victim을 선정해 자원을 빼앗는다. 이를 통해 safe state로 rollback하면 process를 다시 시작한다. 다만 동일한 프로세스가 계속해서 victim으로 선정되면 starvation 문제가 발생한다. 따라서 cost factor에 rollback 횟수도 같이 고려해 한 프로세스만 계속 victim으로 선정되는 것을 막는다.
- Deadlock Ignorance
- deadlock을 시스템이 책임지지 않고 사용자가 해결하게 한다.
- 실제로 deadlock 발생 가능성은 매우 낮고 이를 해결하기 위한 위 세 가지 방법은 overhead가 크기 때문에 UNIX를 포함한 대부분의 OS가 채택하는 방식이다.
출처 : 운영체제 강의
728x90