poeun 🔅

Original Artwork © Henri Matisse (1869 ~ 1954), Le Cheval L’Ecuyere et le Clown, 1947, 64.6 x 42.5, Centre Georges-Pompidou

개인 저장공간입니다.
Since 2021.10

3 분 소요

본 글은 (KOCW) 운영체제, 이화여자대학교 반효경 교수님의 강의를 듣고 내용을 요약 및 정리했습니다.
개인 공부에 목적이 있으며, 자세한 사항은 http://www.kocw.or.kr/home/cview.do?mty=p&kemId=1046323에 참고하시면 됩니다.

Chapter 7.
- Deadlocks 1 - 40분
- Deadlocks 2 - 37분

image



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



Deadlock 발생의 4가지 조건

  1. Mutual exclusion (상호 배제)
    • 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
  2. No preemption (비선점)
    • 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음
  3. Hold and wait (보유대기)
    • 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
  4. Circular wait (순환대기)
    • 자원을 기다리는 프로세스간에 사이클이 형성되어야 함
    • 프로세스 $P_0, P_1, …, P_n$이 있을 때
      • $P_0$은 $P_1$이 가진 자원을 기다림
      • $P_1$은 $P_2$이 가진 자원을 기다림
      • $P_{n-1}$은 $P_n$이 가진 자원을 기다림
      • $P_n$은 $P_0$이 가진 자원을 기다림



Resource-Allocation Graph 1

  • 자원할당그래프



Resource-Allocation Graph 2

  • 점은 자원
  • 그래프에 cycle이 없으면 deadlock이 아니다.
  • 그래프에 cycle이 있으면
    • 자원당 인스턴스가 하나씩 있으면 데드락을 의미
    • 자원의 인스턴스가 여러개 있을 때, 데드락일 수있고 아닐 수 있다.



Deadlock의 처리 방법

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



Deadlock Prevention

  • Mutual Exclusion
    • 공유해서는 안되는 자원의 경우 반드시 성립해야 함
  • Hold and Wait
    • 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
    • 방법 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방버
    • 방법 2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
  • No Preemption
    • process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
    • 모든 피요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
    • State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용 (CPU, memory)
  • Circular Wait
    • 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
    • ex. 순서가 3인 자원 $R_i$를 보유 중인 프로세스가 순서가 1인 자원 $R_j$을 할당받기 위해서는 우선 $R_i$를 release해야 한다.

-> Utilization 저하, throughput 감소, starvation 문제



Deadlock Avoidance

  • Deadlock avoidance
    • 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로부터 안전(safe)한지를 동적으로 조사해서 안전한 경우에만 할당
    • 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법임
  • safe state
    • 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
  • safe sequence
    • 프로세스의 sequence $<P_1, P_2, …, P_n>$이 safe 하려면 $P_i(1\le i \le n)$의 자원 요청이 “가용 자원 + 모든 $P_j (j < i)$의 보유 자원”에 의해 충족되어야 함
    • 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
      • $P_i$의 자원 요청이 즉시 충족될 수 없으면 모든 $P_j(i < j)$가 종료될 때까지 기다린다.
      • $P_{i-1}$이 종료되면 $P_i$의 자원요청을 만족시켜 수행한다.


  • 시스템이 safe state에 있으면 no deadlock
  • 시스템이 unsafe state에 있으면 possibility of deadlock
  • Deadlock Avoidance
    • 시스템이 unsafe state에 들어가지 않는 것을 보장
    • 2가지 경우의 avoidance 알고리즘
      • Single instance per resource types : Resource Allocation Graph algorithm 사용
      • Multiple instances per resource types : Banker’s Algorithm 사용



Resource Allocation Graph algorithm



Banker’s Algorithm

  • 가정
    • 모든 프로세스는 자원의 최대 사용량을 미리 명시
    • 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 이들 자원을 다시 반납한다.
  • 방법
    • 기본 개념: 자원 요청 시 safe 상태를 유지할 경우에만 할당
    • 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택 (그런 프로세스가 없으면 unsafe 상태)
    • 그로 프로세스가 있으면 그 프로세스에게 자원을 할당
    • 할당받은 프로세스가 종료되면 모든 자원을 반납
    • 모든 프로세스가 종료될 때까지 이러한 과정 반복
  • Ex.

  • Allocation : 할당
  • Max : 최대
  • Available : 가용
  • Need : 요구



Deadlock Detection and Recovery

  • Deadlock Detection
    • Resource type 당 single instance인 경우
      • 자원할당 그래프에서의 cycle이 곧 deadlock을 의미
    • Resource type 당 multiple instance인 경우
      • Banker’s algorithm과 유사한 방법 활용
  • Wait-for graph 알고리즘
    • Resource type 당 single instance인 경우
    • Wait-for graph
      • 자원할당 그래프의 변형
      • 프로세스만으로 node 구성
      • $P_j$가 가지고 있는 자원을 $P_k$가 기다리는 경우 $P_k \rightarrow P_j$
    • Algorithm
      • Wait-for graph에 사이클이 존재하는지를 주기적으로 조사
      • $O(n^2)$

  • 위 상황은 자원의 최대 사용량을 미리 알리 필요 없음 -> 그래프에 점선이 없음


  • Resource type 당 multiple instance인 경우

Request는 추가요청가능량이 아니라 현재 실제로 요청한 자원량을 나타냄


  • Recovery
    • Process termination
      • 데드락의 연루된 모든 프로세스를 죽인다.
      • 데드락의 연루된 프로세스를 하나씩 죽여본다. (데드락이 없어질 때까지)
    • Resource Preemption
      • 비용을 최소화할 victim의 선정
      • safe state로 rollback하여 process를 restart
      • Starvation 문제
        • 동일한 프로세스가 계속해서 victim으로 선정되는 경우
        • cost factor에 rollback 횟수도 같이 고려



Deadlock Ignorance

  • Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음
    • Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있음
    • 만약, 시스템에 deadlock이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 등의 방법으로 대처
    • UNIX, Windows 등 대부분의 범용 OS가 채택





댓글남기기

참고