5 교착상태와 기아상태

학습목표 내용 교착상태의 원리를 이해한다. 교착상태 해결을 위한 예방, 회피, 탐지, 회복을 알아본다. 기아상태 해결을 위해‘식사하는 철학자 문제’를 살펴본다. 내용 교착상태 개요 교착상태 해결 기법 교착상태 탐지 교착상태 회복 기법 기아상태

1. 교착상태 개요 교착상태(Deadlock)의 개념 시스템 측면에서 자원의 요구가 뒤엉킨 상태. 한 프로세스 집합 내의 프로세스들에 의해 발생할 사건(Event)을 프로세스들이 서로 기다리고 있는 상태. 둘 이상의 작업이 보류 상태에 놓여 중요한 자원을 이용하기 위해 기다릴 때 발생함. 제한된 자원 이용률을 높이고 시스템 효율성을 증가시키기 위해 사용하는 병행 처리 기술과 자원 공유에 따른 부작용임. [그림 5-1] 교착상태의 예: 교통마비 상태

1. 교착상태 개요 초기 일괄처리 시스템 대화식 시스템 사용자들이 작업 제어카드에 작업을 완료하기 위해 필요한 자원을 명시하여 교착상태가 자주 발생하지 않음. 운영체제가 요청한 자원이 준비 큐로 이동하기 전 사용 가능 여부를 확인하여 할당. 자원이 확보되지 않으면 작업이 준비 큐로 이동할 수 없어 교착상태가 발생하지 않음. 대화식 시스템 동적 자원 공유로 자원의 이용도를 높이는 과정에서 교착상태 발생. [그림5-2] 교착상태 예 예 1 : DVD 드라이브와 프린트가 각각 하나씩 존재하고 다음과 같은 경우. - 프로세스 P : DVD 드라이브 점유 → 프린터 요청 - 프로세스 Q : 프린터 점유 → DVD 드라이브 요청 예 2: 테이프 드라이브가 3개 존재하고 다음과 같은 경우. - 프로세스 P : 테이프 드라이브 점유 - 프로세스 Q : 테이프 드라이브 점유 - 프로세스 R : 테이프 드라이브 점유 또 다른 테이프 드라이브 요청

1. 교착상태 개요 프로세스는 다음 순서로 자원을 이용. 요청 사용 해제 - 프로세스가 필요한 자원을 요청함. - 요청이 즉시 받아들여지지 않으면 다른 프로세스가 사용 중이므로 할당 받을 때까지 대기함. 사용 - 프로세스가 요청한 자원을 사용. 해제 - 프로세스가 자원 사용을 마친 후, 할당 받은 자원을 되돌려 줌. 자원의 요청과 해제 그리고 파일이나 입출력 장치를 읽거나 쓰는 자원의 사용도 시스템 호출에 의해 이루어짐. 운영체제는 프로세스가 자원 요청 시, 할당 받을 수 있도록 항상 확인하고 기록함.

1. 교착상태 개요 교착상태 발생 파일을 요청할 때의 교착상태 파일을 이용해 작업이 실행되는 동안, 파일에 대한 다른 작업의 점유 요청이 인정되면 교착 상태 발생. 파일 요청 시 발생하는 교착상태 예. (그림 5-3) - 두 개의 프로세스(판매, 재고)와 두 개의 파일(공급자 파일, 재고 파일) 자원을 이용한 교착상태 표현. - 할당 요구 순서는 아래와 같음. ① 프로세스 1(판매)은 판매 계획을 위해 공급자 파일을 요청해서 얻는다(할당). ② 프로세스 2(재고)는 재고 확인을 위해 재고 파일을 요청해서 얻는다(할당). ③ 프로세스 1은 주문 요청한 판매를 위해 재고 파일을 요청하지만 허용되지 않는다. ④ 프로세스 2는 주문을 위해 공급자 파일을 요청하지만 허용되지 않는다. [그림5-3] 파일을 요청할 때의 교착상태

1. 교착상태 개요 전용장치를 할당할 때의 교착상태 다중 주변 장치를 할당할 때의 교착 상태 전용장치 할당 시 발생하는 교착 상태 예. - 두 사용자(프로세스 1, 프로세스 2)가 각각 테이프 드라이브 한 대를 사용하고, 한 테이프에서 다른 테이프로 복사하는 작업을 할 경우. - 할당 요구 순서는 다음과 같이 이루어진다 가정함. ① 프로세스 1은 테이프 드라이브 1을 요청해서 얻는다(할당). ② 프로세스 2는 테이프 드라이브 2를 요청해서 얻는다(할당). ③ 프로세스 1은 테이프 드라이브 2를 요청하지만 허용되지 않는다. ④ 프로세스 2는 테이프 드라이브 1을 요청하지만 허용되지 않는다. 다중 주변 장치를 할당할 때의 교착 상태 다중 주변 장치 할당 요구에 의한 교착 상태 예. - 세 개의 프로그램(프로세스 1, 프로세스 2, 프로세스 3)과 세 개의 전용 장치(테이프 드라이브, 프린터, 플로터)를 사용하는 경우. - 할당 요구 순서는 아래와 같다 가정함. ① 프로세스 1은 테이프 드라이브를 요청해서 얻는다(할당). ② 프로세스 2는 프린터를 요청해서 얻는다(할당). ③ 프로세스 3은 플로터를 요청해서 얻는다(할당). ④ 프로세스 1은 프린터를 요청하지만 허용되지 않는다. ⑤ 프로세스 2는 플로터를 요청하지만 허용되지 않는다. ⑥ 프로세스 3은 테이프 드라이브를 요청하지만 허용되지 않는다. [그림5-4] 장치 할당 요구에 의한 교착상태

1. 교착상태 개요 스풀링 시스템에서의 교착상태 디스크를 공유할 때의 교착상태 스풀링 시스템에서 디스크에 할당된 스풀 공간의 출력이 완료되지 않은 상태에서 다른 작업이 스풀 공간을 모두 차지하면 교착상태가 발생. 스풀링 처리부(Input Spooler)에 필요량보다 많은 공간을 배당하여 교착상태 발생률을 줄일 수 있으나 비용이 많이 듬. 스풀링 파일의 ‘일정 포화 임계치(Saturation Threshold)’를 설정하여 교착 상태 예방 가능하나 시스템의 처리량이 줄어들 수 있음. - 예 : 약 75% 정도에 이르면 새로운 작업을 읽어 들이지 못하도록 하여 교착상태를 예방. 디스크를 공유할 때의 교착상태 디스크는 대표적인 공유 자원으로, 사용에 대한 제어가 없다면 교착상태가 발생할 수 있음. 디스크 공유 시 발생하는 교착상태 예. - 프로세스 P1이 실린더 55의 내용을 읽도록 명령함. - 디스크 헤드는 실린더 55로 이동, P1은 중지상태가 되고 입출력 채널은 다음 입출력을 요구함. - 프로세스 P2가 입출력 채널 제어권을 넘겨받아 실린더 245에 위치한 레코드에 쓰기를 명령함. - 디스크 헤드는 실린더 245로 이동, P2는 중지상태. - 입출력 채널 제어권은 다시 P1으로 이동, P1은 실린더 55의 코드 읽기를 명령함. - 디스크 헤드는 실린더 55로 이동, P2는 입출력 채널 제어권을 넘겨받아 다시 명령함. [그림5-5] 디스크 제어기가 프로세서와 독립적으로 작동할 때의 교착상태

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

1. 교착상태 개요 교착상태 발생 조건 다음 네 가지 조건이 동시에 발생할 때, 즉 필요충분조건이 성립될 때 발생. 상호배제 - 자원이 최소 하나 이상 비공유, 즉 한 번에 한 프로세스만 해당 자원을 사용할 수 있어야 함. - 사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 대기해야 함. 점유와 대기 - 최소한 자원 하나를 보유하고 다른 프로세스에 할당된 자원을 얻기 위해 기다리는 프로세스가 있어야 함. 비선점 - 자원은 선점될 수 없음. 즉 자원을 강제로 뺏을 수 없으며 자원을 점유하고 있는 프로세스가 끝나야 해제됨. ※ 위의 세 가지 조건으로 발생할 수 있으나, 발생하지 않을 수도 있으며, 교착상태 발생에는 반드시 아래의 조건이 요구됨. 순환대기 - 대기 프로세스 집합 {P0, P1, …, Pn}이 있을 때, P0은 P1이 보유하고 있는 자원을, P1은 P2, P2 는 P3, Pn-1은 Pn, Pn 은 P0이 보유하고 있는 자원을 각각 얻기 위해 대기하는 경우. [그림5-7] 순환대기의 교착상태

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

1. 교착상태 개요 자원 할당 그래프를 이용한 교착상태 표현 방향 그래프인 시스템 자원 할당 그래프를 이용하여 교착 상태 기술. 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에 할당됨을 의미함(할당). 자원 할당 그래프에 사이클이 존재 시, 원형 안의 프로세스와 자원이 교착 상태에 있음을 의미. [그림5-10] P1, P2 가 교착상태 [그림5-9] Pi → Rj 와 Rj → Pi 그래프

1. 교착상태 개요 자원 할당 그래프 표현 프로세스 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] 자원 할당 그래프

1. 교착상태 개요 자원 할당 그래프 표현 [그림 5-11]의 자원 할당 그래프는 다음 상황을 의미함. - 프로세스 상태 * 프로세스 P1은 자원 R2의 한 개를 점유하고, 자원 R1을 기다린다. * 프로세스 P2는 자원 R1과 R2를 각각 한 개씩 점유하고, 자원 R3을 기다린다. * 프로세스 P3은 자원 R3을 점유하고 있다. 그래프의 주기가 없다면 시스템에 교착 상태가 발생하지 않음. 각 자원 형태가 정확히 자원 하나만 가진다면 주기는 교착상태임을 암시. 주기가 하나뿐인 자원 집합에만 연관되어 있다면 각각 자원을 하나만 가지므로 교착상태 발생. 주기에 포함된 각 프로세스는 교착상태에 있으며, 이 경우에 그래프의 주기는 교착상태의 필요충분 조건이 됨. [그림5-11] 자원 할당 그래프

1. 교착상태 개요 여러 개의 자원에 주기가 있어도 반드시 교착상태의 발생을 의미하지 않음. 그래프의 주기는 교착상태 발생의 필요 조건이기 때문. [그림 5-12] 교착상태의 그래프 - 프로세스 P3이 자원 형태 R2의 자원을 요청한다 가정함. - 사용 가능한 자원이 없으므로 요청 연결선 P3 → R2를 그래프에 추가. - 이 시점에서 두 개의 주기가 시스템에 존재함 ① P1 → R1 → P2 → R3 → P3 → R2 → P1 ② P2 → R3 → P3 → R2 → P2 [그림5-12] 교착상태의 그래프

1. 교착상태 개요 [그림 5-13] 사이클이 있으나 교착상태가 아닌 그래프 - 주기는 있으나 교착상태는 없음. - 프로세스 P4가 자원 R2를 해제할 수 있으며, 해제한 자원을 P3에 할당하면 주기가 없어짐. * P1 → R1 → P3 → R2 → P1 ※ 자원할당 그래프에 주기가 없다면 시스템은 교착상태가 아님. ※ 주기가 있다면 시스템은 교착상태일 수도 있고, 아닐 수도 있음. [그림5-13] 사이클이 있으나 교착상태가 아닌 그래프

2. 교착상태 해결 기법 교착상태 예방 기법 교착상태 해결 기법 교착상태를 해결하는 기법은 크게 3가지로 나뉨. 시스템이 교착상태가 되지 않도록 예방(방지)하는 것. 가능한 교착상태를 회피하는 것. 교착상태를 허용하되 교착상태에서 다시 회복할 수 있게 하는 것. - 사용하기 어렵고 오버헤드가 증가하므로 교재에서 살펴보지 않음. 교착상태 예방 기법 4가지의 교착상태 조건 중 하나라도 발생하지 않도록 함. 상호배제 문제는 고려해야 함. - 전용자원에서는 교착상태가 발생하지 않으므로 프로세스가 원하는 자원을 배타적으로 사용하려는 것은 제외시켜야 함. 하벤더(Havender, 1986년)가 상호배제를 제외한 세 가지 기본 방법 제안. ① 각 프로세스는 한 번에 필요한 모든 자원을 요구해야 하며, 요청한 자원을 모두 제공받기 전까지는 작업을 진행할 수 없음. ② 어떤 자원을 점유하고 있는 프로세스의 요구가 더 이상 허용되지 않으면 점유한 자원을 모두 반납하고 필요할 때 다시 자원을 요구해야 함. ③ 모든 프로세스에 자원을 순서대로 할당해야 함. 모든 프로세스에 각 자원 유형별로 할당 순서를 부여한 후, 순서에 따라 자원을 요구.

2. 교착상태 해결 기법 상호배제 조건 방지 점유와 대기 조건 방지 상호배제 조건은 자원의 비공유를 전제로 함. - 공유 가능한 자원들은 배타적인 접근을 요구하지 않으므로 교착상태가 발생하지 않음. 일반적으로 상호배제 조건을 거부하면 교착상태를 예방하는 것이 불가능함. - 어떤 자원은 공유 자체가 불가능한 것도 있음. 파일 쓰기는 배타적인 접근만이 허용되어야 함. - 하나 이상의 프로세스가 쓰기 권한을 가지면 교착상태가 발생할 가능성이 있음. 점유와 대기 조건 방지 최대 자원 할당. - 프로세스가 작업을 수행하기 전에 필요한 모든 자원을 요청하고 획득해야 함. - 보류 상태에서는 프로세스가 자원을 점유할 수 없으므로 대기 조건이 성립하지 않음. 점유와 대기 조건 방지를 위한 두 가지 방법. - 모든 프로세스는 자원을 요청하고 사용할 수 있음. - 프로세스가 자원을 더 요청하려면, 먼저 자신에게 할당된 자원을 해제해야 함. ① 자원 할당 시 시스템 호출된 프로세스 하나의 실행에 필요한 모든 자원을 먼저 할당하여 실행시킨 후 다른 시스템 호출에 자원을 할당함. ② 프로세스가 자원을 전혀 갖고 있지 않을 때만 자원을 요청할 수 있도록 허용함.

2. 교착상태 해결 기법 비선점 조건 방지 단점 이미 할당된 자원에 대한 선점권이 없어야 한다는 전제 조건을 가짐. ① 자원의 효율성이 낮음. - 많은 자원이 사용되지 않으면서 오랜 시간 할당되기 때문. ② 기아상태 발생이 가능함. - 자주 쓰는(이용하는) 자원이 다른 프로세스에 할당된 경우, 자원을 요청한 프로세스는 무한히 기다려야 하는 경우가 발생. - 적은 수의 자원을 요청한 프로세스의 우선순위가 높으므로, 많은 수의 자원을 요청한 프로세스의 대기 시간이 길어질 수 있음. 비선점 조건 방지 이미 할당된 자원에 대한 선점권이 없어야 한다는 전제 조건을 가짐. - 어떤 자원을 가진 프로세스가 자원 요청 시 기다려야 한다면, 프로세스는 현재 가진 자원을 모두 해제함. - 프로세스가 작업을 시작하려면 요청한 새로운 자원과 해제한 자원을 확보해야 함. - 작업 상태를 쉽게 저장 및 복구 가능할 때 또는 빈번하게 발생하지 않을 때만 좋은 수단으로 이용 가능. 두 가지 대안 제시됨. ① 프로세스가 어떤 자원을 요청할 때, 요청한 자원이 사용 가능한지 검사. - 사용 가능하다면 자원 할당, 사용 불가능한 경우 대기 프로세스가 요청한 자원을 점유하고 있는지 검사. - 요청한 자원을 대기 프로세스가 선점하고 있다면, 자원을 해제하고 요청 프로세스에 할당. - 요청한 자원을 사용할 수 없거나, 실행 중인 프로세스가 점유하고 있으면 요청 프로세스는 대기. ② 두 프로세스에 우선순위를 부여하여, 높은 우선순위의 프로세스가 그보다 낮은 순위의 프로세스가 점유한 자원을 선점하여 해결. - 프로세서 레지스터나 기억장치 레지스터와 같이 쉽게 저장되고 이후 복원이 쉬운 자원에 이용.

2. 교착상태 해결 기법 순환대기 조건 방지 계층적 요구 기법. - 모든 자원에 일련의 순서를 부여, 각 프로세스는 오름차순으로만 자원을 요청할 수 있게 함. - 순환대기의 가능성을 제거하여 교착상태를 예방. - 예상된 순서와 다르게 자원을 요구하는 작업은 자원 낭비를 초래함. R = {R1, R2, …, Rn}을 자원 형태 집합이라 가정하고, 각 자원 형태에 고유 숫자를 부여. 1:1 함수인 ‘F:R → N’으로 정의 가능하며, N은 자연수 집합을 의미함. ① 프로세스는 임의의 자원 Ri을 요청할 수 있지만 그 다음부터는 ‘F(Rj) > F(Ri)’인 경우에만 자원 형태 Rj를 요청할 수 있음. - 각 프로세스는 오름차순으로만 자원들을 요청할 수 있으며, 데이터 형태 자원이 여러 개 필요한 경우 우선 요청할 형태 자원 하나를 정해야 함. ② 프로세스가 자원 형태 Rj을 요청할 때마다 ‘F(Ri) ≥ F(Rj)’가 되도록 Rj의 모든 자원을 해제. 모순에 의한 증명 - 순환대기가 성립한다는 가정에서 사실의 성립. - 순환대기의 프로세스 집합을 {P0, P1, …, Pn}이라 가정하며, Pi는 프로세스 Pi+1이 점유하고 있는 자원 Ri를 대기함 (첨자는 모듈 n이며, Pn은 P0이 점유하고 있는 자원 Rn을 대기). - 프로세스 Pi+1은 자원 Ri+1을 요청하는 동안 자원 Ri를 점유하고 있으므로, 모든 i에 대하여 ‘F(Ri) < F(Ri+1)’이 성립되어야 함. - 이는 ‘F(R0) < F(R1) < … < (Rn) < F(R0)’이 성립함을 의미함. - 즉, ‘F(R0) < F(R0)’는 불가능하므로, 여기에 순환대기가 있을 수 없음. - 함수 F는 시스템에 있는 자원의 정상적인 이용 순서에 따라서 정의되어야 함.

2. 교착상태 해결 기법 계층적 요구의 단점 - 순환대기 조건 가능성을 제거하여 교착상태를 예방하지만, 반드시 그 자원이 가진 번호 순서로 요구해야 한다는 부담(자원 요구순서 예측)이 있음. - 번호 부여 시 실제로 자원을 사용하는 순서를 반영해야 함. ※ 운영체제의 중요한 목적 중 하나는 사용자가 이용하기 편리한 작업 환경을 제공하는 것. ※ 하벤더의 순서 배정법은 순환대기의 가능성을 제거했으나, 사용자가 손쉽고 편리하게 응용 프로그램을 작성하는데 어려움. ※ 순환대기 예방은 프로세스의 속도를 떨어뜨리고 자원에 대한 접근을 불필요하게 거부하므로 비효율적임.

2. 교착상태 해결 기법 교착상태 회피 기법 회피 기법은 크게 두 가지 방법 제시됨. 교착상태의 예방보다 덜 엄격한 조건을 요구함으로써 자원을 좀 더 효율적으로 이용하는 것을 목적으로 함. 교착상태가 일어날 가능성을 인정하고(세 가지 필요조건 허용) 교착상태가 일어나려고 할 때 적절히 회피하며, 이는 예방보다 더 병행성을 허용함. 회피 기법은 크게 두 가지 방법 제시됨. ① 프로세스의 시작 거부 - 프로세스의 요구가 교착상태를 일으킬 수 있다면 프로세스 시작을 중지함. ex: 현재 수행 중인 모든 프로세스의 최대 자원 요구량과 새로운 프로세스의 최대 요구량을 합한 자원 요구량을 수용할 수 있으면 새로운 프로세스를 수용. ② 자원 할당의 거부 - 프로세스가 요청한 자원을 할당했을 때, 교착상태가 발생할 수 있다면 요청한 자원을 할당하지 않음. - 일반적으로 은행가 알고리즘(Banker`’s Algorithm)이라 부름. 교착상태 회피를 위해 자원이 언제 요구되는지에 대한 추가정보가 필요함. - 각 프로세스마다 요청과 해제에 대한 정확한 순서를 파악하고 있다면 요청에 따른 프로세스 대기 여부를 결정 가능함. 요구를 받아들일 지 또는 기다리게 할지를 결정하기 위해 각 프로세스에 대한 요구와 해제를 미리 알고 있어야 함. - 필요한 정보의 양과 종류에 따라 다양한 교착상태 회피 알고리즘을 적용할 수 있음. - 프로세스가 요청할 자원마다 최대치 정보를 미리 파악할 수 있다면 시스템이 교착상태가 되지 않을 확실한 알고리즘을 만들 수 있음.

2. 교착상태 해결 기법 안정상태와 불안정상태 교착상태 회피 알고리즘은 시스템이 순환-대기 조건이 발생하지 않도록 자원 할당 상태를 검사함. 자원 할당 상태는 사용 가능한 자원의 수, 할당된 자원의 수, 프로세스들의 최대 요구 수에 의해 정의됨. 안정한 상태 - 각 프로세스에 자원을 할당할 수 있고(최대치까지), 교착상태를 방지할 수 있음. - 프로세스의 순서 <P1, P2, …, Pn>이 안정 순서란 의미는 모든 Pi가 요청하는 자원이 현재 사용 가능한 자원과 j > i인 모든 Pj가 점유하고 있는 자원들로 충족될 수 있음을 나타냄. - 프로세스 Pi가 필요한 자원을 즉시 사용할 수 없다면, Pi는 모든 Pj가 끝날 때까지 기다렸다가 자원을 확보, 필요한 모든 자원 확보 시 지정된 작업을 끝내고 자원을 반납함. - Pi가 종료하면 Pi+1은 필요한 자원을 확보할 수 있으므로 처리를 계속 진행할 수 있음. 불안정한 상태 - 안정한 상태처럼 프로세스의 자원 할당 및 해제의 순서가 명확히 존재하지 않는 경우. ※ 교착상태는 불안정상태이나, 모든 불안정상태가 교착상태인 것은 아님. [그림5-14] 안정상태, 불안정상태와 교착상태의 공간

2. 교착상태 해결 기법 시스템 상태 변화 시스템의 안정 상태 동일한 자원 12개와 프로세스 P0, P1, P2를 가진 시스템의 경우를 예를 들어 시스템 상태 변환을 설명함. 시스템의 안정 상태 프로세스 P0은 자원을 10개 요구, P1은 4개, P2는 9개 요구함. t0 시간에 프로세스 P0가 자원을 5개 점유, 프로세스 P1은 2개, 프로세스 P2는 2개를 점유할 경우 사용 가능한 자원은 3개임. [표5-1] 안정상태의 자원 예(1)

2. 교착상태 해결 기법 실행 과정 - t0 시간에 시스템은 안정상태이며, <P1, P0, P2> 순서는 안정 조건을 만족함. - 프로세스 P1은 사용 가능한 자원을 2개 할당 받아 실행한 후 반납 가능하므로 시스템의 여분 자원은 5개임. - P0은 사용 가능한 자원 5개를 할당 받아 실행한 후 반납 가능함. - 프로세스 P2가 필요한 자원을 할당받고 실행한 후 반납 가능함. [표5-2] 안정상태의 자원 예(2) 불안정상태 사용 가능한 자원 1개를 어느 프로세스에 할당해 도 프로세스를 만족시킬 수 없음. 프로세스 P0에 남은 장치를 할당하고 반납 전까지 다른 프로세스가 자원을 요구하지 않는 경우 교착 상태를 피할 수 있음. [표5-3] 불안정상태의 자원 예(1)

2. 교착상태 해결 기법 안정상태에서 불안정상태로의 변환 [표 5-1]에서 프로세스 P2가 자원을 1개 더 요구할 경우, 이를 허용 시 불안정상태로 변함. [표5-4] 불안정상태의 자원 예(2) 실행 과정 - 프로세스 P1은 사용 가능한 자원 2개를 할당 받아 실행한 후 장치를 반환. - 프로세스 P0는 자원 5개를 할당 받았지만 최대 10개가 필요하므로 5개를 더 요청하나, 최대 사용량만큼 자원을 할 당할 수 없으므로 대기. - 프로세스 P2는 추가로 자원을 6개 요청하므로, 시스템은 교착상태가 됨. 해결 방법 - 다른 프로세스들이 처리를 종료하고 자원을 반납할 때까지 프로세스 P2를 대기시키면 교착상태를 회피할 수 있음. ※ 시스템이 항상 안정상태에 머무르도록 안정상태 개념에서 교착상태 회피 알고리즘을 정의 가능. : 초기 시스템은 안정상태이므로, 프로세스가 현재 사용 가능한 자원을 요청 시 시스템은 자원 할당/대기 여부를 결정, 자원을 할당한 이후에도 시스템이 항상 안정상태일 경우에만 할당을 허용함.

2. 교착상태 해결 기법 교착상태 회피 예 : 은행가 알고리즘 다익스트라의 은행가 알고리즘(Banker’s Algorithm)을 이용. 각 프로세스가 요청하는 자원 종류의 최대수를 알아야 함. 각 프로세스에 자원을 어떻게 할당(자원 할당 순서 조정)할 것인가의 정보가 필요하며, 이를 이용하여 교착상태 회피 알고리즘을 정의함. 은행에서 모든 고객이 만족하도록 현금을 할당하는 과정과 동일함. 구현 방법 구현을 위해 여러 가지 자료구조를 유지해야 하며, 이는 자원 할당 시스템의 상태를 나타냄. n은 시스템의 프로세스 수, m을 자원 형태의 수라 가정할 때, 다음과 같은 자료구조가 필요함. - Available * 각 형태별로 사용 가능한 자원의 수를 표시하는 길이가 m인 벡터. - Max * 각 프로세스의 최대 자원의 요구를 표시하는 n ⅹ m 행렬. - Allocation * 현재 각 프로세스에 할당되어 있는 각 형태의 자원 수를 정의하는 n ⅹ m 행렬. - Need * 각 프로세스에 남아 있는 자원 요구를 표시하는 n ⅹ m 행렬.

2. 교착상태 해결 기법 구현을 위한 제약 간단한 구현을 위해 다음과 같은 제약을 둠. ① 시간이 진행하면서 벡터의 크기와 값이 변한다. ② x와 Y의 길이가 n인 벡터이다. ③ X[i] ≤ Y[i] 이고, i = 1, 2, …, n일 경우에만 X ≤ Y다. ④ X = (0, 3, 2, 1)이고 Y = (1, 7, 3, 2)이면 X ≤ Y다. ⑤ X ≤ Y 이고 X ≠ Y 이면 X < Y다. 행렬 Allocation과 Need에 있는 각 행을 벡터로 취급하며 이들을 각각 Allocationi와 Needi로 참조함. - Allocationi는 프로세스 Pi에 현재 할당된 자원. - Needi는 프로세스 Pi가 자신의 작업을 종료하는데 필요한 추가 자원.

2. 교착상태 해결 기법 은행가 알고리즘 Requesti를 프로세스 Pi를 위한 요청 벡터라 가정함. 만약 ‘Requesti[j] = k’라면, 프로세스 Pi는 자원 형태 Rj를 k개 요구함. 프로세스 Pi가 자원을 요청 시 다음 동작이 일어남. * 1단계 : Requesti ≤ Needi면 2단계로 가고, 그렇지 않으면 프로세스가 최대 요구치를 초과하기 때문에 오류 상태가 됨. * 2단계 : Requesti ≤ Available면 3단계로 가고, 그렇지 않으면 자원이 부족하기 대문에 Pi는 대기. * 3단계 : 시스템은 상태를 다음과 같이 수정하여 요청된 자원을 프로세스 Pi에 할당. - Available := Available – Requesti; - Allocationi := Allocationi + Requesti; - Needi := Needi – Requesti; 자원 할당 상태가 안정이라면 처리가 이루어지고 프로세스 Pi는 자원을 할당 받음. 불안정 상태이면 Pi는 Requesti를 대기하고 이전 자원 할당 상태로 복귀함.

2. 교착상태 해결 기법 안전 알고리즘 시스템이 안정상태인지, 불안정상태인지를 검사하며, 다음과 같은 과정으로 수행됨. * 1단계 : Work와 Finish를 각각 길이가 m과 n인 벡터라 가정할 때, 다음과 같이 초기화함. - Work := Available, Finish [i] := false, i=1, 2, …, n * 2단계 : 다음과 같은 조건을 만족하는 i값을 찾으며, i값이 없으면 4단계로 이동. - Finish[i] = false - Needi ≤ Work * 3단계 : 다음을 수행하고 2단계로 이동. - Work := Work + Allocation - Finish[i] := ture * 4단계 : 모든 i에 대하여 Finish[i] = true이면 시스템은 안정상태임. 안전 알고리즘의 예. - P0부터 P4까지 5개의 프로세스와 자원 형태 3개(A, B, C)를 가진 시스템에서, 자원 형태 A는 10개, 자원 형태 B는 5개, 자원 형태 C는 7개가 있다고 가정함. - 시간 t0에 시스템의 상태는 다음 [표 5-5]와 같다 가정함. [표5-5] 시간 t0일 경우 시스템의 상태

2. 교착상태 해결 기법 진행 과정. - 시스템은 현재 안정상태이며, <P1, P3, P4, P2, P0> 순서는 안정 조건에 해당함. - 현재 Available 자원은 (3, 3, 2)이며, 프로세스 P1에 할당 가능. - Needi ≤ Available 조건의 참, 거짓 여부는 (1, 1, 2) ≤ (3, 3, 2)이므로 참. - 프로세스 P1 실행 후 할당된 자원 해제 시 Available 자원은 (5, 3, 2). - P3 요구는 (0, 1, 1)이므로 할당이 가능하며, 동일한 과정으로 P4, P2, P0의 안정상태 조건은 만족됨. 프로세스 P1은 자원 형태 A의 자원 1개와 C의 자원 2개를 더 요청하여 Request1 = (1, 0, 2)라 가정함. - 요청의 허용 여부를 결정하기 위해 Request1 ≤ Available 여부((1, 0, 2) ≤ (3, 3, 2))를 확인해야 함. - 요청이 충족되어 새로운 상태에 도달했다 가정할 경우, - 새로운 시스템 상태가 안정한지 판별하기 위해 안전 알고리즘 실행, <P1, P3, P4, P2, P0> 순서가 안전요구 충족함을 확인함. - 프로세스 P1의 요청을 허락. - 프로세스 P4가 (3, 3, 0) 요청 시 자원이 부족하므로 허용할 수 없음. - P0이 (0, 2, 0)을 요청하면 Available 자원이 충분하여 할당하더라도 P0은 실행되지 않고 대기상태가 되어, 결과가 불안정상태이므로 자원 요청을 허용할 수 없음. [표5-6] 시간 t0일 경우 시스템의 새로운 상태

2. 교착상태 해결 기법 은행가 알고리즘의 단점 교착상태를 회피하기 위해 교착상태가 일어나지 않을 때만 작업을 진행. 다음과 같은 단점이 있어 항상 실용적이지 못함. - 할당할 수 있는 자원의 일정량을 요구함. * 자원은 수시로 유지보수가 필요하며 고장이나 예방보수를 함으로써 일정하게 남아있는 자원 수의 파악이 어려움. - 사용자 수가 일정해야 함. * 현재의 다중 프로그래밍 시스템에서는 사용자의 수가 항상 변함. - 교착상태 회피 알고리즘을 실행하면 시스템 과부하가 증가함. - 프로세스는 자원을 보유한 상태로 끝낼 수 없음. * 시스템에서는 이보다 더 강력한 보장이 필요함. - 사용자가 최대 필요량을 미리 알려주도록 요구하지만 자원 할당 방법이 점점 동적으로 변함에 따라 사용자의 최대 필요량을 파악하기 어려워 짐. * 최근의 시스템은 편리한 인터페이스 제공으로 사용자가 필요로 하는 자원을 알 필요가 없음. - 항상 불안정상태를 방지해야 하므로 자원 이용도가 낮음.

3. 교착상태 탐지 교착상태 탐지 알고리즘 쇼사니(Shoshani)와 포크만(Coffman)이 제안. 다음과 같은 자료구조들을 사용함. Available : 자원 형태마다 사용 가능한 자원 수를 표시하는 길이가 m인 벡터. Allocation : 각 프로세스에 현재 할당된 각 형태들의 자원 수를 표시하는 n ⅹ m 행렬. Request : 각 프로세스의 현재 요청을 표시하는 n ⅹ m 행렬. Request[i, j] : 프로세스 Pi가 필요한 자원 수가 k 개라면 프로세스 Pi는 자원 형태 Rj의 자원을 k개 더 요청함. 남아있는 프로세스들에 대한 할당 가능 순서를 모두 찾음. 1단계 : Work과 Finish는 각각 길이가 m과 n인 벡터로, ‘Work := Available’로 초기화 함. - (i = 1, 2, …, n)일 때 ‘Allocationi ≠ 0’이면 ‘Finish[i] := false’이고, 아니면 ‘Finish[i] := true’. 2단계 : 다음과 같은 조건을 만족하는 색인 i를 찾으며, 조건에 맞는 i가 없으면 4단계로 이동. - Finish[i] = false, Requesti ≤ Work 3단계 : 다음이 일치하는지 여부를 판단하여 2단계로 이동. - Work := Work + Allocationi - Finish[i] := true 4단계 : Finish[i] = false라면, 1 ≤ i ≤ n인 범위에서 시스템과 프로세스 Pi는 교착상태임.

3. 교착상태 탐지 교착상태 탐지 알고리즘 예 P0에서 P4까지의 프로세스 5개와 자원 형태 3개, A, B, C를 가진 시스템이 있다 가정함. 자원 형태 A는 자원을 7개, 자원 형태 B는 2개, C는 6개를 가지고 있음. t0 시간에 다음과 같은 자원 할당 상태가 된다 가정함. [표5-7] 시간 t0일 경우 시스템의 새로운 상태 현재 시스템은 교착상태가 아니며, <P0, P2, P3, P1, P4>는 모든 i에 대하여 ‘Finish[i] = ture’임.

3. 교착상태 탐지 교착상태 탐지 알고리즘 사용 횟수 [표5-8] 시간 t0일 경우 시스템의 새로운 상태 프로세스 P2가 자원 형태 C의 자원을 1개 더 요청한다 가정함. Request 행렬은 다음과 같이 수정됨. 현재 시스템은 교착상태임. 프로세스 P0이 점유하고 있는 자원을 요청하더라도 가용한 자원 수는 다른 프로세스들의 요청을 충족시킬 만큼 충분하지 않음. 따라서 프로세스 <P1, P2, P3, P4>로 구성된 교착상태가 존재함. 교착상태 탐지 알고리즘 사용 횟수 탐지 알고리즘 호출 문제는 교착상태 발생 빈도수와 교착상태 발생 시 영향을 받는 프로세스의 수에 따라 결정. 교착상태가 자주 발생하면 탐지 알고리즘도 자주 호출됨. 요청을 할 때마다 교착상태 탐지 알고리즘 호출 시 연산 시간 부담이 큼. 경제적인 방법은 호출 빈도를 줄이는 것으로, 한 시간마다 또는 CPU 이용률이 40%로 저하될 때마 다 호출.

4. 교착상태 회복 기법 프로세스 중지 교착상태 회복 기법 교착상태에서 회복한다는 것은 순환대기에서 탈피한다는 것을 의미함. 이를 위해 프로세스를 한 개 이상 중지시키는 방법과 교착상태의 프로세스들로부터 자원을 선점하는 방법이 있음. 프로세스 중지 두 가지 방법이 있으며, 모두 시스템이 정지된 프로세스에 할당된 모든 자원의 해제를 요구함. 교착상태 프로세스를 모두 중지. - 교착상태의 순환대기를 확실히 해결하지만 자원 사용과 시간 면에서 비용이 많이 듬. - 오랫동안 연산했을 가능성이 있는 프로세스의 부분 결과를 폐기하여 나중에 다시 연산해야 함. 한 프로세스씩 중지. - 한 프로세스가 중지될 때마다 교착상태 탐지 알고리즘을 호출하여 프로세스가 교착상태에 있는지 확인. - 교착상태 탐지 알고리즘 호출에 대한 부담이 큼.

4. 교착상태 회복 기법 부분 종료 방식을 사용하여 교착상태 회복 어느 프로세스를 중지시킬 지 결정해야 하며, 이는 프로세서 스케줄링과 유사한 정책 결정 문제임. 경제적인 문제로, 프로세스들을 중지시키는 데 최소비용으로 중지시키는 방법을 찾아야 함. 일반적으로 다음과 같은 기준으로 프로세스를 선정함. - 프로세스들의 우선순위 - 프로세스가 수행된 시간과 앞으로 종료하는 데 필요한 시간 - 프로세스가 사용한 자원 형태와 수(ex: 자원을 선점할 수 있는지의 여부) - 프로세스 종료를 위해 필요한 자원 수 - 프로세스를 종료하는 데 필요한 프로세스의 수 - 프로세스가 대화식인지 일괄식인지 여부

4. 교착상태 회복 기법 자원 선점 프로세스의 자원을 선점하여 교착상태가 해결될 때까지 선점한 자원을 다른 프로 세스에 할당하여 이용. 다음 세 가지 사항을 해결해야 함. 선점 자원 선택. - 프로세스를 종료할 때, 비용을 최소화하기 위해 적절한 선점 순서를 결정해야 함. - 비용 요인은 교착상태 프로세스가 점유하고 있는 자원 수, 교착상태 프로세스가 지금까지 실행하는 데 소용한 시간과 같은 매개변수가 포함됨. 복귀. - 필요한 자원을 읽은 프로세스는 정상적으로 실행할 수 없으므로, 프로세스를 안정상태로 복귀시키고 다시 시작해야 함. - 단순한 방법은 완전히 복귀시키고(프로세스를 중지) 재시작하는 것이며, 프로세스를 교착상태에서 벗어날 정도로만 복귀시킬 수 있다면 더 효과적임. - 시스템이 실행하는 모든 프로세스의 상태 정보를 유지해야 하는 부담이 존재함. 기아. - 동일한 프로세스가 자원들을 항상 선점하지 않도록 보장할 때, 비용에 근거한 시스템은 동일한 프로세스가 희생자로 선택되기 쉬움. - 이는 프로세스가 자신의 작업을 완료하지 못하는 기아상태가 되어 시스템 조치를 요구함. - 프로세스가 짧은 시간 동안만 희생자로 지정됨을 보장해야 함. - 일반적인 해결 방법은 비용 요소에 복귀 횟수를 포함시키는 것.

5. 기아상태 기아상태(Starvation) 프로세스가 자신의 작업을 완료하지 못하는 상태. 교착상태를 예방하기 위해 자원을 할당할 때 발생(기다림)되는 결과. 다익스트라가 제안한 ‘식사하는 철학자 문제’ 문제의 실질적인 중요성 때문이 아닌 대부분의 병행 문제인 교착상태와 기아상태의 예기 때문에 고전적인 동기 문제로 취급됨. 문제 설명. - 철학자 5명은 대부분의 시간을 생각하고 먹는데 소비하며, 철학자들은 의자 5개로 둘러 쌓인 원형 테이블을 공유함. - 테이블 중앙에 음식이 있으며 포크가 5개 놓여있음. - 지역 풍습에 따라 철학자들은 포크 2개로 식사하며, 5명의 철학자가 동시에 식사할 수 없고, 2명만 동시에 식사 가능. - 철학자가 생각 중일 때는 다른 철학자가 간섭하지 않음. - 배고픈 철학자가 식사를 위해 왼쪽과 오른쪽의 포크 2개를 든 다 가정할 때, - 철학자는 한 번에 포크 하나만 들 수 있으며, 왼쪽 포크를 먼저 집은 후 오른쪽 포크를 집음. - 이웃 철학자가 이미 들고 있는 포크는 집을 수 없음. - 배고픈 철학자는 두 포크를 동시에 갖게 되면 식사를 시작함. - 식사를 마치면 포크 2개를 내려놓고 계속 생각함. - 모든 철학자가 동시에 식사를 한다면 교착상태에 빠짐. [그림5-15] 철학자들의 식사

var chopstick : array [0…4] of semaphore (:=1); 5. 기아상태 포크를 세마포어로 표시하여 교착상태 해결. 철학자는 포크에 해당하는 세마포어에 대한 P 연산을 수행하고 나서 포크를 집음. 포크는 해당 세마포어에 대한 V 연산을 수해함으로써 내려 놓음. 공유 데이터는 다음과 같음. - chopstick의 모든 요소는 1로 초기화되며, 철학자 i의 구조는 다음과 같이 서술 가능함. var chopstick : array [0…4] of semaphore (:=1); 알고리즘 5-1 철학자 i의 구조 01 repeat 02 P(chopstick[i]); 03 P(chopstick[i+1 mod 5]; 04 ... 05 식사한다. 06 ... 07 V(chopstick[i]); 08 V(chopstick[i+1 mod 5]); 09 ... 10 생각한다. 11 ... 12 until false; ※ 이 해결 방법은 두 이웃 철학자가 동시에 식사할 수 없으나, 교착상태가 발생함.

5. 기아상태 교착 상태 발생 해결 방안 철학자 4명만 테이블에 동시에 앉도록 함. 철학자가 양쪽 포크 모드를 사용 가능할 때 포크를 집을 수 있도록 허용(임계영역 내에서)함. 비대칭 해결법을 사용하여, 홀수 번째 철학자는 왼쪽 포크를 집은 후에 오른쪽 포크를, 짝수 번째 철학자는 오른쪽 포크 다음에 왼쪽 포크를 집도록 함. 알고리즘 5-2 식사하는 철학자 문제의 해결방안 01 var chopstick : array[0...4] of semaphore (:=1); 02 room : semaphore (:=4) 03 repeat 04 P(room); 05 P(chopstick[i]); 06 P(chopstick[i+1 mod 5]; 07 ... 08 식사한다. 09 ... 10 V(room); 11 V(chopstick[i]); 12 V(chopstick[i+1 mod 5]); 13 ... 14 생각한다. 15 ... 16 until false;

5. 기아상태 ‘식사하는 철학자 문제’는 철학자 중 한명이라도 굶어 죽는 일이 없어야 함. 교착상태에 대한 해결책은 기아상태의 가능성을 제거할 수 없음. 해결을 위해 먼저 기다리는 작업을 발견하고 각 작업이 기다린 시간을 조사, 추적해야 함. 시스템은 기아상태를 발견하면 즉시 새로운 작업의 시작을 보류하도록 조치해야 함. 빈번한 시스템 보류로 처리량이 감소할 수 있으므로 신중한 접근이 요구됨.