The Deadlock Problem
다중 프로그래밍 환경에서는 여러 스레드가 한정된 자원을 사용하려고 서로 경쟁할 수 있다.
한 스레드가 자원을 요청했을 때, 그 자원을 사용할 수 없는 상황이 발생할 수 있고, 그때는 스레드가 대기 상태로 들어간다. 이처럼 대기 중인 스레드들이 결코 다시는 그 상태를 변경시킬 수 없으면 이런 상황을 교착 상태(deadlock)라 부른다.
System Model
시스템은 경쟁하는 스레드들 사이에 분배되어야 할 유한한 수의 자원들로 구성된다.
이들 자원은 다수의 유형으로 분할되며, 이들 각각은 동등한 다수의 인스턴스(instance)들로 구성된다.
만약 한 스레드가 어떤 자원 유형의 한 인스턴스를 요청하면, 동일 유형 자원의 임의의 인스턴스를 할당함으로써 요청이 충족된다.
정상적인 작동 모드라면, 프로세스는 다음 순서로만 자원을 사용할 수 있다.
- 요청 : 스레드는 자원을 요청한다. 만약 허용되지 않으면 요청 스레드는 자원을 얻을 때까지 대기해야 한다.
- 사용 : 스레드는 자원에 대해 작업을 수행할 수 있다.
- 방출 : 스레드가 자원을 방출한다.
자원의 요청과 방출은 시스템 콜이다. 일례로 파일 open(), close() 등이 있다.
한 스레드 집합 내의 모든 스레드가 그 집합 내의 다른 스레드에 의해서만 발생될 수 있는 이벤트를 기다린다면, 그 스레드 집합은 교착 상태에 있다.
Deadlock Characterization
Necessary Contitions
-
mutual exclusion
최소한 하나의 자원이 비공유 모드로 점유되어야 한다. 비공유 모드에서는 한 번에 한 스레드만이 그 자원을 사용할 수 있다. 다른 스레드가 그 자원을 요청하면, 요청 스레드는 자원이 방출될 때까지 반드시 지연되어야 한다. -
hold&wait
스레드는 최소한 하나의 자원을 점유한 채, 현재 다른 스레드에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기해야 한다. -
no preemption
자원들을 선점할 수 없어야 한다. 즉, 자원이 강제적으로 방출될 수 없고, 점유하고 있는 스레드가 태스크를 종료한 후 그 스레드에 의해 자발적으로만 방출될 수 있다. -
circular wait
대기하고 있는 스레드의 집합 {T0, ..., Tn} 에서 T0는 T1이 점유한 자원을 대기하고, T1은 T2가 점유한 자원을 대기하고....Tn은 T0가 점유한 자원을 대기한다.
Resource Allocation Graph
그래프는 정점 V의 집합과 간선 E의 집합으로 구성된다. 정점 V의 집합은 시스템 내의 모든 활성 스레드 집합인 T와 모든 자원 유형의 집합인 R의 두 가지 유형으로 구별된다.
스레드 T(i)로부터 자원 유형 R(j)로의 방향 간선은 요청 간선(request edge)라고 부르고,
방향 간선 R(j) -> T(i)는 반대로 할당 간선(assignment edge)라고 한다.
그래프가 사이클(cycle)을 포함하지 않으면 시스템 내 어느 스레드도 교착 상태가 아니라는 것을 보일 수 있다. 하지만 사이클은 존재한다고 반드시 교착 상태가 발생한 것은 아니다.
이 그림 또한 사이클을 갖지만, 프로세스 T4가 자원 유형 R2의 인스턴스를 방출한다면, T3에 자원이 할당될 수 있고, 사이클이 없어진다.
따라서 사이클은 교착 상태의 필요충분조건은 아니다.
Methods for Handing Deadlocks
교착상태를 예방하거나 회피하는 프로토콜을 사용한다.
교착 상태 예방은 앞서 언급한 4가지 조건 중 적어도 하나가 성립하지 않도록 하는 방법이다.
교착 상태 회피는 스레드가 평생 요구하고 사용할 자원에 대한 부가적인 정보를 미리 제공받고, 운영체제는 각 요청을 위해 그 스레드가 기다려야 할지 않을지를 결정할 수 있다.
시스템이 교착상태가 가능하도록 허용한 다음에 회복시키는 방법
교착상태가 발생했는지를 조사하는 알고리즘과 교착상태 복구 알고리즘을 사용할 수 있다.
문제를 무시하고, 교착상태가 시스템에서 발생하지 않는 척한다.
오히려 발생한 교착상태를 해결하는 데 더 많은 비용이 들 수 있으므로 무시한다.
이 경우 교착상태가 누적되면 시스템 성능을 저하시킬 수 있기 때문에 수작업으로 다시 시작할 필요가 있다.
Deadlock Prevention
교착 상태가 발생하려면 4가지 필요조건 중 최소한 하나가 성립하지 않도록 보장함으로써, 우리는 교착 상태 발생을 예방할 수 있다.
상호 배제
상호 배제 조건을 성립하기 위해선 적어도 하나의 자원은 공유가 불가능한 자원이어야 한다.
일반적으로 상호 배제 조건을 거부하기 때문에 교착 상태를 예방할 수는 없다.
점유하며 대기
시스템에서 점유하며 대기 조건이 발생하지 않도록 하려면 스레드가 자원을 요청할 때마다 다른 자원을 보유하지 않도록 보장해야 한다.
대안 프로토콜은 스레드가 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있도록 허용하는 것인데, 이는 자원 이용률 감소와 기아 발생 우려가 있다.
비선점
이미 할당된 자원이 선점되지 않아야 한다는 것이다.
이 조건이 성립되지 않게 하기 위해, 어떤 자원을 점유하고 있는 프로세스가 즉시 할당할 수 없는 다른 자원을 요청하면, 현재 점유하고 있는 모든 자원들이 선점되게 할 수 있다.
하지만 프린터 같은 경우에는 불가능하다.
순환 대기
이 조건이 성립되지 않게 하기 위해, 모든 자원 타입에 대해 전체적인 순서를 부여하여, 각 프로세스가 열거된 순서대로 자원을 요청하도록 요구할 수 있다.
Deadlock Avoideance
만약 우리가 각 스레드의 요청과 방출에 대한 완전한 순서를 파악하고 있다면, 우리는 각 요청에 대해서 가능한 미래의 교착 상태를 피하고자 스레드가 대기해야 하는지 여부를 결정할 수 있다.
각 스레드가 자신이 필요로 하는 각 유형의 자원마다 최대 수를 선언하도록 요구하는 것이다.
자원의 최대 수 정보를 미리 파악할 수 있다면, 우리는 시스템이 교착 상태에 들어가지 않을 것을 보장하는 알고리즘을 만들 수 있다.
안전 상태 (Safe state)
시스템 상태가 안전하다는 말은 시스템이 어떤 순서로든 스레드들이 요청하는 모든 자원을 교착 상태를 발생시키지 않고 차례로 모두 할당해 줄 수 있다는 것을 뜻한다. 즉, 시스템이 안전 순서(safe sequence)를 찾을 수 있다면 시스템은 안전하다고 말한다.
또한 안전하다는 것은 교착 상태가 발생하지 않는다는 것을 의미한다.
하지만 불안전하다고 반드시 교착상태로 간다는 것을 의미하진 않는다.
Resource-Allocation Graph(RAG)
자원 할당 그래프를 그려보면서 사이클이 안 생기게 하여 교착 상태를 회피할 수 있다.
자원 할당 그래프에 예약 간선(claim edge)이라는 새로운 타입의 점선으로 된 간선을 도입한다.
이 간선의 원리는 이렇다.
- 자원 요청 시 : 예약 간선은 요청 간선으로 변환된다.
- 방출 요청 시 : 요청 간선은 예약 간선으로 변환된다.
따라서 우리는 스레드 T(i)가 실행되기 전에, 스레드의 모든 예약 간선이 자원 할당 그래프에 표시해야 한다.
스레드 T(i)와 연관된 모든 간선들이 예약 간선일 때만 예약 간선 T(i) -> R(j)를 그래프에 추가하도록 허용하면 된다.
또한 이때 요청 간선 T(i) -> R(j)가 할당 간선으로 변환해도 자원 할당 그래프에 사이클을 형성하지 않을 때만 요청을 허용할 수 있다.
이 그래프에서 사이클을 탐지하는 알고리즘은 n^2 차수의 연산이 필요한데, n은 스레드의 수를 의미한다.
Banker's Algorithm
종류마다 자원이 여러 개인 경우 은행원 알고리즘을 사용하게 된다.
이 시스템에서는 스레드가 시작할 때 스레드가 가지고 있어야 할 자원의 최대 개수를 자원 종류마다 미리 신고하여야 한다.
스레드가 자원을 요청하면 시스템은 그것을 들어주었을 때 시스템이 계속 안전 상태에 머무르게 되는지 여부를 판단해야 한다.
은행원 알고리즘을 구현하려면 몇 가지 자료구조가 필요하다. (n이 스레드 수, m이 자원 종류 수)
- Available : 각 종류별로 가용한 자원의 개수를 나타내는 크기 m짜리 벡터
- Max : 각 스레드가 최대로 필요로 하는 자원의 개수를 나타내는 행렬(n x m). Max[i][j] = k 라면 스레드 T(i)가 R(j)를 최대 k개까지 요청할 수 있음을 말한다.
- Allocation : 각 스레드에 현재 할당된 자원의 개수를 나타내는 행렬(n x m)
- Need : 각 스레드가 향후 요청할 수 있는 자원의 개수를 나타내는 행렬(n x m)
Need[i][j] = Max[i][j] - Allocation[i][j]의 관계가 있다.
안전성 확인
- Work와 Finish는 크기가 m과 n인 벡터이다. Work = Available로 초기 값을 주고, Finish[i] = false를 초기 값으로 준다.
- Finish[i] == false && Need(i) <= Work를 만족시키는 i값을 찾는다. 그런 값을 찾지 못하면 4단계로 간다.
- Work += Allocation(i), Finish[i] = true. 2단계로 간다.
- 모든 i값에 대해 Finish[i] == true이면 이 시스템은 안전 상태에 있다.
자원 요청
- 만약 Request(i) <= Need(i)이면 2단계로 간다. 아니면 시스템에 있는 개수보다 더 많이 요청했으므로 오류
- 만약 Request(i) <= Available이면 3단계로 간다. 아니면 요청한 자원이 당장은 없으므로 P(i)는 기다려야 한다.
- 시스템 상태 정보를 바꾼다. -> Available -= Request(i), Allocation(i) += Request(i), Need(i) -= Request(i)
Deadlock Detection
각 자원 유형이 한 개씩 있는 경우(single instance)
모든 자원들이 한 개의 인스턴스만 있다면, 대기 그래프(wait-for graph)를 이용하여 교착 상태 탐지 알고리즘을 정의할 수 있다.
대기 그래프는 자원 할당 그래프로부터 자원 유형의 노드를 제거하고, 적절한 간선을 결합함으로써 대기 그래프를 얻을 수 있다.
대기 그래프가 사이클을 포함하는 경우에만 시스템에 교착 상태가 존재한다.
교착 상태를 탐지하기 위해 시스템은 대기 그래프를 유지할 필요가 있고, 주기적으로 그래프에서 사이클을 탐지하는 알고리즘을 호출한다.
각 유형의 자원을 여러 개 가진 경우(multiple instance)
대기 그래프는 종류마다 자원이 여러 개씩 존재하는 상황에서는 사용할 수 없다.
따라서, 은행원 알고리즘과 마찬가지로 시시각각 그 내용이 달라지는 자료구조를 사용한다.
Recovery from Deadlock
탐지 알고리즘이 교착 상태가 존재한다고 결정하면, 두 가지 처리 방법이 있다.
- 프로세스 kill
- Rollback(check point)
