교착상태

교착상태(Deadlock)의 개념

시스템 측면에서 자원의 요구가 뒤엉킨 상태.

한 프로세스 집합 내의 프로세스들에 의해 발생할 사건(Event)을 프로세스들이 서로 기다리고 있는 상태.

둘 이상의 작업이 보류 상태에 놓여 중요한 자원을 이용하기 위해 기다릴 때 발생함.

제한된 자원 이용률을 높이고 시스템 효율성을 증가시키기 위해 사용하는 병행 처리 기술과 자원 공유에 따른 부작용임.

대표

사진 설명을 입력하세요.

초기 일괄처리 시스템

사용자들이 작업 제어카드에 작업을 완료하기 위해 필요한 자원을 명시하여 교착상태가 자주 발생하지 않음.

운영체제가 요청한 자원이 준비 큐로 이동하기 전 사용 가능 여부를 확인하여 할당.

자원이 확보되지 않으면 작업이 준비 큐로 이동할 수 없어 교착상태가 발생하지 않음.

대화식 시스템

동적 자원 공유로 자원의 이용도를 높이는 과정에서 교착상태 발생.

예 1 : DVD 드라이브와 프린트가 각각 하나씩 존재하고 다음과 같은 경우.

- 프로세스 P : DVD 드라이브 점유 → 프린터 요청

- 프로세스 Q : 프린터 점유 → DVD 드라이브 요청

예 2: 테이프 드라이브가 3개 존재하고 다음과 같은 경우.

- 프로세스 P : 테이프 드라이브 점유

- 프로세스 Q : 테이프 드라이브 점유

- 프로세스 R : 테이프 드라이브 점유

대표

사진 설명을 입력하세요.

프로세스는 다음 순서로 자원을 이용.

요청

- 프로세스가 필요한 자원을 요청함.

- 요청이 즉시 받아들여지지 않으면 다른 프로세스가 사용 중이므로 할당 받을 때까지 대기함.

사용

- 프로세스가 요청한 자원을 사용.

해제

- 프로세스가 자원 사용을 마친 후, 할당 받은 자원을 되돌려 줌.

자원의 요청과 해제 그리고 파일이나 입출력 장치를 읽거나 쓰는 자원의 사용도 시스템 호출에 의해 이루어짐.

운영체제는 프로세스가 자원 요청 시, 할당 받을 수 있도록 항상 확인하고 기록함.

교착상태 발생

파일을 요청할 때의 교착상태

파일을 이용해 작업이 실행되는 동안, 파일에 대한 다른 작업의 점유 요청이 인정되면 교착 상태 발생.

파일 요청 시 발생하는 교착상태 예. (그림 5-3)

- 두 개의 프로세스(판매, 재고)와 두 개의 파일(공급자 파일, 재고 파일) 자원을 이용한 교착상태 표현.

- 할당 요구 순서는 아래와 같음.

① 프로세스 1(판매)은 판매 계획을 위해 공급자 파일을 요청해서 얻는다(할당).

② 프로세스 2(재고)는 재고 확인을 위해 재고 파일을 요청해서 얻는다(할당).

③ 프로세스 1은 주문 요청한 판매를 위해 재고 파일을 요청하지만 허용되지 않는다.

④ 프로세스 2는 주문을 위해 공급자 파일을 요청하지만 허용되지 않는다.

대표

사진 설명을 입력하세요.

전용장치를 할당할 때의 교착상태

전용장치 할당 시 발생하는 교착 상태 예.

- 두 사용자(프로세스 1, 프로세스 2)가 각각 테이프 드라이브 한 대를 사용하고, 한 테이프에서 다른 테이프로 복사하는 작업을 할 경우.

- 할당 요구 순서는 다음과 같이 이루어진다 가정함.

① 프로세스 1은 테이프 드라이브 1을 요청해서 얻는다(할당).

② 프로세스 2는 테이프 드라이브 2를 요청해서 얻는다(할당).

③ 프로세스 1은 테이프 드라이브 2를 요청하지만 허용되지 않는다.

④ 프로세스 2는 테이프 드라이브 1을 요청하지만 허용되지 않는다.

다중 주변 장치를 할당할 때의 교착 상태

다중 주변 장치 할당 요구에 의한 교착 상태 예.

- 세 개의 프로그램(프로세스 1, 프로세스 2, 프로세스 3)과 세 개의 전용 장치(테이프 드라이브, 프린터, 플로터)를 사용하는 경우.

- 할당 요구 순서는 아래와 같다 가정함.

① 프로세스 1은 테이프 드라이브를 요청해서 얻는다(할당).

② 프로세스 2는 프린터를 요청해서 얻는다(할당).

③ 프로세스 3은 플로터를 요청해서 얻는다(할당).

④ 프로세스 1은 프린터를 요청하지만 허용되지 않는다.

⑤ 프로세스 2는 플로터를 요청하지만 허용되지 않는다.

⑥ 프로세스 3은 테이프 드라이브를 요청하지만 허용되지 않는다.

대표

사진 설명을 입력하세요.

스풀링 시스템에서의 교착상태

스풀링 시스템에서 디스크에 할당된 스풀 공간의 출력이 완료되지 않은 상태에서 다른 작업이 스풀 공간을 모두 차지하면 교착상태가 발생.

스풀링 처리부(Input Spooler)에 필요량보다 많은 공간을 배당하여 교착상태 발생률을 줄일 수 있으나 비용이 많이 듬.

스풀링 파일의 ‘일정 포화 임계치(Saturation Threshold)’를 설정하여 교착 상태 예방 가능하나 시스템의 처리량이 줄어들 수 있음.

- 예 : 약 75% 정도에 이르면 새로운 작업을 읽어 들이지 못하도록 하여 교착상태를 예방.

디스크를 공유할 때의 교착상태

디스크는 대표적인 공유 자원으로, 사용에 대한 제어가 없다면 교착상태가 발생할 수 있음.

디스크 공유 시 발생하는 교착상태 예.

- 프로세스 P1이 실린더 55의 내용을 읽도록 명령함.

- 디스크 헤드는 실린더 55로 이동, P1은 중지상태가 되고 입출력 채널은 다음 입출력을 요구함.

- 프로세스 P2가 입출력 채널 제어권을 넘겨받아 실린더 245에 위치한 레코드에 쓰기를 명령함.

- 디스크 헤드는 실린더 245로 이동, P2는 중지상태.

- 입출력 채널 제어권은 다시 P1으로 이동, P1은 실린더 55의 코드 읽기를 명령함.

- 디스크 헤드는 실린더 55로 이동, P2는 입출력 채널 제어권을 넘겨받아 다시 명령함.

대표

사진 설명을 입력하세요.

네트워크에서의 교착상태

네트워크가 붐비거나 입출력(I/O) 버퍼 공간이 부족한 네트워크 시스템이 메시지 흐름을 제어하는 적절한 프로토콜을 가지지 못한 경우 교착상태 발생.

네트워크에서 발생하는 교착상태 예. (그림 5-6)

- 화살표는 메시지 흐름을 나타냄.

- 노드 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, P2 는 P3, Pn-1은 Pn, Pn 은 P0이 보유하고 있는 자원을 각각 얻기 위해 대기하는 경우.

대표

사진 설명을 입력하세요.

강 건너기 교착상태 예. (그림 5-8)

여러 개의 돌로 된 징검다리가 있는 강을 건너는 경우.

징검다리의 돌 하나는 한 쪽에서 한 사람만 디딜 수 있음(상호배제 성립).

강을 건너는 사람을 프로세스, 징검다리의 돌을 자원이라 가정함.

- 두 사람이 동시에 서로 다른 방향에서 출발, 강 중간에서 만나면 교착상태가 발생했다 할 수 있음.

- 돌을 딛는 것을 자원 할당, 발을 떼는 것을 자원 해제로 볼 때 동시에 같은 돌을 디디려 하면 교착상태가 발생함.

- 각 사람은 돌 하나를 딛고 다음 돌을 요구함(점유와 대기 조건 만족).

- 사람이 딛고 있는 돌을 강제로 제거할 수 없음(비선점 조건 만족).

- 왼쪽에서 오는 사람은 오른쪽 사람을, 오른쪽에서 오는 사람은 왼쪽 사람을 기다림(순환대기 조건 만족).

해결 방법

① 둘 중 한 사람이 되돌아간다(복귀).

② 강을 건너기 전에 상대편 강 쪽을 확인하고 출발한다.

③ 강의 한쪽 편에 우선권을 부여한다.

대표

사진 설명을 입력하세요.

자원 할당 그래프를 이용한 교착상태 표현

방향 그래프인 시스템 자원 할당 그래프를 이용하여 교착 상태 기술.

G = (V, E)로 구성, 정점 집합(V)은 두 가지 형태로 나뉨.

- 프로세스 집합인 P = {P1, P2, …, Pn}

- 시스템 내의 모든 자원들로 구성된 간선 집합(E)인 R = {R1, R2, …, Rn}

집합 E의 각 원소는 (Pi, Rj)나 (Rj, Pi) 같은 순서쌍으로 나타내고, Pi로 프로세스를, Rj로 자원을 표시함.

- Pi → Rj (요청 연결선) : 프로세스 Pi에서 자원 형태 Rj로의 연결선, 프로세스 Pi가 자원 형태 Rj를 요청하는 상태를 의미함(대기).

- Rj → Pi (할당 연결선) : 자원 형태 Rj에서 프로세스 Pi로의 연결선, 자원 형태 Rj가 프로세스 Pi에 할당됨을 의미함(할당).

자원 할당 그래프에 사이클이 존재 시, 원형 안의 프로세스와 자원이 교착 상태에 있음을 의미.

대표

사진 설명을 입력하세요.

자원 할당 그래프 표현

프로세스 Pi는 원, 자원 형태 Rj는 사각형으로 표기함.

원 안에 그려진 작은 원(검은색 점)은 각 집합체의 자원 개수를 나타냄.

할당 연결선은 사각형 안의 작은 점 하나를 가리키고, 요청 연결선은 사각형 Rj만을 가리킴.

- 프로세스 Pi가 자원 형태 Rj의 한 자원을 요청하면, 요청 연결선을 자원 할당 그래프 안에 삽입함.

- 요청이 만족 시 요청 연결선은 즉시 할당 연결선으로 변환, 프로세스가 자원을 해제하면 할당 연결선은 삭제됨.

[그림 5-11]의 자원 할당 그래프는 다음 상황을 의미함.

- 집합 P, R, E

P = {P1, P2, P3}

R = {R1, R2, R3, R4}

E = {P1→R1, P2→R3, R1→P2, R2→P2, R2→P1, R3→P3}

- 자원의 사례

* 자원 형태 R1은 한 개다.

* 자원 형태 R2는 두 개다.

* 자원 형태 R3는 한 개다.

* 자원 형태 R4는 세 개다.

대표

사진 설명을 입력하세요.

자원 할당 그래프 표현

[그림 5-11]의 자원 할당 그래프는 다음 상황을 의미함.

- 프로세스 상태

* 프로세스 P1은 자원 R2의 한 개를 점유하고, 자원 R1을 기다린다.

* 프로세스 P2는 자원 R1과 R2를 각각 한 개씩 점유하고, 자원 R3을 기다린다.

* 프로세스 P3은 자원 R3을 점유하고 있다.

대표

사진 설명을 입력하세요.

그래프의 주기가 없다면 시스템에 교착 상태가 발생하지 않음.

각 자원 형태가 정확히 자원 하나만 가진다면 주기는 교착상태임을 암시.

주기가 하나뿐인 자원 집합에만 연관되어 있다면 각각 자원을 하나만 가지므로 교착상태 발생.

주기에 포함된 각 프로세스는 교착상태에 있으며, 이 경우에 그래프의 주기는 교착상태의 필요충분 조건이 됨.

여러 개의 자원에 주기가 있어도 반드시 교착상태의 발생을 의미하지 않음.

그래프의 주기는 교착상태 발생의 필요 조건이기 때문.

[그림 5-12] 교착상태의 그래프

- 프로세스 P3이 자원 형태 R2의 자원을 요청한다 가정함.

- 사용 가능한 자원이 없으므로 요청 연결선 P3 → R2를 그래프에 추가.

- 이 시점에서 두 개의 주기가 시스템에 존재함

① P1 → R1 → P2 → R3 → P3 → R2 → P1

② P2 → R3 → P3 → R2 → P2

대표

사진 설명을 입력하세요.

[그림 5-13] 사이클이 있으나 교착상태가 아닌 그래프

- 주기는 있으나 교착상태는 없음.

- 프로세스 P4가 자원 R2를 해제할 수 있으며, 해제한 자원을 P3에 할당하면 주기가 없어짐.

* P1 → R1 → P3 → R2 → P1

대표

사진 설명을 입력하세요.

※ 자원할당 그래프에 주기가 없다면 시스템은 교착상태가 아님.

※ 주기가 있다면 시스템은 교착상태일 수도 있고, 아닐 수도 있음.