교착상태와 기아상태

교착상태(Deadlock)

교착상태에 대해서 배워보자. 만약에, 프로세스 동기화에 대한 지식이 없다면 해당 링크를 통해서 배우고오자.

교착상태란

Wikipedia - 교착상태란 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다. 예를 들어 하나의 사다리가 있고, 두 명의 사람이 각각 사다리의 위쪽과 아래쪽에 있다고 가정한다. 이때 아래에 있는 사람은 위로 올라 가려고 하고, 위에 있는 사람은 아래로 내려오려고 한다면, 두 사람은 서로 상대방이 사다리에서 비켜줄 때까지 하염없이 기다리고 있을 것이고 결과적으로 아무도 사다리를 내려오거나 올라가지 못하게 되듯이, 전산학에서 교착 상태란 다중 프로그래밍 환경에서 흔히 발생할 수 있는 문제이다. 이 문제를 해결하는 일반적인 방법은 아직 없는 상태이다.

필요 조건

교착상태가 발생하려면 아래 4가지 조건을 모두 충족 시켜야 한다.

• 상호 배제(Mutual Exclusion)
  • 한 번에 한 프로세스만 해당 자원을 사용할 수 있어야 한다.
  • 다른 프로세스가 그 자원을 요청하면, 요청 프로세스는 자원이 방출될 때 까지 지연되어야 한다.
• 점유와 대기(Hold and Wait)
  • 프로세스는 최소한 하나의 자원을 점유한 채, 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해선 대기해야 한다.
  • 할당된 자원을 가진 상태에서 다른 자원을 기다리는 상태를 의미한다.
• 비선점(No preemption)
  • 자원들을 선점할 수 없어야 한다.
  • 다른 프로세스가 자원의 사용을 끝낼 때 까지 자원을 뺏을 수 없다.
• 순환대기(Circular wait)
  • 프로세스 P1, P2, P3 가 있을 때 P1은 P2가 점유한 자원을 대기하고 P2는 P3가 점유한 자원을 대기하는 현상을 말한다.
  • 각 프로세스가 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있는 상태를 의미한다.

자원 할당 그래프(Resource-Allocation Graph)

교착 상태는 자원 할당 그래프로 표현할 수 있다. 자원 할당 그래프는 정점(Vertex)과 간선(Edge)의 집합으로 이루어져 있다.

정점의 집합은 두 종류이다.

• 프로세스 집합(P1, P2, P3 ...)
  • 각각의 프로세스는 그래프에서 원으로 표시
• 자원의 집합(R1, R2, R3 ...)
  • 각각의 자원은 그래프에스 사각형으로 표시
  • 자원이 갖는 인스턴스는 사각형 내의 점으로 표시

간선도 두 종류이다.

• P(i) -> R(k) : 요청 간선(Request Edge)
• R(k) -> P(i) : 할당 간선(Assignment Edge)

프로세스 P 는 원으로 표현하고 자원 R 은 사각형으로 표시한다. 자원 R(k) 가 갖는 인스턴스는 사각형 내의 점으로 표시한다. 따라서, 할당 간선은 사각형 내의 하나의 점을 갖게 된다. 반면 요청 간선은 사각형 만을 가리킨다.

교착상태를 갖지 않는 그래프

위 그림을 수식으로 표현하면 다음과 같다.

교착 상태를 갖지 않는 그래프의 특징은 사이클(cycle)을 포함하지 않는다는 것이다. 반면, 사이클을 포함한다고 하면 교착상태가 존재할 수 있다. 말 그대로, 존재할 수도 있다는 것이다. 사이클이 있더라도 교착 상태가 발생하지 않을 수 있는데 그림을 통해서 확인하자.

사이클이 있으면서 교착상태를 갖는 그래프

그래프를 보면 알겠지만 현재 사이클이 발생하며, P1, P2, P3 는 현재 교착상태이다. P1 은 P2 가 점유하고 있는 R1 내의 자원을 방출하기 까지 기다린다.

사이클이 있으면서 교착상태를 갖지 않는 그래프

위의 경우에는 사이클이 발생하지만 교착상태를 갖진 않는다.

정리하자면, 자원 할당 그래프에 사이클이 존재하지 않으면 교착상태가 아니다. 만약 사이클이 존재하면 교착상태 일 수도 있고, 아닐 수도 있다.

교착상태 해결 방법

교착상태(Deadlock)을 해결하기 위한 방안은 다음과 같다.

• 교착상태가 되지 않도록 하기 위해 예방 또는 회피 기법 사용
• 교착상태를 허용한 다음 회복하는 기법 사용
• 교착상태를 무시하는 기법 사용

예방(Preventation)

교착상태가 발생하기 위해서는 4가지 조건(상호 배제, 점유와 대기, 비선점, 순환 대기)을 모두 만족해야 했다. 따라서 교착상태 예방은 이 4가지 조건 중 최소 하나라도 발생하지 않도록 예방하는 기법을 의미한다.

상호 배제

상호 배제를 방지하기 위해서는 공유 가능한 자원을 이용하는 것이다. 예를 들면 읽기 전용 파일 등인데, 우리는 깃허브 Repository 에 들어있는 파일을 읽기 위해 파일을 여는데, 해당 파일은 동시 접근을 허용하기 때문에 프로세스는 공유 가능한 자원을 위해 대기할 필요가 없어진다.

상호 배제의 단점은 모든 자원들이 항상 공유 가능하다는 것은 아니다. 공유가 불가능한 경우도 있다. 예를들면 Mutex Locks 의 경우에는 동시에 여러 프로세스들이 공유할 수 없다.

점유와 대기

점유하며 대기하는 조건이 발생하지 않도록 하기 위해서는 프로세스가 자원을 요청할 때, 다른 자원들을 점유하지 않을 것을 보장해야 한다. 점유와 대기를 예방하기 위한 두 가지 방안은 다음과 같다.

• 각 프로세스가 실행되기 전에 자신의 모든 자원을 요청하고 할당 받을 것을 요구한다.
  • Ex. 시험전에 책 3권으로 공부할 예정인데 책 3권중 1권이 아직 배송중이라 그 책 한권이 도착할때 까지 공부하지 않고 기다린다.
  • 이 경우에는 나머지 책이 배송중 파손으로 인해서 배송지연이 되면 책 한권이 도착하기 까지 공부를 못할 수 있다.
• 프로세스가 자원을 전혀 갖고 있지 않은 경우에만 자원을 요청할 수 있다.
  • Ex. 시험전에 책 3권으로 공부할 예정인데 책 3권중 2권은 보유상태이다. 2권에 대한 공부를 마친 후 나머지 책 한권을 주문할 수 있다.
  • 이 경우에는 자신이 갖고 있는 자원들(책 2권)에 대해서만 시간표를 짜서 진행해야 하기 때문에, 공부 효과가 떨어질 수 있다.

즉, 점유와 대기도 위와 같은 단점을 갖고 있다.

비선점

이미 할당된 자원이 선점되지 않아야 한다는 것이다. 하지만 비선점 조건 사용시 어떤 프로세스든 중간에 해당 자원을 사용할 수 있어서 기존에 사용중이던 작업 내용을 잃을 수도 있다.

비선점 예방 또한 Mutex 락과 세마포 같은 자원에는 적용할 수 없다.

순환 대기

순환 대기 조건이 성립되지 않도록 하기 위해선 모든 자원에 순서를 부여하여, 프로세스가 오름차순으로 자원을 요청하도록 요구하는 방법이다. 예를 들어, 컴퓨터를 사용하기 위한 프로세스는 반드시 본체-모니터-마우스-키보드 등의 순서로 자원을 요구해야 하는데, 단점이 단 한번의 요청으로 모든 자원을 할당 받아야 한다는 것이다.

이러한 교착상태 예방(Preventation)방법들에 대한 단점들로 인해서, 교착상태 회피(Avoidance)라는 기법이 나오게 되었다.

회피(Avoidance)

회피 기법이 어떻게 교착상태를 예방할 수 있는지 이해하기 위해서는 몇 가지 선수 지식이 필요하다.

안전 상태(Safe State)

안전(Safe) 하다라는 의미는 프로세스들이 요청하는 모든 자원을 교착상태를 일으키지 않고 차례로 모두 할당해 줄 수 있다는 것 을 뜻한다.

시스템이 안전 순서(Safe Sequence)를 찾을 수 있다면 안전(Safe)하다고 말한다.

안전 순서를 찾을 수 있다라는 의미는 {P(1), P(2), P(3) ... P(N)} 과 같은 process sequence 가 안전하다라는 의미이다. 즉, 모든 P(i) 가 요청하는 자원을 시스템에 남아있는 자원과 P(k) 들이 수행을 마치고 반납할 자원들로 프로세스의 요청을 교착상태를 일으키지 않고 할당해주는 것을 의미한다.

만약에 process sequence 가 불안전(unsafe)하다면, 교착상태가 발생할 수도 있다. 무조건 발생한다라는 것은 아니다.

즉, 회피 기법은 항상 안전 상태를 유지하도록 하는 것이다.

자원 할당 그래프 알고리즘

회피 기법을 사용하기 위한 알고리즘 중 하나로 자원 할당 그래프 알고리즘이 있다. 위에서 배운 그래프에서는 요청 간선과 할당 간선밖에 없었지만, 여기서는 예약 간선(점선)이 추가된다. P(i) -> R(k) 이렇게 표기하며, P(i) 가 R(k) 에게 미래에 자원을 요구할 것이라는 의미이다.

이 그래프에서, P(2) 가 R(2) 에게 요청을 하지만 사이클이 발생하기 때문에 인스턴스를 할당해 줄 수 없다. 즉, 이 그래프에서 안전한지 검사하기 위해서 사이클 탐지(cycle detection) 알고리즘을 이용한다.

은행원 알고리즘

은행원 알고리즘도 회피 기법을 사용하기 위한 방법 중 하나이다. 은행원 알고리즘은 불안전 상태의 자원 할당 그래프의 경우에 사용할 수 있다.

불안전 상태의 자원 할당 그래프란 자원 할당 그래프 알고리즘에 나와있는 그림에서 R(2) -> P(2) 를 가리키는 경우가 추가된 것을 의미한다. 즉, 사이클이 발생한 경우를 의미한다.

은행원 알고리즘은 은행에서 사용되는 대출이 개개인에게 가능한지 확인하는 은행시스템에서 가져왔기 때문에 은행원 알고리즘이라고 불리게 되었다.

은행원 알고리즘을 사용하기 위해서는 몇가지 자료구조가 필요하다.

프로세스의 수를 Pn 이라 하고, 자원의 종류의 수를 Rn이라 하자.

Available

• 각 종류 별로 사용 가능한 자원의 개수를 나타내는 vector 이다. 크기는 Rn 이다.
• Ex. Available[i] = k : R(i) 를 k 개 사용 가능하다라는 것을 의미한다.

Max

• 각 프로세스가 최대로 필요로 하는 자원의 개수를 나타내는 행렬이다. 크기는 Pn x Rn 이다.
• Ex. Max[i, j] = k : P(i) 가 R(j) 를 최대 k 개 까지 요청할 수 있음을 의미한다.

Allocation

• 각 프로세스에게 현재 나가있는 자원의 개수를 나타내는 행렬이다. 크기는 Pn x Rn 이다.
• Ex. Allocation[i, j] = k : P(i) 가 R(j) 를 k 개 사용 중임을 의미한다.

Need

• 각 프로세스가 향후 요청할 수 있는 자원의 개수를 나타내는 행렬이다. 크기는 Pn x Rn 이다.
• Ex. Need[i, j] = k : P(i) 가 항후 R(j) 를 k 개 까지 더 요청할 수 있음을 의미한다.
• Need[i, j] = Max[i, j] - Allocation[i, j] 관계가 있음을 알 수 있다.

이 외에도, 회피 기법에는 안전성 알고리즘, 자원 요청 알고리즘 등이 있다.

탐지(Detection)

교창상태 탐지는 예방이나 교착상태 방지 알고리즘을 사용하지 않는경우에는 교착상태가 발생할 수 있기 때문에, 아래와 같은 방안들을 반드시 지원해야 한다.

• 교착상태가 발생했는지 결정하기 위해 시스템의 상태를 검사하는 알고리즘
• 교착상태로부터 회복하는 알고리즘

회복(Recovery)

탐지 알고리즘이 교착상태가 발생한다고 판단한다면, 시스템이 자동적으로 교착상태로부터 회복(Recovery)하게 할 수 있다.

첫 번째 방법은 순환 대기를 없애기 위해 한 개 이상의 프로세스를 중지(abort)하는 것이고, 두 번째 방법은 교착상태에 있는 하나 이상의 프로세스들로부터 자원을 선점(preempt) 하는 것이다.

자원 선점을 이용하여 교착상태를 제거하기 위해서는 다음과 같은 사항들을 고려해야 한다.

• 희생자 선택(selection of a victim)
  • 비용을 최소화 하기 위해 선점의 순서를 결정해야 한다.
• 후퇴(rollback)
  • 프로세스로부터 자원을 선점하려면, 해당 프로세스를 안전한 상태로 후퇴 시키고 다시 시작해야 한다.
• 기아 상태(starvation)
  • 기아 상태가 발생하지 않는다라는 것을 보장해야 한다.
  • 자원들이 동일한 프로세스로부터 항상 선점되지 않는다는 것을 보장해야 한다.
  • Aging 기법 사용

기아상태(Starvation)

기아상태(Starvation)란 특정 프로세스보다 우선순위가 낮아 원하는 자원을 계속 할당받지 못하는 상태이다. 주로 Priority scheduling 에서 일어난다.

Priority Scheduling : 모든 프로세스에 우선순위를 주고 그 우선순위에 다라서 CPU 가 할당되고 수행된다. 또 시간을 고려하지 않기 때문에 걸리는 시간이 짧아도 우선순위가 높은 프로세스에 할당된다.

• Aging
  • 기아상태를 회피하기 위해 낮은 우선순위를 가진 프로세스들을 기다린 만큼 우선순위를 높여주는 방법이다.

우선순위를 매겨서 실행하는 기법들을 사용할때는 Aging 기법이 필수이다.

References

• 운영체제 9th edition