CS/운영체제
데드락(Deadlock)
D_Helloper
2023. 3. 26. 19:56
데드락(Deadlock) == 교착상태
- 리소스에 대한 요청이 뒤엉킨 상태
- 서로 다른 프로세스가, 서로 점유하고 있는 자원을 기다릴 때 무한 대기에 빠지는 상황
데드락 발생 조건
아래 4가지 조건이 동시에 성립해야 발생함
상호 배제
- 한 번에 프로세스 하나만 해당 자원을 사용할 수 있음
점유 대기
- 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다림
비선점
- 프로세스가 작업을 마친 후 자원을 자발적으로 반환할 때까지 기다림
순환 대기
- 프로세스의 자원 점유 및 점유된 자원의 요구 관계가 원형을 이루면서 대기하는 조건
데드락 해결 방법
예방(Prevention)
- 위 발생 조건 4가지 중 하나를 방지하여 데드락 발생을 예방하는 방법
- 상호 배제 방지
- 점유 대기 방지
- 비선점 방지
- 순환 대기 방지
위 예방 방법은 시스템 처리량이나 자원 사용의 효율성 측면에서 안 좋음
회피(Avoidance)
Safe State
- 시스템의 프로세스들이 요청하는 모든 자원을, 데드락을 발생 시키지 않으면서도 차례대로 모두에게 할당해줄 수 있는 상태
Safe Sequence
- 특정 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서를 찾을 수 있다면, 안전한 순서(Safe Sequence)라고 부름
Unsafe state
- 데드락이 발생할 가능성이 있는 상황
위 개념을 기반으로, 안전한 상태에서만 자원 요청을 허용하는 방법
대표적으로 은행원 알고리즘, 자원 할당 그래프 알고리즘이 있음
데드락 탐지(Detection) 및 회복(Recovery)
탐지(Detection)
- 시스템에 데드락이 발생했는지에 대한 여부를 탐색하고 회복 기법 알고리즘에 활용하는 것
- 지속적으로 교착상태를 확인하는 작업이 필요하기 때문에 오버헤드가 발생
회복(Recovery)
- 프로세스 종료 방법
- 자원 선점 방법
데드락 무시
- 발생 조건 네 가지가 다 충족이 되더라도 반드시 교착이 일어나는 것은 아님.
- 환경에 따라서 오버헤드를 감수하는 것이 비효율적일 수 있음
- 그냥 내비두는 방법도 있음.
식사하는 철학자 문제
5명의 철학자가 원탁에 앉아서 식사를 한다. 철학자들 사이에는 포크가 하나씩 놓여 있고, 철학자들은 다음의 과정을 통해 식사를 한다.
- 일정 시간 생각을 한다.
- 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
- 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
- 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.
- 오른쪽 포크를 내려놓는다.
- 왼쪽 포크를 내려놓는다.
- 다시 1번으로 돌아간다.
이 상황에서 철학자(프로세스)들이 동시에 오른쪽 포크(자원)를 집어든다면?
- 철학자들은 포크를 공유할 수 없음(상호 배제)
- 자신의 왼쪽에 앉은 철학자가 포크를 놓을 때까지 기다림 (점유 상태로 대기)
- 철학자들은 왼쪽 철학자의 포크를 빼앗을 방법도 없음 (선점 불가)
- 각 철학자들은 자신의 왼쪽 철학자의 포크를 대기 (순환대기)
해결 방법
- 상호 배제와 선점 불가의 경우, 문제의 조건 때문에 해소가 불가능
- 점유 대기를 해제하려면 왼쪽 포크를 집을 수 없을 때, 오른쪽 포크를 식탁 위에 내려놓는 방법
- 순환 대기를 해소하려면 포크에 우선 순위를 매기는 방법