[OS] DeadLock (교착상태)

DeadLock (교착상태)

데드락

ㅡ> 서로 상대가 가진 자원을 기다리는 상태 (양보x)

ㅡ> 하드웨어 자원, 소프트웨어 자원

 

프로세스가 자원을 사용하는 절차 4단계

ㅡ> Request

ㅡ> Allocate

ㅡ> Use

ㅡ> Release

데드락 발생조건 4가지

■ 상호배제

ㅡ> 한놈만 사용 가능

■ 비선점

ㅡ> 강제로 빼앗을 수 없음

■ 보유대기

ㅡ> 자원을 자발적으로 내려놓지도 않음

■ 순환대기

ㅡ> 기다리는데 사이클이 형성

Resource-Allocate Graph

■ Resource-Allocate Graph

ㅡ> 데드락이 발생했는지 알아보기 위한 그래프

 

■ 도형

ㅡ> 동그라미 ▶ 프로세스

ㅡ> 네모 ▶ 자원

ㅡ> 네모안의 점 ▶ 자원의 인스턴스 수 (자원의 수)

 

■ 화살표

ㅡ> 네모에서 동그라미 ▶ 자원 할당된 상태

ㅡ> 동그라미에서 네모 ▶ 자원을 기다리는 상태

 

■ 그래프에 사이클이 없는 경우

ㅡ> 데드락x

 

■ 그래프에 사이클이 있는 경우

ㅡ> 인스턴스가 한개면 데드락이다

ㅡ> 인스턴스가 여러개면, 데드락의 가능성이 있다

 

■ 왼쪽그림

R2의 인스턴스가 2개지만

2개 다 사이클에 연류되어 있어서 데드락이다.

 

■ 오른쪽그림

R1, R2의 인스턴스가 2개인데

각각 한개씩만 사이클에 연류되어 있어서

나머지 한개가 반납되면 사이클이 해소될 수 있다

Deadlock의 처리 방법

■ 위에있는 2가지

ㅡ> 데드락을 미연에 방지함

■ 3번째

ㅡ> 데드락이 발생하면 리커버리

■ 4번째

ㅡ> OS가 데드락이 발생해도 그냥 둠

ㅡ> 사람이 알아서 해결해야 함

ㅡ> 현대적인 방식 ▶ 데드락은 빈번한 이벤트가 아니기 때문에, 미연에 방지하려고 오버헤드를 발생시키는건 비효율적

Deadlock Prevention

■  Deadlock Prevention (데드락 방지)

ㅡ> Deadlock의 4가지 조건중 하나를 막아서 방지함

ㅡ> Utilization저하, throuhput 감소, starvation 문제

ㅡ> 잘 일어나지도 않을 데드락을 막느라 제약을 달아놔서 비효율적

 

■ Mutual Exclusion

ㅡ> 공유자원이기 때문에 이건 막으면 안됨

 

■ Hold and Wait

ㅡ> (방법1) 필요한 자원을 모두 할당받은채로 시작 ▶ 안쓰는 자원도 들고있어서 비효율적

ㅡ> (방법2) 자원이 필요한 경우, 지금 가지고있는 자원을 반납함

 

■ No Preepmtion

ㅡ> 자원을 선점할 수 있게 만듬

ㅡ> 근데 아무렇게나 뺏어오면 문제가 생길 수 있음 ▶  State를 쉽게 save하고 restore할 수 있는 자원에서 사용하는게 좋음 (CPU, Memory)

 

■  Circular Wait

ㅡ> 자원을 순서대로만 얻을 수 있게 만들어서 사이클을 막음

ㅡ> 예를들어 오름차순으로 얻어야 한다면, 3번자원을 얻으려면 1번자원을 가지고 있어야 해서, 1번이 없는 다른 프로세스가 3번을 가지고 있을 일이 없다

Deadlock Avoidance

Deadlock Avoidance

ㅡ> 데드락의 가능성이 없는 경우에만 자원을 할당해줌

ㅡ> 프로세스가 최대로 쓸 자원의 양을 미리 알고있다고 가정하고, 그 정보를 바탕으로 판단

 

Safe State

ㅡ> safe sequence가 존재하는 상태

 

Safe Sequence

ㅡ> 지금은 자원요청이 거부 되어도, 앞의 프로세스가 반납하면 자원요청이 가능하고

ㅡ> 그 다음 프로세스도 이전 프로세스가 반납하면 가능해지고

ㅡ> 이런 시퀀스가 생기면 safe sequence라 함

인스턴스 한개 (자원 한개)

ㅡ> Resource Allocation Graph algorithm 사용

인스턴스 여러개

ㅡ> Banker's Algorithm 사용

 

Unsafe 영역에 있어도 반드시 데드락인건 아니지만

Deadlock Avoidance 방식은 Safe영역에 머무르는 방식이

Resource Allocation Graph algorithm

인스턴스가 1개

 

점선

ㅡ> 이 자원을 평생에 한번은 사용할 일이 있다는 의미

ㅡ> 점선은 사이클을 형성하지 않는다

ㅡ> 실선이 되면 그때 사이클을 형성한다

ㅡ> 하지만, Deadlock Avoidance 방식은 최악의 상황을 가정한다 ▶ 점선도 실선으로 생각해서, 사이클이 생기면 자원을 할당해주지 않는다

 

그림에서, 2번 프로세스에게 자원을 부여하면

점선을 포함해서 사이클이 형성된다

그래서 R2 자원이 있어도 P2한테 할당해주지 않는다

Banker's Algorithm 

프로세스 5개

자원 종류 A,B,C

인스턴스 각각 10개, 5개, 7개

 

Allocation : 각 프로세스에 현재 할당된 자원

Max : 각 프로세스가 평생에 쓸 자원의 양

Available : 가용 가능한 자원의 양

Need : 가용가능한 자원이 얼마나 있어야 하는가 (Max - Allocation)

 

 

Need가 Available을 초과하는 경우에는

해당 프로세스가 자원을 몇개를 요청하든 할당해주지 않는다 (1개를 요청해도 거부)

ㅡ> Need가 Avail을 넘는 것 자체가 데드락은 아니지만, 보수적으로 접근하는 것 (최악의 경우를 가정)

Deadlock Detcetion and Recovery

빈번하지도 않은 데드락 막으며 오버헤드 발생시킬 바엔

그냥 냅두고

발생했을 때 탐지해서 회복시키는 방식

인스턴스 1개일땐 그래프

n개의 프로세스에서 화살표는 최대 n(n-1)개이므로

O(n^2)

인스턴스 여러개일땐 유사 Banker's

위 상황은

세이프 시퀀스가 존재하니 데드락이 아니다

 

Request가 없는 P0,P2가 먼저 반납하면 Avail이 늘어나고

그 늘어난 Avail 바탕으로 다른 P의 Request 해소해주고 반납받고 하는 연속선이 존재하면

그것을 세이프 시퀀스라고 한다

Recovery

Process termination

ㅡ> 프로세스 종료

ㅡ> 방법1 : 전부 종료

ㅡ> 방법2 : 하나씩 종료해보며 데드락 해제됐나 확인

 

Resource Preeption

ㅡ> 데드락에 연루된 프로세스로부터 자원을 뺏음

ㅡ> victim : 자원을 뺏길 프로세스

ㅡ> safe tate에서 재시작

 

다른 victim을 선정

ㅡ> 똑같은 패턴으로 계속 데드락에 걸릴 수 있으니 패턴을 바꿔야 함

ㅡ> 똑같은 victim이면 starvation문제도 발생

Deadlock Ignorance

데드락이 발생해도 그냥 둠

ㅡ> OS가 아닌 사용자가 직접 해결해야 함

ㅡ> 현대의 OS들은 이 방식을 채택 

ㅡ> 데드락은 매우 드물어서, 오버헤드를 줄이기 위함