✔️ 교착 상태 (DeadLock)란?
두 개 이상의 프로세스들이 서로가 가진 자원을 기다리며(wait) 중단된 상태이다.
즉, 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에
결과적으로 아무것도 완료되지 못하는 상태이다.
💡 예를 들어, Resource 1(자원)을 가진 Process 1(프로세스)과
Resource 2를 가진 Process 2가 있다.
이때 Process1은 Resource2를 필요로 하고, Process2는 Resource1을 필요로 한다면
두 프로세스는 서로의 자원을 얻기 위해 무한정 기다리게 되는 것이다.
✔️ 주로 언제 발생할까?
- 멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황 발생
- 한 프로세스가 자원을 요청했을 때, 동시에 그 자원을 사용할 수 없는 상황이 발생할 수 있다.
- 이때 프로세스는 대기 상태로 들어간다.
- 대기 상태로 들어간 프로세스들이 실행 상태로 변경될 수 없을 때 '교착 상태'가 발생한다.
→ 다중 프로그래밍(Multi-programming) 환경에서 흔히 발생할 수 있는 문제이다.
→ 이 문제를 해결하는 일반적인 방법은 아직 없는 상태이다.
※ 다중 프로그래밍(Multi-programming)이란?
CPU 작업과 입출력 작업을 병행하는 것이다.
다중 프로그래밍 운영체제에서 여러 개의 작업들이 수행할 준비를 갖추고 있다면,
이 작업들 중에 하나를 선택하기 위해서는 결정이 필요하다.
→ 이것이 CPU 스케줄링이다.
✔️ 데드락(DeadLock)의 발생 조건
교착상태가 일어나기 위한 필요 조건이 네 가지가 존재한다.
이는 필요 조건이므로, 네 가지가 모두 해당된다고해서 반드시 교착상태가 일어나는 것은 아니고,
일어날 확률이 생기는 것이다.
하나라도 성립하지 않으면, 데드락 문제를 해결 가능하다.
1. 상호 배제 (Mutual exclusion)
자원은 한 번에 한 프로세스만 사용할 수 있다.
- 사용 중인 자원을 다른 프로세스가 사용하려면, 요청한 자원이 해제될 때까지 기다려야 한다.
2. 점유 대기 (Hold and wait)
특정 프로세스가 점유한 자원을 다른 프로세스가 요청하고 있는(대기) 상태이다.
- 즉, 다른 프로세스에 할당된 자원을 점유하기 위해, 대기하는 프로세스가 존재해야 한다.
3. 비선점(No preemption)
다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없다.
4. 순환 대기(Circular wait) (또는 '환형 대기')
대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다. (위 그림처럼)
- 즉, 두 개 이상의 프로세스가 자원 접근을 기다릴 때, 관계가 순환적 구조이다.
✔️ 교착상태 처리
데드락의 해결법을 크게 3가지로 분류할 수 있다.
- 데드락이 발생하지 않도록 예방(prevention) 하기
- 데드락 발생 가능성을 인정하면서도 적절하게 회피(avoidance) 하기
- 데드락 발생을 허용하지만 데드락을 탐지(detechion)하여, 데드락에서 회복하기
💡 예방 (Prevention)
위 데드락 발생 조건 4가지 중 하나라도 발생되지 않게 한다.
즉, 각각의 조건을 방지(부정)하여 데드락 발생 가능성을 차단한다.
- 상호배제 부정 : 여러 프로세스가 공유 자원 사용. But, 추후 동기화 관련 문제가 발생할 수 있음.
- 점유대기 부정 : 프로세스 실행 전, 실행에 필요한 모든 자원을 할당. (대기 X)
- 비선점 부정 : 이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선 순위의 프로세스가 해당 자원을 선점할 수 있도록 한다.
- 순환대기 부정 : 자원을 순환 형태로 대기하지 않도록, 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 한다. (Ex. 모든 자원에 번호를 부여하여, 오름차순으로 자원을 요청하게 함)
🚨 이러한 방식들은 시스템 처리량이나 효율성을 떨어트리는 단점이 발생할 수 있다.
다음에 살펴볼 회피법은 보다 덜 제한적인 방법으로 해결하는 방법이다.
💡 회피 (Avoidance)
자원의 할당 상태를 감시하여 교착상태의 가능성을 피해나가는 방법
위의 '방지'와의 차이점은, 교착상태를 다르게 접근하는 것이다.
교착상태 '회피'에서는 교착상태를 자원 요청에 대한 잘못된 승인으로 판단한다.
교착상태 회피의 대표 기법은 은행원 알고리즘이 있다.
→ 은행원 알고리즘에서 운영체제는 안전 상태를 유지할 수 있는 요구만을 수락하고,
불안전 상태를 초래할 사용자의 요구는 나중에 만족될 수 있을 때까지 거절한다.
※ 안정 상태 : 시스템의 프로세스들이 요청하는 모든 자원을
데드락을 발생시키지 않으면서도, 차례로 모두에게 할당해 줄 수 있는 상태.
(안전순서열 존재)
(안전순서열 : 데드락이 발생하지 않는 순서를 찾을 수 있다면...)
※ 불안정 상태 : 안전순서열이 존재하지 않은 상태이다.
교착상태는 불안전상태에서만 발생한다.
하지만 불안정상태라고 무조건 교착상태가 발생하는 것은 아니다.
🔑 은행원 알고리즘 (Banker's Algorithm)
특징
- 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데서 유래함.
- 프로세스가 자원을 요구할 때, 시스템은 사원을 할당한 후에도 안정상태로 남아있게 되는지 사전에 검사하여 교착상태를 회피한다.
- 안정상태면 자원 할당, 아니면 다른 프로세스들이 자원을 해지할 때까지 대기한다.
단점
- 할당할 수 있는 자원의 수가 일정해야 한다.
- 사용자 수가 일정해야 한다.
- 항상 불안정 상태를 방지해야 하므로, 자원 이용도가 낮다.
- 최대 자원 요구량을 미리 알아야 한다.
- 프로세스들은 유한한 시간 안에 자원을 반납해야 한다.
→ 즉, 한마디로 매우 복잡하고 어렵다. 그래서 현재 채택하고 있는 방식이 아니다.
💡 탐지(Detection) 및 회복(Recovery)
시스템이 데드락이 발생할 수 있으니, 여기에서 회복하기 위해 데드락을 탐지하고, 회복하는 알고리즘을 사용한다.
위 두 방법은 사전에 교착상태를 일어나지 않도록 하는 방법이지만,
탐지 및 회복 방법은 교착상태가 일어나는 것을 허용한다.
그 대신, 교착상태가 일어났을 때 이를 인지하고 복구를 해야 한다.
- 탐지 기법 : 자원 할당 그래프를 통해 교착 상태를 탐지
- 지속적으로 교착상태를 확인하는 작업이 필요하기 때문에 오버헤드(성능 저하)가 발생하게 된다.
- 회복 기법 : 교착 상태 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법
- 프로세스 종료 방법
- 교착 상태의 프로세스를 모두 중지
- 교착 상태가 제거될 때까지 하나씩 프로세스 중지
- 자원 선점 방법
- 교착 상태의 프로세스가 점유하고 있는 자원을 선점해, 다른 프로세스에게 할당 (해당 프로세스 일시정시 시킴)
- 우선 순위가 낮은 프로세스나 수행 횟수가 적은 프로세스 위주로 프로세스 자원을 선점
- 프로세스 종료 방법
💡 무시
교착상태에 대한 아무런 조치를 하지 않는 것.
교착상태의 필요조건 4가지를 모두 만족하더라도 교착상태가 반드시 일어나는 것이 아니라고 했듯이,
교착상태는 매우 드문 상황이다.
그러므로 이를 위해 오버헤드를 감수하는 것이 비효율적인 환경도 존재한다.
✔️ 기아 상태
기아상태(Starvation)이란, 여러 프로세스가 부족한 자원을 점유하기 위해 경쟁할 때,
특정 프로세스가 영원히 자원 할당이 되지 않는 경우이다.
✔️ 기아상태 해결 방법
- 우선순위를 변경한다.
- 우선순위를 수시로 변경하거나,
- 오래 기다린 프로세스의 우선순위를 높여주거나,
- Queue를 사용한다.
✔️ 정리 겸 예상 질문
Q. 데드락(교착 상태)가 무엇인가? 발생 조건에 대해 말해보시오.
A. 데드락이란, 두 개 이상의 프로세스들이 서로가 가진 자원을 기다리며 중단된 상태를 의미한다.
교착 상태의 발생 조건은 4가지가 있다.
상호 배제, 점유 대기, 비선점, 환형대기가 있다.
상호배제는 한 프로세스가 자원을 독점하고 있으며, 다른 프로세스들은 접근이 불가하다.
점유 대기는 자원을 가진채 다른 자원을 기다리는 것이다.
비선점은 다른 자원을 강제로 가져올 수 없는 것이고,
순환대기는 그 구조가 순환을 이루는 것이다.
Q. 데드락의 해결 방법은?
A. 예방, 회피, 복구, 무시 방법이 있다.
예방은 데드락 발생 조건 4가지 중 하나라도 만족시키지 않게 하는 것이고,
회피는 데드락이 발생하지 않도록 애초에 자원을 잘 분배하는 알고리즘을 사용하는 것이다. 회피의 대표적인 예로는 은행원 알고리즘이 있다.
복구는 데드락을 허용하고 주기적으로 데드락이 일어났나 검사하고 복구시키는 것이고,
무시는 데드락이 안 일어날 것이라고 생각하고 무시하는 것이다.
Q. 은행원 알고리즘이란?
A. 데드락의 회피에 사용하는 대표적인 알고리즘이다.
교착상태에 빠질 가능성이 없는 요구만을 수락하고,
교착상태에 빠질 가능성이 있는 사용자의 요구는 나중에 만족할 수 있을 때까지 계속 거절하는 것이다.
출처
- https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Operating%20System/DeadLock.md
- https://ko.wikipedia.org/wiki/%EA%B5%90%EC%B0%A9_%EC%83%81%ED%83%9C
- https://chanhuiseok.github.io/posts/cs-2/
- https://cocoon1787.tistory.com/858
'CS > 운영체제' 카테고리의 다른 글
| [운영체제] 세마포어(Semaphore) & 뮤텍스(Mutex) (1) | 2023.02.03 |
|---|---|
| [운영체제] 동기화(Synchronization)와 경쟁상태(Race Condition), 임계영역(Critical Section) (0) | 2023.02.02 |
| [운영체제] CPU 스케줄링 알고리즘 (0) | 2023.02.01 |
| [운영체제] PCB & Context Switching (0) | 2023.01.27 |
| [운영체제] 시스템 콜(System Call) (0) | 2023.01.26 |