Deadlock
- 어떤 프로세스 집단 내의 각 프로세스가 그 집단 내의 또 다른 프로세스에 의해서만 발생할 수 있는 이벤트를 기다리고 있으면, 그 프로세스 집단은 deadlock상태에 있다.
이 그림처럼 차량이 또다른 차량의 앞을 막고, 또 그 차량이 또 다른 차량의 앞을 막아 아무도 빠져나갈 수 없는 상태가 되었을 때 Deadlock상태라고 할 수 있다. 프로세스가 후진을 할 일은 없기 때문에 deadlock이 발생하면 손해없이 복구할 수 없다, deadlock에 관련된 프로세스중 누군가는 rollback또는 사라져야 한다.
위의 사진에서도 차량중 한 개의 차량만 사라져도 Deadlock은 풀리게 된다.
Deadlock 발생 4가지 필요조건
1. 상호 배제(mutual exclution)
- 각 자원은 프로세스 1개 까지만 할당될 수 있음
2. 보유 및 대기(hold and wait)
- 프로세스들은 자원을 보유한 상태에서 추가적인 자원을 요청하며 기다림.
3. 비선점(no preemption)
- 어떤 프로세스에게 이전에 허가된 자원을 강제로 뺏어올 수 없음.
4. 환형 대기(circular wait)
- 두 개 이상의 프로세스들이 환형 사슬을 이룸
- 각 프로세스느 ㄴ사슬의 다음 프로세스에 의해 점유된 자원을 기다림
이 4가지중 1개라도 해당되지 않으면 Deadlock은 발생하지 않음.
모델링
사각형: 자원
동그라미: 프로세스
(a)자원R은 A에게 할당된 상태. (b)B는 자원 S를 요청중인 상태
(c)프로세스 C는 T라는 자원을 요청하는데, T는 D에게 할당되어 있고 U를 요청중이지만 U는 C에게 할당되어 있어서 어느 누구도 자원을 원하는 자원을 점유할 수 없는 상태이다. Deadlock상태이다.
Deadlock 처리 방법
1. 무시: 데드락을 무시하겠다.
2. 탐지 및 회복(dedtction and recovery)
3. 동적 회피(dynamic avoidance): 자원을 할당할 때 주의깊게 할당해서 데드락을 회피하겠다.
4. 예방(prevention): 4가지 필요 조건 중 하나 이상을 제거하겠다.
1. 무시
The Ostrich Algorithm(Ostrich: 타조, 타조는 적을 만나면 머리를 모래속에 파묻고 무시함.)
아무 문제가 없는척한다.
deadlock이 매우 드물게 발생한다면 예방 비용이 크다면 무시한다.
UNIX, WIndows가 이 방법을 사용중이다.
2. Prevention(예방)
상호 배제(Mutual Exclution) 제거
프린터와 같은 자원은 어떤 공유도 불가능하다. a가 프린터를 사용하는 동안 b는 프린터를 사용하지 못하게 해야한다.
이런 조건으로 인해 Mutual Exclution은 무조건 보장되어야 한다.
보유 및 대기(Hold and Wait) 제거
자원을 할당받을 때 필요한 모든 자원을 사전에 확보하고, 반만 확보하고 대기하지 않는다. <- All or nothing
예를 들어 프로세스가 작업을 처리하는데 프린터와 스풀러 두개가 필요하다면 프로세스 실행 시 프린터와 스풀러 모두 점유하고 시작한다.
프린터만 사용하다가 스풀러가 필요할 때 그제서야 요청하지 않는다.
문제점: 프로그램이 앞으로 어떤 자원이 필요할지 미래를 다 알아야한다.
abc가 필요하면 프로세스 초반부에 abc를 모두 다 확보해야하며, ab사용이 끝났다고해서 c가 끝나기전에 점유를 놓아주지 않는다.
이미 사용이 끝난 자원도 확보하고 있어야 하므로 다른 프로세스가 효율적으로 자원을 사용하지 못한다는 문제가 있다.
비선점(No Preemption) 제거
다른 프로그램이 사용중인 자원을 뺏을 수 있게 한다는 말
아예 불가능한 방법이다.
프로세스가 자원을 계속 뺏고 뺏으면서 무한 대기가 일어날 수 있다.
환형 대기(Circular Wait)제거
모든 자원에 번호를 매겨놓고 번호가 증가한 조건에만 자원을 주는 기법
이런 식으로 자원에 번호를 매겨서 사용하는 방법
만약 2, 4, 5자원이 필요할 경우 2번을 확보한 경우에만 4번을 요청할 수 있다는 조건이다.
2번을 확보를 하지 못했으면 4번을 요청도 하지 못한다.
그런데 만약 4번을 사용했는데 2번이 필요하다면 >> 1번을 요청해서 확보를 한 후 2번을 요청해야한다.
항상 번호가 올라가는 경우에만 요청할 수 있다는 단점이 있다.
각 각의 데드락 발생조건을 제거한 경우에도 문제점은 존재한다
3. Dynamic Avoidance(동적 회피)
p: 프로세스 A가 프린터를 요청, 점유
q: 프로세스 B가 플로터를 요청, 점유
r: 프로세스 A가 프린터를 요청, 점유
s: 프로세스 B가 플로터를 요청, 점유
------문제 없음--------
t: 이미 플로터를 B가 점유하고 있는데 A가 요청, 이미 프린터를 A가 점유하고 있는데 B가 요청 <---데드락 발생
이 자원 요청을 받아주게되면 색칠되어 있는 데드락 발생 구간으로 들어가게됨.
저 지점을 회피해서 가도록 운영체제가 자원들을 스케쥴링함
운영체제가 자원 할당을 신중하게 해서 데드락을 회피함.
회피하는 방법?
Safe 상태
- 모든 프로세스가 자신이 필요로 하는 최대 수의 자원을 즉시 요청할지라도 이들이 모두 완료될 수 있는 스케줄링 순서가 있다면 Safe 상태이다.
Has: 현재 보유중인 자원의 개수
Max: 작업 완료에 필요한 최대 개수
Free: 할당되지 않은 자원
프로세스 a가 최대 4개까지 사용하게 된다는 말은 3개를 더 요청하게 된다는 말이다.
현재 남아있는 자원이 2개다. 남는 자원 2개를 B에게 할당하면 6개가 되므로 B의 작업이 마무리되고 남는자원이 6개가 된다.
6개중 3개를C, 남은 3개중 3개를 A에 할당하면 C, A모두 작업이 완료가 가능하다.
A, B, C가 모두 작업을 완료할 수 있는 순서가 존재하면 안전한 상태(Safe 상태)이다.
Unsafe 상태
현재 상태로서 1개의 남는 자원을 누구에 할당해도 아무도 작업을 마치지 못한다
Unsafe 상태이다.
하지만 데드락은 아니다.
은행가 알고리즘(Bankers Algorithm(Djikstra's))
은행가 알고리즘은 각 프로세스가 자원을 요청할 때 세이프 상태로 가게되면 요청을 받아주고 unsafe상태로 가게되면 받아주지 않는다.
현재는 작업 완료가 가능한 상태이다.
어느 누구에게나 먼저 할당해도 작업을 마칠 수 있는 상태이다.
하지만 자원 할당을 잘못하여 남는 자원이 1개가 되었다면 그 누구에게 할당하여도 작업을 완료할 수 없다.
은행가 알고리즘의 단점:
- 프로세스들이 자신의 최대 자원 요구량이 얼마나 될지 알기 어렵다.
- 프로세스의 수는 고정된 것이 아니라, (새로운 사용자가 로그인/로그아웃 함에 따라)변화한다.
4. Detection and Recovery(탐지 및 회복)
탐지:
1. 자원 소유권 및 요청을 그래프로 표현하고 유지한다.
그래프에서 사이클은 deadlock이 있음을 나타낸다.
2. 자원과 프로세스의 자원 점유, 요청에 대한 행렬을 만들고 유지한다.
행렬을 통해 작업의 완료가 가능한지 확인하고 데드락을 탐지한다.
회복:
Preemption을 통한 회복
- 다른 프로세스로 부터 자원을 뺏어온다.
- 중간에 뺏겨도 가능한 자원인지 여부에 달려있다.
- 대게 자원은 뺏기면 안되기 때문에 괜찮은 방법이 아니다.
롤백(Rollback)을 통한 회복
- 주기적으로 프로세스의 체크포인트를 만든다
- 체크 포인트 시점에 상태를 저장해야 한다는 부담이 있다.
- Deadlock이 발견되면 프로세스를 재시작(체크포인트 부터)
프로세스 제거(Killing process)를 통한 회복
- Deadlock을 해소하는 가장 간단한 방법이다.
- 사이클에 있는 프로세스 중 1개를 제거한다.
- 다른 프로세스 들은 kill된 프로세스의 자원을 획득하게된다
- 제거되어야 할 프로세스를 선택해야한다. 이 프로세스는 처음부터 다시 실행된다.