데드락(Deadlock, 교착상태)이란?

데드락(Deadlock, 교착상태)

• 운영체제에서 데드락(교착상태)란 시스템 자원에 대한 요구가 뒤엉킨 상태를 뜻합니다.

• 즉 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기상태에 빠지는 상황을 일컫습니다.

데드락의 발생조건

• 상호 배제
• 한 번에 프로세스 하나만 해당 자원을 사용할 수 있다.
• 사용중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때 까지 기다려야 함..!

• 점유 대기
• 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.

• 비선점
• 이미 할당된 자원을 강제로 빼앗을 수 없다.

• 순환 대기
• 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.

데드락의 해결법

• 예방
[안정 상태 및 안전 순서]
• 데드락의 회피법에는 Safe sequence, Safe State 등이 있습니다.
• 시스템의 프로세스들이 요청하는 모든 자원을, 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해 줄 수 있다면 안정 상태(Safe state)에 있다고 말합니다.
• 이처럼 특정한 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서를 찾을 수 있다면 그것을 안전 순서(Safe sequence)라고 부릅니다.
[불안정 상태]
• 불안정 상태는 안정 상태가 아닌 상황을 말합니다.
• 즉 데드락 발생 가능성이 있는 상황이며, 교착 상태는 불안정 상태일 때 발생할 수 있습니다.

• 회피
• 교착상태의 발생 조건을 없애는 것 보다는 애초에 발생하지 않도록 알고리즘을 적용하는 방법이다.
• 대표적으로 은행원 알고리즘이 있다.

• 탐지 및 회복
[탐지]
• 탐지 알고리즘을 사용하여 교착상태가 발생했는지 탐지하고 교착상태가 탐지되었다면 복구 기법을 통해 교착 상태를 복구한다.
• 이 방식은 지속적으로 확인하는 작업이 필요하기 때문에 성능 저하가 발생한다.
[회복]
• 교척 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법이다.
• 프로세스를 종료하는 방법
1. 교착 상태의 프로세스를 모두 중지한다.
2. 교착 상태가 제거될 때 까지 한 프로세스씩 중지한다.

• 무시
• 프로세스를 종료하거나 시스템을 재부팅하여 교착상태를 해결함

REF

[OS] 교착상태 회복 탐지 알고리즘

본 설명은 책 "그림으로 배우는 구조와 원리 운영체제 개정 3판"를 읽으며 제 나름대로 해석하고 정리해 보았습니다.😉 교착 상태 탐지 알고리즘은 교착 상태 회복을 위한 알고리즘으로 교착상태에 대해 더 자세히 알고 싶다면 교착상태란? 링크를 참고하자. 교착 상태 탐지 알고리즘은 쇼사니와 코프만이 제안했다. 교착 상태 탐지알고리즘 또한 은행가 알고리즘에서 사용한 자료구조들과 비슷하다.

https://hoyeonkim795.github.io/posts/%ED%83%90%EC%A7%80%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/