OS-8) 프로세스 교착상태

topics 700-컴퓨터과학 704 운영체제
types 이론 학습
tags #deadlock #mutex #banker-algorithm

프로세스 교착상태 (Deadlock)

발생 조건

다음 4가지 조건이 동시에 만족할 때 발생한다. 단, 4가지 조건이 동시에 만족한다고 반드시 교착상태가 발생하는 것은 아니다.

조건 설명
상호 배제 (Mutual Exclusion) 동시에 한 자원을 한 프로세스만 사용 가능하다. 이게 아니라면 교착상태가 애초에 발생하지 않음 (한 자원을 한번에 여러 프로세스가 접근 가능하니까)
점유 상태로 대기 (Hold and Wait) 하나 이상의 자원을 가진 프로세스가 다른 프로세스가 가지고 있는 다른 자원을 획득하기 위해 기다린다
선점 불가 (No Preemption) 프로세스가 가진 자원은 사용이 끝난 후에 자발적으로만 방출될 수 있다 (== 뺏을 수 없다)
순환성 대기 (Circular Wait) 프로세스 집합이 존재할 때 순환형으로 자원을 기다리고 있는 상황

순환성 대기 판단

자원 할당 그래프를 그려보면 사이클이 발생하는지 알 수 있다.

상황 결과
그래프에 사이클이 존재하지 않는다 교착상태 없음
사이클이 존재 + 자원 타입마다 오직 하나의 인스턴스가 있다 교착상태 발생
사이클이 존재 + 여러 개 있으면 교착상태 발생 가능성 있음
Pasted image 20240418211706.png

예시

자원 A, B를 두 개의 스레드 S1, S2가 동시에 사용하려고 한다. 이때 자원이 두 개니 뮤텍스 또한 두 개고 A가 있는 뮤텍스를 LockA, B가 있는 뮤텍스를 LockB라고 하자.

  1. S1이 LockA를 확인한다. 내려가 있으니 올린다 (=1이 되면 누군가 점유하고 있다는 뜻이고 다른 프로세스는 이 자원을 획득하기 위해선 기다린다). 자원을 S1이 점유. S1: wait(A)
  2. S2가 LockB를 확인한다. 내려가 있으니 올리고 자원을 점유. S2: wait(B)

지금까지 S1은 A를 소유, S2는 B를 소유하고 있다.

  1. S1은 LockB를 확인한다. 안 내려가 있으니 대기
  2. S2는 LockA를 확인한다. 안 내려가 있으니 대기

교착상태 발생!

교착상태 핸들링

예방 (Prevention)

위의 4가지 필수 조건 중 하나라도 발생하지 않게 한다.

조건 예방 방법
상호 배제 비공유 자원을 미리 확보. 상호 배제 조건을 인정하지 않는 경우는 거의 불가능
점유 상태로 대기 자원 요청 시 어떠한 자원을 보유하지 않음을 보장. 단, 낮은 자원 활용률과 기아 초래
선점 불가 자원 보유 중인 프로세스가 다른 자원을 즉시 할당받지 않을 시 소유 중인 자원을 모두 방출. 선점당한 프로세스는 기존 자원과 새로 요청한 자원을 확보할 수 있는 경우에만 실행
순환 대기 모든 자원 유형을 전체 순서를 정하여 자원 요청

회피 (Avoidance)

각 요청을 운영체제가 직접 분석함으로써 데드락이 발생할 가능성을 확인한다 (동적임). 사용 가능한 추가적인 사전 정보를 시스템이 가져야 한다.

상태 판단

safe state인지를 판단하여 교착상태에 빠지지 않게 한다.

상태 설명
Safe State 모든 프로세스에 순서가 존재함. 교착상태 발생 불가
Unsafe State 교착상태 발생 가능성 있음 (반드시 발생하는 건 아님)
Pasted image 20240418214254.png

자원 할당 그래프

자원이 하나의 인스턴스만 있는 경우에 사용한다.

Pasted image 20240423222740.png

이렇게 사이클이 생기면 unsafe state라는 것이다.

인스턴스 여러 개일 때:

Pasted image 20240424033353.png

Banker 알고리즘

자원이 여러 개의 인스턴스가 있는 경우에 사용한다.

  • 각 프로세스는 최대 필요한 자원 수를 선언
  • 모든 리소스 가져올 시 유한 시간 내 반환
  • need = max - allocation
Pasted image 20240423223102.png

실행 순서:

  1. P1 할당 반환 → available: 5 3 2
  2. P3 할당 반환 → available: 7 4 3
  3. P4 할당 반환 → available: 7 4 5
  4. P0 할당 반환 → available: 7 5 5
  5. P2 할당 반환 → available: 10 5 7

탐지 (Detection)

데드락이 반드시 발생할 것을 가정하고 어느 부분이 데드락이 발생했는지 탐색하는 방식이다.

복구 (Recovery)

프로세스를 강제로 종료시키거나 자원을 강제로 회수한다.

관련 문서