[운영체제] 6강 - 교착상태(1)

✅ 1. 교착상태의 개요

(1) 프로세스의 자원 사용 절차

• 프로세스의 자원 사용 절차: 요구, 사용, 해제 순으로 자원을 사용함.
• 쉽게 말해, 프로세스1이 자원을 요구하고, 자원을 획득하게 되어 사용중에 프로세스 2가 자원을 요구하게 되면 프로세스 2의 자원 요구는 대기상태로 들어가게 된다.
• 이후, 프로세스 1의 자원 사용이 모두 완료되어 해제가 되면, 프로세스 2의 요구가 대기 상태에서 사용으로 바뀌며, 사용됨.

(2) 교착상태(deadlock) 란?

• 교착상태: 서로 가지고 있는 자원을 요구하며, 줄 때 까지 서로 무한으로 대기를 하는 상태를 의미함.
• 프로세스1: 자원 1을 가지고 사용중에 자원 2요구
• 프로세스2: 자원 2를 가지고 사용중에 자원 1요구
• 이 상황에서 자원 1이나 2가 해제가 되어야 대기 상태가 끝나고 자원을 받아서 프로세스1이나 2가 처리가 가능해짐.
• ** 즉, 서로 가지고 있는 자원을 요구하며 줄 때 까지 서로 무한으로 대기를 하는 상태를 교착상태라고 부름. **

(3) 교착상태와 기아상태 차이

• 교착상태: 어느 누구도 더 이상 직진을 못하고, 멈춰 있는 상태 즉, 더 이상의 해결이 불가능한 상태를 의미할 수 있음.
• 기아상태: 좌우로 끊임없이 가는 차들이 있다고 가정하면, 위 또는 아래에서 들어오는 차는 진입이 막혀 기아상태가 될 수 있지만, 시간이 지남에 따라 좌우로 들어온 차들이 안들어올 수 있기 때문에 해결이 가능한 상태임.

---

✅ 2. 교착상태의 특성

(1) 교착상태 - 필요조건

• 교착상태 필요조건: 위의 상호배제, 점유대기, 비선점, 환형대기 4가지 조건이 존재할 때 교착상태가 발생 할 수 있다는 의미임.
• ** 즉, 4개 다 만족해야만 교착상태가 발생 가능한 상태이지 그렇다고 무조건 교착상태가 발생하지는 않음. **

(2) 상호배제(mutual exclusion) 조건

• 상호배제 조건: 프로세스 1이 자원 1을 사용 중에 프로세스 2가 자원 1을 요청한 경우 자원1이 임계영역에서 실행중이라 동시에 사용이 불가능한 자원 조건을 가지며, 프로세스 2가 자원 1을 받을 때 까지 대기하면 상호배제 조건에 성립한다고 함.

(3) 점유대기(hold and wait) 조건

• 점유대기 조건: 프로세스가 자원을 할당받아 점유하고 있는 상태에서 다른 프로세스가 점유하고 있는 자원을 요구하며, 대기하는 상황이면, 점유대기 조건이 성립한다고 봄.
• 쉽게말해, 프로세스가 자원을 점유한 상태에서 다른 프로세스가 사용 중인 자원을 요구하며 대기중인것임.
• ** 핵심은 자원을 들고 있고 또 다른 자원을 달라고 하는 상태가 핵심임. **

(4) 비선점(no preemption) 조건

• 비선점 조건: 자원을 가진 프로세스가 스스로 반납하기 전까지 절대 못 뺏으며, 다른 프로세스는 기다릴 수밖에 없을 때 비선점 조건이 성립한다고 보며, 교착상태의 필요조건 중 하나임.
• 반대로 선점이라면 여러 프로세스가 서로가 사용중인 자원을 뺏어올 수 있음.
• ** 즉, 할당된 자원은 본인을 제외한 타의에 의해서는 해제되지 않고 계속 점유를 하고 있는 상태의 조건을 말하는 것임. **

(5) 환형대기(circular wait) 조건

• 환형대기 조건: 프로세스간 점유하는 자원을 서로가 가지고 있는 자원을 요구하는 경우에 환형을 이루며 대기하게 되는 상황이 환형대기 조건에 성립이 되었다고 봄.

(6) 자원할당 그래프

• 교착상태가 되기 위한 필수조건 4가지를 자원할당 그래프를 통해서 시각적으로 명확하게 볼 수 있음.
• 자원할당 그래프: 프로세스와 자원 사이의 관계를 그래프로 표현해서 교착상태를 분석해주는 도구로 볼 수 있음.
• 쉽게말해, 누가 어떤 자원을 가지고 있고, 누구를 기다리는지 시각적으로 표현한 그래프임.
• P 는 n개의 프로세스, R은 m개의 자원을 의미한다.
• Q 는 프로세스(P)가 자원(R)을 요구한다는 의미이며, 요구간선으로 표시가 됨.
• S 는 자원(R)이 프로세스(P)에 할당이 되어있다는 의미이며, 할당간선으로 표시가 됨.
• ** 또한, 자원은 디스크, 프린터 등 다양한 자원이 존재하기 때문에 r1, r2, r3 등으로 표현하며, 디스크의 자원이 10개가 될 수도 아니면 프린터의 자원이 5개가 될 수도 있는 여러개가 존재 할 수 있기 때문에 단위 자원의 개수(K)를 표기함. **

• 정점의 집합: P에는 프로세스 집합으로 3개가 존재하며, R에는 자원 집합으로 3개가 존재함.
• 방향 있는 간선의 집합: 요구간선 집합 Q는 빨간색 간선으로 표시하며, 할당간선 집합 S는 파란색 간선으로 표시함.
• r3자원의 개수는 2개라는 의미에서 위에 2를 표시함.

• 프로세스와 자원의 관계는 계속적으로 변화하기 때문에 자원할당 그래프 또한, 계속해서 변화되어야 함.
• 즉, 위의 해당 그래프는 계속해서 변하며, 현재 상태의 그래프가 될 수 있음.
• ** 쉽게말해, 요구간선 (p2, r3)가 추가된 경우 빨간색 화살표로 p2 는 r3에게 자원을 요구하게 된다. 이때, r3는 p3에게 자원을 빌려주고 있지만, r3의 자원의 개수는 2개이므로, p2에게 자원을 빌려줄 수 있기 때문에 화살표는 요구간선(빨간색)에서 할당간선(파란색)으로 r3 -> p2 로 자원에서 프로세스로 할당간선으로 바뀌게 되는 것이다.  **
• 이와 같이 자원할당 그래프로 프로세스와 자원간의 할당 및 자원 요구에 대한 그래프로써 표현이 가능함.

(7) 자원할당 그래프 - 교착상태의 필요조건 표현

• 자원할당 그래프에서는 교착상태의 필요조건 4가지가 모두 표현이 가능함.
• 상호배제: 하나의 자원은 하나의 프로세스에게만 빌려줄 수 있는 조건으로, 하나의 할당간선으로 표현이 가능함. 예를들면, r1 이 p1 에게 할당간선(파란색)을 할당해주면 다른 프로세스에게 더 이상 자원을 빌려 줄 수 없으므로, 조건 충족이 됨.
• 점유대기: 프로세스가 자원을 점유한 채로 또 다른 자원을 요구하는 것이므로, 그래프상에서 할당간선과 요구간선의 연결로 점유대기를 표현이 가능함.
• 비선점: 다른 프로세스가 자원을 사용중이라면 뺏어올 수 없다는 조건이며, 요구간선(빨간색)으로 표현이 가능하며, 해당 요구간선은 요구는 하고 있지만 대기하고 있다는 의미를 가지므로, 비선점을 표현 할 수 있음.
• 환형대기: 서로 가진 자원을 요구하며, 해제하지 않는 모습이 환형으로 대기하는 모습을 의미함. 그래프이기 때문에 사이클로 표현이 가능함.

• 단, 필요조건 4가지를 충족한다고해서 교착상태가 반드시 발생하는 것은 아니며, 발생 가능성이 생긴다는 의미임.
• 사이클이 없는 경우: 교착상태 없음
• 사이클이 있는 경우: 점유대기 조건에 의해 교착상태 발생 가능성이 있음.
• 또한, 위의 예시 같은 경우에는 교착상태가 맞는 상황임.

• 위의 예시는 사이클이 존재한다고해서 모두 교착상태가 아닌 상태를 나타내는 예시임.
• ** 이유는, p1과 p2가 각각 r1과 r2의 자원을 사용하면서 사이클이 되어, 교착상태로 볼 것 같지만 다른점은 r1 의 자원의 개수는 2개이며, p4가 해당 자원 r1의 자원을 할당받고 있으므로, p4가 자원을 다 사용하고 해제한다면 p2 는 r1의 자원을 할당받아 사용하기 때문에 교착상태가 아니게 된다. **

(8) 교착상태 - 처리기법

• 교착상태 처리기법: 교착상태가 발생하게 된다면 생기지 않도록 도와주는 기법을 의미함.
• 교착상태 예방: 교착상태의 네 가지 조건이 만족이 되어야지만 교착상태의 가능성이 생기기 때문에 만족되는 것을 피하여 교착상태가 발생하지 않도록 하는 방법을 의미함.
• 교착상태 회피: 프로세스들이 필요한 자원의 양을 사전에 미리 체크를 해두고 이러한 정보를 통해서 교착상태에 발생할 위험을 미리 할당을 하지 않는 회피 방법임.
• 교착상태 탐지 및 복구: 이미 교착상태로 들어간 프로세스들이 존재 할 때 이것을 탐지하고 복구하는 방식을 의미함. 앞선 예방과 회피는 교착상태가 생기지 않도록 미리 처리하는 방식이지만, 이 방식은 교착상태가 발생했다면 어떻게 처리를 할건지 다루는 방식임.

---

✅ 3. 교착상태 예방

• 교착상태 예방: 교착상태의 네 가지 조건을 만족하지 못하도록 피하여 교착상태가 발생하지 않도록 하는 방법임.

(1) 상호배제 조건 제거

• 상호배제 조건 제거: 상호배제를 제거하기 위해서는 임계영역을 둘 만큼 데이터의 일관성 보장이 중요한 작업을 제외한 읽기 전용 파일 등과 같이 read 작업만 한다면 상호배제 조건이 제거되기 때문에 교착상태를 미연에 해결 할 수 있음.
• 공유할 수 있는 자원: 임계영역이 없는 읽기 작업만 하는등의 일관성을 보장하기 때문에 상호배제 필요없음.
• 공유할 수 없는 자원: 프린터같은 경우에는 한 프로세스가 프린터를 할 때 다른 프로세스는 못하는 임계영역이 생기므로, 상호배제가 반드시 필요함.
• ** 공유할 수 없는 자원이 반드시 존재하기 때문에 상호배제 조건은 무조건적으로 제거가 될 수 없기 때문에 상호배제 조건 제거로는 교착상태 예방은 불가능이라고 보면 된다. **

(2) 점유대기 조건 제거

• 점유대기 조건: 프로세스가 자원을 할당 받아 사용 중에 다른 프로세스가 사용 중이던 자원을 요청하며, 기다리는 상황임.
• 점유대기 조건 제거: 점유대기 조건에 대해서 제거를 하려면, 자원을 점유했을 때 대기를 하지 않아야 하거나 대기를 할 때 자원을 점유하고 있지 않아야 점유대기 조건에 부합하게 되는 것임.
• 자원을 점유했을 때 대기하지 않아야 함: 프로세스가 앞으로 필요한 모든 자원을 처음에 한꺼번에 할당을 해줘버리는 방법이 있지만, 자원이용률이 낮아질 수 있고 기아상태가 발생 할 수 있다는 단점이 있음.
• 즉, 하나의 프로세스가 많은 자원을 차지하고 있고, 프로세스가 자원을 사용안하고 있더라도 점유를 하고 있는 문제가 있음.
• 대기할 때 자원을 점유하고 있지 않아야 함: 새로운 자원이 필요해서 요구를 할 때 할당받았던 자원들을 모두 해제버리는 방법이 있지만, 점유 도중 해제할 수 없는 자원에는 적용이 불가능하다는 단점이 있음.
• 즉, 프린터와 같은 점유 도중에 해제할 수 없는 자원이 존재하기 때문에 해당 방법은 적용이 불가능한 방법으로 볼 수 있음.

(3) 비선점 조건 제거

• 비선점 조건 제거: 프로세스가 자원을 사용하고 있을 때 다른 프로세스가 해당 자원을 사용하지 못하도록 하는 것을 비선점이라고 하는데 선점이 가능하도록 바꾸는 것과 다른 프로세스가 대기할 가능성을 줄이는 것으로 생각 할 수 있음. 
• 선점이 가능하도록 해야 함: 자원의 특성에 따라 불가능한 경우 존재함.
• 즉, 프린터와 같은 자원은 선점을 하고 모든 작업을 다 수행하고 자원을 반납해야 하는데, 중간에 다른 프로세스가 선점을 해버리면 데이터의 일관성 등이 깨질 수 있는 문제가 있기 때문에 사실상 불가능한 방법임.
• 다른 프로세스가 대기할 가능성 줄이기: 프로세스가 점유대기 상황이 되면, 자신이 할당받은 모든 자원을 해제함으로써, 교착상태를 막는 방법이지만 위와 동일하게 프린터 같은 자원에는 적용이 불가능해서 사실상 불가능한 방법임.
• 결론은 비선점 조건 제거는 말이 안되는 방법으로 보면 됨.

(4) 환형대기 조건 제거

• 환형대기 조건: 프로세스간 점유하는 자원을 서로가 가지고 있는 자원을 요구하는 경우에 환형을 이루며 대기하게 되는 상황
• 모든 자원에 일련번호를 지정: 자원에 서열(번호, 일련번호)을 정해주고, 번호에 맞게 자원을 획득하도록 강제함으로써 환형 대기를 방지하는 방식임.
• 즉, 함수를 통해 자원 집합에 따라서 자연수 집합을 부여하는 느낌이며, 자원의 유형이 다를 때 일련번호 또한 다르게 세팅이됨.

1. 환형 대기가 발생 이유 (문제 상황)
- 프로세스 A: 자원 **[스캐너]**를 가진 채로 **[프린터]**를 기다림.
- 프로세스 B: 자원 **[프린터]**를 가진 채로 **[스캐너]**를 기다림.
- 결과: 서로 양보 안 함 -> 원형(Cycle) 발생 -> 교착상태

2. 일련번호가 해결하는 방법 (해결책)
- (1) 자원에 일련번호 매핑 (1번: 스캐너, 2번: 프린터)
- (2) 프로세스 A: 1번(스캐너)을 빌림 -> 2번(프린터)을 요청 (가능)
- (3) 프로세스 B: 2번(프린터)을 먼저 빌린 상태에서 1번(스캐너)을 요청 (불가능)
- 결국 사이클은 발생하지 환형대기 조건을 제거 할수는 있음.

• 방법1: 자원의 일련번호를 활용하여, 일련번호가 항상 오름차순이 되도록만 요구할 수 있도록 하는 방법이다.
• ** 쉽게말해, 프로세스가 자원A(일련번호:3) 가지고 있는 상태에서 자원C(일련번호:4) 가 기존에 가지고 있는 자원보다 일련번호가 높기 때문에 빌릴 수 있으며, 만약 자원C의 일련번호가 3 미만인경우 자원을 빌리는 것을 불가능함. **
• 이와 같은 방식으로 환형대기 조건은 제거할 순 있지만, 문제는 r1(3), r2(5), r3(7), r4(9) 이런식으로 r4(9) 의 자원을 사용 중에 있을 때 r1(3) 을 다시 사용하려고 한다면 일련번호가 낮기 때문에 사용이 불가능하다는 큰 문제점이 있음.
• ** 결론은 이 방법만으로는 사실상 불가능하다고 보는게 맞음. **

• 방법2: 방법1의 낮은 일련번호는 무조건 빌릴 수 없다는 문제점을 개선한 방식이며, 점유중인 자원에서 새롭게 요구되는 자원의 일련번호보다 작은 자원은 자진 반납을 하는 방식이다.
• 예시: r1(1), r2(3), r3(7) 에서 r4(5) 를 빌리는 경우 r3(7) 을 자진반납하고 r4(5) 를 빌리는 것임.

• 환형대기 조건 제거: 방법1,2 를 통해서 빌리고 있는 자원보다 일련번호가 큰 자원을 빌리는 오름차순으로 하면 환형대기 발생이 불가능해져 결국엔 환형대기 조건은 제거 할 수 있음.
• 문제점: 프로세스마다 요구순서가 달라 자원의 일련번호 설정이 어렵고, 방법2와 같이 자원의 일련번호가 낮은 자원을 빌릴 때에는 보다 큰 자원은 반납을 해줘야하는데, 만약 프린터와 같이 반납이 불가한 자원은 분명히 존재하기 때문에 환형대기 조건을 제거하는 건 사실상 불가능에 가깝다고 봐야함.

(5) 교착상태 예방 - 결론

• 교착상태 예방 방식으로는 거의 불가능한 가까운 접근 방법으로 보면된다.
• ** 회피 또는 이미 발생한 교착상태에 대해서 탐지 및 복구 방식으로 해결을 해야 한다고 보면 됨. **