[운영체제] Deadlock (데드락, 또는 교착상태)

운영체제 기술면접에 대해 공부하다 보면 세마포어와 뮤텍스의 차이를 물어보는 질문이 자주 나옵니다.

이 차이를 알기 전!!!!!!! 

세마포어와 뮤텍스를 알기 위해서는 먼저 Deadlock 즉, 교착상태에 대해 먼저 알아야 합니다.

 

❓ Deadlock(교착상태)란?

운영체제에서 데드락(교착상태)란, 시스템 자원에 대한 요구가 뒤엉킨 상태입니다.

즉, 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황을 일컫습니다.

 

🔎 Deadlock의 발생조건

Deadlock에 걸리는 요건으로는 4가지가 있습니다.

 

첫 번째, 상호 배제 조건 (Mutual exclusion condition)

프로세스는 한 번에 하나의 자원만 사용할 수 있습니다.

사용 중인 자원을 다른 프로세스가 사용하기 위해서는 사용 중인 자원이 해제될 때까지 기다려야 합니다.

 

두 번째, 점유와 대기 조건 (hole-and-wait condition)

자원을 최소한 하나 보유하고 다른 프로세스에 할당되어 사용중인 자원을 점유하기 위해 기다려야 합니다.

 

세 번째, 비선점 조건 (nopreemption condition)

이미 할당되어 사용중인 자원을 다른 프로세스가 선점할 수 없습니다.

 

네 번째, 순환 대기 조건 (circular-wait condition)

대기 프로세스의 집합이 순환 형태로 자원을 사용하기 위해 대기하고 있어야 합니다.

 

 

그럼 이러한 Deadlock을 해결하기 위해서는 어떤 방법이 있을까요?

👍 데드락 해결 방법 

데드락의 해결 방법은 크게 예방, 회피, 탐지 및 회복하기 가 있습니다.]

 

첫 번째, Deadlock의 상태를 미리 예방합니다.

데드락의 발생조건 4가지 중 하나라도 발생하지 못하게 하면 데드락이 발생하지 않습니다.

즉, 데드락의 발생조건을 방지하여 데드락이 일어날 가능성을 예방합니다.

 

자원의 상호 배제 조건

한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 합니다.

 

점유 대기 조건 방지

프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류해서, 나중에 또 다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 합니다.

 

비선점 조건 방지

다른 프로세스에게 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 합니다.

 

순환 대기 조건 방지

자원을 순환 형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 합니다.

 

하지만, 이와 같이 미리 Deadlock을 예방하게 되면 시스템의 처리량이나 효율성을 떨어트리는 문제점이 발생할 수 있습니다.

 

두 번째, 데드락의 상태를 인정하고 회피합니다.

시스템의 프로세스들이 요청하는 모든 자원을,

데드락을 발생시키지 않으면서 차례로 모두에게 줄 수 있다면 안정 상태에 있다 라고 합니다.

 

또는 특정한 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 Deadlock이 발생하지 않는 순서를 안전 순서 라고 합니다.

 

반면 Deadlock 발생 가능성이 있는 상황을 불안정 상태라고 합니다.

 

교착 상태를 인정하고 피해 가기 위해 시스템이 항상 안정 상태에 있을 수 있도록 자원을 할당하는 방법이 있습니다. 

 

 

세 번째, 데드락을 탐지하고 회복합니다.

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

 

여기서 탐지 기법이란,

Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 여부를 탐색합니다. 이 외에도 자원 할당 그래프를 통해 탐지하는 방법도 있습니다.

 

회복 기법이란, 

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

교착 상태에 빠진 모든 프로세스를 중단시키거나, 프로세스를 하나씩 중단 시킬 때마다 탐지 알고리즘으로 데드락을 탐지하면서 회복시키는 방법이 있습니다.

또는 프로세스에 할당된 자원을 선점해서, 교착 상태를 해결할 때까지 그 자원을 다른 프로세스에 할당해 주는 방법이 있습니다.