[교착상태]

 

교착상태(Deadlock)

둘 이상의 프로세스(또는 스레드)가 서로가 가진 자원을 기다리느라 무한 대기 상태에 빠지는 현상

 

 

* 대표적인 예시로 "식사하는 철학자 문제" 가 있다. (한번 찾아보아라)

 

교착상태의 원인과 해결

 

교착상태 발생 조건 (4가지 모두 만족해야 함)

 

 

• 상호 배제(Mutual Exclusion)
  → 한 번에 한 프로세스만 자원을 사용할 수 있음
• 점유 대기(Hold and Wait)
  → 자원을 보유한 채로 다른 자원을 기다림
• 비선점(No Preemption)
  → 자원을 강제로 뺏을 수 없음
• 환형 대기(Circular Wait)
  → 프로세스들이 원형으로 자원을 기다림
  (A → B → C → A...)

 

해결 방법

 

4가지 조건 중 하나만이라도 제거 하도록 한다.

- 자원 순서를 정해서 순서대로만 요청하도록 한다. (환형 대기 없애기)

- 자원을 한 번에 모두 요청하게 하기 (Hold and Wait 제거) --> 점유 대기를 없애기 위해 한번에 모든 자원을 요청 (점유 대기 없애기)

- 주기적으로 자원 할당 그래프를 통해 교착 상태 감지 

- 동시에 2개 이상의 스레드가 자원을 활용할 수 있도록 함 (상호배제 없애기)

- 선점 허용으로 하는 방법은 간단하지 않고 문제점이 많아서 잘 사용하지 않음

 

 

교착상태 모델링

자원 할당 그래프

프로세스(Process)**와 자원(Resource) 사이의 관계를 노드와 간선으로 표현한 방향 그래프이며

이것을 통해 교착상태 여부를 시각적으로 판별 가능하다.

 

 구성 요소

1. 노드(Node)
   • P1, P2, … : 프로세스 노드 (동그라미)
   • R1, R2, … : 자원 노드 (네모)
2. 간선(Edge)
    방향 중요
   • 요청 간선 (Request Edge)
     P → R : 프로세스가 자원을 요청 중
   • 할당 간선 (Assignment Edge)
     R → P : 자원이 프로세스에게 할당됨

 

 

위 상황에서는 d 경우가 교착상태가 발생하였다.

 

 

교착상태의 회피

 

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

 

Dijkstra가 만든 알고리즘으로, "은행원이 대출해줄 때, 고객이 요청한 돈을 지금 다 줘도 나중에 파산 안 할지 먼저 시뮬레이션해서 결정한다"는 개념

 

즉, 현재 자원을 할당해도 시스템이 안전한 상태인지 시뮬레이션해서 결정하는 방식

 

항목설명

Available	현재 사용 가능한 자원 수
Max	각 프로세스가 필요로 하는 최대 자원 수
Allocation	현재 각 프로세스에게 할당된 자원 수
Need = Max - Allocation	앞으로 추가로 필요한 자원 수

 

동작 절차

1. 프로세스가 자원을 요청함
2. 요청을 임시로 할당해본 뒤
3. **안전한 상태(Safe State)**인지 확인 (모든 프로세스가 결국 실행을 완료할 수 있는 상)
4. 안전하면 진짜 할당, 아니면 거절

 

프로세스	Max	Allocation	Need
P1	7	0	7
P2	5	2	3
P3	3	2	1

 

P1이 자원 2개 요청

1. P1의 Need = 7, 현재 요청 2 → OK (Need보다 작거나 같음)
2. Available = 3 → 2만큼 할당 가능 → OK
3. 임시로 2 할당해보고 안전한지 확인
4. 시뮬레이션 상 모든 프로세스가 종료 가능하면 → 안전 → 진짜로 할당

* 사실상 교착상태는 거의 발생하지 않거나 정해진 특정 상황에서만 발생한다.

운영체제는 엄청 정교하게 만들어졌기 때문에 거의 대비가 되어있다.

발생한다면 사용자 어플리케이션에서 발생 할 것이다.

사실 경쟁조건이 더 많이 발생함

 

교착상태를 예방하는건 꽤 많은 비용을 발생시키므로 

예방을 초점에 맞추기 보다는 "발생하여도 복구할 수 있게"가 중점적이긴 하다.