[운영체제 공룡책] 교착 상태

Posted: 2025.07.08     Updated: 2025.07.15

운영체제 스터디를 하며 ‘운영체제 공룡책’ 교재를 정리한 글입니다.

교착 상태

Mutex 락, 세마포 등 동기화 도구들은 시스템 자원으로 현대 컴퓨터 시스템에서의 교착 상태 발원지이다.
락은 일반적으로 큐에 대한 액세스를 보호하거나 연결 리스트에 대한 액세스를 보호하는데 사용되는 등 특정 자료구조와 연관되어 있다.
스레드는 자원을 사용하기 전에 반드시 요청해야 하고, 사용 후에 반드시 방출해야 한다.

1. 요청: 스레드가 자원을 요청, 요청이 혀용되지 않으면 자원을 얻을 때까지 대기
2. 사용: 스레드가 자원에 대한 작업 수행
3. 방출: 스레드가 자원 방출

자원의 요청과 방출은 장치의 request(), release(), 파일의 open(), close(), 메모리 시스템 콜 allocate()와 free() 등이 있다.
세마포의 획득과 방출은 wait(), signal() 연산, mutex 락의 획득과 방출은 acquire(), release()를 통해 이루어진다.

운영체제는 스레드가 커널이 관리하는 자원을 사용할 때마다 스레드가 자원을 요청했는지, 할당 받았는지를 확인한다.
시스템 테이블은 각 자원이 가용 상태인지 할당되었는지, 어느 스레드에 할당되었는지 기록한다.

한 스레드 집합 내의 모든 스레드가 그 집합 내의 다른 스레드에 의해 발생될 수 있는 이벤트를 기다린다면 이 스레드 집합은 교착 상태에 있게 된다.

다중 스레드 애플리케이션의 교착 상태

스레드 두 개(thread_one, thread_two)와 mutex 락 두 개(first_mutex, second_mutex)가 있다고 가정하자.
thread_one이 1) first_mutex 2) second_mutex 순서대로 락을 획득하려고 한다.
thread_two가 1) second_mutex 2) first_mutex 순서대로 락을 획득하려고 한다.
이 때 thread_one이 first_mutex 를 획득하고 thread_two가 second_mutex 를 획득하면 교착 상태가 발생한다.
하지만 thread_two가 first_mutex 락 획득을 시도하기 전에 thread_one이 first_mutex 를 방출한다면 교착 상태는 발생하지 않는다.

라이브락(Livelock)

라이브락은 교착 상태와 유사하지만 일반적으로 스레드가 실패한 작업을 동시에 재시도할 때 발생한다.
따라서 각 스레드가 실패한 행동을 재시도하는 시간을 무작위로 정하면 회피할 수 있다.
네트워크 충돌이 발생할 때 Ethernet 네트워크의 접근법과 동일하다.

교착 상태 특성

필요조건

한 시스템에서 아래 네 가지 조건이 동시에 성립할 때 발생한다.

1. 상호배제(mutual exclusion): 한 번에 한 스레드만 사용할 수 있는 자원이 하나 이상 점유된다.
2. 점유하며 대기(hold-and-wait): 스레드가 최소 하나의 자원을 점유하고 다른 스레드에 점유된 자원을 추가로 얻기 위해 대기한다.
3. 비선점(no preemption): 자원을 강제로 방출할 수 없다.
4. 순환 대기(circular wait): 대기하고 있는 스레드의 집합에서 다음 스레드가 요구하는 자원을 순환적으로 점유하고 있다.

자원 할당 그래프

자원 할당 그래프는 교착 상태를 정확하게 기술할 수 있는 방향 그래프이다.

이 그래프가 사이클을 포함하지 않으면 시스템 내 어느 스레드도 교착 상태가 아니게 된다.
반대로 사이클을 포함한다면 교착 상태가 존재할 수 있다.
사이클이 각각 하나의 인스턴스만 갖는 자원을 포함한다면 교착 상태가 발생한다.
만약 각 자원 유형이 여러개의 인스턴스를 가지면 반드시 교착 상태가 발생하지는 않는다.

교착 상태 처리 방법

원칙적으로 교착 상태를 처리하기 위한 방법 3가지가 있다.

1. 문제를 무시하고 교착 상태가 시스템에 절대 발생하지 않는 척 한다.
2. 시스템이 교착 상태가 되지 않게 보장하기 위해 교착 상태를 예방하거나 회피하는 프로토콜을 사용한다.
3. 교착 상태를 허용한 뒤 복구시킨다.

Linux, Windows를 포함해 대부분의 운영체제가 첫 번째 해결안을 사용한다.
따라서 응용 개발자가 2번 방식으로 교착 상태를 처리할 수 있게 한다.
데이터베이스와 같은 일부 시스템은 3번째 방식을 주로 사용한다.

교착 상태 예방

상호 배제

공유 가능 자원들은 배타적인 접근을 요구하지 않으므로 교착 상태와 관련될 수 없다.
읽기 전용 파일은 동시 접근을 하용하므로 프로세스가 공유 가능 자원을 위해 대기할 필요가 없다.
그러나 일반적으로 동시에 여러 스레드가 공유할 수 없는 mutex 락과 같은 상황에서 상호 배제 조건을 거부하여 교착 상태를 예방하기는 어렵다.

점유하며 대기

스레드가 자원을 요청할 때마다 다른 자원을 보유하지 않아야 한다.
따라서 스레드가 자원을 가지고 있지 않을 때만 자원을 요청할 수 있도록 해야 한다.
혹은 스레드가 일부 자원을 요청하여 사용할 수 있게 하고, 추가로 자원을 요청하려면 할당된 자원을 모두 방출하게 한다.

자원이 할당되고 오래 사용되지 않을 수 있어 자원 이용률이 낮을 수 있다.
또는 인기 있는 자원이 여러개 필요한 스레드가 자원에 접근할 수 없어 무한정 대기해야 할 수 있다.

비선점

이미 할당된 자원이 선점되지 않게 해야 한다.

만약 스레드가 필요한 자원을 다른 스레드가 보유하고 있다면, 현재 자원을 사용하는 스레드가 자원을 방출할 때까지 기다려야 한다.
그리고 자원을 요청한 스레드는 자원을 사용할 수 있을 때까지 대기 상태가 된다.

어떤 스레드 A가 자원을 요청했을 때, 그 자원을 어떠한 스레드 B가 사용하고 있다면, 자원을 가진 스레드 B가 다른 자원을 위해 대기 중인지 확인한다.
만약 대기 상태에 있다면, 자원을 요청한 스레드 A에게 할당한다.

CPU 레지스터, 데이터베이스 트랜잭션과 같이 상태가 쉽게 저장되고 복원될 수 있는 자원에 종종 적용된다.
mutex 락, 세마포에는 적용하기 어렵다.

순환 대기

위 세가지 방식은 일반적으로 실용적이지 않아, 순환 대기 조건을 무효화하여 해결하는 것이 실용적이다.
모든 자원에 순서를 부여해 각 프로세스가 열거된 순서대로 자원을 요청하도록 한다.
first_mutex, second_mutex 가 동시에 필요한 스레드가 있다면, 반드시 first_mutex를 먼저 요청하고 second_mutex를 요청할 수 있다.

교착 상태 회피

교착 상태 회피는 교착 상태가 생기지 않도록 시스템이 상황을 예측해서 자원 할당을 제어하는 것이다.
어떤 자원이 얼마나 있고, 누가 어떤 자원을 가지고 있는지, 얼마나 요청할지 등의 정보를 알아야 한다.
시스템이 자원의 상태를 미리 분석해 교착 상태가 생길 위험이 있으면 자원의 요청을 거절한다.

안전 상태

안전 상태는 시스템이 어떤 순서로든 스레드들이 요청하는 모든 자원을 교착 상태를 발생시키지 않고 모두 할당해줄 수 있다는 것이다.
시스템이 안전 순서(safe sequence)를 찾을 수 있으면 안전하다고 말한다.
스레드들이 자원을 요청하는 순서가 T1 → T0 → T2 처럼 존재하고, 이 순서대로 자원을 줄 수 있다면 안전한 상태이다.

시스템의 상태가 안전하면 교착상태가 아니다.
교착 상태의 시스템은 불안전한 상태에 있으며, 시스템 상태가 불안전하다고 해서 반드시 교착상태로 간다는 것은 아니다.

자원 할당 그래프 알고리즘

자원 할당 그래프에 예약 간선(claim edge)를 도입할 수 있다.
미래에 자원을 요청한다는 의미이며, 점선으로 표시한다.
스레드가 실제로 자원을 요청하면 요청 간선으로 바뀌고, 자원을 방출하면 다시 예약 간선으로 바뀐다.

사이클 탐지(cycle detection) 알고리즘을 이용해 안전성을 검사한다.
사이클이 발견되면 자원 할당 시 시스템이 불안전 상태가 되므로, 사이클이 없을 때 자원을 할당한다.

은행원 알고리즘(Banker’s Algorithm)

이 알고리즘은 고객들이 현금을 찾으러 왔을 때 일정한 순서에 의해 모든 고객의 다 요청을 들어줄 수 있는 알고리즘이다.
스레드가 시작할 때 스레드가 가지고 있어야 할 자원의 최대 개수를 자원마다 미리 신고해야 한다.

이를 구현하기 위해 4가지의 자료구조가 필요하다.

• Available: 현재 사용 가능한 자원 개수
• Max: 각 스레드가 최대로 필요로 하는 자원의 수
• Allocation: 각 스레드에 현재 할당된 자원의 수
• Need: 각 스레드가 앞으로 더 요청할 수 있는 자원의 수

안전성 알고리즘

시스템이 안전한지를 알아낼 수 있는 알고리즘이다.
$m × n^2$ 연산($m$: 자원 종류 수, $n$: 스레드 수)이 필요하다.

Work: 현재 사용 가능한 자원
Finish[i]: 각 스레드가 완료되었는지

1. Work 를 Available 로 , Finish[i] = False 로 초기화한다.
2. Finish[i] = False 이며 Need[i] ≤ Work 인 i 값을 찾는다. 찾을 수 없으면 4번으로 간다.
3. Work = Work + Allocation[i], Finish[i] = true 후 2번으로 간다.
4. 모든 i 값에 대해 Finish[i] == true 이면 시스템이 안전 상태이다.

자원 요청 알고리즘

자원 요청을 안전하게 수락할 수 있는지 확인하는 알고리즘이다.
어떤 프로세스 Tᵢ가 자원 Request[i]를 요청했을 때, 아래 3단계를 따라간다.

1. Request[i] ≤ Need[i] 이면 2번으로 간다. 아니라면 시스템에 있는 개수보다 많이 요청했으므로 오류로 처리한다.
2. Request[i] ≤ Available 이면 3번으로 간다. 아니면 요청한 자원이 현재는 없어 기다려야 한다.
3. 자원을 실제로 할당한 것처럼 상태를 바꾸고, 안정성 알고리즘을 통해 시스템이 안전한 상태인지 확인한다.
   • 만약 바뀐 상태가 안전하면 자원을 할당하고, 불안전하다면 자원 할당 상태를 원래대로 복원한다.

Available  = Available - Request[i]
Allocation[i] = Allocation[i] + Request[i]
Need[i]       = Need[i] - Request[i]

교착 상태 탐지

시스템이 교착 상태 예방 혹은 방지 알고리즘을 사용하지 않는다면 교착 상태가 발생했는지 결정하기 위해 시스템 상태를 검사하는 알고리즘이나 교착 상태로부터 회복하는 알고리즘이 필요하다.

각 자원 유형이 한 개씩 있는 경우

모든 자원이 하나씩만 있을 때 자원 할당 그래프의 변형인 대기 그래프(wait-for graph)를 사용하여 교착 상태 탐지 알고리즘을 정의할 수 있다.
자원 할당 그래프에서 자원 유형 노드를 제거하고 간선을 결합하여 대기 그래프를 얻을 수 있다.

Tᵢ → Rⱼ → Tⱼ 와 같이 Tᵢ가 Rⱼ를 요청 중이고, Tⱼ가 Rⱼ를 보유 중인 경우 Tᵢ → Tⱼ 간선으로 바꿔 표시한다.

대기 그래프에 사이클이 생기면 교착 상태가 발생한 것이다.
시스템은 대기 그래프를 항상 유지하고 주기적으로 사이클이 있는지 검사해야 한다.

각 유형의 자원을 여러 개 가진 경우

은행원 알고리즘과 유사한 방식으로 교착 상태를 탐지할 수 있다.

• Available: 자원 종류별 사용 가능 개수
• Allocation: 각 스레드에 현재 할당된 자원의 수
• Request: 각 스레드가 요청 중인 자원의 수

1. Work = Available, 스레드에 할당된 자원이 있다면 Finish[i] = false, 할당된 자원이 없다면 true 로 초기화한다.
2. Finish[i] == false, Request[i] ≤ Work 를 만족시키는 i 값을 찾는다. 찾을 수 없다면 4번으로 간다.
3. Work += Allocation[i], Finish[i] = true 후 2번으로 간다.
4. 어떠한 i 값에 대해 Finish[i] == false 가 존재한다면 시스템은 교착 상태이다.

교착 상태 탐지 알고리즘의 사용

교착 상태가 자주 일어난다면 탐지 알고리즘도 자주 돌려야 한다.
극단적인 방법으로 스레드 요청이 즉시 만족되지 않을 때마다 탐지 알고리즘을 돌릴 수 있다.
이렇게 하면 교착 상태에 연루된 스레드와 교착 상태를 야기한 스레드도 알아낼 수 있게 된다.

자원을 요청할 때마다 탐지 알고리즘을 호출하면 오버헤드가 커진다.
지정된 시간 간격 혹은 CPU 이용률이 40% 이하로 떨어질 때 탐지 알고리즘을 호출할 수 있다.
이런 식으로 임의의 시간에 호출하게 되면 자원 그래프가 여러 개의 사이클을 포함할 수 있으므로, 교착 상태를 야기한 장본인인지 알아낼 수 없게 된다.

교착 상태로부터 회복

교착 상태가 존재한다고 결정되면, 교착 상태를 오퍼레이터에게 알리고 수작업으로 처리하거나, 시스템이 자동으로 회복하도록 할 수 있다.
교착 상태를 깨뜨리려면 순환 대기를 깨기 위해 한 개 이상의 스레드를 중지시키거나, 교착 상태의 하나 이상의 스레드로부터 자원을 선점하도록 할 수 있다.

프로세스, 스레드 종료

1. 교착 상태 프로세스 모두 중지

확실하게 교착 상태 사이클을 깨뜨릴 수 있지만 비용이 크다.
프로세스들이 오랫동안 연산했을 가능성이 있으며, 이 계산 결과를 폐기하므로 다시 계산해야 할 수 있다.

1. 교착 상태가 제거될 때까지 한 프로세스씩 중지

프로세스가 중지될 때마다 교착 상태 탐지 알고리즘을 호출해 교착 상태인지 확인해야 하므로 상당한 오버헤드를 유발한다.

프로세스를 중지시킬 때, 프로세스가 파일을 갱신하던 중이거나 mutex 락을 점유한 상태로 공유 데이터를 갱신하는 중이라면 데이터의 무결성 면에서 문제가 생길 수 있다.

부분 종료를 사용한다면 교착 상태의 프로세스 집합에서 어느 프로세스를 중지할 지를 결정해야 한다.
따라서 프로세스를 중지시켰을 때 유발되는 비용이 최소인 프로세스를 중지시켜야 하지만, 최소 비용이 정확하지 않으므로 여러 요인을 고려하여 정책을 결정해야 한다.

자원 선점

교착 상태를 해결하기 위해 선점을 사용할 경우 아래 3가지 사항을 고려해야 한다.

1. 희생자 선택(selection of a victim)

어느 자원과 어느 프로세스들이 선점될지 비용을 최소화하기 위한 선점 순서를 결정해야 한다.

1. 후퇴(rollback)

프로세스로부터 자원을 선점하기 위해서는 프로세스를 계속 실행시킬 수 없으므로, 안전한 상태로 후퇴시키고 다시 시작해야 한다.
안전 상태가 어느 시점인지 결정하기는 어려우므로 프로세스를 완전히 중지시키고 재시작해야 한다.
교착 상태를 깨트릴 수 있을 정도로 프로세스를 후퇴시킬 수 있다면 효과적이다.

1. 기아 상태(starvation)

항상 동일한 프로세스가 희생자로 선택된다면 기아 상태가 발생할 수 있다.
따라서 프로세스들이 한정된 시간 동안만 희생자로 선정된다는 것을 보장해야 한다.