데드락 (DeadLock)

데드락이란?

 - 둘 이상의 프로세스에서 자기 자원은 놓지 않고(lock) 다른 프로세스가 자원을 내놓기를 바라는 상태 (wait)

 

- 결과적으로 아무것도 완료되지 못해 무기한 기다리게 된다.

 

- '교착 상태'라고도 부름

 

- 한정된 자원을 여러 곳에서 사용하려고 할 때 발생

 

 

 

 

데드락이 일어나는 경우

프로세스1과 2가 자원1, 2를 모두 얻어야 한다고 가정해보자

 

 t1 : 프로세스1이 자원1을 얻음 / 프로세스2가 자원2를 얻음 

 t2 : 프로세스1은 자원2를 기다림 / 프로세스2는 자원1을 기다림

 

현재 서로 원하는 자원이 상대방에 할당되어 있어서 두 프로세스는 무한정 wait 상태에 빠짐

 

→ DeadLock

 

 

멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황에서 발생할 수 있다.

 

 

 

 

데드락 발생 조건

4가지 모두 성립해야 데드락 발생 (하나라도 성립하지 않으면 데드락 문제 해결 가능)

 

4가지 조건이 필요조건으로 4조건이 모두 맞았다고 데드락이 발생하는 것은 아니다. 발생 가능한 조건이 생긴 것.

 

 

1 상호 배제 (Mutual exclusion)

자원은 한번에 한 프로세스만 사용 

 

 

 2 점유 대기 (Hold and wait)

최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재

철학자 문제에서 왼쪽 젓가락이 있는 상태에서 오른쪽 철학자에게 젓가락을 달라는 것

 

 

3 비선점 (No preemption)

다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음

예) 프린터, 스캐너, critical section 등등

 

 

4 순환 대기 (Circular wait)

프로세스 집합이 순환(원형) 형태로 상대방의 자원을 기다리는 경우

 

점유 대기와 비선점이 만족해야 성립하는 조건으로 조건들이 서로 독립적이지 않다.

 

 

 

데드락(DeadLock) 처리

교착 상태를 예방 & 회피

1. 예방(prevention)

 - 교착 상태 발생 조건 중 하나를 제거하면서 해결한다. (자원 낭비 심함)

 

상호 배제 부정

여러 프로세스가 자원을 공유하도록 한다.

 

=> 현실적으로 불가능 

 

 

점유 대기 부정

 - 프로세스 실행 전, 필요한 모든 자원을 할당한다. 그 전까지는 작업을 보류한다.

자원을 이미 다 갖고 있어서 자원 요청이 필요없다 

 

 - 또는, 자원을 전혀 갖고 있지 않을 때만 자원을 요청하는 방법이 있다. 

갖고 있는 자원이 하나도 없어서 다른 프로세스가 기다릴 필요없다

 

 - 현재 필요하지 않음에도 자원 소유, 필요한 자원을 파악하기 위한 비용 => 자원 효율성이 낮다.

기아 상태가 발생할 수 있다.

 

 

비선점 부정

 - 프로세스의 자원이 사용 끝나기 전에 선점될 수 있게 한다.

 

 - 즉 프로세스가 다른 자원을 요구할 때 즉시 할당 받을 수 없다면, 점유하고 있는 모든 자원을 반납하고 기다린다.

( 내가 갖고 있던 자원을 놓고(비선점) 자원이 사용가능할때까지 기다리는 것 )

 

 -그리고, 반납한 자원과 필요로 한 자원 모두를 사용 가능할 때 프로세스는 재실행된다. 

 

 - 이 방법은 cpu register, memory space같은 자원이 쉽게 선점되고 할당되는 경우에 종종 쓰인다. 하지만, 뮤텍스락이나 세마포어에서는 일반적으로는 사용되지 않는다. 

 

 

 

순환 대기 부정

자원에 고유번호 할당 후 순서대로 자원 요청

 

하지만 노는 자원이 발생가능하다.

 

ex) 프로세스는 순서의 증가 방향으로만 자원 요청 가능

R1, R2, R3, R4

 

P1 (1, 2, 4 모두 필요)

P2 (1, 3 모두 필요)

 

P1이 먼저 R1을 사용하면, P2는 R1을 못 쓰기 때문에 P2가 실행 불가.

따라서, 자원 3는 아무것도 하지 않는다.

 

=> 교착 상태의 해결 방법들은 자원 사용의 효율성이 떨어지고 비용이 많이 드는 문제점이 있다.

 

 

 

2 회피(avoidance)

교착 상태 발생 가능성을 검사하여 피하는 방법

 

대표적인 은행원 알고리즘(Banker's Algorithm) https://jhnyang.tistory.com/102

 - 다익스트라가 만들었다!!

 

 - safe state와 unsafe state로 나누어 safe state일 때만 자원 할당

 

- 은행이 항상 모든 고객에게 현금을 대출해주는데 서 유래됨 

 

- 은행(os)은 최소한 고객(프로세스) 한 명에게 대출할 정도의 돈(자원)이 있어야 한다.

 

 - 그렇지 않으면 은행은 불안정 상태 (  데드락이 발생 가능한 상태 )

 

- 프로세스가 자원을 요구할 때, 자원 할당 후에 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피

 

- 안정 상태면 자원 할당, 아니면 다른 프로세스가 자원 해지까지 대기

 

 

 

 

데드락 탐지 & 회복

시스템에서 데드락 예방 및 회피가 적용되지 않았을때, 데드락 탐지 및 회복 알고리즘이 제공된다. 

 

하지만, 런타임 중 탐지와 회복 알고리즘으로 추가적인 오버헤드가 발생한다. 

 

1 탐지(Detection)

자원 할당 그래프(Resource-allocation graph) 를 통해 교착 상태를 탐지함

(자원 할당 그래프 https://developerhenrycho.tistory.com/20)

 

하지만 어느 시점에서 교착상태를 탐지해야 할지를 알 수 없으므로 주기적( 또는 요청 시)으로 알고리즘을 실행해야 되는데, 이에 드는 코스트가 커서 실용적이지는 못하다.

 

 

2 회복(Recovery)

교착 상태 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법

 

- 프로세스 종료

데드락 프로세스를 모두 중지

=> 재실행 비용이 크다

 

데드락이 제거될 때까지 프로세스를 하나씩 중지

=> 데드락 탐지 알고리즘 오버헤드가 크고, 중지할 프로세스 선택 문제가 복잡하다.

 

 

- 자원 선점

교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당 (해당 프로세스 일시정지 시킴)

 

우선 순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점

 

 

 

 

기아(starvation) 란?

교착 상태가 아니어도 특정 프로세스의 우선순위가 낮아서 원하는 자원을 계속 할당 받지 못하는 상태를 말한다.

 

 

데드락과 기아의 차이

결국은 둘다 자원을 할당 받지 못하는 상태다. 그런데 발생하는 원인이 다르다.

 

데드락은 여러 프로세스가 동일 자원 점유를 요청할 때 발생

 

기아는 여러 프로세스가 부족한 자원을 점유하기 위해 경쟁할 때 발생

 

 

 

주요 질문

데드락(교착 상태)가 뭔가요? 발생 조건에 대해 말해보세요.

 

회피 기법인 은행원 알고리즘이 뭔지 설명해보세요.

 

기아 상태를 설명하는 식사하는 철학자 문제에 대해 설명해보세요.

  

교착 상태 해결책

 

n명이 앉을 수 있는 테이블에서 철학자를 n-1명만 앉힘

한 철학자가 젓가락 두개를 모두 집을 수 있는 상황에서만 젓가락 집도록 허용

누군가는 왼쪽 젓가락을 먼저 집지 않고 오른쪽 젓가락을 먼저 집도록 허용 ( 대칭성 제거 )