데드락
데드락(DeadLock)이란?
두 개 이상의 프로세스나 스레드가 서로가 가진 자원을 기다리면서 무한히 wait 상태에 빠지는 것을 뜻한다.
간단하게 예시를 들어보자. 프로세스 1은 자원 A가 할당되어 있고 프로세스 2는 자원 B가 할당되어 있다.
이 때 1은 작업에 자원 B를 기다리고 2는 자원 A를 기다린다면 서로가 필요로 하는 자원을 영원히 얻을 수 없어 무한히 wait 상태에 빠지게 된다.
데드락을 발생시키는 자원은 한정된 시스템 자원이라면 뭐든지 될 수 있다. 한번에 하나의 스레드만 접근 가능한 임계구역일 수도 있고, 마이크 스피커 등의 하드웨어 자원일 수도 있다.
이러한 데드락의 발생 조건에는 4가지가 있다.
데드락(DeadLock)의 발생 조건
4가지가 있으며 이 중 하나라도 만족하지 못한다면 데드락 상태는 발생하지 않는다.
1) 상호 배제(Mutual Exclusion) : 저번 포스팅에서 배웠던 Mutex이다. 임계 구역으로의 동시접근은 해결했지만 데드락이라는 문제가 생겼다.
2) 점유 대기(Hold and Wait) : 자원을 최소한 하나를 보유하고, 이후 다른 프로세스가 점유 중인 자원을 얻기 위해 기다리는 프로세스가 필요하다. 즉 자원을 동시에 2개 이상 요구하는 프로세스여야 한다.
3) 비-선점(non-preemptive) : CPU 스케줄링에서 배웠던 비-선점형 스케줄링이다. 다른 프로세스가 이미 점유 중인 자원을 강제로 뺏어올 수는 없는 스케줄링이다.
4) 순환 대기(circular wait) : 프로세스 간의 대기 관계가 서로 이어져 서클 형태를 그려야 한다. 위의 예시와 같다.
이러한 데드락 상태를 해결하기 위한 몇 가지 기법이 존재한다.
데드락의 예방(Prevention)
데드락 상태가 일어나지 않도록 데드락의 발생 조건 4가지 중 하나를 원천 봉쇄하는 것이다. 따라서 4가지 방법이 있다.
1) 상호 배제의 방지 : 여러 개의 프로세스가 하나의 자원을 점유할 수 있도록 한다. 동기화 포스팅에서 배웠듯이 임계 구역에 대한 부적절한 접근이 일어날 수 있다.
2) 점유 대기의 방지 : 프로세스가 필요한 모든 자원을 한꺼번에 요구하고 그것이 가능할 때까지 무기한 wait한다. 딱 봐도 매우 비효율적으로 보인다.
3) 비-선점의 방지 : 더 높은 우선순위의 프로세스가 다른 프로세스의 자원을 요구하면 해당 자원을 가질 수 있도록 한다. CPU 스케줄링의 선점형 스케줄링이다.
4) 순환 대기의 방지 : 자원에 우선 순위를 두고 우선 순위가 높은 자원을 얻기 위해서는 우선 순위가 낮은 자원을 모두 할당 해제하도록 한다. 계속해서 자원의 할당과 해제를 반복해야 하기에 처리가 매우 복잡해진다.
데드락의 예방은 극단적인 방법이 많아 시스템의 처리율과 효율성을 저해할 수 있다. 원인을 원천 봉쇄하는 것이 아닌 좀 덜 극단적인 데드락의 회피가 존재한다.
데드락의 회피(Avoidance)
데드락의 원인을 봉쇄하는 것이 아닌 데드락의 발생만을 회피 하는 것이다. 이를 위해 알아야 할 개념이 3개가 있는데 Safe state, Safe sequence, Unsafe state이다.
- 안정 상태(Safe state) : 자원을 할당하는 경우의 수 중에 데드락이 발생하지 않는 경우의 수가 하나라도 존재하는 상태
- 안전 순서(Safe sequence) : 데드락이 발생하지 않는 프로세스의 실행 순서
- 불안정 상태(Unsafe state) : 안전 순서가 없어 데드락이 발생할 가능성이 있는 상태
데드락의 회피는 안정 상태를 유지하는 것이 핵심이다. 안정 상태라면 안전 순서가 존재하기에 데드락이 발생하지 않는다. 그러므로 프로세스의 처리 순서를 계속 시뮬레이션 하여 불안정 상태로 가는 요구는 모두 거절하고 계속해서 안정 상태를 유지할 수 있는 요청만 수락하여 데드락의 발생을 회피한다. 안정 상태를 유지하는 알고리즘 중 대표적인 것으로 은행원 알고리즘(Banker’s algorithm)이 있다.
은행원 알고리즘(Banker’s algorithm)
은행원 알고리즘을 설명하기 전에 선행해서 알아둬야 할 알고리즘이 있다. 현재 상황에서 안전 순서가 있는지를 검사하는, 즉 현재 상태가 안정 상태인지를 알아보는 안정성 알고리즘(Safety algorithm)이다.
예를 들어 시스템이 현재 13개의 자원을 가지고 있다고 가정하자. 여기 프로세스 3개와 각 프로세스의 최대 할당량, 현재 할당량, 필요 할당량이 있다.
| max | allocation | need | available | |
|---|---|---|---|---|
| p0 | 10 | 5 | 5 | |
| p1 | 4 | 2 | 2 | |
| p2 | 9 | 2 | 7 |
need 값은 max-allocation이다. 현재 할당 완료된 자원의 양은 총 9이고, 따라서 available은 4개이다. 여기서 안전 순서가 있는지를 찾아보자. 안정성 알고리즘은 다음과 같은 순서로 작동한다.
1) need<=available인 프로세스를 찾는다. = 가용 자원으로 완료시킬 수 있는 프로세스를 찾는다.
2) 찾은 프로세스를 완료시키고 프로세스에 할당되어 있던 자원들을 available로 돌린다. 3) 1,2를 반복하고 모든 작업이 완료된다면 안정 상태, 남은 작업이 있다면 불안정 상태이다.
위와 같은 작업을 현재의 표에 적용해보면 p1->p0->p2 순서일 때 모든 작업이 완료되는 것을 알 수 있다.
1) p1의 need인 2가 available인 4보다 작으므로 할당하여 작업을 완료시킨다. 작업을 완료하고 할당되어있던 자원을 반납하므로 현재 available은 6
2) p0의 need인 5가 현재 available인 6보다 작으므로 할당하여 작업을 완료시킨다. 작업을 완료하고 자원을 반납하면 현재의 available은 11
3) p2의 need인 7이 현재의 available인 11보다 작으므로 할당하여 작업을 완료시키면 모든 작업이 완료된다.
즉 위의 상태는 안전 순서가 있으므로 안정 상태임을 알 수 있다. 이제 안정성 알고리즘을 배웠으니 진짜 은행원 알고리즘을 배워보자.
은행원 알고리즘의 핵심은 간단하다. 요청을 수락했을 때 안정 상태가 유지된다면 수락, 불안정 상태가 된다면 거절하는 것이다. 작동 순서는 다음과 같다.
1) 프로세스 p가 자원을 req_p 만큼 요청했다. 일단 req_p<=need_p인지 먼저 검사한다. 만족한다면 2번으로, 만족하지 않는다면 필요 자원보다 더 많은 양을 요청한 것이므로 예외를 호출한다.
2) req_p<=available 인지를 검사한다. 만족한다면 현재 가용 가능한 자원으로 요청을 수락할 수 있으므로 3번으로 이동, 만족하지 않는다면 현재 불가능한 요청이므로 프로세스를 wait시킨다.
3) 요청을 수락했다고 가정하고 값을 갱신시킨다. available-=req_p, allocation_p+=req_p, need_p-=req_p 와 같이 값을 갱신한다.
4) 현재의 상황으로 안정성 알고리즘을 가동한다. 만약 현재의 상태가 안정 상태로 밝혀지면 그대로 프로세스에 자원을 할당한다. 만약 불안정 상태라면 3번에서 수정했던 값을 롤백하고 프로세스를 wait 시킨다.
은행원 알고리즘을 사용하면 분명 데드락을 회피할 수 있지만 프로세스들의 최대 자원 요구량을 미리 알아둬야 하고(프로세스가 항상 일정량의 자원을 요구하지는 않는다)
available을 계속해서 정확하게 갱신해야 하는 등의 제약조건에 따른 성능의 저하가 발생할 수 있어 현대 OS에서는 사용되지 않는다.
만약 데드락을 예방, 회피하는데 오버헤드가 너무 크다고 판단될 때에는 데드락의 탐지와 회복 기법을 사용할 수 있다.
데드락의 탐지(Detection)와 회복(Recovery)
데드락의 탐지는 간단하게는 자원 할당 그래프를, 자원이 여러 개라면 안정성 알고리즘을 사용하여 탐지할 수 있다.
데드락의 회복 방법으로는 데드락에 빠진 프로세스들을 모두 중단시키기, 데드락에 빠진 프로세스를 하나씩 중단시키면서 데드락이 해결되었는지 탐지하기, 데드락에 빠진 프로세스의 자원을 선점하여 다른 프로세스에 할당해주는 방법 등이 있다.
지금까지 데드락 문제에 대해 배워보았다. 다음 포스팅에서는 가상 메모리와 페이징에 대해 배워보도록 하겠다.