제 7 장 교착 상태 (Deadlocks) 7.1 시스템 모델 (System Model) 자원 요청->할당 불가->대기(wait) 상태: 교착 상태 가능 7.1 시스템 모델 (System Model) 한정된 자원 물리적: CPU, 기억장치, I/O 장치 논리적: 파일, 세마포, 모니터 여러 형태 자원을 사용 전 요청하고 사용 후 해제 시스템 호출(open, close, alloc, free, ...) 요청 수락 불가(최대 허용 수 초과) ->해당 자원의 ‘큐’에 추가

7.2 교착 상태의 특징 (Deadlock Characterization) 7.2.1 필요한 조건들 (Necessary Conditions) 동시 만족될 조건들  상호 배제 (mutual exclusion) 점유와 대기 (hold and wait) 비선점 (no preemption) 순환 대기 (circular wait) *hold-and-wait를 암시

7.2.2 자원 할당 그래프 (Resource-Allocation Graph) 정점 V = {P, R} (프로세스 혹은 자원의 집합) 자원 할당 그래프 (resource-allocation graph) 요청선(request edge) Pi Rj P가 R 형태의 자원 하나를 요청하고 대기 중 할당선(assignment edge) Rj Pi Rj 형태의 자원 하나가 Pi에 할당되어 있음 자원을 요청하면 요청선이 삽입되고 만족되면 즉시 할당선으로 변환 (해제하면 삭제) 사이클(cycle)이 존재하고 각 자원 형태가 한 개의 자원만을 가지면 => “교착 상태” (그림 7.2 7.3)

7.3 교착 상태 처리 방법 (Methods for Handling Deadlocks) 발생 안하게 : 교착 상태가 생기지 않는 프로토콜 사용 예방(prevention) 교착 상태 발생 4 조건 중 하나가 만족되지 않게 회피(avoidence) 각 P의 자원 요구에 대한 사전 정보를 이용 현재는 물론 미래에 교착상태가 발생하지 않도록 자원 할당 발생 후 회복 : 발생 허용 -> 탐지 -> 회복 방치 : 많은 OS가 채택 비용 절감, 교착 상태는 매우 간혹 발생한다 발생하면 => 시스템 정지

7.4 교착 상태 예방 (Deadlock Prevention) 7.4.1 상호 배제 4 조건 중 하나를 예방, 장치 이용율 및 시스템 성능 저하 7.4.1 상호 배제 예방 힘듬 : 파일(공유 가능) <-> 프린터(공유 불가) 7.4.2 점유와 대기 보유 자원이 없을 때만 자원 요청이 가능하게 예) 1.테이프 - 2.디스크 파일 - 정렬(sort) - 3.프린터 두 자원(1, 2) 요청 -> 모두 해제 -> 다시 두 자원(2, 3) 요청 문제점 : 낮은 자원 이용률, 기아 가능

7.4.3 비선점 (No Preemption) 7.4.4 순환 대기 (Circular Wait) 각 자원 형태에 순서 부여 (복구 가능한-CPU/메모리 등)자원을 빼앗을 수 있게 방법 1: 다른 자원 요청 시 즉시 할당 안되면 무조건 사용중인 자원을 모두 뺏앗김. 나중에, 모든 자원(새 자원 포함)을 동시 할당받을 수 있을 때까지 대기 방법 2: 다른 자원 요청 시 즉시 할당 안되면 그 자원을 사용 중인 다른 P의 상태를 검사. 대기 중이면 뺏고 아니면 자신이 대기 7.4.4 순환 대기 (Circular Wait) 각 자원 형태에 순서 부여 1. 자원을 오름차순으로 요청 혹은, 2. Rj의 한 자원을 요청하려면 F(Ri)  F(Rj)인 Ri 형태의 자원을 모두 해제해야 한다

7.5 교착 상태 회피 (Deadlock Avoidence) 앞의 예방 기법은 처리율 감소가 너무 심함 미래의 자원 사용을 파악(예측) : 예) 최대 사용 수 순환 조건이 만족되지 않게 하는 알고리즘 사용 7.5.1 안정 상태(Safe State) 안정 상태: <P1, P2, … Pn>의 모든 Pi에 대해 Pi가 요청하는 자원들이 ‘현재의 가용 자원’ + ‘j < i인 Pj가 점유하고 있는 자원’으로 만족될 수 있는 상태 (그림 7.4) 안정 순서 최대 수요 현재 수요 P0 10 5 안정 순서: <P1, P0, P2> P1 4 2 P2 9 2 3이 되면 불안정 상태 자기 테잎 수 = 총 12 개

7.5.2 자원 할당 그래프 알고리즘 각 자원 형태마다 자원이 한 개라고 가정 요청 가능(claim) 선(점선)을 추가 실제 요청 시 ‘요청 가능선-> 요청선’ (해제 시 반대 현상) 요청선을 할당선으로 바꿀 때, 다른 프로세스의 요청 가능선을 포함하여 사이클이 생기면 할당 가능해도 요청 거절 => 불안정 상태를 발견하는 한 방법 (그림 7.5, 7.6)

7.5.3 은행가 알고리즘 (Banker’s Algorithm) 각 자원 형태 당 여러 개 자원, 덜 효과적 자원 요구 시 안정 상태 유지 여부 따라 할당 n: 프로세스의 수, m: 자원 형태의 수 Available: 자원 형태별 자원 수 (m) Max: 각 P의 최대 자원 요구 (n  m) Allocation: 현재 각 P에 할당된 자원 수 (n  m) Need: 각 P의 추가 자원 요구 (n  m) Need[i, j] = Max[i, j] - Allocation[i, j]

안정 알고리즘(safe algorithm)  Work := Available, Finish[i] := false Finish[i] = false이고 Needi  Work인 i를 찾는다 발견 없음 Finish[i] := true Work := Work + Allocationi 안정상태 모든 Finish[i] := true ? 예 알고리즘 복잡도 = O(m  n2)

자원 요청 알고리즘(Resource Request Algorithm)  Requesti  Needi ? 오류 아니오 Requesti  Availablei ? 대기 아니오 Available := Available - Requesti; Allocationi := Allocationi + Requesti; Needi := Needi - Requesti; 성공 안정 상태 ? 취소 네 아니오

불안정상태 안정상태 Allocation Max Available A B C A B C A B C (10개) (5개) (7개) P0 0 1 0 7 5 3 3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3 Need A B C 7 4 3 1 2 2 6 0 0 0 1 1 4 3 1 불안정상태 Request0 = (0, 2, 0) 취소 Allocation Available Need A B C A B C A B C P0 0 1 0 2 3 0 7 4 3 P1 3 0 2 0 2 0 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 <P1, P3, P4, P2, P0> Request1 = (1, 0, 2) 안정상태

Allocationi  0이면 Finish[i] := false 아니면 true 교착상태 탐지 알고리즘 (자원 형태마다 여러 개의 자원이 있는 경우) Work := Available Allocationi  0이면 Finish[i] := false 아니면 true Finish[i] = false이고 Requesti  Work인 i를 찾는다 발견 없음 Finish[i] := true Work := Work + Allocationi false인 Pi끼리 교착상태 모든 Finish[i] := true ? 현재로선 교착상태 없음 아니오 알고리즘 복잡도 = O(m  n2)

교착상태 Allocation Request Available A B C A B C A B C (7개) (2개) (6개) P0 0 1 0 0 0 0 0 0 0 P1 2 0 0 2 0 2 P2 3 0 3 0 0 0 P3 2 1 1 1 0 0 P4 0 0 2 0 0 2 Request A B C 0 0 2 2 0 2 0 0 1 1 0 0 <P0, P2, P3, P1, P4> <P0, P1, P2, P3, P4> 교착상태아님 교착상태

7.6.3 탐지 알고리즘 사용 (Detection Algorithm Usage) 교착 상태의 빈도수나 관련된 P의 수와 비례하여 사용 예) 요청이 즉시 만족 안될 때마다 /1시간 마다/CPU 이용률이 40%이하일 때마다 교착 상태의 원인이 되는 P를 파악하기는 힘들다 7.7 교착 상태로부터의 회복 7.7.1 프로세스 중지 (Termination) 모두 중지시키거나, 해결될 때까지 차례로 중지시킴 간단치 않음 (파일 갱신중, …) 우선순위, 수행 시간/남은 시간, 사용 중인 자원/추가 자원, 대화식 여부 등을 고려하여 중지할 P 선정

7.7.2 자원 선점 (Resource Preemption) 7.8 교착 상태 해결을 위한 복합 방식 희생자 선택, 복귀(rollback), 기아 상태 등을 고려 7.8 교착 상태 해결을 위한 복합 방식 자원들을 계층적으로 부류(class)화하여 class 단위로 ‘자원 순서 기법’을 적용 내부자원(PCB…) - CPU - 작업 자원(장치…) - swap 공간 각 class 내에서는 예방-회피-탐지 중 한 가지 선택 예: CPU는 선점 가능 => ‘예방’ 가능