교착 상태

교착 상태란?

 

둘 이상의 프로세스들이 자원을 점유한 상태(Hold)에서 서로 다른 프로세스가 점유하고 있는 자원을 요구(Request)하며 무한정 기다리는 현상입니다. 

 

교착 상태 발생 조건

 

다음 네 가지 조건이 모두 만족되어야 Deadlock이 발생합니다.

 

1. 상호 배제

한 프로세스에 의해 점유된 자원을 다른 프로세스들이 접근할 수 없어야 한다.

 

2. 점유와 대기

최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가 로 점유하기 위해 대기하는 프로세스가 있어야 한다.

 

3. 비선점

프로세스가 자원을 비선점하고 있기 때문이다. 비선점 자원은 그 자원을 이용하는 프로세스의 작업이 끝나야만 비로소 이를 이용할 수 있습니다. 즉, 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하기 때문에 교착 상태가 발생하는 것입니다. 

 

4. 원형 대기

 

공유자원과 공유자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어, 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 교착 상태가 발생할 수도 있습니다.

 

이는 발생하지 않을 수도 있다는 것! 예시를 통해 확인 해보겠습니다.

 

#Example 1

해당 그래프에 cycle이 없으므로, 시스템의 어떤 프로세스도 Deadlock 상태에 있지 않습니다. 

 

 

 

 

 

 

 

 

 

 

#Example 2

Process  P1, P2, P3  모두 Deadlock 상태입니다.

 

 

 

 

 

 

 

 

 

 

#Example 3

Cycle이 존재하지만 Deadlock이 아닙니다. P4 가 R2의 instance를 release하면, R2 resource는 P3 로 할당될 수 있는데, 이와 같은 경우 cycle이 깨지게 됩니다.

 

 

 

 

 

 

 

 

 

 

 

교착 상태 해결 방법

 

1. 예방

Deadlock의 발생조건인 Mutual Exclusion(상호 배제), Hold and Wait(점유와 대기), No preemption(비선점), Circular Wait(환형 대기) 중 최소한 1가지 조건이 성립하지 않도록 합니다.

 

2. 회피

추가적인 사전 정보(priori information)로 simulation을 통하여 Deadlock을 예측하고 회피할 수 있습니다.

Deadlock-avoidance algorithm은 Resource-allocation state를 통해 Circular-Wait 조건이 발생하지 않도록 할 수 있습니다.

Resource-allocation state는 process가 요구하는 최대 resource 개수, 사용 가능한 resources, 현재 할당된 resources 를 통해 시스템의 state가 safe/unsafe인지 판단합니다.

 

Safe State(안전한 상태) → 교착 상태가 발생하지 않는다.

Unsafe State(불안전한 상태) → 교착 상태가 발생할 수도 있다. 

 

#Example1

Total 12 resources are available

 

① Current resources 가 각각 <5,2,2>이므로 현재 Available resources는 12-(5+2+2)=3이다.

② P0는 Need resources가 5이므로, 현재 Available resources가 이를 제공할 수 없다. 따라서, P0나 P2가 종료되어 resources를 반환하길 기다려야 한다. 

③ P1에게 resources를 2개 주고, P1 프로세스가 종료되면 총 4개의 resources를 반환하여 Available resources가 5가 된다.

④ P0에게 resources를 5개 주고. P0 프로세스가 종료되면 총 10개의 resources를 반환하여 Available resources가 10이 된다.

⑤ P2에게 resources를 7개 주고. P0 프로세스가 종료되면 총 9개의 resources를 반환하여 Available resources가 10-7+9=12가 된다.

 

따라서, System은 <P1, P0, P2> sequnece일 때 safe하다.

# P1 이후의 P0 또는 P2 순서는 알고리즘을 어떠한 방식으로 구현했는지에 따라 방향을 결정하게 된다.

 

#Example2

Total 12 resources are available

 

① Current resources 가 각각 <5,2,3>이므로 현재 Available resources는 12-(5+2+3)=2이다.

② P0는 Need resources가 5이므로, 현재 Available resources가 이를 제공할 수 없다. 따라서, P0나 P2가 종료되어 resources를 반환하길 기다려야 한다. 

③ P1에게 resources를 2개 주고, P1 프로세스가 종료되면 총 4개의 resources를 반환하여 Available resources가 4가 된다.

④ 이때, P0나 P1의 Need resources가 각각 5와 6인데 이는 Available resources인 4보다 크기 때문에 더이상 진행할 수 없다. 

⑤ 따라서, 더이상 sequence가 형성될 수 없으므로, 시스템은 not safe이다. 

 

3. 탐지

각 리소스마다 하나의 인스턴스가 있는 경우 Wait-for graph를 통해 Deadlock을 유발하는 cycle을 탐지할 수 있습니다.

 

 

# 탐지 알고리즘 호출 주기

 

 

① Deadlock이 일어날 확률이 어느정도인가?

② Deadlock을 유발하는 process들을 얼마나 많이 roll back 해야 하나?

 

탐지 알고리즘은 오버해드가 있기 때문에 위와 같은 가정들과 탐지 알고리즘을 수행 사이의 Trade-off를 고려해야 한다.

 

4. Recovery (복구)

1) Process Termination(프로세스 강제 종료를 통한 회복)

 

(1) 모든 Deadlocked process를 종료(Terminate)

 

(2) Deadlock cycle이 없어질 때까지 process를 하나씩 종료(Terminate)

어떠한 기준으로 프로세스를 종료할까?

① Priority of the process

② How long process has computed, and how much longer to completion

③ Resources the process has used

④ Resources process needs to complete

⑤ How many processes will need to be terminated

⑥ Is process interactive or batch?

 

2) Resource Preemption(선점을 통한 회복)

 

교착 상태에 있는 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하여 해당 프로세스를 일시 정지시키는 방법입니다.

 

(1) Selecting a victim

Cost가 최소인 Victim process를 선택하여야 합니다.

 

(2) Rollback

선점된 프로세스를 문제 없던 이전 상태(Safe State)로 롤백해야 합니다. 보통 가장 안전한 방법은 프로세스를 중지시키고 재시작하는 것입니다.

 

(3) Starvation 

이때 한 프로세스가 계속 선점되는 것을 막아야합니다. 자원이 같은 프로세스에게만 할당되지 않게 할 수 있을까?

→ 한 가지 방법은 우선 순위를 사용하여 선점 될때마다 프로세스 우선순위를 높이는 것!