교착 상태

교착 상태란 뭘까?

A : 2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태

 

아사 상태와 차이점?

아사 현상 : 운영체제가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제

교착 상태 : 여러 프로세스가 작업을 진행하다 보니 지연 발생적으로 일어나는 문제

 

교착 상태의 발생

• 시스템 자원 : 교착 상태는 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생

• 공유 변수 : 교착 상태는 공유 변수를 사용할 때 발생

• 응용 프로그램 : 데이터베이스 같은 응용 프로그램에서도 교착 상태 발생, 데이터베이스는 데이터의 일관성을 유지하기 위해 잠금을 사용하는데, 이때 교착 상태가 발생할 수 있음

 

자원 할당 그래프

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

다중 자원

여러 프로세스가 하나의 자원을 동시에 사용하는 경우

수용할 수 있는 프로세스 수를 사각형 안에 작은 동그라미로 표

 

식사하는 철학자 문제

왼쪽에 있는 포크를 잡은 뒤 오른쪽에 있는 포크를 잡아야만 식사 가능

교착 상태가 발생하는 조건

• 철학자들은 서로 포크를 공유할 수 없음
  • 자원을 공유하지 못하면 교착 상태가 발생
• 각 철학자는 다른 철학자의 포크를 빼앗을 수 없음
  • 자원을 빼앗을 수 없으면 자원을 놓을 때까지 기다려야 하므로 교착 상태가 발생
• 각 철학자는 왼쪽 포크를 잡은 채 오른쪽 포크를 기다림
  • 자원 하나를 잡은 상태에서 다른 자원을 기다리면 교착 상태가 발생
• 자원 할당 그래프가 원형
  • 자원을 요구하는 방향이 원을 이루면 양보를 하지 않기 때문에 교착 상태가 발생

 

교착 상태 필요 조건

• 4가지 조건이 모두 발생해야만 교착상태 발생 (필요조건)
  • 4가지 중 단 한가지라도 만족하지 않으면 교착상태가 발생하지 않음
• 상호 배제(mutual exclusion) : 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 함
• 비선점(non-preemptive) : 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 함
• 점유와 대기(hold and wait) : 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 함 
• 원형 대기(circular wait) : 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 함

 

교착 상태 해결 방법

• 교착 상태 예방(prevention) : 교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방식으로 교착상태 조건 4가지에 대하여 각각의 방법이 존재 함.
• 교착 상태 회피(avoidance) : 자원 할당량을 조절하여 교착 상태를 회피하는 방식
• 교착 상태 검출(detection)과 회복(recovery) : 교착 상태 검출은 어떤 제약을 가하지 않고 자원 할당 그래프를 모니터링하면서 교착 상태가 발생하는지 살펴보는 방식으 로 만약 교착 상태가 발생하면 교착 상태 회복 단계가 진행됨

 

교착 상태 조건 4가지에 대하여 각각의 방식이 존재

• 상호 배제 예방
  
  • 시스템 내에 있는 상호 배타적인 모든 자원, 즉 독점적으로 사용할 수 있는 자원을 없애버리는 방법
  • 현실적으로는 모든 자원을 공유할 수 없으며 상호 배제를 적용하여 보호해야 하는 자원이 있음
  • 상호 배제를 무력화하는 것은 사실상 어려움
• 비선점 예방
  • 모든 자원을 빼앗을 수 있도록 만드는 방법
  • 그러나 아사 현상을 일으켜 비선점 조건을 무력화하기는 어려움
• 점유와 대기 예방
  • 프로세스 자원을 점퓨한 상태에서 다른 자원을 기다리지 못하게 하는 방법
  • 전부 할당 아니면 아예 할당하지 않는 방식을 적용
  • 자원이 아닌 프로세스의 자원 사용 방식을 변화시켜 교착 상태를 처리함

• 점유와 대기 예방의 단점
  
  • 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어려움
  • 자원의 활용성이 떨어지며 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리함
  • 결국 일괄 작업 방식으로 동작
• 원형 대기 예방
  
  • 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법
  • 모든 자원에게 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당
  • 하지만 프로세스 작업 진행에 유연성이 떨어지고, 자원의 번호를 어떻게 부여할 것인지가 문제

 

교착 상태 회피

교착 상태 회피의 개념

• 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어주는 방법
• 교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 교착 상태가 발생하는 범위에 있으면 프로세스를 대기시킴
• 즉, 할당되는 자원의 수를 조절하여 교착 상태를 피함

안정 상태와 불안정 상태

• 할당된 자원이 적으면 안정 상태가 크고, 할당된 자원이 늘어날수록 불안정 상태가 커짐
• 교착 상태는 불안정 상태의 일부분이며, 불안정 상태가 커질수록 교착 상태가 발생할 가능성이 높아짐
• 교착 상태 회피는 안정 상태를 유지할 수 있는 범위 내에서 자원을 할당함 으로써 교착 상태를 피함

은행원 알고리즘

• 교착 상태 회피를 구현하는 대표적인 알고리즘
• 은행이 대출을 해주는 방식, 즉 대출 금액이 대출 가능한 범위 내이면 허용되지만 그렇지 않으면 거부되는 것과 유사한 방식

안정상태

각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한 번 이상인 경우를 말함

교착 상태 회피의 문제점

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

 

 

교착 상태 검출

운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방식

 

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

• 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리함
• 타임아웃이 되면 프로세스가 종료

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

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

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

• 단일 자원을 사용하는 경우 자원 할당 그래프에 사이클이 있으면 교착 상태

 

교착 상태 회복

• 교착 상태가 검출된 후 교착 상태를 푸는 후속 작업을 하는 것
• 교착 상태 회복 단계에서는 교착 상태를 유발한 프로세스를 강제로 종료

 

쉽게 배우는 운영체제 | 조성호 - 교보문고 (kyobobook.co.kr)