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

2. 교착상태 해결 기법 교착상태 회피 예 : 은행가 알고리즘 다익스트라의 은행가 알고리즘(Banker’s Algorithm)을 이용. 교착상태가 발생하지 않도록 안정상태를 유지하도록 자원을 할당하는 알고리즘. - 시스템이 불안정 상태일 경우 반드시 교착상태는 아니지만, 교착상태에 빠질 확률이 높고 해결하기 어 려움. - 따라서 가급적 자원을 할당할 때, 시스템이 안정상태를 유지하도록 시스템을 운용하는 기법. 각 프로세스에 자원을 어떻게 할당(자원 할당 순서 조정)할 것인가의 정보가 필요. 각 프로세스가 요청하는 자원 종류의 최대수를 알아야 하며, 이를 이용하여 교착상태 회피 알고리즘을 정의함. 은행에서 모든 고객이 만족하도록 현금을 할당하는 과정과 동일함.

2. 교착상태 해결 기법 구현 방법 구현을 위해 여러 가지 자료구조를 유지해야 하며, 이는 자원 할당 시스템의 상태를 나타냄 . n은 시스템의 프로세스 수, m을 자원 형태의 수라 가정할 때, 다음과 같은 자료구조가 필요 함. - Available * 각 형태별로 사용 가능한 자원의 수를 표시하는 길이가 m인 벡터. * Available[j] = k : 자원을 k개 사용할 수 있다는 의미. - Max * 각 프로세스의 최대 자원의 요구를 표시하는 n ⅹ m 행렬. * Max[i,j] = k : 프로세스 Pi는 자원 형태가 Rj인 자원을 최대 k개까지 요구할 수 있다는 의미. - Allocation * 현재 각 프로세스에 할당되어 있는 각 형태의 자원 수를 정의하는 n ⅹ m 행렬. * Allocation[i,j] = k : 프로세스 Pi는 자원 형태가 Rj인 자원을 최대 k개 할당받고 있다는 의미. - Need * 각 프로세스에 남아 있는 자원 요구를 표시하는 n ⅹ m 행렬. * Need[i,j] = k : 프로세스 Pi는 자신의 작업을 종료하기 위해 자원 형태 Rj를 k개 더 요구한다는 의미 . * Need[i,j] = Max[i,j] – Allocation[i,j]

2. 교착상태 해결 기법 행렬 Allocation과 Need에 있는 각 행을 벡터로 취급하며 이들을 각각 Allocationi와 Needi로 참조함. - Allocationi는 프로세스 Pi에 현재 할당된 자원. - Needi는 프로세스 Pi가 자신의 작업을 종료하는데 필요한 추가 자원. 은행가 알고리즘 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이면 시스템은 안정상태임. [표5-5] 시간 t0일 경우 시스템의 상태

2. 교착상태 해결 기법 진행 과정. 안전 알고리즘의 예. - P0부터 P4까지 5개의 프로세스와 자원 형태 3개(A, B, C)를 가진 시스템에서, 자원 형태 A는 10개, 자 원 형태 B는 5개, 자원 형태 C는 7개가 있다고 가정함. - 시간 t0에 시스템의 상태는 다음 [표 5-5]와 같다 가정함. 진행 과정. - 시스템은 현재 안정상태이며, <P1, P3, P4, P2, P0> 순서는 안정 조건에 해당함. - 현재 Available 자원은 (3, 3, 2)이며, 프로세스 P0에 할당 불가능, 프로세스 P1에 할당 가능. - Needi ≤ Available 조건의 참, 거짓 여부는 (1, 2, 2) ≤ (3, 3, 2)이므로 참. - 프로세스 P1 실행 후 할당된 자원 해제 시 Available 자원은 (5, 3, 2). - P3 요구는 (0, 1, 1)이므로 할당이 가능하며, 동일한 과정으로 P4, P2, P0의 안정상태 조건은 만족됨. [표5-5] 시간 t0일 경우 시스템의 상태

2. 교착상태 해결 기법 프로세스 P1은 자원 형태 A의 자원 1개와 C의 자원 2개를 더 요청하여 Request1 = (1, 0, 2)라 가정함. - 요청의 허용 여부를 결정하기 위해 Request1 ≤ Need1 여부((1, 0, 2) ≤ (1, 2, 2))를 확인해야 함. Request1 ≤ Available 여부((1, 0, 2) ≤ (3, 3, 2))를 확인해야 함. - 시스템 상태를 수정하고 요청이 충족되어 새로운 상태에 도달했다고 가정. - 새로운 시스템 상태가 안정한지 판별하기 위해 안전 알고리즘 실행, <P1, P3, P4, P2, P0> 순서가 안전요 구 충족함을 확인함. - 프로세스 P4가 (3, 3, 0) 요청 시 자원이 부족하므로 허용할 수 없음. - P0이 (0, 2, 0)을 요청하면 Available 자원이 충분하여 할당하더라도 P0은 실행되지 않고 대기상태가 되 어, 결과가 불안정상태이므로 자원 요청을 허용할 수 없음. Available := Available – Requesti; Allocationi := Allocationi + Requesti; Needi := Needi – Requesti; [표5-5] 시간 t0일 경우 시스템의 상태 - 102 + 102 [표5-6] 시간 t0일 경우 시스템의 새로운 상태 8

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

3. 교착상태 탐지 교착상태 탐지 알고리즘 쇼사니(Shoshani)와 포크만(Coffman)이 제안. 단점 : 자주 사용시 시스템의 성능 감소. 장점 : 교착상태에 빠진 프로세스를 빨리 발견하여 자원의 유휴상태를 방지. 시스템에서는 교착상태 방지를 위해서 다음과 같은 알고리즘을 지원해야 함. 교착상태가 발생했는지를 파악하기 위해 시스템 상태를 검사하는 알고리즘 교착상태로부터 회복하는 알고리즘

3. 교착상태 탐지 다음과 같은 자료구조들을 사용함. 남아있는 프로세스들에 대한 할당 가능 순서를 모두 찾음. 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는 교착상태임. 11

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

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

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

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

SUMMARY 교착상태 교착상태의 필요충분조건 대기 중인 프로세스 중 한 프로세스에 의해서만 발생할 수 있는 사건을 둘 이상의 프로세스가 무한히 대기할 때 발생함. 근본적인 해결 방법은 세 가지. 시스템이 절대 교착상태가 되지 않음을 보장하는 방법(예방). 교착상태를 회피하는 방법. 시스템이 교착상태가 되는 것을 허용하고 다시 회복시키는 방법. 교착상태의 필요충분조건 교착상태는 파일 요청, 전용장치 할당, 다중 주변장치 할당, 스풀링 시스템, 디스크 공유, 네트워크 시스템 등에서 발생함. 교착상태 발생의 네 가지 필요 조건(상호배제, 점유 및 대기, 비선점, 순환대기)이 시스템 내에서 동시에 충족되어야 함.

SUMMARY 교착상태를 예방하는 세 가지 기본 방법 교착상태 회피 필요충분조건 중 최소 하나만이라도 발생하지 않도록 함. 점유 및 대기 : 프로세스의 실행에 앞서 필요한 자원을 모두 확보. 비선점 : 프로세스가 일부 자원을 점유하고 있으면서 다른 자원 요청 시, 즉시 할당할 수 없으면 프로세스가 현재 점유하고 있는 모든 자원을 해제한 후 대기. 순환대기 : 모든 자원 형태에 선형으로 순서를 부여하며, 각 프로세스는 오름차순으로만 자원을 요청할 수 있음. 교착상태 회피 교착상태 예방 알고리즘보다 덜 엄격하며, 각 프로세스가 자원을 이용하는 방법에 대한 정보를 가짐. 교착상태를 안정상태와 불안정상태로 구분하여 회피할 수 있음. 교착상태 발생 여부 확인을 위해 교착상태 탐지 알고리즘을 호출함. 교착상태 탐지 시 시스템은 교착상태의 프로세스를 중지시키거나, 교착상태의 프로세스로부터 자원을 선점하여 회복하며, 희생자를 최소한 하나 선택해야 함.

SUMMARY 은행가 알고리즘(Banker’s Algorithm) 교착상태 회복 기법 기아상태 교착상태를 회피하기 위한 방법으로 다익스트라가 제안함. 각 프로세스에 자원을 어떻게 할당할 것인가라는 정보가 필요하므로, 각 프로세스가 요청하는 자원 종류의 최대수를 알아야 함. 교착상태 회복 기법 교착상태에서 회복을 위해 순환대기를 탈피하는 방법으로, 프로세스를 한 개 이상 중지 시키거나 교착상태에 있는 프로세스들의 자원을 선점하는 방법이 있음. 기아상태 작업이 결코 사용할 수 없고 계속 기다려야 하는 자원을 할당할 때 발생되는 결과.