제 7 장 교착 상태 7.1 개요 7.1.1 개념 교착 상태란 프로세스들의 집합이 더 이상 진행을 못하고 영구적으로 블록되어 있는 상태 집합 내의 한 프로세스가 특정 사건의 발생을 기다리며 대기하고 있고, 이 사건이 집합 내의 다른 블록 된 프로세스에 의해 발생될 수 있을 때 이 프로세스의 집합은 교착 상태가 된다. A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set. 7.1.2 교착 상태의 모델 교착상태의 예 여러 개의 돌로 된 징검다리가 있는 강을 건너는 문제 사거리 교차로에서 교착상태 Slide 1 (of 13)
프로세스는 자원을 요구(Request)사용(Use)해제(Release)한다. 자원의 여러 가지 형태 분류: 선점 가능 자원, 선점 불가능 자원, 전체 할당 자원, 분할 할당 자원, 공유 할당 자원, 배타적 할당 자원, 순차적 재사용 자원, 소비성 자원 자원 할당 그래프 Slide 2 (of 13)
간단한 자원 교착 상태 7.1.3 교착 상태 조건 교착 상태는 시스템에서 다음과 같은 네 가지 조건이 동시에 필요충분조건이 될 때 발생한다. 상호 배제(Mutual Exclusion): 프로세스들은 자신이 필요로 하는 자원에 대해 배타적인 사용을 요구한다. 점유와 대기(Hold & Wait): 프로세스가 적어도 하나의 자원을 점유하면서, 다른 프로세스에 의해 점유된 다른 자원을 요구하고 할당 받기를 기다린다. Slide 3 (of 13)
7.2 교착 상태 예방(Deadlock Prevention) 비선점(No Preemption): 자원을 점유하고 있는 프로세스는 그 작업의 수행이 끝날 때까지 해당 자원을 반환하지 않는다. 환형 대기(Circuit Wait): 프로세스들의 환형 대기가 존재하여야 하며, 이를 구성하는 각 프로세스는 환형 내의 이전 프로세스가 요청하는 자원을 점유하고, 다음 프로세스가 점유하고 있는 자원을 요구하고 있는 경우 교착 상태가 발생할 수 있다. 7.2 교착 상태 예방(Deadlock Prevention) 교착 상태 발생에 필요한 조건들이 발생하지 않도록 한다. 점유와 대기(Hold & Wait) 조건 방지 비선점(No preemption) 조건 방지 환형 대기(Circular Wait) 조건 방지 7.2.1 점유와 대기 조건 방지 각 프로세스는 필요한 자원들을 모두 한꺼번에 신청하고, 시스템은 요청된 자원들을 분석하여 한 프로세스가 요구한 자원을 전부 할당하여 주거나 또는 하나라도 부족하면 전혀 할당하지 않는 방식으로 자원을 할당하도록 한다. 7.2.2 비선점 조건 방지 추가 자원에 대한 요구가 거절 당한 프로세스는 자원을 전부 반납하고 필요하다면 추가 자원과 함께 다시 요구하도록 하는 방법으로 자원을 관리한다. Slide 4 (of 13)
7.3 교착 상태 회피(Deadlock Avoidance) 7.2.3 환형 대기 조건 방지 시스템 설치 시 모든 자원에게 고유 번호를 부여하여, 프로세스들이 자원을 요청할 때에는 번호가 증가하는 순으로 요청하도록 하고, 또 추가로 요청하는 경우에도 현재 가지고 있는 자원보다 더 큰 번호를 가진 자원만을 요청하도록 제한한다. 7.3 교착 상태 회피(Deadlock Avoidance) 자원이 어떻게 요청되는지에 대한 추가적인 정보를 가지고 이 정보를 이용하여 교착 상태를 피하는 방법이다. 7.3.1 은행가 알고리즘 자료구조 m : 자원 종류의 수 n : 프로세스의 수 Available(j) : 자원 Rj 중 사용 가능한 수 Max(i, j) : 프로세스 Pi가 자원 Rj에 대하여 최대로 요구할 수 있는 수 Request(i, j) : 프로세스 Pi가 필요로 하는 자원 Rj의 수 Allocation(i, j) : 프로세스 Pi가 할당 받은 자원 Rj의 수 Need(i, j) : 프로세스 Pi가 추가로 필요로 하는 자원 Rj의 수 Slide 5 (of 13)
7.3.2 안전(Safety) 알고리즘 안전 상태: 모든 프로세스들이 교착 상태를 일으키지 않으면서 수행을 끝낼 수 있는 순서가 최소한 하나 이상 존재할 때의 상태 안전 순서(Safe Sequence): The sequence <P1, P2, …, Pn> is safe if for each Pi, the resources that Pi can request can be satisfied by currently available resources + resources held by all the Pj, with j<i. Slide 6 (of 13)
자원 요청 알고리즘 Slide 7 (of 13)
은행가 알고리즘의 예 전체 자원의 수: A(9), B(5), C(7) 할당량 (Allocation) 필요량 (Need) 최대 요구량 (Max) 잔여량 (Available) A B C P1 1 6 4 3 7 5 2 P2 P3 P4 P5 안전순서 <P4, P2, P5, P3, P1>이 존재하므로 안전 상태이다. Slide 8 (of 13)
7.4 교착 상태 탐지 7.4.1 탐지 알고리즘 시스템의 상태를 검사하는 알고리즘은 주기적으로 교착 상태를 찾는 데 이용된다. 만일, 교착 상태가 탐지되면 시스템은 이 교착 상태로부터 회복해야 한다. 프로세스에 할당된 자원에 관한 정보뿐만 아니라 자원 할당 요청에 대한 정보도 유지해야 한다. 시스템이 교착 상태에 있는지, 아닌지를 알아내기 위해 이 정보를 이용한 알고리즘이 제공되어야 한다. 탐지 알고리즘 자료구조: 시스템에 n개의 프로세스와 m개의 자원의 종류가 있는 경우 Available : 각 종류에 사용 가능한 자원 수를 나타내는 길이가 m인 벡터 Allocation : 현재 각 프로세스에 할당된 각종 자원의 수를 정의한 nm 행렬 Request : 각 프로세스가 현재 요청한 자원을 나타내는 n m 행렬 Slide 9 (of 13)
알고리즘 (1) Work와 Finish는 각각 의 값이 m과 n인 벡터이다. 초기치로 Work := Available, if Allocation i ≠ 0 then Finish[i] = false otherwise Finish[i] = true 단, i=1, 2, …, n (2) 다음과 같이 되는 i 값을 찾는다. a. Finish[i] = false b. Need i ≤ Work 만일, 이러한 i 값이 존재하지 않는다면 4단계로 간다. (3) Work := Work + Allocation i Finish[i] := true go to step (2) (4) 모든 i에 대하여 Finish[i] = true이면, 이 시스템은 안전 상태이다. 또한, Finish[i] = false이면 Pi는 교착 상태이다. Slide 10 (of 13)
탐지 알고리즘의 예 Slide 11 (of 13)
7.5 교착 상태 회복 교착 상태 회복을 위한 가장 적절한 접근 방법은 효과적인 중지/재개 방법이다. 7.5.2 회복 방법 교착 상태의 회복 방법으로는 교착 상태에 있는 한 개 또는 그 이상의 프로세스를 희생시켜 선점을 허용함으로써 해결한다. 희생자(victim) 선정 희생자 선택의 기준은 최소 비용에 기준해서 결정해야 하는데 실제로 최소 비용을 결정하는 요인 프로세스들의 우선순위 프로세스가 얼마나 오랫동안 연산하였고, 또 일을 완료하기 위해서 앞으로 얼마만큼의 시간을 요구하는가? 프로세스가 어떤 유형의 자원과 몇 개의 자원들을 사용하고 있는가? 몇 개의 프로세스를 희생시킬 것인가? Slide 12 (of 13)
복귀(rollback) 문제 기아현상의 문제 교착 상태를 해소 시킬 수 있는 최소한의 프로세스를 최소한의 시간 범위 안에서 복귀시키는 것이다. 기아현상의 문제 기아현상: 어느 한 프로세스가 반복적으로 희생자로 선정될 수 있다. 희생자를 선정하더라도 반복하여 선정될 그 반복 횟수의 상한선을 정한다. Slide 13 (of 13)