[운영체제] 교착상태(Deadlock)

교착상태(deadlock)

위의 사진처럼 자신의 길을 점유하고 있으면서 아무도 양보 안 한다면 계속 이렇게 막힌 상태가 유지되는 상태

 

Deadlock

• 일련의 프로세스들이 서로가 가진 자원을 기다리며 Block된 상태

Resource(자원)

• 하드웨어, 소프트웨어 등을 포함하는 개념
• I/O device,CPU cycle, memory space, semaphore 등
• 프로세스가 자원을 사용하는 절차
  • Request(요청하는 절차), Allocate(점유), Use(사용), Release (반납)

 

 

Deadlock 예시

P0은 P(A)를 점유하고 P1은 P(B)를 점유하고 있을 때에 P0이 P(B)를 할 때 P1이 가지고 있고 P1이 P(A)를 하려 할 때 P0이 가지고 있어 서로 못 가져가는 상황

 

 

Deadlock 발생의 4가지 조건

• Mutual exclusion(상호 배제)
  • 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
  • 얻었다면 독점적으로 사용할 수 있다.
• No preemption (비선점)
  • 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
• Hold and wait( 보유대기)
  • 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음.
• Circular wait(순환 대기)
  
  • 자원을 기다리는 프로세스간에 사이클이 형성되어야함
  • 프로세스 P0,P1,....Pn이 있을 때
  • P0은 P1이 가진 자원을 기다림
  • P1은P2가 가진 자원을 기다림
  • Pn-1은 Pn이 가진 자원을 기다림 

 

Deadlock의 처리방법

• Deadlock Prevention
  • 자원 할당 시 Deadlock 의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
• Deadlock Avoidance
  • 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당
  • 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
• Deadlock Detection and recovery
  • Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견식 recover
• Deadlock ignorance
  • Deadlock을 시스템이 책임지지 않음
  • 대부분 OS가 채택

위에 2개가 미연에 방지하는 방식 밑에 두개는 발생하고난 뒤 처리하는 방식

Deadlock이 빈번하게 발생하지 않기 때문에 그에 대비해놓는 것은 너무많은 오버헤드가 발생하여 대부분이 무시하는 것을 채택하고 있습니다.

 

Deadlock Prevetion

4가지 필요 조건중 하나를 만족되지 않도록 하는방식

Hold and wait:자진해서 반납함으로 문제를 해결

No Preemption:자원을 선점할 수 있게 설정하여 해결

• 아무렇게나 자원을 빼앗아 오면 문제가 생기지만, CPU와 memory는 쉽게 save 하고 restore를 할 수 있어 허용합니다.

Circular Wait:자원에 순서를 할당하여 해결

• 획득 순서를 걸어놓아서 순서에 따라 자원을 얻도록 하므로 해결

이 방법 들은 원천적으로 Deadlock를 해결할 순 있지만 생기지도 않을 데드락을 생각해서 제약조건을 많이 달아놓으므로 비효율적입니다.

Deadlock Avoidance

평생 사용할 최대의 자원들을 선언하여 만약 데드락의 위험 생이 생길 것 같다면 자원을 내주지 않는 방식

예시) Banker's Algorithm

사진에 대한 설명은 각각 프로세스에 대하여 현재 할당 되어있는 값(Allocation) 

프로세스가 최대로 요청할 수 있는 값(Max)

현재 사용 가능한 자원의 수( Available) -> P0~P4까지 Allocation 더한 값을 총 자원의수(resource)에서 뺀값 

프로세스에서 최대로 요청할 수 있는 자원의 수 (Max - Allocation) 

여기서 어떻게 데드락을 판단하는지는.. 

만약 P1이 자원 B에대해서 2개를 요청한다고 가정한다면 현재 여유가 있어서 바로 줄 수 있지만 그거를판단하기 이전에

이 프로세스가 최대로 요청할 수 있는 자원의 수부터 보게 됩니다. 그리하여 A 1개 B 2개 C 2개 이기 때문에 이용가능한 자원의 수보다 작으므로 P1에게 자원을 할당 가능하게 됩니다.

하지만 P0의 경우 C 1개를 요청하더라도 P0의 프로세스가 최대로 요청할 수 있는 자원의 수를 보게되면 A 7 개 B 4개 C 3개 임으로 P0에게는 Deadlock이 발생할 수도 있다고 판단하여 내주지 않습니다.

Banker's 알고리즘의 경우 최악의 경우를 예상해서 줄지 안줄지 판단하는 알고리즘입니다.

DeadlockDetection and Recovery

먼저 시스템이 데드락 예방이나 회피 법을 사용하지 않았을 때, 데드락이 발생할 수 있으니 여기에서 회복하기 위해 데드락을 탐지하고, 회복하는 알고리즘을 사용합니다.

• 탐지 기법
  • Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 여부를 탐색합니다. 즉, 은행원 알고리즘에서 했던 방식과 유사하게 현재 시스템의 자원 할당 상태를 가지고 파악합니다.
  • 이 외에도 자원 할당 그래프를 통해 탐지하는 방법도 있습니다.
• 회복 기법
  • 단순히 프로세스를 1개 이상 중단시키기
    • 교착 상태에 빠진 모든 프로세스를 중단시키는 방법 : 계속 연산중이던 프로세스들도 모두 일시에 중단되어 부분 결과가 폐기될 수 있는 부작용이 발생할 수 있음
    • 프로세스를 하나씩 중단시킬 때마다 탐지 알고리즘으로 데드락을 탐지하면서 회복시키는 방법 : 매번 탐지 알고리즘을 호출 및 수행해야 하므로 부담이 되는 작업일 수 있음
  • 자원 선점하기
    • 프로세스에 할당된 자원을 선점해서, 교착 상태를 해결할 때까지 그 자원을 다른 프로세스에 할당해 주는 방법
• 데드락을 탐지 기법을 통해 발견했다면, 순환 대기에서 벗어나 데드락으로부터 회복하기 위한 방법을 사용합니다.

Deadlock Igonorace

• 아무런 조치를 취하지 않음
• 매우 드물게 발생하는 Deadlock에 대한 조치는 오히려 더 많은 오버헤드 발생
• 대부분의 OS에서 채택