Operating System Concepts 7장 교착상태(Deadlocks) 시스템 모델 교착상태의 특징 교착상태 처리 방법 교착상태 예방 교착상태 회피 교착상태 탐지 교착상태로부터의 회복 Operating System Concepts

Operating System Concepts 교착상태란 ? 여러 프로세스들이 각자 자원을 점유하고 있으면서 다른 프로세스가 점유하고 있는 자원을 요청하면서 무한하게 대기하는 상태 예 1: 시스템에 두개의 테이프 드라이브가 있을때, 프로세스 P1 과 P2 가 하나씩 테이프 드라이브를 사용하면서 상대방 프로세스의 테이프 드라이브를 필요로 함 예 2: 두개의 세마포어 A 와 B, (초기값은 1) P0 P1 wait (A); wait(B); wait (B); wait(A); Operating System Concepts

Operating System Concepts 교착상태란? 두 자동차가 다리의 한쪽을 차지하고 있으면서 서로 다른 한쪽을 차지하려고 함. 상대방 자동차가 뒤로 가주기를 무한히 기다림. Operating System Concepts

Operating System Concepts 시스템 모델 시스템의 자원들 : CPU, 기억장치공간, 파일, 입출력장치 등 각 자원 유형 Ri 는 여러개의 사례(instances)를 가질 수 있다. 시스템에 두개의 CPU가 있다면, CPU 자원 유형은 두개의 사례를 가짐 프로세스가 자원을 사용하려면 다음 순서로 수행함 요청(request) 요청이 즉시 허용되지 않는 경우, 자원을 얻을때까지 대기함 사용(use) 해제(release) Operating System Concepts

교착상태의 특징 교착상태는 다음 네 조건이 동시에 만족될때 발생한다. 상호배제(Mutual exclusion): 한번에 오직 한 프로세스만이 자원을 사용할 수 있다. 점유와 대기(Hold and wait): 프로세스가 적어도 하나의 자원을 점유하면서 다른 프로세스가 점유하고 있는 자원을 추가로 얻기위해 대기한다. 비선점(No preemption): 점유된 자원은 강제로 해제될 수 없고, 점유하고 있는 프로세스가 작업을 마치고 자원을 자발적으로 해제한다. 순환대기(Circular wait): 대기하고 있는 프로세스 집합 {P0, P1, …, Pn}에서 P0 은 P1이 점유한 자원을 대기하고, P1은 P2가 점유한 자원을 대기하고, Pn–1 은 계속해 Pn을 대기하며, Pn은 P0이 점유한 자원을 대기한다. Operating System Concepts

자원 할당 그래프 그래프란, 정점(vertex) 들과 정점을 연결하는 간선(edge)들로 이루어진 것. 자원 할당 그래프 : 프로세스와 자원간의 관계를 나타내는 그래프 정점의 두 형태 프로세스들을 나타내는 정점 P = {P1, P2, …, Pn} 자원들을 나타내는 정점 R = {R1, R2, …, Rm} 간선의 두 형태 요청선(request edge) : 프로세스 정점에서 자원 정점으로의 연결선 Pi  Rj 할당선(assignment edge) : 자원 정점에서 프로세스 정점으로의 연결선 Rj  Pi Operating System Concepts

Operating System Concepts 자원 할당 그래프 (Cont.) 프로세스 : 원으로 표현 자원 : 사각형으로 표현하며, 사례의 개수를 점으로 나타냄 Pi 가 자원 형태 Rj의 한 자원을 요청함 Pi 가 자원 형태 Rj 의 한 자원을 점유하고 있음 Pi Rj Pi Rj Operating System Concepts

Operating System Concepts 자원 할당 그래프의 예 Operating System Concepts

Operating System Concepts 교착상태가 있는 자원 할당 그래프의 예 주기(싸이클)가 존재 -> 교착상태 두 개의 주기가 존재함  P1 -> R1 -> P2 -> R3 -> P3 -> R2 -> P1  P2 -> R3 -> P3 -> R2 -> P2 Operating System Concepts

주기는 있지만 교착상태가 아닌 자원 할당 그래프 P1 -> R1 -> P3 -> R2 -> P1 그러나, P4가 R2를 해제하면, P3가 R2를 사용할 수 있다. 따라서, 교착상태가 아니다. Operating System Concepts

Operating System Concepts 관찰 그래프에 주기가 없으면  교착상태가 없다 그래프에 주기가 있으면  자원 유형에 하나의 사례만 있으면, 교착상태 자원 유형에 여러 사례가 있으면, 교착상태 가능성 Operating System Concepts

Operating System Concepts 교착상태 처리 방법 세가지 방법 교착상태가 발생하지 않도록 보장 : 예방, 회피 2) 교착상태를 허용하고, 발생을 탐지한 후, 복구 3) 문제를 무시하고 교착상태가 발생하지 않는다고 가정 (대부분의 운영체제에서 사용하는 방법) 대부분의 시스템은 교착상태가 잘 발생하지 않으며, 교착상태 예방, 회피, 탐지 및 복구 방법을 사용하는 것은 비용이 많이든다. Operating System Concepts

교착상태 예방 교착상태 발생 네가지 조건 중에서 하나라도 성립하지 않으면 됨 상호배제 – 공유가능한 자원들은 배타적인 접근이 아니므로 교착상태가 발생하지 않는다. 예) 읽기 전용의 파일 점유와 대기 예방 방법 프로세스가 실행되기 전에 사용할 모든 자원을 함께 요청 프로세스가 자원을 전혀 갖고있지 않을때만 자원을 요청 단점 자원의 낮은 사용률 : 자원을 실제로 사용하지 않는 동안에도 자원을 점유하고 있어야 함 기아 상태 가능성 Operating System Concepts

Operating System Concepts 교착상태 예방 (Cont.) 비선점 예방 방법 어떤 자원을 가진 프로세스가 추가의 자원을 요청하여 대기하게 되면, 가지고 있던 자원을 해제하고 대기함 대기 중인 프로세스는 이전의 자원들과 새 자원을 모두 갖게되면 재시작함 순환대기 예방 방법 모든 자원 유형에 전체 순서를 부여하고, 프로세스는 오름차순으로 자원을 요청 교착상태 예방법들은 자원의 사용률을 저하시키는 문제점이 있다. Operating System Concepts

Operating System Concepts 교착상태 회피 각 프로세스는 자원 유형마다 필요한 최대 개수를 선언하고, 시스템은 이 정보를 이용해서 교착상태가 되지 않도록 하는 방법 교착상태 회피 알고리즘은 자원-할당 상태를 감시하여 순환대기 조건이 발생하지 않도록 한다. 자원-할당 상태 : 자원의 가용 개수와 할당 개수, 프로세스들의 최대 요구 개수로 정의됨 Operating System Concepts

Operating System Concepts 안정 상태 (Safe State) 어떤 프로세스가 자원을 요청하면, 시스템은 이 자원을 할당한 후의 상태가 안정 상태인지 검사함. 안정 상태 : 특정한 순서대로 각 프로세스에 자원을 할당할 수 있고, 교착상태를 방지할 수 있는 경우 프로세스들의 순서 <P1, P2, …, Pn>는, 모든 Pi,에 대해서 Pi 가 요청하는 자원들이 현재 사용가능한 자원들과 j < i인 Pj가 점유하는 자원으로서 만족된다면 안정상태이다. 이때 Pi 가 필요한 자원들을 즉시 사용할 수 없다면, Pi 는 Pj 가 끝날때까지 대기한다. Pj 가 끝나면, Pi 는 필요한 자원을 획득하고, 작업을 수행한 후 모든 점유하는 자원을 해제하고 종료한다. Pi 가 종료하면, Pi+1 이 필요한 자원을 확보하고 계속 처리를 진행한다. Operating System Concepts

안정 상태의 예 3개의 프로세스 : P0, P1, P2 12개의 자기 테이프 시간 t0에서의 시스템 상태 최대 수요 현재 수요 이때, 시스템은 안정 상태에 있다. 프로세스 P1이 먼저 수행되면, 테이프 장치를 할당받아 작업을 마칠 수 있고, 다음에 프로세스 P0이 수행되어 테이프 장치를 할당받을 수 있으며, 다음에 프로세스 P2가 수행되면 모두 완료되기 때문이다. 즉, <P1, P0, P2> 순서는 안정 상태를 충족한다. 현재 총 수요가 9이므로 남아있는 테이프는 3개이다 최대 수요 현재 수요 P0 10 5 P1 4 2 P2 9 2 Operating System Concepts

Operating System Concepts 안정, 불안정, 교착 상태 Operating System Concepts

Operating System Concepts 관찰 시스템이 안정상태라면  교착상태가 없다 시스템이 불안정상태라면  교착상태 가능성 교착상태는 불안정 상태이다. 그러나, 불안정 상태라고 해서 모두 교착상태는 아니다. 교착상태 회피  시스템이 불안정상태에 들어가지 않도록 함 Operating System Concepts

Operating System Concepts 자원 할당 그래프 알고리즘 자원 유형마다 하나의 자원을 가진 시스템에서 사용한다. 요청가능 선(Claim edge) Pi  Rj : 프로세스 Pj 가 미래에 자원 Rj를 요청할 것을 의미함. 점선으로 표현. 요청가능 선은 프로세스가 자원을 요청하면 요청선으로 변환됨 요청선은 자원이 할당되면 할당선으로 변환됨 프로세스가 자원을 해제하면 할당선은 요청가능선으로 변환됨 프로세스가 실행되기 전에, 프로세스의 모든 요청가능 선들을 자원 할당 그래프에 포함시킴. 그래프에 주기가 생기는 지 검사함 주기가 없다면 시스템은 안정상태 주기가 생기면 불안정상태 Operating System Concepts

Operating System Concepts 예 할당선 요청선 요청가능선 요청가능선 Operating System Concepts

Operating System Concepts 불안정 상태 Operating System Concepts

은행가 알고리즘(Banker’s Algorithm) 자원 유형에 다수개의 자원을 가진 시스템에서 사용 각 프로세스는 실행되기 전에 필요로 하는 모든 자원 형태들의 최대수를 선언한다. 프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는 지를 검사함. 안정 상태에 있으면 자원을 할당하고 그렇지 않으면 다른 프로세스들이 자원을 해제할 때까지 대기함 Operating System Concepts

Operating System Concepts 은행가 알고리즘의 자료 구조 n = 프로세스의 개수, m = 자원 유형의 개수 Available: 길이가 m인 벡터. available [j] = k : 자원 유형 Rj 에 k개의 자원 사례가 사용가능함 Max: n x m 행렬. Max [i,j] = k : 프로세스 Pi 는 자원 유형 Rj에 최대 k개의 자원을 요청할 수 있음. Allocation: n x m 행렬. Allocation[i,j] = k : 프로세스 Pi 는 현재 자원 유형 Rj의 자원을 k개 할당받았음. Need: n x m 행렬. Need[i,j] = k : 프로세스 Pi 작업을 끝내기 위해서 자원 유형 Rj 의 자원을 k개 필요로 함. Need [i,j] = Max[i,j] – Allocation [i,j]. Operating System Concepts

안정 알고리즘(Safety Algorithm) 시스템이 안정상태인지 판단하는 알고리즘 1. Work와 Finish 를 길이가 각각 m과 n인 벡터라고 하자. 초기값은, Work := Available Finish [i] = false, i = 1,2, …, n. 2. 다음과 같이 되는 i를 찾는다. (a) Finish [i] = false (b) Needi  Work 이런 i가 없다면, 단계 4로 간다. 3. Work := Work + Allocationi Finish[i] := true 단계 2로 간다. 4. 모든 i에 대해서, Finish [i] = true, 시스템은 안정 상태이다. Operating System Concepts

Operating System Concepts 프로세스 Pi의 자원 요청 알고리즘 Requesti = 프로세스 Pi의 요청벡터, 즉, Requesti [j] = k 이면, 프로세스 Pi 가 자원 유형 Rj의 자원 k개를 요청 1. Requesti  Needi 이면 단계 2로 간다. 그렇지 않으면, 오류. 2. Requesti  Available 이면 단계 3으로 간다. 그렇지 않으면 Pi 는 대기한다. 3. 시스템은 상태를 다음과 같이 수정한다: Available := Available - Requesti; Allocationi := Allocationi + Requesti; Needi := Needi – Requesti;; 결과가 안정 상태이면, 프로세스 Pi 에게 자원을 할당. 불안정 상태이면, Pi 는 대기하고, 자원할당 상태는 이전으로 복원된다. Operating System Concepts

Operating System Concepts 은행가 알고리즘의 예제 5개의 프로세스 : P0 ~ P4 3개의 자원 유형 : A (10 instances), B (5 instances), C (7 instances). 시간 T0: Allocation Max Available A B C A B C A B C 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 Operating System Concepts

Operating System Concepts 예제 (Cont.) 행렬 Need 의 내용 : Max – Allocation Need A B C P0 7 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 P4 4 3 1 이때 이 시스템은 안정상태에 있다. < P1, P3, P4, P2, P0> 순서가 안정조건을 충족함 Operating System Concepts

Operating System Concepts Request  Available인지 검사 (즉, (1,0,2)  (3,3,2)  true인지 검사). 조건이 만족되어 다음의 새로운 상태로 가게 됨 Allocation Need Available A B C A B C A B C P0 0 1 0 7 4 3 2 3 0 P1 3 0 2 0 2 0 P2 3 0 1 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 이 상태가 안정상태인지 검사 : <P1, P3, P4, P0, P2> 가 안정조건을 충족함 P4 가 (3,3,0)을 요청하면 : 자원 부족이므로 허용 불가 P0 이 (0,2,0)을 요청하면 : 불안정 상태이므로 허용 불가 Operating System Concepts

Operating System Concepts 교착상태 탐지 교착상태가 일어나도록 허용함 교착상태가 발생했는 지를 탐지하는 알고리즘이 수행 교착상태로부터 회복하는 알고리즘이 수행 Operating System Concepts

Operating System Concepts 각 자원 형태가 하나의 자원을 가진 경우 대기 그래프(wait-for graph) 자원 할당 그래프의 변형을 사용함 (자원 형태의 노드를 제거) 대기 그래프의 노드는 프로세스를 표현함 Pi 가 Pj의 자원을 대기하는 상태 : Pi  Pj 탐지 알고리즘은 주기적으로 수행하면서 대기 그래프에 주기가 생기는지 검사함. 그래프의 노드가 n개 이면, n2 의 연산이 필요함 Operating System Concepts

Operating System Concepts 자원 할당 그래프와 대기 그래프 자원 할당 그래프 대응하는 대기 그래프 Operating System Concepts

Operating System Concepts 각 자원 형태가 여러 자원을 가진 경우 자원 형태의 개수 : m, 프로세스의 개수 : n Available: 각 자원 형태마다 사용가능한 자원의 수를 표시하는 길이가 m인 벡터 Allocation: 각 프로세스에 현재 할당된 각 형태들의 자원의 수를 표시하는 n x m 형렬 Request: 각 프로세스의 현재 요청을 표시하는 n x m 행렬. 만약 Request [I, j] = k라면, 프로세스 Pi 는 자원 형태 Rj의 자원을 k개 더 요청 Operating System Concepts

Operating System Concepts 탐지 알고리즘 1. Work 와 Finish 는 길이가 각각 m 과 n인 벡터이고 초기값은, (a) Work := Available (b) For i = 1,2, …, n, if Allocationi  0, then Finish[i] := false; otherwise, Finish[i] := true. 2. 다음과 같은 색인 i 를 찾는다: (a) Finish[i] = false (b) Requesti  Work 만약 이런 i 가 없다면, 단계 4로 간다. Operating System Concepts

Operating System Concepts 탐지 알고리즘 (Cont.) 3. Work := Work + Allocationi Finish[i] := true 단계 2로 간다. 4. 어떤 i(1  i  n)에서 Finish[i] = false가 되면 시스템은 교착상태가 됨. 그리고, Finish[i] = false이면, Pi 는 교착상태에 있다. 이 알고리즘은 교착상태에 있는 지를 탐지하기 위해 m x n2 의 연산을 요구한다. Operating System Concepts

Operating System Concepts 탐지 알고리즘의 예제 다섯개의 프로세스 (P0 ~ P4)와 세개의 자원 형태 A (7 자원), B (2 자원), C (6 자원). 시간 T0: Allocation Request Available A B C A B C A B C 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 <P0, P2, P3, P1, P4> 순서는 모든 i에 대해서 Finish[i] = true로 됨 Operating System Concepts

Operating System Concepts 예제 (Cont.) P2 가 자원 형태 C의 자원을 한 개 더 요청하면 : Request A B C P0 0 0 0 P1 2 0 2 P2 0 0 1 P3 1 0 0 P4 0 0 2 시스템의 상태는 ? 교착상태가 존재 Operating System Concepts

Operating System Concepts 교착상태로부터 회복 오퍼레이터가 수동적으로 처리 시스템이 자동적으로 처리 프로세스 중지 교착상태에 있는 모든 프로세스를 중지시킴 교착상태가 해결될 때까지 프로세스를 하나씩 중지 자원 선점 프로세스로부터 자원을 선점해 이들을 교착상태가 해결될 때까지 다른 프로세스에게 준다 Operating System Concepts