상호 배제를 보장하는 락인 뮤텍스, 자원의 접근을 제어하는 세마포어, 바쁜 대기 상태를 유지하는 스핀락
| 교착상태 (Deadlock)
둘 이상의 프로세스가 서로 가진 자원을 기다리면서 무한정 대기하는 상태를 말한다.
즉, 각 프로세스가 다른 프로세스가 점유하고 있는 자원을 요청하며 대기하므로, 아무런 작업도 처리되지 않는 상태다.
예시 프로세스 A가 자원 1을 가지고 있고, 자원 2를 기다리는 중이다. 동시에 프로세스 B는 자원 2를 가지고 있고, 자원 1을 기다리는 상황이다. 이 경우, 두 프로세스 모두 무한정 대기하게 된다.
| 교착 상태 발생의 4가지 조건
교착 상태가 발생하기 위해서는 다음 네 가지 조건이 모두 만족되어야 한다.
1. 상호 배제 (Mutual Exclusion) - 자원은 한 번에 하나의 프로세스만 사용할 수 있다.
2. 점유 대기 (Hold and Wait)
- 최소한 하나의 자원을 점유한 프로세스가 다른 자원을 추가로 점유하기 위해 대기하고 있어야 한다.
3. 비선점(No Preemption)
- 프로세스가 점유한 자원을 강제로 빼앗을 수 없다. 프로세스는 자발적으로 자원을 해제해야 한다.
4. 순환 대기 (Circular Wait)
- 자원과 프로세스의 집합 {P1, P2, ..., Pn)에서 P1은 P2가 점유한 자원을 기다리고, P2는 P3가 점유한 자원을 기다리고, ... Pn은 P1이 점유한 자원을 기다리는 형태의 순환 대기 상태가 존재해야 한다.
| 교착 상태 처리 방법
1.예방(Prevention) - 교착 상태 발생 조건 중 하나 이상을 만족시키지 않도록 하여 교착 상태를 원천적으로 예방하는 방법
상호 배제 조건 방지 : 일부 자원을 공유 가능하게 만들어 상호 배제 조건을 없앤다.
점유 대기 조건 방지 : 프로세스가 자원을 점유하고 있을 때 다른 자원을 요청하지 않도록 한다. ex) 프로세스가 시작하기 전에 필요한 모든 자원을 요청하고, 하나라도 할당되지 않으면 아무 자원도 할당 받지 않도록 한다.
비선점 조건 방지 : 자원을 강제로 회수하여 비선점 조건을 없앤다. ex) 프로세스가 필요한 자원을 얻지 못하면, 현재 점유하고 있는 자원을 반환하고 다시 요청하도록 한다.
순환 대기 조건 방지 : 자원에 번호를 매겨 순서대로 자원을 요청하게 하는 방법 ex) 자원 A,B,C가 있을 때, 프로세스가 A를 점유하고 있으면 B,C를 요청할 수 있지만, C를 점유하고 있으면 A,B를 요청할 수 없 게 한다.
2. 회피 (Avoidance)
- 교착 상태가 발생할 가능성을 줄이기 위해 자원 할당을 신중하게 하는 방법
대표적 알고리즘으로 은행가 알고리즘(Banker's Algorithm)이 있다. 시스템이 안전 상태를 유지하도록 자원을 할당한다. 프로세스의 자원 요청을 허용하기 전에, 요청이 이루어진 후에도 시스템이 안전한 상태인지 확인한다.
3. 탐지(Detection)
- 교착 상태가 발생했는지 주기적으로 검사하고, 교착 상태를 탐지하면 이를 해결하기 위해 조치를 취하는 방법
교착 상태를 탐지하기 위한 그래프 알고리즘을 사용하거나, 자원 할당 상태를 점검하여 교착 상태를 파악할 수 있다. 자원 할당 그래프 : 프로세스와 자우너 간의 할당과 요청 관계를 나타낸 그래프를 사용하여 교착 상태를 탐지한다. 주기적인 검사 : 운영체제가 주기적으로 자원 할당 상태를 점검하여 교착 상태가 발생했는지 확인한다.
ex) 자원 할당 그래프를 사용하여, 그래프에 사이클이 존재하는지 검사한다. 사이클이 존재한다면 교착 상태가 발생한 것이다.
4.회복(Recovery)
프로세스 종료 : 교착 상태에 있는 프로세스를 종료하여 자원을 회수 ex) 교착 상태에 있는 P1, P2, P3 중에서 P1을 종료하여 자원 A를 회수하고, 이를 P2 또는 P3에게 할당하여 교착 상태를 해소한다.
자원 선점 : 교착 상태를 해소하기 위해 일부 자원을 강제로 회수하여 다른 프로세스에 할당한다. 운영체제가 자원을 선점하여 교착 상태 프로세스를 다른 프로세스에게 할당한다. ex) 자원 A를 P1이 사용하는 동안, P2와 P3가 A를 기다리고 있어 교착 상태에 빠진 경우, os가 P1으로부터 자원 A를 선점하여 P2에게 할당하여 교착 상태를 해소한다.
기아 상태 : 자원 할당을 기다리지만 우선순위가 낮아서 자원 할당을 받지 못하는 상태 (주택 청약...)
