교착상태(Deadlock)

교착상태(Deadlock)

- 두개 이상의 프로세스가 각각 어떤 자원을 소유하고 있으면서 다른 프로세스가 소유한 자원을 추가로 요청하여 기다리고 있는 상황

- 필요조건 

1. 상호배재 (Mutual Exclusion) : 한번에 오직 한 프로세스 만이 자원을 활용할 수 있다.

2. 점유와 대기 (Hold and wait) : 프로세스가 적어도 하나의 자원을 점유하면서 다른 프로세스가 점유하고 있는 자원을 추가로 얻기위해 대기한다.

3. 비선점 (No preemption) : 점유된 자원은 강제로 해체될 수 없고, 점유하고 있는 프로세스가 작업을 마치고 자원을 자발적으로 해체한다.

4. 순환대기 (Circular wait) : 대기하고 있는 프로세스 집합 {P0, P1, ... , Pn} 에서 P0은 P1이 점유한 자원을 대기하고, P1은 P2가 점유한 자원을 대기하고, Pn-1은 계속해서 Pn을 대기하며, Pn은 P0이 점유한 자원을 대기한다.

ex) 식사하는 철학자(Dining philosophers problem)

o 조건

1. 왼쪽 포크가 사용 가능해질 때까지 생각을 한다. 만약 사용 가능해지면 집어든다.

2. 오른쪽 포크가 사용 가능해질 때까지 생각을 한다. 만약 사용 가능해지면 집어든다.

3. 양쪽의 포크를 잡으면 정해진 시간만큼 식사를 한다.

4. 오른쪽 포크를 내려놓는다.

5. 왼쪽 포크를 내려놓는다.

6. 다시 1번으로 돌아간다.

교착상태 처리방법

- 교착상태의 처리 방법

o 교착상태 예방 (Deadlock Prevention)

1. 자원의 요청방법을 제약 : 락을 요청하는 시점 등을 제약을 검

자원의 이용률과 처리율이 낮아짐

2. 상호배제(mutual exclusion) 예방 : 동시 접근하는 자원에 대한 상호배제를 무시

현실적으로 불가능

3. 점유하며 대기(hold and wait) 예방 : 자원을 할당받지 않은 상태에서만 자원을 요청할 수 있음

자원의 이용률이 낮아지며 기아(starvation) 발생

4. 비선점(no preemtion) 예방 : 다른 자원 점유를 요청하면 현재 소유하고 있는 자원의 선점을 허용

자원 사용상태의 저장과 복원이 단순한 경우에만 가능 (ex) CPU 레지스터, 메모리 공간)

5. 순환대기(circulation) 예방 : 자원에 순번을 부여하고 순번의 오름차순에 의해서만 자원부여(사이클 예방)

가장 현실적인 방법

o 교착상태 회피 (Deadlock Avoidance)

1. 안전상태 (Safe state)

교착상태를 유발하지 않고 모든 프로세스들에게 자원을 할당해줄 수 있는 상황

안전상태인 경우만 자원 할당을 허락함(애초에 방지)

2. 교착상태 회피 알고리즘

미래에 발생할 가능성이 있는 자원을 요청 할 시 허락하지 않음

ex) 은행원(Banker) 알고리즘

프로세스가 시작하기 전에 필요한 자원의 종류와 최대 개수를 선언,

자원에 대한 할당 요청이 있을 때, 시스템의 안전여부를 검사,

자원 요청이 허락되지 않으면, 다른 프로그램이 끝날 때까지 대기

ex) P2의 R2에 대한 요청을 허락하지 않음

o 교착상태 탐지 (Deadlock Detection)

> 대기 그래프에서 사이클이 있는지를 검사

> 계속해서 탐지를 하면 탐지 알고리즘 자체가 오버헤드를 유발할 수 있기 때문에, 즉시 자원할당이 안될 때만 탐지 (비 효율적)

> 실질적으로 활용되지 않음

o 교착상태로부터 회복 (Deadlock Recovery)

> 프로세스를 제거하거나 자원을 선점, 어느 지점까지 프로세스가 활용되고 자원을 활용했는지 파악하기 어렵기때문에 현실적으로 불가능