Deadlock

시스템 모델

→ 컴퓨터 시스템은 여러 프로세스와 CPU를 포함하여 여러 자원들을 사용하면서 운용된다.

 

1. 자원 (resources) : 메모리공간, CPU cycles, files, I/O 장치, 둘이상의 CPU에서 CPU 등.

2. 자원의 이용 절차

• 요청(Request) : 자원을 요청하여 즉시 할당받지 못하면 대기한다.

• 사용(Use) : 프로세스가 자원을 운용한다.

• 해제(Release) : 프로세스가 자원을 반환한다.

 

Deadlock Charcaterization

1. 교착상태의 개념

• 대기중인 프로세스가 자신의 상태를 바꾸지 못하는 경우 : 한 집합내의 프로세스에 의해 일어날 수 있는 어떤 사건(event)을 기다리고 있는 그 집합내의 모든 프로세스는 교착상태에 있다고 함

• 교착상태는 시스템의 상황

• 시스템 내에 있는 프로세스들의 상태 : 서로의 resource 요구관계 때문에 맞물려서 아무도 자원에 대한 CPU 제어권을 얻을 수 없는 상태

• 교착상태는 system 내에서 빈번히 일어나므로 이를 해결하는 mechanism 이 필요

 

2. 필요조건 (교착상태가 발생하기 위한...)

• 상호배제(Mutual Exclusion) 조건

- 프로세스들은 자신이 필요로 하는 자원에 대해 배타적인 사용을 요구

- 적어도 하나의 자원은 반드시 비공유되는(nonsharable) 상태에서 점유

• 점유와 대기(Hold & Wait) 조건

- 프로세스가 적어도 하나의 자원을 점유하고, 다른 프로세스에 의해 점유된 다른 자원을 요구하고 할당받기를 기다림

• 비선점(No preemption) 조건

- 자원은 선점될 수 없음, 자원은 점유한 프로세스가 작업을 종료한 뒤에 해제된다.

• 순환대기(Circular Wait) 조건

- 프로세스들이 순환을 이루어서 존재하여야 하며, 이를 구성하는 각 프로세스는 순환내의 이전 프로세스(predecessor)가 요청하는 자원을 점유하고 다음 프로세스(successor)가 점유하고 있는 자원을 요구

 

3. 자원 할당 그래프 - 교착상태에 빠지지 않도록 하는 설계를 위해 작성한다.

 a) 교착상태에 빠진 경우  

 

b) 작업완료 순서 : P3 → P2 → P1

 

 

 

3. 교착상태 해결을 위한 방법

• 교착상태가 절대 일어날 수 없도록 시스템을 설계

• 운영체제 시스템의 설계단계에서 방지(prevention)

• 운영체제가 시스템이 교착상태로 들어가지 못하도록 회피(avoidance)

• 교착상태가 일어날 수 있도록 시스템을 설계하고 계속 시스템의 상태를 감시

 

4. 교착상태 방지

• 교착상태의 네 가지 조건이 동시에 발생할 수 없도록 적어도 하나의 조건을 만족시키지 않도록 운영체제를 설계하는 것

• 교착상태 방지의 문제점 : 자원의 사용률과 시스템의 처리율을 저하시키는 문제

 

1) 상호배제(Mutual Exclusion) 조건

• 만일 시스템의 모든 자원이 공유 가능한 자원이라면 절대 교착상태가 일어나지 않음

• 그러나 모든 시스템에는 비공유 자원이 존재하므로 상호배제의 조건은 반드시 지켜져야만 하고, 교착상태 방지의 방법에서 이 조건을 이용하여 교착상태를 방지할 수는 없음

 

2) 점유와 대기(Hold & Wait) 조건

• 점유와 대기가 시스템에서 일어나지 않도록 하는 방법

- 프로세스가 요청을 할 때에, 자신이 점유하고 있는 자원이 없도록 하는 것

- 프로세스가 자신의 작업에 필요한 모든 자원을 확보할 수 있을 때에만 작업을 시작

• 위 방법들의 문제점

- 자원의 활용도 및 시스템의 프로세스 처리율이 현저히 떨어짐

- 기아(starvation)를 초래

- 자원을 확보하지 못한 프로세스는 언제까지 대기(wait)상태에 머물러야 하는지 보장을 받지 못함

 

3) 비선점(No Preemption) 조건

• 선점을 위한 두 가지의 방법

• 자원을 요청한 프로세스의 자원을 선점 : 어떤 자원을 점유하고 있는 프로세스가 또 다른 자원을 할당받기를 요청하였고, 만일 시스템에 이 자원이 가용하지 않을 경우, 운영체제가 강제로 이 프로세스가 점유했던 자원을 선점

• 대기중인 프로세스의 자원을 선점 : 어떤 프로세스가 가용하지 않은 자원을 요청하였을 때에 운영체제가 다른 대기중인 프로세스들이 점유하고 있는 자원 목록을 본 후 만약 요청한 자원이 있다면 이를 선점

 

4) 순환대기(Circular Wait) 조건

• 운영체제가 시스템의 자원을 할당하려고 할 때 일정 순서를 지키며 할당

• 모든 자원의 종류에 순번을 할당하고, 프로세스가 자원의 요청을 할 때 순번을 지키도록 함

• 점유한 자원보다 높은 순번을 가진 자원을 할당받으려고 할 때, 요청하는 자원보다 낮은 순번을 갖는 자원을 모두 반환하고 재요청

• 자원의 활용도 향상, 자원의 효율적 사용 저해

 

5. 교착상태 회피

• 자원들에 대한 요청이 들어올 때마다, 현재 사용 가능한 자원들, 각 프로세스에 할당된 자원들, 그리고 할당되었으나 반환될 자원들을 검사하여, 지금 들어온 요청을 허가하고도 교착상태에 빠지지 않을 것인가를 확인한 후에 결정한다.

• 부수적인 정보의 유지와 교착상태를 피하기 위해 수행되는 알고리즘은 운영체제에 부담

 

5.1 Safe State

- 각각 프로세스를 위해 자원을 안전한 상태에 배치하면 교착상태를 피할수 있다.

 

6. 교착상태 탐지

• 시스템 내부에 교착상태가 발생할 수도 있으며, 이런 경우의 운영체제의 임무는 이를 탐지하고 해결하는 것

• 교착상태 탐지의 문제점 : 운영체제는 탐지를 위하여 실시간으로 교착상태 탐지 알고리즘을 수행, 부수적인 시스템과 프로세스의 정보를 유지, 만일 교착상태가 존재한다면 이를 해결하는 과정에서 프로세스와 자원의 낭비가 요구

 

7. 교착상태 회복

• 시스템 내부에 교착상태가 존재함을 탐지 : 이 교착상태는 회복되어야 함

• 따라서 교착상태의 탐지와 회복은 함께 사용되는 해결방법으로 생각

• 교착 상태 회복 알고리즘 : 순환상태가 확인되면 순환상태가 없어질 때까지 프로세스를 단계적으로 제거

 

8. 복합적인 접근 방법

• 기본적인 방식들(회피, 예방, 탐지) 만으로는 운영체제에서 발생하는 전체 자원 할당문제를 취급하는 것은 적절하지 못하므로 이들을 복합적으로 결합하여 시스템의 자원 종류마다 최적의 접근 방식을 채택하는 것이 좋다.