1. Deadlock
- 운영체제에서 데드락(교착상태)이란, 시스템 자원에 대한 요구가 뒤엉킨 상태이다.
- 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황을 뜻한다.
1-1. Deadlock의 발생조건
데드락은 다음과 같은 4가지 조건을 모두 만족해야 발생한다.
-
상호 배제
한 번에 프로세스 하나만 해당 자원을 사용할 수 있다. 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다. -
점유 대기
자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다. -
비선점
이미 할당된 자원을 강제로 빼앗을 수 없다(비선점). -
순환 대기
대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.
1-2. Deadlock의 해결법
데드락은 다음과 같은 4가지 방법으로 해결이 가능하다.
1. 교착 상태 예방
-
교착 상태 발생 조건 중 한 가지를 제거하여 교착 상태가 발생하는 것을 예방한다.
-
자원의 상호배제 조건 방지
모든 자원을 공유 허용 -
점유와 대기 조건 방지
프로세스 대기를 없애기 위해서 프로세스가 실행되기 전에 필요한 모든 자원을 할당 (자원 낭비 발생)
자원을 점유하지 않고 있을 때에만 다른 자원을 요청할 수 있도록 한다. (기아상태가 될 수 있음) -
비선점 조건 방지
모든 자원에 대한 선점을 허용
프로세스가 할당받을 수 없는 자원을 요청하는 경우, 기존에 가지고 있던 자원을 모두 반납하고 새 자원과 이전 자원을 얻기 위해 대기하도록 한다. (자원 낭비 발생 ) -
순환 대기 조건 방지
자원에게 순서 부여를 통해 프로세스 순서의 증가 방향으로만 자원 요청
-
- 자원 낭비가 가장 심한 해결법이다.
2. 교착 상태 회피
-
프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태(Safe State)로 남아있는가를 확인하여 교착 상태를 회피하는 방법이다.
-
교착상태 회피를 하기 위해서는 다음과 같은 가정이 필요하다.
- 프로세스 수가 고정되어 있어야 한다.
- 자원의 종류와 수가 고정되어 있어야 한다.
- 프로세스가 요구하는 자원 및 최대 자원의 수를 알아야 한다.
- 프로세스는 반드시 자원을 사용 후 반납해야 한다.
Safe state
- safe sequence 가 존재하여 모든 프로세스가 정상적으로 종료할 수 있는 상태
safe sequence : 교착 상태를 발생 시키지 않고 자원을 할당하는 순서
Unsafe state
- 교착상태가 될 수 있는 상태
- 불안정 상태라서 반드시 교착상태가 발생하는 것은 아니다.
- Safe Sequence가 존재하면 Safe state라고 할 수 있다.
-
위와 같은 예시에서 P2 → P1 → P3로 자원을 할당하는 Safe Sequence가 존재하기에 Safe state라고 할 수 있다.
-
반면에 아래와 같은 예시는 Safe State가 존재하지 않는다.
교착 상태 회피 알고리즘
- 교착 상태 회피에는 여러가지 알고리즘이 활용된다.
- 자원 할당 그래프 알고리즘 (Resource-Allocation Graph Algorithm)
- 자원 할당 그래프에 예약 간선을 추가한다.
- 프로세스 시작 전에 모든 예약 간선들을 자원할당 그래프에 표시한다.
- 프로세스는 예약 간선으로 설정한 자원에 대해서만 요청할 수 있고 사이클이 형성되지 않을 때에만 자원을 할당 받는다.
예약 간선(claim edge)
향후 요청할 수 있는 자원을 가리키는 간선
- 자원 할당 그래프 알고리즘은 각 자원마다 하나의 인스턴스를 갖는 경우에만 사용할 수 있다.
- 위와 같이 종류마가 자원이 여러개 존재할 때는 사이클이 발생하더라도 데드락이 발생하지 않는 경우가 존재한다.
- 은행원 알고리즘 (Banker's Algorithm)
- 교착상태를 예측하여 교착상태가 가능한 상태는 자원을 할당하지 않는 알고리즘
- 검사하여 안정상태에 있으면 자원을 할당하고 불안정 상태라면 다른 프로세스들이 자원을 해제할 때까지 대기한다.
- 은행원 알고리즘을 적용하기 위해서는 자원의 양과 사용자(프로세스) 수가 일정해야 한다.
- 은행원 알고리즘은 프로세스의 모든 요구를 유한한 시간안에 할당하는 것을 보장한다.
3. 교착 상태 탐지
- 교착 상태 탐지는 탐지 알고리즘을 사용하여 교착상태가 발생했는지 탐지한다.
- 교착 상태가 탐지되었다면 복구 기법을 통해 교착상태를 복구한다.
- 이 방식은 지속적으로 확인하는 작업이 필요하기 때문에 성능 저하가 발생하게 된다.
- 대기 그래프(wait for graph)
- 각 자원 유형 마다 인스턴스가 하나가 있는 경우 자원 할당 그래프를 변형한 대기 그래프를 사용하여 교착 상태를 탐지한다.
- 자원 할당 그래프에서 자원을 제거 후 간선들을 결합하여 대기 그래프로 표현을 할 수 있다. ( a -> b)
- 대기 그래프에 사이클이 존재하면 데드락 상태이다.
- 은행원 알고리즘
- 각 자원 유형 마다 인스턴스가 여러게 있는 경우 은행원 알고리즘(Banker's Algorithm)을 사용하여 교착상태를 탐지한다.
- 각 프로세스의 자원 요청(Request) 개수를 사용
- 현재 상태가 안전 상태(safe state)인지 확인
- 불안정 상태(unsafe state)라면 교착상태라고 판단
- 각 자원 유형 마다 인스턴스가 여러게 있는 경우 은행원 알고리즘(Banker's Algorithm)을 사용하여 교착상태를 탐지한다.
4. 교착 상태 회복
- 교착 상태가 발생했다면 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제함으로써 복구를 한다.
- 프로세스 종료
- 교착상태에 있는 프로세스를 종료하는 방식
- 현대의 운영체제가 선택한 방식
- 교착 상태의 프로세스를 모두 중지
- 교착 상태가 제거될 때까지 한 프로세스씩 중지
- 자원 선점
- 교착 상태에 있는 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하여 해당 프로세스를 일시 정지시키는 방법
- 자원 선점에 있어서 다음 사항들을 고려해야 한다.
- 희생자 선택 (selection of a victim)
- 최소의 피해를 줄 수 있는 프로세스를 선택
- 롤백(rollback)
- 선점 된 프로세스를 문제 없던 이전 상태로 롤백
- 보통 가장 안전한 방법은 프로세스를 중지시키고 재시작
- 기아 상태(starvation)
- 한 프로세스가 계속 선점되어 기아상태가 되는 것을 방지
- 한 가지 방법은 우선 순위를 사용하여 선점 될때마다 프로세스 우선순위를 높이는 것
- 희생자 선택 (selection of a victim)
참고
