Today Sulim Learned

Chapter 7. Deadlock

26 Jan 2022 | 운영체제 CS

KOCW에 공개된 이화여대 반효경 교수님 운영체제 강의 수강 후 정리한 내용입니다.

1. Deadlock (교착 상태)

  • Deadlock: 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
  • Resource (자원)
    • 하드웨어, 소프트웨어 등을 포함하는 개념
      • ex) IO device, CPU cycle, memory space, semaphore 등
    • 프로세스가 자원을 사용하는 절차: Request, Allocate, Use, Release

Deadlock 발생의 4가지 조건

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

Deadlock 발생 확인 방법

Resource-Allocation Graph (자원 할당 그래프)

resourceallocation

  • 동그라미: 프로세스 / 사각형: 자원 / 사각형 안의 점: 자원의 수
  • 화살표 종류
    • 자원에서 프로세스로 나가는 화살표: 프로세스가 해당 자원을 가지고 있는 상태
    • 프로세스에서 자원으로 나가는 화살표: 프로세스가 해당 자원을 요청했지만 아직 획득하지는 못한 상태
  • 그래프를 봤을 때, cycle이 없으면 deadlock이 아님
  • 그래프에 사이클이 있으면.
    • 자원당 인스턴스가 하나 밖에 없다면 (사각형 안의 점이 한 개인 경우), deadlock 발생
    • 자원당 인스턴스가 여러 개 있는 경우, deadlock일수도 있고 아닐 수도 있음

graph

  • 왼쪽 그래프의 경우 deadlock 발생
    • 자원의 인스턴스가 2개가 있지만, 사이클이 2개가 만들어져 더 이상의 진행이 불가능
    • R2의 경우 하나는 P1, 다른 하나는 P2에 있기 때문에, P3가 R2를 요청했을 때 할당할 수 있는 자원이 없기 때문
  • 오른쪽 그래프의 경우, 사이클이 있지만 deadlock 발생하지 않음
    • P2와 P4는 deadlock과 연관되어 있지 않은 프로세스. P4가 R2의 자원을 쓴 후 반납하면 P3은 R2의 자원을 쓸 수 있기 때문에 deadlock이 발생하지 않음

2. Deadlock의 처리 방법

1. Deadlock Prevention

  • 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
  • Utilization 저하, throughput 감소, starvation 문제 발생

Mutual Exclusion: 공유해서는 안되는 자원의 경우 반드시 성립해야 함

Hold and Wait

  • 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 함
  • 방법 1) 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
    • wait할 일이 발생하지 않기 때문에 deadlock이 발생하지 않음
    • 자원의 비효율성이 생김
  • 방법 2) 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
    • 자원을 자진해서 반납해 문제를 해결

No preemption

  • process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
  • 모든 필요한 자원을 얻을 수 있들 때 그 프로세스는 다시 시작됨
  • State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용 (CPU, memory)

Circular Wait

  • 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
  • ex) 순서가 3인 자원 R_i를 보유 중인 프로세스가 순서가 1인 자원 R_j을 할당받기 위해서는 우선 R_i를 release해야 함

2. Deadlock Avoidance

  • 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당
    • 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
  • 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법
  • 항상 safe state를 유지

2가지 경우의 avoidance 알고리즘

  • 자원당 인스턴스가 하나인 경우: Resource Allocation Graph algorithm 사용
  • 자원당 인스턴스가 여러 개인 경우: Banker’s algorithm 사용

Resource Allocation Graph algorithm

resourceallocationgraphalgorithm

  • 점선 화살표: 프로세스로부터 자원으로 가는 화살표만 있음. 프로세스가 적어도 한 번은 이 자원을 요청할 수 있다는 의미
    • 요청을 하게 되면 실선으로 바뀜
  • 현재 그림은 deadlock이 아님. 하지만 P1이 R2에게 자원을 요청할 경우 deadlock이 발생
  • 최악을 가정하는 알고리즘이기 때문에 deadlock이 발생할 확률이 있는 경우(점선 화살표까지 포함해서 사이클이 완성될 경우) 자원을 할당하지 않음

Banker’s algorithm

bankers

  • Allocation: 할당된 자원의 개수 / Max: 최대로 자원을 사용할 때의 자원 개수 / Available: 현재 사용 가능한 자원의 개수
  • Need: 추가로 할당 가능한 자원의 개수 (Max - Allocation)
  • Banker’s algorithm은 항상 최대 요청을 할 것이라고 가정하고, 최대 요청이 현재 가용 자원을 가지고 충족이 되는지를 확인
    • 충족이 될 경우, 어떤 요청이든 받아들임
    • 충족이 되지 않을 경우, 요청을 받아들이지 않음
  • Banker’s algorithm은 프로세스가 자원 요청을 했을 때 받아들일지 받아들이지 않을지를 결정하는 역할을 함
  • sequence <P1, P3, P4, P2, P0>가 존재하므로 시스템은 safe state
    • 각 프로세스의 최대 요청 자원을 모두 충족할 수 있는 sequence가 존재하면 이 상황은 safe한 상태로 절대 deadlock이 발생하지 않음
  • 자원이 남아있어도 최악의 상황 때문에 자원을 할당하지 않으므로 비효율적

3. Deadlock Detection and recovery

  • Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover

  • 자원당 하나의 인스턴스를 가지는 경우: 자원할당 그래프에서의 cycle이 곧 deadlock을 의미
  • 자원당 인스턴스가 여러 개인 경우: Banker’s algorithm과 유사한 방법 활용

Wait-for graph

deadlockdetection

  • 자원당 인스턴스가 하나인 경우 사용. 자원 할당 그래프를 변형시킨 그래프
  • 프로세스만으로 node를 구성
    • P_i가 가지고 있는 자원을 P_k가 기다리는 경우 P_k -> P_i
  • wait-for graph에 사이클이 있는지를 주기적으로 조사 (O(n^2))

자원당 인스턴스가 여러 개인 경우

deadlockdetection_1

  • Request: 추가 요청 가능량이 아닌 현재 실제로 요청한 자원량을 나타냄
  • 만약 예시에서 P2가 C를 요청한다면 Deadlock 발생
  • 가용 자원이 몇 개 있는지를 확인 후, 가용 자원으로 처리 가능한 프로세스가 있는지 확인. 자원을 요청하지 않은 프로세스에게 할당되어 있는 자원을 가용 자원으로 합쳐 놓고, 합친 가용 자원으로 처리 가능한 프로세스가 있는지 확인해 나감

Recovery

  1. Rrocess termination
    • deadlock과 관련된 모든 프로세스 사살
    • deadlock이 없어질 때까지 deadlock에 연류된 프로세스를 하나씩 죽임
  2. Resource Preemption
    • deadlock에 연류된 프로세스에게서 자원을 뺏음
    • 비용을 최소화할 희생양 선정 후 그 프로세스로부터 자원을 뺏어 deadlock을 없앤 후, safe state로 rollback해 process를 restart
      • deadlock을 없앴지만, 같은 패턴으로 다시 문제 발생 가능 (Starvation 문제 발생 가능)
      • 동일한 프로세스가 계속해서 희생양으로 선정되는 경우
      • cost factor에 rollback 횟수도 같이 고려

4. Deadlock Ignorance

  • Deadlock을 시스템이 책임지지 않음
  • 만약, 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 등의 방법으로 대처

현재는 4번 방법 채택!

deadlock은 빈번하게 발생하는 event가 아니고, deadlock에 대한 조치 자체가 더 큰 오버헤드일 수 있기 때문에 비효율적이라 생각. 따라서 deadlock이 발생하면 사용자가 deadlock을 처리하는 방법을 채택함

Chapter 7 끝!!!

게시물에 사용한 사진은 강의 내용을 캡쳐한 것입니다.

Related Posts