24_교착 상태(Deadlock)

24_교착 상태(Deadlock)

 

다중 프로그래밍 환경에서 여러 프로세스들이 한정된 자원을 사용하려고 서로 경쟁 할 수 있다. 한 프로세스가 자원을 요청 했을 때 그 시각에 그 자원을 사용할 수 없는 상황이 발생할 수 있고 그 때는 프로세스가 대기 상태로 들어 간다. 이처럼 대기중인 프로세스들이(요청된 프로세스가 다른 프로세스에 의해 대기) 다시는 그 상태를 변경 시킬 수 없으며 이러한 상황을 교착 상태라 한다.

 

교착 상태는 한 시스템 내에서 다음의 조건이 동시에 설립 될 때 발생한다.

• 상호 배제(Mutual exclusion) : 최소한 하나의 자원이 비공유 모드로 점유되어야 한다. 비공유 모드에서는 한 번에 한 프로세스만이 그 자원을 사용할 수 있다. 다른 프로세스가 그 자원을 요청하면 요청 프로세스는 자원이 방출 될 때까지 반드시 지연되어야 한다.
• 점유 대기(hold and wait) : 프로세스는 최소한 하나의 자원을 점유한 채 현재 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기해야 한다.
• 비선점(No preemption) : 자원들을 선점할 수 없어야 한다. 자원이 강제적으로 방출될 수 없고 점유하고 있는 프로세스가 태스크를 종료 한 후 그 프로세스에 의해 자발적으로만 방출 될 수 있다.
• 순환대기(Circular wait) : 대기하고 있는 프로세스의 집합 {P0, P1, ,…Pn}에서 P0는 P1이 점유한 자원을 대기하고 P1은 P2가 점유한 자원을 대기하고 P2…Pn-1은 Pn이 점유한 자원을 대기하며 Pn은 P0가 점유한 자원을 대기 한다.

 

 

교착 상태는 시스템 자원 할당 그래프라고 하는 방향 그래프로 보다 정확하게 기술할 수 있다. 그래프는 정점(vertex) v의 집합과 간선(edge) E의 집합으로 구성된다.

 

• 프로세스 Pi로부터 자원유형 Rj로의 방향 간선은 Pi ->Rj로 표현하며 이것은 프로세스 Pi가 자원 유형 Rj의 인스턴스를 하나 요청하는 것으로 현재 이 자원을 기다리는 상태이다. (요청 간선(request edge)라 부른다.)
• 자원 유형 Rj로부터 프로세스 Pi로의 방향 간선은 Rj->Pi로 표현하며 이것은 자원 유형 Rj의 한 인스턴스가 프로세스 Pi에 할당된 것을 의미 한다. (할당 간선(assignment edge)이라 부른다.)

 

[교착 상태의 자원 할당 그래프]

 

P3가 자원유형 R2의 인스턴스를 하나 요청한다. 사용 가능한 자원이 없기 때문에 요청 간선 P3 -> R2를 그래프에 추가한다. 이 시점에서 시스템 내에 두 개의 최소의 사이클이 존재 한다. 프로세스 P1, P2, P3는 교착 상태이다. 프로세스 P2는 프로세스 P3를 점유하고 있는 자원 R2를 기다린다. 프로세스 P3은 프로세스 P1이나 P2가 자원 R2를 방출하기를 기다린다. 프로세스P1은 P2가 자원 R1을 방출하기를 기다린다.

 

[교착 상태 처리]

교착 상태를 처리하는 방법에는 세 가지 방법이 있다.

• 시스템이 결코 교착 상태가 되지 않도록 보장하기 위하여 교착상태를 예방하거나 회피하는 프로토콜을 사용
• 시스템이 교착상태가 되도록 허용한 다음에 회복시키는 방법
• 문제를 무시하고 교착 상태가 시스템에서 결코 발생하지 않는 척 한다.

 

 

[교착 상태 예방(Deadlock Prevention)]

• 상호배제(Mutual Exclusion) : 상호 배제 조건은 불가능한 자원에 대해서는 반드시 성립해야 한다.
• 점유 대기(Hold and wait) : 프로세스가 자원을 요청 할 때는 다른 자원들을 점유하지 않을 것을 반드시 보장해야 한다. 이용할 수 있는 한가지 프로토콜은 각 프로세스가 실행되기 전에 자신의 모든 자원을 요청하고 할당 받을 것을 요구 한다. 한 프로세스를 위해 자원을 요청하는 시스템 호출이 모든 다른 시스템 호출에 앞서 나타날 것을 요구함으로써 이 규정을 구현 할 수 있다.
• 비전섬(No Preemption) : 이미 할당된 자원이 선점되지 않아야 한다. 어떤 자원을 점유하고 있는 프로세스가 즉시 할당할 수 없는 다른 자원을 요청하면 현재 점유하고 있는 모든 자원들이 선점된다. 즉 이 자원들이 묵시적으로 방출된다.
• 순환대기(Circular Wait) : 모든 자원 유형들에게 전체적인 순서를 부여하여 각 프로세스가 열거된 순서대로 오름차순으로 자원을 요청하도록 요구.

 

[교착 상태 회피 (Deadlock Avoidance)]

교착 상태를 위해 필요한 조건 중 최소한 하나가 발생하지 않도록 보장하여 교착상태가 성립하지 못하게 한다. 이러한 방식의 교착 상태 예방은 장치의 이용률이 저하되고 시스템 처리율이 감소 되는 문제가 있다.

 

교착 상태를 회피하는 다른 대안은 자원이 어떻게 요청 될지에 대한 추가 정보를 제공하도록 요구하는 것이다. 각 요청에 대해 대기하는 결정을 하기 위해 현재 가용 자원, 현재 각 프로세스에 할당된 자원, 각 프로세스가 앞으로 요청하거나 방출할 자원을 고려해야 한다.

 

[교착 상태 탐지(Deadlock Detection)]

시스템의 교착 상태를 방지 하기 위해 교착 상태가 발생하였는지 검사하는 알고리즘과 교착 상태로부터 회복하는 알고리즘을 지원해야 한다.

 

모든 자원들이 한 개의 인스턴스만 있다면 대기 그래프라고 하는 자원 할당 그래프의 변형을 사용해 교착 상태 탐지 알고리즘을 정의할 수 있다. 자원 할당 그래프로부터 자원 유형의 노드를 제거하고 적절한 간선들을 결합함으로써 대기 그래프를 얻을 수 있다.

 

 

 

대기 그래프는 각 종류마다 자원이 여러 개씩 존재하는 상황에서는 사용할 수 없다.

 

교착 상태가 자주 발생한다면 탐지 알고리즘도 자주 돌려야 한다. 교착 상태가 된 프로세스로부터 자원을 회수하기까지는 그 자원들은 아무도 못 쓰는 자원으로 묶이게 되며 시간이 더 경과하면 교착 상태에 연루되는 프로세스의 수도 늘어 날 수 있다.

 

자원을 요청 할 때마다 탐지 알고리즘을 실행하면 오버헤드가 발생한다. 오버헤드를 방지하기 위하여 가끔 탐지 알고리즘을 실행하면 한꺼번에 여러 개의 사이클이 탐지될 수도 있다. 이 경우 어느 프로세스가 최종적으로 교착 상태를 발생시키는지 알 수 없게 된다.

 

[교착 상태로부터 회복(Recovery from Deadlock)]

프로세스 종료 (Process Termination)

• 교착 상태의 프로세스를 모두 중지 : 이 방식은 확실하게 교착 상태의 사이클을 깨뜨리지만 비용이 크다. 이 프로세스들은 오랫동안 연산했을 가능성이 있으며 이들 부분 계산의 결과들을 반드시 폐기해야 하며 이후 다시 계산해야 하기 때문이다.
• 교착 상태가 제거 될 때까지 한 프로세스씩 중지 : 각 프로세스가 중지 될 때마다 교착 상태 탐지 알고리즘을 호출해 프로세스들이 아직도 교착 상태에 있는지 확인해야 하기 때문에 오버헤드가 발생

 

자원 선점 (Resource Preemption)

• 희생자 선택(Selecting a victim) : 프로세스 종료와 같이 비용을 최소화하기 위해 선점 순서를 결정해야 한다. 비용요인으로는 교착 상태 프로세스가 점유하고 있는 자원의 수 그리고 교착 상태 프로세스가 지금까지 실행하는데 소요한 시간과 같은 매개변수들이 포함될 수 있다.
• 롤백(Rollback) : 일반적으로 안전 상태가 어떤 것인지 결정하기 어렵기 때문에 가장 단순한 해결안은 완전히 롤백 하는 것이다. 즉 프로세스를 중지(abort)하고 다시 시작하는 것이다. 그로나 프로세스를 단지 교착 상태만 깨뜨릴 정도로 롤백 할 수 있다면 매우 효과적이다. 반면에 이 방식은 시스템이 실행하는 모든 프로세스들의 상태에 대한 보다 많은 정보를 유지할 것을 필요로 한다.
• 기아 상태(Starvation) : 희생자의 선택이 주로 비요 요인에 근거한 시스템에서는 동일한 프로세스가 항상 희생자로 선택 될 수 있다. 그 결과 이 프로세스는 자신의 태스크를 결코 완료하지 못하는 기아 상태에 있게 되며 이러한 문제는 모든 실용적인 시스템에서 해결해야 할 문제이다. 대부분의 일반적인 해결 방법은 비용 요소에 롤백의 회수를 포함시키는 방법이다.

 

 

[참고자료]

Operating System Concepts / 홍릉과학출판사