[운영체제] Deadlocks

데드락 (Deadlocks)

 

데드락은 일련의 프로세스들이 서로가 가진 자원을 기다리는 교착 상태를 의미한다.

 

이때 자원은 하드웨어 소프트웨어 등을 포함하는 개념이다.

ex) I/O device, CPU, memory space, semaphore...

 

 

 

 

 

 

데드락의 조건

 

Dealock은 아래의 4가지 조건을 동시에 만족할 때 발생한다.

Mutual Exclusion (상호 배제)

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

No Preemption (비선점)

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

Hold and Wait (보유 대기)

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

Circular Wait (순환 대기)

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

 

 

 

 

 

 

데드락의 처리 방법

Deadlock Prevention

자원 할당 시 Deadlock의 4가지 필요조건 중 어느 하나가 만족되지 않도록 하여 예방한다.

Deadlock Avoidance

자원 요청에 대한 부가적인 정보를 이용해서 deadlcok의 가능성이 없는 경우에만 자원을 할당한다.

즉, 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원을 할당한다.

Deadlock Detection and recovery

Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견 시 recovery를 수행한다.

Deadlock Ignorance

Deadlock을 시스템이 책임지지 않는다.

Unix를 포함한 대부분의 OS가 해당 방법을 채택하고 있다.

 

 

 

 

 

 

Deadlock Prevention

Mutual Exclusion

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

공유 가능한 자원들을 사용하면 배타적인 접근을 요구하지 않으므로 교착상태가 발생하지 않는다.

Hold and Wait

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

 

1. 프로세스 시작 시 모든 필요한 자원을 할당받게 한다.

2. 자원이 필요할 경우 점유하던 자원을 모두 놓고 다시 요청한다.

No Preemption

process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점되게 한다.

모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.

State를 쉽게 save 하고 restore 할 수 있는 자원에서 주로 사용한다.

CPU, memory 등에서 사용하는데 이때에는 선점당해도 주소를 기억하고 있기 때문이다.

Circular wait

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

예를 들어 순서가 3인 자원 R1를 보유 중인 프로세스가 순서가 1인 자원 R2를 할당받기 위해서는 우선 R1를 release 해야 한다.

 

Deadlock Prevention의 문제점

Utilization 저하, Throughput 감소, Starvation 문제가 존재한다.

 

 

 

Deadlock Avoidance

 

자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로부터 안전한 지를 동적으로 조사해서 안전한 경우에만 할당한다.

 

가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법이다.

 

Deadlock으로부터 안전한 상태를 safe state, 반대의 경우를 unsafe state라고 한다.

 

safe state에 있으면 deadlock이 발생하지 않으며 unsafe state에 있으면 deadlock이 발생할 가능성이 있다.

 

Single instance per resource types의 경우에는 Resource Allocation Graph algorithm을 사용하고

Multiple instance per resource types의 경우에는 Banker's Algorithm을 사용한다.

 

 

 

 

 

Deadlock Detection and Recovery

 

Single instance per resource types의 경우에 그래프에서의 cycle은 곧 deadlock을 의미하며

Multiple instance per resource types의 경우에는 Banker's Algorithm과 유사한 방법을 사용한다.

 

Deadlock에서 회복할 때, 두 가지 방법을 사용한다.

Process termination (프로세스 종료)

Abort all deadlocked processes (deadlock 프로세스를 모두 중지)

Abort one process at a time until the deadlock cycle is eliminated (deadlock이 제거될 때까지 한 프로세스씩 중지)

 

다만, 데이터 갱신 도중 종료된다면 데이터 무결성은 보장하기 때문에 프로세스를 종료하는 것은 어렵다.

 

또한, 어떤 프로세스를 중지할 것인지 결정해야 한다. 따라서 아래와 같은 요인들을 비교하여 결정한다.

 

프로세스의 우선순위

지금까지 프로세스가 수행된 시간과 지정된 일을 종료하는 데 더 필요한 시간

프로세스가 사용한 자원의 유형과 수

프로세스가 종료하기 위해 더 필요한 자원의 수

앞으로 종료해야 할 프로세스의 수

 

Resource Preemption (자원 선점)

교착상태가 제거될 때까지 자원을 선점하여 다른 프로세스에 주어야 한다.

 

- selection of victim

비용을 최소화할 victim을 선정한다.

선점의 순서를 정해야 한다.

 

- Rollback

safe state로 rollback 하여 process를 restart 한다.

 

- Starvation 문제

동일한 프로세스가 계속해서 victim으로 선정되는 경우

cost factor에 rollback 횟수도 같이 고려한다.