6장 교착상태

교착상태의 개요

교착 상태의 정의

• 교착 상태(deadlock)
  • 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태
    • 아사 현상과 관계가 있으나 구분하도록!
• 아사 상태와 차이점
  • 아사 현상(starvation): 운영체제가 잘못 된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제(특정 프로세스가 자원을 가져오지 못해 작업이 계속 지연)
    • 개인 프로세스의 문제, 우선순위가 밀려서 서비스를 못 받음
  • 교착 상태: 여러 프로세스가 작업을 진행하다보니 자연 발생적으로 일어나는 문제
    • 2개 이상의 프로세스, 한 없이 발생하게 됨
• 시스템 자원
  • 교착 상태는 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생
    • 동시에 사용할 수 없는 자원, 상호 배제가 지켜져야 함
• 잠금
  • 교착 상태는 잠금을 사용할 때도 발생
• 응용 프로그램
  • 데이터베이스 같은 응용 프로그램에서도 교착 상태 발생
  • 데이터베이스는 데이터의 일관성을 유지하기 위해 잠금을 사용하는데, 이때 교착 상태가 발생할 수 있음
    • 트렌젝션이 반대방향으로 동작할 때도 교착상대가 발생 가능

자원 할당 그래프(resource allocation graph)

• 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지(점선)를 방향성이 있는 그래프(directional graph)로 표현한 것
• 프로세스는 원으로, 자원은 사각형으로 표현

  

 

• 다중 자원(multiple resource)
  • 여러 프로세스가 하나의 자원을 동시에 사용하는 경우
  • 수용할 수 있는 프로세스 수를 사각형 안에 작은 동그라미로 표현
• 식사하는 철학자 문제에서 교착 상태가 발생하는 조건→ 자원을 공유하지 못하면 교착 상태 발생→ 자원을 놓을 때까지 기다려야 하므로 교착 상태 발생→ 자원 하나를 잡은 상태에서 다른 자원을 기다리므로 교착 상태 발생→ 자원 요구 방향이 원이면 양보를 하지 않아 교착 상태 발생
• ① 철학자들은 서로 포크를 공유할 수 없음
• ② 각 철학자는 다른 철학자의 포크를 빼앗을 수 없음

• ③ 각 철학자는 왼쪽 포크를 잡은 채 오른쪽 포크를 기다림
• ④ 자원 할당 그래프가 원형

• 교착 상태 필요 조건(necessary condition)
  • 다음 4가지 조건 모두 만족해야 교착 상태 발생. 한가지라도 만족하지 않으면 교착 상태 발생하지 않음

교착 상태 필요조건

교착 상태 필요조건

• 교착 상태 필요 조건
  • 상호 배제(mutual exclusion): 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 함 → 배타적 자원 사용하면 교착 상태 발생
  • 비선점(non-preemptive): 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 함 → 빼앗을 수 없으면 공유 안되니 교착 상태 발생
  • 점유와 대기(hold and wait): 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 함 → 자원을 점유하면서 다른 자원을 기다리면 교착 상태 발생
  • 원형 대기(circular wait): 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 함 → 프로세스들이 서로 양보하지 않아 교착 상태 발생
• 교착 상태 필요 조건 분석
  • 상호 배제, 비선점 조건 : 자원이 어떤 특징을 가지는지를 나타냄
    • 뺏어야 하며, 깨기가 어려운 조건이다.
  • 점유와 대기, 원형 대기 조건 : 프로세스가 어떤 행위를 하고 있는지를 나타냄
    • 동작에 대한 설명이며 이 두 행위가 일어나지 않도록 하는 것이 교착 상태 제지 조건이다.

식사하는 철학자 문제와 교착 상태 필요조건

—pass

교착 상태 해결 방법

교착 상태 해결

• 교착 상태 예방(prevention): 교착 상태를 유발하는 네가지 조건이 발생하지 않도록 하여 아예 예방하는 방식으로 교착상태 조건 4가지에 대하여 각각의 방법이 존재함.
  • 가장 보수적인 것, 필요조건 중 하나라도 발생하지 않도록 함
• 교착 상태 회피(avoidance): 교착상태가 발생하지 않도록 자원 할당량을 조절하여 교착 상태를 회피하는 방식
  • 일어날 것 같으면 회피 하는 식, 자원을 안주는 편
• 교착 상태 검출(detection)과 회복(recovery): 교착 상태 검출은 어떤 제약을 가하지 않고 자원 할당 그래프를 모니터링하면서 교착 상태가 발생하는지 살펴 보는 방식으로 만약 교착 상태가 발생하면 교착 상태 회복 단계가 진행됨
  • 일어하면 그냥 일어나게 둠
• 아래로 올수록 오버헤드가 적다.

교착 상태 예방

• 상호 배제 예방
  • 시스템 내에 있는 상호 배타적인 모든 자원, 즉 독점적으로 사용할 수 있는 자원을 없애는 방법
  • 현실적으로는 모든 자원을 공유할 수 없으며 상호 배제를 적용하여 보호해야 하는 자원이 있음
  • 상호 배제를 무력화하는 것은 사실상 어려움
• 비선점 예방
  • 모든 자원을 빼앗을 수 있도록 만드는 방법
  • 그러나 아사 현상을 일으켜 비선점 조건을 무력화하기는 어려움
    • 생길 문제들이 많음. 피해가 계속 발생하게 되거나 우선순위가 깡패다. 교착 생태 막자고 다른 문제들을 야기 시킨다.
• 점유와 대기 예방
  • 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법
  • ‘전부 할당하거나 아니면 아예 할당하지 않는’ 방식을 적용
    • hold & wait
  • 자원이 아닌 프로세스의 자원 사용 방식을 변화시켜 교착 상태를 처리한다는 점에서 의미가 있음
  • 점유와 대기 예방의 단점
    • 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어려움
    • 자원의 활용성이 떨어짐
    • 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리함
    • 결국 일괄 작업 방식으로 동작
• 원형 대기 예방
  • 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법
  • 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하는 것
    • ex) 마우스를 할당받은 상태에서 프린터를 할당받을 수는 있지만 프린터를 할당받은 상태에서는 마우스나 하드디스크를 할당받을 수 없음
  • 원형 대기 예방과 교착 상태 해결
    • 프로세스 P2는 자원을 할당받을 수 없어 강제 종료되고 프로세스 P1은 정상적으로 실행
  • 원형 대기 예방의 단점
    • 프로세스 작업 진행에 유연성이 떨어짐
    • 자원의 번호를 어떻게 부여할 것인지가 문제
• 교착 상태 예방 정리
  • 교착 상태를 유발하는 네 가지 조건이 일어나지 않도록 제약을 가하는 방법
  • 자원을 보호해야 하므로 상호 배제와 비선점 예방은 사용하기 어려움
  • 점유와 대기, 원형 대기 예방은 프로세스 작업 방식을 제한하고 자원을 낭비하기 때문에 사용할 수 없음

교착 상태 회피

• 교착 상태 회피의 개념
  • 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어주는 방법
  • 교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 교착 상태가 발생하는 범위에 있으면 프로세스를 대기 시킴
  • 즉, 할당되는 자원의 수를 조절하여 교착 상태를 피함
• 안정 상태와 불안정 상태
  • 교착 상태 회피는 자원 총수와 현재 할당된 자원 수를 기준으로 시스템을 안정 상태(safe state)와 불안정 상태(unsafe state)로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당
  • 할당된 자원이 적으면 안정 상태가 크고, 할당된 자원이 늘어날수록 불안정 상태 커짐
  • 교착 상태는 불안정 상태의 일부분이며, 불안정 상태 커질수록 교착 상태 발생 가능성 높아짐
    • 100% 교착은 아니지만 조심하고자 함, 반드시가 아님을 유념
  • 교착 상태 회피는 안정 상태를 유지할 수 있는 범위 내에서 자원을 할당해 교착 상태를 피함
• 은행원 알고리즘
  • 교착 상태 회피를 구현하는 대표적인 알고리즘
  • 은행이 대출을 해주는 방식, 즉 대출 금액이 대출 가능한 범위 내이면(안정 상태이면) 허용되지만 그렇지 않으면 거부되는 것과 유사한 방식total 시스템 내 전체 자원의 수

    Available(가용 자원)	시스템 내 현재 사용할 수 있는 자원의 수
    가용 자원 = 전체 자원- 모든 프로세스의 할당 자원
    Max(최대 자원)	각 프로세스가 선언한 최대 자원의 수
    Allocation(할당 자원)	각 프로세스에 현재 할당된 자원의 수
    need	각 프로세스가 앞으로 사용한 자원의 수
    필요량 = 최대 자원 -할당 자원
    필요량

• 은행원 알고리즘에서 자원 할당 기준
  • 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당
  • 가용 자원이 어떤 기대 자원보다 크지 않으면 할당하지 않음

  

  
  
  • 안정 상태의 예

    

    • 현재 각 프로세스에 할당된 할당량 10(2+4+4)개, 잔여량 (2)
    • 프로세스 2의 요구량 → 2, 먼저 할당
    • → 6개 반납 받음. → 나머지 순차적으로 마칠 수 있어서 안정상태!
    • 프로세스 3이 1개 요청 → 1개 남음 → 다른 자원 순차적으로 마칠 수 없어서 불안정 상태 ⇒ 할당 x
  • 불안정 상태의 예

  • 

• 교착 상태 회피의 문제점
  • 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 함
  • 시스템의 전체 자원 수가 고정적이어야 함
  • 자원이 낭비 됨 - 최대 자원을 사용하지 않고도 작업을 마치는 수가 있기 때문에 불안정 상태라고 무조건 자원을 할당하지 않는 것은 자원 낭비임.

 

 

 

교착 상태 검출

• 교착 상태 검출의 개념
  • 운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방법
  • 교착 상태가 발견되면 이를 해결하기 위해 교착 상태 회복 단계를 밟음
    • 교착 상태가 자주 발생하지 않는다는 가정
• 타임아웃을 이용한 교착 상태 검출
  • 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리
  • 교착 상태가 자주 발생하지 않을 것이라는 가정하에 사용하는 것으로, 특별한 알고리즘이 없어 쉽게 구현
  • 타임아웃이 되면 프로세스 종료
• 데이터베이스에서 타임아웃의 문제
  • 데이터베이스에서 타임아웃으로 프로세스가 종료되면 일부 데이터의 일관성이 깨질 수 있음
  • 데이터의 일관성이 깨지는 문제를 해결하기 위해 체크포인트와 롤백 사용
    • 체크포인트(check point): 작업 중 문제 발생하면 저장된 상태로 돌아오기 위한 표시
    • 롤백(roll back): 작업 중 문제 발생하여 과거의 체크포인트로 되돌아가는 것
• 자원 할당 그래프를 이용한 교착 상태 검출
  • 단일 자원을 사용하는 경우 자원 할당 그래프에 사이클 있으면 교착 상태

    

 

교착 상태 회복

• 교착 상태가 검출된 후 교착 상태를 푸는 후속 작업을 하는 것
• 교착 상태 회복 단계에서는 교착 상태를 유발한 프로세스를 강제로 종료
  • 여러 프로세스가 관계 있음
• 프로세스를 강제로 종료하는 방법② 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
  • 희생양을 정함
  • 우선순위가 낮은 프로세스를 먼저 종료
  • 우선순위가 같은 경우 작업 시간이 짧은 프로세스를 먼저 종료
    • 긴 것은 이미 어느정도 진행이 된 것이기 때문에 짧은 것 우선 종료
  • 위의 두 조건이 같은 경우 자원을 많이 사용하는 프로세스를 먼저 종료
    • 교착 상태 해결가능성이 높기 때문