데드락(DeadLock, 교착 상태)

데드락(DeadLock, 교착상태)

데드락이란 두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태를 말한다.

 

데드락이 일어나는 경우

프로세스1과 2가 자원1, 2를 모두 얻어야 한다고 가정하면,

t1 : 프로세스1이 자원1을 얻음 / 프로세스2가 자원2를 얻음

t2: 프로세스1은 자원2를 기다림 / 프로세스2는 자원1을 기다림

 

서로 원하는 리소스가 상대방에게 할당되어 있기 때문에 이 두 프로세스는 무한정 기다리게 되는데 이러한 상태를 DeadLock 상태라고 한다.

 

주로 발생하는 경우

멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황 발생

한 프로세스가 자원을 요청했을 때, 동시에 그 자원을 사용할 수 없는 상황이 발생할 수 있음. 이때 프로세스는 대기 상태로 들어감

대기 상태로 들어간 프로세스들이 실행 상태로 변경될 수 없을 때 '교착 상태' 발생

 

데드락 발생 조건

아래 4가지 모두 성립해야 데드락 발생

(하나라도 성립하지 않으면 데드락 문제 해결 가능)

 

상호 배제(Mutual exclusion)

자원은 한번에 한 프로세스만 사용할 수 있음

점유 대기(Hold and wait)

최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 함

비선점(No preemption)

다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음

순환 대기(Circular wait)

프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함

 

데드락 처리

교착 상태를 예방 & 회피

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

 

1. 예방(prevention)

교착 상태 발생 조건 중 하나를 제거하면서 해결한다 (자원 낭비 엄청 심함)

• 상호배제 부정 : 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다.
  • 그러나 추후 동기화 관련 문제가 발생할 수 있다.
• 점유대기 부정 : 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류해서, 나중에 또 다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 한다.
  • 자원 낭비가 심하다
  • 예를 들어, 10분 동안 프린터 사용 후 마지막 10초에 스캐너 필요하다고 할 때 처음부터 스캐너를 확보하게 된다.
• 비선점 부정 : 이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 한다.
  • 계속 뺏고 다시 할당해야 한다. 작업 중단 → 복구 → 재실행 비용이 크다.
  • 프린터 출력, 파일 쓰기 같은 자원은 중간에 회수하기 어렵다.
• 순환대기 부정 : 자원을 순환 형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 한다.

이러한 조건을 방지해서 데드락을 예방하는 방법은 시스템의 처리량이나 효율성을 떨어트리는 단점이 발생할 수 있다.

다음에 살펴볼 데드락 회피법은 예방법보다는 조금 덜 제한적인 방법으로 예방법의 단점을 일부 해결할 수 있다.

 

2. 회피(avoidance)

데드락 회피법에서는 Safe sequence, Safe state 등이 키워드이다.

 

시스템의 프로세스들이 요청하는 모든 자원을, 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해 줄 수 있다면 안정 상태(safe state)에 있다고 말한다. 

 

그리고 이처럼 특정한 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서를 찾을 수 있다면, 그것을 안전 순서(safe sequence)라고 부른다.

 

반면 불안정 상태는 안정 상태가 아닌 상황을 말한다. 즉, 데드락 발생 가능성이 있는 상황이며, 교착상태(데드락)는 불안정 상태일 때 발생할 수 있다. 불안정 상태가 교착 상태보다 좀 더 큰 집합이다. (즉, 교착 상태가 불안정 상태의 부분집합)

 

이처럼 회피 알고리즘은 자원을 할당한 후에도 시스템이 항상 Safe state에 있을 수 있도록 할당하자는 것이 기본 특징이다. 이러한 특징을 살린 알고리즘으로 유명한 것이 은행원 알고리즘이다.

은행원 알고리즘

다익스트라가 제안한 기법으로, 어떤 자원의 할당을 허용하는지에 관한 여부를 결정하기 전에, 
미리 결정된 모든 자원들의 최대 가능한 할당량을 가지고 시뮬레이션 해서 Safe state에 
들 수 있는지 여부를 검사합니다. 즉 대기중이 다른 프로세스들의 활동에 대한 교착 상태 가능성을 
미리 조사하는 것입니다.

 

은행원 알고리즘 설명 링크

#24 데드락 해결 by 은행원 알고리즘(Banker's algorithm)

 

교착 상태를 탐지 & 회복

먼저 시스템이 데드락 예방이나 회피법을 사용하지 않았을 때, 데드락이 발생할 수 있으니 여기에서 회복하기 위해 데드락을 탐지하고, 회복하는 알고리즘을 사용한다.

 

1. 탐지 기법

• Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 여부를 탐색한다. 즉, 은행원 알고리즘에서 했던 방식과 유사하게 현재 시스템의 자원 할당 상태를 가지고 파악한다.
• 이 외에도 자원 할당 그래프를 통해 탐지하는 방법도 있다.

2. 회복 기법

데드락을 탐지 기법을 통해 발견했다면, 순환 대기에서 벗어나 데드락으로부터 회복하기 위한 방법을 사용한다.

• 단순히 프로세스를 1개 이상 중단시키기
  • 교착 상태에 빠진 모든 프로세스를 중단시키는 방법 : 계속 연산중이던 프로세스들도 모두 일시에 중단되어 부분 결과가 폐기될 수 있는 부작용이 발생할 수 있다.
  • 프로세스를 하나씩 중단 시킬 때마다 탐지 알고리즘으로 데드락을 탐지하면서 회복시키는 방법 : 매번 탐지 알고리즘을 호출 및 수행해야 하므로 부담이 되는 작업일 수 있다.
• 자원 선점하기
  • 프로세스에 할당된 자원을 선점해서, 교착 상태를 해결할 때까지 그 자원을 다른 프로세스에 할당해주는 방법

 

참고 자료

https://gyoogle.dev/blog/computer-science/operating-system/DeadLock.html

데드락 (DeadLock, 교착 상태) | 👨🏻‍💻 Tech Interview

https://chanhuiseok.github.io/posts/cs-2/

[운영체제] 데드락(Deadlock, 교착 상태)이란?