Dead Lock
정의
2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태를 교착 상태(dead lock)라고 한다. 서로 비켜주기를 기다리며 꼼짝 못하는 상태이다.
아사 현상과 비슷해 보이지만 차이가 있다.
- 아사 현상 : 운영체제가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제
- 교착 상태 : 여러 프로세스가 작업을 진행하다 보니 자연적으로 일어나는 문제.
따라서 운영체제는 감시를 하다 교착 상태 발생시 강압적으로 해결해야 한다.
Dead Lock 발생
- 교착 상태는 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생한다.
- 예를 들어 P1이 프린터를 할당 받고 레코더를 기다리고, P2가 레코더를 할당받고 프린터를 기다리면 교착 상태에 걸린다.
- 공유 변수를 사용할 때도 발생한다. 이는 예전 한정 대기의 코드와 같이 둘 다 임계구역에 진입하고 반복문을 나오지 못하는 경우이다.
- 데이터베이스 같은 응용 프로그램에서도 교착 상태가 발생한다. 데이터베이스는 일관성 유지를 위해 잠금을 사용하는데, 이때 교착상태가 발생할 수 있다.
Dead Lock 필요 조건
교착 상태 필요 조건 (4가지 다 충족해야함)
- 상호 배제 : 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다.
- 비선점 : 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.
- 점유와 대기 : 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다.
- 원형 대기 : 점유와 대기를 하는 프로세스 간의 원을 이루어야 한다.
Dead Lock 해결 방법
에방(prevention), 회피(avoidance), 검출(detection)이며, 추가적으로 교착 상태가 발견된 후에 자원을 회복(recovery)하는 방법도 있다.
| 해결 방법 | 특징 |
|---|---|
| 교착 상태 예방 | 교착 상태를 유발하는 네 가지 조건을 무력화한다. |
| 교착 상태 회피 | 교착 상태가 발생하지 않는 수준으로 자원을 할당한다. |
| 교착 상태 검출과 회복 | 자원 할당 그래프를 사용하여 교착 상태를 발견한다. |
| 교착 상태 회복 | 교착 상태를 검출한 후 해결한다. |
- 교착 상태 예방 : 교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화 하는 방식. 실효성이 적어 잘 사용하지 않음
- 교착 상태 회피 : 자원 할당량을 조절하여 교착 상태를 해결하는 방식. 자원을 할당하다가 교착 상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중단하고 지켜보기. 하지만 보장할 수 없기 때문에 실효성 적음.
- 교착 상태 검출과 회복 : 교착 상태 검출은 어떤 제약을 가하지 않고 자원 할당 그래프를 모니터링. 교착 상태 발생시 회복 단계 진행. 가장 현실적인 접근 방법이다.
예방
- 상호 배제 예방은 독점적으로 사용할 수 있는 자원을 없애버리는 방법이다. 현실적으로 모든 자원 공유 불가.
- 비선점 예방은 모든 자원을 빼앗을 수 있도록 만드는 방법이다. 사실상 불가능하다.
- 점유와 대기 예방은 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법이다. 즉 사용하려는 모든 자원을 모두 점유하거나 아니면 모두 반납하거나 둘 중하나이다. 결국 일괄 작업이므로 비효율적이다.
- 원형 대기 예방은 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법이다. 즉 우선순위를 매긴다는 뜻이다. 유연성이 떨어지고 자원의 우선 순위를 정하기가 힘들다.
회피
은행원 알고리즘
다익스트라씨가 또 발명했다.
| 변수 | 설명 |
|---|---|
| 전체 자원(Total) | 시스템 내 전체 자원의 수 |
| 가용 자원(Available) | 시스템 내 현재 사용할 수 있는 자원의 수(가용 자원=전체 자원 - 모든 프로세스의 할당 자원) |
| 최대 자원(Max) | 각 프로세스가 선언한 최대 자원의 수 |
| 할당 자원(Allocation) | 각 프로세스에 현재 할당된 자원의 수 |
| 기대 자원(Expect) | 각 프로세스가 앞으로 사용할 자원의 수(기대 자원 = 최대 자원 - 할당 자원 |
- 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당한다. 가용 자원이 기대 자원보다 크다는 것은 그 자원을 사용하여 작업을 끝낼 수 있는 프로세스가 있다는 의미이므로 안정 상태이다.
- 가용 자원이 어떤 기대 자원보다 크지 않으면 할당하지 않는다. 가용 자원을 사용하여 작업을 마칠 수 있는 프로세스가 없다는 의미이므로 불안정 상태이다.
결론 : 각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한 번 이상인 경우를 말한다.
문제점
- 프로세스가 자신이 사용할모든 자원을 미리 선언해야 한다.
- 시스템의 전체 자원 수가 고정적이어야 한다.
- 자원이 낭비된다.
자원 할당 알고리즘
자원 타입 당 사용할 수 있는 인스턴스가 하나일 경우 사용할 수 있는 알고리즘이다. 그래프가 사이클이 생기지 않도록 하게 하는 알고리즘이다.
이 외에도 안전 상태 판단 알고리즘과 자언 요청 알고리즘 등이 있다.
검출
예방은 구현이 어렵고 , 회피는 자원을 낭비한다. 그래서 현실적인 것은 검출 회복 방법이다.
- 타임아웃을 이용한 교착 상태 검출은 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법. 하지만 엉뚱한 프로세스가 강제 종료 되거나 모든 시스템에 적용할 수 없다(분산시스템).
- 하지만 DB와 운영체제에서 많이 선호한다. 구현이 간단하기 때문이다. 그래서 이를 가벼운 교착 상태 검출이라 부르고, 자원 할당 그래프를 이용하는 방법을 무거운 교착 상태 검출이라고 한다.
- 자원 할당 그래프를 이용한 교착 상태 검출 : 자원 할당 그래프를 보면 시스템 내의 프로세스가 어떤 자원을 사용하고 기다리고 있는지를 알 수 있다.
- 교착 상태가 없는 자원 할당 그래프는 사이클이 존재하지 않는다.
- 교착 상태가 있는 자원 할당 그래프는 사이클이 발생하면 교착 상태가 검출된 것으로 판단한다.
즉 사이클 발생시 교착 상태가 검출된 것으로 판단한다. 하지만 다중 자원은 모두 교착상태라고 할 수 없다.
이 방식은 프로세스를 제한하지 않으면서 교착 상태를 정확하게 파악할 수 있다는 것이 장점이다. 그러나 자원 할당 그래프를 유지하고, 갱신하고, 사이클을 검사하는 추가 작업으로 오버헤드가 발생하는 단점이 있다. 그래서 일정 시간마다 하는 방식도 생겨났다.
다중 자원과 사이클
다중 자원을 쓸 경우 사이클이 발생해도 교착상태가 발생하지 않는다. 그래서 다중 자원이 포함된 자원 할당 그래프에서는 대기 그래프와 그래프 감소 방법을 이용하여 사이클을 찾는다.
대기 그래프와 그래프 감소
대기 그래프(wait for graph)는 자원 할당 그래프에서 프로세스와 프로세스 간에 기다리는 관계만 나타낸 그래프이다. 그래프 감소(graph reduction)는 대기 그래프에서 작업이 끝날 가능성이 있는 프로세스와 화살표와 관련 프로세스의 화살표를 연속적으로 지워가는 작업을 말한다. 만약 그래프 감소가 끝난 후에 사이클이 있다면 교착 상태로 간주한다.
탐지 알고리즘
은행원 알고리즘에서 사용한 방법과 유사하다.
회복
- 교착 상태를 일으킨 모든 프로세스 종료 : 말그대로 모두 종료한다. 하지만 종료된 프로세스들이 모두 동시에 다시 작업을 시작하면 다시 교착상태가 일어날 가능성이 크다. 따라서 순차적으로 해야하고, 기준이 필요
- 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료 : 말그대로 종료하면서 나머지 프로세스들의 상태를 파악하는 방법이다.
- 우선순위가 낮은 프로세스 먼저 종료
- 우선순위가 같은 경우 작업 시간이 짧은 프로세스를 먼저 종료
- 위의 두 조건이 같으면 자원을 많이 쓰는 프로세스 종료
회복은 종료했으면 복구하는 일도 해야한다. 체크포인트 방식이 좋지만 작업량이 상당하여 선택적으로 사용해야 한다.
