교착상태의 특성
•
Deadlock의 발생 조건은 4가지가 있다.
◦
상호 배제(Mutual exclusion)
▪
자원은 한 번에 하나의 프로세스만이 사용할 수 있어야 한다.
◦
점유 대기(Hold and wait)
▪
최소 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.
◦
비선점(No preemption)
▪
다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다.
◦
순환 대기(Circular wait)
▪
프로세스의 집합이 있다면 P1→P2→…→P1→P2 순으로 프로세스가 각자의 자원을 점유하고 있으며 다른 프로세스가 가진 자원을 대기하는 순환이 발생해야 한다.
•
교착상태를 시스템 자원 할당 그래프로 표현하면 아래와 같다.
◦
스레드(T)에서 자원(R)으로 향하는 화살표는 요청 간선(request edge)라 부르고, 자원(R)에서 스레드(T)로 향하는 간선을 할당 간선(Assingment edge)라 부른다.
교착 상태 처리 방법
•
Prevention(예방)
◦
교착 상태의 발생 조건 중 하나를 미리 제거함으로써 해결하는 방법이다.
◦
상호 배제(Mutual exclusion) 부정
여러 개의 프로세스가 공유 자원을 동시에 사용할 수 있도록 한다.
◦
점유 대기(Hold and wait) 부정
프로세스가 실행되기 전 필요한 모든 자원을 할당한다.
◦
비선점(No preemption) 부정
자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때는 점유하고 있는 자원을 반납 후 다른 자원의 반납을 기다리도록 한다.
◦
순환 대기(Circular wait) 부정
자원에 고유한 번호를 할당하고 번호 순서대로 자원을 요구하도록 한다.
◦
자원의 낭비가 매우 심하다.
•
Avoidance(회피)
◦
교착 상태가 발생하면 해당 상황을 피해가는 방법으로, 프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있는지(교착 상태가 발생하지 않는지) 사전에 검사하여 교착 상태를 회피하는 방법이다.
◦
안정 상태(safe state)
▪
프로세스들이 요구하는 모든 자원을 교착 상태 없이 모두 할당할 수 있다면 안정 상태에 있다고 말한다.
◦
안전 순서(safe sequence)
▪
특정한 순서로 프로세스들에게 자원을 할당하고 실행 및 종료 등 작업을 할 때 교착 상태가 발생하지 않는 순서를 안전 순서라고 부른다.
▪
대표적으로 은행원 알고리즘이 있으며, 회피 방식은 미리 최대 자원 요구량을 알아야하고 할당할 수 있는 자원 수가 일정해야 하는 등의 사용 조건에 제약이 많다. 또한 사용 조건 제약에 따른 자원의 이용률이 낮아진다는 단점도 있다.
◦
자원 할당 그래프 알고리즘을 통한 방법이나 은행원 알고리즘(Banker’s Algorithm)이 회피 방법에 속한다.
•
교착 상태 탐지 및 회복
◦
교착 상태가 되도록 허용한 다음 교착 상태가 발생하면 회복시키는 방법으로, 대부분의 시스템은 교착 상태가 잘 발생하지 않고 교착 상태를 예방, 회피하는 것은 비용이 많이 들기 때문에 사용하는 방법이다.
◦
탐지 기법
▪
현재 시스템의 자원 할당 상태를 확인하여 시스템에 교착 상태가 발생했는지를 파악한다.
◦
회복 기법
▪
교착 상태가 발생했다면, 순환 대기 상태에서 벗어나 교착 상태를 회복한다. 순환 대기를 벗어나는 방법은 프로세스를 1개 이상 중단시키거나, 프로세스에 할당된 자원을 뺏어와(선점) 교착 상태가 해결될 때까지 해당 자원을 다른 프로세스에 할당해주는 방법이 있다.
▪
자원을 요청할 때마다 교착 상태가 발생했는지 확인하는 탐지 알고리즘을 실행하기 때문에, 그에 따른 오버헤드가 발생한다.