교착 상태(deadlock)

Posted Jul 12, 2022

By your_full_name 7 min read

교착 상태란

두 개 이상의 작업이 상대방의 작업이 끝나기만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태
- A 스레드가 B 스레드에 할당된 자원을 기다리고 있지만, B 스레드도 A 스레드에 할당된 자원을 기다리고 있는 경우
서로 마주 보고 있는 기차가 서로가 비켜주길 기다리는 상태와 같다.

다음 네 조건을 동시에 모두 만족해야 교착 상태가 발생한다.

상호배제(Mutual exclusion)
1. 프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구
2. 자원은 한 번에 하나의 프로세스만이 사용할 수 있다.
3. 다른 프로세스는 이미 점유 중인 자원을 사용하기 위해 기다려야 한다.
점유대기(Hold and wait)
1. 프로세스는 최소한 하나의 할당된 자원을 가진 상태에서 다른 자원을 기다려야 한다.
비선점(No preemption)
1. 프로세스는 다른 프로세스가 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다.
순환대기(Circular wait) :
1. 각 프로세스가 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.
2. 점유대기 조건과 비선점 조건을 만족해야 성립한다.

일반적으로 교착 상태를 해결하기 위한 세 가지 방법이 있다.

교착 상태를 무시하고 시스템에서 교착 상태가 절대 일어나지 않는다고 가정한다.
1. Linux와 Windows를 포함한 대부분의 운영 체제가 사용하는 방법
2. 교착 상태에 빠지지 않도록 프로그램을 작성해야 한다.
교착 상태를 예방하고 회피하기 위한 프로토콜을 사용하여 시스템이 절대 교착 상태로 들어가지 않도록 한다.
시스템이 교착 상태에 들어가는 걸 감지하고 해결한다.

교착 상태의 네 가지 조건 중 최소한 한 개의 조건 상황이 발생하지 않도록 해 교착 상태를 예방한다.

상호배제 조건의 제거
- 공유 가능한 자원은 상호배제 조건이 필요하지 않기 때문에 교착 상태를 예방할 수 있다.
  - 읽기 전용 파일은 대표적인 공유 가능한 자원이다.
- 하지만 어떠한 자원들은 본질적으로 공유 불가능하기 때문에 상호배제 조건을 제거해도 교착 상태를 완벽히 예방할 수 없다.
점유와 대기 조건의 제거
- 프로세스가 자원을 요청할 때 그 프로세스는 다른 자원을 가지고 있지 않도록 해야 한다.
- 사용 가능 프로토콜
  1. 각 프로세스가 실행되기 전에 모든 자원을 할당시킨다.
  2. 프로세스는 자원이 전혀 없을 때만 자원을 요청한다.
- 자원을 사용하는데 효율성이 낮으며, 기아 상태가 발생할 수 있는 문제점이 있다.
  - 기아 상태: 프로세스가 끊임없이 필요한 컴퓨터 자원을 가져오지 못하는 상황
비선점 조건의 제거
- 이미 선점 중인 자원을 요구할 때 실행을 멈추고 그 자원을 내주고, 다시 해당 자원을 가져올 수 있는 경우 재실행한다.
환형 대기 조건의 제거
- 자원 유형에 따라 순서를 매긴다.

자원이 어떻게 요청될지에 대한 추가정보를 요구하여 이를 바탕으로 시스템이 교착 상태가 발생하지 않도록 자원 할당 상태를 검사한다.
교착 상태 회피를 위한 알고리즘으로 크게 두 가지가 있다.
1. 자원 할당 그래프 알고리즘 (Resource Allocation Graph Algorithm)
2. 은행원 알고리즘 (Banker’s algorithm)

예방 혹은 회피기법을 프로그래밍해서 넣으면 성능에 큰 영향을 미칠 수 있게 된다. 그렇기 때문에 데드락의 발생 확률이 비교적 낮은 경우 별다른 조치를 취하지 않는다.

교착 상태를 감시/발견하는 알고리즘을 이용해 교착 상태 발생을 확인하고 해결한다.

This post is licensed under CC BY 4.0 by the author.