Deadlock

Deadklock이란?

• Process가 자원을 얻지 못해 다음 처리를 못하는 상태

  • ex) 서로 원하는 리소스가 상대방에게 할당되어 있어서 두 process가 무한정 기다리게 되는 상태

• 멀티프로그래밍 환경에서 한정된 자원을 사용하려고 경쟁하는 상황이 발생 할 수 있다

  • 어떤 process가 자원을 요청했을 때 그 시각에 그 자원을 사용할 수 없는 상황이 발생할 수 있고, 그 때는 process가 대기 상태 로 들어가게 된다

  • 대기 상태로 들어간 process들이 실행 상태로 변경될 수 없을 때를 교착상태라고 한다

DeadLock 발생 조건

한 시스템 내에서 다음의 네가지 조건이 동시에 성립할 때 발생한다

1. 상호 배제

   • 자원은 한 번에 한 프로세스만 사용할 수 있어야 한다

2. 점유 대기

   • 최소한 하나의 자원을 점유하고 있으면서, 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다

3. 비선점

   • 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빠앗을 수 없어야 한다

4. 순환 대기

   • 프로세스의 집합 {P0, P1, ,…Pn}에서 P0는 P1이 점유한 자원을 대기하고 P1은 P2가 점유한 자원을 대기하고 P2…Pn-1은 Pn이 점유한 자원을 대기하며 Pn은 P0가 점유한 자원을 요구해야 한다

Dead Lock 탐지 및 회복

• 교착 대상 탐지

  • 자원 할댕 그래프를 통해 교착 상태를 탐지할 수 있다

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

• 교착 상태로부터 회복

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

  • 프로세스 종료 방법

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

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

  • 자원을 선점하는 방법

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

    2. 우선 순위 가 낮은 프로세스, 수행 횟수가 적은 프로세스를 위주로 자원을 선점한다