Deadlock(교착상태)
둘 이상의 프로세스 혹은 스레드(작업)들이 서로 상대방이 사용중인 자원을 쓰기 위해 대기하고 있는 상황.
*병목현상과 혼동하지만 원인이 다르다. 병목 현상은 여러 구성 요소가 동시에 실행될 때, 가장 느린 쪽의 속도에 맞추기 위해 전체 시스템이 느려지는 상황.
*기아상태와도 혼동할 수있는데, 교착상태는 프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태를 말하고 기아 상태는 프로세스가 원하는 자원을 계속 할당 받지 못하는 상태이다. 즉 교착 상태는 여러 프로세스가 동일한 자원 점유를 원할 때 발생하고 기아 상태는 여러 프로세스가 자원을 점유하기 위해 경쟁 할 때 특정 프로세스는 영원히 자원 할당을 받지 못하는 것이다.
Deadlock 의 필요 조건
다음 4가지의 조건을 모두 만족해야 교착상태가 발생한다.
→ 즉, 한 가지 조건이라도 만족하지 못하게 한다면 교착상태를 해결할 수 있다.
1. 상호 배제(mutual exclusion)
매 순간 하나의 자원은 하나의 작업이 점유한다. 즉, 하나의 자원을 얻었다면 독점적으로 사용하며, 다른 작업이 해당 자원을 요청하면 자원이 방출될 때까지 지연(대기)한다.
2. 점유 대기(Hold-and-wait)
자원을 가진 작업이 하나의 자원을 가진 채 다른 자원을 기다릴 때, 현재 보유한 자원을 놓지 않고 계속 기다린다.
3. 비선점 (no preemption)
자원을 선점할 수 없다. 즉, 자원이 강제적으로 빼앗기지 않고, 작업이 끝난 이후 자발적으로만 반납(방출)된다.
4. 순환 대기(circular wait)
자원을 기다리는 작업들 간에 사이클이 형성되어야 한다. (1→2→3→1 )
Deadlock 처리 방법
1.
문제 무시
2.
예방
3.
회피
4.
교착 상태 허용 후 복구
대부분의 운영체제는 1번 방법, 무시를 택한다. 교착상태를 처리하는 프로그램을 작성하는 것은 응용 개발자의 몫이며, 통상 2,3번 접근법을 사용한다. DB와 같은 일부 시스템은허용 후 복구작업을 수행한다.
*현대 OS가 Deadlock을 처리하지 않고 무시하는 이유는?
1.
빈번히 발생하는 이벤트가 아니기 때문에 미연에 방지하기 위해 훨씬 더 많은 오버헤드를 들이는것이 비효율적이라고 판단함.
2.
현대 시스템의 복잡성으로 인해 교착 상태를 완전히 방지하는 것은 불가능
3.
만약 시스템에서 deadlock이 발생한 경우 시스템이 비정상적으로 작동한것을 사람이 느낀후 직접 process를 죽이는 방법으로 대처
예방(Prevention)
데드락을 발생시키는 4가지 조건 중 적어도 하나가 성립하지 않도록 보장하는 방법
•
상호 배제
◦
자원을 작업들이 동시에 사용할 수 있게 하는 방법. 이를 사용하면 동시에 접근이 가능하여 교착상태가 일어나지 않는다.
◦
불가능하다. 어떤 자원은 근본적으로 공유가 불가능(mutex 락, 프린터 등)하고, 동기화에 문제가 생길 수 있다.
•
점유 대기
◦
작업이 자원을 요청할 때마다 다른 자원을 보유하지 않도록 보장. 즉, 하나의 프로토콜이 필요한 모든 자원을 요청하고 할당해야 한다.
▪
자원 이용률이 낮아진다. 요청만 해놓고 안쓰는 자원이 많아진다.
▪
기아상태가 발생할 수 있다. 무한정 대기해야 하는 상황이 발생할 수 있다.
•
비선점
◦
이미 다른 작업이 가지고 있는 자원을 선점한다. 모든 자원을 얻을 수 있을 때, 그 작업이 다시 시작된다.
◦
CPU레지스터나 DB트랜젝션처럼, 그 상태가 쉽게 저장되고 복원될 수 있는 자원에 종종 적용된다. 가장 흔하게 교착상태가 발생하는 mutex 락이나 세마포 같은 자원에는 일반적으로 적용할 수 없다.
•
순환대기
◦
모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당한다.
◦
현실적인 접근 방법 (공룡책 의견)
데드락을 예방하는 방법은 자원의 낭비가 극심하기 때문에 좋은 방법은 아니다.
회피(Avoidance)
데드락 발생 가능성을 계속 검사하여 가능성이 있다면 회피하는 방식
이를 위해서는
•
현재 가용 자원
•
각 작업에 할당된 자원
•
각 작업이 필요한 자원
을 고려해야 하며, 작업은 필요한 자원을 모두 사용한 후 한번에 해제한다는 가정을 전제로 해야 한다.
안전상태(safe state) 유지
시스템의 상태가 안전하다는 것은, 교착상태를 야기시키지 않고 차례로 자원을 모두 할당해줄 수 있는 순서가 존재하는 상태이다.
사용 가능한 자원은 총 12개, 3개의 프로세스가 존재하며, 9개의 자원은 아래 표와 같이 할당되었을 때 아래 표의 안전 상태를 점검해보자.
시스템의 상태가 항상 안전상태를 유지하도록 고수한다. 작업이 자원을 요청하면, 시스템은 상태가 안전상태인지 확인하고 할당해준다. 물론, 작업이 기다려야 하는 상황이 생기므로 회피를 안 쓸 때에 비해서 이용률이 낮아질 수 밖에 없다.
자원할당그래프(Resource Allocation Graph) 알고리즘
예약 간선(Claim edge) 를 도입. 미래에 자원을 요청할 것을 의마하는 점선으로 표시
R은 자원, P는 작업. R→P 는 할당간선, P→R은 요청간선이다.
위와 같은 상황에서, 점선이 없다면 위 상태는 safe하다. P1이 R1을 해제하면 P2가 R1을 사용할 수 있기 때문이다.
하지만, Claim Edge(예약간선, 점선)을 고려한느 순간 위 상태는 두가지 상태로 바뀌게 된다.
위처럼 두가지 케이스가 나오는데, Case1 의 경우에만 안전하기 때문에, 사이클이 존재하는 Case2는 무시되며, Case1 이 채택된다.
*사이클이 존재하면 불안전하다.
은행원 알고리즘 (Banker’s Algorithm)
자원 할당 그래프 알고리즘은 종류마다 자원이 여러개(R_A, R_B…)씩 있게 되면 사용할 수 없으므로, 은행원 알고리즘을 사용할 수 있다.
은행원 알고리즘은 각 작업이 필요로 하는 자원의 최대값과 현재 할당된 자원의 양을 바탕으로 안전상태를 유지할 수 있는지 여부를 판단한다.
하지만, 모든 프로세스가 최대 자원을 요구할 때는 안정적인 상태를 유지할 수 없으므로 이러한 경우에는 교착상태가 발생할 가능성이 있으므로 다른 방법을 사용하여 교착상태를 방지 필요
1.
각 프로세스가 필요로 하는 자원의 최대값(Max)과 현재 할당된 자원의 양(Allocation)을 입력받습니다.
2.
시스템에서 가용 자원의 양(Available)을 입력받습니다.
3.
각 프로세스가 요청할 자원의 양(Request)을 입력받습니다.
4.
시스템은 Request 자원을 할당받았을 때 교착상태가 발생하지 않는지 여부를 판단합니다.
•
Request <= Available : Request 자원을 할당받았을 때 안전상태를 유지할 수 있다면, 자원을 할당하고 프로세스를 실행합니다.
•
Request > Available : Request 자원을 할당받았을 때 안정적인 상태를 유지할 수 없다면, 자원을 할당하지 않고 대기합니다.
5.
프로세스가 자원을 사용하고 반환할 때, Available 자원의 양을 갱신합니다.
탐지 및 복구(Detection and Recovery)
탐지 기법
1.
각 유형의 자원이 하나씩만 있는 경우
a.
대기 그래프 사용. 자원 할당 그래프에서 자원을 없애고 얻을 수 있음.
2.
각 유형의 자원을 여러 개 가진 경우
a.
Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 여부를 탐색한다. 즉, 은행원 알고리즘에서 했던 방식과 유사하게 현재 시스템의 자원 할당 상태를 가지고 파악
복구 기법
1.
프로세스와 스레드의 종료
a.
교착상태의 작업 모두 중지
i.
확실하게 사이클을 깨뜨리지만, 비용이 크다.
b.
교착상태가 제거될 때까지 하나씩 중지
i.
하나의 작업이 중지도리 때마다 교착상태 탐지 알고리즘을 호출해야 하므로 상당한 오버헤드를 유발한다.
2.
자원 선점
교착 상태가 깨질 때까지 자원을 계속 선점하여 다른 작업에 주어야 한다.
