교착상태와 무기한 연기

6432 단어 운영체제CSOSCS

교착상태 (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 호출 경우

좋은 웹페이지 즐겨찾기