[OS] 데드락(DeadLock) 과 해결방법 4가지

[msung99]

예상 면접 질문

• 식사하는 철학자 문제(Dining Phliosophers Problem) 에 대해 설명해주세요.
• 데드락을 해결하기 위한 해결방안 4가지에 대해 설명해주세요.
• 데드락 예방(Prevention) 기법에는 어떤 방식이 있으며, 각 방식의 장단점에 대해 설명해주세요.
• 데드락 회복(Recovery) 기법은 어떠한 방식으로 회복을 수행하는에 대해 설명해주세요.

---

관련 포스팅

https://haon.blog/cs/os/deadlock/

[JaeJunday]

1. 식사하는 철학자 문제는 교착상태를 표현하는 대표 문제입니다. N명의 철학자가 존재하고 N-1개의 젓가락/포크가 존재합니다. 한철학자가 자신의 N-1, N번째 자원을 점유하면 식사를 할 수 있습니다. 포크가 철학자의 수 * 2보다 부족하기 때문에 필연적으로 식사를 끝내기 전까지 다른 철학자는 대기해야 하고 이때 교착상태가 발생합니다.

2. 예방, 회피, 탐지, 복구하는 방법이 있습니다.

3. 데드락을 예방하는 방법은 데드락을 발생시키는 4가지 필수조건 점유대기, 선점불가, 순환대기, 상호배제 중 한가지를 골라 미리 해결해서 예방하는 것입니다.

4. 데드락이 이미 발생했을때 해당 프로세스를 종료하거나 자원을 강제로 회수하는 방식으로 해결할 수 있습니다.

[LEE-DA-EUN]

1. 식사하는 철학자 문제(Dining Phliosophers Problem) 에 대해 설명해주세요.

   • 데드락이 발생하는 상황을 설명하기 위한 문제로, 철학자 4명이 식탁에 앉아있고, 식사를 하는 상황에서 본인의 양측에 있는 젓가락을 집어서 식사를 하는 상황을 가정한다. 여기서 철학자1이 젓가락1을 손에 집었다면 철학자4는 본인의 왼쪽의 젓가락1을 획득할 때까지 기다려야 하는 문제가 발생한다. 모든 철학자가 동시에 젓가락을 집어 식사를 하면 누군가는 다른 철학자가 젓가락을 내려놓을 때까지 영원히 대기해야 하는 상황에 빠진다. 이렇듯 공유자원을 본인이 이미 획득한 자원을 내려놓지 못하고, 다른 프로세스가 획득한 자원을 얻기 위해 무한정 대기하고 있는 상황인 데드락이라는 개념을 설명할 수 있는 고전적인 문제이다.

2. 데드락을 해결하기 위한 해결방안 4가지에 대해 설명해주세요.

   • 예방 : 3번 문제
   • 회피 : 불안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당한다.
   • 탐지 : 4번 문제
   • 회복 : 4번 문제

3. 데드락 예방(Prevention) 기법에는 어떤 방식이 있으며, 각 방식의 장단점에 대해 설명해주세요.

   • 상호배제 제거, 점유와 대기 제거, 비선점 모드 제거, 원형 대기 제거 방식이 있다.
   • 상호배제 제거 : 여러 프로세스가 모든 자원을 공유하여 사용하게 하지만 현실적으로 사용하기에는 무리라는 단점이 존재
   • 점유와 대기 제거 : 특정 프로세스가 모든 자원을 획득하도록 허용하거나 아예 어떤 자원도 획득하지 못하도록 하는 것이다. 하지만 자원이용률이 낮아진다는 치명적인 단점이 있다. 병렬적인 작업을 하지 못하고 한 프로세스만 작업을 해야하기에 효율성이 떨어진다.
   • 비선점모드 제거 : 선점모드가 되면 자원을 획득하여 사용할 수 있다. 한 프로세스가 CPU를 이용하다가 타임아웃이 발생하여 다른 프로세스가 CPU를 할당받아 사용할 수 있는 경우에는 효율적인 방법이 될 수 있지만 장단점이 모두 존재하여 범용성이 떨어진다.
   • 원형 대기 제거 : 모든 자원에 번호를 붙이고 오름차순으로 할당하여 원형대기가 발생하지 않도록 한다. 앞선 방식보다 비교적 현실적이지만 컴퓨터 시스템 내에 존재하는 수많은 자원에 번호를 붙이는 것은 번거로운 작업이라 설계측면에서 어렵다는 단점이 있다.

4. 데드락 회복(Recovery) 기법은 어떠한 방식으로 회복을 수행하는에 대해 설명해주세요.

   • 데드락이 해결될 때까지 한 프로세스씩 자원을 몰아주는 '선점을 통한 회복'이 있고, 프로세스를 강제로 종료시켜서 데드락을 회복하는 확실한 방법도 있다.

[rimeir]

1. 식사하는 철학자 문제는 여러 프로세스가 동시에 돌아갈 때 발생하는 데드락(교착 상태)의 원인을 설명할 수 있는 문제입니다. 원형 식탁에 4명의 철학자가 앉아있고 4개의 젓가락이 있는 경우 철학자 양 옆에 두 개의 젓가락을 이용하여 식사할 수 있습니다. 이때 모든 철학자가 본인의 오른쪽 젓가락을 동시에 먼저 가져가게되면 왼쪽의 젓가락은 가져올 수 없기 때문에 영원히 대기를 해야 하는 상황이 발생할 수 있습니다. 이렇게 다른 프로세스의 자원을 계속 기다리게 되는 상황이 데드락(교착 상태)입니다.
2. 데드락을 해결하기 위한 방법으로 예방, 회피, 탐지, 회복 방법이 있습니다. 예방은 데드락이 발생하지 않도록 사전에 자원을 적절하게 분배합니다. 회피는 자원을 조금씩 할당하여 데드락이 발생하지 않게 하고 위험이 발생하면 자원을 할당하지 않습니다. 탐지는 자원을 제약 없이 할당하다가 데드락을 탐지하는 것이고, 탐지되면 데드락을 회복합니다.
3. 데드락을 예방하는 기법은 상호배제, 점유와 대기, 비선점 모드, 원형 대기를 사전에 막아버리는 방법이 있습니다. 상호배제 제거는 여러 개의 프로세스가 모든 자원을 공유한다는 방식이지만 현실적으로 적용하기 어려운 방식입니다. 점유와 대기 제거는 특정 프로세스가 모든 자원을 획득하거나 모든 자원을 획득하지 못하게 하는 방식입니다. 하지만 이러한 방식은 자원 이용률이 낮아진다는 단점이 있습니다. 비선점 모드 제거는 다른 프로세스가 사용 중인 자원을 빼앗아 사용할 수 있는 방식입니다. 원형 대기 제거는 모든 자원에 번호를 매겨 오름차순으로 자원을 할당하게하는 방식입니다. 다른 3가지 방식보다 실용적이지만 번호를 붙이는 번거로운 작업과 번호에 따라 자원 이용률이 떨어질 수 있어 설계 측면에서 어렵다는 단점이 있습니다.
4. 데드락을 회복하는 기법은 선점을 통한 회복과 프로세스 강제 종료를 통한 회복이 있습니다. 선점을 통한 회복은 데드락이 해결될 때까지 다른 프로세스의 자원을 빼앗아 한 프로세스에 자원들을 몰아주는 방식이다. 프로세스 강제 종료를 통한 회복은 운영체제에서 데드락에 빠진 프로세스들을 모두 강제종료하거나 데드락이 없어질 때까지 한 프로세스만 강제 종료합니다.