[OS] DeadLock(교착상태) 발생과 해결 방안

1. DeadLock (교착상태) 란?

교착상태란 여러 프로세스나 스레드가 서로 자원을 기다리며 실행이 멈추는 상태를 말한다.

예를 들어, 프로세스 A가 프로세스 B의 자원을 요청할 때 프로세스 B도 프로세스 A가 점유하고 있는 자원을 요청하는 것이다.

 

2. DeadLock 원인

DeadLock(교착상태)은 아래의 네가지 조건을 모두 만족할 때 발생한다.

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

 

3. DeadLock 해결 방안

DeadLock 해결 방안에는 예방, 회피, 탐지 및 복구, 무시 네가지가 있다.

3-1. DeadLock(교착상태) 예방

기본적으로, 교착 상태 발생 조건 중 하나를 제거함으로써 교착상태를 해결하는 방법으로 현대 시스템에서는 거의 사용되지 않는다.

• 상호 배제 부정 : 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다.
• 점유 대기 부정 : 프로세스가 실행되기 전 필요한 모든 자원을 할당한다.
• 비선점 부정 : 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고 요구한 자원을 사용하기 위해 기다린다.
• 순환 대기 부정 : 자원에 고유한 번호를 할당하고, 번호를 순서대로 자원을 요구하도록 한다.

이처럼, 예방은 조건 중 하나라도 제거하여 교착상태를 예방하는 것인데 이것은 자원을 효율적으로 이용하지 못하게 한다.

 

3-2. DeadLock(교착상태) 회피

기본적인 회피의 개념은 "교착 상태를 인정하고 피해가자" 는 개념이다

 

• 대표적으로 회피 알고리즘은 은행원 알고리즘가 있다.

자원을 요청할 때 마다 시스템의 상태를 판단하고 회피하는 알고리즘을 사용해 오버헤드가 심하게 발생하기 때문에 현대 시스템에서는 이러한 오버헤드를 감당할 시스템이 거의 존재하지 않는다.

은행원 알고리즘이란?
- 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데서 유래한 기법
- 프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지를 사전에 검사하여 교착 상태를 회피하는 기법
- 안정 상태에 있으면 자원을 할당하고, 그렇지 않으면 다른 프로세스들이 자원을 해지할 때까지 대기함
- 교착 상태가 되지 않도록 보장하기 위하여 교착 상태를 예방하거나 회피하는 프로토콜을 이용하는 방법

3-3. DeadLock(교착상태) 탐지 및 복구

탐지 및 복구의 경우 "교착 상태가 자주 일어나는 시스템에서 일반적으로 사용하는 방법"이다.

• 교착 상태 탐지
  • 자원 할당 그래프를 이용하여 교착 상태 존재 여부를 파악하고 교착 상태에 연관된 프로세스와 자원을 알아낸다.
  • 순환 대기 여부에 초점을 맞춰 교착 상태를 탐지한다.
• 교착 상태 복구
  • 탐지된 교착상태에서 순환 대기를 깨면서 교착 상태에서 회복한다.
  • 이때 방법은 순환 대기가 깨질 때 까지 프로세스를 종료하거나, 순환 대기에 포함된 프로세스의 제어권을 빼앗고 롤백하는 방법이 있다.

3-4. DeadLock(교착상태) 무시

무시의 경우 "교착 상태가 자주 일어나지 않는 시스템에서 일반적으로 사용하는 방법"이다.

• 대부분 교착 상태를 해결하는 데 드는 비용이 더 크기 때문에 비효율적이다 판단하면 사용하는 방법이다.
• 만약, 무시 상태에서 교착 상태가 발생한다면 사용자가 직접 교착 상태를 만드는 프로세스를 종료하거나 재부팅 시켜 해결한다.

4. Starvation (기아상태)

• 기아 상태는 여러 프로세스가 부족한 자원을 점유하기 위해 경쟁하는 상태이다.
• 우선 순위에 의해 특정 프로세스가 영원히 자원을 할당 받지 못하는 상태

4-1. Starvation 해결방법

• 프로세스의 우선 순위를 수시로 변경하는 방법
• 대기 시간이 긴 프로세스의 우선 순위를 높이는 방법
• 프로세스가 우선 순위가 아닌 요청 순서에 따라 처리하는 FIFO 형태의 Queue를 사용하는 방법

예상 질문
1. 데드락의 경우 멀티 프로세스나 멀티 스레드의 환경에서만 발생하는가?
→ 데드락은 기본적으로 멀티 프로세스/멀티 스레드 환경에서 발생한다. 즉, 단일 프로세스의 멀티 스레드 환경에서도 발생할 수 있다.

2. 교착 상태와 기아 상태는 모두 여러 프로세스가 부족한 자원을 점유하기 위해 경쟁하는 상태인것 같은데 차이점은 무엇인가요?
→ 교착 상태는 관련된 모든 프로세스가 무한 대기 상태에 빠지며 시스템의 일부가 멈추게 되지만, 기아 상태는 특정 프로세스만이 자원을 얻지 못하고 무한 대기하게 된다.

3. 교착 상태 복구가 진행될 때, 프로세스를 종료하는 데 사용되는 방법이 따로 있나요? 아니면 무작위의 프로세스를 계속해서 종료하는 건가요?
→ 교착 상태에 빠진 모든 프로세스를 종료하거나, 우선순위, 자원 사용 시간, 자원 점유수 등 특정 기준에 따라 하나씩 프로세스를 종료하는 방법을 사용한다.

4. 교착 상태를 회피하는 알고리즘 중 은행원 알고리즘 말고 또 다른 방법이 있을까요?
→ 자원 간의 관계를 나타낸 다이어그램 내 사이클을 검출하여 교착 상태를 회피하는 자원 할당 그래프 알고리즘이 있다. 추가적으로, 동적으로 자원 할당을 조정하여 시스템이 안전한 상태를 유지하도록 설계하는 교착 상태 회피 알고리즘이 있다.

5. 데드락(교착 상태)가 뭔가요? 발생 조건에 대해 말해보세요.
→ 교착 상태란 여러개의 프로세스/스레드가 서로의 자원을 요구하며 무한 대기에 걸리는 상태로, 발생조건은 비선점, 환형 대기, 상호 배제, 점유 대기 4가지 있는데, 해당 조건이 모두 발생했을 때 교착상태가 발생한다.

6. 상호 배제(Mutual Exclusion)가 교착 상태를 유발할 수 있는 이유는 무엇인가요?
→ 상호배제란 자원은 한 번에 한 프로세스만이 사용할 수 있어야 한다는 것을 의미하는데, 이미 사용중인 자원을 다른 프로세스가 사용할 수 없어 교착 상태의 원인이 될 수 있다.

7. 교착 상태 발생 후 복구하는 방법에는 어떤 것이 있나요
→ 순환 대기가 깨질 때 까지 프로세스를 종료하거나 순환 대기에 포함된 프로세스의 제어권을 빼앗고 롤백하는 방법이 있다.