7.Deadlock Resolution

데드락

데드락의 개념

데드락은 위의 이미지처럼 어떤 프로세스들도 자신이 원하는 자원을 얻을 수 없어 일을 할 수 없는 상태를 말한다.

 

Blocked/Asleep 상태 즉  프로세스가 특정 이벤트 또는 자원을 기다리는 상태에서 발생할 가능성이 없는 이벤트를 기다리는 경우 프로세스가 deadlock상태에 빠졌다고 한다. 

시스템내에서 dealock에 빠진 프로세스가 있다면 시스템이 deadlock상태에 있다고도 말한다.

 

그럼 이전에 배운 Starvation 상태와 데드락 상태의 차이점은 무엇일까?

starvation vs deadlock

starvation 은 프로세스가 CPU를 기다리는 상태에서 운이 없게도 계속 자신보다 우선순위가 높은 아이들이 들어와 뒤로 밀리거나 하는 등의 이유로 CPU를 할당받지 못해 무한 대기에 빠지는 것이다. 하지만 CPU를 받을 가능성이 아예 0%는 아니다.

 

Deadlock은 asleep상태로 들어가 자원/이벤트를 기다리는데 해당 자원이나 이벤트를 기다리나 일어나거나 자원을 받을 가능성이 ZERO인 경우이다.

 

 

데드락 관점에서 바라본 자원?

일반적으로 자원은 HW자원, SW자원으로 분류하나

데드락 관점에서 자원을 바라보고 분류하면 아래와 같다

1. 선점 가능한가?

2. 할당 단위가 어떻게 되는가?

3. 동시에 사용가능한가?

4. 재사용이 가능한가? 

 

1. 선점 가능한가

Preemptible resouces

자원을 빼앗긴 다음에 다시 내가 사용할 때도 문제가 발생하지 않는 자원을 Preemptible resouces라고 하며 이러한 자원에는 Proccessor(cpu), memory 등이 있다.

왜>?

context switching, swap device 등으로 작업을 중단할 때 save를 하고 떠났다가 돌아와서 복구하기 때문에 그렇다.

 

Non- Preemptible resouces

선점 가능한 자원과 반대로 선점 불가능한 자원이란 누군가에게 뺏겼을 때(선점당했을 때) 이후 진행에 문제가 발생하는 자원이다. 

여권 자녀에게 뺏기고 돌려받음

2. 할당 단위가 어떻게 되는가?

total allocation resources / partitioned allocation resources로 분류가 가능하며 토털 얼로케이션 리소스는 말 그대로 자원 전체를 프로세스에게 할당하는 것으로 Proccessor, disk drive 등이 있다
파티션 얼로케이션 리소스는 하나의 자원을 여러 조작으로 나누어 여러 프로세스에게 할당하는 가능한 자원으로 Memory 등이 이에 속한다.

 

3. 동시 사용 가능 여부에 따른 분류

> Exclusive allocation resources :  한 순간에  한 프로세스만 사용 가능한 자원

ex) proessor, memorry, disk drive... 메모리의 일정 공간을 할당하면 한순간 하나의 프로세스만 사용 가능하다.

 

> Shared allocation resources : 여러 프로세스가 동시에 사용 가능한 자원 

ex) Program, Shared data... 프로그램을 여러 개 띄어 동시에 사용 가능하다.

 

4. 재사용이 가능한가?

serially-reuable Resoursed(SR)

> 시스템 내에 항상 존재하는 자원으로 사용이 끝나면 다른 프로세스가 사용 가능한 자원이다.

ex) processor , memory, disk drive, program 등

 

Consumable resources(CR)

> 한 프로세스가 사용한 후 사라지는 자원 

ex) signal , message 등

 

 

어떤 자원이 Deadlock을 발생시킬 수 있을까?

1. Non-Preemptible resources

한번 자원을 할당받으면 끝날 때까지 뺏기면 안 되는 논 프림프터블 자원이 데드락이 생길 가능성이 있다.

2. Exclusive allocation resources

혼자만 쓸 수 있는 자원이 데드락을 만들 가능성이 있다.

3. SR, CR

SR은 한 번에 하나의 프로세스에 의해 사용 가능하기 때문에 문제가 발생할 수 있고CR은 사용후 사라지기에 데드락이 발생할수 있으나 CR을 고려한 Deadlock Model은 복잡하다.

 

할당 단위는 전체를 주는 자원도 선점이 가능하다면 문제가 되지 않기 때문에 영향을 미치지 않는다.

 

문제가 일어나는 자원을 보면 한순간 하나의 프로세스만 실행하고, 누군가에게 뺏길 가능성이 없는 자원(Non-Preemptible resources)들이 데드락을 발생시키는 자원으로 볼 수 있겠다.

 

Deadlock 발생 예

프로세스 1이 R2를 원하고 프로세스 2는 R1을 원한다 이때 프로세스 1이 R1을 원하지만 p2가 사용 중이므로 얻지 못하고 프로세스 2가 R2를 원하지만 R2의 소유자는 아직 프로세스 1이기 때문에 동작을 이어가지 못한다. 이제 둘은 이러지도 저러지도 못하고 멈추게 된다 

 

그래프로 표현하면 

이런 상태이다.

 

다른 방법으로 State Transition Model로 

 

이렇게 p1와 p2의 자원 할당 반납에 따른 모든 state에 따라 transition을 시각화 해준 모델로 process가 3개가 되면 3차원으로도 나타낼 수 있고 어떤 경우 교착상태에 빠지는지 알아볼 수 있다.

 

그림이 다소 복잡해 보이지만 이해하면 쉽다. 

 

Deadlock의 발생 필요조건

자원특성

1. Exclusive use of resources

2. Non-Preemprible resources

프로세스 특성

3. Hold and wait(Partial allocation)

4. Circular wait

 

필요조건이란 위 4가지 조건이 모두 만족해야 Deadlock이 발생한다는 것이고 반대로 말하면 한 가지라도 만족하지 않으면 데드락이 발생하지 않는다는 말이다.

 

자원의 특성을 보면 함께 사용 불가능하고 뺏기지 않는 자원을 가진 프로세스가 욕심도 많아서 이러한 자원은 들고 있는 상태에서 다른 자원까지 요청해서 프로세스의 요청 관계가 Circular wait의 형태를 띠는 경우다.

 

 

Deadlock의 해결법

1. Deadlock prevention methods (비현실적임.. )

교착상태를 사전에 예방하는 방법으로 앞서 말한 데드락 발생의 필요조건 중 하나를 제거해 데드락이 생기는 일을 예방해보자는 방법이다.

 

첫 번째로  데드락 유발 자원의 특성인 Exclusive use of resources 특성을 제거한다면? 모든 자원의 공유를 허용한다는 것인데 이는 현실적으로 불가능하다. 그럼 두 번째로 Non-Preemprible resources 특성을 제거해 모든 자원의 선점을 허용한다면? 

이것 역시 현실적으로 불가능하다. 프로세스가 할당받을 수없는 자원을 요청받았을 때 기존 작업하던 프로세스에게 무조건 뺏어와 자원을 뱉어내게 하고 실행 가능하지만? 이렇게 되면 99%까지 작업하다 모든 자원을 뱉어낸 프로세스는 다시 처음부터 일을 해야 한다  이는 자원낭비를 유발하므로 현실적으로 사용하지 못할 방법이다.

 

그럼 자원 차원은 어느 하나 포기를 못하니 프로세스 특성에서  Hold and wait(Partial allocation 특성을 제거하여 자원이 필요한 프로세스는 자신이 필요한 자원을 한꺼번에 모두 받아버린다면? 지금 당장 필요하지 않은 자원까지 들고 있기 때문에 자원낭비가 발생하고 정작 해당 자원이 필요한 자원은 무한 대기를 하는 Starvation상태 가능성이 있다.

 

그럼 마지막으로 Circular wait 조건을 자원들에게 순서를 부여해서 자원의 순서가 증가하는 방향으로만 요청이 가능하도록 하면 Circular wait 은 막을 수 있지만 아래 예시처럼 자원 2의 경우 1을 요청받지 못해 3을 먼저 받아 실행해도 됨에도 불구하고 요청하지 못하여 자원 3을 놀리게 되는 자원 낭비가 발생한다. 

Prevention 문제점 :

데드락 Prevention은 데드락 발생 필요조건 중 하나를 제거한다는 쉬워 보이는 아이디어로 절대 deadlock이 발생하지 않게 할 수 있지만 그렇게 할 경우 device 사용률이 너무 낮아지거나 심각한 자원낭비로 인해 시스템 전체 속도를 저하시키는 등의 문제를 일으켜 비현실적인 방법이다.

2. Deadlock Avoidance

예방은 현실적으로 불가능하니 피해 가는 방법을 택해보는 것이다.

이를 위해서 시스템의 상태를 계속 감시하다가 시스템이 deadlock상태가 될 가능성이 있는 자원을 할당하는 경우 요청을 보류하고 시스템을 항상 safe_state로 유지시키는 것이 Deadlock Avidance 방법이다.

 

safe_state?

safe_state란 모든 프로세스가 정상적으로 종료 가능한 상태로

Deadlock상태가 되지 않을 수 있는 Safe sequence가 존재하느냐 따라 존재하면 모든 프로세스가 정상적으로 종료 가능하다는 것을 의미한다. 

 

Unsafe state

데드락이 될 가능성이 있는 상태로, 꼭 발생하는 건 아니지만 가능성이 있는 상태를 말한다.

 

데드락 회피 방식의 가정은 아래와 같다.

프로세스 수 고정, 자원의 종류 및 수 고정, 프로세스가 요구하는 자원 및 최대수량 미리 알고 있음, 프로세스는 자원을 사용 후 반드시 반납.

 

이러한 가정이 있어야 경로를 미리 예측하여 그곳으로 가지 않게 안내가 가능한데 약간 Not practical 비현실적이다.

 

• Dijkstra’s banker’s algorithm

Deadlock avoidance를 위한 간단한 이론적 기법으로 다익스트라가 고안하였다.

뱅커스 알고리즘의 가정은 한 종류의 자원이 여러 개라 가정하여 시스템을 항상 safe state로 유지하는 알고리즘이다.

간단하게 이해하면 내가 돈을 10만 원 가지고 있는데 친구 ABC가 돈을 각각 빌려달라고 한다. 빌려준 돈은 반드시 받을 수 있다고 하였을 때

A(P1)는 1 만원 B(P2)는 5만 원 C(P3)는 2만 원을 빌려달라고 하였다 나에게는 현재 2만원이 남아있고 다음번에 또 A가 2만원 B가 4만원 C가 3만원을 빌려달라고 하였을떄 

우선 A에게 2만원을 빌려준 후 A가 3만 원을 반납하면 C에게 3만원을 빌려주고 5만 원을 돌려받아 마지막으로 B에게 4만 원을 빌려주고 9만 원을 돌려받는 다면 모두에게 돈을 빌려줄 수 있다. 즉 Safe Seauence 존재하므로 이 상태를 유지해 주면 되는 것이다.

그런데 위와 같이 나에게는 현재 2만 원만 남았는데 다음에 빌려달라는 경우는 4만 원 4만원 5만 원이다. 이런 경우 돈을 빌려주지 못하는 Not Safe Sequence로 Unsafe state가 된다 하지만 이 경우 반드시 데드락에 빠지는 건 아니다 돈을 안 빌리고 일을 끝낼 수도 있기 때문이다.

 

그럼 safe sequence를 어떻게 찾을까? 

 

친구들에게 추가로 자원 하나를 더 빌려줬다고 가정하고 돈을 빌려줘 보는 것이다. 

 

이렇게 돈을 빌려줘 보고 길이 보이면 자원을 할당 요구를 처리해주고 빌려줬는데 데드락이 발생할 것 같은 상황이 오면 요청을 거절하는 것 이것이 병 커스 알고리즘이다.

 

Habermann’s algorithm

하버 먼의 알고리즘은 다익스트라 알고리즘을 확장한 것으로 다익스르라가 하나의 자원을 예시로 알고리즘을 만들었다면 하버먼 알고리즘은 여러 종류의 자원을 고려한 뱅커스 알고리즘이라고 보면 된다. 

3종류의 자원이 있고 각각의 자원은 10개 5개 7개가 있다고 했을 때  뱅커스 알고리즘을 적용한 것이다.

최초 각 자원이 (10개 5개 7개)가 있었는데 (3,3,2) 개를 빌려주고 (7,2,5) 개가 남았으니 각 자원이 이것보다 적게 필요한 프로세스에게 먼저 빌려주는 방향으로 safe_sequence를 찾으면 safe_state를 유지할 수 있다

Deadlock Avoidance단점

데드락의 발생을 막을 수는 있으나 항상 시스템을 감시해야 하기 때문에 Overhead가 크고 safe state를 유지하기 위해 자원이 있음에도 불구하고 자원을 빌려주지 못해 자원낭비가 발생한다.

또한 프로세스의 수 , 자원 수가 고정되어있어야 하고 필요한 최대 자원수를 미리 말고 있어야 하기 때문에 현실적으로 어려움이 있다.

 

3.Deadlock Detection Method

데드락을 발생하면 해결하는 방법으로 데드락 방지를 위한 사전작업을 하지 않는다!

주기적으로 시스템, 프로세스가 deadlock 상태인지 확인하며 

데드락이 발생했는지 확인하는 방법으로 Resource Allocation Graph(RAG)를 사용한다.

< Resource Allocation Graph(RAG)를 이해하기 위한 정리 >

Resource Allocation Graph(RAG)

Resource Allocation Graph(RAG)는 프로세스와 자원으로 그룹을 나눈 방향성을 가진 그래프이다.

Edge는 프로세스와 리소스 사에만 존재하고 프로세스에서 프로세스 혹은 리소스에서 리소스로의 에지는 없다.

R1, R2... Rk는 서로 다른 타입의 자원이며 여기서 tk는 각 자원이 가진 개수를 의미한다고 보자.

 

이렇게 RAG에 대한 이해를 하고 보면 위 그래프가 이해가 될 것이다. 

P1는 R1타입의 자원 두 개를 할당받았고 R2타입 자원 하나를 요청한 상태이다.

P2는 R1타입의 자원을 하나 할당받았고 추가로 하나를 더 요청한 상태이며 R2자원을 하나 할당받았고 R2자원 하나를 추가로 하나 더 요청한 상황이다.

 

데드락이 발생했는지 그래프를 보고 알 수 있을까?

그림에서 Unblocked Process에 연결된 모든 edge 즉 내가 필요한 자원을 모두 받을 수 있는 프로세스에 연결된 모든 edge를 지우고 

더 이상 unblocked process가 없을떄가지 edge들을 지웠을대 모든 edge가 제거되었다면 현 상태에서 deadlock이 없음을 확인한 것이다. 

그런데 일부 edrger가 남았다면? 현재 deadlockd이 존재한다는 의미이다.

예 1 데드락 아님

예 2 엣지가 남아서 데드락

단점

단점으로는 검사주기에 영향을 받고 노드의 수가 많은 경우 overhead가 크다는 것이다. 

문제점이 있으면 해결하려는 여러 노력이 있어 해당 디텍션 방법 외에도 낮은 오버헤드를 가지는 방법으로 

특별한 경우를 가정하고 나온 Cycle detection , Knot detection 등 여러 탐색 방법이 나와있다. 

 

이제 이렇게 데드락을 검출하였다면 이제 이를 해결해 주는 과정이 필요하다.

 

4. Deadlock Recovery

데드락을 복구하는 방법은 아래와 같다.

1. Process termination

데드락 상태에 있는 일부 프로세스를 종료시키고 나중에 재시작시키는 방법

2. Resource preemption

데드락 상태 해결을 위해 선점할 자원을 선택하고 자원을 뺏긴 프로세스는 강제 종료시키는 방법

 

 

1. Process termination

데드락 상태의 프로세스 중 일부를 종료시켜야 하는데 죽이는 것도 고민이 되기에 기준이 필요하다. 

Termination cost model( 누굴 죽일까?)

우선순위, 프로세스 타입, 총 수행 시간, 남은 수행시간 , Accounting cost 등을 기준으로 코스트가 가장 작은 애를 죽이는 방법으로 갈 수 있다.

 

2. Resource preemption

데드락 상태 해결을 위해 선점하 자원을 선택하고 해당 자원을 가지고 있는 프로세스를 종료시킨다. 하지만 이런 경우 데드락 상태가 아닌 프로세스임에도 종료될 수 있다. 이렇게 강제로 자원을 뻇긴 프로세스는 이후 새로 재시작해야 한다.

 

그럼 누구의 자원을 뺏어야 하나?

preemption cost model이 필요하다 최소 비용 recovery method를 사용하는데 자원을 가지고 있는 애마다 한 번씩 뺏어보는 것을 가정해서 계산해보면 되기 때문에 O(R) 시간이 소요된다.

 

 

 

리커버리 방법을 보면 어쨌든 프로세스를 종료시킨다. 그럼 종료되는 애는 억울하게 지금까지 했던 작업을 날리게 되므로 이러한 부분을 방지하기 위해 Checkpoint를 만드는 방법을 택했다.
Checkpoint-restart method

프로세스의 수행 중 특정 지점마다 context를 저장하고 이렇게 저장한 checkpoint는 강제 종료 후 가장 최근의  checkpoint를 찾아 재시작하는 Rollback을 위해 사용된다.