교착상태와 무기한 연기

교착상태 (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 이전의 프로세스들이 사용하고 반납하는 자원들에 의해서 확보 가능
  • 불안전 상태
    • 모든 프로세스를 완료할 수 있다는 것을 보장할 수 없는 상태
    • 결국 교착상태가 발생할 수도 있는 상태
      

• 각 프로세스의 자원 요청 및 반환 순서를 완전히 안다고 전제

• 각 프로세스는 필요한 각 자원 별 최대 개수 선언

• 프로세스의 자원 요청에 대해서 교착상태 회피를 위해 허용할지 대기시킬지 여부 결정

• 프로세스의 자원 요청시

  1. 해당 자원을 할당하여 안전 상태가 되면, 자원 할당
  2. 불안전 상태가 되면, 다른 프로세스가 자원을 반환할 때 까지 대기

• 단점

  • 자원의 개수 고정
  • 프로세스의 집단 고정
  • 프로세스는 미리 최대 필요 자원 개수의 보고 필요
  • 프로세스는 유한한 시간 내에 모든 자원 반환 가정

• 실제 시스템에 적용 사례 적음

교착상태의 감지

• 교착상태가 발생할 수 있는 시스템에 사용
• 교착상태의 발생 여부 결정
• 교착상태 발생시 관련 프로세스 및 자원 식별
• 교착상태 감지 알고리즘은 상당한 시간 부담 초래

자원-할당 그래프

• 사각형: 프로세스
• 큰 원: 동일 자원의 클래스
• 작은 원: 자원

그래프 축약

• 프로세스의 자원 요청이 수용될 수 있으면, 해당 프로세스에 의한 그래프 축약
  - 연결선(edge, 간선) 삭제
  
• 그래프가 모든 프로세스에 의해 축약되면, 교착상태에서 자유
  - 모든 연결선 제거 상태
  
• 그래프가 프로세스에 의해 축약될 수 없으면, 축약되지 않는 프로세스들이 교착상태 구성

교착상태의 회복

• 교착 상태에 있는 프로세스들이 교착 상태를 벗어나도록 하는 것

• 교착상태를 해소하여, 교착상태의 프로세스가 작업을 종료하고 자원을 반환하도록 하는 것

• 일시중단(suspend)/재시작(resume) 방법

  • 프로세스를 임시로 중단시키는 것
  • 일시중단된 프로세스는 처리내용의 손실없이 다시 시작

• 체크포인트(checkpoint)/복귀(rollback) 방법

  • 일시중단/재시작 기능 이용
  • 마지막 체크포인트 이후의 작업은 손실 가능

교착상태의 처리 전략

• 일부 시스템은 교착상태 발생 3개 조건 중 하나를 피하도록 구현
• PC에서는 교착상태를 사소한 것으로 처리
  - PC 등에서는 교착상태 감지의 따른 시스템 성능에 영향이 크기때문에 교착상태 처리 무시
  
• 교착상태는 지속적인 중요한 연구 주제
  - 핵심업무 시스템, 실시간 시스템 등
  

라이브락(Livelock)

• 교착상태와 비슷하게 프로세스가 진행이 되지 않은 것이지만, 라이브락에 빠진 프로세스는 상대 프로세스에 대해 지속적으로 상태 변화
• 프로그램 수행 중 끝없이 동일 과정을 반복하는 것
  • 잘못된 정보가 지속적으로 제공되어 특정 루프를 반복하는 경우
  • 프로세스 A가 프로세스 B 호출, 프로세스 B는 프로세스 A 호출 경우