운영체제#16

LeeMir, 31 May 2021

6강 - Deadlock


Deadlock
  • 한 집단의 프로세스들이 서로 이벤트가 끝나길 기다리는 상황이 발생해 무한 대기에 빠지는 현상
    • Deadlock에 걸리는 상황은 자원 공유뿐 아니라 여러 이벤트가 존재함
  • Deadlock의 4 조건
    • Mutual exclusion condition(상호 배제 기능이 있을 때)
    • Hold and wait condition(독점적으로 자원을 사용할 때)
    • No preemption condition(문맥교환 같은 경우가 아니라 한 번 이벤트를 시작하면 끝날때까지 중단할 수 없을 때)
    • Circular wait condition(프로세스들이 꼬리에 꼬리를 물면서 hold and wait에 빠질 때)
  • 조건을 모두 달성했다고 해서 Deadlock이 반드시 발생하지는 않고, 각 프로세스를 어떤 순서로 실행하느냐에 따라 발생할 수도 있음
  • Deadlock Modeling
    • 사각형 : 자원, 동그라미 : 프로세스
  • Deadlock 해결책
    • 타조 전략(문제를 무시하고 그냥 재부팅을 권함)
    • 운영체제의 주기적인 Deadlock Detection
      • utilization이 많이 떨어진 프로세스가 있을 경우 Deadlock으로 의심
      • Deadlock이면 프로세스를 죽임
    • Deadlock 회피
      • 자원을 할당해 줄 때 Deadlock 발생 가능성을 검사해 발생 가능성이 있으면 자원 할당을 하지 않음
    • Prevention(예방)
      • Deadlock의 4 조건을 없애버림
Deadlock Detection
  • 각 타입의 자원이 하나만 존재할 때
    • 자원할당 그래프를 그린 후, 사이클이 존재하는지 검사
  • 각 타입의 자원이 여러개 존재할 때
    • Bankus 알고리즘
      • Allocate Table과 Require Table을 만듦
      • Table을 탐색하면서, 현재 쓸 수 있는(Available) 자원으로 처리할 수 있는 프로세스부터 끝냄
      • 한 프로세스가 끝나고 자원을 반납하면 쓸 수 있는 자원이 늘어나 처리할 수 있는 프로세스가 또 생김
      • 만약 프로세스가 살아있는데 현재 쓸 수 있는 자원으로 처리할 수 있는 프로세스가 하나도 없을 경우 Unsafe 상태로 판단
        • Deadlock 회피를 적용한다면, 할당할 때부터 할당해주면 Unsafe가 될 수 있는지 검사해 가능성이 있으면 할당하지 않음
Recovery from Deadlock
  • Deadlock을 Detect했다면 Recovery가 필요함
  • preemption
    • 자원이 preemption이 가능하다면 프로세스를 일시정지해서 자원을 다른 프로세스에게 줌
  • rollback
    • 프로그래밍 기법 중 하나
    • 체크포인트를 기록해뒀다가 Deadlock이 발생하면 rollback
  • killing processes
    • 대부분의 경우 프로세스를 희생해야 함
    • Deadlock에 걸려있는 프로세스 중 하나를 죽이고 그 자원을 다른 프로세스에게 부여
Deadlock Avoidance
  • 자원을 할당할 때, Deadlock이 발생하지 않을 것 같을 때에만 할당해주는 기법
Deadlock Prevention
  • Attacking the Circular Wait Condition
    • Circular Wait가 생기는 이유 : 프로세스들이 임의의 순서로 자원을 요구하기 때문
    • 따라서 자원을 할당받는 순서를 통일하면 Circular Wait을 예방할 수 있음
      • 자원의 종류가 너무 많아 이를 모든 프로세스에 요구하기에는 까다로움
  • Attacking the No Preemption
    • CPU나 메모리의 경우에는 기본적으로 Preemption이 가능
    • printer의 경우 원래 Preemption이 불가능한데, 스풀링 같은 기법을 사용하면 Preemption이 가능해짐
  • Attacking the Mutual Exclusion
    • 운영체제를 잘 설계하면 Deadlock이 발생하지 않게 상호 배타적인 디바이스들을 상호 배타하지 않게 할 수 있음
    • 한 프로세스가 하드디스크 전체를 독점하지 않음
      • 하드디스크 안에 파일 단위로 나뉘어있어 여러 프로세스가 하드디스크를 공유해서 쓸 수 있음
      • 스풀링 기법
  • Attacking the Hold and Wait
    • 프로세스가 여러 자원을 요구할 때 순차적으로 요구하게 하는게 아니라, 한꺼번에 다 받아오고 시작하게 함
    • 자원 효율이 많이 떨어짐
    • 자원을 많이 요구한 프로세스는 꽤 오래 기다려야할 수 있어 Starvation이 발생할 수 있음
    • 현실성이 많이 떨어지는 기법
Intergrated Deadlock Strategy
  • 운영체제에서는 Deadlock의 발생 가능성을 줄이고자 모든 방법을 동원하고 있음
    • Swappable space : 처음에 Swap 영역을 할당할 때 나중에 더 요구하는 경우가 없게 여유롭게 할당해 줌
    • Process resource : resource ordering을 해서 deadlock을 예방하거나 deadlock 회피
    • Main memory : preemption을 통한 예방
    • Internel resource : resource ordering을 해서 deadlock을 예방함
Other Issue
  • Two-phase locking
    • lock의 순서가 엇갈려 deadlock이 발생하는 것을 막는 방법
    • 하나를 lock하는 데 성공하고 다른 하나를 lock하려는데 이미 lock이 되어있는 상태(다른 프로세스에서 사용중인 상태)라면 처음에 lock했던 것을 unlock하고 기다림
  • Communication Deadlocks
    • 통신에서 송신 버퍼와 수신 버퍼가 일치할 경우 각 호스트에서 송신을 위해 송신 버퍼를 채우는데, 우연히 동시에 송신을 위해 버퍼를 꽉채울 경우 상대의 버퍼가 비어있지 않아 송신을 할 수 없고 Deadlock에 빠짐
  • Livelock
    • 겉으로는 실행되는 것처럼 보이지만 서로 폴링하고 있는거라 사실상 Deadlock과 같은 상태
    • CPU를 소비하는 거라 Deadlock보다 더 안좋음
  • Starvation
    • Deadlock이 발생해 하나의 프로세스를 희생했는데, 그 이후 그 프로세스가 실행되었을 때 다시 Deadlock이 발생했고 또 그 프로세스가 희생되는 반복에 빠짐