[운영체제] DeadLock

도움1
도움2

📌 데드락이란?

교착상태를 말한다. 사진으로 간단하게 설명할 수 있다!
즉, 두개 이상의 스레드 혹은 프로세스가 서로가 가진 리소스를 기다리는 상태

📌 데드락을 만들기 위한 조건

1. mutual exclusion
   리소스를 공유해서 사용할 수 없다.

2. Hold and wait
   프로세스가 이미 하나 이상의 리소스를 취득한(hold) 상태에서 다른 프로세스가 사용하고 있는 리소스를 추가로 기다린다.(wait)

• 사진을 보면 모든 프로세스 혹은 스레드가 하나 이상의 자원을 획득한 상태. (숫자가 리소스)

3. No preemption

• 리소스 반환(release)은 오직 그 리소스를 취득한 프로세스만 할 수 있다.

4. Circular wait

• 프로세스들이 순환 형태로 서로의 리소스를 기다린다.

📌 데드락을 OS가 해결하는 방법

1. 데드락 방지 (Deadlock prevention)

네 가지 조건 중 하나가 충족되지 않게 시스템을 디자인

(1) mutual exclusion

• 리소스를 공유 가능하게 함 (이 방법은 현실적으로 불가능!)

(2) hold and wait

• 사용할 리소스들을 모두 획득한 뒤에 시작
• 리소스를 전혀 가지지 않은 상태에서만 리소스 요청
  -> 만약 오른쪽 위 차량이 2번 리소스를 먼저가지고 작업을 시작하다가 2번으로 할 수 있는 작업을 다 한 뒤에 2번 리소스를 release 시키고, 3번 리소스에 가서 2번과 3번에 대한 리스소를 요청하고 만약에 불가능하다면 다른 프로세스가 2번 리소스를 획득할 수 있도록 기회를 주는 것.

-> 단점: 모두 확보한 상태일 때 2번, 3번을 모두 획득했다라고 가정 시, 2번이 매우 오래걸리는 작업이면 3번이 놀게되어 리소스 낭비가 발생,
또 만약, 2번과 3번의 리소스가 너무 인기가 많아서 오른쪽 위 프로세스는 대기를 지속하게 된다. 그렇게 되면 기아현상(Starvation)이 발생한다.

(3) no preemption

• 추가적인 리소스를 기다려야 한다면 이미 획득한 리소스를 다른 프로세스가 선점 가능하도록 한다.

(4) circular wait

• 모든 리소스에 순서 체계를 부여해서 오름차순으로 리소스를 요청 (4번 리소스 다음 1번의 리소스를 차지 못함)

2. 데드락 회피 (Deadlock avoidance) [가장 많이 사용됨!]

• 실행 환경에서 추가적인 정보를 활용해서 데드락이 발생할 것 같은 상황을 회피하는 것
• 운영체제가 동작하고 있을 때 현재 사용하고 있는 리소스들, 이미 어딘가에 할당된 리소스들, 미래에 있을 리소스 요청, 반환 등에 관한 정보

• 대표적인 Banker algorithm

• 리소스 요청을 허락해줬을 때 데드락이 발생할 가능성이 있으면 리소스를 할당해도 안전할 때 까지 계속 요청을 거절하는 알고리즘

데드락 감지와 복구 (거의 최후의 카드)

• 데드락을 허용하고 데드락이 발생하면 복구하는 전략

1. 프로세스를 종료한다.

• 데드락에 빠진 모든 프로세스를 종료한다. or 한명씩 강제로 종료 (데드락 해결되면 다시 진행)

2. 리소스의 일시적인 선점을 허용한다.

• 데드락이 발생하면 일시적으로 프로세스에게 선점을 허용해서 필요한 리소스들을 할당해서 해결.

데드락 무시

• 아몰랑.. 개발자가 알아서 하겠지..? ㅇㅅaㅇ

자바로 보는 프로그래밍 레벨에서 데드락

public class Main {

    public static Object object1 = new Object();
    public static Object object2 = new Object();

    public static void main(String[] args) {
        FirstThread thread1 = new FirstThread();
        SecondThread thread2 = new SecondThread();

        thread1.start();
        thread2.start();

    }

    private static class FirstThread extends Thread{
        @Override
        public void run() {
            synchronized (object1){
                System.out.println("First Thread has object1's lock");

                try {
                    Thread.sleep(10);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println("First Thread want to have object2's lock. so wait");

                synchronized (object2){
                    System.out.println("First Thread has object2's lock too");
                }
            }
        }
    }

    private static class SecondThread extends Thread{
        @Override
        public void run() {
            synchronized (object2){
                System.out.println("Second Thread has object2's lock");

                try {
                    Thread.sleep(10);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println("Second Thread want to have object1's lock, so wait");

                synchronized (object1){
                    System.out.println("Second Thread has object1's lock too");
                }
            }
        }
    }
}

결과

First Thread has object1's lock
Second Thread has object2's lock
First Thread want to have object2's lock. so wait
Second Thread want to have object1's lock, so wait

환형대기 조건을 만족하지 않는 경우

public class Main {

    public static Object object1 = new Object();
    public static Object object2 = new Object();

    public static void main(String[] args) {
        FirstThread thread1 = new FirstThread();
        SecondThread thread2 = new SecondThread();

        thread1.start();
        thread2.start();

    }

    private static class FirstThread extends Thread{
        @Override
        public void run() {
            synchronized (object1){
                System.out.println("First Thread has object1's lock");

                try {
                    Thread.sleep(10);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println("First Thread want to have object2's lock. so wait");

                synchronized (object2){
                    System.out.println("First Thread has object2's lock too");
                }
            }
        }
    }

    private static class SecondThread extends Thread{
        @Override
        public void run() {
            synchronized (object1){
                System.out.println("Second Thread has object2's lock");

                try {
                    Thread.sleep(10);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println("Second Thread want to have object1's lock, so wait");

                synchronized (object2){
                    System.out.println("Second Thread has object1's lock too");
                }
            }
        }
    }
}

First Thread has object1's lock
First Thread want to have object2's lock. so wait
First Thread has object2's lock too
Second Thread has object2's lock
Second Thread want to have object1's lock, so wait
Second Thread has object1's lock too