[DeadLock] 데드락 ( 교착 상태 )

DEADLOCK ( 교착 상태 )

2개이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있는 상태로 결과적으로 아무것도 완료되지 못하는 상태를
의미

 

1 교착상태의 조건(교착 상태가 발생하는 네가지 조건, 하나라도 해당 안되면 교착상태 해제)

1. 상호배제(Mutual exclusion)
한 번에 오직 한 개의 작업만 자원에 접근할 수 있다.

자원을 점유하고 있는 프로세스나 스레드가 자원을 해제해야 다른 프로세스나 스레드가 해당 자원에 접근할 수 있습니다.

2. 점유대기(Hold and wait)
프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.

이로 인해 여러 프로세스나 스레드가 필요한 자원을 점유한 채로 대기하며, 다른 프로세스나 스레드가 해당 자원을 사용할 수 없는 상태가 됩니다.

3. 비선점(No preemption)
프로세스가 어떤 자원의 사용을 끝낼 때 까지 그 자원을 뺏을 수 없다.

4. 순환대기(Circular wait)
각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.

2 교착 상태 예방 ( 교착 상태 발생 조건 중 하나를 제거, 자원 낭비 심함)

1. 상호배제 부정

교착상태는 2개 이상의 프로세스가 공유가능한 자원을 사용할 때 발생하는 것이므로 자원을 공유하지 않는 조건, 
즉 한번에 여러개의 프로세스가 공유자원을 사용할 수 있도록 합니다.

2. 점유대기 부정

한 프로세스에 수행되기 전에 모든 자원을 할당시키고 나서 점유하지 않을 때에는 다른 프로세스가 자원을 요구하도록 하는 방법으로 자원 과다 사용으로 인한 효율성, 프로세스가 요구하는 자원을 파악하는 데에 대한 비용, 자원에 대한 내용을 저장 및 복원하기 위한 비용, 기아 상태, 무한대기 등의 문제점이 있다.

3. 비선점 부정

비선점 프로세스에 대해 선점 가능한 프로토콜을 만들어 준다.

4. 순환대기 부정

자원에 고유한 번호를 할당하여 순서대로 자원을 요구한다.

3 교착 상태 회피 ( 교착 상태 발생 시 피하는 방법 )

1. 자원할당 그래프 알고리즘(Resource Allocation Graph Algorithm)

자원이 하나일 때 사용하는 알고리즘으로 자원 할당 그래프에 요청 간선과 할당 간선에 추가하여, 예약 간선이라는 새로운 유형의 간선을 도입합니다. 
자원할당 그래프의 사이클이 존재하는지 확인하여 사이클이 존재한다면, 자원 유형에 하나의 사례만 있으면 교착상태, 자원 유형에 여러 사례가 있으면 교착상태 가능성으로 판단합니다.

2. 은행원 알고리즘(Banker's algorithm)

은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데 유리한 기법입니다. 
프로세스가 자원을 요구하는 경우에 시스템은 자원을 할당한 이후 안정상태로 있는지 사전에 검사하여 교착을 회피합니다. 안정적인 상태에 있는 경우 자원을 할당하고 그렇지 않은 경우 다른 작업이 자원을 해지할 때 까지 대기합니다.

4 교착 상태 탐지 & 회복

1. 탐지

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

자원 요청 시, 탐지 알고리즘을 실행시켜 그에 대한 오버헤드 발생함

2. 회복

교착 상태 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법

1. 프로세스 종료 방법
  * 교착 상태의 프로세스를 모두 중지
  * 교착 상태가 제거될 때까지 하나씩 프로세스 중지
2. 자원 선점 방법
  * 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당 (해당 프로세스 일시정지 시킴)
  * 우선 순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점