2025-10-08 14:28
Tags: 운영체제
교착상태 (Deadlock)
-
프로세스가 필요한 자원을 기다리며 영원히 멈추는 현상인 교착 상태]는 다중 프로그래밍(Multiprogramming) 시스템의 근본적인 문제다.
-
교착상태는 상호 배제, 점유와 대기, 비선점, 환형 대기라는 네 가지 조건이 동시에 충족될 때 발생하며, 이 중 하나라도 제거하면 예방할 수 있다.
-
교착상태를 해결하기 위해 예방, 회피, 탐지 및 회복, 무시 등 다양한 전략이 사용되며, 각 전략은 시스템의 특성과 요구사항에 따라 장단점을 가진다.
- 예방은 너무 엄격해서 자원 효율성을 떨어뜨리고,
- 회피는 비현실적인 가정을 요구하며 오버헤드가 크다.
- 탐지 및 회복은 복잡하고 비용이 많이 든다.
- 이 때문에 대부분의 현대 운영체제는 교착상태를 ‘무시’하는 실용적인 노선을 택했다.
-
여러 프로그램을 메모리에 동시에 올려놓고 CPU가 유휴 상태일 때 다른 프로그램으로 전환하여 실행하는 ‘다중 프로그래밍(Multiprogramming)’ 기술이 등장
-
다익스트라는 ‘식사하는 철학자들(Dining Philosophers Problem)‘이라는 유명한 비유를 통해 교착상태의 본질을 설명했다.
- 이 비유는 한정된 자원(포크)을 여러 프로세스(철학자)가 특정 순서에 따라 요청할 때 어떻게 시스템 전체가 멈출 수 있는지를 명확하게 보여준다.
5명의 철학자가 원탁에 앉아 식사를 한다. 각 철학자의 양옆에는 포크가 하나씩 놓여 있고, 철학자가 스파게티를 먹기 위해서는 양쪽의 포크 두 개가 모두 필요하다. 만약 모든 철학자가 동시에 왼쪽 포크를 집는다면 어떻게 될까? 각자 하나의 포크를 든 채, 오른쪽 포크가 다른 철학자에 의해 놓이기를 영원히 기다리게 된다. 아무도 식사를 하지 못하고 결국 모두 굶어 죽게 되는 상황, 이것이 바로 교착상태다.
교착상태의 필수 조건 4가지
1. 상호 배제 (Mutual Exclusion)
- 정의: 자원은 한 번에 하나의 프로세스만 사용할 수 있다.
- 설명:
- 프린터와 같은 자원은 본질적으로 공유가 불가능하다.
- 만약 여러 프로세스가 동시에 프린터에 데이터를 보낸다면 결과물은 의미 없는 종이 낭비일 뿐이다.
- 이처럼 자원의 무결성을 보호하기 위해, 운영체제는 특정 자원을 사용하는 프로세스가 작업을 마칠 때까지 다른 프로세스의 접근을 막는다
2.2. 점유와 대기 (Hold and Wait)
- 정의: 프로세스가 최소한 하나의 자원을 점유한 상태에서, 다른 프로세스에 할당된 자원을 추가로 기다리고 있다.
- 설명:
- ‘식사하는 철학자’ 비유에서 철학자가 왼쪽 포크를 손에 쥔(점유) 상태로, 오른쪽 포크를 기다리는(대기) 상황과 같다.
- 프로세스가 이미 할당받은 자원을 놓지 않은 채로 다른 자원을 계속해서 요구할 때 이 조건이 성립된다.
2.3. 비선점 (No Preemption)
- 정의: 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없다.
- 설명:
- 어떤 프로세스가 파일을 사용하고 있는데, 다른 프로세스가 필요하다고 해서 운영체제가 그 파일의 제어권을 강제로 빼앗아 올 수 없다는 의미다.
- 자원은 할당받은 프로세스가 자발적으로 ‘놓아줄(release)’ 때만 반납된다.
- 만약 자원을 강제로 빼앗을 수 있다면(선점이 가능하다면), 한 프로세스가 무한정 기다리는 일은 없을 것이다.
2.4. 환형 대기 (Circular Wait)
- 정의: 대기하고 있는 프로세스들이 원형으로 구성되어, 각 프로세스가 다음 프로세스가 점유한 자원을 기다린다.
- 설명:
- 교착상태의 핵심 조건이다.
- 프로세스 P0는 P1이 가진 자원을 기다리고, P1은 P2가 가진 자원을, …, 그리고 마지막 프로세스 Pn은 P0가 가진 자원을 기다리는 꼬리물기 형태의 대기 사슬이 만들어지는 것이다.
- 이 원형 고리가 형성되면 어느 누구도 자신의 자원을 놓지 못하고, 다른 프로세스가 자원을 놓기만을 영원히 기다리게 된다.