[운영체제] Deadlock

Deadlock

프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태로 ‘교착 상태’라고도 한다.

 

System model

-  CPU, files, I/O device 등의 리소스들은 R로 표현

-  각 리소스 R은 인스턴스 W를 가짐(R이 CPU라면 W는 CPU 코어들)

-  Request , use, release

 

 

 

Deadlock 발생조건

1.  Mutual exclusion – 하나의 리소스는 하나의 스레드만 사용할 수 있다.

2.  Hold and wait – 이미 하나의 리소스를 가지고 있고 추가적으로 다른 스레드의 리소스를 원할 때

3.  No preemption – 리소스를 한번 가져가면 작업을 수행하기 전까지는 리소스를 release하지 않는다.

4.  Circular wait – wait cycle이 존재할 때

 

circular wait

 

 

 

Resource allocation graph

-   T -> R이면 스레드가 리소스를 요청한  것

-   R -> T이면 리소스가 스레드에 할당된 것

-   리소스 안의 점은 리소스의 인스턴스들

-  사이클이 없으면 데드락도 없음

-  사이클이 있으면 데드락 가능성 있음(리소스에 인스턴스가 한 개씩이면 무조건 데드락이지만 여러 개 있으면 아닐 수도 있음)

 

 

 

Deadlock Handling

1.  deadlock prevention: 데드락 자체가 발생 안하도록 보장(애초에 데드락이 생기는 것이 불가능하도록 만듬)

2.  deadlock avoidance: 데드락 상황이 오지 않도록 상황에 따라 적절한 대처를 함

3.  deadlock detection: 데드락이 발생하면 다시 복구시킴

 

 

 

Deadlock Prevention

-   데드락 자체가 발생 안하도록 보장

-   mutual exclusion, hold and wait, no preemption이 안 일어나게 해줌

 

 

위 세가지 조건은 제약이 많이 작용하기 때문에 잘 사용되지 않음

-   Circular wait: 모든 resource에 번호를 부여한 다음 프로세스가 자원을 요구할 때 오름차순으로만 요구할 수 있게 한다.

-   Deadlock prevention은 request를 제한하는 것이기 때문에 성능이 떨어질 수 있음

 

 

 

Deadlock avoidance

-  Resource request에 대한 추가적인 정보를 가지고 deadlock을 피함

-  스레드가 자신이 사용할 최대 리소스 수를 선언

-  현재 사용가능한 리소스 개수, 현재 할당된 리소스 개수, 스레드가 사용할 최대 리소스 수 등을 고려하면서 deadlock을 막아줌

-  Safe state

스레드가 사용가능한 리소스를 요청할 때 시스템은 할당을 해주어도 시스템을 안전한 상태로 유지되는지 판단한다.

Safe state에서는 deadlock이 발생하지 않고 unsafe state에서는 deadlock이 발생할 가능성이 있으므로 safe state에 남아있도록 유지시키는 것이 deadlock avoidance이다.

스레드가 현재 사용가능한 리소스 외에도 다른 스레드가 사용하고 있는 리소스까지 고려(다른 스레드가 리소스를 모두 사용하면 그걸 가져와 사용하면 되므로)

 

 

 

 

Deadlock avoidance algorithm

 

1.  Resource allocation graph

리소스 타입당 인스턴스가 한 개일 때

 

Claim edge: 점선은 스레드가 미래에 request할 수도 있는것

Claim to request – 실제로 request를 해서 claim이 request(점선이 실선)으로 바뀌는 것

Request to assignment – resource가 실제로 allocated됐을 때 화살표 방향이 바뀜

Assignment to claim – resource가 release됨 미래에 다시 request될 수 있으니 claim으로 바꿈(다시 점선으로)

위 예시에서 R2가 T2에 allocated되면 cycle이 생기므로 allocate하면 안되는 것으로 판단

 

 

 

2.  Banker’s algorithm

리소스 타입당 인스턴스가 여러 개일 때

 

-   Available: 현재 사용할 수 있는 리소스 수

-   Max: 각 스레드가 사용할 최대 리소스 수

-   Allocation: 각 스레드마다 리소스가 얼마나 할당되어 있는지

-   Need: 스레드가 앞으로 리소스를 얼마나 요구할지

-   Safety algorithm: 현재 시스템이 safe state인지 판단하는 알고리즘

-   Resource request algorithm: request를 allocate해도 되는지 결정하는 알고리즘

 

 

 

Deadlock detection

-  일단 deadlock이 발생한 후에 recovery해줌

-   Wait for graph

Resource가 없고 어떤 스레드가 어떤 스레드를 기다리고 있는지만 표현해줌

그래프에 cycle이 있으면 deadlock이 있는 것

 

 

-  Recovery 방법

1.  Deadlock되 있는 스레드를 다 terminate 해 버림

2.  Deadlock 사이클에서 하나씩 terminate 해 봄

(어떻게 terminate할지는 시스템마다 다름)

3.  희생양을 정해서 resource를 뺐어 옴

4.  이전 safe state로 복구 시킴

등등