[OS] 교착 상태(Deadlocks)

 

서론

---

한 스레드가 자원을 요청했을 때, 그 시각에 그 자원을 이용할 수 없는 사황이 발생할 수 있고, 그때는 스레드가 대기 상태로 들어갑니다. 이처럼 대기 중인 스레드들이(그들이 요청한 자원들이 다른 스레드들에 의해서 점유되어 있고 그들도 다 대기 상태에 있기 때문에) 결코 다시는 그 상태를 변경시킬 수 없으면 이런 상황을 교착 상태라 부릅니다.

[OS] 식사하는 철학자들 문제(The Dining-Philosophers Problem)

위 게시글의 식사하는 철학자들이 전부 왼쪽 젓가락을 집었을 때의 경우와 "두 기차가 교차로에서 서로 접근할 때는, 둘 다 완전히 정지해야 하며 상대방이 없어지지 않는 한 누구도 다시 출발할 수 없다."라는 예제가 교착상태의 좋은 예시입니다.

일반적으로 교착 상태를 해결하는 방법에는 크게 세 가지가 있습니다.

교착상태를 해결하는 세 가지  방법
교착 상태 예방(Prevention) 또는 회피(Avoidance)	교착 상태가 되지 않도록 합니다.
교착 상태 탐지(Detection) 및 복구(Recovery)	교착 상태가 탐지되면 시스템에 문제가 발생하지 않도록 조치를 취합니다.
교착상태 무시(Ignore)	교착 상태가 정말 드물게 발생하는 경우(1년에 한번) 교착 상태 예방 또는 탐지와 관련된 지속된 오버헤드 및 성능 저하를 발생 시키는 것보다 교착 상태가 발생하도록 하고 필요에 따라 재부팅하는 것이 더 나을 수 있습니다. (Unix 및 window를 포함한 대부분의 운영체제가 사용하는 방법)

이번 게시글에서는  아래와 같이 교착상태 예방과 회피만 다뤄 볼 것이며 목차는 아래와 같습니다.

• 교착 상태를 특징짓는 4가지 필수 조건을 정의한다.
• 자원 할당 그래프에서 교착 상태 상황을 식별한다.
• 교착 상태 예방을 위한 4가지 방법을 평가한다.
• 교착 상태 회피를 위해 은행원 알고리즘(Banker's Algorithm)을 적용한다.

 

교착 상태 특성(_Deadlock Characterization)

---

(1) 필요조건들(_Necessary Conditions)

교착 상태는 한 시스템에 다음 네 가지 조건이 동시에 성립될 때 발생할 수 있습니다. (발생할 수도 있다는 것이지 꼭 발생하는 것은 아님)

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

우리는 교착 상태가 발생하려면 위 네 가지 조건이 성립되어야 함을 꼭 기억해야 합니다. 순환 대기 조건은 점유하며 대기 조건을 암시하므로, 서로 합쳐도 될 것 같지만 각 조건을 별개로 간주하는 것이 유용하기 때문에 나눠졌습니다.

(2) 자원 할당 그래프(_Resource-Allocation Graph)

교착 상태는 시스템 자원 할당 그래프라고 하는 방향 그래프로 더욱 정확하게 기술할 수 있습니다. 이 그래프는 정점(vertex) V의 집합과 간선(edge) E의 집합으로 구성됩니다. 정점 V의 집합은 시스템 내의 모든 활성 스레드의 집합인 T = {T1, T2, .... Tn}과 시스템 내의 모든 자원 유형의 집합인 R = {R1, R2, ... Rm}의 두 가지 유형으로 구별됩니다.

 스레드 Ti로부터 자원 유형 Rj로의 방향 간선(directed edge)은 Ti->Rj로 표현하며, 이것은 스레드 Ti가 자원 유형 Rj의 인스턴스를 하나 요청하는 것으로 현재 이 자원을 기다리는 상태입니다. 자원 유형 Rj로부터 스레드 Ti로의 방향 간성은 Rj -> Ti로 표현하며, 이것은 자원 유형 Rj의 한 인스턴스가 스레드 Ti에 할당된 것을 의미합니다. 방향 간선 Ti -> Rj는 요청 간선(request edge)이라 부르고, 방향 간선 Rj -> Ti는 할당 간성(assignment edge)이라 합니다.

 도식적으로, 우리는 각 스레드 Ti를 원으로 표현하고, 각 자원 유형 Rj는 사각형으로 표현합니다. 간단한 예로, 아래 이미지에 표시된 자원 할당 그래프는 교착상태 상황을 잘 나타내고 있습니다.

교착상태인 자원 할당 그래프

first_mutex 권한을 가지고 있는 스레드1이 second_mutex를 기다리는데  second_mutex는 스레드2가 가지고 있고, 이 스레드2는 first_mutex를 기다리고 있어서 영원히 서로 할당받을 수 없는 교착상태를 보여줍니다. 

 자원 유형 Rj가 한 개 이상의 인스턴스를 가질 때는 각 인스턴스를 사각형 내의 하나의 점으로 표시합니다. 할당 간선은 또한 반드시 사각형 안의 하나의 점을 지정해야만 하지만, 요청 간선은 사각형 Rj만을 가리킨다는 것에 유의해야 합니다.

 스레드 Ti가 자원 유형 Rj의 한 인스턴스를 요청하면, 요청 간선이 자원 할당 그래프 안에 삽입됩니다. 이 요청이 만족할 수 있으면, 요청 간선은 즉시 할당 간선으로 변환됩니다. 스레드가 더 자원에 대한 접근을 해야 하지 않으면 자원을 방출하고, 그 결과 할당 간선은 삭제됩니다.

 아래 이미지를 예시로 상황을 한번 설명해 보겠습니다.

자원 할당 그래프

스레드 집합 T, 자원 집합 R, 그리고 상태를 나타내는 E는 아래와 같습니다.

• T = {T1, T2, T3}
• R = {R1, R2, R3, R4}
• E = {T1->R1, T2->R3, R1->T2, R2->T2, R2->T1, R3->T3}

자원의 인스턴스는 아래와 같습니다.

• 자원 유형 R1의 인스턴스가 한 개
• 자원 유형 R2의 인스턴스가 두 개
• 자원 유형 R3의 인스턴스가 한 개
• 자원 유형 R의 인스턴스가 세 개

스레드 상태는 아래와 같습니다.

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

자원 할당 그래프의 정의로부터, 우리는 만일 그래프가 사이클(cycle)을 포함하지 않으면 시스템 내 어느 스레드도 교착 상태가 아니라는 것을 알 수 있습니다. 반면, 그래프가 사이클을 포함하면 교착 상태가 존재할 수 있습니다(반드시 발생하는 건 아님)

 만일 각 자원 유형이 정확하게 하나의 인스턴스만을 가지면, 하나의 사이클은 교착 상태가 발생하였음을 암시합니다. 만일 사이클이 각각 하나의 인스턴스만 갖는 자원 유형의 집합만을 표함 한다면, 교착 상태가 발생한 것입니다. 사이클에 포함된 각 스레드는 교착 상태에 있습니다. 이 경우에 그래프 내의 한 사이클은 교착 상태가 존재하기 위한 필요충분조건이 됩니다.

 만일 각 자원 유형이 여러 개의 인스턴스를 가지면, 사이클이 반드시 교착상태가 발생했음을 의미하지는 않습니다. 이 경우 그래프 내의 사이클은 교착 상태가 존재하는 데 필요조건이며 충분조건이 되지는 않습니다.

 이 개념을 설명하기 위해, 다시 위 자원 할당 그래프 이미지를 살펴봅시다. 스레드 T3가 자원 유형 R2의 인스턴스를 하나를 요청한다고 가정해봅시다. 사용 가능한 자원이 현재 없기 때문에, 요청 간선 T3 -> R2를 그래프에 아래의 이미지와 같이 추가합니다. 

교착 상태를 갖는 자원 할당 그래프

이 시점에서 시스템 내에 두 개의 최소 사이클이 존재합니다.

• T1 -> R1 -> T2 -> R3 -> T3 -> R2 -> T1
• T2 -> R3 -> T3 -> R2 -> T2

스레드 T1, T2 그리고 T3는 교착 상태입니다. 스레드 T2는 스레드 T3이 점유하고 있는 자원 R3을 기다립니다. 스레드 T3는 반면에 스레드 T1이나 T2가 자원 R2를 방출하기를 기다립니다. 또한 스레드 T1은 T2가 자원 R1을 방출하기를 기다립니다.

 이제 아래 이미지에 있는 자원 할당 그래프를 생각해 봅시다. 

사이클이 있지만 교착 상태가 아닌 자원 할당 그래프

이 예에서도 역시 사이클을 갖습니다.

• T1 -> R1 -> T3 -> R2 -> T1 

그러나 위 예에서는 교착 상태가 없습니다. 프로세스 T4가 자원 유형 R2의 인스턴스를 방출할 수 있음을 자세히 봐야 합니다. 이어 그 자원이 T3에 할당될 수 있고, 그 경우 사이클이 없어집니다.

 요약하자면, 자원 할당 그래프에 사이클이 없다면, 시스템은 교착 상태가 아닙니다. 반면에, 사이클이 있다면 시스템은 교착 상태일 수도 있고 아닐 수도 있습니다. 

 

교착 상태 예방(_Deadlock Prevention)

---

우리가 위에서 살펴본 것처럼, 교착 상태가 발생하려면 네 가지의 필요조건 각각이 성립해야 함을 알 수 있었습니다. 그렇다면 우리는 이제 이들 조건 중에서 최소한 하나가 성립하지 않도록 보장함으로써 우리는 교착 상태의 발생을 예방할 수 있습니다.

상호 배제(Mutual Exclusion)의 부정	- 읽기 전용 파일과 같은 공유 자원을 사용합니다.
점유 및 대기(Hold and Wait)의 부정	- 프로세스 대기를 없애기 위해서 프로세스가 실행되기 전에 필요한 모든 자원을 할당합니다. (자원 낭비 발생) - 자원을 점유하지 않고 있을 때에만 다른 자원을 요청할 수 있도록 합니다. (기아상태가 될 수 있음)
비선점(No Preemption) 의 부정	- 모든 자원에 대한 선점을 허용합니다. - 프로세스가 할당받을 수 없는 자원을 요청하는 경우, 기존에 가지고 있던 자원을 모두 반납하고 새 자원과 이전 자원을 얻기 위해 대기하도록 합니다. (자원 낭비 발생)
순환 대기(Circular Wait)의 부정	- 자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구하도록 합니다. (자원 낭비 발생)

 

 

교착상태 회피(_Deadlock Avoidance)

---

바로 위에서 설명한 교착상태 예방 방법을 이용하면 장치의 이용률이 저하되고 시스템 총 처리율(throughput)이 감소한다는 문제가 있습니다. 

교착상태를 회피하는 대안은 자원이 어떻게 요청될지에 대한 추가 정보를 제공하도록 요구하는 것입니다. 예를 들어, 자원 R1과 R2를 가진 시스템에서 스레드 P가 두 자원을 모두 방출하기 전에 먼저 R1을 요청하고, 다음에 R2를 요청한다고 가정하고, 스레드 Q는 먼저 R2를 요청하고, 다음에 R1을 요청한다고 가정합시다. 각 스레드의 요청과 방출에 대한 완전한 순서를 파악하고 있다면, 우리는 각 요청에 대해서 가능한 미래에 교착 상태의 발생을 피하게 하기 위해 스레드가 대기해야 하는지 마는지의 여부를 결정할 수 있습니다. 각 요청에 대해 위와 같은 결정을 하려면 시스템은 현재 요청을 받아들일 수 있는지 또는 반드시 대기해야 할 것인지를 결정하기 위해 아래의 세 가지를 고려해야 합니다.

• 현재 가용 자원
• 현재 각 스레드에 할당된 자원
• 각 스레드가 앞으로 요청하거나 방출한 자원

이 방법을 사용하는 다양한 알고리즘들은 필요한 정보의 양과 유형에서 차이가 있습니다. 가장 단순하고 제일 유용한 모델은 각 스레드가 자신이 필요로 하는 각 유형의 자원마다 최대 수를 선언하도록 요구하는 것입니다. 각 스레드가 요청할 각 유형의 자원의 최대 수 정보를 파악할 수 있다면, 우리는 시스템이 교착 상태에 들어가지 않을 것을 보장하는 알고리즘을 만들 수 있습니다. 교착 상태 회피 알고리즘은 시스템에 순환 대기 상황이 발생하지 않도록 자원 할당 상태를 검사합니다. 자원 할당 상태는 강요 자원의 수, 할당된 자원의 수 그리고 스레드들의 최대 요구 수에 의해 정의됩니다.

 

이제 두 개의 교착 상태 회피 알고리즘(자원 할당 그래프 알고리즘, 은행원 알고리즘)을 알아볼 건데 그전에 안전 상태라는 용어에 대해 먼저 알아보겠습니다.

안전 상태(_Safe State)

시스템 상태가 안전(safe)하다는 말은 시스템이 어떤 순서로든 스레드들이 요청하는 모든 자원을(최대 요구 수를 요구하더라도) 교착 상태를 야기시키지 않고 차례로 모두 할 당해 줄 수 있다는 것을 뜻합니다. 즉, 시스템이 안전 순서(safe sequence)를 찾을 수 있다면 시스템은 안전하다고 말합니다. <T1, T2, ..., Tn>과 같은 스레드 순서가 안전하다는 말은(모든 Ti에 대해) 그 Ti가 요청하는 자원을 시스템에 현재 남아있는 자원과 앞에서 수행을 마칠 모든 스레드 Tj들이(j <i) 반납하는 자원들로 만족시켜 줄 수 있음을 뜻합니다. 이의 경우 Ti가 요청할 자원들을 즉시 만족시켜줄 수 없을 것으로 판단되면 Ti가 모든 Tj들이 마친 후 까지 기다리게 하면 됩니다. 그러면 Ti는 모든 Tj들이 반납한 자원들을 가지고 수행을 할 수 있게 됩니다. Ti가 끝났을 때 T(i+1)은 필요한 모든 자원을 얻게 되고 이와 같은 상황이 계속됩니다. 이처럼 모든 스레드를 무사히 마칠 수 있는 시퀀스를 찾을 수 없으면 불안전(unsafe)하다고 말합니다.

 시스템의 상태가 안전하다면 물론 교착 상태가 아닙니다. 반대로 교착 상태에 있는 시스템은 불안전한 상태에 있습니다. 그렇지만 아래의 이미지와 같이 시스템 상태가 불안전하다고 해서 반드시 교착 상태로 간다는 것을 뜻하는 것은 아닙니다.

안전, 불안전, 그리고 교착 상태 공간

시스템이 불안전하다는 말은 앞으로 교착 상태로 가게 될 수도 있다는 뜻입니다. 그러므로 시스템이 안전 상태에 머무는 한 운영체제는 불안전 상태나 교착 상태 모두를 예방할 수 있습니다. 그러나 일단 불안전 상태에 들어가게 되면 운영체제는 교착 상태가 일어날 수도 있는 자원 요청을 막을 수는 없습니다. 스레드들의 행동 양태가 불안전 상태를 제어합니다.

 예를 들어 아래 예시처럼 시스템에 12개의 자원이 있고 T0, T1, T2 세 개의 프로세스가 있다고 가정해 봅시다. T0가 10개의 자원을 필요로 하고, T1이 4개, T2가 9개까지의 자원을 필요로 할 수 있습니다. 임의의 시점 t0에서 T0가 5개, T1이 2개, T2가 2개의 자원을 보유 중입니다.(따라서 이제 3개의 자원이 시스템 보유분으로 남았습니다.)

최대 소요량과 현재 사용량

t0에서 시스템의 상태는 안전합니다. <T1, T0, T2> 순서가 있으므로 안전 상태입니다. 왜냐하면 T1이 시스템 보유분으로 먼저 끝내고 나면(이젠 원래 보유분 3개 남았던 것에 T1이 반납하는 2를 추가하여 3 + 2 = 5개가 시스템 보유분이 됩니다), T0이 그 다섯 개를 가져가 끝낼 수 있고, 마지막으로 T2가 끝내면 됩니다(이제 시스템 보유분은 다시 12개가 됩니다).

 시스템은 안전 상태에 있다가도 불안전 상태로 전이할 수 있습니다.

1. 예를 들어 t1에서 T2가 자원 한 개를 추가로 요청하여 그것을 주었다고 가정해 봅시다.
2. 그러면 이제 시스템 상태는 더 이상 안전하지 않게 됩니다.
3. 이 상태에서는 T1 만이 원하는 자원을 다 할당받을 수 있습니다.
4. T1이 마치고 자원을 반납해도 시스템 보유분은 4개뿐입니다.
5. T0가 5개를 가지고 있고 최대 10개를 필요로 하므로 추가로 5개까지를 더 요청할 수 있습니다.
6. 그럴 경우 자원의 개수가 부족하므로 T0은 끝내지 못하고 기다릴 수밖에 없게 됩니다. 마찬가지로 T2도 6개까지의 자원을 추가로 요청할 수 있습니다. 그러면 이 스레드도 기다려야 합니다.
7. 결과는 교착상태입니다.

그러므로 위에서 T2가 자원을 한 개 더 달라고  할 때 그 요청을 그대로 들어주면 실수를 범하는 셈이 됩니다. T2가 한 개를 요청했더라도 다른 스레드가 끝날 때까지 기다리게 했다가 그것을 주었다면 교착 상태를 피할 수도 있었을 것입니다.

이제 안전이라는 개념이 이해되었다면 회피 알고리즘이 어떻게 교착 상태를 회피할 수 있는지 정의할 수 있습니다. 기본 원칙은 시스템의 상태가 항상 안전 상태를 떠나지 않도록 고수하는 것입니다. 최초의 상태는 물론 안전합니다. 그 후 스레드들이 자원을 요청하면 시스템은 자원을 즉시 할당할 수 있는지 아니면 스레드가 대기해야 하는지 결정해야 합니다. 요청한 자원을 즉시 승낙해 주는 경우는 시스템의 상태가 안전 상태에서 안전 상태로 옮길 때뿐입니다.

 이러한 방식에서는 스레드가 요청한 자원보다 많은 양을 시스템이 보유하고 있다고 하더라도 그 프로세스를 기다리게 하는 상황이 벌어질 수 있습니다. 따라서 자원의 이용률은 회피를 안 쓸 때 비해서 낮아질 수밖에 없습니다.

 

(1) 교착상태 회피 알고리즘 1: 자원 할당 그래프 알고리즘

만약 각 자원 유형마다 단지 하나의 인스턴스를 갖는 자원 할당 시스템을 갖고 있다면, 우리는 교착 상태 회피를 위해 위에서 설명한 자원 할당 그래프의 변형을 사용할 수 있습니다. 요청 간선과 할당 간선에 추가하여, 우리는 예약 간선(claim edge)이라는 새로운 타입의 간선을 도입합니다. 예약 간선(Ti -> Rj)은 Pi가 미래에 자원 Rj를 요청할 것이라는 의미입니다. 이 간선의 방향은 요청 간선과 유사하지만 점선(dashed line)으로 표시합니다. 프로세스 Ti가 자원 Rj를 요청하면, 예약 간선 Ti -> Rj는 요청 간선으로 변환됩니다. 마찬가지로  Ti가 자원 Rj를 방출할 때, 할당 간선 Rj -> Ti는 예약 간선 Ti -> Rj로 다시 변환됩니다.

 우리는 시스템에서 자원이 반드시 예약되어야 함에 유의해야 합니다. 즉, 스레드 Ti가 실행되기 전에, 스레드의 모든 예약 간선이 자원 할당 그래프에 표시되어야 합니다. 스레드 Ti와 연관된 모든 간선들이 예약 간선일 때만 예약 간선 Ti -> Rj를 그래프에 추가하도록 허용함으로써 우리는 앞의 조건을 완화할 수 있습니다.

 스레드 Ti가 자원 Rj를 요청한다고 가정해봅시다. 요청 간선 Ti -> Rj를 할당 간선 Rj -> Ti로 변환해도 자원 할당 그래프에 사이클을 형성하지 않을 때만 요청을 허용할 수 있습니다. 

만약 사이클이 없다면 자원을 할당해도 시스템은 안전 상태가 됩니다. 사이클이 발견되면, 할당은 시스템을 불안전 상태로 만들 것입니다. 그러므로 스레드 Ti는 자신의 요청이 충족될 때까지 반드시 대기해야 합니다.

 이 알고리즘을 설명하기 위해 아래의 자원 할당 그래프를 고려해 봅시다.

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

T2가 R2를 요청한다고 가정해 봅시다. R2가 현재 가용 상태이지만, 우리는 이를 T2에 할당할 수 없습니다. 왜냐하면, 아래와 같이 할당할 경우 그래프에 사이클이 생기기 때문입니다.

불안전 상태의 자원할당 그래프

사이클은 시스템이 불안전한 상태에 있음을 의미합니다. 만일 T1이 R2를 요청하고, T2가 R1을 요청하면 교착 상태가 발생합니다.

(2) 교착상태 회피 알고리즘 2: 은행원 알고리즘(Banker's Algorithm)

자원 할당 그래프 알고리즘은 종류마다 자원이 여러 개씩 있게 되면 사용할 수 없습니다. 아래에서 기술하는 은행원 알고리즘은 자원이 여러 개씩 있을 때도 사용할 수 있습니다. 하지만 앞의 자원 할당 그래프보다 은행원 알고리즘은 효율성이 다소 떨어집니다. 이 알고리즘이 은행원(banker's)라고 붙여진 이유는 이 알고리즘을 은행에 적용하면 고객들이 현금을 찾으러 와도 일정한 순서에 의해 모든 고객의 요청을 다 들어줄 수 있게 되기 때문입니다.

 이 시스템에서는 스레드가 시작할 때 스레드가 가지고 있어야 할 자원의 최대 개수를 자원 종류마다 미리 알려야 합니다. 물론 이 숫자가 자원의 총 보유 수를 넘어서면 안 됩니다. 스레드가 자원들을 요청하면 시스템은 그것을 들어주었을 때 시스템이 계속 안전 상태에 머무르게 되는지 여부를 판단해야 합니다. 계속 안전하게 된다면 그 요청을 들어줍니다. 그렇지 않다면 이 스레드의 요청은 허락이 안 된 채 다른 스레드가 끝날 때까지 기다리게 됩니다.

 은행원 알고리즘을 구현하려면 먼저 아래의 자료들을 알아야 합니다. n은 스레드의 수이고 m이 자원의 수라고 가정합니다.

• Available: 각 종류별로 가용한 자원의 개수를 나타내는 벡터, 크기 m
• Max: 각 스레드가 최대로 필요로 하는 자원을 나타내는 행렬, n x m
• Allocation: 각 스레드에 현재 할당된 자원의 개수를 나타내는 행렬, n x m
• Need: 각 스레드가 향후 요청할 수 있는 자원의 개수를 나타내는 행렬, 크기 n x m

위 자료들은 시간이 지남에 따라서 그 값과 크기가 변할 수 있습니다.

이제 예시를 들어 한번 은행원 알고리즘을 알아봅시다.

• 현재 시스템에는 다섯 개의 프로세스 T0부터 T4까지 있고, A, B, C 세 가지 종류의 자원이 있다고 가정합니다.
• 시스템에는 A 자원이 10개, B자원이 5개, C자원이 7개가 있습니다. 

Need(필요로 하는 수) 행렬 값은 (Max - Allocation)으로 부터 얻어집니다.(최대 필요로 하는 수 - 현재 할당된 수)

이 시스템은 안전하다고 말할 수 있습니다. 왜냐하면 <T1, T3, T4, T2, T0> 순으로 자원을 할당하게 되면 안전성 기준을 만족시키기 때문에 안전 순서(safe sequence)를 가졌기 때문입니다.

이번에는 T1이 A자원 한 개와 C 자원 두 개를 추가로 요청, 즉 Request = (1, 0, 2)라고 가정해 봅시다. 이 요청을 즉시 들어줄 것인지를 판단하기 위해서는 먼저 Request < Available인지 여부를 검사해야 합니다. 즉 (1,0,2) <= (3, 3, 2)인지 여부를 검사해야 합니다. 이 조건이 만족하므로 다음 단계로 마치 이 요청을 들어주는 것처럼 상태 정보를 만들어 봅시다.

이제 이 상태가 안전한지 여부를 살펴보면 됩니다. T0부터 순서대로 계산해보면 결국 <T1, T3, T4, T0, T2>라는 안전 순서(safe sequence)가 나옴을 알 수 있습니다. 따라서 T1의 요청을 즉시 들어줄 수 있습니다.

 만약 이러한 상태에서 T4가 (3, 3, 0)을 요청하면 자원이 모자라므로 들어줄 수 없다는 것 을 알 수 있습니다. 또한 T0가 (0, 2, 0)을 요청한다면 자원은 충분히 있지만 상태를 불안전 상태로 만드므로 역시 그 요청을 즉시 들어줄 수 없다는 것을 알 수 있습니다.