운영체제 5. 교착과 기아

교착상태

다중 프로그래밍 시스템에서 프로세스가 결코 일어날지 않을 사건을 기다리는 상태

작업이 정지되어 명령 진행이 불가해진다

외부종료 명령어로 해결해야함

자원을 서로 기다리고 있는 경우 발생함

작업도 못하고 자원해제도 못하는 상황

 

프로세스의 자원 사용 순서

자원 요청 -수락할 때 까지 대기

자원 사용 - 자원을 휙득 사용

자원해제 - 자원 사용을 마친 후 자원 반환

 

스풀링 시스템에서 교착

디스크엥 할당괸 스풀 출력을 완료하지 않은 상태에서 다른 작업이 스풀을 차지해버린 경우 - 교착상채 발생

디스크 사용에 제어가 없을 경우 발생

 

네트워크에서 교착상태

네트워크가 붐빌 떄 버퍼 공간이 부족하거나 흐릅제어 프로토콜이 없으면 교착 발생

 

교착 상태의 4가지 조건

상호 배제 - 자원을 최소한 1개이상 비공유. 요청한 자원 해제까지 대기

점유와 대기 - 자원을 최소한 하나 보유, 다른 프로세스가 할당된 자원을 얻으려고 대기해야함

비선점 - 자원 선점 불가. 사용중인 자원을 강제로 뺏을 수 없음

순환대기 - 서로가 서로의 응답이나 반환값을 기다리는 경우

 

사이클이 없으면 교착은 발생하지 않는다. 

하지만 사이클이라고 해서 모두 교착이 생기는 것은 아니다

 

교착상태의 해결방법 3가지

예방

회피

탐지

 

교착상태의 예방

하벤더의 교착상태 예방 방법

각 프로세스는 필요한 자운을 한번에 모두 요청, 모두 제공받기 전에는 작업 불가

프로세스의 요청을 더 이상 허용하지 않은면 점유한 자원을 모두 반납, 필요시 다시요청

 

예방방법

자원의 상호배ㅑ제 조건 방지

점유와 대기조건 방지

비선점 조건 방지

순환대기 조건 방지

 

자원의 상호배제 조건 방지

여러 개의 프로셋그가 동시에 공유자원 사용 가능

 

점유와 대기 조건 방지

프로세스 작업 수행 전 필요한 자원을 모두 요청하고 휙득해야함

대기 상태에서는 자원 점유 자체가 불가하므로(한꺼번에 요청해야함) 대기 없음

필요한 자원을 모두 할당 실행 후 다른 시스템 호출에 자원 할당

프로세스가 자원을 전혀 갖고있지 않을 때 자원 요청가능, 자신이 가진 자원을 우선 모두 해제해야함

자원 효율성 매우 낮음, 기아상태 발생 가능성

 

비선점 조건 방지

이미 할당된 자원에 대한 선점권이 없어야함

요청한 자원을 즉시 할당할 수 없어 기다려야하며ㅛㄴ 현재 가진 자원을 모두 해제해야함

프로세스간 우선순위를 부여하고 우선순위가 낮은 프로세스의 자원을 선점하야 해결

 

순환대기 조건 방지

모든 자원에 일련순서를 부여 오름차순으로만 자원을 요철 할 수 있도록 함

계층적 방법으로 순환대기 가능성을 제거함, 교착 예방

 

교착상태 회피

예방보다 효율적인 자원 사용을 위함

프로세스의 시작 중단

프로세스 요구가 교착상태를 발생시킬 수 있다면 프로세스 시작 중단

자원 할당 거부

프로세스가 요청한 자원 할당이 교착을 만들어 낸다면 요청 자우너을 할당하지 않음

 

프로세스 시작 중단

자원을 언제 요청하는지에 대한 추가정보가 필요힘

순서파악을 하고 있다면 대기여부를 알 수 있음

교착회피 알고리즘에 의해 순환대기가 발생하지 않도록 자원 할당 상태를 검사함

자원할당 상태 : 사용가능한 자원 수, 할당된 자원 수, 프로세스의 최대 요청 수 

 

안정상태 

각 프로세스가 원하는 최대 치까지 할당 할 수 있음, 교착상태 예방 가능

불안정 상태

교착이 일어날 수 있는 상태

모든 교착은 불안정 상태에서 발생

 

자원할당 거부

최대 할당량을 미리 계산함

모든 교착상태를 조사하여 안전 상태 여부 확인

불안정할 수 ㅣ이다면 연기, 거부

 

다익스트라 뱅커스 알고리즘

Availvable 사용가능한 자원 수

max 프로세스 자원 최대 요청량

allocation, 프로세스의 현재 자원 사용량

need  프로세스 추가 필요량

단점 자원은 수시로 변하기 때문에 파악 곤란

이로 인해 최대 자원필요량 파악도 곤란

사용자 수는 항상 변함

시스템과부하가 알고르짐으로 인해 증가

자원이용률 낮음

 

교착상태 회복

교착상태 탐지 알고리즘으로 교착상태를 찾음

교착상태에서 회복시킴

 

특징

교착상채 탐지를 언제 어디서 해야할지 결정이 어려움

자주 이용하염 성능이 떨어지지만 프로그램 자원의 유휴상태를 방지할 수 있음

탐지와 회복에 필요한 부담이 있음

 

교착 탐지 알고리즘

쇼사니 코프만

뱅커스 알고리즘과 비슷하나 max, need가 없음

Available 사용가능한 자원 수

Allocation 현재 할당된 자원 수

Request    각 프로세스의 현재 요청을 표시

교착 발생 빈도, 영행을 받는 프로세스 수에 따라 결정됨

자주 발생하면 탐지도 더 자주함

교착 발생 -> 해결 전까지 유휴 -> 교착 프로세스 증가

자주 부르면 교착은 해결되나 연산 부ㅈ담 증가

 

교착 회복 방법

교착프로세스 모두 중단하는 방법

확실한 해결 자원 시간 손해

 

프로세스를 하나씩 중단하는 방법

교착알고리즘이 비대해져 부르는데 부담

 

고아를 만들어 교착을 해결하는 방법

한 프로세스를 희생자로선택한 뒤 잠깐 기아상태로 만듬

그 사이 나머지 프로세스 처리

기아상태 해지