운영체제 - 교착상태
교착상태의 개념
> 딱 걸려서 , 오도가도 못하는 상태! (데드락 : 죽어있는 상태, 해결하지 못하는 상태)
2개 이상의 프로세스가 서로 상대방의 작업이 끝나기만을 기다리고 있는 상태
결과적으로 아무도 완료되지 못하는 상태
정상적인 상태
프로세스1 : 자원요구 > 사용 > 자원해제
프로세스2 : 자원요구(대기) > 자원 및 사용 > 해제
교착상태
프로세스1 : 자원1 요구 > 사용 > 자원2 요구(대기) ...
프로세스2 : 자원2 요구 > 사용 > 자원1 요구(대기) ...
교착상태와 기아상태의 차이
교착상태 : 서로가 서로를 막고 있는 상태 (영원히 기다릴수 밖에 없는 상황)
기아상태 : 어느 한쪽이 해소되면, 해결되는 상황
*교착상태의 특성
교착상태의 필요조건
네가지의 조건이 동시에 만족될 경우 교착상태가 발생할 수 있다. (안 할 수도 있음)
- 상호배제 조건
- 점유 대기 조건
- 비선점 조건
- 환형 대기 조건
상호배제 조건
자원이 있을 때 , 자원이 배타적인 통제권이 필요한 경우 (누군가 사용하고 있으면 다른사람은 접근못함)
적어도 하나 이상의 자원은 공동 사용될 수 없음
필요로 하는 자원을 다른 프로세스가 사용하고 있으면 대기해야함
점유대기 조건
프로세스가 이미 다른 자원을 할당받은 상태에서, 다른 프로세스가 점유하고 있는 배타적 자원을 받기 위해 대기하고 있는 상황
비선점 조건
프로세스에 할당된 자원은 그 프로세스가 사용을 마치고 스스로 반환하기 전에는 제거되지 않음.
다른 프로세스가 뺏어갈 수 없음.
환형대기
프로세스의 자원 점유 및 점유된 자원의 요구 관계가 환형을 이루며 대기
자원할당 그래프 G = ( V , E )
정점의 집합 V = P와 R의 합집합
P = {1 ... n } : n개의 프로세스
R = {1 ... m } : m개의 자원
방향 있는 간선의 집합 E = Q와 S의 합집합
Q = {(p1, r1)} 프로세스 p가 자원j를 요구함 (요구간선)
S = {(r1,p1)} 자원 r가 프로세스 p에 할당됨 (할당간선)
자원과 자원, 프로세스와 프로세스 사이의 연결은 없다
교착상태와의 관계
상호배제 조건 - 할당간선
점유 대기 조건 - 할당간선 +요구간선
비선점 조건 - 요구간선
환형 대기 조건 - 사이클
교착상태 방지
교착상태 처리 3가지
교착상태 방지
교착상태의 필요조건 중 하나라도 발생할 수 없도록 막는다.
교착상태 회피
필요한 자원의 최대량에 대한 정보를 활용하여 교착상태가 발생하지 않도록 함
교착상태 탐지 및 복구
교착상태가 발생하면 이에 따른 적절한 조치를 취하여 정상 상태로 복구
교착상태 방지
1. 상호배제 조건의 제거 -> 불가능
공유할 수 있는 자원 : 상호배제와 무관
공유할 수 없는 자원 : 반드시 상호배제 해야함
2. 점유 대기 조건의 제거
프로세스가 자원을 요청할 때, 그 프로세스는 어떤 자원도 할당받지 않은 상태여야함
방법1.
프로세스가 수행을 시작하기 전에 필요한 자원을 모두 할당 받아버림 > 자원이용률이 매우 낮아질 수 있음
방법2.
자원을 부분적으로 요청하여 할당받을 수 있도록 하되, 자원을 추가로 요청할때에는 이전에 가지고 있던 자원을 모두 해제한 후 할당받음 / 가진걸 다 버렸다가 다시 요청 -> 기아상태가 발생할 수 있다. 가지고 있던걸 내놓는 순간, 다른 프로세스가 가져가서 사용할 수 있다.
3. 비선점 조건의 제거
방법1
자원을 점유하고있는 프로세스가 즉시 사용할 수 없는 상황의 다른 자원을 요청하는 경우 점유하고 있던 자원을 해제해준다. > 기아상태 가능
방법2
프로세스가 가용하지 않은 자원 R을 요청(다른 프로세스가 사용중인 자원R을 요청중)
R이 할당된 프로세스가 다른 자원을 기다리며 대기중인지 확인
대기 중이면 대기상태인 프로세스로부터 R을 선점하여 가져오겠다. 아니면 대기
>상태를 쉽게 복구하고 보관할 수 있는 자원이 아니라면 적용 불가능
환형 대기조건의 제거
모든 자원의 유형에 일련번호를 지정하기 위해 함수 F 정의
F : R > N (R: 자원 유형의 집합 / N : 자연수)
방법1
프로세스는 자원을 일련번호 기준으로 항상 오름차순으로 요청!
f(r1) < f(r2) 여야만 r1을 가지고 있는 프로세스가 r2를 요청할 수 있음 .
방법2
프로세스 Ri를 요구할 때마다 f(Ri) <= f(Rj)인 자원 Rj는 모두 해제