교착상태 : 여러 개의 프로세스가 서로 상대방의 작업이 끝나기만 기다리고 있어 어느 쪽도 진행이 안 되는 상태
기아상테 : 특정 프로세스의 우선 순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태
교착상태의 필요조건 : 상호배제, 점유대기, 비선점, 환형대기
네 가지 조건이 동시에 만족될 때 교착상태 발생이 가능하다.
1. 상호배제
- 프로세스가 자원에 대한 배타적인 통제권을 요구
- 여러 프로세스에 의해 사용 불가능하다.
- 필요로 한다면 대기한다.
2. 점유대기
- 이미 한 자원을 할당 받아 점유하고 있는 상황에서 다른 프로세스가 점유하고 있는 또 다른 자원을 요구하여 해제되기를 기다리는 상황
- 즉 자원을 점유한 상태로 대기한다.
3. 비선점
- 프로세스 할당된 자원은 그 프로세스가 사용을 마치고 반환하기 전까지 해제되지 않는다.
- 타인에 의해 해제되지 않는다.
4. 환형대기
- 서로 점유를 원한다.
자원 할당 그래프 G = (V,E)
V: 정점의 집합
E : 방향 있는 간선읩 집합
표현 방법
그래프 예시
요구간선 : 빨강선 : 프로세스 p가 자원 r을 요구
할당간선 : 파랑선 : 자원 r이 프로세스 p에 할당
자원할당 그래프를 보고 교착상태에 있는지 간단하게 확인하는 법은
싸이클을 확인하면 된다.
이런식으로 싸이클을 형성할 경우
교착상태가 발생 할 수 있다.
교착상태 처리 기법
1. 교착상태 예방 : 네 가지 필요조건 동시에 만족되는 것을 피하게 만든다.
- 상호배제 조건 제거 으로는 교착 상태 예방은 불가능하다
- 공유할 수 있는 자원 -> 상호배제가 필요없다
- 공유할 수 없는 자원 -> 상호배제가 필요하다 (프린터)
- 점유대기 조건 제거
- 1. 자원을 점유 했을때 대기하지 않아야한다 -> 처음에 한 번에 요구하여 할당 받는다.
- 2. 대기할 때 점유하고 있지 않는다-> 새로운 자원을 요구할 때 할당 받은 자원 모두 해제한다.
- 점유 도중 해제할 수 없는 자원에는 적용 불가하다.
- 비선점 조건 제거
- 자원의 특성에 따라 불가능한 경우도 있다 (프린터)
- 다른 프로세스가 대기할 가능성을 줄인다.
- 점유대기 상황이 발생하면 할당받았던 자원을 모두 해제한다 (프린터 같은건 불가능)
- 환형대기 조건 제거
- 모든 자원에 일렬번호를 저장하고, 오름 차순으로 정렬한다. f(ri) < f(rj) 를 만족해야 한다.
- 프로세스가 자원을 요구할 때 그보다 일렬번호가 작은 자원만 점유하도록 한다.
- 점유대기 중인 프로세스는 점유 중인 자원의 일렬번호보다 대기 중인 자원의 일렬번호가 크다.
- 문제점 :
- 자원의 일렬번호 설정이 어렵다
- 오름차순 못 지키면, 점유자원 해제 필요하나, 적용 불가한 자원이 존재한다.
1. 교착상태 회피 : 프로세스의 자원 사용에 대한 사전 정보를 활용해 교착상태가 발생하지 않는 상태에 머물도록 하는 방법
사전정보 :
- 현재 할당된 자원
- 가용상태의 자원
- 프로세스들의 최대 요구량
안전 상태(Safe State): 시스템이 교착 상태를 일으키지 않으면서 각 프로세스가 요구한 최대 요구량만큼 필요한 자원을 할당해 줄 수 있는 상태. 안전순서열이 존재해야 한다.
불안전 상태(Unsafe State): 안전순서열이 존재하지 않는 상태.
안전순서열 ??
각 p(i) 에 대하여 p(i) 가 추가로 요구할 수 있는 자원의 양이 현재 가용상태의 자원으로 충당되거나 혹은 여기 p(j) 에 할당된 자원까지 포함하여 충당 가능한 경우
즉 p(3) 가 추가로 요구할 수 있는게 70개가 더 필요한데 가용할 수 있는게 10개이다.
p(1),p(2) 에서 이미 할당된 값을 가져올 수 있을때 p(3)는 문제가 없다고 한다.
예를 들어
이런 상태이고
p(2) 에 1개, p(3)에 5개를 할당한 상태이면
p(1) 은 5개가 필요하고
p(2) 은 1개가 필요하고
p(3) 은 3개가 더 필요하다.
하지만 r 에는 할당할 수 있는게 2개 밖에 없다. 그럼 p2에게 먼저 1개를 할당해 안전순서열에 하나 추가해주고
그 다음은 사용할 수 있는게 총 3개니깐 p3 그러면 11개 사용가능 하니깐 p1
그러면 <p2, p3, p1> 이 된다.
근데 만약에 p1 에게 1개를 처음에 할당한 상태로 r이 1개 이면??
바로 불안전상태가 된다.
그래서 이때 p1 이 r에게 1개를 요구를 했지만. 1개를 할당하지 않은 상태 이 상태가
교착상태 회피 이다.
그럼 이걸로 본 결론은
교착상태는 불안전 상태에서만 가능하고.
항상 안전상태를 유지해야만 하며
프로세스가 가용상태 자원을 요구하더라도 프로세스는 대기상태가 될 수 있다.
하지만
회피하기 위해서 현재 가용할 수 있는 자원을 사용 안 하기 때문에
자원 이용율은 낮아질 수 있다.
교착상태 회피 알고리즘
1. 각 자원의 단위자원이 한 개 밖에 없는경우
-> 변형된 자원 할당 그래프
- 자원 정점에 표시하던 단위자원의 개수제거 즉 1개 밖에 없다.
- 선언간선 추가
- p1, p2 가 r2를 언젠가 요구할 수 있다.
- p가 r을 요구한다.
- 점선으로 표시한다.
자원을 요구 받으면 해당 선언 간선(빨강) 을 요구 간선으로 변경한다.
그 요구간선을 할당간선으로 변환해도 사이클이 생기지 않는 경우에만 자원을 할당하고 할당간선으로 변환한다.
2. 각 자원의 단위자원이 여러 개일 수 있는 경우
-> 은행원 알고리즘 : 자원을 요구 받으면 그 자원을 할당해주고 난 후의 상태를 계산해서 그것이 안전상태인지 확인한다.
즉 할당하기 전에 안전상태인지 확인을 하고 안전상태이면 자원을 할당한다.
Max : 최대요구
Alloc: 할당자원
Need : 추가요구
Avail : 가용자원
교착 상태 탐지 및 복구
사후 처리
1.교착상태 탐지
- 주기적으로 상태 조사 알고리즘 수행 (Shoshani와 Coffman 알고리즘)
Shoshani와 Coffman 알고리즘
시간 복잡도 : O(mn^2)
수행시점 : 즉시 받아들일 수 없는 자원요구가 있을때, 정해진 시간간격, CPU 효율이 일정 수준 이하로 떨어질때
2. 교착상태 복구
복구의 주체 : 오퍼레이터 : 수작업
운영체제: 자동 복구
복구 방법:
- 교착상태 프로세스 종료
- 단점: 진행했던 내용에 대한 복원비용이 큼
- 사이클이 제거될 때 까지 교착상태 프로세스 하나씩 종료
- 단점 : 종료 대상을 선택하지 위한 비용 매 프로세스 종료 후 교착상태 재확인을 위한 비용
- 교착상태 프로세스가 할당받은 자원을 해제
- 사이클이 제거될때 까지 할당된 자원을 단계적으로 선점하여 다른 프로세스들에 할당
- 프로세스와 자원 선택 기준
- 프로세스 진척도, 사용 중인 자원 수 등
- 복귀 시점도 제반 요소 고려하여 결정
- 기아상태 빠지지 않도록 복구 횟수 고려
댓글