[OS] 교착 상태(deadlock) 개념과 발생 원인

교착 상태의 개념

교착 상태(deadlock) 결코 일어나지 않을 사건(event)을 기다리는 상태. 즉, 컴퓨터에서는 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원(비공유)을 기다릴 때를 의미한다.

프로세스 A는 스캐너 사용 권한을 요청하여 허용되었고, 프로세스 B는 CD 레코터를 요청하여 허용
프로세스 A가 CD 레코더를 요청하더라도 프로세스 B가 CD 레코더를 해제할 때까지 요청 거부
프로세스 B가 CD 레코더를 해제하지 않고 스캐너를 요청하면 두 프로세스는 서로 차단되어 영원히 기다림.

초기 일관 처리 시스템에서는 교착 상태가 발생하지 않았다. 사용자가 작업 제어 카드에 작업을 완료하는데 필요한 자원을 명시했고 일관 처리 시스템의 OS는 요청한 자원을 준비 큐로 이동시키기 전에 먼저 사용 가능 여부를 확인했기 때문이다.

반면 대화식 시스템에서는 동적 자원을 공유하여 자원의 사용률을 높이는 과정에서 교착 상태가 발생할 가능성이 있었다.

교착 상태가 일어나는 이유

제한된 자원의 사용률과 효율성을 높이기 위해 병행 처리 기술과 자원 공유에 따른 부작용이다. 교착 상태를 이해하려면 먼저 프로세스가 어떤 순서로 자원을 사용하는지 알아야 한다.

자원 요청 : 프로세스가 필요한 자원을 요청한다. 해당 자원을 사용할 수 있으면 요청을 즉시 수락하지만, 해당 자원을 다른 프로세스가 사용 중이면 요청을 수락할 떄까기 대기한다.
자원 사용 : 프로세스가 요청한 자원을 획득하여 사용한다.
자원 해제 : 프로세스가 자원 사용을 마친 후 해당 자원을 되돌려(해제) 준다.

교착 상태는 어떤 작업에 필요한 자원을 다른 작업이 점유하여 사용할 수 없을 때 발생하므로 교상 상태에서는 자원의 요청과 해제가 중요
자원 요청, 해제 그리고 파일이나 IO 장치 등 자원을 읽거나 쓰는 자원의 사용도 시스템 콜로 이루어짐.
그러므로 OS는 프로세스가 자원을 요청하면 할당받을 수 있도록 항상 확인하고 기록해야 한다.

교착 상태의 예

스풀링 시스템에서 발생하는 교착 상태

디스크에 할당된 스풀 공간의 출력을 완료하지 않은 상태에서 다른 작업이 스풀 공간을 모두 차지할 때 발생.
스풀링 처리부(Input Spooler)에 필요량보다 많은 공간을 배당하여 교착 생타 발생률을 줄일 수 있으나 비용이 많이듬.
스풀링 공간의 "일정 포화 임계치(Saturation Threshold)"를 설정하면 예방 가능하나 그 만큼 시스템 처리량이 줄어들 수 있음.
- 예를 들어 스풀 공간이 75% 정도 차면 새로운 작업을 읽어 들이지 못하도록 하여 교착 상태를 예방.

디스크를 공유할 때

디스크 사용에 제어가 없으면 프로세스들이 서로 충돌하는 명령을 요청할 때 교착 상태가 발생.
디스크 공유 시 살생하는 교착 상태 예
- 프로세스 P1 이 실린더 55의 내용을 읽도록 명령함.
- 디스크 헤드는 실린더 55로 이동, P1 은 중지 상태가 될고 입출력 채널은 다음 입출력을 요구함.
- 프로세스 P2 가 입출력 채널 제어권을 넘겨받아 실린더 245에 위치한 레보드에 쓰기를 명령함.
- 디스크 헤드는 실린더 245로 이동, P2는 중지 상태.
- 입출력 채널 제어권은 다시 P1으로 이동, P1은 실린더 55의 코드 읽기를 다시 명령함.
- 디스크 헤드는 다시 실린더 55로 이동하는 동안 P2는 입출력 채널 제어권을 넘겨받아 다시 명령함.
- 결국 디스크 헤드는 실런더 55와 실런더 245 사이를 반복적으로 이동하여 두 서비스를 완료할 수 없음

네트워크

네트워크가 붐비거나 입출력(I/O) 버퍼 공간이 부족한 네트워크 시스템이 메시지 흐름을 제어하는 적절한 프로토콜을 가지지 못한 경우 교착 상태 발생
네트워크에서 발생하는 교착 상태 예
- 화살표는 메시지 흐름을 나타냄.
- 노드 N6, N7 에서 출발하여 목적지가 N2 인 메시지는 N1 의 출력 큐에 임시 저장됨.
- N3, N4 에서 출발하여 N1 이 목적지인 메시지는 N2 의 출력 큐에 임시 저장됨.
- N1 의 버퍼 공간이 부족할 때 N1 은 N2 로부터 메시지를 수신할 수 없음.
- N2 의 버퍼 공간이 부족할 때 N1 이나 다른 노드로부터 메시지를 수신할 수 없다면, N1 과 N2 사이의 통신 선로는 교착 상태에 빠짐.
- N1 은 N6, N7 로부터 메시지를 전송 받을 수 있으나, N2 로 전송이 불가능하므로 교착상태에 빠짐.

교착 생태의 발생 조건

교착 상태는 시스템에서 다음 네 가지 조건을 만족할 때 발생한다.

이 중 ① ~ ③ 만 만족해도 교착 상태가 발생할 수도 있고, 발생하지 않을 수도 있음.
④ 는 ① ~ ③ 조건을 만족할 때 발생할 수 있는 결과이고, 점유와 대기 조건을 포함하므로 네 가지 조건이 모두 독립적인 것은 아님

① 상호 배제

자원을 최소 하나 이상 비공유해야 한다. 즉, 한 번에 프로세스 하나만 해당 자원을 사용할 수 있어야 한다.
사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.

② 점유와 대기

자원을 최소한 하나 정도는 보유하고, 다른 프로세스에 할당된 자원을 얻으려고 기다리는 프로세스가 있어야 한다.

③ 비선점

자원을 선점할 수 없다. 즉, 자원은 강제로 빼앗을 수 없고, 자원을 점유하고 있는 프로세스가 끝나야 해제된다.

※ 위 세가지 조건으로 발생할 수 있으나, 발생하지 않을 수도 있으며, 교착상태 발생에는 반드시 아래 조건이 요구됨.

④ 순환 대기

대기 프로세스 집합 {P0, P1, ... Pn}이 있을 때, P0 은 P1 이 보유한 자원을, P1 은 P2 가 보유한 자원을, ..., Pn-1 은 Pn이 보유한 자원을, Pn 은 P0 이 보유한 자원을 각각 얻으려고 기다리는 것을 순환 대기하고 한다.

※ 참고

선점 자원과 비선점 자원

컴퓨터 자원은 성질에 따라 선점 자원과 비선점 자원으로 구분하여 생각할 수 있다.

선점 자원

부작용 없이 소유한 프로세스에서 빼앗아 선점할 수 있는 자원이다. 일정 시간 동안 특정 프로세스에 할당했다가 다른 프로세스에 할당하고 다시 부작용 없이 처음 프로세스에 재할당 할 수 있다.
ex. 메모리, 버퍼, 프로세서

비선점 자원

하나의 프로세스에서 빼앗아 선점할 수 없고, 부작용 없이 다른 프로세스에 할당할 수 없는 자원이다. 그러므로 계산 오류를 발생시키지 않고 현재 소유자에게서 빼앗을 수 없다.
ex. 프린터, CD 드라이브, 스캐너, 디스크 드라이브, 임계 영역 등

보통 교착 상태는 비선점 자원이 발생시킨다. 선점 자원을 사용할 때도 발생할 수 있지만, 선점 자원은 일반적으로 하나의 프로세스에서 다른 자원을 재할당하여 해결할 수 있다.

강 건너기 교착 상태 예

여러 개의 돌로 된 징검다리가 있는 강을 건너는 경우
징검 다리의 돌 하나는 한 쪽에서 한 사람만 디딜 수 있음 (상호배제 성립)
강을 건너는 사람을 프로세스, 징검다리의 돌을 자원이라 가정.
- 두 사람이 동시에 서로 다른 방향에서 출발, 강 중간에서 만나면 교착 상태가 발생했다 할 수 있음.
- 돌을 딛는 것을 자원 할당, 발을 떼는 것을 자원 해제로 볼 때 동시에 같은 돌을 디디려 하면 교착 상태가 발생함.
- 각 사람은 돌 하나를 딛고 다음 돌을 요구함 (점유와 대기 조건 만족)
- 사람이 딛고 있는 돌을 강제로 제거할 수 없음 (비선점 조건 만족)
- 왼쪽에서 오는 사람은 오른쪽 사람을, 오른쪽에서 오는 사람은 왼쪽 사람을 기다림 (순환대기 조건 만족)
해결 방법
- 둘 중 한 사람이 되돌아간다 (복귀)
- 징검다리 반대편을 먼저 확인하고 출발한다.
- 강의 한쪽 편에 우선권을 부여한다.