운영체제 - 교착상태 정리 (방송통신대학교 운영체제)

교착상태 필요조건

• 상호배제
• 점유대기
• 비선점
• 환형대기

상호배제

• 프로세스들이 자원에 대한 배타적인 통제권을 요구
• 적어도 하나 이상의 자원은 공동 사용될 수 없음
• 즉, 필요로 하는 자원을 다른 프로세스가 점유하고 있으면 반드시 대기해야 함

점유대기

• 프로세스가 이미 다른 자원을 할당받아 배타적으로 점유하고있는 상황에서 다른 프로세스가 점유하고 있는 자원이 해제되기를 기다리는 상호아

비선점

• 프로세스에 할당된 자원은 그 프로세스가 사용을 마치고 스스로 반환하기 전에 제거되지 않음
• 즉, 다른 프로세스에 의해서는 해제되지 않음

환형 대기

• 프로세스의 자원 점유 및 점유된 자원의 요구 관계가 환형을 이루며 대기

자원할당 그래프

정점 V = P U R

P: 프로세스

R: 자원

Q(p,r): 요구간선, p가 r을 요구함

S(p,r): 할당간선, r이 P에 할당됨

• 상호배제: 할당간선
• 점유대기: 할당간선+요구간선
• 비선점: 요구간선
• 환형대기: 사이클

교착상태 처리

교착상태 방지

• 교착상태의 필요조건 중 하나라도 발생할 수 없도록 막음

교착상태 회피

• 프로세스에 필요한 자원의 최대량의 대한 정보를 활용하여 교착상태가 발생하지 않도록 함

교착상태 탐지 및 복구

• 교착상태가 발생하면 이에 따른 적절한 조치를 취하여 정상 상태로 복구

교착상태 방지

1. 상호배제 조건의 제거

• 공유할 수 있는 자원: 상호배제와 무관
• 공유할 수 없는 자원: 반드시 상호배제 해야 함
• 상호배제 조건의 제거는 불가능

2.점유대기 조건의 제거

• 프로세스가 자원을 요청할 때 그 프로세스는 어떠한 자원도 할당받지 않은 상태여야 함

1. 프로세스가 수행을 시작하기 전에 필요한 모든 자원을 한꺼번에 요구하여 할당받음 → 처리하지 않는 시간동안 리소스를 들고 있어서 자원 이용률이 매우 낮아질 수 있음
2. 자원을 부분적으로 요청하여 할당받을 수 있도록 하되, 자원을 추가로 요청할 때에는 이전에 가지고 있던 자원을 반드시 모두 해제한 후 할당받음 → 기아상태가 발생할 수 있음

3.비선점 조건의 제거

1. 자원을 점유하고 있는 프로세스가 즉시 사용할 수 없는 상황의 다른 자원을 요청하는 경우 점유하고 있던 자원을 해제 → 기아상태 발생 가능
2. 프로세스가 가용하지 않는 자원을 요청, 그 자원이 할당된 프로세스가 다른 자원을 기다리며 대기 중인지 조사, 대기중이면 대기상태인 프로세스로부터 자원을 선점하여 요청한 프로세스에 할당. 대기 중이 아니라면 요청한 프로세스는 대기 → 상태를 쉽게 보관하고 복구할 수 있는 자원이 아니라면 적용이 불가능

4.환형대기 조건의 제거

1. 프로세스는 자원을 일련번호 기준으로 항상 오름차순으로 요청
2. 프로세스가 자원 r_i를 요구할 때마다 f(r_j) ≤ f(r_i)인 자원 r_i는 모두 해제

교착상태 회피

• 프로세스의 자원 사용에 대한 사전 정보를 활용하여 교착상태가 발생하지 않는 상태에 머물도록 하는 방법
• 사전 정보: 현재 할당된 자원, 가용상태의 자원, 프로세스들의 최대 요구랑
• 프로세스의 상태 영역: 안전 상태와 불안전 상태로 나뉜다
• 안전상태: 교착상태를 회피하면서 각 프로세스에게 그들의 최대 요구량까지 빠짐없이 자원을 할당할 수 있는 상태, 안전 순서열이 존재하는 상태이다.
• 불안전상태: 교착상태가 발생할 수 있는 상태. 안전 순서열이 존재하지 않는 상태이다.

안전 순서열

• 순서 있는 프로세스 집합 <p1, p2, p3, … pn >
• 각 p_i에 대해, p_1~p_i가 가용상태인지 체크
• 현재 리소스를 투입하여 먼저 해결할 수 있는 프로세스의 순서대로 처리
• 특정 프로세스가 리소스를 요구 했을 때, 안전 순서열을 유지하지 못하면 리소스를 할당해주지 않음

예시

r: 9개의 리소스, 6개를 프로세스에 할당해주고 3개가 남음

Pa: 7개의 리소스를 요구, 현재 0개의 리소스 할당됨

Pb: 3개의 리소스를 요구, 현재 1개의 리소스 할당됨

Pc: 9개의 리소스 요구, 현재 5개의 리소스 할당됨

1. 현재 r에 남은 3개의 리소스를 이용해 해결가능한 프로세스는 Pb이기 때문에 Pb를 먼저 수행
2. Pb에 할당되어있던 리소스 1개가 반환되어 r에는 4개의 리소스가 남음. 이를 이용하여 Pc를 수행
3. Pc에 할당되어있던 리소스 5개가 반환되어 r에는 9개의 리소스가 남음. 이를 이용하여 Pa를 수행
4. 안전 순서열은 < Pb, Pc, Pa > 로 결정되며, 이 케이스는 안전상태이다.

교착상태는 불안전상태에서 발생

• 프로세스가 가용상태의 자원을 요구하더라도 안전상태를 유지하기 위해 프로세스는 대기상태가 될 수 있음

교착상태 회피 알고리즘

각 자원 유형의 단위자원이 여러 개일 경우

• 은행원 알고리즘

각 자원 유형의 단위자원이 하나밖에 없는 경우

• 변형된 자원할당 그래프

은행원 알고리즘

• 자원을 요청받으면 그 자원을 할당해 주고 난 후의 상태를 계산해서 그것이 안전상태가 보장되는 경우에만 자원을 할당
• NEED = MAX - ALLOC

안전 알고리즘

• 현재 상태에서 안전 순서열이 존재하는지 체크
• 가용한 자원을 나타내는 WORK 변수를 이용, 초기값은 AVAIL
• 각 프로세스에 FINISH 변수를 이용하여 종료 상태를 체크
• 프로세스를 순회하며, NEED가 WORK보다 작다면 수행
• O(mn^2)

이후 리소스 요구가 들어온 경우, 요구값만큼 AVAIL의 값을 줄이고, 요구한 프로세스의 ALLOC, NEED값을 갱신한 다음 안전 알고리즘을 수행

변형된 자원할당 그래프

• 선언간선이 추가
• 선언간선: 앞으로 프로세스 p가 자원r을 요구하게 될 것임

교착상태 탐지

Shoshani와 Coffman 알고리즘

• 교착상태를 체크하는 알고리즘
• NEED 대신 REQ(현 시점에 요구하는 리소스 량)를 체크한다.
• 현재 상태에서 모든 프로세스가 처리 가능하면 교착상태가 아님
• O(mn^2)

시간복잡도가 크기 때문에 자주 실행하지 않는 것이 좋다.

• 즉시 받아들일 수 없는 할당요구가 있을 때
• 정해진 시간간격 또는 CPU 효율이 일정 수준 이하로 떨어질 때

교착상태 복구

복구의 주체

• 오퍼레이터: 수작업
• 시스템: 자동적으로 복구

복구의 방법

• 교착상태 프로세스를 종료
• 교착상태 프로세스로부터 자원을 회수

프로세스 종료

• 모든 교착상태 프로세스를 종료 → 복원 비용이 큼
• 사이클이 제거될 때까지 프로세스를 하나씩 종료 → 종료 대상을 선택하기 위한 비용이 큼

자원 회수

• 사이클이 제거될 떄까지 자원들 단계적으로 선점하여 다른 프로세스들에 할당
• 고려사항: 희생자 선택, 복귀, 기아사태

복합적 접근방법

• 자원 유형에 따라 방지, 회피, 탐지 및 복구 방법 중 적절하게 사용
• 때문에 실제 교착상태 처리는 더욱 복잡함