교착상태(Deadlock)

| 교착상태(Deadlock)

- 다중 프로그래밍 시스템에서 아무리 기다려도 결코 일어나지 않을 사건을 기다리고 있는 하나 또는 그 이상의 프로세스들이 있는 상태

- 둘 이상의 서로 다른 프로세스가 자신이 요구한 자원을 할당받아 점유하고 있으면서 상호간에 상대방 프로세스에 할당되어 있는 자원을 요구하는 경우에 발생

| 교착상태의 4가지 필요조건

1) 상호 배제(Mutual Exclusion)

   : 프로세스들이 자원을 배타적으로 점유하고 있어, 다른 프로세스들이 자원을 사용할 수 없게 만듦 (자원의 배타적인 제어권)

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

   : 최소한 하나의 자원을 점유하고 있는 프로세스가 존재해야하며, 이 프로세스는 다른 프로세스에 할당된 자원을 추가로 점유하기 위해 대기함

3) 비선점(Non-preemption)

   : 비선점 자원들은 그들을 점유하는 프로세스로부터 벗어나지 못한다.(도중에 해지될 수 없음) 점유한 프로세스만이 자원을 해재할 수 있다.

4) 환형 대기(Circular Wait)

   : 프로세스와 자원들이 원형을 이루며, 각 프로세스가 자신에게 할당된 자원을 가지면서 상대방 프로세스의 자원을 상호 요청하는 경우

| 교착상태 해결방법

1) 교착상태 예방(Prevention)

   - 교착상태를 유발하는 4가지 조건 중 최소한 하나가 성립하지 않도록 보장

   - 자원의 낭비가 심함

상호 배제 부정	여러 개의 프로세스가 공유 자원을 사용할 수 있도록 함
점유 대기 부정	프로세스가 실행되기 전 필요한 모든 자원을 할당
비선점 부정	자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 함
순환 대기 부정	자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구하도록 함

2) 교착상태 회피(Avoidance)

   - 교착상태가 발생하면 피하는 방법

   - 은행원 알고리즘(Banker's Algorithm)

> Dijkstra가 제안한 방법으로 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데에서 유래된 기법

> 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지를 사전에 검사하여 교착상태를 회피하는 기법

> 안정상태면 자원을 할당하고, 그렇지 않으면 다른 프로세스들이 자원을 해지할 때까지 대기함

3) 교착상태 탐지

   - 자원할당 그래프를 통해서 교착상태 탐지

   - 자원을 요청할 때마다 탐지알고리즘을 실행하면 오버헤드가 발생

4) 교착상태 회복

   - 교착상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제함으로써 회복하는 것

   - 프로세스 종료 방법

> 1. 교착 상태의 프로세스를 모두 중지

> 2. 교착 상태가 제거될 때까지 한 프로세스씩 중지

   - 자원 선점 방법

> 1. 교착 상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며, 해당 프로세스를 일시정지

> 2. 우선순위가 낮은 프로세스, 수행된 횟수가 적은 프로세스 등을 위주로 프로세스의 자원을 선점

[참고]

http://cs.sch.ac.kr/lecture/os/2013/7-OS-Dedlock.pdf 

http://developerhenrycho.tistory.com/20

http://includestdio.tistory.com/12

알기쉬운 정보보안기사&산업기사 / 탑스팟 / 조상진