교착상태(DeadLock)

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

교착 상태는 여러 프로세스가 서로 양보하지 않는 상태. 교착 상태가 발생하면 운영체제가 강압적으로 해결해야 한다.

 

교착 상태의 발생

교착 상태는 시스템 자원, 공유 변수(또는 파일), 응용 프로그램 등을 사용할 때 발생한다.

 

• 시스템 자원
  • 예를 들면, 프로세스 P1은 프린터를 할당 받은 후 CD 레코더를 기다리고 프로세스 P2는 CD 레코더를 할당 받은 후 프린터를 기다리면 교착 상태 발생
  • 여기서 프린터와 CD 레코드 같은 자원은 임계구역으로 보호받고 있음
• 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생(대표적)
• 공유 변수
  • 예를 들면, 서로 다른 프로세스가 한 공유 변수의 값을 바꾸면서 무한 루프를 도는 경우
• 한 변수를 할당받은 상태에서 다른 변수를 기다리면 교착 상태 발생
• 응용 프로그램
• 데이터베이스 같은 응용 프로그램에서 데이터의 일관성을 유지하기 위해 잠금을 사용하는데 이 때 교착 상태가 발생

 

 

자원 할당 그래프

자원 할당 그래프는 프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것이다. 자원 할당 그래프를 사용하면 어떤 프로세스에 자원이 할당되었는지 어떤 프로세스가 자원을 기다리고 있는지 한 눈에 파악 할 수 있다.

 

 

 

 

 

 

 

 

• 다중 자원
• 여러 프로세스가 하나의 자원을 동시에 사용하는 것
• 다중 자원을 수용할 수 있는 프로세스 수를 사각형 안에 작은 동그라미로 표현한다.
• 
  
   

   

   

   

   

 

 

 

식사하는 철학자 문제

철학자 4명이 둥그런 식탁에 둘러앉아 식사를 하는데, 왼쪽에 있는 포크를 잡은 뒤 오른쪽에 있는 포크를 잡아야만 식사가 가능하다는 조건이 있다. 철학자들은 음식을 먹기 위해 왼손에 포크를 잡고 오른쪽 포크를 잡으려고 옆을 보지만, 이미 왼손에 포크를 들고 있는 다른 철학자를 보게 된다. 결국 오른쪽 포크를 잡지 못해 모두 굶어 죽는다는 것이다. 교착 상태를 설명하기 위한 예제.

 

식사하는 철학자 문제에서 교착 상태가 발생하는 조건을 다음과 같다. 이 중 단 하나라도 충족하지 않으면 교착상태가 발생하지 않는다.

 

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

    

중요한 점은 교착 상태와 아사 현상이 다르다는 것이다. 아사 현상은 정책상 잘못이나 오류로 인해 특정 프로세스의 작업이 이뤄지지 않는 것을 말한다. 아사 현상은 몇 번 이상 양보했다면 더 이상 양보하지 않도록 조정하는 에이징으로 해결할 수 있다. 교착 상태는 아사 현상과 달리 정책상 잘못이나 오류가 없어도 자연적으로 발생한다. 따라서 교착 상태를 해결하는 방법에는 예방, 회피, 검출의 방법이 있다.

 

교착 상태 해결 방법

 

해결 방법	특징
교착 상태 예방	교착 상태를 유발하는 네 가지 조건을 무력화한다.(실효성이 낮아 잘 사용안함)
교착 상태 회피	교착 상태가 발생하지 않는 수준으로 자원을 할당한다.(실효성이 낮음)
교착 상태 검출	자원 할당 그래프를 사용하여 교착 상태를 발견한다.(현실적인 방법)
교착 상태 회복	교착 상태를 검출한 후 해결한다.

 

 

교착 상태 예방

• 상호 배제 예방
• 시스템 내에 있는 상호 배차적인 모든 자원, 즉 독점적으로 사용할 수 있는 자원을 없애버리는 방법
• 시스템 내의 모든 자원을 공유할 수 있다면 교착 상태가 발생하지 않는다.(모든 철학자가 포크를 공유)
• 현실적으로 모든 자원을 공유하기 어려움
• 비선점 예방
• 모든 자원을 빼앗을 수 있도록 만드는 방법(옆 사람의 포크를 빼앗을 수 있다)
• 임계구역을 지켜야하기 때문에 사실상 불가능(이 방법은 아사 현상을 일으킴)
• 점유와 대기 예방
  • 프로세스가 자신이 원하는 모든 자원을 자세히 알기 어렵다.
  • 자원을 활용성이 떨어진다.
  • 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리하다.
  • 결국 일괄 작업 방식으로 동작한다.
• 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법(전부 할당하거나 아예 할당하지 않는 방식)
• 이 방법은 왼쪽 포크를 잡은 상태에서 오른쪽 포크를 잡지 못하도록 막는 것과 같다.
• 상호 배제 예방, 비선점 예방은 자원에 대한 제약을 풀어버리는 것이지만 임계구역으로 보호받는 자원에 대한 제약을 풀기 어렵다. 그러나 이 방법은 프로세스의 자원 사용 방식을 변화시키기 때문에 의미가 있음.
• 그러나 다음과 같은 단점이 있다.
• 원형 대기 예방
• 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법(자원을 한 방향으로 사용하도록 설정)
• 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하는 방법
• 프로세스 작업 진행에 유연성이 떨어지며, 자원의 번호를 어떻게 부여할 것인지가 문제.
• 정리
• 자원을 보호하기 위해 상호 배제와 비선점을 예방하기 어려우며 점유와 대기, 원형 대기는 프로세스 작업 방식을 제한하고 자원을 낭비하기 때문에 위 방법들은 크게 효과가 있지 않다.

 

            

교착 상태 회피

• 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어주는 방법
• 교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 교착 상태가 발생하는 범위에 있으면 프로세스를 대기 시킨다.
• 교착 상태 회피는 자원의 촐수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당한다.

 

 

 

 

 

 

은행원 알고리즘의 자원 할당 기준

· 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당함

· 가용 자원이 어떤 기대 자원보다 크지 않으면 할당하지 않음

 

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

 

 

 

 

 

 

 

 

 

 

안정 상태인 이유는 현재 가용 자원이 2개인데 프로세스 P2가 필요로 하는 자원이 2개이기 때문. 프로세스 P2가 가용 자원 2개를 사용하여 실행을 종료하면 이미 할당받은 자원 6개를 반환하고, 이를 프로세스 P1이나 P3에 할당하면 전체 작업을 무리 없이 완료 할 수 있다.

 

 

 

 

 

 

 

가용 자원이 1개인데 이것으로는 어떤 프로세스의 기대 자원도 충족할 수 없다. 현재 남은 자원으로는 어떤 프로세스도 끝낼 수 없다는 의미이다. 은행원 알고리즘에서는 현재 실행 중인 프로세스 가운데 하나라도 끝낼 수 있을 때 가용 자원을 할당해야 함

 

 

교착 상태 회피의 문제점

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

 

 

교착 상태 검출

교착 상태 예방은 실제로 구현하기 어렵고, 교착 상태 회피는 구현할 수 있지만 자원을 낭비하는 문제가 있다. 따라서 교착 상태 해결 방법 중 가장 현실적인 것은 바로 교착 상태 검출이다. 교착 상태ㅐ가 발견되면 이를 해결하기 위해 교착상태 회복 단계를 밟는다.

 

교착 상태 검출 방법

• 타임아웃을 이용한 교착 상태 검출
  • 엉뚱한 프로세스가 강제 종료될 수 있다.
  • 모든 시스템에 적용할 수 없다.
  • 체크포인트 : 작업을 하다가 문제가 발생하면 저장된 상태로 되돌아오기 위한 표시(현재의 시스템 상태가 하드디스크에 저장됨(스냅샷)
  • 롤백 : 작업을 하다가 문제가 발생하여 과거의 체크포인트로 되돌아가는 것
• 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법
• 타임아웃 되면 프로세스가 종료된다.
• 교착 상태가 자주 발생하지 않을 것이라는 가정하에 사용(대부분의 데이터베이스와 운영체제에서 많이 선호함)
• 다음과 같은 문제가 있음
• 운영체제의 경우 일정 시간동안 응답이 없으면 프로세스를 종료하면 되지만 데이터베이스에서는 데이터 일관성이 깨지면 안되기 때문에 복잡하다.
• 타임아웃으로 인한 데이터 일관성이 깨지는 문제를 해결하기 위해 데이터베이스에서는 체크포인트와 롤백을 사용
• 이런 방식은 운영체제에도 적용된다.(시스템 복원)
• 자원 할당 그래프를 이용한 교착 상태 검출
• 자원 할당 그래프를 보면 시스템 내의 프로세스가 어떤 자원을 사용하고 있는지, 기다리고 있는지를 알 수 있다.
• 자원 할당 그래프에서 자원을 서로 요구하는 사이클이 발견되면 교착상태임을 알 수 있다.

 

 

교착 상태 회복

 

교착 상태가 검출되면 교착 상태를 푸는 후속 작업을 한다. 교착 상태 회복 단계에서는 교착 상태를 유발하는 프로세스를 강제 종료한다. 프로세스를 강제로 종료하는 방법은 두 가지가 있다.

• 교착상태를 일으킨 모든 프로세스 동시에 종료
• 교착상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
• 우선순위가 낮은 프로세스를 먼저 종료한다.
• 우선순위가 같은 경우 작업 시간이 짧은 프로세스를 먼저 종료한다.
• 위의 두 조건이 같은 경우 자원을 많이 사용하는 프로세스를 먼저 종료한다.

 

From. 쉽게 배우는 OS - 조성호