[OS] Deadlock

Deadlock

위의 사진의 경우,  S = Q = 1 일 때, P0 의 wait(S) 에 의해 S는 0이, P1의 wait(Q) 에 의해 Q 는 0 이된다. P0 가 wait(Q) 를 실행할 때, P1 이 signal(Q) 를 실행할 때까지 대기해야한다. 비슷하게 P1 이 wait(S) 를 실행할 때, P0가 signal(S) 를 실행할 때까지 기다려야 한다. 결국 P0 와 P1은 무한 대기하게 되며 이를 deadlock 되었다고 한다.

resource 를 가지고 있고 다른 프로세스가 보유한 resource 를 얻기 위해 대기하는 block 된 프로세스들의 집합을 Deadlock 이라고 한다.

 

 

Deadlock Necessary Conditions

Deadlock 이 발생하려면 다음 네 가지 조건을 동시에 만족해야한다.

• Mutual exclusion (상호 배제) : 한 번에 하나의 스레드가 자원을 사용할 수 있다.
• Hold and wait (점유 대기) :  하나 이상의 자원을 보유한 스레드가 다른 스레드가 보유중인 자원을 얻기 위해 대기해야 한다.
• No preemption (비선점) : 자원은 해당 스레드가 작업을 완료한 후에, 자원을 보유한 스레드에 의해서만 자발적으로 해제될 수 있다.
• Circular wait (순환 대기) : 순환 형태로 자원을 대기하고 있어야 함. 예를 들어, T1, T2, ... Tn 이 있다고 하면 T1 은 T2 의 자원을, T2 는 T3 의 자원을 , ... Tn 은 T1 의 자원을 대기한다.

 

 

Resource-Allocation-Graph 

Request edge : 스레드 Ti 가 자원 Rj 를 요청하여 해당 자원을 대기 중인 상태, Ti -> Rj 라고 표기한다.

Assignment edge : 자원 Rj 가 Ti 에 할당된 상태, Rj -> Ti 라고 표기한다.

 

resoucre allocation graph 에 cycle 이 없다면 deadlock state 가 될 수 없고, cycle 이 있다면 deadlock state 가 될 수도 있다.

 

 

Deadlock Prevention (예방)

Deadlock 이 발생하기 위해서는 네 가지 조건 모두 만족해야 하므로, 하나 이상의 조건을 충족하지 못하게 하여 Deadlock 을 막는 방법이다.

Mutual exclusion (상호 배제)

읽기 전용 파일 같은 공유 가능한 자원을 사용한다. 하지만, 일반적으로 일부 자원은 공유가 불가하므로 상호 배제 조건을 부정하여 Deadlock 을 방지하기 어렵다.

Hold and wait (점유 대기)

대기 상태가 발생하지 않으려면, 스레드가 자원을 요청할 때마다 다른 자원을 가지지 않도록 보장해야 한다.

• 실행 전 모든 자원을 요청하고 할당받는다. -> 비현실적
• 자원을 가지고 있지 않을 때만, 자원을 요청할 수 있도록 한다. 즉, 자원 요청 전 현재 할당 된 모든 자원를 해제한다.

Disadvantage

• 자원이 할당되었지만 오래 사용되지 않아 자원 사용률 낮을 수 있음 (자원 낭비)
• 필요한 자원이 다른 스레드에 할당되어 무기한 기다리는 starvation 발생 가능

No preemption (비선점) 

리소스를 선점할 수 있도록 한다.

• 스레드가 일부 리소스 보유 중, 즉시 할당할 수 없는 다른 리소스 요청하면 현재 보유중인 리소스를 선점되도록 한다. 
• 스레드가 일부 리소스 요청하면서 사용 가능한지 확인. 사용 가능하면 할당. 사용 가능하지 않으면 다른 자원을 기다리는 스레드에 할당되어 있는지 확인 후 선점.

Circular wait (순환 대기) 

모든 리소스에 순서를 정한 후, 순서대로 요청한다.

동적으로 lock 을 획득할 수 있는 경우, 순서를 부여해도 deadlock prevention 이 보장되지 않음

 

 

Deadlock Avoidance (회피)

Deadlock prevention 은 device utilization 이 낮아지고 시스템 처리량이 감소하는 부작용이 있을 수 있다.

자원을 요청하는 방법에 대한 추가 정보를 요구하여 deadlock 을 피할 수 있다. deadlock avoidance 알고리즘은 리소스 할당 상태(resource-allocation state)를 동적으로 검사하여 circular-wait 가 존재할 수 없도록 한다. 이때, 리소스 할당 상태는 사용 가능/할당된 리소스 수와 스레드 최대 수요에 의해 정의된다.

 

Safe state

시스템이 각 스레드에 리소스를 순서대로 할당하고 deadlock 을 피할 수 있는 상태를 safe 하다고 한다. 즉, safe sequence 가 존재하는 상태를 safe state 라고 한다.

safe sequence가 존재하지 않으면 시스템이 unsafe 하다고 한다. 이때, unsafe 하다고 반드시 deadlock 이 발생하는 것은 아니다. 

safe state 개념을 사용하면, deadlock 에 빠지지 않도록 보장하는 avoidance 알고리즘을 정의할 수 있다. 자원이 할당되도 safe state 를 유지하는 경우에만 자원 요청을 승인하도록 한다.

 

Resource-Allocation-Graph Algorithm (자원 할당 그래프 알고리즘)

리소스 유형이 하나만 있는 경우, 자원 할당 그래프 알고리즘을 사용해 deadlock 을 예방할 수 있다. 기존 request edge 와 assginment edge 이외에 claim edge(클레임 엣지) 를 추가한다.

 

Claim edge

• Ti -> Rj 는 스레드 Ti 가 미래 어느 시점에 리소스 Rj 를 요청할 수 있음을 나타낸다. 
• claim edge Ti -> Rj 에서 Ti 가 Rj 를 요청하면 request edge Ti -> Rj 로 바뀌며, assignment edge Rj -> Ti 에서 Rj 가 Ti 에 의해 해제되면 claim edge Ti -> Rj로 바뀜

calim edge 로 설정한 리소스에 대해서 cycle 이 생기지 않을 때만 safe state 로 판단해, 자원을 할당받아 deadlock 을 회피한다. cycle 이 생긴다면 unsafe state 로 판단한다.

 

Banker's Algorithm (은행원 알고리즘)

자원 할당 그래프 알고리즘은 여러 종류의 리소스가 있는 경우에 적합하지 않다. 은행원 알고리즘의 경우 이러한 시스템에 적용할 수 있지만, 리소스 할당 그래프 방식에 배히 효율이 떨어질 수 있다.

새 스레드가 실행될 때, 필요한 리소스 종류의 최대 인스턴스 수를 선언해야 한다. 리소스 집합을 요청하면 시스템은 리소스를 할당해도 safe state 를 유지하는지 확인한다. 안전하다면 리소스가 할당되고, 아니라면 다른 스레드가 충분한 리소스를 해제할 때까지 대기한다.

 

알고리즘에 필요한 데이터들은 다음과 같다.

• Available : 스레드에 할당 가능한 리소스
• Max : 스래드가 필요하는 리소스 최대 수
• Allocation : 스레드에 현재 할당 된 리소스 수
• Need : 스레드가 필요하는 남은 리소스. Max - Allocation

알고리즘은 다음과 같다.

1. Request <= Need 라면 step2 로 간다. 아니라면 스레드의 요청이 MAX 를 초과했으므로 error
2. Request <= Available 이라면 step3 로 간다. 아니라면 리소스를 사용할 수 없으므로 스레드는 대기해야 한다.
3. 스레드에 요청된 자원을 할당하며, 다음과 같은 데이터 변경이 일어난다.
   • Available = Available - Request
   • Allocation = Allocaiton + Request
   • Need = Need - Request
   • 자원 할당의 결과가 safe 하다면 스레드에 자원을 할당하고, unsafe 하다면 이전 상태를 유지한다.

 

예를 들어, 스레드 T0~T4 와 리소스 A, B, C 가 있다고 하자. 자원 A 는 10개, B 는 5개, C는 7개가 있다. 시스템의 한 시점을 아래와 같다고 하자.

그렇다면 Max - Allocation 을 통해 Need 를 구할 수 있다. 이는 아래와 같다.

T1 이 A, B, C 를 1, 0, 2개 요청한다고 하자. 즉, Request1 = (1,0,2) 라고 하자. 이때 Request1 <= Need (1,2,2) 와 Request1 <= Available (3,3,2) 를 만족하므로,  요청이 다음과 같은 결과를 만드는 것을 볼 수 있다.

이때 시스템은 safe 하므로, T1 에 자원을 할당해 줄 수 있다. 이러한 알고리즘을 따른다면  시퀀스 <T1, T3, T4, T0, T2> 는 safe sequence 를 만들기 때문에 실행 가능하다.

 

 

Deadlock Detection (탐지)

시스템은 deadlock 이 발생했는지 탐지하는 알고리즘과, deadlock 을 회복시키는 알고리즘을 사용해 deadlock 에 대처할 수 있다. 리소스 종류의 개수에 따라 사용되는 방법이 다르다. 

 

Wait-for graph

리소스의 종류가 하나일 때 사용한다. 자원할당 그래프에서 리소스를 제거하고 간선들을 연결시켜 새로운 그래프를 만든다. 위의 그림과 같이 (a) 를 (b) 로 만들 수 있다. 만약 wait-for graph 가 cycle 을 가진다면 해당 상태는 deadlock 이라고 말할 수 있다.

 

Banker's algorithm

리소스의 종류가 여러 개일 때 사용한다. deadlock avoidance 에서 사용하는 방법과 유사하며, unsafe 라면 deadlock 이라고 판단한다.

 

 

모든 리소스 요청에 deadlock detection 알고리즘을 사용하면, 오버헤드가 너무 커지므로 호출 빈도를 정해야 한다. 그 예들은 다음과 같다.

• 할당 요청이 승인되지 않을 때마다 호출
• 일정된 간격으로 호출
• CPU 사용률이 특정 값 미만이 되면 호출

 

 

Deadlock Recovery (회복)

deadlock 을 탐지하면 이용자에게 수동으로 deadlock 을 다루라고 알리거나, 자동으로 deadlock 으로 부터 회복할 수 있다. deadlock 을 자동으로 벗어나는 방법에는 두 가지가 있다.

 

Process and Thread Termination

프로세스나 스레드를 종료해서 deadlock 을 제거할 때, 두 가지 방법 중 하나를 사용한다.

• 모든 deadlock 프로세스들 종료하기 : deadlock 을 명확하게 제거할 수 있지만 실행중인 작업들을 잃어버릴 수 있음
• deadlock cycle 제거될 때까지 한번에 하나씩 프로세스 종료하기 : 상당한 overhead 가 발생한다.

상황에 맞추어 가장 적은 비용을 만드는 방법을 사용해야 한다.

 

 

Resource Preemption

선점을 통해 deadlock 을 제거하려면, deadlock cycle 이 깨질때 까지 프로세스로 부터 일부 자원을 선점하고 다른 프로세스에게 주어야 한다. 이를 위해서, 다음 세 가지를 고려해야 한다.

1. victim 선택하기
   • 비용을 최소화 할수 있는 프로세스와 리소스를 선점한다.
2. rollback
   • 리소스를 선점당한 프로세스를 safe state 로 rollback 하고 재시작한다.
   • 가장 간단한 해결책은 프로세스를 중단하고 다시 시작하는 것이다.
   • 필요한 만큼 rollback 하는게 더 효과적이지만, 정보 보관의 문제가 있다.
3. starvation
   • 한 프로세스가 계속 victim 으로 선택되어 starvation 이 발생하는 것을 고려해야 한다.
   • victim 을 선택할 때  rollback 횟수를 고려하여 비용을 계산한다.

 

 

Deadlock Ignorance (무시)

deadlock 의 성능 저하보다 이를 해결할 때의 성능저하가 더 큰 경우, deadlock 을 무시한다. 만약 deadlock 이 발생한다면,  사용자가 직접 프로세스를 종료하도록 한다.