쉽게 말해, 프로세스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) 교착상태 예방 - 결론
교착상태 예방 방식으로는 거의 불가능한 가까운 접근 방법으로 보면된다.
** 회피 또는 이미 발생한 교착상태에 대해서 탐지 및 복구 방식으로 해결을 해야 한다고 보면 됨. **
