교착상태

교착상태(deadlock)

 

여러 개의 프로세스가 서로 상대방의 작업이 끝나기만 기다리고 있어 어느쪽고 영원히 진행하지 못하는 상태

 

개요

프로세스 자원 사용 절차

요구 -> 사용 -> 해제

요구과정에서 가용한 자원이 없으면 자원 획득까지 대기

 

교착상태와 기아상태의 차이

교착상태 영원히 대기가 중인 상태

기아상태 언젠가는 대기가 풀릴 수 있는 상태

 

특성

 

필요조건

네 가지 조건이 동시에 만족될 때 교착상태 발생가능

 

상호배제(mutual exclusion)

프로세스가 자원에 대한 배타적인 통제권을 요구

적어도 하나 이상의 자원은 여러 프로세스에 의해 동시에 사용될 수 없음

다른 프로세스가 점유한 자원이 필요하면 반드시 대기

 

점유대기(hold and wait)

프로세스가 이미 한 자원을 할당 받아 점유하고 있는 상황에서 다른프로세스가 점유하고 있는 또 다른 자원을 요구하여 해제되기를 기다리는 상황

 

비선점(no preemption)

프로세스에 할당된 자원은 그 프로세스가 사욧ㅇ을 마치고 스스로 반환 하기 전에는 해제 되지 않음

할당된 자원은 타의에 의해서는 해제 안됨

 

환형대기(circulat wait)

프로세스의 자원 점유 밑 점유된 자원의 요구 관계가 환형을 이루며 대기하는 상황

 

자원할당 그래프 G = ( V, E )

V :정점의 집합 V = P ∪ R

P = {p1,p2....pn}: n개의 프로세스 = pi

R = {r1,r2....rn}: n개의 자원 = rj

 

E: 방향 있는 간선의 집합 E = Q ∪ S

Q = {(pi,rj): pi ∈ P, rj ∈ R}: 프로세스 pi 가 자원 rj를 요구

요구 간선

S = {(rj,pi): rj ∈ P, pi ∈ R}: 자원 rj가 프로세스 pi에 할당

할당 간선

 

교착상태의 필요 조건 표현

상호배제 : 하나의 할당 간선

점유대기 : 한프로세스에 할당간선과 요구간선 연결

비선전 : 요구간선

환형대기 : 사이클

 

처리기법

예방

교착 상태의 네가지 필요 조건이 동시에 만족되는 것을 피하여 교착상태가 발생하지 않도록 하는 방법

 

상호배제 조건 제거

공유할 수 있는 자원 : 상호배제 필요 없음

예: 읽기 전용파일

공유할 수 없는 자원 : 반드시 상호배제 필요

예 : 프린터

상호배제 조건 제거로 교착상태 예방은 불가능

 

점유대기 조건 제거

자원을 점유했을 때 대기하지 않아야 함

프로세스가 앞으로 필요한 모든 자원을 처음에 한떠번에 요구하여 할당받음

, 자원이용률 낮아짐 기아상태 가능

 

대기할 때 자원을 점유하고 있지 않아야함

새로운 자원을 요구할 때 할당 받았던 자원을 모두 해제

점유 도중 해제할 수 없는 자원에는 적용 불가

 

비선점 조건 제거

선점이 가능학도록 해야함

자원 특성에 따라 불가능한 경우 존재

예 : 프린터

다른 프로세스가 대기할 가능성 줄이기

점유대기 상황이 발생하면 할당받았던 자원을 모두 해제

프린터 같은 자원에 적용 불가

 

환형대기 조건 제거

모든 자원에 일련번호 지정

함수 f: R -> N (R:자원집합, N:자연수 집합)

방법1 - 프로세스는 자원을 요구할 때 일련번호 기준으로 항상 오름차순이 되도록 요구

가장 최근에 할당받은 자원이 ri이면 다음에 요구할 자원 rj는 f(ri) < f(rj) 만족

방법2 – 프로세스가 자원을 요구할 때 그보다 일련번호가 작은 자원만 점유하도록 함

점유대기 중인 프로세스는 점유 중인 자원의 일련번호보다 대기 중인 자원의 일련번호가 큼

, 환형대기 발생 불가능

 

프로세스마다 요구순서가 다를 수 있어 자원의 일련번호 설정 어려움

요구순서가 일련번호 오름차순으로 못 지키면 점유자원 해제 필요하나 적용 불가한 자원 존재

 

 

회피

프로세스에 필요한 자원의 최대량에 대한 정보를 이용하여 교착상태가 발생하지 않도록 하는 방법

 

사전정보

현재 할당된 자원

가용상태의 자원

프로세스들의 최대 요구량

 

안전상태

교착상태를 회피하면서 각 프로세스에 그들의 최대 요구량 까지 빠짐없이 자원을 할당할 수 있는 상태

안전순서열이 존재하는 경우

안전순서열 순서 있는 프로세스의 집합<p1, p2,.... pn>

각 pi 에 대해 pi가 추가로 요구할 수 있는 자원의 양이 현재 가용상태의 자원으로 충당되거나 혹은 여기에 pj(단 j< I)에 할당된 자원까지 포함하여 충당 가능한 경우

 

교착상태 회피

교착상태는 불안전 상태에서만 발생 가능

항상 안전상태를 유지

프로세스가 가용상태의 자원을 요구하더라도 프로세스는 대기 상태가 될수 있음

자원이용율은 다소 낮아질 수 있음

 

교착상태 회피 알고리즘

각 자원의 단위자원이 하나밖에 없는 경우

변형된 자원 할당 그래프

자원 정정에 표시하던 단위자원의 개수 제거

선언간선(pi, rj) 추가

앞으로 프로세스 pi가 자원 rj를 요구하게 될 것임

자원을 요구 받으면 해당 선언간선을 요구간선으로 변경

그 요구간선을 할당간선으로 변환해도 사이클이 생기지 않는 경우에만 자원을 할당하고 할당간선으로 변환

 

각 자원의 단위자원이 여러 개일 수 있는 경우

은행원 알고리즘

자원을 요구 받으면 그자원을 할당해 주고 난 후의 상태를 계산해서 그것이 안전상태인지 확인

안전상태가 보장되는 경우에만 자원을 할당

MAX 최대 필요한 자원

ALLOC 할당된 자원

NEED 추가로 필요한 자원

AVAIL 남아 있는 자원

 

불안전상태

안전순서열이 존재 하지 않는 경우

 

 

탐지 및 복구

교착상태의 발생 여부를 조사하여 발생한 경우에는 적절한 조치를 취해 정상상태로 복구하는 방법

 

사후에 처리하는 방법

 

교착상태 탐지

시스템의 교착상태 여부를 오자사기 위해 주기적으로 상태조사 알고리즘 수행

Shoshani와 Coffman알고리즘

 

교착상태 복구

교착상태가 탐지된 경우 적절한 조치를 취해 복구

복구의 주체

오퍼레이터 = 수작업으로 복구

운영체제 = 자동으로 복구

방법

교착상태 프로세스를 종료

모든 교착상태 프로세스를 종료

단점 : 진행했던 내용에 대한 복원비용이 큼

사이클이 제거될 때 까지 교착상태 프로세스를 하나씩 종료

단점 :　종료대상을 선택하기 위한 비용 , 매 프로세스 종료 후 교착상태 재확인을 위한 비용

 

교착상태 프로세스가 할당받은 자원을 해제

사이클이 제거될 때까지 할당된 자원을 단계적으로 선점하여 다른 프로세스들에 할당

프로세스와 자원 선택 기준

프로세스 진척도, 사용 중인 자원의 수 등

프로세스 복귀 시점도 제반 요소를 고려하여 결정

기아상태에 빠지지 않도록 프로세스 선택 시 복구 횟수 고려