[OS] Deadlock

카테고리 없음

이진2 2021. 8. 7. 00:02

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

Resouce(자원)이란?

1. Mutual Exclusion : 매 순간 하나의 프로세스만이 자원을 선점할 수 있다

2. No Preemption : 프로세스는 스스로 자원을 내놓기 전까지는 강제로 빼앗기지 않는다

3. Hold and Wait : 자원을 가진 프로세스가 추가 자원을 기다릴 때 보유한 자원을 포기하지 않는다

4. Circular Wait : 자원을 기다리는 프로세스들 간에 사이클이 형성된다

반대로, 이 중 조건을 하나라도 만족하지 않으면 데드락이 형성되지 않는다 ❗❗

Resource - Allocation Graph

resource-allocation graph는 어떤 프로세스가 어떤 자원을 점유하고 있고, 현재 어떤 자원을 요구하는지 나타낸 그래프이다.

이 graph에서 cycle이 생기지 않으면, 데드락이 발생하지 않는다. 또한 resource마다 instance가 하나밖에 없으면 데드락이 발생할 수 있다.

데드락은 예방, 방지, 탐지 및 복구, 무시 방법을 통해 처리할 수 있다

: 자원 할당 시 데드락의 4 가지 필요 조건 중 어느 하나가 성립하지 않도록 하는 것

공유해서는 안 되는 자원의 경우 반드시 성립해야 함
프로세서가 자원 요청 시 다른 어떤 자원도 가지고 있지 않아야 함
- 프로세스 시작 시 모든 필요한 자원을 한번에 할당
- 자원이 필요할 경우 보유 자원을 모두 포기하고 다시 요청
프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨.
- 모든 필요한 자원을 얻을 수 있을 때 해당 프로세스 다시 시작
- State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용(CPU, memory)
모든 자원 유형에 할당 순서를 정해 그 순서대로만 자원 할당

하지만 utilization 저하, throughput 감소, starvation 문제가 발생할 수 있다.

: 자원 요청에 대한 부가적인 정보를 이용해서 데드락 가능성이 없을 때 에만 자원 할당

ex) 프로세스들이 필요로 하는 각 자원 별 최대 사용량을 미리 선언하도록 정의

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

safe sequence

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

➡ system이 unsafe state에 들어가지 않는 것을 보장한다 ❗

Avoidance 알고리즘에는 두 가지 종류가 있다

1. Single instance per resource types - Resourse Allocation Graph Algorithm

2. Multiple instances per resources types - Banker's Algorithm

Detection

+ Wait-for graph 알고리즘(Resource type 당 single instance인 경우): wait-for graph에 사이클이 존재하는지 주기적으로 조사하는 방법( O(n^2) )

Recovery

1. Process Termination

2. Resource Preemption

비용을 최소화 할 victim의 선정
safe state로 rollback하여 process를 restart
Starvation 문제 발생 가능
- 동일한 프로세스가 계속해서 victim으로 선정되는 경우
- cost factor에 rollback 회수도 같이 고려

: 데드락이 발생하지 않는다고 생각하고 아무런 조치도 취하지 않는다 ❗