개요
앞선 글에서 자원, 동기화, 병행성 이슈들을 다뤘다면
이번엔 시스템에서 피할 수 없는 문제, 교착상태(Deadlock)에 대해 정리 해보려고 한다.
운영체제와 데이터베이스 시스템에서 교착상태는 성능 저하, 서비스 장애의 주요 원인이 되므로
발생 원인부터, 진단, 예방법과 해결책까지 알아보자.
목차
1. 교착상태란? (Deadlock 정의)
- 두 개 이상의 프로세스가 서로가 점유한 자원을 기다리며, 아무도 작업을 못하는 상태
- OS, DB, 멀티스레드 환경, 네트워크, 철학자 문제 등 현실에서 다양하게 등장한다.
1-1. 교착상태와 아사(starvation) 차이
- 아사(starvation): 스케줄링 정책 등 운영체제의 문제로 특정 프로세스만 오랫동안 실행 기회를 못받는 현상 (정책/알고리즘 결함)
- 교착상태(deadlock): 여러 프로세스가 서로 자원을 점유한 채, 자연적으로 (알고리즘상 결함 없이도) 아무도 전진 못하는 상태
- 아사는 우선순위, Aging 등 정책으로 해결. 교착상태는 구조적 자원 경쟁에서 발생 → 더 근본적인 문제
1-3. 자원 할당 그래프와 교착상태
자원 할당 그래프란 프로세스가 어떤 자원을 사용중이고, 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것이다.
- 프로세스(원), 자원(사각형) 노드로,
- 요구/점유 상태를 간선으로 연결한 방향 그래프
- 사이클이 있으면 교착상태 가능성 있음
- 여러 자원, 동시 요청 구조는 "원형" 요구 패턴 → 교착상태 유발
2. 교착상태 발생의 네 가지 필요조건
교착상태가 발생하려면 다음 네 가지 모든 조건이 동시에 충족되어야 한다. 단 한가지라도 만족하지 않으면 교착 상태가 발생하지 않는다.
- 상호배제(Mutual Exclusion):
- 한 번에 하나의 프로세스만 자원을 점유'
(공유 X, 독점적 자원)
-> 배타적 자원 사용하면 교착 상태 발생
- 한 번에 하나의 프로세스만 자원을 점유'
- 비선점(Non-preemptive):
- 점유한 자원은 스스로 반납할 때까지 빼앗을 수 없음 (강제 중단 불가)
-> 빼앗을 수 없으면 공유 안되니 교착 상태 발생
- 점유한 자원은 스스로 반납할 때까지 빼앗을 수 없음 (강제 중단 불가)
- 점유와 대기(Hold and Wait):
- 자원을 점유한 채 추가 자원 요청 가능 (A를 가진 상태로 B를 요청)
-> 자원을 점유하면서 다른 자원을 기다리면 교착 상태 발생
- 자원을 점유한 채 추가 자원 요청 가능 (A를 가진 상태로 B를 요청)
- 원형 대기(Circular Wait):
- 프로세스 간 자원 요구가 원형(고리) 구조를 이룸 (P1→P2→…→Pn→P1)
-> 프로세스들이 서로 양보하지 않아 교착 상태 발생
- 프로세스 간 자원 요구가 원형(고리) 구조를 이룸 (P1→P2→…→Pn→P1)
이 중 하나라도 무력화하면 교착상태는 발생하지 않는다.
그렇다면 위의 교착 상태의 필요조건을 좀 더 자세하게 보면
- 상호 배제, 비선점 조건 : 자원이 어떤 특징을 가지는지를 나타낸다.
- 점유와 대기, 원형 대기 조건: 프로세스가 어떤 행위를 하고 있는지 나타낸다.
즉 필요조건도 자원의 특징과 프로세스의 행위에 따라 나뉜다.
원형 대기 조건은 나머지 세가지 조건이 만족했을 때의 결과로 나타나므로 엄밀히 말하면 상호 배제, 비선점 , 점유와 대기 조건이 만족하면 교착상태가 발생 할 수 있다.
2-1. 교착 상태의 예시
위 그림처럼 양쪽에서 사람들이 한 명씩 강을 건너고 있다고 생각해보자.
조건에 맞게 서로 앞으로 걸어가다 서로 마주치면 누구도 앞으로 나아갈 수 없는 상황이 발생한다. 이 구조는 운영체제의 교착상태를 표현하는 것 과 같다.
3. 교착상태 해결 방법
실제 운영체제는 예방, 회피, 검출/회복 세 가지 접근법을 사용한다.
3-1. 교착상태 예방 (Prevention)
- 상호 배제 예방
- 시스템 내에 있는 상호 배타적인 모든 자원, 즉 독점적으로 사용할 수 있는 자원을 없애 버리는 방법
-> 현실적으로 모든 자원을 공유할 수는 없으며 상호 배제를 적용하여 보호해야 하는 자원이 있기 때문에 상호 배제를 무력화하는 것은 사실상 어렵다.
- 비선점 예방
- 모든 자원을 빼앗을 수 있도록 만드는 방법 (선점형을 사용하는 방법)
-> 아사 현상이 발생할 수 있기 때문에 비선점 조건을 무력화하는 것은 사실상 어렵다.
- 점유와 대기 예방
-
프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법(전부 할당 or 아예 할당하지 않는 방식을 적용)
-> 자원이 아닌 프로세스의 자원 사용 방식을 변화시켜 교착 상태를 처리한다는 점에서 의미가 있다. (누가 양보를 할지 결정해야하는 문제가 있긴 하지만..)
-
단점: 프로세스가 자신이 사용하는 모든 자원에 대해 미리 자세히 알기 어렵다. (입력에 따라 달라지는 프로세스일 경우는 더욱더)**
당장 사용하지 않을 자원도 미리 선점하기 때문에 자원의 활용성이 떨어진다.
많은 자원을 사용하는 프로세스는 적은 자원을 사용하는 프로세스보다 불리하다. (많은 자원을 다 확보해야 실행이 가능하므로 실행 기회가 적음 -> 일괄 작업 방식으로 동작하게 됨)
- 원형 대기 예방
- 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당받을 수 있도록 하여 원형을 이루지 못하도록 막는 방법
-> 프로세스 작업 진행에 대한 유연성이 떨어지며(왜 R2> R1 ?), 자원의 번호를 어떻게 부여할 것인지가 문제이다.
3-2. 교착상태 회피 (Avoidance)
교착 상태의 모든 발생 가능성을 미리 제거하는 것이 아닌 교착 상태 발생 가능성을 인정하고(세 가지 필요조건 허용), 교착 상태가 발생하려고 할 때 적절히 회피하는 방법이다.
자원의 할당 제한
-
프로세스에 자원을 할당할 때 교착 상태가 발생하지 않는 범위를 미리 파악하여 그 범위 내에서만 자원을 할당한다.
-
교착 상태가 발생할 수 있는 수준 이상의 자원을 요청하면 프로세스를 대기 상태로 전환하여 교착 상태를 피한다.
-
즉, 자원의 할당량을 적절히 조절하여 안정 상태(safe state)를 유지하는 것이 핵심이다.
-
대표적인 예시: 은행원 알고리즘(Banker's Algorithm)
자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당한다.
은행원 알고리즘(Banker's Algorithm)
-
은행이 대출을 허용하는 방식과 유사한 알고리즘이다.
- 은행은 전체 자금 내에서 대출이 가능한 범위 내(안정 상태)에서는 대출을 허용하지만, 범위를 초과하면 거부하는 것과 유사하다.
-
예시: 우동 10인분, 스파게티 20인분의 재료가 있을 때 10명 이상의 예약을 받으면 문제가 발생하므로 최대 10명까지만 예약을 받는 상황과 유사하다.
은행원 알고리즘의 사용 변수
- 전체 자원(Total): 시스템 내의 모든 자원 수
- 가용 자원(Available): 현재 사용할 수 있는 자원의 수 (전체 자원 - 현재 할당된 모든 자원)
- 최대 자원(Max): 각 프로세스가 선언한 최대 자원 요청량
- 할당 자원(Allocation): 각 프로세스에 현재 할당된 자원 수
- 기대 자원(Expect): 각 프로세스가 앞으로 추가로 사용할 자원 수 (최대 자원 - 할당 자원)
은행원 알고리즘의 자원 할당 기준
- 각 프로세스의 기대 자원과 가용 자원을 비교하여 가용 자원이 기대 자원보다 크거나 같으면 자원을 할당한다.
- 기대 자원을 충족하지 못하는 경우 자원을 할당하지 않고 프로세스를 대기시킨다.
은행원 알고리즘의 안정 상태 조건
- 시스템의 가용 자원이 프로세스의 기대 자원보다 크거나 같은 상황이 하나라도 존재하면 안정 상태라고 본다.
- 불안정 상태라고 해서 반드시 교착 상태가 발생하는 것은 아니지만, 교착 상태 발생 가능성이 높아진다.
교착 상태 회피의 문제점
- 프로세스가 미리 사용할 모든 자원을 정확히 선언해야 한다.
- 전체 자원의 수가 고정적이어야 하며, 자원 활용률이 낮아진다.
- 실시간이나 동적 시스템에 적용하기 어렵다.
3-3. 교착상태 검출/회복 (Detection & Recovery)
- 교착 상태가 발생할 가능성을 허용하고, 실제 교착 상태 발생 시 탐지 및 복구한다.
교착 상태 검출
-
OS가 프로세스의 작업을 지속적으로 관찰하여 교착 상태 여부를 확인한다.
-
자원 할당 그래프를 모니터링하여 사이클이 발견되면 교착 상태로 판단한다.
-
타임아웃(Time-out)을 통한 검출 방법도 있다.
- 일정 시간 동안 진행되지 않은 프로세스를 교착 상태로 간주하여 종료한다.
- 구현이 간단하고 자주 발생하지 않을 상황에 적합하다.
데이터베이스에서의 타임아웃 문제
- 데이터베이스의 트랜잭션이 타임아웃으로 종료되면 데이터 일관성이 깨질 수 있다.
- 이를 방지하기 위해 체크포인트(checkpoint)와 롤백(rollback)을 사용한다.
-
해당 부분에 관해서는 별도로 데이터베이스의 트랜잭션 파트에 필자의 벨로그에 정리해놨다.
- 체크포인트: 문제가 발생하면 이전 정상 상태로 돌아가기 위한 저장점
- 롤백: 문제가 발생했을 때 체크포인트로 되돌아가는 과정
교착 상태 회복
- 교착 상태 검출 후, 이를 해결하기 위한 작업이다.
- 주로 교착 상태를 유발한 프로세스를 강제로 종료시킨다.
종료 방법
-
모든 프로세스를 동시에 종료
-
특정 프로세스를 선택하여 순차적으로 종료
- 우선순위가 낮은 프로세스를 먼저 종료
- 우선순위가 같으면 작업 시간이 짧은 프로세스를 먼저 종료
- 위 조건이 같다면 자원을 많이 사용하는 프로세스를 먼저 종료
[Reference]
