교착상태란
세마포어 사용 예
교착상태
- 차단된 프로세스 집합의 경우 각 프로세스는 리소스를 보유하고 있으며 집합의 다른 프로세스가 보유한 리소스를 획득하기 위해 대기
교착 상태 특성화
시스템 모델링
- 프로세스: P1, P2, … Pn.
- 자원 유형: R1, R2, …, Rm
- CPU 주기, 메모리 공간, I/O 장치, 파일 등.
- 각 리소스 유형의 Ri에는 Wi 인스턴스가 있다.
- 각 프로세스는 다음과 같이 리소스를 활용
네 가지 조건이 동시에 유지되면 교착 상태가 발생
- 상호 배제(Mutual exclusion)
- 한 번에 하나의 프로세스만 리소스를 사용 가능
- 점유 및 대기(Hold and wait)
- 하나 이상의 리소스를 보유한 프로세스가 다른 프로세스에서 보유한 추가 리소스를 획득하기 위해 대기 중
- 비선점(No preemption)
- 리소스는 보유 프로세스에 의해서만 자발적으로 해제 가능
- 순환 대기(Circular wait)
- P0, P1, …, P0개의 대기 프로세스 집합
- P0이 P1이 보유한 리소스를 대기
- P1이 P2가 보유한 리소스를 대기
- ...,
- Pn–1은 Pn이 보유한 리소스를 대기
- Pn이 P0이 보유한 리소스를 대기
리소스 할당 그래프
- V는 두 가지 유형으로 분할
- P = {P1, P2, …, Pn}, 시스템의 모든 프로세스 집합
- R = {R1, R2, …, Rm} 시스템의 모든 리소스 유형 집합
- E도 두 가지 유형으로 분할
- Pi → Rj : 요청
Rj → Pi : 할당
예
Pi가 Rj의 인스턴스를 요청
Pi는 R의 인스턴스를 보유
리소스 할당 그래프를 사용한 교착 상태 예제
- 그래프에 주기가 없는 경우,
- 그래프에 주기가 포함된 경우,
- 리소스 유형당 하나의 인스턴스만 있는 경우 교착 상태
- 리소스 유형당 여러 인스턴스가 있는 경우 교착 상태일 가능성
교착 상태 처리 방법
예방
- 시스템이 교착 상태에 빠지지 않는다.
- 네 가지 조건 중 하나 이상을 유지할 수 없다.
회피
- 시스템이 교착 상태에 빠지지 않는다.
- 각 프로세스가 리소스를 어떻게 활용할 것인지에 대한 사전 정보가 필요
탐지 및 복구
- 시스템이 교착 상태에 빠졌다가 복구될 수 있다.
교착 상태 방지
네 가지 조건 중 하나 이상을 유지할 수 없다.
상호 배제(Mutual Exclusion)
점유 및 대기(Hold and Wait)
- 프로세스가 실행을 시작하기 전에 모든 리소스를 요청하고 할당 가능
비선점(No Preemption)
- 일부 리소스를 보유하고 있는 프로세스가 즉시 할당할 수 없는 다른 리소스를 요청하면 현재 보유한 모든 리소스 해제
- 프로세스는 요청 중인 새 리소스뿐만 아니라 이전 리소스도 되찾을 수 있을 때만 다시 시작
순환 대기(Circular Wait)
- 모든 리소스 유형의 총 순서를 지정하며, 각 프로세스에서 열거 순서가 증가하는 리소스를 요청
교착 상태 회피
교착 상태 회피 알고리즘
- 프로세스가 사용 가능한 리소스를 요청할 때 시스템은 즉시 할당이 시스템을 안전한 상태로 유지하는지 여부 결정
- 시스템이 각 프로세스에 리소스를 어떤 순서로(최대치까지) 할당할 수 있지만 교착 상태를 피할 수 있다면 상태는 안전
- 시스템에 몇 가지 추가적인 사전 정보가 있어야 한다.
시스템이 안전한 상태(safe state)인 경우,
시스템이 안전하지 않은 상태(unsafe state)인 경우,
리소스 할당 그래프
- 클레임 에지 Pi → Rj
- Pj는 Rj를 요청할 수 있다.
- 점선으로 표시
- 클레임 에지가 요청 에지로 변환
- 요청 에지가 할당 에지로 변환
- 할당 에지가 클레임 에지로 다시 변환
[참고]
- 리소스 유형의 인스턴스가 여러 개일 경우 banker 알고리즘을 사용
안전하지 않은 상태 예제
주기 없음 -> 안전 -> 허가 / 주기 -> 안전하지 않음 -> 거부
교착 상태 감지 및 복구
시스템이 교착 상태로 전환되도록 허용
탐지 알고리즘
- 그래프에서 주기적으로 주기를 검색하는 알고리즘을 호출
- [참고] 리소스 유형의 인스턴스가 여러 개인 경우 더 복잡한 알고리즘을 사용
복구 구성표
- 프로세스 종료
- 교착 상태의 모든 프로세스를 중단
- 교착 상태 주기가 제거될 때까지 한 번에 하나의 프로세스를 중단
- 자원 선점
- 프로세스에서 일부 리소스를 선점하고 교착 상태 주기가 중단될 때까지 이러한 리소스를 다른 프로세스에 제공
요약
- 교착 상태
- 프로세스가 대기 프로세스로 인해 발생하는 이벤트를 무한정 기다리는 상황
- 네 가지 조건이 동시에 유지될 경우 발생
- 상호 배제(mutual exclusion)
- 점유 및 대기(hold and wait)
- 비선점(no preemption)
- 순환 대기(circular wait)
- 교착 상태 방지
- 네 가지 조건 중 하나 이상을 유지할 수 없도록 한다.
- 시스템이 안전하지 않은 상태(unsafe state)로 전환되지 않는다.
- 교착 상태 감지 및 복구
댓글