[OS] DeadLock(데드락)

Deadlock이란?

상호배제에 의해 나타나는 문제점. 둘 이상의 프로세스들이 각각 자원을 점유한 상태에서, 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 서로의 작업이 끝나기만을 기다리다가 영원히 끝나지 않는 상황을 의미한다.

Deadlock 이 동작하기 위한 4가지 조건

- Mutual exclusion (상호배제) : 매 순간 하나의 프로세스만이 자원을 사용할 수 있음

  -> 자원을 얻었으면 독점적으로 쓴다.

- No preemption(비선점) : 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음

- Hold and wait(보유 &대기) : 자원을 가진 프로세스가 다른 자원을 기다릴때 보유자원을 놓지 않고 계속 가지고 있음

- Circular wait (순환대기): 자원을 기다리는 프로세스간에 사이클이 형성되어야 

그렇다면 3가지만 충족하면 왜 Deadlock 이 발생하지 않을까요?

Deadlock 발생에 필요한 조건이 4가지 중 하나인 "순환 대기(Circular Wait)" 조건이 포함되어 있기 때문입니다. 순환 대기 예를 들어,

1. 상호 배제 조건이 없으면 두 개 이상의 프로세스가 동시에 자원을 사용할 수 있으므로, 대기할 필요가 없어짐
2. 점유 및 대기 조건이 없으면 자원을 요청한 프로세스는 해당 자원을 할당받지 못하고 바로 실패하게 되므로 대기X
3. 비선점 조건이 없으면 다른 프로세스가 자원을 강제로 해제할 수 있으므로, 프로세스들이 서로 계속해서 자원을 해제하고 점유할 수 있게 됨

따라서, 세 가지 조건만 충족된다면 순환 대기 조건이 없어서 Deadlock이 발생하지 않으며, 순환 대기 조건이 포함된 경우 4가지 조건이 모두 충족되어야 Deadlock이 발생합니다.

 

처리방법

- Prevention : 자원 할당시 DeadLock의 4가지 필요조건 중 어느하나가 만족되지 않도록 하는것

- Avoidance

1. 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당.
2. 시스템 state가 원래 state로 돌아올수 있는 경우에만 자원 할당

- Detection and recovery

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

- Ignorance : Deadlock을 시스템이 책임지지 않음 -> 대부분 OS가 채택    

왜 현대 OS는 Deadlock을 처리하지 않을까요?

1. 빈번히 발생하는 이벤트가 아니기 때문에 미연에 방지하기 위해 훨씬 더 많은 오버헤드를 들이는것이 비효율적이라고 판단함.
2. 현대 시스템의 복잡성으로 인해 교착 상태를 완전히 방지하는 것은 불가능
3. 만약 시스템에서 deadlock이 발생한 경우 시스템이 비정상적으로 작동한것을 사람이 느낀후 직적 process를 죽이는 방법으로 대처

 

예방방법

Prevention

데드락을 발생시키는 4가지 조건을 애초에 발생시키지 않도록 해서 데드락이 발생하지 않도록함 

- Mutual Exclusion (상호 배제) : 뮤텍스를 획득하고 해제하는 순서를 정의하는 것 -> 이를 통해 순환 대기(Circular Wait) 조건을 제거하여 데드락을 예방

 

예를 들어, 두 개의 공유 자원 A와 B가 있고, 스레드 T1과 T2가 이 자원들을 사용한다고 가정합시다. 데드락을 예방하기 위해 자원을 사용하기 전에 뮤텍스를 획득하고, 작업을 완료한 후에 뮤텍스를 해제하는 순서를 정의합니다.

Thread T1:
1. Acquire Mutex A
2. Acquire Mutex B
3. Access shared resources (A and B)
4. Release Mutex B
5. Release Mutex A

Thread T2:
1. Acquire Mutex A
2. Acquire Mutex B
3. Access shared resources (A and B)
4. Release Mutex B
5. Release Mutex A

 

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

class SharedResource {
    private final Lock lock = new ReentrantLock();
    private int counter = 0;

    public void increment() {
        lock.lock(); // 락 획득
        try {
            counter++;
            System.out.println("Counter: " + counter);
        } finally {
            lock.unlock(); // 락 해제
        }
    }
}

class MyThread extends Thread {
    private final SharedResource sharedResource;

    public MyThread(SharedResource sharedResource) {
        this.sharedResource = sharedResource;
    }

    @Override
    public void run() {
        for (int i = 0; i < 10; i++) {
            sharedResource.increment();
        }
    }
}

public class MutexExample {
    public static void main(String[] args) {
        SharedResource sharedResource = new SharedResource();
        MyThread t1 = new MyThread(sharedResource);
        MyThread t2 = new MyThread(sharedResource);

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

위 예제에서는 뮤텍스 획득과 해제의 순서가 동일하므로, 순환 대기 조건이 제거되고 데드락이 발생하지 않습니다. 이러한 방식으로 뮤텍스를 사용하여 데드락을 예방할 수 있습니다. 하지만 이 방법은 프로그램의 복잡성에 따라 뮤텍스 획득 및 해제 순서를 관리하는 것이 어려울 수 있습니다.

 

 

-No Preemption (비선점) 

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

 

- Hold and wait (점유와 대기) : 프로세스가 자원을 요청할때 다른 어떤 자원도 가지고 있지 않아야 한다.

(자원을 기다리는 상태에서 자원을 보유하고 있지 않으면 됨, 자진반납)

1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법 (종료시 모두 반납-> 매시점마다 필요한 자원이 다른데, 모든걸 hold하고 자원에 대해 비효율적)
2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청 (필요할때 그때그때 할당받음)

 

- 자원 할당 순서 결정 : 일반적으로 자원 요청 순서를 기준으로 결정

Circular wait (순환대기)

• 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
• ex. 순서(3)인 자원 R(a)를 보유중인 프로세스가 순서(1)인 자원 R(b)을 할당받이위해서 자원 R(a)를 release해줘야한다. -> Utilization 저하, throughpu감소, starvation 문 
• 1,3번을 필요를 할때, 1번을 획득해야지만 3번을 획득해야한다는 조건. -> 자원마다 획득 순서를 정해둠

Avoidance

• 자원이 있지만 deadlock의 가능성이 전혀 없는 경우만 할당함
• 평생에 쓸 자원을 미리 알고있어서 자원요청이 있을때 deadlock가능성이 있으면 자원의 여분이 있음에도 할당 안해줌

 

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

다중 프로세스 환경에서 교착상태(deadlock)을 방지하기 위해 사용되는 알고리즘

은행원 알고리즘은 각 프로세스가 필요로 하는 자원의 최대값과 현재 할당된 자원의 양을 바탕으로 안정적인 상태(stable state)를 유지할 수 있는지 여부를 판단

*안정적인 상태

모든 프로세스의 자원 요구를 만족시키면서 교착상태가 발생하지 않는 상태

 

하지만, 모든 프로세스가 최대 자원을 요구할 때는 안정적인 상태를 유지할 수 없으므로 이러한 경우에는 교착상태가 발생할 가능성이 있음 -> 다른 방법을 사용하여 교착상태를 방지 필요

1. 각 프로세스가 필요로 하는 자원의 최대값(Max)과 현재 할당된 자원의 양(Allocation)을 입력받습니다.
2. 시스템에서 가용 자원의 양(Available)을 입력받습니다.
3. 각 프로세스가 요청할 자원의 양(Request)을 입력받습니다.
4. 시스템은 Request 자원을 할당받았을 때 교착상태가 발생하지 않는지 여부를 판단합니다.
   • Request <= Available : Request 자원을 할당받았을 때 안정적인 상태(stable state)를 유지할 수 있다면, 자원을 할당하고 프로세스를 실행합니다.
   • Request > Available : Request 자원을 할당받았을 때 안정적인 상태를 유지할 수 없다면, 자원을 할당하지 않고 대기합니다.
5. 프로세스가 자원을 사용하고 반환할 때, Available 자원의 양을 갱신합니다.

 

*은행원 알고리즘에서 왜 각 프로세스가 필요로 하는 자원의 최대값(Max)과 현재 할당된 자원의 양(Allocation)을 입력받는 이유

교착상태가 발생했는지 여부를 판단하기 위해서는, 각 프로세스가 얼마만큼의 자원을 요구하고, 현재 얼마만큼의 자원을 할당받았는지를 파악해야 합니다.

따라서, 각 프로세스가 필요로 하는 자원의 최대값(Max)과 현재 할당된 자원의 양(Allocation)을 입력받아 

해당 프로세스가 최대 얼마만큼의 자원을 요구할 수 있는지를 알아내고 해당 프로세스가 현재까지 얼마만큼의 자원을 할당받았는지를 알아냅니다.

Detection and recovery(검출 및 복구)

• 데드락이 생기던 말든 냅둠(데드락이 빈번하게 발생하지 않기 때문에)
• 갑자기 시스템이 느려지면 데드락 detection-> 발견시 ->recovery
• 교착상태를 방지하는 것보다는 교착상태가 발생한 후에 이를 해결하는 방법 ->교착상태 방지에 비해 비효율적

1. 자원 할당 그래프(Resource Allocation Graph)를 구성합니다.
   • 자원 할당 그래프란 프로세스와 자원 간의 관계를 그래프로 표현한 것입니다.
   • 그래프 상에서 교착상태가 발생했는지 검사합니다.
2. 교착상태가 발생한 경우, 교착상태를 발생시킨 프로세스나 자원을 찾아내고, 해당 프로세스나 자원을 중지(하나씩 혹은 전체)시킵니다.
   • 이때, 교착상태를 발생시킨 프로세스나 자원이 다른 프로세스나 자원에 의존하는 경우, 이를 모두 중지시켜야 합니다.
   • 중지된 프로세스나 자원은 해당 자원을 반환하고 다른 프로세스나 자원이 사용할 수 있도록 해야 합니다.
3. 중지된 프로세스나 자원을 다시 시작합니다.
   • 이때, 프로세스나 자원이 다른 프로세스나 자원에 의존하는 경우, 이를 먼저 시작해야 합니다.

 

Ignorance

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

 

Wait Free와 Lock Free를 비교해 주세요.

Wait-free와 Lock-free는 모두 멀티스레딩 환경에서 공유 자원에 대한 동시 접근을 처리하는 기술

Wait-free는 모든 스레드가 동시에 진행될 수 있는 것에 비해,

Lock-free는 일부 스레드가 블로킹될 가능성이 있지만, 구현이 더 쉽고 성능이 높은 경우가 많음.

	Wait-free	Lock-free
공통점	- 스레드가 락을 획득하거나 해제하는 데 소비되는 시간이 줄어듭니다. - 락 경쟁으로 인한 병목 현상이 줄어들어 여러 스레드가 효율적으로 동시에 실행될 수 있습니다. - 무한 대기 상황을 방지함으로써 데드락과 라이브락 문제를 해결
설명	모든 스레드가 동시에 진행되고, 하나의 스레드가 멈추더라도 다른 스레드는 계속 진행될 수 있도록 구현	항상 하나 이상의 스레드가 진행할 수 있음이 보장
특징	Wait-free에서는 어떤 스레드도 블로킹(blocking) 되지 않음	공유 자원에 대한 동시 접근을 처리하기 위해 락(lock)을 사용하지 않고, 원자적(atomic) 연산을 사용
단점	- Wait-free는 복잡하고 구현하기 어려운 경우가 많아서 일반적으로 사용되기 어려움 - Lock-Free보다 더 많은 오버헤드가 발생할 수 있	일부 스레드가 블로킹될 가능성이 있으므로, 높은 지연시간을 보일 수 있음
장점	모든 스레드가 한정된 시간 내에 진행할 수 있는 것을 보장	-구현하기 쉽고, 항상 하나 이상의 스레드가 진행할 수 있음이 보장 - 스레드 간 상호작용 없이 공유 자원을 안전하게 사용할 수 있도록 보장

 

*세마포어,뮤텍스와 모니터 VS  Wait-Free, Lock-Free

세마포어, 뮤텍스, 모니터와 Wait-Free, Lock-Free는 동시성 제어를 처리하는 다양한 동기화 방법입니다.

세마포어, 뮤텍스, 그리고 모니터는 Lock을 사용하는 Locking 매커니즘

Wait-Free, Lock-Free : Lock대신 CAS를 이용하여 동기화 하는 기술(atomic operation)

 

CAS 연산

동시성 제어에서 사용되는 원자적(atomic) 연산(실행 중에 다른 작업에 의해 방해받지 않고, 완전히 실행되거나 실행되지 않는 연산)

• CAS 연산은 하드웨어 수준에서 지원
• 멀티 스레드 환경에서 공유 자원에 대한 동시 접근을 안전하게 처리하는 데 사용
• 대상 메모리 위치의 값이 예상 값과 같은지 비교한 다음, 조건이 충족되면 새로운 값으로 업데이트하는 작업 수행

-> 모든 과정이 원자적으로 수행되기 때문에, 여러 스레드가 동시에 CAS 연산을 수행하더라도 데이터 경쟁(race condition)이 발생하지 않음