제6장 교착상태 OS 컴퓨터 운영체제 Operating Systems Copyright(c) 1999, Distributed Systems Lab., SungKyunKwan University, All rights reserved. No part of these slides may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, without the prior written permission of Distributed Systems Lab., SungKyunKwan University.

개요 대기 상태(blocked/asleep state)의 의미 교착상태(deadlock state)의 의미 프로세스가 특정 사건의 발생을 기다리는 상태 프로세스가 원하는 자원의 할당을 기다리는 상태 교착상태(deadlock state)의 의미 프로세스가 전혀 발생할 가능성이 없는 사건을 기다리는 경우 정의 : 교착상태 프로세스가 전혀 발생할 가능성이 없는 사건을 기다리는 경우 그 프로세스는 교착상태에 놓여 있다고 함 교착상태에 놓인 프로세스가 하나 이상 있는 경우 그 시스템은 교착상태에 있다고 함 교착상태와 무기한 연기 상태 구분 필요

교착상태를 포함한 프로세스 상태 전이도 terminated running dispatch (schedule) sleep (block) timerrunout (preemption) ready asleep deadlocked wakeup created transition impossible

자원의 분류 일반적인 자원의 분류 그외의 자원 분류 방법 하드웨어 자원/소프트웨어 자원 선점가능성에 의한 분류 할당 방식에 따른 분류 할당 형태에 따른 분류 자원의 속성에 따른 분류

자원의 분류 선점가능성에 의한 분류 선점가능 자원 (preemptible resources) 선점된 후 복귀시 아무런 문제점이 발생하지 않는 자원 프로세서(processor), 메모리(memory) 등 선점불가능 자원 (nonpreemptible resources) 자원을 선점하였을 때 이를 선점 당한 프로세스에게 어떤 형태로든 영향을 미치게 되는 경우 자기테이프 장치(tape drive) 등

할당 방식에 따른 분류 전체 할당식(total allocation) 자원 프로세스에 할당될 때 항상 자원 전체를 할당하게 되는 경우 프로세서, 자기테이프 장치 등 분할 할당식(partitioned allocation) 자원 하나의 자원을 여러 조각들로 분할하고 이렇게 분할된 조각 단위로 프로세스에게 할당할 수 있는 자원 메모리 등

할당 형태에 따른 분류 배타적 할당(exclusive allocation) 자원 여러 프로세스가 동시에 같이 사용할 수 없는 자원 프로세서, 메모리, 자기테이프 장치, 버퍼, 터미널 등 공유식 할당(sharable allocation) 자원 여러 프로세스가 동시에 같이 할당받아 사용할 수 있는 자원 대부분 공유 소프트웨어나 데이터 자원 프로그램(시스템/유틸리티 프로그램 등), 공유 데이터 등

자원의 속성에 따른 분류 순차적 재사용(SR : Serially Reusable Resources) 자원 없어지지 않고 영구적으로 존재하는 자원 프로세서, 메모리, 버퍼, 테이프 장치, 프로그램 등 소비성(CR : Consumable Resources) 자원 한 프로세스가 사용한 후 그 자원이 사라지는 형태의 자원 시그널(signal), 메시지(message) 등

교착상태 모델에서 대상이 되는 자원의 일반적인 형태 - 선점불가능 자원(nonpreemptible resources) - 배타적 할당 자원(exclusive resources) - 순차적 재사용 자원(serially reusable resources) 소비성 자원(consumable resources)을 대상으로 하는 교착상태 모델도 있음

교착상태의 예 교착상태의 발생과정의 예 2개의 프로세스 (P1, P2) 2개의 자원 (R1, R2) 간단한 교착상태 발생 과정 시간 프로세스 P2 ... request R2 request R1 release R1 release R2 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 ... request R1 request R2 release R1 release R2  Ⓐ  Ⓑ  Ⓒ  Ⓓ  Ⓦ  Ⓧ  Ⓨ  Ⓩ

P1 R1 R2 P2 그래프 모형 노드(node) 프로세스 노드(Pi), 자원 노드(Rj) 에지(edge) Rj  Pi : 해당 자원이 프로세스에게 할당됨 Pi  Rj : 프로세스가 해당 자원을 요청, 대기중 간단한 교착상태가 발생한 상황의 그래프 모형 P1 R1 R2 P2

시스템 상태 전이 모델 가정 상태 시스템에 2 개의 프로세스와 2 개의 단위 자원만이 존재함 프로세스는 한번에 하나의 단위 자원만을 요청/반납 가능함 상태 상태 할당 받은 단위 자원의 수 요청 여부 x 1 o 2 1 x 3 1 o 4 2 x Note 자원형(resource type) 단위 자원(resource unit)

시스템 상태전이도 (2 X 2 시스템) S41 P2 holds 0, needs 0 P2 holds 0, needs 1 P2

교착상태 발생원인 교착상태 발생 원인 4가지 필요조건(necessary conditions) 다음 4가지 조건이 모두 만족되는 경우에 교착상태 발생됨 자원에 대한 배타적 사용 (exclusive use) 선점불가능 자원(nonpreemptible resources)의 존재 프로세스에 대한 자원의 부분 할당 (partial allocation) 환형대기 상태(circular wait condition)의 발생

교착상태 해결기법 교착상태 해결 기법 교착상태 예방(prevention) 기법 교착상태 회피(avoidance) 기법 교착상태 검출(detection) 및 교착상태 복구(recovery) 기법

교착상태 예방 기법 교착상태 예방 기법 교착상태 발생의 4가지 필요조건들 중 한가지 조건을 제거 시스템 내에서 교착상태가 절대로 발생하지 않도록 함 대부분의 경우 자원의 심각한 낭비 초래함 비현실적임

교착상태 예방 기법 교착상태 발생의 필요조건 4가지에 대한 제거 방법 자원에 대한 배타적 사용 조건 배제  자원의 공유 자원에 대한 선점 기능 지원 자원의 전체 할당(total allocation) 기법 환형 대기상태의 배제

교착상태 예방 기법 자원에 대한 배타적 사용 조건 배제 자원에 대한 선점 기능 지원 시스템 내의 모든 자원들을 공유 가능하게 하는 방법 불가능함 자원에 대한 선점 기능 지원 유사한 방법 프로세스가 일부 자원을 할당받고, 가용하지 않는 자원을 추가로 요청할 경우 기존에 할당받은 모든 자원들을 반납하고 모든 작업을 취소함 자원의 낭비가 매우 심함 비실현적임

교착상태 예방 기법 자원의 전체 할당(total allocation) 기법 환형 대기상태의 배제 프로세스들로 하여금 필요한 모든 자원들을 실행 전에 미리 할당 받도록 하는 기법 단점 자원의 낭비 초래 무기한 연기 상태 발생 가능 환형 대기상태의 배제 자원들에 대한 순서화 모든 프로세스들은 순서상의 한쪽 방향으로만 자원을 요구하고 할당 받을 수 있도록 하는 기법 자원의 전체 할당 기법을 좀더 일반화한 기법임

교착상태 예방 기법 교착상태 예방 기법의 요약 - 교착상태 발생의 4가지 필요조건들 중 어느 하나를 배제함 - 대부분의 경우 자원의 심각한 낭비를 초래 - 현실적으로 사용하기 어려움

교착상태 회피 기법 교착상태 회피 기법 개요 항상 시스템 상태를 감시 자원의 할당 과정에서 시스템 상태가 교착상태로 전이될 가능성이 있다고 판단되면 자원 할당을 유보 시스템을 안전상태로만 유지

교착상태 회피 기법 Safe state vs unsafe state 안전 상태의 의미 비안전 상태의 의미 시스템 내의 모든 프로세스들을 유한 시간 내에 정상 종료시킬 수 있는 상태 Safe sequence 존재 그렇지 않은 경우를 비안전 상태(unsafe state)라 함 안전 상태의 의미 시스템의 상태가 교착상태로 전이되지 않도록 보장할 수 있음 비안전 상태의 의미 교착상태로의 전이를 피하지 못할 가능성 존재 반드시 교착상태가 발생한다는 의미 아님

교착상태 회피 기법 가정 프로세스의수가 고정되어 있어야 함 자원형 및 단위 자원의 수가 고정되어 있어야 함 각 프로세스가 시스템에 요구하는 자원의 최대 요구량이 미리 알려져야 함 프로세스는 할당받은 자원을 이후 반드시 반납하여야 함 not practical

교착상태 회피 기법 교착상태 회피 기법의 종류 Dijkstra’s Banker’s algorithm Habermann’s algorithm

Dijkstra’s 알고리즘 교착상태 회피를 위한 간단한 이론적 기법 시스템 내에 자원형이 한 가지만 존재하는 경우 1 resource type, multiple units 시스템의 상태를 항상 안전상태로만 진행 시킴

Dijkstra’s 알고리즘 상태 - 1 안전 상태의 예 시스템의 가정 프로세스-ID 최대 요구량 현재 할당량 추가요구 가능량 P1 3 1 2 P2 9 5 4 P3 5 2 3 Available resource units : 2 실행 종료 순서 : P1  P3  P2 - 안전 순서 (safe sequence) 현재 상태에서 안전 순서가 하나이상 존재하면 안전 상태임

Dijkstra’s 알고리즘 상태 - 2 비안전 상태의 예 시스템의 가정 프로세스-ID 최대 요구량 현재 할당량 추가요구 가능량 P1 5 1 4 P2 9 5 4 P3 7 2 5 Available resource units : 3 안전 순서 : 없슴 임의의 순간에 세 프로세스들이 모두 세 개 이상의 단위 자원을 요청하는 경우 시스템은 교착상태 놓이게 됨

Dijkstra’s 알고리즘 상태 - 1 시스템 운영 방법의 예 시스템의 가정 상태-1에서 프로세스들이 추가 자원 요청시 승인/거절 여부 결정 상태 - 1 프로세스-ID 최대 요구량 현재 할당량 추가요구 가능량 P1 3 1 2 P2 9 5 4 P3 5 2 3

Dijkstra’s 알고리즘 상태 - 1 상태 - 1 - 1 프로세스-ID 최대 요구량 현재 할당량 추가요구 가능량 P1 3 2 P2 9 5 4 P3 5 2 3 상태-1에서 P1이 하나의 단위 자원을 추가 요청하는 경우 - 할당 후 안전 상태 P1  P3  P2 존재 이를 할당한 후의 상태가 안전 상태이므로 이를 승인함 상태 - 1 - 1 프로세스-ID 최대 요구량 현재 할당량 추가요구 가능량 P1 3 2 1 P2 9 5 4 P3 5 2 3

Dijkstra’s 알고리즘 상태 - 1 상태 - 1-2 프로세스-ID 최대 요구량 현재 할당량 추가요구 가능량 P1 3 1 9 5 4 P3 5 2 3 상태-1에서 P2가 하나의 단위 자원을 추가 요청하는 경우 - 할당 후 안전 상태 존재하지 않음 이후의 상태가 비안전 상태이므로 이를 거절함 상태 - 1-2 프로세스-ID 최대 요구량 현재 할당량 추가요구 가능량 P1 3 1 2 P2 9 6 3 P3 5 2 3

Habermann’s 알고리즘 Dijkstra’s 알고리즘의 확장 기법임 여러 종류의 자원형이 존재함을 고려 multiple resource types multiple resource units for each resource type 시스템의 상태를 항상 안전 상태로만 진행 시킴

프로세스가 요청할 수 있는 자원에 대한 최대 요구량 Habermann’s 알고리즘 시스템 운영 방법과 안전 상태의 예 시스템의 가정 - 세가지 종류의 자원형 Ra, Rb, Rc 존재 - 각 자원형에 단위 자원이 10개, 5개, 7개씩 존재 - 프로세스 5개 존재 프로세스가 요청할 수 있는 자원에 대한 최대 요구량 프로세스-ID 최대 요구량 Ra Rb Rc P1 7 5 3 P2 3 2 2 P3 9 0 2 P4 2 2 2 P5 4 3 3

Habermann’s 알고리즘 상태 - 3 프로세스-ID 최대 요구량 현재 할당량 추가요구 가능량 Ra Rb Rc P1 7 5 3 0 1 0 7 4 3 P2 3 2 2 2 0 0 1 2 2 P3 9 0 2 3 0 2 6 0 0 P4 2 2 2 2 1 1 0 1 1 P5 4 3 3 0 0 2 4 3 1 Available resource units : (3, 3, 2) 안전 순서 : P2  P4  P1  P3  P5 - 현재 상태에서 안전 순서가 하나이상 존재하면 안전 상태임

Habermann’s 알고리즘 (상태 - 3 - 1) 상태-3에서 P2가 (1, 0, 2)만큼의 자원을 추가 요청하는 경우 - 할당 후 안전 상태 P2  P4  P1  P3  P5 존재 이후의 상태가 안전 상태이므로 이를 승인함 (상태 - 3 - 1) 프로세스-ID 최대 요구량 현재 할당량 추가요구 가능량 Ra Rb Rc Ra Rb Rc Ra Rb Rc P1 7 5 3 0 1 0 7 4 3 P2 3 2 2 3 0 2 0 2 0 P3 9 0 2 3 0 2 6 0 0 P4 2 2 2 2 1 1 0 1 1 P5 4 3 3 0 0 2 4 3 1

Habermann’s 알고리즘 (상태 - 3 - 2) 상태-3에서 P1이 (0, 3, 0)만큼의 자원을 추가 요청하는 경우 - 할당 후 안전 상태 존재하지 않음 이후의 상태가 비안전 상태이므로 이를 거절함 (상태 - 3 - 2) 프로세스-ID 최대 요구량 현재 할당량 추가요구 가능량 Ra Rb Rc Ra Rb Rc Ra Rb Rc p1 7 5 3 0 4 0 7 1 3 p2 3 2 2 2 0 0 1 2 2 P3 9 0 2 3 0 2 6 0 0 p4 2 2 2 2 1 1 0 1 1 p5 4 3 3 0 0 2 4 3 1

교착상태 검출 기법 교착상태 검출 기법 개요 교착상태에 대비한 사전 처리 없음 시스템 운영중 주기적으로 또는 필요한 경우에 교착상태 확인 현재 시스템이 교착상태인지의 여부 현재 시스템이 교착상태라면 교착상태의 프로세스 검출 자원 할당 그래프(resource allocation graph) 사용

교착상태 검출 기법 자원 할당 그래프 (resource allocation graph) 교착상태 검출을 위해 사용 방향성 이분 그래프 (directed bipartite graph) 사용 속성 방향성 그래프 (directed graph), G = (N, E)로 표현 N = { Np, Nr } where Np is the set of processes = {P1, P2, ..., Pn} and Nr is the set of resources = {R1, R2, ..., Rm}

요구 에지 (request edge) : Pi  Rj 할당 에지 (allocation edge) : Rj  Pi 모든 에지들은 Np와 Nr간에만 존재함 요구 에지 (request edge) : Pi  Rj 할당 에지 (allocation edge) : Rj  Pi Each edge e  E is between Pi  Np and Rj  Nr e = (Pi, Rj) : request edge e = (Rj, Pi) : allocation edge 자원 노드는 해당 자원의 형을 의미함 tk : 자원형 Rk에 대한 단위 자원의 수 For each Rk  Nr,  tk which is the number of units of Rk |(a, b)| 임의의 노드 a로부터 다른 노드 b로 향한 에지의 개수

자원 할당 그래프의 예 P1 t1 = 3 t2 = 2 R1 R2 P2

교착상태 검출 기법 그래프 단순화 (graph reduction) 기법 사용 주어진 그래프에 대해 에지들을 제거해 나가는 기법 완전히 단순화되었다 (completely reduced) 주어진 그래프의 모든 에지들이 제거되는 경우 현재 교착상태가 존재하지 않는다고 판단 단순화 불가능하다 (irreducible) 주어진 그래프의 모든 에지들이 제거되지 않는 경우 교착상태가 존재하는 것으로 판단

교착상태 검출 기법 그래프 단순화 (graph reduction) 기법 시스템 내에 존재하는 unblocked 프로세스를 찾아 이에 인접한 에지들을 제거함 unblocked 프로세스 현재 상태에서 요구한 자원들을 모두 할당 받을 수 있는 프로세스 정의 : unblocked 프로세스 시스템 상태를 그래프 모델로 표현했을 때 다음 조건을 만족시키는 프로세스 Pi를 말함 j (|(Pi, Rj)|  tj -  |(Rj, Pk)| ) all k

자원 할당 그래프에 대한 그래프 단순화 절차 임의의 unblocked 프로세스 노드를 찾아 인접한 모든 에지 제거 최종 형태에서 모든 에지들이 제거 되었다면 completely reduced 현재 상태에 교착상태가 존재하지 않다고 판단함 남아 있는 에지 있다면 irreducible 현재 상태에 교착상태가 존재한다고 판단함 정리 자원 할당 그래프를 단순화할 때 단순화 후의 최종 그래프 모형은 단순화 순서에 관계없이 항상 같음

자원 할당 그래프의 단순화 과정 예(1) P1 t1 = 3 t2 = 2 R1 R2 P2 Non-deadlock State (b) 프로세스 P1에 의해 단순화된 상태 (c) 프로세스 P2에 의해 단순화된 상태

자원 할당 그래프의 단순화 과정 예(2) P1 P1 R1 R2 R1 R2 P2 P3 P2 P3 R3 R3 (b) 프로세스 P3에 의해 단순화된 상태 (a) 초기상태 (b) 상태에서는 프로세스 P1과 P2가 계속 모두 blocked 상태임 - 초기 상태 그래프는 더 이상 단순화 불가능함 - 초기 상태가 교착상태임

교착상태 검출 기법 종류 그래프 단순화기법 특수한 가정 하에 오버헤드를 줄일 수 있는 교착상태 검출 기법 오버헤드가 매우 큰 기법임 특수한 가정 하에 오버헤드를 줄일 수 있는 교착상태 검출 기법 single-unit resource의 경우 사이클(cycle) 검사 기법 사용 가능 single-unit request in expedient state의 경우 knot 검사 기법 사용 가능

교착상태 검출 기법과 회피 기법의 차이 교착상태 회피 기법 교착상태 검출 기법 최악의 경우(worst case)를 고려함 최선의 경우(most favorable case)를 고려함 현재 상태에 교착상태에 놓인 프로세스가 있는가 검사 미래 상태에는 관심/대응 없음

교착상태 복구 기법 교착상태 검출 기법에 의해 교착상태의 프로세스를 검출한 후에 사용 시스템 내에 존재하는 교착상태를 제거 교착상태 복구 방법 프로세스 종료 (process termination) 기법 교착상태에 놓은 프로세스들 중 일부를 강제로 종료 시킴 강제 종료된 프로세스들은 이후 재시작됨 자원 선점 (resource preemption) 기법 교착상태를 제거하기 위해 선점되어야 할 자원들을 결정 선정된 자원들을 할당받고 있는 프로세스들로부터 선점

교착상태 복구 기법 프로세스 종료 (process termination) 기법 교착상태의 프로세스들 중 일부를 강제로 종료시킴 종료 비용 (termination cost) 모델 사용 교착상태를 제거하기 위해 종료될 프로세스들을 선택 종료 비용 산출 요소 프로세스 우선순위 (priority) 프로세스의 종류 (type) 각 프로세스의 현재까지의 실행시간 각 프로세스가 실행을 마치기 위하여 앞으로 남은 시간 회계 비용 (accounting cost) 각 프로세스 별로 종료 비용 산출

교착상태 복구 기법 프로세스 종료 (process termination) 기법 종료시킬 프로세스들의 선정 방법 lowest-termination-cost process first 기법 간단하고 오버헤드 적음 불필요한 프로세스들이 종료될 수 있음 minimum cost recovery 기법 최소 비용으로 교착상태를 제거하기 위한 프로세스들 선정 가능 선정 과정이 복잡하고 오버헤드 큼

자원 선점 (resource preemption) 기법 교착상태를 제거하기 위해 선점되어야 할 자원들을 선정 선정된 자원을 선점당한 프로세스들은 종료되고 이후 다시 실행을 시작함 교착상태에 놓이지 않은 프로세스들도 강제 종료의 대상이 됨 선점 대상 자원들의 선정 자원들의 선점 비용 모델 설정 최소의 비용을 갖는 복구 기법 사용

검사점-재시작 (checkpoint-restart) 기법 실행중인 프로세스들 필요한 시점(검사점)에서 그 프로세스의 context를 보존 프로세스가 강제 종료된 후 최근 검사점부터 재 실행하도록 함 검사점-재시작 기법 start checkpoint-1 (context saved) checkpoint-2 (context saved) checkpoint-k (context saved) abnormally terminated finish