[쉽게 배우는 운영체제] 6장 교착 상태

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

Starvation은 운영체제가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제이고, 교착 상태는 여러 프로세스가 작업을 진행하다 자연적으로 일어나는 문제

 

다중 자원 : 여러 프로세스가 하나의 자원을 동시에 사용할 수 있는 자원

 

교착 상태 필요 조건

상호 배제, 비선점, 점유와 대기, 원형 대기를 모두 충족해야 발생, 하나라도 충족하지 않으면 교착 상태가 발생하지 않음

 

상호 배제(Mutual Exclusion) : 한 프로세스가 사용되는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 함

(배타적인 자원은 임계구역으로 보호되기 때문에 다른 프로세스가 동시에 사용할 수 없음)

비선점(Nonpreemptive) : 한 프로세스가 사용 중인 자원은 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 함

 

점유와 대기(Hold And Wait) : 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 함

원형 대기(Circular Wait) : 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어 프로세스들이 서로 양보하지 않아야 함

 

상호 배제와 비선점 조건은 자원의 특징을 나타내고, 점유와 대기, 원형 대기 조건은 프로세스의 행위를 나타냄

 

교착 상태 해결 방법

예방

교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방식

실효성이 적어 잘 사용되지 않음

• 상호 배제 예방 : 상호 배타적인 모든 자원을 없애는 방법, 현실적으로 모든 자원을 공유할 수 없으며 보호해야 하는 자원이 있으므로 어려움
• 비선점 예방 : 모든 자원을 빼앗을 수 있도록 만드는 방법, 상호 배제를 보장할 수 없고 임계구역 보호가 불가능하고 Starvation을 초래하므로 어려움
• 점유와 대기 예방 : 필요한 자원을 전부 할당하거나 아예 할당하지 않는 방법
  프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어려움
  앞으로 사용할 자원까지 미리 선점해버리기 때문에 자원 낭비가 심함
  많은 자원을 사용하는 프로세스의 작업이 지연되는 Starvation 현상 발생
  실제로 구현하면 일괄 작업 방식으로 처리되므로 시스템의 효율이 떨어짐
• 원형 대기 예방 : 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법
  모든 자원에 번호를 부여하고 번호가 큰 방향으로 자원을 할당
  프로세스 작업 진행에 유연성이 떨어짐
  자원의 번호를 어떻게 부여할지의 문제가 있음

 

회피

자원을 할당하다가 교착 상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중단하고 대기하는 방법

 

자원의 총 수와 현재 할당된 자원의 수를 기준으로 시스템을 안정(safe) 상태와 불안정(unsafe) 상태로 나누고 안정 상태를 유지하도록 자원을 할당

불안정 상태에서 항상 교착 상태가 발생하는 것이 아닌 교착 상태 발생 가능성이 높아짐

 

• 은행원 알고리즘(Banker's Algorithm)
  스레드(프로세스)가 요청하는 최대 자원 개수를 신고
  스레드가 자원을 요청했을 때 안정 상태이면 자원을 할당하고, 불안정 상태이면 다른 스레드가 끝날 때까지 대기

 

자원을 얼마나 할당해야 교착 상태가 발생하지 않는다는 보장이 없기 때문에 실효성이 적음

• 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 하는데 어려움
• 시스템의 전체 자원 수가 고정적이어야 하는데, 시스템의 자원 수는 유동적임
• 모든 불안정 상태가 교착 상태가 되는 것은 아니므로 최대 자원을 사용할 수 없어 자원이 낭비됨

 

검출

어떤 제약을 가하지 않고 자원 할당 그래프를 모니터링하면서 교착 상태가 발생하는지 살펴보는 방식

• 타임아웃을 이용한 교착 상태 검출 : 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리
  • 타임아웃 시간 동안 작업이 진행되지 않은 모든 프로세스가 교착 상태 때문에 작업이 이루어지지 않은 것은 아니므로 엉뚱한 프로세스가 강제 종료될 수 있음
  • 윈도우의 '프로그램이 응답이 없어 종료합니다' 메시지
• 자원 할당 그래프를 이용하여 교착 상태 검출
  • 운영체제는 자원을 요청하거나 할당할 때마다 자원 할당 그래프를 갱신하는데, 사이클이 발생하면 교착 상태가 검출된 것으로 판단 
  • 작업이 너무 많아 구현하기 어려워 자주 발생하지 않는 교착 상태를 찾기 위해 자원 할당 그래프를 유지하면서 모든 자원을 감시하기에 어려움

 

회복

교착 상태를 검출한 후 교착 상태를 유발한 프로세스를 강제 종료하여 교착 상태를 푸는 후속 작업

• 교착 상태를 일으킨 모든 프로세스를 종료 : 종료된 프로세스가 동시에 작업을 시작하면 다시 교착 상태를 일으킬 가능성이 크기 때문에 다시 실행할 때는 순차적으로 실행해야 함
• 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료

프로세스를 강제 종료하는 일뿐 아니라 강제 종료된 프로세스가 실행되기 전에 시스템을 복구하는 일도 해야 함

명령어가 실행될 때마다 체크포인트를 만드는 일은 작업량이 상당하여 시스템에 부하를 주므로 선택적으로 사용해야 함