Ch. 8 교착상태 (Deadlocks) 29-Nov-18

8.1 시스템 모델 교착상태 예제 Traffic jam 징검다리 건너기 Loop PA PB step – 자원 할당 leave – 자원 회수 동일한 징검다리 밟을 때 - deadlock 되돌아오기 - rollback Loop Allocate Request R1 PA PB R2 Request Allocate

8.1 시스템 모델 자원 사용 순서 무기한 연기(Indefinite postponement) 요청 사용 해제 요청이 즉시 허용되지 않으면 요청 프로세스는 자원을 얻을 때까지 대기해야 한다. 사용 프로세스는 자원에 대해 작업을 수행할 수 있다. 해제 프로세스가 자원을 해제한다. 무기한 연기(Indefinite postponement) 무기한 연기를 실행하는 프로세스 스케줄링의 경우 이유 : 자원 스케줄링 정책 Aging 우선순위가 낮은 프로세스의 무한 블로킹 문제 시스템에서 오랫동안 기다린 프로세스의 우선순위를 점진적으로 높여줌

8.2 교착상태 특징 필요 조건들 상호 배제(mutual exclusion) 점유대기(hold and wait) 교착상태는 한 시스템에 다음의 네가지 조건이 동시에 성립할 때 발생할 수 있다. 상호 배제(mutual exclusion) 최소한 하나의 자원이 독점적으로 점유한다. 점유대기(hold and wait) 최소한 하나의 자원을 점유한 채, 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 대기하고 있는 프로세스가 반드시 있어야 한다. 비선점(nopreemption) 자원들을 선점할 수 없어야 한다. 순환 대기(circular wait) R2 P2 R3 P3 R3 P3 P1 R1 Pn Rn Pn-1

8.2 교착상태 특징 Ex) 징검다리를 건널 때 상호 배제(Mutual exclusion ) 점유/대기(Hold/Wait) 한사람만이 징검다리 하나를 밟을 수 있다. 점유/대기(Hold/Wait) 한사람이 징검다리를 밟고 다른 징검다리를 요청한다. 비선점(No-preemption) 한사람이 다른 사람의 징검다리를 뺏을 수 없다. 순환 대기(Circular wait ) 한사람이 다른 사람의 징검다리를 얻기 위하여 기다린다.

8.2 교착상태 특징 자원 할당 그래프   P1 P2 P3 P1 P2 P3 그림 8.1 자원 할당 그래프 R1 R2 R3 R4  P1 P2 P3 R1 R2 R3 R4 그림 8.1 자원 할당 그래프 그림 8.2 교착상태를 갖는 자원할당그래프

그림 8.3 사이클이 있으면서 교착상태가 아닌 자원할당그래프 8.2 교착상태 특징 자원 할당 그래프 P2 R1  P3 P1 R2  P4 그림 8.3 사이클이 있으면서 교착상태가 아닌 자원할당그래프

8.3 교착상태 처리 방법 교착상태 처리 방법 Detailed algorithms 교착상태가 되도록 허용한 다음 회복 시스템이 교착상태가 되지 않도록 보장하는 프로토콜을 사용 교착상태가 되도록 허용한 다음 회복 교착상태를 무시 Detailed algorithms 교착상태 예방(Prevention) 필요 조건들 중 하나가 성립하지 않도록 보장 교착상태 회피(Avoidance) 프로세스가 요청/사용할 자원의 정보를 미리 제공할 것을 요구 교착상태 검출(Detection) 회복(Recovery)

8.4 교착상태 예방 상호 배제(Mutual Exclusion) 점유/대기(Hold & Wait) 프로세스 Pi가 필요한 자원을 한꺼번에 모두 할당하거나 불가능하면 전혀 할당하지 않음 단점 자원 활용률이 낮음 starvation  무기한 연기

8.4 교착상태 예방 비선점(No Preemption) 순환 대기(circular Wait) request additional resources if it is rejected these resources are released implicitly  request all resources after 단점 오버헤드 (abort all jobs untile now as resources are released) 순환 대기(circular Wait) 자원들에게 전체 순서를 부여 열거된 순서대로 자원을 요청하도록 요구 낮은 자원이용률 ( As Pi need only a resource of high number )

Safe, unsafe, and deadlock state spaces. 8.5 교착상태 회피 각 프로세스는 자신이 필요한 자원의 최대 수를 선언하도록 요구 Safe State Maximum Needs Current Needs P0 10 5 P1 4 2 P2 9 2 deadlock unsafe safe Safe, unsafe, and deadlock state spaces.

8.5 교착상태 회피 은행가 알고리즘(Banker’s Algorithm) 자원할당그래프 알고리즘 maintain sharing the same resources with users fairly 자원할당그래프 알고리즘 R1 R1 P1 P2 P1 P2 예약간선 R2 R2 교착상태 회피를 위한 자원할당 그래프 불안전 상태의 자원할당 그래프

8.6 교착상태 검출 정기적으로 검사 복구 Detect with Resource Allocation Graph R1 R3 R1 정기적으로 검사 복구 Detect with Resource Allocation Graph R1 R3 R1 R3 P1 P2 P3 P1 P2 P3 R4 R4 R2 R2 교착상태를 가진 자원할당 그래프 자원 할당 그래프

Resource-allocation graph with a cycle but no deadlock 8.6 교착상태 검출 P2 R1 P3 P1 R2 P4 Resource-allocation graph with a cycle but no deadlock

8.6 교착상태 검출 R1 P1 P2 R2 교착상태 회피를 위한 자원할당 그래프 R1 P1 P2 R2 불안정 상태의 자원할당 그래프

(a) 자원할당 그래프 (b) 대기 그래프(wait-for graph) 8.6 교착상태 검출 P5 P5 R1 R3 R4 P1 P2 P3 P1 P2 P3 R2 P4 R5 P4 (a) 자원할당 그래프 (b) 대기 그래프(wait-for graph)

8.7 교착상태로부터의 회복 프로세스 종료 : 강제로 프로세스를 종료시킴  자원 회수 교착상태 프로세스를 모두 중지 교착상태가 제거될 때까지 한 프로세스씩 중지 자원 선점 : victim processes 선택  Take resource by force 문제점 희생자의 선택 Process’s precedence Process’s processing time requirement Process’s resource requirement Rollback time  Total Rollback Time Starvation : 일부 프로세스의 계속적인 희생자 선택 가능성이 있음.