운영체제 (공룡책) - 8

‍주민하·2021년 11월 18일

운영체제

목록 보기

8/10

3. 프로세스 동기화

8. 데드락

스레드가 한정된 자원에 대해서 경쟁할 때, 만약 자기가 원하는 자원이 남이 사용하고 있다면 자신이 쓸 수 있을 때까지 대기를 함. 근데, 이게 자꾸 남이 계속 사용하고 있으면 나는 평생 기다려야함. 이 상황을 데드락 deadlock이라 부름. 6 단원에서 일종의 라이브니스 실패 상황이라고 얘기했었음. 즉, 데드락이란 한 프로세스 집합에서 모든 프로세스가 집합의 어떤 한 프로세스가 일으켜야할 이벤트에 대해 대기하고 있는 상태임.

데드락의 예시:

A~S급 선수들: 쇼쵸가 오면 너네 팀 갈게
쇼메이커, 쵸비: S급 라이너들 데려오면 너네 팀 갈게

B급: ㅇㅇ 좃될게

단원 목표

상호배제 락 사용 시 데드락이 발생할 수 있는 경우

데드락의 4 가지 필수 조건

자원 할당 그래프에서의 데드락 상황

데드락 방지하는 네 가지 방법

데드락 회피를 위한 뱅커 알고리듬

데드락 복구하는 방법

8.1. 시스템 모델

시스템엔 여러 한정된 수의 자원이 있어 이걸 서로 경쟁하는 스레드에게 배분해줘야 함. 스레드가 어떤 자원형에 대한 개체를 요청한다면, 해당 형을 갖는 임의의 개체를 할당해도 요구사항을 만족할 것. 만약 그렇지 않다면 개체가 동일하지 않다는 것이고 자원형 클래스가 제대로 정의가 안 된 것임.

상호배제 락, 세마포어도 시스템 자원임. 요즘 시대에 데드락을 일으키는 가장 일반적인 자원이기도 함. 근데 여기서 문제는 쟤네의 정의가 아님.

지금까지는 스레드가 커널 자원을 사용할 때에 대해 다뤘지만, 만약 한 스레드가 다른 스레드의 자원을 사용하려고 한다면? 이때에 대한 데드락은 커널 탓이 아니게 됨. 고로 여기서 다루지 않음.

스레드는 자원을 사용하기 전에 반드시 요청을 해야하고, 다 썻으면 반납해야 함. 원하는 만큼 요청 가능함. 당연히 시스템의 총 자원 수보다 많게는 못하겠지. 다시 말해 시스템에 네트워크 인터페이스가 하나 밖에 없다고 치면, 스레드가 이걸 두 개 이상 요청할 수 없다는 것.

일반적인 모드로 연산을 한다면, 스레드는 다음 순서로 자원을 사용:

요청 request. 바로 받아들여지지는 않음(상호배제 락이 다른 스레드가 사용하고 있는 경우 등). 이 경우, 자원 받을 때까지 대기해야 함.
사용 use.
반납 release.

장치에 대해서는 request()와 release(), 파일에 대해서는 open()과 close(), 메모리 시스템 호출의 경우 allocate()과 free(), 세마포어의 경우 wait()과 signal(), 상호배제 락의 경우 acquire()과 release(). 스레드가 커널에서 관리하는 자원을 쓸 경우 스레드의 요청과 할당을 운영체제에서 보장해줘야 함. 즉, 자원이 사용 중인지 아닌지를 기록한 시스템 표가 있음.

위에서 언급한 데드락의 정의에서 말하는 이벤트란 자원 얻기와 반납을 의미함. 여기서 말하는 자원은 보통 논리적(상호배제 락, 세마포어, 파일 등)인 애들이지만, 네트워크 인터페이스 혹은 IPC(프로세스 간 통신)로부터 읽어오기 등과 같은 다른 이벤트형도 데드락 문제를 일으킬 수 있음.

데드락 상황을 다시 생각해내려면, 7.1.3 절의 철학자 문제 보면 됨. 만약 모든 철학자가 동시에 배고파져서 전부 왼쪽에 있는 젓가락 하나를 들면, 전부 오른쪽 젓가락을 사용할 수 있을 때까지 대기해야 함.

8.2. 멀티스레드 어플리케이션에서의 데드락

Pthread의 POSIX 상호배제 락으로 데드락 상황 보이기:

우선 초기화부터:

pthread_mutex_t first_mutex;
pthread_mutex_t second_mutex;

pthread_mutex_init(&first_mutex, NULL);
pthread_mutex_init(&second_mutex, NULL);

얘네가 각각 do_work_one() 함수랑 do_work_two() 함수를 수행함.

/* thread_one이 이 함수 실행 */
void* do_work_one(void* param)
{
    pthread_mutex_lock(&first_mutex);
    pthread_mutex_lock(&second_mutex);
    /**
     * 뭔가를 함
     */
    pthread_mutex_unlock(&second_mutex);
    pthread_mutex_unlock(&first_mutex);
    
    pthread_exit(0);
}

/* thread_two가 이 함수 실행 */
void* do_work_two(void* param)
{
    pthread_mutex_lock(&second_mutex);
    pthread_mutex_lock(&first_mutex);
    /**
     * 뭔가를 함
     */
    pthread_mutex_unlock(&first_mutex);
    pthread_mutex_unlock(&second_mutex);
    
    pthread_exit(0);
}

위의 예제의 경우 thread_one은 (1) first_mutex와 (2) second_mutex 순으로 상호배제 락을 얻음. thread_two는 동시에 이와 반대의 순서로 얻음. thread_one이 first_mutex를 얻는 동시에 thread_two가 second_mutex를 얻었다면 데드락이 발생함.

8.2.1. 무한 반복

무한 반복 livelock은 라이브니스 실패 중 하나. 두 개 이상의 스레드가 앞으로 진전하지 못하게 해준다는 점에서 데드락과 유사하나 그 사유가 다름. 데드락은 한 놈이 이벤트를 대기 중이라는 사유가 있다면, 무한 반복은 스레드가 계속해서 실패하는 행동을 할 때 발생함. 비유를 하자면, 둘만 건널 수 있는 좁은 길목에서 서로 반대 방향으로 가는 도중 만났다고 가정. 그럼 둘이 중간에 만날텐데, 그럼 한 명은 가만히 있고 다른 한 명이 옆으로 가서 지나치면 되는데, 둘 다 배려심이 넘쳐서 둘 다 옆으로 움직임. 그럼 또 둘 다 부딪힐텐데, 그럼 또 옆으로 움직임. 이런 게 무한 반복. 대기 중이 아닌데도 진전이 없는 것임.

예시:

/* thread_one이 이 함수 실행 */
void* do_work_one(void* param)
{
    int done = 0;
    
    while (!done) {
    	pthread_mutex_lock(&first_mutex);
    	if (pthread_mutex_trylock(&second_mutex)) {
            /**
             * 뭔가를 함
             */
            pthread_mutex_unlock(&second_mutex);
            pthread_mutex_unlock(&first_mutex);
            done = 1;
     	} else {
            pthread_mutex_unlock(&first_mutex);
        }
    }
    
    pthread_exit(0);
}

/* thread_two가 이 함수 실행 */
void* do_work_two(void* param)
{
    int done = 0;
    
    while (!done) {
    	pthread_mutex_lock(&second_mutex);
    	if (pthread_mutex_trylock(&first_mutex)) {
            /**
             * 뭔가를 함
             */
            pthread_mutex_unlock(&first_mutex);
            pthread_mutex_unlock(&second_mutex);
            done = 1;
     	} else {
            pthread_mutex_unlock(&second_mutex);
        }
    }
    
    pthread_exit(0);
}

무한 반복은 보통 스레드가 동시에 실패할 연산을 할 때 발생함. 그래서 임의의 시간마다 재시작하게 해주는 것으로 회피해줄 수 있음. 이게 네트워크 충돌 일어날 때 이더넷에서 사용하는 전략임(역자: CSMA/CA).

8.3. 데드락의 특징

8.3.1. 필수 조건

상호 배제 mutual exclusion. 최소한 한 자원은 반드시 공유 불가능한 상태여야 함; 즉, 한 순간에 한 스레드만 해당 자원을 사용할 수 있음. 다른 스레드가 자원 요청할 경우 자원 반납될 때까지 그 스레드는 대기.
붙잡고 기다리기 hold and wait. 스레드는 반드시 최소한 한 자원을 붙잡은 상태에서 다른 스레드가 현재 붙잡고 있는 추가적인 자원을 얻기 위해 대기해야함.
비선점 no preemption. 자원은 선점될 수 없음; 즉, 스레드가 일 볼 거 다 보고 스스로 반납해줘야함.
순환 대기 circular wait. 대기 중인 스레드 집합 { T0, …, Tn }이 다음 규칙에 따라 반드시 존재해야 함: T0이 T1이 붙잡고 있는 자원을 기다리고, Tn - 1은 Tn이 붙잡고 있는 자원을 기다리고, Tn은 T0이 붙잡고 있는 자원을 기다림.

네 가지 조건 전부 만족해야 데드락이 발생함. 순환 대기 자체에 붙잡고 기다린다는 조건이 내포되어 있으므로 서로 완전히 독립인 관계는 아님. 근데 8.5 절에서 보겠지만 서로 독립적으로 보는게 편함.

8.3.2. 자원 할당 그래프

데드락은 시스템 자원 할당 그래프 system resource-allocation graph라 부르는 방향성 그래프로 더 정확하게 표현해줄 수 있음. 정점 V는 두 가지로 분류: T = { T1, …, Tn은 모든 활성화 스레드, R = { R1, …, Rm }은 모든 자원형.

스레드 Ti에서 자원 Rj로의 방향성 모서리는 Ti → Rj로 표기. 즉, 스레드 Ti가 자원형 Rj의 개체를 요청했으며, 현재 대기 중이라는 의미. 반대 방향 Rj → Ti의 경우 자원형 Rj의 개체가 스레드 Ti에 할당되었다는 의미. 전자를 요청 모서리 request edge, 후자를 할당 모서리 assignment edge라 부름.

스레드는 원으로, 자원은 직사각형으로 보통 그려줌. 요청 모서리는 그냥 화살표, 할당 모서리는 점에서 시작하는 화살표의 형태.

스레드 Ti가 자원형 Rj의 개체를 요청하면 요청 모서리가 우선 그래프에 추가됨. 요청이 수행 가능해지면 요청 모서리는 즉시 할당 모서리로 변함. 더 이상 자원 필요없어지면 자원 반환해주어 할당 모서리가 삭제됨.

위의 자원 할당 그래프는 다음 상황을 의미함:

T, R, E 집합:
- T = { T1, T2, T3 }
- R = { R1, R2, R3, R4 }
- E = { T1 → R1, T2 → R3, R1 → T2, R2 → T2, R2 → T1, R3 → T3 }
자원 개체:
- 자원형 R1 개체 하나
- 자원형 R2 개체 둘
- 자원형 R3 개체 하나
- 자원형 R4 개체 셋
스레드 상태:
- 스레드 T1은 자원형 R2 개체 하나 붙잡고 있고, 자원형 R1 개체 대기 중.
- 스레드 T2은 자원형 R1 개체 하나랑 자원형 R2 개체 하나 붙잡고 있고, 자원형 R3 개체 대기 중.
- 스레드 T3은 자원형 R3 개체 하나 붙잡고 있는 중.

즉, 그래프엔 순환 구조가 없기 때문에 데드락 상태인 스레드가 없음. 만약 순환 구조가 존재한다면 데드락이 있을 수도 있음.

만약 모든 자원형의 개체가 하나인 상태에서 순환 구조가 존재한다면 데드락이 발생했음을 의미함. 만약 순환 구조 내의 자원이 오로지 하나의 개체만 존재하는 자원형이라면 데드락이 발생한 것임. 순환 구조 내의 스레드가 데드락 상태인 것임. 이 경우 이 그래프 내의 순환구조는 데드락 존재 여부의 필요충분조건임.

만약 각 자원형의 개체 수가 둘 이상이라면 순환 구조가 있다고 해서 데드락이 발생했다는 건 아님. 이 경우엔 순환구조는 데드락의 필요조건이지 충분조건은 아님.

만약 스레드 T3가 자원형 R2의 개체 하나를 요청했다고 가정. 그럼 현재 받을 수 있는 개체가 없으니 요청 모서리 T3 → R2를 그려줌.

이러면 최소한 두 개의 순환이 존재함:

T1 → R1 → T2 → R3 → T3 → R2 → T1
T2 → R3 → T3→ R2 → T2

스레드 T1, T2, T3은 데드락 상태임.

위의 그래프의 경우 다음 순환이 존재함:

T1 → R1 → T3 → R2 → T1

이 경우엔 데드락이 없음. T4이 자원형 R2의 개체를 반납해줄 수도 있잖아?

요약하자면 자원 할당 그래프에 순환이 없다면 시스템은 데드락 상태가 아니고, 순환이 있다면 데드락 상태일 수도 있음.

8.4. 데드락 처리법

일반적으로 다음 세 가지 방법으로 처리 가능:

데드락이 일어났었나...? 몰?루
데드락 방지 혹은 회피하는 프로토콜을 통해 시스템이 절대로 데드락 상태가 되지 않도록 해주기.
데드락 상태에 들어갈 수 있다면, 이를 탐지하고 복구해주기.

리눅스, 윈도우즈 등을 포함한 대부분의 운영체제는 첫번째 방법을 사용. 데드락 처리하는 건 보통 두번째 방법을 사용해서 커널 개발자나 어플리케이션 개발자들이 알아서 처리하시라구 ㅋㅋ. 데이터베이스와 같은 시스템의 경우 세번째 방법을 통해 데드락이 발생은 할 수 있되, 복구를 해줄 수 있게 해줌.

당장 위의 세 가지 방법도 적합하지 않다고 하는 연구자들도 있음. 당연히 이 방법들은 혼용해줄 수 있음.

데드락이 절대 발생하지 않도록 해주려면 시스템은 데드락 방지 혹은 데드락 회피 방법을 사용하면 됨. 데드락 방지 deadlock prevention는 최소한 한 필요조건이 성립하지 않도록 해주는 방법임. 자원에 요청을 어떻게 할 수 있느냐에 제약을 걸어서 처리함.

데드락 회피 deadlock avoidance의 경우 운영체제에게 스레드가 어떤 자원을 수명 동안 요청을 할 지 등의 추가 정보를 넘겨주어야 함. 이 추가적인 정보로 운영체제가 각 요청에 대해 스레드가 대기해야하는지 여부를 결정함. 이 요청을 받아들일지 지연시킬지를 위해선 현재 사용 가능한 자원, 현재 스레드가 할당된 자원, 그리고 각 스레드의 앞으로의 요청과 반납에 따라 결정.

이런 거 안해주면 결국 데드락은 발생할 수 밖에 없음. 이 경우 이를 탐지하고 복구하느냐, 내비두냐의 차이.

내비두게 되면 결국 아무것도 해결 못하는 것이지만, 그래도 제일 많이 사용함. 비용이 중요한 부분이긴 함. 데드락 무시하는게 다른 방법보다 훨씬 쌈. 데드락이 애초에 대부분의 시스템에서 자주 발생 안하기에(예를 들어 한 달에 한 번) 그런 것임.

라이브락과 같이 라이브니스 조건에서 복구하는 방법도 데드락에 복구하는 방법으로 사용해줄 수 있음.

8.5. 데드락 방지

8.5.1. 상호 배제

최소한 한 자원이 반드시 공유 불가능한 상태. 공유 가능한 자원은 상호배제적 접근권을 얻을 수 없기에 데드락에 포함하지 않음. 대표적인 예시가 읽기 전용 파일들. 하지만 공유 불가능한 자원이 존재하므로 상호배제 조건을 무시할 순 없음. 대표적인 예시로 상호배제 락은 여러 스레드가 동시에 공유할 수 없으니깐.

8.5.2. 붙잡고 기다리기

이게 절대 안 일어나도록 보장하려면 스레드가 자원을 요청했을 때 다른 자원을 붙잡고 있지 않게 해야 함. 이를 위한 한 프로토콜로는 실행하기 이전에 필요한 자원을 모두 한 방에 요청하고 할당 받는 것임. 당연히 자원 요청의 동적인 성격 상 대부분의 어플리케이션에서는 비실용적인 경우임.

다른 방법으로는 스레드가 아무 것도 안 갖고 있을 때만 자원을 요청하게 만드는 것임. 자원이 여러 자원 요청하고 사용할 수는 있는데, 여기에 추가 자원 요청할거면 지금 할당 받은 애들을 우선 반납하고 전부 한 번에 다시 요청하라는 의미임.

둘 다 단점이 있음. 우선 자원 효용성이 낮다는 것임. 자원이 할당은 될텐데, 사용하지 않는 기간이 너무 긺. 두번째로는 기아 현상이 발생할 수도 있다는 것임.

8.5.3. 비선점

이걸 보장하지 않기 위해서는 다음 프로토콜 쓰면 됨: 스레드가 어떤 자원을 붙들고 있고, 당장 자신에게 할당될 수 없는 자원을 요청한다면, 스레드가 현재 붙들고 있는 모든 자원을 선점시켜줌. 즉, 이 자원들은 암시적으로 반납이 됨. 선점당한 자원들은 스레드가 대기할 자원 목록에 추가해줌. 갖고 있었던 자원들을 다시 되돌려 받고 요청한 자원까지 받은 후에야 다시 재시작함.

이 프로토콜은 CPU 레지스터나 데이터베이스 거래와 같이 쉽게 저장하고 나중에 복구해줘야하는 경우에 자주 사용.

8.5.4. 원형 대기

위의 세 가지 경우를 방지하는 방법은 일반적으로 대부분의 경우 실용적이지 않음. 하지만 원형 대기 조건의 경우 필요조건 하나를 무효화 시켜주어 실질적인 해법을 제공해줌. 이 조건이 참이 아니기를 보장하려면 모든 자원형을 정렬해주어 각 스레드가 증가하는 순서로 자원을 요청하게 해주면 됨.

즉, 각 자원형마다 고유한 정수를 부여하여 이를 바탕으로 순서를 결정함. 수학적으로 보자면 일대일 함수 F: R → N(N은 자연수)을 정의하라는 것임. 예를 들어 처음에 봤던 Pthread 프로그램의 락 순서는 다음과 같음.

프로그램:

/* thread_one이 이 함수 실행 */
void* do_work_one(void* param)
{
    pthread_mutex_lock(&first_mutex);
    pthread_mutex_lock(&second_mutex);
    /**
     * 뭔가를 함
     */
    pthread_mutex_unlock(&second_mutex);
    pthread_mutex_unlock(&first_mutex);
    
    pthread_exit(0);
}

/* thread_two가 이 함수 실행 */
void* do_work_two(void* param)
{
    pthread_mutex_lock(&second_mutex);
    pthread_mutex_lock(&first_mutex);
    /**
     * 뭔가를 함
     */
    pthread_mutex_unlock(&first_mutex);
    pthread_mutex_unlock(&second_mutex);
    
    pthread_exit(0);
}

위의 경우 F(first_mutex) = 1, F(second_mutex) = 5로 둘 수 있음.

각 스레드는 오로지 증가하는 순서로 자원을 요청할 수 있음. 즉, 스레드가 초기에 자원 Ri의 개체를 요청했다면, 다음엔 반드시 F(Rj) > F(Ri)를 만족하는 자원형 Rj의 개체만을 요청할 수 있음. 위의 예시를 보자면 first_mutex와 second_mutex를 동시에 사용하려면 우선 first_mutex를 요청하고나서 second_mutex를 요청해야 함. 다른 방법으로는 Rj 개체를 요청하려면 반드시 F(Ri) ≥ F(Rj)인 모든 자원 Ri을 반납해야해주게 하는 법이 있음. 이때 같은 자원형의 여러 개체가 필요할 경우 각 개체마다 요청을 한 번 씩 해줘야 함.

이 두 프로토콜을 사용할 경우 원형 대기 조건은 거짓이 됨. 모순에 의한 증명으로 증명 가능.

참고로 순서 혹은 계층을 개발한다고 해서 데드락을 방지하는 건 아님. 어플리케이션 개발자들이 이 순서를 따르도록 해줘야함. 근데 락 순서 세우는 건 좀 어려움. 특히 락이 수백 수천 개일 수록 그럼. 이걸 해결하려고 자바 개발자들은 락 할당 순서 함수System.identityHashCode(Object) 메서드를 사용함.

락을 동적으로 얻을 수 있는 경우 락 순서를 강제한다고 해서 데드락을 방지해줄 수 있는 건 아님. 예를 들어 두 계정 간 금액을 전달하는 함수가 있다고 할 때, 경합 조건을 방지하려면 각 계정은 get_lock() 함수로 얻을 수 있는 상호배제 락을 사용할 것임. 이때 두 스레드가 동시에 transaction() 함수를 호출해 서로 다른 계정을 옮겨줄 때 데드락이 발생할 수도 있음. 즉, 한 스레드가

transaction(checking_account, savings_account, 25.0)

를 호출하고 다른 스레드가

transaction(savings_account, checking_account, 50.0)

를 호출하는 경우를 의미함.

아래가 그 코드임:

void transaction(Account from, Account to, double amount)
{
    mutex lock1 = get_lock(from);
    mutex lock2 = get_lock(to);
    
    acquire(lock1);
    	acquire(lock2);
            withdraw(from, amount);
            deposit(to, amount);
	release(lock2);
    release(lock1);
}

리눅스 lockdep 도구
\
자원 획득이 제대로된 순서임을 보장하는 것은 커널 및 어플리케이션 개발자의 책임임. 물론 소프트웨어를 추가적으로 써줄 수도 있긴 함. 리눅스는 데드락이 발생할 수도 있는 상황을 탐지하기 위한 도구인 lockdep를 제공함. lockdep의 대표적인 기능 두 가지:

락 획득 순서는 동적으로 시스템에 의해 관리. lockdep가 순서가 안 지켜지는 걸 감지하는 순간 데드락 발생할 수도 있는 조건이라고 보고함.

리눅스에서는 인터럽트 처리자에 스핀락을 사용해줄 수 있음. 커널이 인터럽트 처리자로도 사용되는 스핀락을 얻을 때 데드락이 또 발생할 수 있음. 락이 붙잡힌 상태에서 인터럽트가 발생하면 인터럽트 처리자가 현재 락을 붙잡는 커널 코드를 선점해버려서 데드락 상태가 발생하게 됨. 이걸 회피하는 일반적인 전략은 인터럽트 처리자에서도 사용되는 스핀락을 얻기 전에 현재 프로세서에서 인터럽트를 비활성화해주는 것임. 커널 코드가 인터럽트 처리자 안에서도 사용되는 락을 얻게 된 상태에 인터럽트가 활성화 되어있음을 lockdep가 감지하는 즉시 데드락 가능성 있는 상황이라고 보고함.

lockdep은 커널 코드 개발 및 수정할 때 도구로서 사용하도록 개발되었지 성능 이슈 때문에 실제 판매용 시스템에 사용하도록 개발되진 않음. 새 장치 드라이버나 커널 모듈이 데드락의 원흉이 될 수도 있는지 확인할 때에나 사용됨. lockdep 개발자들에 따르면 개발했던 2006년 이후 초기에는 시스템의 데드락 발생 보고가 기하급수적으로 줄어들었다고 함. 물론 애초에 lockdep은 커널에서만 사용하도록 설계되었으나 요즘에는 Pthread 상호배제 락으 사용하여 사용자 어플리케이션에서 데드락을 탐지하는 데에도 사용되기도 함. 링크 참고

8.6. 데드락 회피

요청 횟수에 제한을 줘서 해줄 수도 있음. 이 경우 부작용으로는 낮은 장치 효용과 시스템 처리율이 있음.

다른 방법으로는 자원이 요청되는 방법에 대한 추가적인 정보를 요구하는 것임. 예를 들어 두 자원 R1과 R2를 갖는 시스템에서는 스레드 P가 R1을 먼저 요청하고 다음에 R2를 요청한 다음, 둘 다 반납해주는지, Q가 R2를 먼저, 그 다음에 R1을 요청하는지 등의 정보를 알아야하는 것임. 이런 전체적인 그림을 알 수 있게 된다면 시스템이 각 요청마다 이걸 받아줘야, 혹은 대기하기 만들어야 데드락을 피할 수 있을까를 판단해서 처리함.

이걸 구현한 알고리듬마다 정보량과 그 유형이 다 다름. 가장 간단하면서 유용한 모델의 경우 각 스레드가 각 유형별로 필요할 수도 있는 자원의 최대 개수를 선언하게 만드는 것임. 이런 사전 정보가 주어진다면 시스템이 절대 데드락 상태에 빠지지 않도록 해주는 알고리듬을 만들 수 있음. 이런 알고리듬들은 동적으로 자원 할당 상태를 확인해주어 원형 대기 조건이 존재하지 못하도록 보장해줌. 자원 할당 상태 state는 사용 가능한 자원, 그리고 할당된 자원의 수와 스레드가 요청 가능한 최대값으로 정의함.

8.6.1. 안전 상태

시스템 호출이 각 스레드에 어떤 순서에 따라 자원을 할당하면서도 데드락을 회피할 수 있다면, 안전한 상태에 있다고 부름. 이때, 시스템이 안전할 필요충분조건은 안전 순서 safe sequence의 존재성. 연속된 스레드 <T1, …, Tn>가 현재 할당에 대해 안전한 순서려면 각 Ti마다 Ti이 할 수 있는 자원 요청이 현재 사용 가능한 자원 상태 + j < i인 Tj이 붙잡고 있는 자원들에 대해서도 요청 가능해야 함. 이 경우 Ti이 필요로 하는 자원이 당장 사용 불가능하면 Ti는 모든 Tj가 끝날 때까지 대기해야 함. 다 끝나면 Ti이 그제야 필요한 자원을 전부 얻고 자기 할 거 하고 반납하고 종료할 수 있음. Ti이 종료되면 Ti + 1가 자기가 필요한 자원 요청하는 순으로 계속 진행이 됨. 이런 순서가 존재하지 않으면 시스템은 안전하지 않음.

안전 상태는 데드락 상태가 아님. 즉, 데드락 상태는 안전하지 않은 상태임. 안전하지 않은 상태라고 해서 다 데드락인 건 아니지만, 안전하지 않으면 데드락일 가능성이 있음. 안전하지 않은 상태에서는 운영체제가 데드락이 발생할 수도 있는 상황을 방지할 수가 없음.

예시로 보자면, 12 개의 자원과 세 개의 스레드로 이루어진 시스템이 있다고 가정. 스레드 T0는 열 개의 자원을 필요로 하고, T1은 네 개, T2는 아홉 개를 필요로 함. 만약 어느 순간 t0에 T0가 다섯 개의 자원을 들고 있고, T1이 두 개, T2가 두 개의 자원을 들고 있다고 가정. (즉, 놀고 있는 자원이 세 개.)

	최대 수요	현재 수요
T0	10	5
T1	4	2
T2	9	2

t0엔 안전한 상태임. 1, 0, 2 순으로 하면 안전 조건을 만족함.

만약 t1에선 스레드 T2가 하나 더 요청한다고 가정. 그럼 더 이상 안전한 상태가 아님. 이러면 T1만 모든 자원을 할당 받을 수 있게 됨. 이걸 전부 반환하면 시스템에 자원이 네 개 밖에 안 남는데, T0는 다섯 개를 요구하므로 대기해야 함. 마찬가지로 스레드 T2는 여섯 개의 추가적인 자원을 요구할 수도 있으니 대기해야함. 즉, 데드락이 발생함. 여기서 문제가 되는 건 T3에 자원을 더 줬다는 점임.

핵심은 시스템이 언제나 안전한 상태에 머무르게 해야한다는 점임. 시스템 초기엔 당연히 안전한 상태겠지만, 스레드가 현재 사용 가능한 자원 요구할 때마다 시스템은 자원을 당장 할당해줘도 되는지, 대기해야하는지를 결정해야 함. 그리고 오로지 이걸 할당해줘도 시스템이 안전할 때만 요청을 수락해야 함.

즉, 이 방법을 사용할 경우 자원이 사용 가능하더라도 대기해야할 수도 있으므로 자원 효용률이 낮음.

8.6.2. 자원 할당 그래프 알고리듬

만약 각 자원형이 오로지 한 개체로만 구성되어있으면 자원 할당 그래프를 확장해서 데드락 회피를 해줄 수 있음. 기존 개념에 요청 가능 모서리 claim edge라는 모서리 개념을 추가해주는 것임. 요청 가능 모서리 Ti → Rj란 스레드 Ti가 나중에 자원 Rj를 요청할 수도 있다는 의미. 그림으로 그릴 땐 요청 선이랑 똑같이 그리되 중간 중간 끊어진 점선으로 그림. 요청이 실제로 들어가게 되면 요청 가능 모서리가 요청 모서리로 바뀌게 됨. 마찬가지로 Ti가 자원 Rj를 반환하면, 할당 모서리 Rj → Ti가 요청 가능 모서리 Ti → Rj로 바뀜.

참고로 자원은 시스템 전에 요청이 가능해야 함. 즉, 스레드 실행 이전에 모든 요청 가능 모서리가 이미 그래프 상에 표기되어야 한다는 의미. 대신, Ti에 연결된 모든 모서리가 요청 가능 모서리라는 가정하에 실행 전에도 그래프에 그려줄 수 있음.

이제 스레드가 자원을 요청을 하는 경우, 요청 모서리를 할당 모서리로 바꿀 때 전체 그래프에 순환구조가 존재하지 않을 때만 이 요청을 받아줘야 함. 이때 순환구조 탐지 알고리듬으로 n이 시스템 내의 스레드 수일 때 n2 복잡도로 순환을 탐지할 수 있음.

순환이 없으면 할당해도 안전한 상태가 됨. 순환이 있으면 스레드는 우선 요청을 받아들여도 안전해질 때까지 대기함.

이걸 그림으로:

8.6.3. 은행원 알고리듬

각 자원형마다 개체가 여러 개인 자원할당 시스템의 경우 자원 할당 그래프 알고리듬 적용해줄 수 없음. 그래서 덜 효율적이지만 그래도 이 경우에 적용 가능한 은행원 알고리듬 banker's algorithm을 적용. 이름이 은행원인 이유는 이 알고리듬을 은행에 적용해서 은행이 소비자의 소요를 만족하지 못하는 수준으로, 갖고 있는 금액을 절대 할당하지 않도록 보장해줄 수 있게 때문.

새 스레드가 시스템에 추가되면 반드시 필요한 자원형들에 대해 최대 수요를 선언해줘야함. 이 숫자는 시스템의 총 자원 수를 초과해서는 안 됨. 사용자가 자원을 요청하면 시스템은 이걸 들어줬을 때 안전한지 아닌지를 판단. 안전하면 할당해주고, 아니면 안전한 요청이 될 때까지 대기시킴.

은행원 알고리듬 구현하려면 몇 가지 자료구조를 사용해야함. 이 자료구조로 자원 할당 시스템의 상태를 인코딩해줌. 이때 n은 시스템 안의 스레드의 개수이며, m은 자원형의 개수임:

사용 가능 Available. 길이 m인 벡터로, 각 자료형마다 사용 가능한 자원의 개수를 의미.
최대 Max. n × m 행렬로 각 스레드의 자원형 별 최대 수요를 의미.
할당 Allocation. n × m 행렬로 각 스레드의 자원형 별 할당된 자원의 개수를 의미.
수요 Need. n × m 행렬로 각 스레드의 자원별 남은 수요를 의미. 즉, Need[i][j] == Max[i][j] - Allocation[i][j]

당연히 시간에 따라 크기나 값은 달라짐.

은행원 알고리듬을 단순화하기 위해 몇 가지 표기법을 소개. X와 Y가 길이 n의 벡터라 가정. 이때 X ≤ Y일 필요충분조건은 모든 i = 1, …, n인 X[i] ≤ Y[i]에 대해 만족하는 경우. 즉, X = (1, 7, 3, 2)와 Y = (0, 3, 2, 1)일 경우 Y ≤ X임. 또한 Y < X라면 Y ≤ X이면서 Y ≠ X인 경우임.

행렬 Allocation과 Need의 각 행을 벡터로서, 즉 Allocationi, Needi로 표기. Allocationi의 경우 스레드 Ti에 현재 할당된 자원을 의미. Needi의 경우 스레드 Ti이 작업을 완료하기 위해 앞으로 더 요청할 수도 있는 추가적인 자원의 수를 의미.

8.6.3.1. 안전 알고리듬

시스템이 안전한 상태인지 판단하는 알고리듬:

Work와 Finish가 각각 길이가 m, n인 벡터. Work = Available, i = 0, …, n - 1에 대해 Finish[i] = false로 초기화.
다음 조건을 만족하는 첨자 i를 탐색
1. Finish[i] == false
2. Needi ≤ Work
이를 만족하는 i가 없을 경우 4번 단계로 진행
Work = Work + Allocationi
Finish[i] = true
2단계로
모든 i에 대해 Finish[i] == true라면 시스템은 안전한 상태임.

m × n2 복잡도로 상태가 안전한지 판단.

8.6.3.2. 자원 요청 알고리듬

요청이 안전하게 받아들일 수 있는지를 판단하는 알고리듬. Requesti가 스레드 Ti의 요청 벡터. Requesti[j] == k라는 건 스레드 Ti가 자원형 Rj의 개체를 k 개를 요구한다는 의미. 요청이 들어갈 경우 다음 알고리듬이 돎:

Requesti ≤ Needi라면 2단계로. 아니라면 스레드가 최대 수요를 초과했으니 오류 조건을 냄.
Requesti ≤ Available이라면 3 단계로. 아니라면 현재 자원이 부족하므로 대기해야 함.
시스템이 일단 자원을 할당했다고 가정:
Available = Available - Requesti
Allocationi = Allocationi + Requesti
Needi = Needi - Requesti
만약 결과적으로 나온 자원 할당 상태가 안전하다면 거래가 완료되었으므로 스레드 Ti에 자원을 할당. 아니라면 Requesti에 대해 대기해야하고, 시스템은 기존 상태로 복구해줌.

8.6.3.3. 그림으로 보는 예시

스레드가 다섯 개, 자원형은 A, B, C 세 가지. A는 개체가 열 개, B는 다섯 개, C는 일곱 개:

	Allocation A B C	Max A B C	Available A B C
T0	0 1 0	7 5 3	3 3 2
T1	2 0 0	3 2 2
T2	3 0 2	9 0 3
T3	2 1 1	2 2 2
T4	0 0 2	4 3 3

Need 행렬의 내용물은 Max - Allocation로 정의함:

	Need A B C
T0	7 4 3
T1	1 2 2
T2	6 0 0
T3	0 1 1
T4	4 3 1

시스템은 현재 안전한 상태임. 1, 3, 4, 2, 0이면 안전함. 만약 스레드 1에 A형 자원 하나 추가하고, C형 자원 두 개, 즉 Request1 = (1, 0, 2)를 요청한다면? 우선 Request1 ≤ Available인지 확인. (1, 0, 2) ≤ (3, 3, 2)이므로 참이므로, 이 요청을 받아들였다 가정하고 상태 확인:

	Allocation A B C	Need A B C	Available A B C
T0	0 1 0	7 4 3	2 3 0
T1	3 0 2	0 2 0
T2	3 0 2	6 0 0
T3	2 1 1	0 1 1
T4	0 0 2	4 3 1

이제 시스템 안전한지 판단하기 위해 안전 알고리듬 돌려보면 1, 3, 4, 0, 2 순서가 안전 요구사항 만족하는 걸 알 수 있으므로, 요청 받아줄 수 있음.

하지만 이 경우 T4의 (3, 3, 0) 요청은 받을 수 없음. 자원이 모자라니까. T0의 (0, 2, 0)도 마찬가지임. 자원은 있는데 주면 안전하지 않게 됨.

8.7. 데드락 탐지

데드락 방지나 데드락 회피 알고리듬 안 쓰면 적어도 다음 중 하나는 제공해야함:

시스템의 상태를 보고 데드락이 발생했는지를 판단하는 알고리듬
데드락에서 복구하는 알고리듬

물론 이 방법 사용하면 여기에 필요한 정보를 유지하고 탐지 알고리듬을 돌린다는 런타임 부담에다가 데드락에서 복구할 때 발생할 수 있는 손실도 발생하긴 함.

8.7.1. 자원 당 개체 하나

각 자원마다 개체가 하나 밖에 없다면 자원 할당 그래프랑 유사한 대기 wait-for 그래프를 사용하면 됨. 자원 할당 그래프에서 자원 노드를 없애고 적절한 모서리를 줄여주면 됨.

대기 그래프에서 Ti에서 Tj로의 모서리는 스레드 Ti가 자기가 필요한 자원을 Tj가 반환하기를 배기한다는 의미임. 대기 그래프에서 모서리 Ti → Tj의 필요충분조건은 대응하는 자원 할당 그래프가 임의의 자원 Rq에 대해 모서리 Ti → Rq와 모서리 Rq → Tj를 가질 경우임.

즉, 데드락의 존재 여부의 필요충분조건은 그래프가 순환을 가질 경우임. 데드락을 탐지하기 위해 시스템은 대기 그래프를 유지하고 주기적으로 그래프 내에 순환 구조를 탐지하는 알고리듬을 실행해줘야 함. n이 그래프 내의 정점 개수일 때 이 탐지 알고리듬은 O(n2)이 걸림.

Java 스레드 덤프를 통한 데드락 탐지

Java가 명시적으로 데드락 탐지 기능을 제공하지는 않지만, 스레드 덤프 thread dump로 데드락 발생했는지 분석 가능. 스레드 덤프는 현재 Java 어플리케이션의 스레드들의 상태를 보여주는 매우 유용한 디버깅 도구임. 스레드 덤프가 생성되면 JVM이 대기 그래프를 통해 순환 구조를 탐지하여 데드락 탐지하여 보고함. 실행 중인 어플리케이션의 스레드 덤프 생성하려면 명령줄에서 Ctrl-L(UNIX, Linux, macOS) 혹은 Ctrl-Break (Windows) 명령어를 주면 됨.

8.7.2. 자원 당 개체 여러 개

대기 그래프 사용 불가. 은행원 알고리듬에서 사용했던 것과 유사한 자료구조를 통한 탐지 알고리듬을 사용해야 함.

사용 가능. 길이가 m인 벡터. 각 자원별 가용한 자원 수.
할당. n × m 행렬. 스레드 별 각 자원 할당량.
요청. n × m 행렬. 스레드 별 현재 요청량. Request[i][j] == k일 때, 스레드 Ti은 자원 Rj k 개를 더 요구한다는 뜻임.

벡터 간의 ≤ 관계는 8.6.3 절과 동일함. 탐지 알고리듬은 단순히 완성해야하는 남아있는 모든 가능한 할당 시퀀스를 확인해줌. 8.6.3 절의 알고리듬과 비교하면서 읽어보도록:

일과 완료가 각각 길이 m, n의 벡터. 일 = 사용 가능으로 초기화하고, 할당i ≠ 0이라면 완료[i] = false고, 아니라면 true임.
다음 둘을 만족하는 색인 i를 탐색
1. 완료[i] == false
2. 요청i ≤ 일
  만약 이런 i가 존재하지 않을 경우 4단계로
일 = 일 + 할당i
완료[i] = true
2단계로
만약 완료[i] == false인 i가 존재한다면, 시스템은 현재 데드락 상태임. 이때 스레드 Ti가 데드락 상태인 것임.

m × n2 번의 연산 필요.

요청i ≤ 일(2.2 단계)을 만족하는 순간 왜 스레드 Ti의 자원을 다시 되찾는지(3단계) 궁금할 수도 있음. Ti가 현재 데드락과 연관되어있지 않다는 것을 아니까(요청i ≤ 일) 좀 낙관적으로 생각해서 Ti가 작업을 완료하기 위해 추가적인 자원이 앞으로 필요없다고 가정해버리는 것임. 그러므로 현재 할당된 자원을 전부 시스템에 반환할 것임. 만약 가정이 틀렸다면 데드락이 나중에 발생할 수도 있다는 것임. 발생한다면 다음 번에 데드락 탐지 알고리듬 돌릴 때 탐지해낼 수 있음.

이 알고리듬을 보이기 위해 스레드 다섯 개에 자원이 세 가지인 예시로 이해. 자원 A는 일곱 개, B는 두 개, C는 여섯 개:

	할당 A B C	요청 A B C	사용 가능 A B C
T0	0 1 0	0 0 0	0 0 0
T1	2 0 0	2 0 2
T2	3 0 3	0 0 0
T3	2 1 1	1 0 0
T4	0 0 2	0 0 2

알고리듬 실행 시 시퀀스 <T0, T2, T3, T1, T4>의 경우에 모든 완료[i]가 참이 되므로 이 시스템은 데드락 상태가 아님을 알 수 있음.

여기에 세번째 스레드가 자원 C 하나 더 요구했다고 가정:

	요청 A B C
T0	0 0 0
T1	2 0 2
T2	0 0 1
T3	1 0 0
T4	0 0 2

이제는 데드락 상태임. 첫번째 스레드의 자원은 되찾을 수 있는데, 다른 스레드의 요구를 들어주기에는 사용 가능한 자원이 불충분함. 즉, 데드락이 존재하며, 첫번째 스레드 빼고는 다 데드락 상태임.

데이터베이스에서 데드락 관리

데이터베이스 시스템이 데드락 관리하는 교과서임. 데이터베이스에 대한 갱신은 일종의 거래 transaction로 보며, 데이터의 무결성을 보장하기 위해 락을 사용함. 한 거래에는 여러 락을 사용할 수도 있으므로 동시에 거래 여러 번할 경우 데드락 발생할 수 있음. 이걸 관리하기 위해 대부분의 거래형 데이터베이스 시스템은 데드락 탐지 및 복구 메커니즘을 구현해둠. 데이터베이스 서버가 주기적으로 대기 그래프에 순환 구조를 찾아내서 여러 거래들 중에서 데드락 탐지함.데드락이 탐지되면 해당 거래를 중단시키고 롤백시켜 해당 거래가 갖고 있던 락을 반환시켜 데드락에서 나머지 거래들을 풀어줌. 나머지 거래가 재개되면 중단시킨 거래를 재개함. 데드락에 걸린 거래 중 누구를 중단시킬지는 데이터베이스 시스템에 달린 문제임; 예를 들어 MySQL은 삽입하거나 갱신하거나 삭제할 행의 개수가 가장 적은 거래를 선택함.

8.7.3. 탐지 알고리듬 용도

탐지 알고리듬을 언제 돌려야?

이 질문은 다음 두 가지 질문으로 답할 수 있음:

얼마나 자주 데드락 발생?
발생하면 얼마나 많은 스레드에 영향?

데드락 자주 발생한다면 탐지 알고리듬을 자주 호출해야함.

데드락은 한 스레드가 당장 들어줄 수 없는 요청을 할 때만 발생함. 이 요청이 기차 놀이 중인 스레드를 연쇄적으로 풀어줄 수 있는 요청일 수도 있음. 극단적으로는 매번 요구사항을 들어줄 수 없을 때마다 데드락 탐지 알고리듬을 돌릴 수도 있긴 함. 이러면 단순히 데드락 발생한 스레드 뿐만 아니라 누가 데드락을 "야기"했는지도 알 수 있음. (실제로는 데드락 걸린 스레드가 전부 자원 그래프의 순환 구조의 링크 역할을 할 수도 있으니 전부 동시에 데드락의 원인에 기여하고 있을 수도 있음.) 자원이 여러 가지면 한 요청에 의해 자원 그래프에 여러 순환 구조가 생길 수도 있음. 이때 각 순환 구조는 가장 최근 요청에 의해 완료되며, 하나의 식별 가능한 스레드에 의해 "야기"됨.

당연히 이거 부담 엄청됨. 차라리 정해진 간격마다 호출하는게 비용이 저렴함. 한 시간에 한 번이나 CPU 효용이 40% 떨어질 때마다 등이 있음. 대신 이땐 누가 데드락을 "야기"했는지는 모름.

8.8. 데드락 복구

탐지한 다음엔 연산자에게 데드락 발생했으니 너가 알아서 하라고 하는 방법이 있고, 다른 방법으로는 시스템이 자동으로 데드락 상태에서 복구 recover하게 해주는 방법이 있음. 데드락을 부수는 방법도 두 가지임. 하나는 그냥 스레드 하나 종료 시켜서 강제로 순환 대기 부수는 거고, 다른 하나는 데드락 상태의 스레드의 자원을 선점시켜버리는 거임.

8.8.1. 프로세스 및 스레드 종료

두 가지 방법이 있음. 둘 다 시스템이 종료된 프로세스의 자원을 되돌려 받음.

데드락 프로세스 전부 종료시킴. 확실히 데드락은 없애주는데 댓가가 좀 큼. 이 프로세스가 좀 오랜 기간 돌아가고 있을 수도 있으니 중간 결과물을 반드시 버리고 나중에 다시 재연산해줘야할 수도 있음.
데드락 순환 구조가 사라질 때까지 프로세스 하나 씩 없앰. 하나 중단시킬 때마다 데드락 탐지 알고리듬을 다시 돌려야하니 상당한 부담이 되긴 함.

프로세스 중단이 그리 쉬운게 아님. 파일 갱신 도중이었다면 파일이 손상될 수도 있음. 만약 상호배제 락을 가진 상태에서 공유 자료를 수정 중이라면 반드시 락을 다시 사용 가능한 상태로 복구해줘야 함. 물론 공유 자료의 무결성은 몰?루.

만약 일부 종료 방법을 사용하면 누구를 종료할 지를 결정해야함. 이건 CPU 스케줄링처럼 사실상 정책으로 결정할 문제임. 그냥 경제적인 질문임; 누구 종료 비용이 제일 쌀까? 근데 문제가 최소 비용이라는게 정확하게 정의가 안된다는 것임. 여러 요소가 있음:

프로세스의 우선순위
얼마나 오랜 기간 돌았는지, 그리고 주어진 작업을 완료하기까지 얼마나 더 필요할지
프로세스가 사용한 자원의 개수와 유형 (예를 들어 자원이 선점하기 쉬운지)
프로세스가 완료할 때까지 자원이 얼마나 더 필요한지
프로세스를 얼마나 종료해야하는지.

8.8.2. 자원 선점

선점으로 데드락 없애주면 데드락 순환 구조가 깨질 때까지 연속적으로 프로세스에서 여러 자원을 선점해주어 이 자원을 다른 프로세스한테 줘야함.

선점으로 처리할 경우 다음 문제 처리해야함:

피해자는 누구? 그래서 누구 자원을 뺏을 것임? 프로세스 종료 방식처럼 결국 비용을 최소화하는 방향으로 선점해야함. 여기서 비용에는 데드락 상태의 프로세스가 가진 자원 개수라든가 지금까지 소모한 실행 시간 등이 있음.
롤백. 프로세스에서 자원 선점할 경우 해당 프로세스는 정상적으로 실행을 지속시킬 수 없음. 필요한 자원을 뺏겼으니까. 그러므로 이 프로세스를 안전한 상태로 롤백시켜주고 해당 상태에서 재시작해줘야함.
사실 보통 안전한 상태가 뭔지 잘 모르니까 가장 간단한 해법은 그냥 완전 롤백해버리는 것임. 프로세스 중단하고 재시작해버리기. 당연히 데드락 없앨 만큼만 롤백하는게 제일 효과적이겠지만, 이러려면 시스템이 실행 중인 모든 프로세스의 상태에 추가적인 정보를 계속 갖고 있어야함.
기아 상태. 기아가 발생하지 않도록 어떻게 보장? 즉, 자원이 언제나 같은 프로세스로부터 선점되지 않도록 어떻게 보장?
단순히 비용만으로 결정할 경우 계속 똑같은 놈이 피해자가 될 수도 있음. 그러므로 평생 자기 할 일을 못하게 될 수도 있음. 즉, 실무에서는 이걸 반드시 처리해줘야 함. 물론 한정된 횟수만큼 선점이 될 수 있도록 해줄 수도 있음. 가장 일반적인 방법은 롤백 횟수를 비용에 포함시키느 것임.

8.9. 요약

• 프로세스의 집합이 주어졌을 때, 이 집합의 모든 프로세스가 다른 프로세스가 실행해야하는 이벤트를 대기 중인 경우에 데드락이 발생함.

데드락의 네 가지 필요 조건:
1. 상호 배제
2. 붙잡고 기다리기
3. 비선점
4. 순환 대기
  데드락은 오로지 이 네 가지를 전부 만족해야 발생 가능.
데드락은 자원 할당 그래프로 모델링 가능. 이때 순환 구조가 데드락을 의미.
네 가지 필요 조건 중 하나라도 발생하지 않음을 보이면 데드락 방지 가능. 그 중 가장 실용적인 방법이 순환 대기 없애기임.
데드락은 은행원 알고리듬으로 회피 가능. 은행원 알고리듬은 어떤 자원 요청을 들어줄 경우 시스템이 데드락이 발생할 수도 있는, 안전하지 않은 상태가 될 경우에 요청을 들어주지 않음.
데드락 탐지 알고리듬은 실행 중인 시스템에서 프로세스와 자원을 평가하여 프로세스가 데드락 상태인지를 확인함.
데드락이 발생할 경우 순환 대기 중인 프로세스 중 하나를 중단시키든, 데드락에 걸린 프로세스에 할당된 자원을 선점하든 해서 데드락 상태로부터 복구를 해야함.

‍주민하

개발자

이전 포스트

운영체제 (공룡책) - 7

다음 포스트

운영체제 (공룡책) - 8

운영체제

3. 프로세스 동기화

8. 데드락

단원 목표

8.1. 시스템 모델

8.2. 멀티스레드 어플리케이션에서의 데드락

8.2.1. 무한 반복

8.3. 데드락의 특징

8.3.1. 필수 조건

8.3.2. 자원 할당 그래프

8.4. 데드락 처리법

8.5. 데드락 방지

8.5.1. 상호 배제

8.5.2. 붙잡고 기다리기

8.5.3. 비선점

8.5.4. 원형 대기

리눅스 `lockdep` 도구

8.6. 데드락 회피

8.6.1. 안전 상태

8.6.2. 자원 할당 그래프 알고리듬

8.6.3. 은행원 알고리듬

8.6.3.1. 안전 알고리듬

8.6.3.2. 자원 요청 알고리듬

8.6.3.3. 그림으로 보는 예시

8.7. 데드락 탐지

8.7.1. 자원 당 개체 하나

Java 스레드 덤프를 통한 데드락 탐지

8.7.2. 자원 당 개체 여러 개

데이터베이스에서 데드락 관리

8.7.3. 탐지 알고리듬 용도

8.8. 데드락 복구

8.8.1. 프로세스 및 스레드 종료

8.8.2. 자원 선점

8.9. 요약

운영체제 (공룡책) - 7

운영체제 (공룡책) - 9

0개의 댓글

운영체제 (공룡책) - 8

운영체제

3. 프로세스 동기화

8. 데드락

단원 목표

8.1. 시스템 모델

8.2. 멀티스레드 어플리케이션에서의 데드락

8.2.1. 무한 반복

8.3. 데드락의 특징

8.3.1. 필수 조건

8.3.2. 자원 할당 그래프

8.4. 데드락 처리법

8.5. 데드락 방지

8.5.1. 상호 배제

8.5.2. 붙잡고 기다리기

8.5.3. 비선점

8.5.4. 원형 대기

리눅스 lockdep 도구

8.6. 데드락 회피

8.6.1. 안전 상태

8.6.2. 자원 할당 그래프 알고리듬

8.6.3. 은행원 알고리듬

8.6.3.1. 안전 알고리듬

8.6.3.2. 자원 요청 알고리듬

8.6.3.3. 그림으로 보는 예시

8.7. 데드락 탐지

8.7.1. 자원 당 개체 하나

Java 스레드 덤프를 통한 데드락 탐지

8.7.2. 자원 당 개체 여러 개

데이터베이스에서 데드락 관리

8.7.3. 탐지 알고리듬 용도

8.8. 데드락 복구

8.8.1. 프로세스 및 스레드 종료

8.8.2. 자원 선점

8.9. 요약

운영체제 (공룡책) - 7

운영체제 (공룡책) - 9

0개의 댓글

리눅스 `lockdep` 도구