CS/Operating System

[전공생이 설명하는 OS] 동기화 - (5) Deadlock

동현 유 2022. 5. 31. 08:20

Review

  지금까지 race condition 이 발생하는 이유와, 이를 해결하기 위해 다양한 동기화 기법이 필요하다는 점을 설명했다. 특히 이전 포스팅에서는 할당 가능한 자원의 개수를 (0~MAX)개로 제한하는 web server request buffer 를 살펴보면서 `생산자-소비자 문제`(bounded buffer problem) 를 해결해보았다. 

 이번에는 동기화로 인해 발생할 수 있는 심각한 문제인 교착상태(deadlock)을 알아보도록 한다.

1. Deadlock 이란?

프로세스 P1 과 P2 는 데드락 상태에 빠질 수 있다.

  다수의 스레드 또는 프로세스가 서로 깨워주기를 기다리면서, 모두 대기하고 있는 상태를 데드락이라고 한다. 데드락은 실제로 자주 발생하는 문제는 아니다. 하지만 한번 발생하면 서비스에 심각한 장애를 발생시키고, 또 그 원인을 제대로 파악하기가 매우 힘들다. (모든 자원 간의 의존관계를 파악해야한다.)

2. Resource

  여태까지 동기화에 대해 설명할 때에는 여러 실행 흐름을 제어하기 위한 관점에서 바라보았다면, 데드락에서는 자원의 분배 관점에서 바라보는 것이 더 유익할 듯하다. 데드락은 Non-preemptable 한 자원에 대해서 발생할 수 있다. 즉 한 프로세스가 어떤 자원을 점유하고 있을 때, 다른 프로세스가 그것을 강제로 빼앗을 수 없는 자원의 종류를 말한다. 크게 재사용 가능한 자원과 일회용 자원으로 나눌 수 있다. 두 자원 모두 non-preemptable 하기 때문에 데드락이 발생할 수 있다.

  • Reusable Resource 
    - 한 프로세스가 사용한다고 해서 사라지지 않는 자원. 한번에 한 프로세스만 사용가능한 경우가 많다.
    - 보통 request -> lock -> use -> unlock 의 과정을 거친다.
    - cpu, memory, file, database, etc.
  • Consumable Resource
    - 한번 사용하면 사라지는 일회성 자원.
    - interrupts, signals, messages, IO buffers, etc.

3. Resource Allocation Graph

  Resource Allocation Graph는 데드락이 발생할 수 있는 상황인지 파악할 수 있도록, 프로세스와 자원 사이의 관계를 도식화하는 방법이다. 프로세스는 원, 공유자원은 사각형으로 표현한다. 사각형 내부에 그려진 검은 점들은 자원의 개수를 의미할 수 있고 부분적으로 떼어줄 수 있다는 뜻이다.(생산자-소비자 문제에서의 버퍼, 할당가능한 메모리 크기 등). 화살표의 방향은 의존관계를 나타낸다. 

  이 그래프에서 순환 의존 관계가 발생하게 되면 데드락이 발생할 수 있다. 그림 (c)는 데드락이 발생한 상황이다. 그림 (d)는 데드락 상황은 아니지만, 추후에 얼마든지 데드락이 발생할 수 있다.

 

4. 데드락 발생의 4가지 필요조건

  위에서 설명한 것을 토대로 교착상태가 발생하는 4가지 조건을 정리하면 다음과 같다. 다음 중 하나라도 만족하지 않으면 교착상태는 발생하지 않는다.

  1. 공유자원이 non-preemptive 한다. 즉, 빼앗을 수 없다.
  2. 공유자원에 대해 상호배제가 이루어진다.
  3. 프로세스가 한 자원을 잡고 있으면서 다른 자원을 요청하는 Hold & Wait 상태가 발생한다.
  4. 순환 대기가 발생한다.

5. 교착상태를 해결하는 4가지 방법

  1. Deadlock Prevention
    - 4가지 조건을 모두 만족시키지 못하게 하는 방법.
    - resource 의 utilization 이 낮아지고, concurrency 가 저하된다.
  2. Deadlock Avoidence
    - 자원 요청이 있을 때, deadlock 이 발생가능하면 거절하고, 그렇지 않으면 할당하는 방법
    - 시스템의 모든 자원을 파악해야하고, 프로세스가 어떤 자원을 얼만큼 필요로하는지 미리 파악해야한다. 
  3. Deadlock Detection & Recovery
    - deadlock 이 발생했는지를 주기적으로 확인한다. 발생한 경우 자원을 회수하거나 프로세스를 종료하는 등의 조치를 취한다.
    - 교착상태는 매우 드물게 발생하기 때문에 overhead 가 크다.
  4. Ignore
    - 매우 드물게 발생한다 -> 무시하는게 오히려 효율성이 좋을수도 있다.

 

  다음 포스팅에서는 대표적인 데드락 상황인 식사하는 철학자 문제를 알아보고, 그에 따른 Prevention 과 Avoidence 방법을 실제 코드를 작성하면서 알아보도록 한다.