공룡책과 함께 OS를 배워보자 7일차 - Deadlocks

본 포스트는 공룡책이라 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』 을 바탕으로 작성하였습니다.

 

 

Ch 8.  교착 상태 (Deadlocks)

---

다중 프로그래밍 환경에서는 여러 스레드가 한정된 자원을 사용하려고 서로 경쟁할 수 있다.

한 스레드가 자원을 요청했을 때, 그 자원을 사용할 수 없는 상황이 발생할 수 있고, 그때는 스레드가 대기 상태로 들어간다. 이처럼 대기 중인 스레드들이 결코 다시는 그 상태를 변경시킬 수 없으면 이런 상황을 교착 상태라 부른다.

 

교착 상태의 유명한 사례는 이러하다.

두 기차가 교차로에서 서로 접근할 때는, 둘 다 완전히 정지해야 하며 상대방이 없어지지 않는 한 누구도 다시 출발할 수 없다. (20세기 초 캔자스 주 의회가 통과한 법률)

 

 

보통 운영체제들은 교착 상태 예방 기능을 제공하지 않는다.

따라서 교착 상태가 없는 프로그램을 설계하는 것은 전적으로 프로그래머의 책임으로 남는다.

 

 

 

8.1 시스템 모델

---

시스템은 경쟁하는 스레드들 사이에 분배되어야 할 유한한 수의 자원들로 구성된다.

이들 자원은 다수의 유형으로 분할되며, 이들 각각은 동등한 다수의 인스턴스(instance)들로 구성된다.

 

만약 한 스레드가 어떤 자원 유형의 한 인스턴스를 요청하면, 동일 유형 자원의 임의의 인스턴스를 할당함으로써 요청이 충족된다.

 

정상적인 작동 모드라면, 프로세스는 다음 순서로만 자원을 사용할 수 있다.

1. 요청 : 스레드는 자원을 요청한다. 만약 허용되지 않으면 요청 스레드는 자원을 얻을 때까지 대기해야 한다.
2. 사용 : 스레드는 자원에 대해 작업을 수행할 수 있다.
3. 방출 : 스레드가 자원을 방출한다.

 

자원의 요청과 방출은 시스템 콜이다. 일례로 파일 open(), close() 등이 있다.

 

한 스레드 집합 내의 모든 스레드가 그 집합 내의 다른 스레드에 의해서만 발생될 수 있는 이벤트를 기다린다면, 그 스레드 집합은 교착 상태에 있다.

 

 

* 라이브락 (Livelock)

라이브락은 라이브니스 장애로, 교착 상태와 유사하다.

라이브락은 스레드가 실패한 행동을 계속해서 시도할 때 발생하며, 예를 들어 두 사람이 복도를 지나갈 때 한 사람은 오른쪽으로 움직이고 다른 한 사람은 왼쪽으로 움직이면서 서로 길막당할 때, 서로 반대로 이동하는 조치를 취하면 여전히 앞으로 나아갈 수 없다.

 

 

 

8.2 교착 상태의 특징

---

이번에는 교착 상태를 특징짓는 조건에 대해 자세히 알아보자.

 

* 필요조건들 (Necessary Contitions)

교착 상태는 한 시스템에 다음 4가지 조건이 동시에 성립될 때 발생할 수 있다.

 

1. 상호 배제(mutual exclusion) : 최소한 하나의 자원이 비공유 모드로 점유되어야 한다. 비공유 모드에서는 한 번에 한 스레드만이 그 자원을 사용할 수 있다. 다른 스레드가 그 자원을 요청하면, 요청 스레드는 자원이 방출될 때까지 반드시 지연되어야 한다.
2. 점유하며 대기(hold-and-wait) : 스레드는 최소한 하나의 자원을 점유한 채, 현재 다른 스레드에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기해야 한다.
3. 비선점(no preemption) : 자원들을 선점할 수 없어야 한다. 즉, 자원이 강제적으로 방출될 수 없고, 점유하고 있는 스레드가 태스크를 종료한 후 그 스레드에 의해 자발적으로만 방출될 수 있다.
4. 순환 대기(circular wait) : 대기하고 있는 스레드의 집합 {T0, ..., Tn} 에서 T0는 T1이 점유한 자원을 대기하고, T1은 T2가 점유한 자원을 대기하고....Tn은 T0가 점유한 자원을 대기한다.

 

* 자원 할당 그래프

시스템 자원 할당 그래프라는 방향 그래프는 교착 상태를 더욱 정확히 설명해준다.

그래프는 정점 V의 집합과 간선 E의 집합으로 구성된다. 정점 V의 집합은 시스템 내의 모든 활성 스레드 집합인 T와 모든 자원 유형의 집합인 R의 두 가지 유형으로 구별된다.

 

스레드 T(i)로부터 자원 유형 R(j)로의 방향 간선은 요청 간선(request edge)라고 부르고,

방향 간선 R(j) -> T(i)는 반대로 할당 간선(assignment edge)라고 한다.

 

자원 할당 그래프

 

위 그림의 자원 할당 그래프는 다음 상황을 묘사한다.

 

• 자원 유형 R의 인스턴스 수는 순서대로 1, 2, 1, 3개를 갖고 있다.
• 스레드 T1은 자원 유형 R2의 인스턴스 한 개를 점유하고, 자원 유형 R1의 인스턴스 한 개를 기다리며 대기
• 스레드 T2는 R1과 R2의 인스턴스를 각각 한 개씩 점유하고, 자원 유형 R3의 인스턴스 한 개를 기다린다.
• 스레드 T3는 R3의 인스턴스 한 개를 점유하고 있다.

 

 

자원 할당 그래프의 정의상, 만약 그래프가 사이클(cycle)을 포함하지 않으면 시스템 내 어느 스레드도 교착 상태가 아니라는 것을 보일 수 있다. 하지만 사이클은 존재한다고 반드시 교착 상태가 발생한 것은 아니다.

 

* 사이클이 있고, 교착 상태인 그래프

 

스레드 T2는 T3이 점유하고 있는 자원 R3을 기다리고, 스레드 T3은 스레드 T1 또는 T2가 자원 R2를 방출하기를 기다린다.

또한 T1은 T2가 자원 R1을 방출하기를 기다린다. 이 경우 모든 스레드가 교착 상태에 있다.

 

* 사이클이 있고, 교착 상태가 아닌 그래프

 

이 그림 또한 사이클을 갖지만, 프로세스 T4가 자원 유형 R2의 인스턴스를 방출한다면, T3에 자원이 할당될 수 있고, 사이클이 없어진다.

따라서 사이클은 교착 상태의 필요충분조건은 아니다.

 

 

8.4 교착 상태 처리 방법

---

원칙적으로 교착 상태 문제를 처리하는 데는 다음과 같은 세 가지 다른 방법이 있다.

 

1) 교착상태를 예방하거나 회피하는 프로토콜을 사용한다.

 

교착 상태 예방은 앞서 언급한 4가지 조건 중 적어도 하나가 성립하지 않도록 하는 방법이다.

교착 상태 회피는 스레드가 평생 요구하고 사용할 자원에 대한 부가적인 정보를 미리 제공받고, 운영체제는 각 요청을 위해 그 스레드가 기다려야 할지 않을지를 결정할 수 있다.

 

2) 시스템이 교착상태가 가능하도록 허용한 다음에 회복시키는 방법

 

교착상태가 발생했는지를 조사하는 알고리즘과 교착상태 복구 알고리즘을 사용할 수 있다.

 

3) 문제를 무시하고, 교착상태가 시스템에서 발생하지 않는 척한다.

 

오히려 발생한 교착상태를 해결하는 데 더 많은 비용이 들 수 있으므로 무시한다.

이 경우 교착상태가 누적되면 시스템 성능을 저하시킬 수 있기 때문에 수작업으로 다시 시작할 필요가 있다.

 

 

8.5 교착 상태 예방

---

앞서 설명한 것처럼, 교착 상태가 발생하려면 4가지 필요조건이 모두 성립해야 한다.

이들 조건 중 최소한 하나가 성립하지 않도록 보장함으로써, 우리는 교착 상태 발생을 예방할 수 있다.

 

1) 상호 배제

 

상호 배제 조건을 성립하기 위해선 적어도 하나의 자원은 공유가 불가능한 자원이어야 한다.

일반적으로 상호 배제 조건을 거부함으로써 교착 상태를 예방할 수는 없다. 어떤 자원들은 근본적으로 공유가 불가능하기 때문이다.

 

2) 점유하며 대기

 

시스템에서 점유하며 대기 조건이 발생하지 않도록 하려면 스레드가 자원을 요청할 때마다 다른 자원을 보유하지 않도록 보장해야 한다.

대안 프로토콜은 스레드가 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있도록 허용하는 것인데, 이는 자원 이용률 감소와 기아 발생 우려가 있다.

 

3) 비선점

 

이미 할당된 자원이 선점되지 않아야 한다는 것이다.

이 조건이 성립되지 않게 하기 위해, 어떤 자원을 점유하고 있는 프로세스가 즉시 할당할 수 없는 다른 자원을 요청하면, 현재 점유하고 있는 모든 자원들이 선점되게 할 수 있다.

 

4) 순환 대기

 

지금까지 제시된 세 가지 옵션은 대부분 상황에서 일반적으로 실용적이지 않다.

그러나 마지막 순환 대기 조건은 꽤나 실용적이라고 한다.

이 조건이 성립되지 않게 하기 위해, 모든 자원 타입에 대해 전체적인 순서를 부여하여, 각 프로세스가 열거된 순서대로 자원을 요청하도록 요구할 수 있다.

 

 

8.6 교착 상태 회피

---

위에서 설명한 교착 상태 예방 알고리즘은 시스템 처리율이 감소한다는 문제가 있다.

만약 우리가 각 스레드의 요청과 방출에 대한 완전한 순서를 파악하고 있다면, 우리는 각 요청에 대해서 가능한 미래의 교착 상태를 피하고자 스레드가 대기해야 하는지 여부를 결정할 수 있다.

이와 같은 결정을 하려면, 현재 가용 자원, 각 스레드에 할당된 자원, 각 스레드가 앞으로 요청하거나 방출할 자원을 고려해야 한다.

 

이 방법을 사용하는 가장 단순한 모델은, 각 스레드가 자신이 필요로 하는 각 유형의 자원마다 최대 수를 선언하도록 요구하는 것이다.

자원의 최대 수 정보를 미리 파악할 수 있다면, 우리는 시스템이 교착 상태에 들어가지 않을 것을 보장하는 알고리즘을 만들 수 있다.

 

 

* 안전 상태 (Safe state)

시스템 상태가 안전하다는 말은 시스템이 어떤 순서로든 스레드들이 요청하는 모든 자원을 교착 상태를 발생시키지 않고 차례로 모두 할당해 줄 수 있다는 것을 뜻한다. 즉, 시스템이 안전 순서(safe sequence)를 찾을 수 있다면 시스템은 안전하다고 말한다.

 

또한 안전하다는 것은 교착 상태가 발생하지 않는다는 것을 의미한다.

하지만 불안전하다고 반드시 교착상태로 간다는 것을 의미하진 않는다.

 

이제 안전이라는 개념을 통해 회피 알고리즘이 어떻게 교착 상태를 회피할 수 있는지 정의할 수 있다.

기본 원칙은 시스템의 상태가 항상 안전 상태를 떠나지 않도록 고수하는 것이다.

우선, 최초 상태는 당연히 안전하고, 그 후 스레드들이 자원을 요청할 때마다 시스템은 승낙해도 안전 상태인지 확인하고 승낙한다.

하지만, 이 방법은 프로세스가 요청한 자원보다 시스템이 더 많은 자원을 갖고 있더라도 때에 따라 그 프로세스를 기다리게 할 수 있으므로, 자원의 이용률이 낮아질 수 있다.

 

 

* 자원 할당 그래프 알고리즘

자원 할당 그래프를 그려보면서 사이클이 안 생기게 하여 교착 상태를 회피할 수 있다.

위 8.2에서 설명한 자원 할당 그래프에 예약 간선(claim edge)이라는 새로운 타입의 점선으로 된 간선을 도입한다.

이 간선의 원리는 이렇다.

 

• 자원 요청 시 : 예약 간선은 요청 간선으로 변환된다.
• 방출 요청 시 : 요청 간선은 예약 간선으로 변환된다.

 

교착 상태 회피를 위한 자원 할당 그래프

 

따라서 우리는 스레드 T(i)가 실행되기 전에, 스레드의 모든 예약 간선이 자원 할당 그래프에 표시해야 한다.

스레드 T(i)와 연관된 모든 간선들이 예약 간선일 때만 예약 간선 T(i) -> R(j)를 그래프에 추가하도록 허용하면 된다.

 

또한 이때 요청 간선 T(i) -> R(j)가 할당 간선으로 변환해도 자원 할당 그래프에 사이클을 형성하지 않을 때만 요청을 허용할 수 있다.

이 그래프에서 사이클을 탐지하는 알고리즘은 n^2 차수의 연산이 필요한데, n은 스레드의 수를 의미한다.

 

 

* 은행원 알고리즘

자원 할당 그래프 알고리즘은 종류마다 자원이 여러 개씩 있게 되면 사용할 수 없다.

이럴 때는 은행원 알고리즘을 사용하는데, 이름의 유래는 이 알고리즘을 은행에 적용하면 고객들이 현금을 찾으러 와도 일정한 순서에 의해 모든 고객의 요청을 다 들어줄 수 있게 되기 때문이다.

 

이 시스템에서는 스레드가 시작할 때 스레드가 가지고 있어야 할 자원의 최대 개수를 자원 종류마다 미리 신고하여야 한다.

스레드가 자원을 요청하면 시스템은 그것을 들어주었을 때 시스템이 계속 안전 상태에 머무르게 되는지 여부를 판단해야 한다.

 

은행원 알고리즘을 구현하려면 몇 가지 자료구조가 필요하다. (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)

 

 

8.7 교착 상태 탐지

---

만약 시스템이 교착 상태 예방이나 교착 상태 방지 알고리즘을 사용하지 않는다면, 교착 상태가 발생할 수 있다.

이때, 시스템은 다음 알고리즘들을 반드시 지원해야 한다.

 

• 교착 상태가 발생했는지 결정하기 위해 시스템의 상태를 검사하는 알고리즘
• 교착 상태로부터 회복하는 알고리즘

 

* 각 자원 유형이 한 개씩 있는 경우

모든 자원들이 한 개의 인스턴스만 있다면, 대기 그래프(wait-for graph)를 이용하여 교착 상태 탐지 알고리즘을 정의할 수 있다.

대기 그래프는 자원 할당 그래프로부터 자원 유형의 노드를 제거하고, 적절한 간선을 결합함으로써 대기 그래프를 얻을 수 있다.

 

(a) 자원 할당 그래프     (b) a에 대응되는 대기 그래프

 

 

마찬가지로, 대기 그래프가 사이클을 포함하는 경우에만 시스템에 교착 상태가 존재한다.

교착 상태를 탐지하기 위해 시스템은 대기 그래프를 유지할 필요가 있고, 주기적으로 그래프에서 사이클을 탐지하는 알고리즘을 호출한다.

 

 

* 각 유형의 자원을 여러 개 가진 경우

대기 그래프는 종류마다 자원이 여러 개씩 존재하는 상황에서는 사용할 수 없다. 

따라서, 은행원 알고리즘과 마찬가지로 시시각각 그 내용이 달라지는 자료구조를 사용한다.

 

 

* 탐지 알고리즘 사용

교착 상태가 자주 일어난다면 탐지 알고리즘도 자주 돌려야 한다.

교착 상태가 일어나는 시점은 어떤 스레드가 자원을 요청했는데 그것이 즉시 만족되지 못하는 시점이다. 

자원을 요청할 때마다 탐지 알고리즘을 호출하면 오버헤드가 크게 되는데, 이에 상응하는 대안은 한 시간에 한 번 또는 CPU이용률이 40% 이하로 떨어질 때 탐지 알고리즘을 호출하는 것이다. (CPU 이용률, 교착 상태 야기한 스레드 파악 불가로 좋지 않은 방법)

 

 

 

8.8 교착 상태 회복

---

탐지 알고리즘이 교착 상태가 존재한다고 결정하면, 두 가지 처리 방법이 있다.

 

1. 운영자가 수작업으로 처리
2. 시스템이 자동으로 교착 상태로부터 회복

 

또한 교착 상태를 깨뜨리는 데는 두 가지 방법이 있다.

 

1. 한 개 이상의 스레드를 중지(abort)
2. 교착 상태에 있는 하나 이상의 스레드들로부터 자원을 선점(preempt)

 

* 프로세스 종료

 

프로세스를 중지(abort)시킴으로써 교착 상태를 제거하기 위해 두 방법 중 하나를 사용한다.

 

1. 교착 상태 프로세스를 모두 중지 : 확실하게 사이클을 깨뜨리지만, 비용이 크다. 이들 계산의 결과물들을 반드시 폐기해야 하며, 아마 나중에 다시 계산해야 하기 때문이다.
2. 교착 상태가 제거될 때까지 한 프로세스씩 중지 : 각 프로세스가 중지될 때마다 교착 상태 탐지 알고리즘을 호출해야 하므로 상당한 오버헤드를 유발한다.

 

 

* 자원 선점

자원 선점을 이용해 교착 상태를 제거하려면, 교착 상태가 깨어질 때까지 프로세스로부터 자원을 계속 선점해 이들을 다른 프로세스에 주어야 한다.

고려해야 할 사항은 다음과 같다.

 

• 희생자 선택(selection of a victim) : 어느 자원과 어느 프로세스들이 선점될 것인가?
• 후퇴(rollback) : 프로세스로부터 자원을 선점하려면 이 프로세스를 어떻게 해야 하는가? 이 프로세스를 안전한 상태로 후퇴시키고, 그 상태로부터 다시 시작할 필요가 있다.
• 기아 상태(starvation) : 기아 상태가 발생하지 않는 것. 즉 자원들이 동일한 프로세스로부터 항상 선점되지 않는다는 것을 어떻게 보장하는가?