이론 5) 교착 상태

 

 

 

 

 

 

0. 프로세스는 다음의 순서로 자원을 이용한다.

자원 요청 -> 사용(점유) -> 해제

 

1. 교착 상태란?

: 프로세스에 의해 발생할 사건(Event)을 프로세스들이 서로 기다리고 있는 상태이다.

둘 이상의 작업이 보류 상태에 놓여 자원을 이용하기 위해 서로 기다린다.

 

 

 

 

 

 

 

 

2. 교착 상태 발생의 네가지 조건

1) 상호배제 : 한 번에 한 프로세스만 해당 자원을 사용할 수 있어야 한다.

2) 점유와 대기 : 최소한 자원 하나를 보유하고, 다른 프로세스에 할당된 자원을 얻기 위해 기다리는 프로세스가 있어야 한다.

3) 비선점 : 자원을 갖에로 빼앗을 수 없다.

4) 순환대기(환형대기) : 교착상태를 따라가면 원이 만들어진다.

 

 

 

 

-> 이 중 하나라도 발생하지 않으면 교착 상태가 발생하지 않는다 !

 

 

 

 

 

 

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

 

V = 정점들의 집합 (시스템 내의 모든 자원 R 과 프로세스 P )

E = 간선들의 집합( 요청 / 할당 간선 )

 

 

ex 1)

 

 

 

 

-> P1은 R2를 보유하고 있고, R1을 기다리고 있다.

-> P2는 R1을 보유하고 있고, R3를 기다리고 있다.

-> P3는 R3 하나를 보유하고 있다.

 

 

< 교착 상태 발생 여부 확인 >

상호 배제 : O

점유와 대기 : X -> P3가 다른 프로세스에 할당된 자원을 기다리고 있지 않다.

비선점 : O

순환대기 : X

-> 순환대기를 만족하지 않기 때문에 교착상태가 아니다.

 

 

 

 

ex 2)

: P1 -> R1 -> P2 -> R3 -> P3 ->R2 -> P1

: P2 -> R3 -> P3 -> R2 -> P2

-> 두 개의 사이클 

 

< 교착 상태 발생 여부 확인 >

상호 배제 : O

점유와 대기 : O

비선점 : O

순환대기 : O

-> 모든 조건을 만족하기 때문에 교착상태이다.

 

 

 

 

 

ex 3)

: 사이클이 있지만, 모든 프로세스가 참여하는 것은 아니므로 교착상태가 아니다.

 

< 교착 상태 발생 여부 확인 >

상호 배제 : O

점유와 대기 : X -> P2, P4가 만족하지 않는다.

비선점 : O

순환대기 : X

-> 교착상태가 아니다.

 

 

 

 

 

 

 

 

3. 교착 상태 처리 방법

 

1) 운영체제가 관여하여 프로토콜을 사용한다.

- 교착 상태 예방 (정적 - 현재 상황에 영향을 안 받음 )

- 교착 상태 회피 (동적 - 현재 상황에 영향을 받음 )

 

2) 운영체제가 교착 상태에 들어가도록 허용한 다음 회복한다.

- 교착 상태 탐지 및 회복 (어렵고 비용 많이 소요)

 

3) 교착 상태가 시스템에서 발생하지 않은 것처럼 무시한다. ( 운영체제가 관여하지 않는다. 제일 많이 사용하는 방법 )

- UNIX 등 대부분의 운영체제에서 사용한다.

- 응용 프로그래머가 자체적으로 해결한다.

 

 

 

 

 

 

4. 교착 상태 예방

: 교착 상태 네 가지 조건 중 하나만 성립하지 않도록 한다.

 

1) 상호 배제 

- 결정성 (같은 입력값에 대해 항상 같은 결과가 나오는 것)이 위배될 가능성이 높다.

- 주변 장치의 특성 때문에 상호 배제를 피하기는 힘들다.

 

 

2) 점유와 대기

: 프로세스가 자원을 요청할 때에는 언제나 다른 자원을 점유하지 않도록 한다.

- 각 프로세스는 수행 전에 필요한 모든 자원을 요청하여 할당한다. (자원 활용의 효율성 감소)

- 프로세스가 자원을 가지고 있지 않은 상태에서만 자원 요청을 할 수 있도록 허용한다. (기아 상태 유발)

 

 

3) 비선점

: 선점을 허용한다.

- 구현 복잡

 

 

4) 순환 대기

: 모든 자원에 번호를 부여한다.

: 한 프로세스는 자신이 가진 자원보다 번호가 큰 것만 요청한다. 

- 새로운 자원이 시스템에 추가되면 프로그램과 시스템을 재구성해야 한다.

- 사용자가 손쉽게 응용 프로그램을 작성하는데 어려움이 있다.

 

 

 

 

 

 

5. 교착 상태 회피

: 교착 상태 예방보다 덜 엄격한 조건을 요구한다. 자원의 효율성도 향상된다.  비행기 테러를 방지하기 위해

 

- 예방 : 자원 사용 제약 조건을 정적으로 사전에 설정한다. (상대적으로 경직)   비행기를 안 타고 배를 탄다.

- 회피 : 자원 사용 제약 조건을 동적으로 실행중에 결정한다. (상대적으로 유연)   탑승자에 아랍 사람이 있는지 여부로 탑승여부 결정한다.

 

 

: 자원 요청 시, 자원할당으로 인해 교착상태 유발 가능성 검사한다.

 

- 유발 가능성이 전혀 없으면 안정 상태, 자원 할당

- 유발 가능성이 존재하면 불안정 상태, 자원 할당 연기

 

 

 

 

 

1) 안정 상태 vs 불안정 상태

시스템이 안전 상태에 있다는 것은 교착 상태가 유발되지 않았다는 것이다.

불안정 상태에서 안정 순열이 존재하지 않을 경우, 교착 상태 가능성이 존재한다.

 

교착상태 회피란?

시스템이 불안정 상태가 아님을 보장하는 것

 

 

 

2) 안정 상태

: 안정 순열의 존재를 의미한다.

 

 

안정 순열 <P1, P0, P2>

 

 

 

 

 

3) 불안정 상태

: 사용 가능한 자원 1개를 어느 프로세스에 할당해도 프로세스를 만족시킬 수 없다.

 

 

 

 

만약, P2가 자원 1개를 더 요구할 경우,

P1 종료 이후 잔여량이 4로 종료시킬 수 있는 프로세스가 없어 불안정 상태에 놓이게 된다.

 

 

 

 

 

 

 

 

 

 

6. 자원 할당 그래프 알고리즘을 활용해보자

 

예약 간선 : 프로세스가 자원을 요청할 것을 의미한다. 점선으로 표시한다.

예약 간선은 프로세스가 자원을 요청할 때에 요청 간선으로 변환된다.

자원은 시스템에서 미리 예약되어야 한다.

 

 

- 자원 할당 후에 사이클이 존재하면 불완전 상태이다.