06. 교착상태

교착상태

교착상태 개념

• 둘 이상의 프로세스가 서로가 가진 한정된 자원을 요청하는 경우 발생하는 것으로, 프로세스가 진전되지 못하고 모든 프로세스가 대기 상태가 된다.
  • 영구적으로 블록되어 있는 상태

교착상태 조건

1. 상호배제(Mutual exclusion)

• 한 번에 한 프로세스만 해당 자원을 사용할 수 있어야 함(자원의 비공유)
  • 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 대기해야 함.

2. 점유와 대기(Hold and wait)

• 최소한 자원 하나를 보유하고 다른 프로세스에 할당된 자원을 얻기 위해 기다리는 프로세스가 있어야 함.

3. 비선점(No preemption)

• 자원은 선점될 수 없음. 즉 자원을 강제로 뺏을 수 없으며 자원을 점유하고 있는 프로세스가 끝나야 해제됨.

4. 환형대기(Circular wait)

• 프로세스 간에 닫힌 연결이 존재함
  • 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있음.

---

• 교착상태가 발생하기 위해서는 조건1 ~ 조건3이 기본적으로 필요하다.
• 이러한 세 가지 조건이 만족되면, 교착상태가 발생할 수 있다. (교착상태가 발생할 수 있는 필요조건)
  • 위의 세 조건만으로 교착상태가 실제로 발생하는 것은 아니다.
• 조건4까지 만족되면 교착상태가 발생할 수 있는 필요충분조건이 된다.
  • 조건4는 조건1 ~ 조건3의 결과에 의해 발생한다.

운영체제 교제에 따라 교착상태의 조건으로 조건1 ~ 4를 동일하게 다루고 있다.

하지만 교착상태 예방과 교착상태 회피의 명확한 구분을 위해 조건1 ~ 3과 조건4는 다르게 다루어야 한다.

조건1 ~ 3은 정책이며, 조건4는 이러한 정책에 의해 발생한 상태이기 때문이다.

조건1 ~ 4를 동일하게 다루면 이후 논의할 교착상태 예방과 교착상태 회피의 명확한 구분이 어려워 진다.

교착상태의 관리

교착상태를 해결하기 위한 다양한 접근 방법들이 제안 되었다.

1. 교착상태 예방
   • 교착상태의 발생 조건 1~4 중 하나를 시스템에서 허용하지 않는 것
2. 교착상태 회피
   • 현재 자원 할당의 상태에 따라 안전하게 자원 할당을 결정하는 것
3. 교착상태 회복
   • 교착상태가 발생하면 그것을 발견하고 회복하는 것

교착상태 예방

• 운영체제를 설계할 때 교착상태가 발생할 가능성을 없애는 것
  • 교착상태가 발생하기 위한 네 가지 필요충분조건 중 하나를 설계 단계에서 배재하는 것
• 교착상태 예방 방법은 크게 간접적인 방법과 직접적인 방법으로 구분
  • 간접적인 방법
    • 조건 1~3 중 하나를 허용하지 않는 것
  • 직접적인 방법
    • 조건4를 허용하지 않는 것

상호배제

• 시스템 내에 있는 상호 배타적인 모든 자원, 즉 독점적으로 사용할 수 있는 자원을 없애버리는 방법
• 현실적으로는 모든 자원을 공유할 수 없으며 상호 배제를 적용하여 보호해야 하는 자원이 있음
• 상호 배제를 무력화하는 것은 사실상 어려움

점유와 대기

• 최대 자원 할당
  • 프로세스가 작업을 수행하기 전에 필요한 모든 자원을 요청하고 획득해야 함.
  • 단점
    1. 모든 자원을 할당받기 위해 오랜 기간 기다릴 수 있다. (기아상태 발생 가능)
    2. 한꺼번에 할당 받은 자원 중 일부는 실제 수행이 끝날때쯤 사용될 도 있다.
    3. 프로세스가 미래에 사용될 모든 자원을 미리 알기는 어렵다.

비선점

1. 프로세스가 어떤 자원을 요청할 때, 요청한 자원이 사용 가능한지 검사.
   • 사용 가능하다면 자원 할당, 사용 불가능한 자신이 점유한 자원을 반납한 후 원래 자원과 새로 원하는 자원을 요청
2. 두 프로세스에 우선순위를 부여하여, 높은 우선순위의 프로세스가 그보다 낮은 순위의 프로세스가 점유한자원을 선점하여 해결.

환형대기

• 자원의 할당 순서를 정하여 교착상태를 예방
  • 모든 자원에 일련의 순서를 부여, 각 프로세스는 오름차순으로만 자원을 요청할 수 있게 함

예

두 자원 $R_i$ 와 $R_j$ 가 있으며, 운영체제가 $i<j$ 인 할당 순서를 정했다고 하자.

$i<j$ 는 $R_i$ 가 먼저 할당되어야 하며 그 이후에 $R_j$ 가 할당될수 있다는 것을 의미한다.

프로세스 $P$ 가 자원 $R_i$ 를 할당하고 $R_j$ 를 요청했다고 하자.

이 상황에서 교착상태가 발생하려면 다른 프로세스 $Q$ 는 $R_j$ 를 할당하고 $R_i$ 를 요청해야 한다.

하지만, 이것은 운영체제의 자원 할당 순서에 위배개기 때문에 나타날수 없다.

결국, 자원들의 할당 순서를 정하면 교착상태가 발생하지 않는 것이다.

교착상태 회피

• 교착 상태의 모든 발생 가능성을 미리 제거하는 것이 아닌 교착 상태 발생할 가능성 인정하고(세 가지 필요조건 1~3 허용), 교착 상태가 발생하려고 할 때 적절히 회피하는 것
• 예방 방법에 비해 더 많은 병행성을 제공(자원의 효율성이 높음)

---

• 교착상태 회피를 위한 두가지 방법

  1. 프로세스의 시작중단
     • 프로세스의 요구가 교책상태가 발생할 수 있다면 프로세스를 시작을 중지함
  2. 자원 할당 거부(은행원 알고리즘)
     • 프로세스가 요청한 자원을 할당했을때, 교착상태가 발생할 수 있다면 요청한 자원을 할당하지 않음

---

• 어떤 프로세스가 요청을 할 때 미래에 대한 분석을 통해 교착상태를 회피
  • 교착상태를 회피하기 위한 알고리즘을 위해서는 프로세스가 현재 사용 가능한 자원, 다른 프로세스에 할당된 자원 등 각 프로세스에 대한 요구와 해제 정보가 필요

안정상태와 불안정상태

교착상태 회피를 위해 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정상태와 불안정한 상태로 나누고 시스템이 안정상태를 유지하도록 자원을 할당

안정상태

• 시스템이 교착상태를 일으키지 않으면서 각 프로세스가 요구한 최대 요구량만큼 필요한 자원을 할당해 줄 수 있는 상태

불안정상태

• 안정 상태와 달리 프로세스의 자원 할당 및 해제의 순서가 불명확하여 교착상태의 발생가능성이 존재

교착상태

• 교착 상태는 불안정 상태의 일부분이며, 불안정 상태가 커질수록 교착 상태가 발생할 가능성이 높아짐

---

은행원 알고리즘

COMMING SOON

교착상태 회복

자원의 접근에 대한 제한이나 프로세스의 행위에 제한을 두지않기 때문에 교착상태가 발생할수 있다.

따라서

1. 교착상태가 발생했는지를 파악하기위해 시스템 상태를 주기적으로 검사
2. 교착상태로부터 회복

의 기능을 지원해야한다.

교착상태 탐지

COMMING SOON

교착상태로부터 회복

• 교착상태를 회복한다는 것은 환형대기에서 탈피한다는 것인데 이를 위한 방법으로 2가지 방법을 사용할 수 있음

1. 프로세스 종료

1) 교착상태 프로세스를 모두 중지

• 교착상태의 순환대기를 확실히 해결하지만 자원 사용과 시간 면에서 비용이 많이 듬.
• 오랫동안 연산했을 가능성이 있는 프로세스의 부분 결과를 폐기하여 나중에 다시 연산해야 함.

2) 한 프로세스씩 중지

• 한 프로세스가 중지될 때마다 교착상태 탐지 알고리즘을 호출하여 프로세스가 교착상태에 있는지 확인.
• 교착상태 탐지 알고리즘 호출에 대한 부담이 큼.

2. 자원 선점

• 프로세스의 자원을 선점하여 교착상태가 해결될 때까지 선점한 자원을 다른 프로세스에 할당하여 이용
• 다음의 세가지 사항을 해결해야 함.

1) 희생자 선택(selection of a victim)

자원 선점에 앞서 어떤 자원과 어느 프로세스가 선점될 것인가?

---

• 프로세스를 종료할 때, 비용을 최소화하기 위해 적절한 선점 순서를 결정해야 함.
• 비용 요인은 교착상태 프로세스가 점유하고 있는 자원 수, 교착상태 프로세스가 지금까지 실행하는 데 소용한 시간과 같은 매개변수가 포함됨.

2) 롤백(rollback)

만약 특정 프로세스을 자원을 강제로 방출하고 선점시켰다면, 그 프로세스를 어떻게 처리 할 것인가?

---

• 필요한 자원을 읽은 프로세스는 정상적으로 실행할 수 없으므로, 프로세스를 안정상태로 복귀시키고 다시 시작해야 함.

  • 단순한 방법은 완전히 복귀시키고(프로세스를 중지) 재시작하는 것이며, 프로세스를 교착상태에서 벗어날 정도로만 복귀시킬 수 있다면 더 효과적임.
  • 시스템이 실행하는 모든 프로세스의 상태 정보를 유지해야 하는 부담이 존재함.

3) 기아 상태(starvation)

자원 선점을 통해 기아상태가 발생하지 않을까?

---

• 동일한 프로세스가 자원들을 항상 선점하지 않도록 보장할 때, 비용에 근거한 시스템은 동일한 프로세스가 희생자로 선택되기 쉬움.

  • 이는 프로세스가 자신의 작업을 완료하지 못하는 기아상태가 되어 시스템 조치를 요구함.

• 프로세스가 짧은 시간 동안만 희생자로 지정됨을 보장해야 함.

• 일반적인 해결 방법은 비용 요소에 복귀 횟수를 포함시키는 것.

Reference

『IT CookBook, 운영체제』, 구현회 집필, 한빛아카데미

『IT CookBook, 쉽게 배우는 운영체제』, 조성호 집필, 한빛아카데미

『운영체제 : 내부구조 및 설계원리 (6판)』, WILLIAM STALLINGS 저, PEARSON HALL