OS의 교착상태(Deadlock)

[운영체제] 데드락(Deadlock, 교착 상태)이란? | ChanBLOG (chanhuiseok.github.io)

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

상기 블로그 게시글을 학습한 내용입니다.

 

OS에서 교착상태란 시스템 자원에 대한 요구가 뒤엉킨 상태를 말한다.

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

데드락의 발생조건은 크게 4가지로 나뉜다.

1. 상호 배제

한 번에 프로세스 하나만 해당 자원을 사용할 수 있다. 사용 중인 ㅏㅈ원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.

2. 점유 대기

자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.

3. 비선점

이미 할당된 자원을 강제로 빼앗을 수 없다.

4. 순환 대기

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

이렇게 발생하는 데드락을 예방하려면 위 4가지 조건 중 하나라도 발생하지 않게 하는 것이 방법이다. 

자원의 상호 배제 조건을 방지하기 위해서 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다. 하지만 이는 추후 동기화 관련해 문제가 발생할 수 있다.

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

비선점 조건을 방지하기 위해서는 이미 다른 프로세스에게 할당된 자원이 선점권이 없다고 가정할 때, 높은 우선순위의 프로세스가 해당 자원을 선점할 수 있도록 한다.

마지막으로 순환 대기 조건을 방지하기 위해서 자원을 순환 형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 한다. 

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

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

데드락 회피법은 Safe sequence, Safe state 등이 있다.

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

그리고 특정한 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 데드락이 발생하지 않을 수 있다면 그것을 Safe sequence라고 한다.

반면에 불안정 상태는 데드락 발생 가능성이 있는 상황이며, 교착 상태가 발생할 수 있다. 불안정 상태는 교착 상태보다 좀 더 큰 집합이다. 

이처럼 회피법은 자원을 할당한 후에도 시스템이 항상 Safe state에 있을 수 있도록 할당을 허용하자는 것이 기본 특징이다. 

이러한 특징을 살린 알고리즘으로 '은행원 알고리즘'이 있다. 

또한 데드락의 탐지와 회복에는 그에 따른 알고리즘을 사용한다.

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

데드락을 탐지했다면 순환 대기에서 벗어나 데드락으로부터 회복하기 위한 방법을 사용한다.
먼저 단순하게 프로세스 1개 이상을 중단시키는 것이다. 먼저 교착 상태에 빠진 모든 프로세스를 중단시키는 방법이 있는데, 이는 계속 연산중이던 프로세스들도 모두 일시에 중단되어 부분 결과가 폐기될 수 있다는 단점이 있다.
프로세스를 하나씩 중단 시킬 때 마다 탐지 알고리즘으로 데드락을 탐지하면서 회복시키는 방법도 있다. 다만 매번 알고리즘을 호출하고 수행해야 하기 때문에 부담이 될 수 있다.

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