운영체제(Operating System) 6강

 in Computer Science / Operating-system
운영체제(Operating System) 6강

반효경 교수님 - Deadlocks


Lecture


Deadlock

image


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


  • Resource
    • 하드웨어, 소프트웨어 등을 포함하는 개념
      • I/O device, CPU cycle, memory space, semaphore etc.
    • 프로세스가 자원을 사용하는 절차
      • Request, Allocate, Use, Release
  • Example
    • Example 1
      • 시스템에 2개의 tape drive가 있다
      • P1과 P2가 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있다
    • Example 2
      • 이진 세마포어 A와 B가 있다
      • P1이 A를 얻은 상태에서 Context Switch가 발생했다
      • P2에게 CPU 제어권이 넘어갔고, P2가 B를 얻었다
      • 다시 Context Switch가 발생하여 P1에게 CPU 제어권이 넘어갔다
      • P1이 B를 얻고 싶어하지만 이미 P2가 B를 가지고 있기 때문에 P1은 P2가 B를 내놓기를 기다린다
      • 다시 Context Switch가 발생하여 P2에게 CPU 제어권이 넘어갔다
      • 마찬가지로 P2가 A를 얻고 싶어하지만 이미 P1이 A를 가지고 있기 때문에 P2는 P1이 A를 내놓기를 기다린다
      • 무한히 서로를 기다린다


Deadlock’s Requirements

데드락은 하기의 4가지 조건이 모두 만족될 때 발생한다.

반대로 생각하면 단 하나라도 조건을 만족하지 않는다면 데드락은 절대 발생하지 않는다.


  • Mutual Exclusion (상호 배제)
    • 매 순간 하나의 프로세스만이 공유 자원을 점유 할 수 있다
  • No preemption (비선점)
    • 프로세스는 공유 자원을 자발적으로 내어 놓을 뿐 강제로 빼앗기지는 않는다
  • Hold and wait (점유와 대기)
    • 공유 자원을 점유한 프로세스가 다른 공유 자원을 기다릴 때 보유한 공유 자원을 내어 놓지 않고 계속 가지고 있는다
  • Circular wait (순환 대기)
    • 공유 자원을 기다리는 프로세스간에 순환 대기가 형성되어야 한다
    • 프로세스 P0, P1, … , Pn이 있을 때
      • P0은 P1이 가진 자원을 기다린다
      • P1은 P2가 가진 자원을 기다린다
      • P(n-1)은 Pn이 가진 자원을 기다린다
      • Pn은 P0이 가진 자원을 기다린다


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

image


P(동그라미)는 프로세스를 의미하며, R(사각형)은 자원을 의미한다.

화살표는 두 가지가 있다.

  • 자원 -> 프로세스
    • 자원이 프로세스에 점유되어있다
  • 프로세스 -> 자원
    • 프로세스가 자원 점유를 요청하였으나 획득하지는 못하였다


데드락은 다음과 같이 판단한다.


image


  • 그래프에 사이클(순환 대기)이 없으면 데드락이 아니다
  • 그래프에 사이클이 있으면,
    • 자원 하나에 하나의 인스턴스만 있다면 데드락이다
    • 자원 하나에 여러 인스턴스가 존재한다면 데드락 가능성이 있다


  • 왼쪽 그래프
    • P1에게 R2 1개가 점유되고 있고, P2에게 R2 1개가 점유되고 있는 상황이다
    • 이 때 P3이 R2를 요구한다
    • P2는 R3 1개를 요청하지만, R3은 이미 P3가 가지고 있다
    • 이 때 P1은 R1을 요청하지만, 이것은 P2가 가지고 있다. 즉, 사이클이 존재한다
    • 사이클이 존재하며, 자원 하나에 프로세스 하나씩 할당돼있기 때문에 데드락이다.


  • 오른쪽 그래프
    • P1에게 R2가 할당되어 있다
    • P4에게 R2가 할당되어 있다
    • P3가 R2를 요구하면 P4가 R2 자원을 반납하면 된다
    • 즉, 사이클이 없다
    • 따라서 데드락이 아니다


Deadlock Resolution

데드락을 해결하기 위한 방법들은 다음과 같다.


Deadlock Prevention (데드락 예방)

  • 자원 할당 시 데드락의 4가지 필요 조건 중 어느 하나를 만족되지 않도록 하는 것
  • Mutual exclusion (상호 배제)
    • 공유해서는 안되는 자원의 경우 반드시 성립해야 하므로 건들지 않는다
  • Hold and wait (점유와 대기)
    • 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다
    • 방법 1 - 프로세스 시작 시 필요한 모든 자원을 할당받게 한다
    • 방법 2 - 자원이 필요할 경우 보유 자원을 모두 내어 놓은 후 요청 한다
  • No preemption (비선점)
    • 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점된다
    • 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다
    • 상태를 쉽게 저장하고 불러올 수 있는 자원에서 주로 사용한다
  • Circular wait (순환 대기)
    • 모든 자원 유형에 할당 순서를 정하여서 정해진 순서대로만 자원을 할당한다

데드락 예방 방법을 선택하면, 생길지 안생길지 모르는 데드락을 막을려고 사전에 많은 제약을 걸어두기 때문에, 이용률 저하, 시스템 성능 감소, Starvation 등의 문제가 발생할 수 있다.

즉, 효율성이 떨어진다.


Deadlock Avoidance (데드락 회피)

  • 자원 요청에 대한 부가 정보를 이용해서 자원 할당이 데드락으로부터 안전(Safe)한지를 동적으로 조사해서 안전한 경우에만 할당
  • 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법임
  • 시스템이 안전 상태에 있으면 데드락이 아니며, 불안전 상태에 있으면 데드락의 가능성이 있다고 볼 수 있다
  • 데드락 회피는 시스템이 불안전 상태에 들어가지 않는 것을 보장한다
    • 자원 유형 당 1개의 인스턴스만 존재
      • Resource Allocation Graph Algorithm (자원 할당 그래프 알고리즘)
    • 자원 유형 당 여러 개의 인스턴스 존재
      • Banker’s Algorithm (은행원 알고리즘)


image


Resource Allocation Graph Algorithm (자원 할당 그래프 알고리즘)

image


  • Claim edge(점선)
    • 프로세스가 자원을 미래에 요청할 수 있음을 뜻한다
  • Request edge(실선)
    • 프로세스가 해당 자원 요청 시 실선으로 바뀐다
  • 데드락 회피는 데드락이 위험성이 있으면 자원을 할당하지 않는다
    • 위에서 3번째 이미지는 데드락의 위험성이 있기 때문에 자원이 할당되지 않는다


Banker’s Algorithm (은행원 알고리즘)

은행에서 사람들에게 돈을 대출해주는 것에서 착안한 알고리즘으로, 현재 사용할 수 있는 자원과 필요로 하는 자원들을 계산하여, 데드락의 위험성이 있는지 검증한다.


image


image


  • A는 10개, B는 5개, C는 7개가 존재
  • Allocation은 현재 각 프로세스에 할당된 자원의 수를 의미
  • Max는 각 프로세스마다 최대로 할당 받고 싶은 자원의 수를 의미
  • Available은 각 자원이 프로세스에게 추가로 할당 할 수 있는 가용 자원의 수를 의미
  • Need는 각 프로세스가 현재 최대로 필요로 하는 자원의 수를 뜻하며, Max에서 Allocation을 뺀 값
  • 자원은 현재 가용 자원을 보고, Need만큼 자원을 줄 수 있는 프로세스를 하나도 찾지 못하면 불안전한 상태가 됨
    • 자원을 줄 수 있는 프로레스가 있다면 해당 프로세스에게 자원을 주고난 후, 프로세스가 끝날 때 모든 자원을 가져온다
    • 이 과정을 반복하면 <P1, P3, P4, P2, P0>라는 안전 순서열을 만들 수 있다


데드락 회피 또한, 데드락을 막기 위해 사전에 많은 제한을 걸게 되므로 비효율적이다


Deadlock Detection and recovery (데드락 탐지 및 회복)

데드락이 발생할 때 까지 아무런 조치를 하지 않다가, 데드락이 발생하면 조치를 취한다

  • Deadlock Detection (데드락 탐지)
    • 자원 당 인스턴스가 하나인 경우 == 자원할당 그래프의 사이클이 곧 데드락을 의미
  • Deadlock recovery (데드락 회복)
    • Process termination
      • 방법 1 - 데드락에 연관된 모든 프로세스를 죽인다
      • 방법 2 - 데드락에 연관된 프로세스를 하나씩 죽이다 데드락이 풀리면 그만둔다
    • Resource Preemption
      • 비용을 최소화할 희생양을 선정하여, 그 프로세스로 부터 자원을 빼앗아온다


Deadlock Ignorance (데드락 무시)

  • 데드락이 일어나지 않는다고 가정 아무런 조치도 취하지 않는다
    • 데드락이 애초에 매우 드물게 발생하므로 데드락에 대한 조치 자체가 더 큰 오버헤드일 수 있다
    • 만약 시스템에 데드락이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 프로세스를 죽이는 등의 방법으로 대처한다
    • UNIX, Windows 등 대부분의 OS에서 채택하였다


Deadlock implemented in Java

public class Deadlock {
    private static final Logger logger = Logger.getLogger(Deadlock.class.getName());

    public static void main(String[] args) {
        Integer lock1 = 1;
        Integer lock2 = 2;

        Thread t1 = new Thread(() -> {
            synchronized (lock1) {
                logger.info("t1 got lock1. now going to try to get a lock2");
                synchronized (lock2) {
                    logger.info("t1 got lock2");
                }
                logger.info("If this message is printed, it means that t1 has acquired lock2");
            }
        });

        Thread t2 = new Thread(() -> {
            synchronized (lock2) {
                logger.info("t2 got lock2. now going to try to get a lock1");
                synchronized (lock1) {
                    logger.info("t2 got lock1");
                }
                logger.info("If this message is printed, it means that t2 has acquired lock1");
            }
        });

        t1.start();
        t2.start();
    }
}



INFO: t1 got lock1. now going to try to get a lock2
INFO: t2 got lock2. now going to try to get a lock1


© 2022. All rights reserved.