[운영체제] 교착 상태(Deadlock)의 개념

이 글은 혼자 공부하는 컴퓨터 구조 + 운영체제 (저자 : 강민철)의 책과 유튜브 영상을 참고하여 개인적으로 정리하는 글임을 알립니다.

---

교착 상태(Deadlock)

교착 상태의 정의 : 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상

 

아래는 모두 프로세스를 예로 들었지만 스레드에서도 똑같이 적용된다.

 

예를 들어, 아래와 같은 상황을 교착 상태라고 말할 수 있다.

• 게임 프로세스는 자원 A를 점유한 채 웹 브라우저 프로세스가 점유하고 있는 자원 B의 사용을 기다림
• 웹 브라우저 프로세스는 자원 B를 점유한 채 게임 프로세스의 자원 A 사용이 끝나길 기다림

 

 

또 다른 교착상태의 예를 들면 식사하는 철학자 문제가 있다.

식사하는 철학자 문제에서 한두 명의 철학자가 식사를 할 때는 문제가 되지 않지만, 모든 철학자가 동시에 포크를 집어 식사를 하면 어떤 철학자도 식사를 할 수 없다.(교착 상태)

 

---

 

자원 할당 그래프(resource-allocation graph)

교착 상태는 자원 할당 그래프를 통해 단순하게 표현할 수 있다.

자원 할당 그래프는 어떤 프로세스가 어떤 자원을 사용하고 있고, 또 어떤 프로세스가 어떤 자원을 기다리고 있는 지를 표현하는 간단한 그래프이다.

 

자원 할당 그래프는 아래와 같은 규칙으로 그려진다.

1. 프로세스는 원으로, 자원의 종류는 사각형으로 표현
2. 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현
3. 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원 프로세스를 향해 화살표를 표시
4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시

 

자원할당 그래프 예제

• SSD자원은 세 개, CPU 자원은 두 개, 프린터는 하나
• 프로세스 A는 SSD를 할당받아 사용 중, 프로세스 B와 C는 CPU를 할당받아 사용 중, 프로세스 D는 프린터를 사용 중
• 프로세스 E는 프린터 자원을, 프로세스 F는 CPU 자원의 할당을 기다리는 중

 

---

 

교착 상태 발생 조건

교착 상태가 발생할 조건에는 아래와 같이 네 가지가 있다.

아래의 조건 중 하나라도 만족하지 않는다면 교착 상태가 발생하지 않지만, 아래 조건이 모두 만족될 때 교착 상태가 발생할 가능성이 생긴다.

• 상호 배제(mutual exclusion) : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
• 점유와 대기(hold and wait) : 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
• 비선점(nonpreemptive) : 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
• 원형 대기(circular wait) : 자원 할당 그래프를 그렸을 때, 프로세스들이 원의 형태로 자원을 대기하는 상태

위에서 교착 상태 예제로 들었던 상태들을 자원 할당 그래프로 나타내면 아래와 같다.