교착 상태의 개요
교착상태의 정의
교착 상태 : 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상황
아사 상태와의 차이점
아사 현상 : 운영체제가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 상황
-> 해결방안 : 에이징(기다린 시간이 너무 길면 실행시켜줌)
교착 상태 : 여러 프로세스가 작업을 진행하다보니 자연 발생적으로 일어나는 문제
-> 해결방안 : 강압적을 교착상태를 해결해줘야함
교착 상태의 발생
자원 할당 그래프
자원 할당 그래프 : 프로세스가 어떤 자원을 사용중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것
프로세스는 원, 자원은 사각형
다중 자원 여러 프로세스가 하나의 자원을 동시에 사용하는 경우
수용할 수 있는 프로세스 수를 사각형 안에 작은 동그라미로 표현
교착 상태 필요 조건
교착 상태 필요 조건
다음 4가지 조건이 모두 발생해야만 교착상태 발생(필요조건)
- 상호배제 : 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이여야함
- 비선점 : 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이여야함
- 점유와 대기 : 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야함
- 원형 대기 : 점유와 대기를 하는 프로세스간에 관계가 원을 이루어야 함
교착상태 필요조건 분석
- 상호배제, 비선점 조건 : 자원이 어떤 특징을 가지는지를 나타냄
- 점유와 대기, 원형 대기 조건 : 프로세스가 어떤 행위를 하는지 나타냄
교착상태 해결 방법
- 교착 상태 예방(prevention) : 교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방식으로 교착상태 조건 4가지에 대하여 각각의 방법이 존재함.
- 교착 상태 회피(avoidance) : 교착상태가 발생하지 않도록 자원 할당량을 조절하여 교착상태를 회피하는 방식
- 교착상태 검출과 회복 (detection & recovery) : 교착 상태 검출은 어떤 제약을 가하지 않고 자원 할당 그래프를 모니터링하면서 교착 상태가 발생하는지 살펴보는 방식으로 만약 교착 상태가 발생하면 교착 상태 회복 단계가 진행됨
교착 상태 예방
- 상호 배제 예방 : 시스템 내에 있는 상호 배타적인 모든 자원, 즉 독점으로 사용할 수 있는 자원을 없애버림
but 상호 배제하여 보호 해야하는 자원이 있으므로 어려움
- 비선점 예방 : 모든 자원을 빼앗을 수 있는 자원으로 만듬
but 아사현상이 일어남
- 점유와 대기 예방 : 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게하는 방법 '전부 할당 or 아무것도 할당x'
자원이 아닌 프로세스의 자원사용방식을 바꾸는 것이기 때문에 의미가 있음
but
- 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어려움
- 자원의 활용성이 떨어짐
- 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리함
- 일괄 작업 방식으로 동작
- 원형 대기 예방 : 점유와 대기를 하는 프로세스들이 원형을 이루지 못하는 함, 모든 자원에 숫자를 부여하고 숫자가 큰방향으로만 자원을 할당
ex) 마우스를 할당받은 상태에서 프린터를 할당 받을수는 있지만 프린터를 할당받은 상태에서는 마우스나 하드디스크를 할당 x
but
프로세스 작업 진행에 유연성이 떨어짐, 자원의 번호를 어떻게 부여할 지가 문제
교착상태 예방 정리
- 교착 상태를 유발하는 네 가지 조건이 일어나지 않도록 제약을 가하는 방법
- 자원을 건드는 상호 배제, 비선점은 어려움
- 점유와 대기, 원형 대기는 프로세스 작업방식을 제한하고 자원을 낭비해 사용할수 없음
교착 상태 회피
- 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어 주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어 주는 방법
- 교착 상태가 발생하지 않는 범위 내에서만 자원 할당, 그 외는 대기 시킴
- 곧 할당되는 자원의 수를 줄여서 교착상태를 피함
안정상태와 불안정 상태
안정 상태면 자원을 주고, 불안정 상태면 대기시킴
뱅커 알고리즘(은행원 알고리즘)
교착 상태 회피를 구현하는 대표적인 알고리즘
은행이 대출을 해주는 방식, 즉 대출금액이 대출 가능한 범위 내이면(안정상태이면) 허용되지만 그렇지 않으면 거부되는 것과 유사(최악의 경우를 기준으로 함)
전체 자원(Total) : 시스템 내 전체 자원의 수
가용 자원(Available) : 시스템 내 현재 사용 할수 있는 자원의 수(가용 자원=전체 자원-모든 프로세스의 할당 자원)
최대 자원(Max) : 각 프로세스가 선언한 최대 자원의 수
할당 자원(Allocation) : 각 프로세스에 현재 할당된 자원의수
기대 자원(expect) : 각 프로세스의 앞으로 사용할 자원의수 (기대자원=최대자원-할당자원)
뱅커 알고리즘에서 자원 할당 기준
- 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당(available>=Expect)할당
- 가용 자원이 어떤 기대 자원보다 ㅁ크지 않으면 할당하지 않음
(acailable< expect)할당x
교착 상태회피의 문제점
- 프로세스가 자신이 사용할 모든 자원을 미리 선언해야함
- 시스템의 전체 자원수가 고정적이여야함
- 자원이 낭비됨
교착상태 검출
교착상태 검출 : 운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방식, 교착 상태를 발견하면 바로 교착상태 회복으로 감
타임아웃을 이용한 교착 상태 검출
- 일정시간 작업이 진행되지 않으면 교착상태라고 판단
- 교착이 자주 발생하지 않을 것을 가정함, 특별한 알고리즘 없이 쉽게 구현 가능
- 타임아웃이 되면 프로세스가 종료됨
데이터베이스에서 타임아웃의 문제
- 데이터베이스에서 타임아웃으로 프로세스가 종료되면 일부 데이터의 일관성이 깨질 수 있음
- 데이터의 일관성이 깨지는 문제를 해결하기위해 체크포인트 와 롤백 사용
- 체크포인트 : 작업하다가 문제가 발생하면 저장된 상태로 돌아오기위해 표시
- 롤백 : 작업을 하다가 문제가 발생하면 과거의 체크포인트로 되돌아오는 것
자원 할당 그래프를 이용한 교착 상태 검출
- 단일 자원을 사용할 경우 그래프에 사이클이 있으면 교착상태
교착 상태 회복
- 교착 상태를 유발한 프로세스를 강제종료
심화학습 다중 자원과 교착 상태 검출
자원 R1은 두 프로세스가 동시에 사용할 수 있는 다중자원이다.
대기 그래프 : 자원 할당 그래프에서 프로세스와 프로세스 간의 관계ㄱ만 나타낸 그래프
그래프 감소 : 대기 그래프에서 작업이 끝날 가능성이 있는 프로세스의 화살표와 관련 프로세스의 화살표를 연속으로 지워가는 작업