[운영체제] 교착 상태(Deadlock)

교착 상태 (Deadlock)

두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있어 아무것도 완료되지 못하는 상태

한정된 자원을 여러 곳에서 사용하려고 할 때 발생하는 문제이며, 프로세스가 자원을 얻지 못해서 다음 처리를 하지 못하는 상태이다.

프로세스1과 프로세스2 모두 자원1,2를 얻어야 한다고 가정했을 때,

• t1 : 프로세스1이 자원1을 얻고, 프로세스2가 자원2를 얻음
• t2 : 프로세스1이 자원2를 기다리고, 프로세스2가 자원1을 기다림
  위와 같이 서로 원하는 자원이 상대방에게 할당되어 있어 두 프로세스는 무한정 대기상태에 빠지게 되는데 이러한 상황을 교착상태라고 한다.

* Busy wating : 자원을 사용할 수 있는지 무한루프를 돌며 조건문을 확인하는 방식

교착 상태 발생 조건

• 상호 배제 (Mutual Exclusion)
  자원은 한 번에 한 프로세스만 사용할 수 있다.

• 점유와 대기 (Hold and Wait)
  최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다. (자원 가지고 있으면서 다른 프로세스것도 탐내야 됨)

• 비선점 (No Preemption)
  다른 프로세스에 할당된 자원은 사용이 끝나서 반납할 때 까지 강제로 선점할 수 없다. (자원 뺏으면 안댐)

• 환형대기 (Circular Wait)
  프로세스의 집합 {P0,P1,...,Pn}에서 P0은 P1이 점유한 자원을 대기하고 P1은 P2가 점유한 자원을 대기하고 Pn은 P0이 점유한 자원을 요구해야 한다.
  즉 프로세스 집합에서 순환 형태로 자원을 대기하고 있어야 한다.

교착 상태는 위의 4가지 조건이 동시에 성립할 때 발생하며 하나라도 성립하지 않는다면 교착 상태를 해결할 수 있다.

교착 상태 예방

교착 상태 발생 조건 중 한가지를 제거함으로써 교착 상태를 해결하는 방법이다.

• 상호 배제 (Mutual Exclusion)
  여러 프로세스가 공유 자원을 사용하도록 한다.
  하지만 상호 배제는 일관성을 유지하기 위해 반드시 필요한 조건이므로 제거하기 힘들다.

• 점유와 대기 (Hold and Wait)
  프로세스는 자신이 사용할 모든 자원을 한 순간에 요청해서 프로세스가 실행되기 전 모든 자원을 할당받도록 한다.
  매우 비효율적인 방법이며 프로세스들이 모든 자원을 할당받기 위해 오랜 시간 대기 상태에 있을 수 있고 프로세스가 미래에 사용할 자원이 무엇인지 알기 힘들다는 단점이 있다.

• 비선점 (No Preemption)
  한 프로세스에서 다른 프로세스가 점유한 자원을 원하면 운영체제는 다른 프로세스가 점유한 자원을 강제적으로 반납시키고 그것을 원하는 프로세스에 할당하도록 한다.
  프로세스들이 다른 우선순위를 가지고 있을 때 교착상태를 예방할 수 있다.

• 환형대기 (Circular Wait)
  자원의 할당 순서를 정하고 프로세스는 그 순서대로 자원을 요청하도록 한다. (일방향으로 자원을 요청)

교착 상태 회피 (은행원 알고리즘)

교착 상태가 발생하기 전에 교착 상태를 예상하여 안전한 상태(safe state)에서만 자원 요청을 허용하는 방법이다.

은행원 알고리즘에서는 교착 상태에 빠질 가능성이 있는지 판단하기 위해 상태를 안전 상태와 불안전 상태로 나눈다.

그리고 안전 상태를 유지할 수 있는 요구만을 수락하고, 불안전 상태를 초래할 사용자의 요구는 안전 상태를 만족할 수 있을 때 까지 계속 거절하며 안전 상태를 유지할 수 있게 한다.

예시

현재 운영체제는 10개의 자원을 가지고 있고 이 자원을 필요로하는 프로세스가 3개 존재한다.
프로세스는 필요로 하는 자원이 충족 되어야 일을 해결할 수 있고 사용한 자원을 반납할 수 있다.

위 프로세스 세 개는 각각 4개, 5개, 7개의 자원이 필요하다.
운영체제는 가지고 있는 10개의 자원 중 일단 2개씩 주기로 했다.
그러면 프로세스는 각각 2개, 3개, 5개의 자원이 더 필요하다.
하지만 지금 운영체제에 남은 자원은 4개이다. 어떻게 해결할 수 있을까?

프로세스1 에게 2개를 주고, 일을 마치고 자원을 반납할 때 까지 기다렸다가 다른 프로세스에게 주는 방법이 있다.

이 경우처럼 필요한 자원을 할당할 수 있고, 다시 자원을 돌려받을 수 있는 상태를 안전상태라고 한다.

• P1 - P2 - P3
• P2 - P1 - P3
• P2 - P3 - P1

위의 순서대로 자원을 할당하면 모든 프로세스에게 자원을 할당해줄 수 있는데, 이를 안전 순서열이 존재한다고 한다.

만약 처음에 프로세스3에게 2개가 아닌 5개의 자원을 할당한다면 운영체제에 남는 자원은 1개 뿐이다.
이 상황에서는 세 프로세스 중 어떤 것도 해결해 줄 수 없게 되며 안전순서열이 존재하지 않게 되는데 이 상태를 불안전상태라고 한다.

• 안전상태(Safe State)
  시스템이 교착상태를 일으키지 않으면서 각 프로세스에게 필요한 자원을 할당해줄 수 있는 상태로 안전순서열이 존재하는 상태를 의미한다.

• 불안전상태(Unsafe State)
  안전순서열이 존재하지 않는 상태를 말한다. 교착상태는 불안전상태에서만 발생하지만 불안전상태라고 해서 무조건 교착상태가 발생하는 것은 아니다.

은행가 알고리즘은 할당할 수 있는 자원의 수와 사용자 수가 일정해야 하고, 항상 불안전 상태를 방지해야 하므로 자원 이용도가 낮다.
그리고 최대 자원 요구량을 미리 알아야 하며, 프로세스는 유한한 시간 안에 자원을 반납해야 하는 등 엄청 복잡한 알고리즘이다. 따라서 현재 채택하고 있는 방식은 아니다.

교착 상태 탐지

탐지 알고리즘을 사용하여 교착상태가 발생했는지 탐지하고, 교착 상태가 탐지되었다면 복구 기법을 통해 교착상태를 복구한다.

자원할당 그래프를 통해서 교착 상태를 탐지할 수 있다.

• 프로세스 Pi → 자원 Rj : Pi가 Rj를 요청하는 것으로 현재 이 자원을 기다리는 상태
• 자원 Rj → 프로세스 Pi : Rj가 Pi에 할당된 것을 의미한다.

자원을 요청할 때마다 탐지 알고리즘을 실행하므로 오버헤드가 발생하여 실용적이지는 못하다.

교착 상태 회복

교착 상태를 일으킨 프로세스를 종료하거나 할당된 자원을 해제함으로써 회복한다.

• 프로세스를 종료하는 방법
  교착 상태의 프로세스를 모두 중지한다. 프로세스 재실행 비용이 큰 방법이다.
  교착상태 탐지 알고리즘을 수행해 오버헤드가 크고, 중지할 프로세스 선택 문제가 복잡하다.

• 자원을 선점하는 방법
  교착 상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하고 해당 프로세스를 일시정지시키는 방법이다.
  우선순위가 낮거나 수행된 횟수가 적은 프로세스 등을 위주로 프로세스의 자원을 선점한다.

기아 상태

특정 프로세스의 우선순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태

• 교착상태 : 프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태

• 기아 상태 : 프로세스가 원하는 자원을 계속 할당 받지 못하는 상태

교착 상태는 여러 프로세스가 동일한 자원 점유를 원할 때 발생하고 기아 상태는 여러 프로세스가 자원을 점유하기 위해 경쟁 할 때 특정 프로세스는 영원히 자원 할당을 받지 못하는 것이다.
기아 상태는 오래동안 대기 상태인 프로세스의 우선순위를 높이는 에이징 기법을 통해 해결할 수 있다.

식사하는 철학자 문제

교착상태와 기아상태를 설명하는 대표적인 문제이다.
철학자 다섯명이 원형 식탁에 앉아 식사를 하려고 한다.
그들의 양쪽에는 각각 젓가락이 하나씩 놓여있고, 밥을 먹으려고 할 때는 다음의 과정을 따른다.

1. 왼쪽 젓가락부터 집어든다.다른 철학자가 이미 왼쪽 젓가락을 사용하고 있다면
   내려놓을 때 까지 대기한다.
2. 왼쪽을 들었으면 오른쪽 젓가락을 든다. 들 수 없다면 대기한다.
3. 두 젓가락을 모두 들었다면 일정시간 동안 식사를 한다.
4. 식사를 마쳤으면 오른쪽 젓가락을 내려 놓은 후 왼쪽 젓가락을 내려놓는다.
5. 다시 배고프면 1번부터 진행한다.

이러한 프로세스는 교착상태 발생의 4가지 필요조건을 모두 만족한다.

• 상호배제 : 젓가락은 한 번에 한 철학자만 사용할 수 있다.

• 점유와 대기 : 왼쪽 젓가락을 점유하면서 오른쪽 젓가락을 대기한다.

• 비선점 : 누군가 집어든 젓가락을 뺏을 수 없다.

• 환형 대기 : 모든 철학자들이 오른쪽에 앉은 철학자가 젓가락 놓기를 기다린다.

만약 모든 철학자가 동시에 배가 고파서 왼쪽 젓가락을 집어든다면, 모든 철학자의 오른쪽 젓가락은 이미 자신의 오른쪽에 앉은 철학자가 집어들었을 것이므로 모두가 영원히 오른쪽 젓가락을 들지 못하게 된다.
그렇게 되면 상단 과정의 2번에서 더이상 진행하지 못하고 철학자들은 영원히 생각에 빠지게 되는데 이런 상태를 교착상태라고 한다.
또한 어떤 경우에는 젓가락 양쪽을 동시에 집을 수 없어서 식사를 하지 못하는 기아상태가 발생할 수도 있다.

해결 방법

• n명이 앉을 수 있는 테이블이라고 가정했을 때 n-1명의 철학자만 앉힌다.
  무조건 1개 이상의 젓가락은 대기상태로 있어야 하기 때문에 어떤 철학자는 무조건 식사가 가능하게 된다.

• 한 철학자가 젓가락 두개를 모두 집을 수 있는 상황에서만 젓가락 집는 것을 허용한다. (점유와 대기 제거)

• 누군가는 왼쪽 젓가락을 먼저 집고, 누군가는 오른쪽 젓가락을 먼저 집게 한다. (환형 대기 제거)

이러한 방법들은 교착상태는 해결해주지만 기아현상까지 해결해주지는 못한다.

Reference

https://ko.wikipedia.org/wiki/%EA%B5%90%EC%B0%A9_%EC%83%81%ED%83%9C
https://m.blog.naver.com/minimilla/20200414427
https://m.blog.naver.com/hirit808/221788147057
https://jhnyang.tistory.com/102