[Computer Science][Operating System] 데드락(DeadLock)과 교착 상태에 대한 이해 🛑

데드락(DeadLock)은 두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해 다음 처리를 하지 못하는 상태를 의미한다. 이 상태는 무한히 다음 자원을 기다리게 되는 현상으로, 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생한다. 이는 마치 외나무 다리의 양 끝에서 서로 비켜주기를 기다리고 있는 상황과 비슷하다.

데드락이 일어나는 경우 🔄

예를 들어, 프로세스 1과 2가 자원 1과 2를 모두 얻어야 한다고 가정해보자.

• t1: 프로세스 1이 자원 1을 얻고, 프로세스 2가 자원 2를 얻는다.
• t2: 프로세스 1은 자원 2를 기다리고, 프로세스 2는 자원 1을 기다린다.

결과적으로 서로 원하는 자원이 상대방에 할당되어 있어 두 프로세스는 무한정 대기 상태에 빠지게 된다. 이것이 바로 데드락이다!

주로 발생하는 경우 ⚠️

• 멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황이 발생한다.
• 한 프로세스가 자원을 요청했을 때, 동시에 그 자원을 사용할 수 없는 상황이 발생할 수 있다. 이때 프로세스는 대기 상태로 들어간다.
• 대기 상태에 있는 프로세스들이 실행 상태로 변경될 수 없을 때, 교착 상태가 발생한다.

데드락 발생 조건 🔑

데드락이 발생하기 위해서는 다음 네 가지 조건이 모두 성립해야 한다. (하나라도 성립하지 않으면 데드락 문제 해결이 가능하다.)

1. 상호 배제(Mutual exclusion): 자원은 한 번에 한 프로세스만 사용할 수 있다.
2. 점유 대기(Hold and wait): 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 한다.
3. 비선점(No preemption): 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없다.
4. 순환 대기(Circular wait): 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 한다.

데드락 처리 방법 ⚙️

교착 상태를 예방 & 회피

1. 예방(Prevention): 교착 상태 발생 조건 중 하나를 제거하여 해결한다. (자원 낭비가 심함)

   • 상호 배제 부정: 여러 프로세스가 공유 자원을 사용한다.
   • 점유 대기 부정: 프로세스 실행 전 모든 자원을 할당한다.
   • 비선점 부정: 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원을 반납한다.
   • 순환 대기 부정: 자원에 고유 번호를 할당 후 순서대로 자원을 요구한다.

2. 회피(Avoidance): 교착 상태 발생 시 피해나가는 방법이다.

   • 은행원 알고리즘(Banker's Algorithm): 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지를 사전에 검사하여 교착 상태를 회피한다. 안정 상태란 시스템이 교착 상태에 빠지지 않고 모든 프로세스가 필요로 하는 자원을 결국엔 할당받을 수 있는 상태를 의미한다. 안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기한다.
   • 자원 할당 그래프 알고리즘(Resource-Allocation Graph Algorithm): 자원과 프로세스에 대해 요청 간선과 할당 간선을 적용하여 교착 상태를 회피하는 알고리즘이다. 프로세스가 자원을 요구 시 요청 간선으로 변경했을 때 사이클이 생성되는지를 확인한다. 사이클이 생성된다 하여 무조건 교착 상태인 것은 아니다. 자원에 하나의 인스턴스(자원의 개별적인 단위)만 존재 시 교착 상태로 판별하고, 여러 인스턴스가 존재 시 교착 상태 가능성으로 판별한다. 사이클을 생성하지 않으면 자원을 할당한다.

교착 상태를 탐지 & 회복

교착 상태가 되도록 허용한 다음 회복시키는 방법이다.

1. 탐지(Detection): 자원 할당 그래프를 통해 교착 상태를 탐지한다. 자원 요청 시 탐지 알고리즘을 실행시켜 그에 대한 오버헤드가 발생한다.
2. 회복(Recovery): 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법이다.
   • 프로세스 종료 방법: 교착 상태의 프로세스를 모두 중지하거나, 교착 상태가 제거될 때까지 하나씩 프로세스를 중지한다.
   • 자원 선점 방법: 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당한다. 해당 프로세스는 일시 중지되고, 우선 순위가 낮은 프로세스나 수행 횟수가 적은 프로세스 위주로 자원을 선점한다.

식사하는 철학자 문제(The Dining Philosophers Problem) 🍽️

문제 상황

5명의 철학자가 원형 테이블에 앉아있을 때, 각 철학자의 왼쪽과 오른쪽에 하나씩 있는 두 개의 젓가락을 사용해 식사를 해야 한다. 식사를 하려면 두 개의 젓가락이 필요하지만, 각 젓가락은 한 번에 하나의 철학자만 사용할 수 있다.

교착 상태와 기아 상태

• 교착 상태(DeadLock): 모든 철학자가 동시에 자신의 왼쪽 젓가락을 집고, 다음으로 오른쪽 젓가락을 집으려고 시도하면 무한 대기 상태에 빠져 교착 상태가 된다.
• 기아 상태(Starvation): 특정 철학자가 지속적으로 젓가락을 얻지 못해 영원히 식사를 시작하지 못하는 경우가 발생할 수 있다.

교착 상태 해결책

1. n명이 앉을 수 있는 테이블에서 철학자를 n-1명만 앉힘: 5개의 젓가락이 있을 때, 4명의 철학자만 테이블에 앉게 하면 적어도 한 명의 철학자가 두 개의 젓가락을 동시에 집을 수 있어 교착 상태가 발생할 수 없다.
2. 한 철학자가 젓가락 두 개를 모두 집을 수 있는 상황에서만 젓가락 집도록 허용: 한 철학자가 한 번에 한 개의 젓가락을 집는 대신, 두 개의 젓가락을 모두 집을 수 있을 때만 젓가락을 집도록 규칙을 설정하여 한 명의 철학자가 두 젓가락을 확보할 수 없어 젓가락을 집지 않고, 다른 철학자가 식사할 수 있게 된다.
3. 누군가는 왼쪽 젓가락을 먼저 집지 않고 오른쪽 젓가락을 먼저 집도록 허용: 철학자 중 한 명(또는 일부)이 다른 철학자들과는 반대로 오른쪽 젓가락을 먼저 집도록 하여 사이클이 발생할 가능성을 줄여 교착 상태를 피할 수 있다.

이 글은 데드락과 관련된 개념을 이해하는 데 도움이 될 것이다. 교착 상태를 예방하고 회피하는 방법, 탐지 및 회복 방법을 잘 이해하고 적용하는 것이 중요하다. 🛠️

이런 자료를 참고했어요.
[1] Gyoogle - 데드락 (DeadLock, 교착 상태) | 👨🏻‍💻 Tech Interview (https://gyoogle.dev/blog/computer-science/operating-system/DeadLock.html)
[2] velog - [운영체제] 데드락(DeadLock,교착상태) (https://velog.io/@miin-hyukkk/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EB%8D%B0%EB%93%9C%EB%9D%BDDeadLock%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C)
[3] 티스토리 - [운영체제/OS] 데드락(DeadLock, 교착상태)의 개념, 발생 조건 ... (https://coding-zzang.tistory.com/39)
[4] 티스토리 - [운영체제] 교착 상태(데드락, Deadlock) - 5/5 (https://lealea.tistory.com/244)

뤼튼 사용하러 가기 > https://agent.wrtn.ai/5xb91l