6) 교착 상태

1. 교착 상태

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

컴퓨터 시스템에서 교착 상태는 시스템 자원, 공유 변수(또는 파일), 응용 프로그램 등을 사용할 때 발생할 수 있습니다.

P1은 R1이라는 자원을 가진 상태로 R2의 자원을 요청합니다.
P2는 R2라는 자원을 가진 상태로 R3의 자원을 요청합니다.
P3는 R3라는 자원을 가진 상태로 R4의 자원을 요청합니다.
P4는 R4라는 자원을 가진 상태로 R1의 자원을 요청합니다.
이때 서로 자원을 가진 상태로 다른 프로세스가 가진 자원을 요청하기 때문에
작업을 진행할 수 없는 상태가 지속되는 것이 교착상태 입니다.

 

2. 자원 할당 그래프

프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것 입니다.

자원 할당 그래프를 사용하면 자원의 할당과 대기 상태를 한눈에 파악할 수 있습니다.

• Pn 는 프로세스를 의미하며 Rn 은 자원을 의미합니다.
• 점선은 프로세스가 요청하는 자원을 의미 합니다.
• 실선은 프로세스가 현재 사용하는 자원을 의미합니다.
• 자원안에 작은 파란 원은 자원이 할당해 줄 수 있는 자원의 수 입니다. 만약 파란원이 2개라면 2개의 프로세스에 자원을 할당해줄 수 있습니다.

3. 교착 상태 필요조건

 

• 상호 배제 : 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다.
• 비선점 : 한 프로세스가 사용 중인 자원은 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.
• 점유와 대기 : 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다.
• 원형 대기 : 점유와 대기를 하는 프로세스 간에 관계가 원을 이루어야 한다.

4. 식사하는 철학자 문제

교착상태에 대해 설명하기 위한 예로 오랫동안 사용되었습니다.

철학자 4명이 둥그런 식탁에 둘러앉아 식사를 하는데, 왼쪽에 있는 포크를 잡은 뒤 오른쪽에 있는 포크를 잡아야만 식사가 가능하다는 조건이 있는 문제입니다.

식사하는 철학자 문제

식사하는 철학자 문제를 자원 할당 그래프로 나타내면 위와 같습니다.

5. 교착 상태 해결 방법

• 교착 상태 예방 : 교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방식입니다.
      
      - 상호 배제 예방 : 독점적으로 사용할 수 있는 자원을 없애버립니다. 하지만 시스템 내에는 공유할 수 없는 자원        이 있기때문에 상호 배제를 무력화하는 것은 사실상 어렵습니다.
         ex ) 프린터를 아무렇게나 공유하면 여러 데이터가 뒤엉켜 출력물이 엉망이 됩니다.
  
      - 비선점 예방 : 모든 자원을 빼앗을 수 있도록 만드는 방법입니다.
        하지만 임계구역을 보호하기 위해서 잠금을 사용하면 자원을 빼앗을 수 없을 뿐만 아니라 상호 배제도 보장할        수 없습니다. 그러므로 사실상 시스템의 모든 자원을 빼앗을 수 있도록 하지 못합니다.
  
      - 점유와 대기 예방 : 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법입니다.
        다시 말해서 '전부 할당하거나 아니면 아예 할당하지 않는' 방식을 적용하는 것입니다.
        프로세스는 시작 초기에 자신이 사용하려는 모든 자원을 한꺼번에 점유하거나, 그렇지 못할 경우 자원을 모두        반납해야합니다. 
  
        점유와 대기 예방은 프로세스 자신이 사용하는 모든 자원을 자세히 알기 어렵고 자원의 활용성이 떨어집니다.
        또한 많은 자원을 사용하는 프로세스가 적은 사원을 사용하는 프로세스보다 자원을 확보하기 어려워 불리한 
        점이 있습니다.
        결국 실제로 구현했을 때 일괄 작업 방식으로 동작해서 비효율적입니다.
  
  
      - 원형 대기 예방 : 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법입니다.
        프로세스들이 한줄로 길게 늘어선다면 그 줄의 맨 끝에서 부터 해결될 것입니다.
        즉 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하는 것입니다.
  
        원형 대기 예방의 단점에는 프로세스 작업 진행에 유연성이 떨어지는 점
        자원의 번호를 어떻게 부여할 것인지 결정하는 문제가 있습니다.
        
• 교착 상태 회피 : 자원 할당량을 조절하여 교착 상태를 해결하는 방식입니다.
  
  즉, 자원을 할당하다가 교착 상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중단하고 지켜봅니다.
  교착 상태 회피를 구현하는 방법에는 은행원 알고리즘이 있습니다.
  
  교착 상태 회피의 문제점에는
  - 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 하는것
  - 시스템의 전체 자원 수가 고정적이어야 하지만 일시적인 고장이나 새로운 자원이 추가되는 일은 자주 있습니다.
  - 자원이 낭비되는 점이 있습니다.
• 교착 상태 검출과 회복 : 자원 할당 그래프를 모니터링 하면서 교착 상태가 발생하는지 살펴보는 방식입니다.
  막약 교착 상태가 발생하면 교착 상태 회복 단계가 진행됩니다.
  
  - 교착 상태 검출은 타임아웃을 이용하는 방법, 자원 할당 그래프를 이용하는 방법 2가지가 있습니다.
  
  - 타임아웃을 이용하는 방법 : 일정 시간 동안 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리    하는 방법입니다.
  
  - 자원 할당 그래프를 이용하는 방법
      자원 할당 그래프를 보며 사이클이 존재 유무를 판단하여 교착 상태를 검출하는 방법입니다.
      그러나 다중 자원(2개 이상의 프로세스에 자원할당이 가능한 자원)을 사용하는 경우에는 사이클이 있다해도
      모두 교착상태라고 판달할 수 없습니다.
      자원 할당 그래프를 이용하는 방법은 프로세스의 작업 방식을 제한하지 않으면서 교착 상태를 정확하게 파악할      수 있다는 것이 장점입니다.
  그러나 자원 할당 그래프를 유지, 갱신, 사이클 검사하는 추가 작업으로 인해 오버헤드가 발생하는 단점이 있습니다.
  
  - 교착 상태 회복 : 교착 상태가 검출되면 고착 상태를 푸는 후속 작업을 하는데 이를 교착 상태 회복이라고 합니다.
  
      프로세스를 강제종료 하는 방법에는 다음 두 종류가 있습니다.
      * 교착 상태를 일으킨 모든 프로세스를 동시에 종료
      * 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료

6. 은행원 알고리즘

교착 상태 회피를 구현하는 방법으로, 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당합니다.