[운영체제] 교착 상태

aramjs·2023년 5월 3일
OS

운영체제

목록 보기
4/6
  • 교착 상태의 정의와 발생 원인 :
    • 2개 이상의 프로세스가 서로 다른 프로세스의 작업이 끝나기만을 기다림으로 인해 작업을 진행할 수 없는 상태,
    • 식사하는 철학자 문제-자원 공유 불가, 놓을 수 없음, 왼쪽 잡으면서 오른쪽을 대기해야 함, 원형 관계
  • 교착 상태가 발생하는 네 가지 필요조건 :
    • 상호 배제(실행 중 자원 공유 불가), 비선점(빼앗을 수 없음), 점유와 대기, 원형 대기(점유-대기 관계가 원형)
  • 교착 상태 해결 방법과 그 실효성 :
    • 예방(상호 배제/비선점 =>자원의 특징을 바꾸므로 불가능. 프린터 등 점유대기/원형대기 => 프로세스 작업 방식 제한, 자원 낭비로 어려움)
    • 회피(은행원 알고리즘)
    • 검출(타임아웃, 자원할당그래프 원형이면 끊기)
    • 회복(프로세스 우선순위대로 죽이기)

교착 상태 개요

정의

  • 교착 상태 deadlock : 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만을 기다림으로 인해 작업을 진행하지 못하는 상태이다.
  • 믹서 요리사와 오븐 요리사 2명이 있는데, 믹서 주인은 오븐이 끝나기만을 기다리고, 오븐 주인은 믹서가 끝나기만을 기다린다.
  • 아사 현상과 차이점
    • 아사 현상 starvation : 운영체제의 잘못된 정책으로 인해 프로세스의 작업이 지연된다.
    • 교착 상태 : 올바른 정책을 사용하지만 자연적으로 발생하는 상태이다.

  • 예시 1

    • 프로세스 P1은 프린터에서 스캐너로 데이터를 보내고, P2는 스캐너에서 프린터로 데이터를 보내는 일을 한다.
    • P2는 스캔을 완료하고 프린터를 사용하여 출력하기 위해 프린터가 자신에게 할당되기를 기다리고, P1은 프린터 사용을 완료 후 스캔 작업을 하기 위해서 스캐너가 자신에게 할당되기를 기다린다.
    • 서로 기다리므로 두 프로세스 모두 작업을 끝내지 못한다.

  • 예시 2 : 잠금을 사용하는 경우

    • P1에서 while(lock2==true); 까지 실행 중 타임아웃이 발생하여
      P2의 lock2=true; while(lock1==true); 가 실행되는 경우
      lock1도 true , lock2도 true 이므로 무한 루프에 빠지게 된다.
..........................................................

boolean lock1=false;
boolean lock2=false;

..........................................................

//P1
lock1=true; //이 코드로 인해 P2 임계구역에 접근이 불가능하다.
while(lock2==true);
	--------
	|임계구역|
	--------
lock1=false; //P2의 while 무한루프가 끝나게 된다.

..........................................................

//P2
lock2=true; //이 코드로 인해 P1 임계구역에 접근이 불가능하다.
while(lock1==true);
	--------
	|임계구역|
	--------
lock2=false; //P1의 while 무한루프가 끝나게 된다.

..........................................................
  • 예시 3 : 데이터베이스에서 데이터의 일관성을 유지하기 위해 잠금을 사용하는 경우 발생할 수 있다.

자원 할당 그래프

  • 자원 할당 그래프 : 프로세스가 사용중인 자원, 기다리는 자원을
    방향성이 있는 그래프 directional graph 로 표현한다.

    • 원 : 프로세스를 나타낸다.
    • 사각형 : 자원을 나타낸다.
    • 실선 : 할당되었다.
    • 점선 : 할당을 기다린다.

  • 단일 자원 single resource : 한 프로세스당 한 자원만 사용한다.

  • 다중 자원 multiple resource : 여러 프로세스가 한 자원을 동시에 사용하는 경우이다.

  • 식사하는 철학자 문제 : 원형 식탁에 의자와 포크가 4개 있다. 이 때, 왼쪽에 있는 포크를 잡은 뒤 오른쪽의 포크를 잡아야만 식사할 수 있다.

    • 포크는 공유할 수 없다.
    • 모두 왼쪽 포크를 잡으면 모두 오른쪽 포크를 잡을 수 없으므로 식사를 할 수 없다.

  • 교착 상태가 발생하는 조건 : 4가지

  1. 자원을 공유하지 못한다.
  2. 자원을 놓을 수 없다. 다른 사람은 기다리지만 자원이 할당되지 않는다.
  3. 자원 하나를 잡은 상태에서 다른 자원을 기다린다.
  4. 자원 요구 방향이 원이다.

교착 상태 필요조건

교착 상태 필요 조건 : 4가지

necessary condition : 4가지

  • 상호 배제 mutual exclusion : 한 프로세스가 사용중인 자원은 다른 프로세스와 공유하지 않는다.
  • 비선점 non-preemptive : 한 프로세스가 사용중인 자원은 다른 프로세스가 빼앗을 수 없다.
  • 점유와 대기 hold and wait : 프로세스가 자원을 할당받은 상태에서 다른 자원을 기다린다.
  • 원형 대기 circular wait : 점유와 대기를 하는 프로세스 간 관계가 원형이다.
  • 상호 배제, 비선점 : 자원의 특징을 나타낸다.
  • 점유와 대기, 원형 대기 : 프로세스 행위의 특징을 나타낸다.
  • 점유-대기 프로세스 간 관계가 일렬이면 가장자리는 양보하게 되므로 교착상태가 발생하지 않는다.

교착 상태 예방 (prevention)

교착 상태의 필요조건에 충족하지 않도록 미리 방지 한다.
자원의 특징인 상호 배제와 비선점을 바꾸면 운영체제의 기능이 제대로 되지 않는다.

상호 배제 예방

  • 시스템 내의 상호 배타적인 모든 독점 자원을 없앤다.

  • 현실적으로 모든 자원을 공유할 수 없고 상호 배제를 적용하여 보호해야 하는 자원이 있다.
  • 프린터 사용 시 출력이 이상하게 되는 일이 발생한다.
  • 현실적으로 어렵다.

비선점 예방

  • 모든 자원을 빼앗을 수 있게 한다.

  • 프로세스마다 우선순위를 두고 뺏게 한다.
    -> 순위가 낮은 프로세스는 아사현상이 발생한다.

  • 비선점 조건을 완전히 무력화하기는 어렵다.

점유와 대기 예방

  • 자원을 점유하면서 다른 자원을 대기하지 못하게 한다.

  • 필요자원을 모두 할당한 후 실행한다.

  • 전부 점유하거나 아예 할당하지 않는 방식을 적용한다.

    • 대기가 불가능하므로 필요한 자원들을 한꺼번에 요구한다.
    • 요구 자원들 중 사용중인 자원이 있다면 대기하지 않고 아예 할당하지 않는다.
    • 사용중인 자원이 없다면 모두 할당한다.

  • 장점 : 프로세스의 자원 사용 방식을 변화시키는 것이 의미있다.

  • 단점 : 사용할 모든 자원을 자세히 알기 어렵다.

    • 자원의 활용성이 떨어진다.
    • 많은 자원을 사용하는 프로세스가 불리하다.
    • 일괄 작업 방식과 같아진다.

원형 대기 예방

번호를 부여하고 큰 방향으로만 할당한다.

  • 모든 자원에 번호를 부여하고 큰 방향으로만 자원을 할당한다.

    • P1 : 마우스1 을 점유하고 프린터3 을 대기할 수 있다.

    • P2 : 프린터3 을 점유하고 하드디스크2 를 대기할 수 없다.

    • P2는 3 -> 2 할당받지 못하므로 강제 종료되고, P1은 정상 실행된다.

  • 장점 : 자원,기능에 영향이 가지 않음

  • 단점 : 프로세스의 작업 진행의 유연성 저하, 번호 부여 오버헤드

교착 상태 예방의 문제점

  • 네 조건(상호 배제, 비선점, 점유와 대기, 원형 대기)이 일어나지 않도록 제약을 정한다.
  • 상호 배제 / 비선점 예방 사용 어려움 : 자원의 특징을 바꾸기 때문에 자원이 손상된다.
  • 점유 대기 / 원형대기 예방 사용 불가 : 프로세스 작업 방식을 제한하고 자원을 낭비한다.

교착 상태 회피 (avoidance)

필요조건에 만족하지 않도록 자원의 할당량을 조절한다.

할당되는 자원의 수를 조절하여 교착 상태를 피한다.

  • 어느 수준 이상의 자원을 나누어 주면 교착 상태가 발생하는지 파악하여 해당 수준 이하로 자원을 나누어 준다.
  • 교착 상태가 발생하지 않는 범위 내에서 자원을 할당하고, 범위 밖에 있으면 프로세스를 대기시킨다.

안정 상태와 불안정 상태

  • 자원 총수와 할당된 자원 수를 기준으로 안정 상태와 불안정 상태로 나누고 안정 상태를 유지하도록 자원을 할당한다.
  • 교착 상태는 불안정 상태의 일부이다.
  • 안정 상태 safe state : 할당된 자원이 적다.
  • 불안정 상태 unsafe state : 할당된 자원이 많다. 커질수록 교착 상태 발생 가능성이 높아진다.

은행원 알고리즘

교착 상태 회피를 구현하는 대표적인 알고리즘이다.
은행이 자원을 대출해준다. 안정이면 허용, 불안정이면 거부이다.

  • 은행원 알고리즘의 자원 할당 기준 : 가용 자원 > 기대 자원
  • 안정 상태 : 각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한 번 이상인 경우이다.

  • 안정 상태와 불안정 상태

  • 변수

변수설명
Total : 전체 자원시스템 내 전체 자원의 수
Available : 가용 자원시스템 내 현재 사용할 수 있는 자원의 수 -> 가용 자원 = 전체 자원 - 모든 프로세스의 할당 자원
Max : 최대 자원각 프로세스가 선언한 최대 자원의 수
Allocation : 할당 자원각 프로세스에 현재 할당된 자원의 수
Expect : 기대 자원각 프로세스가 앞으로 사용할 자원의 수 -> 기대 자원 = 최대 자원 - 할당 자원

교착 상태 회피의 문제점

  • 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다.
  • 시스템의 전체 자원 수가 고정적이어야 한다.
  • 자원이 낭비된다.

교착 상태 검출 (detection)

프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 주시한다.
검출되면 회복 단계로 넘어간다.

타임아웃을 통한 교착 상태 검출

  • 일정 시간 동안 작업이 진행되지 않는 프로세스를 교착 상태로 간주하여 프로세스를 종료한다.

  • 교착 상태가 자주 발생하지 않는다는 가정 하에 사용한다.

  • 장점 : 구현이 쉽다.   단점 : DB에서 데이터의 일관성 위배 -> 체크포인트 , 롤백 사용

데이터베이스에서 타임아웃의 문제

  • 데이터베이스에서 타임아웃으로 프로세스가 종료되면 일부 데이터의 일관성이 깨질 수 있다.

  • 체크포인트 check point : 스냅샷, 세이브포인트의 역할이다.

  • 롤백 roll back : 작업 중 문제가 발생하여 체크포인트 로 되돌아간다.

자원 할당 그래프를 이용한 교착 상태 검출

자원 할당 그래프를 이용한다.

  • 단일 자원을 사용하는 경우 : 자원 할당 그래프에 사이클이 있으면 교착 상태이다.
  • 해결 : 프로세스 자원 할당을 끊어 사이클을 끊는다.

교착 상태 회복 (recovery)

교착 상태를 검출 후 상태 회복 단계가 진행된다.
교착 상태를 유발한 프로세스를 강제로 종료한다.

모두 종료

  • 유발한 모든 프로세스를 동시에 종료

희생자 선정

  • 유발한 프로세스 중 하나를 골라 순서대로 종료 : 우선순위가 낮은 프로세스를 먼저 종료한다.

    • 우선순위가 같은 경우 : 작업 시간이 짧은 프로세스를 먼저 종료한다. -> 날라가는 작업이 적다.
    • 우선순위==작업시간인 경우 : 자원을 많이 사용하는 프로세스를 먼저 종료한다.
      -> 다른 프로세스가 자원을 쓸 수 있다.
  1. 우선순위가 낮은
  2. 지금까지 작업한 시간이 짧은
  3. 자원을 많이 쓰는
    프로세스가 종료된다.
profile
aramjs
안녕하세요.
다음 포스트

[운영체제] 물리 메모리 관리

0개의 댓글