Deadlock

Deadlock

시스템 자원에 대한 요구가 뒤엉킨 상태로 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴때 무한 대기에 빠지는 상황을 말한다.

데드락의 발생 조건

• 상호배제
  한번에 프로세스 하나만 해당 자원을 사용할 수 있다.
  사용중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다려야 한다.

• 점유대기
  자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재한다.

• 비선점
  이미 할당된 자원을 강제로 빼앗을 수 없다.

• 순환대기
  대기 프로세스의 집합이 순환형태로 자원을 대기하고 있어야한다.

데드락이 발생할 수 있는 경우

프로세스1과 프로세스2가 자원 1,2를 모두 얻어야한다고 가정한다.
t1 : 프로세스1이 자원1을 얻고, 프로세스2가 자원을 2를 얻는다.
t2 : 프로세스1은 자원2를 기다리고, 프로세스2는 자원1을 기다린다.
현재 서로 원하는 자원이 상대방에 할당되어 있어서 두 프로세스는 무한정 wait 상태에 빠진다 => 데드락

데드락 발생하는 경우

• 멀티 프로그래밍 환경에서 한정된 자원을 사용하려고 서로 경쟁하는 상황이 발생할 수 있다.
• 어떤 프로세스가 자원을 요청 했을때 그 시각에 그 자원을 사용할 수 없는 상황이 발생할 수 있는데 그때는 프로세스가 대기 상태로 들어가게 된다.
• 대기 상태로 들어간 프로세스들이 실행 상태로 변경될 수 없을 때 이러한 상황을 교착 상태라 한다.

데드락 해결법

-예방(prevention)
교착 상태 발생 조건 중 하나를 제거하면서 해결한다.(자원 낭비 심함)

• 상호배제 부정 : 여러 프로세스가 공유 자원 사용
• 점유대기 부정 : 프로세스 실행전 모든 자원을 할당
• 비선점 부정 : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납
• 순환대기 부정 : 자원에 고유번호 할당 후 순서대로 자원 요구

-회피(avoidance)
교착 상태 발생 시 피해나가는 방법

• 은행원 알고리즘
  • 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래했다.
  • 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피한다.
  • 안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기한다.

시스템 자원은 A : 10, B : 5, C : 7개의 자원이 있다.
Need(Max-Allocation) 값은
A B C
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1
이다.
Need 값이 Available 값보다 작거나 같아야지 자원할당이 가능하다.
1. P0 => 할당 안됨
2. P1 => (1,2,2) <= (3,3,2) 할당 됨 => 자원 반환 => Available (5,3,2)
3. P2 => 할당 안됨
4. P3 => (0,1,1) <= (5,3,2) 할당 됨 => 자원 반환 => Available (6,4,3)
5. P4 => (4,3,1) <= (6,4,3) 할당 됨 => 자원 반환 => Available (6,4,5)
6. P2 => (6,0,0) <= (6,4,5) 할당 됨 => 자원 반환 => Available (10,4,7)
7. P0 => (7,4,3) <= (10,4,7) 할당 됨 => 자원 반환 => Available (10,5,7)

P1 -> P3 -> P4 -> P2 -> P0 일때 안전하다.

교착 상태가 되도록 허용한 다음 회복시키는 방법이다.
-탐지(detection)
자원 할당 그래프를 통해 교착 상태를 탐지한다.
지원 요청시, 탐지 알고리즘을 실행시켜 그에 대한 오버헤드를 발생한다.

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

• 프로세스 종료 방법

  • 교착 상태의 프로세스를 모두 중지한다.
  • 교착 상태가 제거될 때까지 하나씩 프로세스 중지한다.

• 자원 선점 방법

  • 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당한다.(해당 프로세스 일시정지 시킴)
  • 우선 순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 자원 선점한다.