교착상태와 무기한 연기
교착상태 (deadlock)
프로세스나 쓰레드가 아무리 기다려도 일어날 수 없는 사건을 대기하고 있는 상태
자원 경쟁 교착 상태
- 독점 자원에 대한 경쟁에서 교착상태 발생
- 환경 대기가 있을 때 발생
자원요구 교착상태
- 어느 프로세스도 보유 자원을 포기하려고 하지 않은 상황의 환형대기
- 자원할당 그래프에 의한 표현
- 노드
- 원: 자원의 종류
- 사격형: 프로세스
- 원 속의 점: 개별 자원
- 에지
- 자원 할당 및 요구 관계
- 노드
교착 상태의 예
- 세마포어 사용에서의 교착 상태
Semaphore S = new Sempahore(1);
Semaphore Q = new Sempahore(1);
// 쓰레드 T1
void T1( )
{
bool done = false;
while (!done) {
P(S)
P(Q)
:
V(S);
V(Q)
}
}
// 쓰레드 T2
void T2( )
{
bool done = false;
while (!done) {
P(Q);
P(S);
:
V(Q)
V(S)
}
}
스풀링 시스템의 교착상태
- 스풀링 파일을 스풀 파일 공간에 보내고 있는 도중에 스풀 공간이 차버리는 경우
- 해결방법
- 충분한 스풀 공간 확보
- 스풀링 파일이 일정한 임계치를 넘지 못하게 강제
- 스풀링 파일이 전부 스풀 공간에 저장되기 전에 프린트 시작
- 오디오나 비디오 스트림 서비스에서 유사한 개념 적용
자원
선점 자원
- 손실없이 프로세스로 부터 회수 가능한 자원
- 프로세서, 메인 메모리 등
비선점 자원
- 회수하게 되는 경우 손실이 발생가능한 자원
- 프린터, 스캐너 등
공유 가능 자원
- 재진입 코드
- 사용 중에 변경이 없는 코드
- 동시에 여러 프로세스에 의해 공유 가능
- 바로 이전에 실행중인 것의 결과에 새로이 실행되는 것이 영향을 주지 않는 것
- 재귀함수 등
공유 불가 자원
- 순차적 재사용 가능 코드
- 변경가능하나, 사용할 때마다 재 초기화가 수행되는 코드
- 한번에 하나의 프로세스만 사용 가능
무기한 연기
- 프로세스가 자원을 사용할 수는 있지만, 자원 할당 스케줄링 정책 때문에 계속 대기해야 하는 상황
- 운영체제의 편중된 자원 할당 정책 때문에 발생
식사하는 철학자 문제
-
생각하거나 먹거나 하며 시간을 보내는 철학자들
- 배가 고프면, 젓가락 2개를 집어서 식사
- 젓가락은 한번에 한 사람이 사용
-
제약조건
- 기아 상태에 빠지지 않아야 함
- 교착상태 배제
- 무기한 연기 상태 배제
- 상호 배제 강제
- 두 명이 철학자가 동시에 같은 젓가락 사용 불가
- 기아 상태에 빠지지 않아야 함
-
eat() 메소드 구현시 고려상황
- 상호배제, 교착상태, 무기한 연기 -
무기한 연기 문제
- 젓가락을 계속해서 사용할 수 없는 경우
- 무기한 연기 해결 방법
- 노화(aging) 기법
- 프로세스가 자원을 기다린 시간에 비례하여 우선순위 부여
- 오랫동안 대기한 프로세스가 새로 도착하는 다른 모든 프로세스보다 우선순위가 높아져 먼저 자원 확보
교착상태 발생의 필요조건
교착상태 발생의 4가지 필요조건
- 상호 배제
- 자원을 배타적으로 점유
- 한번에 한 프로세스만 자원 사용
- 점유와 대기
- 이미 어떤 자원을 점유하고 있으면서, 부가적으로 다른 자원 추가 요구
- 비선점
- 프로세스에 할당된 자원은 사용을 완료하기 전에 회수 불가
- 환형대기
- 프로세스와 자원들이 원형을 이루며, 프로세스가 할당된 자원을 점유하며 추가적인 자원요청
교착상태 처리 방법
교착 상태의 예방
- 교착상태 발생 가능성을 사전에 제거
교착상태의 회피
- 교착상태가 발생하려고 할 때, 적절히 피해가는 방법
교착상태의 감지
- 교착상태의 발생여부를 판단하고, 교착상태에 관련된 프로세스와 자원을 결정
교착상태의 회복
- 시스템으로부터 교착상태를 제거하고, 교착상태에 빠진 프로세스가 완료되게 진행시키는 것
교착상태의 예방
- 교착상태 발생 가능성을 사전에 제거
- 교착상태 발생 필요조건의 하나라도 제거
- 점유와 대기 조건 배제
- 비선점 조건 배제
- 환형대기 조건 배제
- 상호배제 조건의 배제 불가
점유와 대기 조건의 배제
-
필요한 자원을 모두 한꺼번에 요청
-
프로세스가 요구할 자원을 전부 할당하든지 또는 하나라도 부족하면 전혀 할당하지 않음
-
단점
- 심각한 자원 낭비 가능성
- 마지막 단계에서 사용할 자원도 처음부터 요구 - 비효율적 자원공유
- 무기한 연기 발생 가능
- 심각한 자원 낭비 가능성
비선점 조건의 배제
- 추가 자원 요구가 거절되면, 원래 점유하고 있던 자원을 모두 반납하고 나중에 다시 해당 자원들을 요구
- 보유 자원 반납시 현 시점까지 수행한 모든 작업 손실 가능
- 단점
- 비용 및 시간 증가
- 빈번한 자원 반납 가능 및 재시작 - 무기한 연기 발생 가능
- 비용 및 시간 증가
환형대기 조건의 배제
-
각 자원의 유형별로 할당 순서를 부여
-
프로세스가 어떤 유형의 모든 자원을 할당받았으면, 순서에 따라 나중에 위치하는 자원만 요구 가능
-
현재 프로세스가 가진 자원보다 큰 번호의 자원만 요청 가능
-
단점
- 자원할당의 융통성 부족
- 프로세스가 필요한 자원순서와 부여된 번호가 다를 경우, 미리 자원 할당
- 자원 낭비 초래
- 새로운 자원을 시스템에 추가시, 기존 프로그램과 시스템 재구성 필요
- 급한 프로세스에 대한 자원할당 어려움
- 프로그래머가 자원할당 순서 고려한 프로그래밍
교착상태의 회피
- 교착상태가 발생하려고 할 때, 적절히 피해가는 방법
- 교착상태 예방기법보다 자원의 효율적 이용을 위해, 덜 엄격한 제약
- 자원할당 패턴에 제약을 주는 미래의 프로세스 행위에 대한 지식에 의존
- Dijkstra의 은행가 알고리즘
은행가 알고리즘
- 안전 상태와 불안전 상태
- 안전 상태
- 현재 모든 프로세스를 일정 시간 내에 완료할 수 있는 상태
- 안전한 프로세스 순서 존재
- (P1,P2,...,Pn)
- Pi가 요구하는 자원이 현재 가용자원과 Pi 이전의 프로세스들이 사용하고 반납하는 자원들에 의해서 확보 가능
- 불안전 상태
- 모든 프로세스를 완료할 수 있다는 것을 보장할 수 없는 상태
- 결국 교착상태가 발생할 수도 있는 상태
- 안전 상태
-
각 프로세스의 자원 요청 및 반환 순서를 완전히 안다고 전제
-
각 프로세스는 필요한 각 자원 별 최대 개수 선언
-
프로세스의 자원 요청에 대해서 교착상태 회피를 위해 허용할지 대기시킬지 여부 결정
-
프로세스의 자원 요청시
- 해당 자원을 할당하여 안전 상태가 되면, 자원 할당
- 불안전 상태가 되면, 다른 프로세스가 자원을 반환할 때 까지 대기
-
단점
- 자원의 개수 고정
- 프로세스의 집단 고정
- 프로세스는 미리 최대 필요 자원 개수의 보고 필요
- 프로세스는 유한한 시간 내에 모든 자원 반환 가정
-
실제 시스템에 적용 사례 적음
교착상태의 감지
- 교착상태가 발생할 수 있는 시스템에 사용
- 교착상태의 발생 여부 결정
- 교착상태 발생시 관련 프로세스 및 자원 식별
- 교착상태 감지 알고리즘은 상당한 시간 부담 초래
자원-할당 그래프
- 사각형: 프로세스
- 큰 원: 동일 자원의 클래스
- 작은 원: 자원
그래프 축약
- 프로세스의 자원 요청이 수용될 수 있으면, 해당 프로세스에 의한 그래프 축약
- 연결선(edge, 간선) 삭제
- 그래프가 모든 프로세스에 의해 축약되면, 교착상태에서 자유
- 모든 연결선 제거 상태
- 그래프가 프로세스에 의해 축약될 수 없으면, 축약되지 않는 프로세스들이 교착상태 구성
교착상태의 회복
-
교착 상태에 있는 프로세스들이 교착 상태를 벗어나도록 하는 것
-
교착상태를 해소하여, 교착상태의 프로세스가 작업을 종료하고 자원을 반환하도록 하는 것
-
일시중단(suspend)/재시작(resume) 방법
- 프로세스를 임시로 중단시키는 것
- 일시중단된 프로세스는 처리내용의 손실없이 다시 시작
-
체크포인트(checkpoint)/복귀(rollback) 방법
- 일시중단/재시작 기능 이용
- 마지막 체크포인트 이후의 작업은 손실 가능
교착상태의 처리 전략
- 일부 시스템은 교착상태 발생 3개 조건 중 하나를 피하도록 구현
- PC에서는 교착상태를 사소한 것으로 처리
- PC 등에서는 교착상태 감지의 따른 시스템 성능에 영향이 크기때문에 교착상태 처리 무시
- 교착상태는 지속적인 중요한 연구 주제
- 핵심업무 시스템, 실시간 시스템 등
라이브락(Livelock)
- 교착상태와 비슷하게 프로세스가 진행이 되지 않은 것이지만, 라이브락에 빠진 프로세스는 상대 프로세스에 대해 지속적으로 상태 변화
- 프로그램 수행 중 끝없이 동일 과정을 반복하는 것
- 잘못된 정보가 지속적으로 제공되어 특정 루프를 반복하는 경우
- 프로세스 A가 프로세스 B 호출, 프로세스 B는 프로세스 A 호출 경우
Author And Source
이 문제에 관하여(교착상태와 무기한 연기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jeongmin99/교착상태와-무기한-연기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)