[운영체제] 교착상태 개요와 처리방법

• Deadlock (교착상태)의 정의

- 두 개 이상의 프로세스가 필요한 자원을 기다리면서 무한정 중지된 상태

• Deadlock (교착상태)의 발생 원인

- 제한된 자원의 이용률을 높이고 시스템 효용성을 높이려 한 것의 부작용

• Deadlock의 발생 사례

1. 파일을 요청할 때

2. 다중 주변장치를 할당할 때

3. 디스크를 공유할 때 발생

4. 네트워크에서 발생

5. 전용장치를 할당할 때 발생

6. 스풀링 시스템에서 발생

• Deadlock 발생 필요충분조건

상호배제 + 점유와 대기 + 비선점 + 순환대기 

• Deadlock 처리기법

- Deadlock Prevention (예방)

- Deadlock Avoidance (회피)

- Deadlock Detection (탐지)

- Deadlock Recovery (복구)

1.  Deadlock Prevention

앞서 언급한 4가지 필요충분 조건이 발생하지 않도록 하는 방법이다.

-상호배제 

자원에 따라 다르므로 상호배제는 유지

ex) Read-only 경우 가능

write의 경우 상호배제를 해야함 (공유가 불가능)

-점유와 대기 방지

필요한 자원을 한꺼번에 요청하고 동시에 허용될때까지 프로세스 보류

-비선점 방지

강제로 자원을 회수하여 방지한다.

-순환대기 방지

모든 자원에 순서를 부여하여 순서 순으로만 자원을 할당한다.

2. Deadlock Avoidance

예방은 문제를 해결할 수는 있으나 장치의 비효율적 사용, 시서템 처리성능 저하의 문제 발생 -> 회피 대책을 사용

-프로세스 시작거부 : 

최대 요구량(현재 프로세스) + 최대요구량 > 최대값

-자원 할당의 거부 : 

자원 할당시 Deadlock 가능성이 높으면 할당 거부

* Deadlock Avoidance Algorithm

-자원 할당 그래프

-은행가알고리즘

2-1. Resource Allcoation Graph Algorithm

-단일 Instance

-Cycle이 존재하는가? -> Yes : 불안정상태

   No : 안정상태 (자원 할당 가능)

2-2. Banker's Algorithm

 -다중 Instance

 

3. Deadlock Detection

     교착상태가 발생하도록 허용하되 교착상태의 발생을 탐지하고 복구

-Detection Algorithm

-Recovery Algorithm

3-1. Detection Algorithm

- Multiple instances of resource

  Banker's algorithm의 변형 알고리즘을 활용한다.

*Available 

*Allocation

*Request ( != Need : Banker's algorithm과 차이점)

*Request[i,j]

- Single instance of resource

  wait-for graph (프로세스만 갖고 만든 그래프) 활용 알고리즘

-Cycle이 존재하는가? -> Yes : 불안정상태

            No : 안정상태(자원 할당 가능)

4. Deadlock Recovery

교착상태 복구 방법에는 프로세스 중단, 자원 선점 방법이 있다.

4-1. 프로세스 중지

 - 방법1 : 교착상태와 관련된 모든 프로세스를 중단

 - 방법2 : 교착상태가 해결될 때 까지 한 프로세스씩 중지

4-2. 자원 선점

 - 희생자의 선택

 - 이 때 희생자는 Rollback을 해줘야만 안전하다.

 - Starvation (기아 상태) : 특정 프로세스만 자원을 선점하지 못하는 상태

  : 해결책으로는 rollback 횟수를 측정하는 방법을 이용한다.