교착상태(Deadlock)

교착상태의 개념

프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우로 시스템 내에 하나라도 교착상태에 빠진 프로세스가 있다면 시스템은 교착상태인 것

🙄 Starvation과의 차이

기다린다는 점에서 starvation과 비슷한 점이 있기 때문에 헷갈리는 경우가 있지만 starvation은 발생할 수 있지만 우선순위와 같은 이유로 계속해서 밀리는 경우를 말한다. 또한 Starvation은 CPU스케줄링에서 쓰이는 용어로 기다리는 대상이 CPU이다. (ready상태에서 발생)

하지만 교착상태는 발생가능성이 없는 이벤트에 대한 기다림이고 CPU가 아닌 다른 자원이 대상이다.(blocked상태에서 발생)

교착상태 발생 필요조건

교착상태는 아래 4가지 경우를 모두 만족하면 발생합니다

• 공유될 수 없는 자원
• 선점될 수 없는 자원
• 자원 하나를 hold하면서 다른 자원을 요청
• 원형을 이루며 기다림
  위에 두가지는 데드락을 일으키는 자원으 특성이고 밑에 두가지는 상황을 뜻합니다.

해결방법

1. 예방

교착상태를 해결하는 방법 중 첫번째로 예방입니다. 교착상태가 일어나는 것을 미리 감지하고 일어나지 못하도록 막는 것입니다. 그럼 예방은 어떻게 할 수 있을까요? 앞에서 살펴봤던 교착상태 발생 필요조건 중 하나를 제거해주면 됩니다.

• 공유될 수 없는 자원 -> 모든 자원의 공유허용
  - 현실적으로 불가능..
• 선점될 수 없는 자원 -> 모든 자원 선점허용
  - 현실적으로 불가능...
  - 할당 받을 수 없는 자원을 요청하면 프로세스가 가지고 있던 모든 자원을 반납하고 다시 시작하는 방법으로 유사하게 실현 가능 -> 엄청난 비효율
• 자원 하나를 hold하면서 다른 자원을 요청 -> 필요한 자원을 한번에 모두 할당
  - 자원 낭비가 발생
• 원형을 이루며 기다림 -> 자원을 할당받을 수 있는 순서를 부여
  - 자원 낭비가 발생

장점

• 데드락이 절대 발생하지 않음

단점

• 심각한 자원낭비

• 비현실적

  
  
  
  

2. 회피

두 번째 해결방법은 회피입니다. 시스템을 계속해서 감시하며 교착상태가 될 가능성이 있는 자원의 할당요청을 보류하는 것입니다. 즉 시스템을 항상 safe state로 유지하면 됩니다. 이 방법은 아래와 같은 전제가 필요합니다

• 프로세스의 수 고정
• 자원의 종류와 수 고정
• 프로세스가 요구하는 자원과 최대 수량을 알고있음
• 프로세스는 자원을 사용한 뒤 반납함

safe state

모든 프로세스가 정상적으로 종료가 가능한 상태 즉 교착상태가 되지 않음을 보장하는 것입니다. safe state는 safe sequence의 존재를 통해 확이할 수 있습니다.

unsafe state

교착상태가 발생할 가능성이 있는 상태로 safe sequence가 존재하지 않는 상태입니다. (반드시 발생하는 것 아님)

회피알고리즘1 : 다익스트라의 banker's algorithm

• 한 종류의 자원이 여러개 있음
• 시스템은 항상 safe state로 유지해야함

아래는 하나의 자원에 대해서 여러 프로세스가 이미 할당받은 개수(Has)와 필요한 개수(Max)를 나타낸 것입니다.

이제부터 Safe Sequence를 찾아봅시다.
총 10개가 있던 자원이기 때문에 현재 3개의 여유가 있습니다. 그러면 B -> C -> A 순으로 자원을 빌려주고 반납받으면 모든 프로세스가 정상종료를 할 수 있습니다. 따라서 safe state인 것을 알 수 있습니다.

회피알고리즘2 : Habermann's algorithm

banker's algorithm의 확장판으로 자원의 종류가 여러개인 것이 특징입니다. 나머지는 banker's와 동일합니다.

아까와 비슷하지만 자원이 a,b,c 세 종류로 늘어났습니다.

이제부터 Safe Sequence를 찾아봅시다.
자원이 각각 3,3,2개씩 여유가 있기 때문에 p2 -> p4 -> p1 -> p3 -> p5순서로 자원을 할당해주고 반납받으면 모든 프로세스가 정상종료를 할 수 있습니다. 따라서 safe state인 것을 알 수 있습니다.

장점

• 교착상태를 막을 수 있음

단점

• 항상 시스템을 감시해야함
• safe state를 유지하기 위해 자원 활용도가 낮아짐
• 전제를 만족해야하기 때문에 비현실적

3. 탐지 & 회복

그래서 나온 방법이 방지나 예방없이 교착상태가 탐지되면 해결하는 방식입니다. 이 방법은 주기적으로 교착상태의 발생을 확인합니다.

탐지 : RAG(resource allocation graph)활용

• P -> R : 프로세스가 해당 리소스를 요청(아직 할당 못받음)
• R -> P : 프로세스가 해당 리소스를 사용하고 있음
  

이는 프로세스가 리소스를 요청하고 할당받은 관계를 그래프로 나타낸 것입니다.

Graph reduction

이 방법은 RAG를 활용해서 교착상태를 확인하는 방법입니다.
1. 필요한 자원을 모두 할당 받을 수 있는 프로세스를 찾아서 모든 edge(선)를 제거해줍니다.
2. 이를 계속해서 반복합니다
3. 결과

• 모든 edge가 제거되면 교착상태가 아닙니다
• edge가 남아있다면 교착상태입니다.

회복1 : 종료할 프로세스 찾기

• 종료비용이 가장 낮은 프로세스부터 종료 -> 불필요한 프로세스가 종료될 수 있음
• 최소의 비용으로 교착상태를 해결할 수 있는 프로세스 선택 -> 복잡함

회복2 : 선점할 자원 선택

• 자원을 뺏어서 필요한 프로세스에게 주기, 자원을 뺏긴 프로세스는 재시작 -> 불필요한 프로세스가 종료될 수 있음