Deadlock(교착상태)?
- 데드락(Deadlock) 또는 교착 상태는 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태이다.
- 위 이미지를 보면 취업을 하기 위해서는 경력이 필요한데 경력을 쌓기 위해서는 취업을 해야하는 웃픈 상황이 발생한다. 데드락을 설명하기 좋은 예제이다.
- 이 상황을 프로세스와 자원의 관계로 바꿔서 이미지를 만들어 보면 이렇게 된다.
- P1은 R1을 점유하고 있고 P2는 R2를 점유하고 있다.
- P1은 자신의 테스크를 진행하기 위해 R2를 요청하지만 R2는 이미 P2가 점유하고 있으므로 대기한다.
- 반대로 P2는 자신의 테스크를 진행하려고 R1을 요청하지만 이미 P1에 점유되어 있으므로 P2 또한 테스크를 진행하지 못하고 대기하게 된다.
- 결국 서로 대기만 하고 진행하지 못하게 되는 데드락이 발생한 것이다.
# 데드락 발생조건
- 데드락은 언제 발생할까? 아무때나 발생할 수 있을까? -> No, 데드락은 발생조건이 있다.
- 상호 배제 : 한번에 한 프로세스만 자원 사용 가능하다.
- 점유 대기 : 프로세스가 자원을 가지고 있는 상태에서 다른 자원을 사용하기 위해 대기하고 있어야 한다.
- 비선점 : 이미 할당된 자원은 강제로 빼앗을 수 없다.
- 순환 대기 : 자원을 기다리는 프로세스 간에 사이클이 형성되어야 한다.
- 위 발생조건 4가지가 모두 충족되어야만 교착상태 발생한다.
데드락 해결책
- 데드락을 해결하기 위한 방법은 4가지가 있다.
- 예방
- 회피
- 탐지 및 회복
- 무시
교착상태 예방
- 데드락을 예방한 다는 것은 데드락이 발생하지 않도록 한다는 것이다.
- 위의 데드락의 발생조건을 보면 4가지가 모두 충족되어야 한다고 했다.
- 반대로 말한다면 발생조건 중 1가지라도 충족되지 않는다면 데드락이 발생하지 않는다는 것이다.
- 따라서 4가지 조건 중 1가지 조건을 방지하여 사전에 데드락을 예방한다.
- 상호 배제 조건 방지
- 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다.
- 그러나 추후 동기화 관련 문제가 발생할 수 있다.
- 점유 대기 조건 방지
- 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류해서, 나중에 또다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 한다.
- 비선점 조건 방지
- 이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 한다.
- 순환 대기 조건 방지
- 자원을 순환 형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 한다.
단점
- 사실 위의 4가지 조건은 테스크 진행 시 프로세스가 자원을 효율적으로 사용하게 해주는 조건이다.
- 이 조건을 방지하게 되면 프로세스가 자원을 효율적으로 사용하지 못하게 되어 전체적인 작업효율이 떨어지게 되므로 좋은 해결책이 아니다.
교착상태 회피
- 교착상태 회피는 자원이 어떻게 요청될지에 대한 정보를 미리 파악하고 회피 알고리즘을 통해 교착상태가 일어나지 않도록 자원을 할당하는 방식이다.
![안정 상태 이미지]()
- 위의 이미지는 안정 순서(Safe Sequence)를 찾을 수 있는지 없는지를 기준으로 나누어져 있다.
- 안정 순서란 프로세스들이 요청한 모든 자원들을 교착상태 발생 없이 할당할 수 있는 순서를 의미한다.
- 안정 순서를 찾을 수 있다면 Safe State, 찾을 수 없다면 Unsafe State이다.
- Safe state라면 교착상태가 발생하지 않는다는 것을 보장할 수 있다.
- Unsafe state라고 무조건 교착상태가 발생하는 것은 아니다.
- 자원 할당 시 상태가 Unsafe state가 된다면 자원을 할당해주지 않고 대기한다.
- 즉, 항상 Safe state 상태로 유지된다. ### 회피 알고리즘
- 자원 할당 그래프 알고리즘(Resource-Allocation Graph Algorithm)
- 자원이 하나일 때 사용하는 방법으로 자원 할당 그래프를 이용해 교착상태를 회피하는 것.
- 자원 할당 그래프에 예약 간선(claim edge)를 추가한다.
- 예약 간선이란 향후 요청할 수 있는 자원을 가리키는 점선으로 표시된 간선을 뜻함.
- 프로세스 시작 전에 모든 예약 간선들을 자원 할당 그래프에 표시한다.
- 예약 간선으로 설정한 자원에 대해서만 요청할 수 있고 사이클이 형성되지 않을 때만 자원을 할당 받는다.
- 사이클 생성 여부를 조사할 때 O(n^2) 시간이 걸린다.
- 은행원 알고리즘 (Banker’s Algorithm)
- 자원이 여러 개일 때 은행원 알고리즘으로 교착상태를 회피할 수 있음.
- 프로세스 시작 시 자신이 필요한 각 자원의 최대(Max) 개수를 미리 선언한다.
- 각 프로세스에서 자원 요청이 있을 때 요청을 승인하면 시스템이 안정 상태로 유지되는 경우에만 자원을 할당함.
- 불안정 상태가 예상되면 다른 프로세스가 끝날 때까지 대기를 한다.
단점
- 전제 조건
- 프로세스 수, 자원의 종류가 고정되어 있어야 한다.
- 프로세스가 요구하는 자원 및 최대 자원의 수를 알아야 한다.
- 프로세스는 반드시 자원을 사용 후 반납해야 한다.
- 큰 오버헤드
- 자원 할당 그래프 알고리즘의 시간복잡도는 O(n^2), 은행원 알고리즘의 시간복잡도는 O(m(n^2))이다.
- 매 자원 할당마다 회복 알고리즘을 사용한다면 큰 오버헤드가 발생한다.
교착상태 탐지 및 회복
- 교착상태를 허용하지만 상태를 탐지하고 회복하는 방식이다.
- 알고리즘을 특정 기준에 따라 실행함으로써 시스템에 발생된 교착상태를 회복한다.
- 회피와 비슷하지만 매 자원 할당마다 회피 알고리즘을 실행시키는 것과 달리 특정 주기적으로 대기 그래프에 주기가 있는지 탐지 알고리즘을 호출하여 교착상태를 탐지한다.
- 탐지 알고리즘을 통해 교착상태를 탐지하면 회복 알고리즘을 통해 교착상태를 해결한다.
- 얼마나 자주 교착상태가 발생하는지 얼마나 많은 프로세스가 교착 상태에 연루되어 있는지에 따라 호출 빈도를 조절해야 한다.
- 탐지 알고리즘을 실행시키는 기준
- 주기적으로 일정 시간마다 호출
- 자원이 즉시 할당되지 못하는 경우
- CPU 사용률이 40%이하로 떨어지는 경우
탐지 알고리즘
- 대기 그래프 알고리즘(Corresponding wait-for Graph Algorithm)
- 자원 할당 그래프에서 자원을 제거 후 간선들을 결합하여 대기 그래프로 표현을 할 수 있다.
- 대기 그래프에서 Pi→Pj는 프로세스 Pi가 Pj프로세스가 보유하고 있는 자원을 기다리고 있음을 나타낸다.
- 대기 그래프에 주기(cycle)가 있다면 교착 상태를 의미한다.
- 은행원 알고리즘 (Banker’s Algorithm)
- 회피에서 사용하는 은행원 알고리즘과는 약간의 차이가 있다.
- 각 프로세스의 자원 요청(Request) 개수를 사용한다.
- 현재 상태가 안전 상태(safe state)인지 확인한다.
- 불안정 상태(unsafe state)라면 교착상태라고 판단한다.
회피 알고리즘
- 교착상태 일으킨 프로세스를 종료하거나 할당된 자원을 해제시켜 회복시키는 방법이 있다.
- 프로세스 종료 방법
- 교착상태의 프로세스를 모두 중지한다.
- 교착상태가 제거될 때까지 하나씩 프로세스를 중지한다.
- 자원 선점 방법
- 교착상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당한다.
- 우선 순위가 낮은 프로세스나 수행 횟수가 적은 프로세스 위주로 프로세스 자원을 선점한다.
교착상태 무시
- 말 그대로 교착상태에 대해 아무런 대응도 하지 않는 것이다.
- 교착상태는 거의 발생하지 않는데다가 예방과 처리 비용이 많이 든다.
- 무책임한 것 같지만 오히려 경제적인 측면에서 제일 효율적이다.
- Unix, Windows를 포함한 대부분의 운영체제에서 사용하는 방법이다.
- 만약 교착상태가 발생하면 사용자가 교착상태의 프로세스를 강제로 종료하거나 재부팅 하는 방법으로 해결해야 한다.
참고
블로그
- https://rebro.kr/177
- https://chanhuiseok.github.io/posts/cs-2/
- https://yoongrammer.tistory.com/67
- https://ohjoohyung.github.io/deadlock/
- https://iambeginnerdeveloper.tistory.com/163
유튜브
- https://www.youtube.com/watch?v=FXzBRD3CPlQ&t=9s
- https://www.youtube.com/watch?v=Ry_gB34cvwc&t=16s