[OS] 데드락 개념, 필요 조건과 데드락 해결 방법(식사하는 철학자 예시)

 

☠️ 데드락

두 개 이상의 프로레스/스레드가 서로가 가진 리소스를 무한히 기다리게 되어 다음 처리를 하지 못하는 상태

 

 

데드락 발생 필요 조건 4가지

데드락은 다음 4가지 조건이 동시에 성립될 때에만 발생할 수 있다.

1️⃣ 상호 배제(Mutual exclusion)

리소스를 공유해서 사용할 수 없다 = 한 번에 한 스레드만이 그 자원을 사용할 수 있다.

📌 참고

이 조건은 공유 데이터에 대한 일관성과 무결성을 보장하기 위해 프로세스/스레드 간의 동기화를 시키는 데에 필요한 조건이었다.

하지만 이 조건이 아래 3가지 조건이 만나면 관련된 프로세스/스레드가 더 이상 진행되지 못하는 데드락이 발생할 수 있다.

2️⃣ 점유하며 대기 (Hold and wait)

프로세스가 이미 하나 이상의 리소스를 취득한 상태(hold)에서 다른 프로세스가 사용하고 있는 리소스를 추가로 기다린다(wait)

📌 예시 살펴보기

위 예시1에서

• 형은 이미 축구공을 가지고 있으면서 동생의 농구공을 갖기를 원함

⇒ Hold and wait

 

위 예시1에서

• 형은 이미 축구공을 가지고 있으면서 동생의 농구공을 갖기를 원함
• 동생은 이미 농구공을 가지고 있으면서 형의 축구공을 갖기를 원함

⇒ Hold and wait && Circular wait

3️⃣ 비선점 (No preemption)

• 리소스 반환(release)을 오직 그 리소스를 취득한 프로세스만 할 수 있다.
• 이미 어떠한 리소스를 점유하고 있다면 다른 프로세스가 이걸 강제로 빼앗을 수 없고, 점유하고 있는 스레드가 태스크를 종류한 후 자발적으로 방출되어야만 한다.

📌 예시 살펴보기

• 형은 동생의 농구공을 강제로 빼앗을 수 없고,
• 동생은 형의 축구공을 강제로 빼앗을 수 없다

4️⃣ 순환 대기 (Circular wait)

• 프로세스들이 순환 형태(circular)로 서로의 리소스를 기다린다
• 대기하고 있는 스레드의 집합에서 $T_0$은 $T_1$이 점유한 자원을 대기, $T_0$은 $T_2$이 점유한 자원을 대기, $T_0$은 $T_3$이 점유한 자원을 대기, … ♾️

📌 예시 살펴보기

위 예시1에서

• 형은 동생의 농구공을 대기
• 동생은 형의 축구공을 대기

위 예시2에서

• 자동차 1은 자동차 2의 리소스를 대기
• 자동차 2는 자동차 3의 리소스를 대기
• 자동차 3은 자동차 4의 리소스를 대기
• 자동차 4는 자동차 1의 리소스를 대기 …

 

운영체제에서는 데드락을 어떻게 해결할까?

💡 원칙적으로 데드락을 처리하는 데는 3가지 방법이 있다.

1. 데드락 무시 : 문제를 무시하고, 데드락이 시스템에서 절대 발생하지 않는 척한다
리눅스와 윈도우를 포함해 대부분의 운영체제가 사용하는 방법 → 나머지는 개발자의 몫

2. 데드락 예방과 회피 : 시스템이 결코 데드락이 되지 않도록 보장하기 위해 데드락을 예방하거나 회피하는 프로토콜을 사용한다

3. 데드락 탐지와 복구 : 시스템이 데드락이 되도록 허용한 다음에 복구시킨다
데이터베이스와 같은 일부 시스템은 데드락의 발생을 허용하고, 복구 작업을 수행

 

❓ 왜 대부분의 현대 운영체제는 데드락을 무시하는 방법을 채택할까?

1. 데드락을 예방하고 회피하는 알고리즘(ex 은행가 알고리즘) 또는 데드락 탐지하고 복구하는 알고리즘을 운영체제 레벨에서 구현하는 것은 리소스 낭비가 너무 큼(오버헤드)
2. 현대 운영체제는 데드락이 드물게 발생되도록 설계되어 대부분 환경에서 데드락은 자주 발생하지 않음

👉 정리
데드락을 예방하고 회피, 탐지하고 복구하는 알고리즘을 운영체제 레벨에서 구현하는 것은 매우 복잡하고 리소스 낭비가 심하기 때문에 데드락 발생시 처리하는 대신 운영체제 설계 단계에서 데드락이 최소화되도록 설계하여 데드락 발생 가능성을 줄인다.

또한 데드락 발생시 복구할 수 있는 방식이 존재하기 때문에 이를 처리하는 과정을 개발자에게 위임하고, 이 과정에서 필요한 도구와 방법들을 제공함으로써 데드락 처리의 효율성을 높인다.

 

 

데드락 예방과 회피

✅ 데드락 예방

데드락 4가지 필요조건 중 적어도 하나가 성립하지 않도록 시스템을 디자인하는 방법

 

1️⃣ 상호 배제(Mutual exclusion) 조건 거부

⇒ 리소스를 공유 가능하게 한다

❌ 하지만 현실적으로 불가능함

어떤 자원들은 근본적으로 공유가 불가능. 즉, mutual exclusion이 보장되어야 하는 리소스들이 있기 때문(ex. print, mutex락은 동시에 여러 스레드가 공유할 수 없다)

 

2️⃣ 점유하며 대기(Hold and wait) 조건 거부

⇒ 사용할 리소스들을 모두 획득한 뒤에 시작

⇒ 리소스를 전혀 가지지 않은 상태에서만 리소스를 요청

🚫 단점

- 자원 이용률이 낮음 : 필요한 모든 자원을 할당한 뒤 시작할 수 있다면, 어느 자원이 비선점되기까지 오래 걸린다면 나머지 자원들은 할당되지 않기 때문에 자원 이용률이 낮음
- 기아 상태 발생할 수 있다 : 인기 있는 여러 개의 자원이 필요한 스레드는 필요한 자원 중 적어도 하나는 항상 다른 스레드에 할당되므로 무한정 대기해야 할 수 있다.

 

3️⃣ 비선점(no preemption) 조건 거부

⇒ 추가적인 리소스를 기다려야 한다면 이미 획득한 리소스를 다른 프로세스가 선점 가능하도록 한다

⇒ 즉, 프로세스가 요청한 자원을 다른 프로세스가 점유하고 있으면 강제로 중단시켜 자원을 요청한 프로세스에게 넘기는 것

🚫 단점

- 프로세스 성능 저하 : 자원을 빼앗기는 프로세스의 성능에 부정적인 영향을 끼침
- 프로세스 불안정성 : 강제로 작업이 중단된 프로세스는 이전 상태를 잃어버릴 수도 있음

 

4️⃣ 순환 대기 조건 거부

⇒ 모든 리소스에 순서 체계를 부여해서 오름차순으로 리소스를 요청하도록 강제하는 것

예시)

 

모든 자동차는

리소스 1을 요청한 뒤, 리소스 2를 요청할 수 있다

리소스 2을 요청한 뒤, 리소스 3를 요청할 수 있다

리소스 3을 요청한 뒤, 리소스 4를 요청할 수 있다

 

 

✅ 가장 많이 쓰이며 실용적인 해결책

🚫 단점 : 자원 활용 효율성이 떨어질 수 있다.

 

✅ 데드락 회피

실행 환경에서 추가적인 정보를 활용해서 데드락이 발생할 것 같은 상황을 회피하는 것

추가적인 정보란?

• 현재 사용가능한 리소스들
• 이미 누군가에게 할당된 리소스들
• 리소스 요청과 반환 등에 관한 정보

은행가 알고리즘(Banker Algorithm)

리소스를 요청을 허락해줬을 때 데드락이 발생할 가능성이 있으면
리소스를 할당해도 안전할 때까지 계속 요청을 거절하는 알고리즘

• 안전한 상태란? 모든 프로세스가 자원을 할당받고 실행을 마칠 수 있는 상태
• 동작 과정
  1. 자원 할당 요청 시마다 시스템은 자원의 현재 상태를 확인 (안전 상태가 가능한지)
     • 요청된 자원이 시스템에 남아있는 자원 내에서 할당할 수 있는지
     • 자원을 할당한 후, 시스템이 여전히 안전 상태에 있을 수 있는지 시뮬레이션
  2. 자원 할당 뒤에 안전 상태라면, 요청 승인
  3. 그렇지 않다면, 자원 할당 거부
  4. 자원을 요청할 때마다 위 과정 반복

데드락 탐지와 복구

데드락을 일단 허용하고, 데드락이 발생하면 복구하는 전략

✅ 데드락 탐지

• 자원 할당 그래프를 변형한 대기 그래프(wait-for graph)
• 데드락 탐지 알고리즘을 사용
• 데드락의 발생 빈도와 관련 스레드의 개수에 따라 탐지 알고리즘의 사용 타이밍을 정함

✅ 데드락 복구

데드락을 깨뜨리는 데는 두가지 방법

 

1️⃣ 프로세스와 스레드의 종료 (데드락의 순환 대기를 깨뜨림) 

• 종료 방식1) 데드락 프로세스를 모두 중지
  확실하게 데드락 사이클을 깨뜨리지만, 그 비용이 크다
• 종료 방식2) 데드락이 제거될 때까지 한 프로세스씩 중지
  각 프로세스가 중지될 때마다 데드락 탐지 알고리즘을 호출해 데드락 여부를 확인해야 함으로 오버헤드를 유발한다.

2️⃣ 리소스의 일시적인 선점을 허용 (데드락의 비선점 조건을 깨뜨림)

• 데드락이 깨질 때까지 프로세스의 자원을 빼앗아 다른 프로세스에게 줌
• 3가지 고려사항이 있음
  • 희생자 선택 : 어느 자원과 어느 프로세스들이 선점될 것인가?
  • 후퇴 : 프로세스로부터 자원을 선점하려면, 그 프로세스를 어떻게 해야 하는가?
  • 기아 상태 : 기아 상태가 발생하지 않는 것을 어떻게 보장할 것인가?

 

식사하는 철학자 문제

데드락과 기아상태를 보여주는 예시

5명의 철학자가 원탁에 앉아서 식사를 합니다.
애처롭게도, 철학자 사이사이에 젓가락은 하나씩만 주어집니다.
그렇기 때문에 아래와 같은 과정을 통해 식사를 해야 합니다.

 

1. 철학자들은 일정 시간 동안 생각을 한다.
2. 왼쪽 젓가락이 사용 가능할 때까지 기다린다. 만약 사용 가능하다면 집어든다.
3. 오른쪽 젓가락이 사용 가능할 때까지 기다린다. 만약 사용 가능하다면 집어든다.
4. 젓가락 한 쌍을 얻었다면 식사를 한다.
5. 오른쪽 젓가락을 내려 놓는다.
6. 왼쪽 젓가락을 내려 놓는다.
7. 1번 과정으로 돌아간다.

 

❗️ 철학자들 모두 왼쪽 젓가락만 들고 오른쪽 젓가락을 기다리기만 하는 상황에서 문제가 발생

• 데드락 : 두 식사를 하지 못하기 때문에 젓가락을 내려놓을 일이 없고, 3번 과정으로 넘어가지 못함
• 기아 상태 : 이러한 상황이 지속된다면 철학자들 모두 굶어 죽고 말 것

운영체제와의 비유

• 젓가락 = 자원
• 철학자 = 프로세스(혹은 스레드)
• 젓가락 한 쌍 = 프로세스가 필요한 자원의 수

데드락 발생 조건 4가지

1️⃣ Mutual exclusion : 다른 철학자가 사용 중인 젓가락을 서로 공유하며 사용할 수 없습니다.

2️⃣ Hold and wait : 철학자가 젓가락(자원) 1개를 가지고 있는 상태에서, 다른 철학자가 사용 중인 젓가락을 요청합니다.

3️⃣ No preemtion : 규칙상 다른 철학자가 가지고 있는 젓가락을 함부로 빼앗거나 선점할 수 없습니다.

4️⃣ Circular wait : 철학자들이 서로 꼬리에 꼬리를 무는 형태로 젓가락을 기다리고 있습니다.

 

문제 해결 방법

1. 철학자 5명이 앉을 수 있는 테이블에 최대 4명만 앉을 수 있도록 허용한다.
   • 3명이 젓가락을 한 개씩 가지고 있다고 하더라도 최소한 나머지 1명은 젓가락을 2개 얻을 수 있으므로 식사가 가능
   • 따라서 1명이 식사를 마치면, 언젠가는 다른 철학자들도 식사를 할 수 있으므로 Deadlock 발생 상황을 배제할 수 있다
2. 젓가락을 한 번에 2개씩 들도록 규칙을 바꾼다.
   • 자신의 왼쪽, 오른쪽에 놓인 젓가락을 동시에 들 수 있도록 바꾸어준다면, 최소한 1명 이상은 식사를 할 수 있으므로 Deadlock 발생 상황을 배제할 수 있다
   • 하드웨어적인 해결책
     • 하드웨어 명령어 즉, Atomic operation을 자원 1개가 아닌, 2개씩 가져가도록 변경
     • Atomic operation하나를 실행하는 도중에 interrupt가 발생해서 명령을 방해하는 상황은 발생하지 않는다.
     • Atomic operation을 젓가락 1쌍을 한 번에 가져가도록 설계해준다면 Context switch가 발생해도 이미 철학자의 손에는 2개의 젓가락이 쥐어졌기 때문에 나중에 CPU를 다시 할당 받아도 식사를 못할 걱정이 없어짐
     • 더 이상 쪼개어질 수 없는 명령

 

 

3. 앉은 자리별로 젓가락 드는 순서를 다르게 한다.

무조건 왼쪽, 오른쪽 순으로 젓가락을 기다리는 방법에서

홀수(1, 3, 5) 철학자는 왼쪽, 오른쪽 순서로 젓가락을 기다리고

짝수(2, 4) 철학자는 오른쪽, 왼쪽 순서로 젓가락을 기다리도록 합니다.

--> 기존에 Circular wait이 발생할 수 있는 상황을 배제