교착상태(Deadlock)

2021. 4. 15. 17:44

교착상태(Deadlock)

두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다.

교착상태의 조건

상호 배제(Mutual exclusion)

프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구한다.

점유 대기(Hold and wait)

프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.

비선점(No preemption)

프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다.

cf. 선점(preemption)

한 프로세스가 CPU를 할당받아 실행 중이라도

다른 프로세스가 현재 프로세스를 중지시키고 CPU를 강제적으로 뺏을 수 있는 스케줄링 방식

순환 대기(Circular wait)

각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.

이 조건 중에서 한 가지라도 만족하지 않으면 교착 상태는 발생하지 않는다.

이 중 순환 대기 조건은 점유 대기 조건과 비선점 조건을 만족해야 성립하는 조건이므로,

위 4가지 조건은 서로 완전히 독립적인 것은 아니다.

교착상태 관리 방법

교착 상태의 예방

상호 배제 조건의 제거

교착 상태는 두 개 이상의 프로세스가 공유 가능한 자원을 사용할 때 발생하는 것이므로
공유 불가능한, 즉 상호 배제 조건을 제거하면 교착 상태를 해결할 수 있다.

점유와 대기 조건의 제거

한 프로세스에 수행되기 전에 모든 자원을 할당시키고 나서 점유하지 않을 때에는 다른 프로세스가 자원을 요구하도록 하는 방법이다.
자원 과다 사용으로 인한 효율성, 프로세스가 요구하는 자원을 파악하는 데에 대한 비용, 자원에 대한 내용을 저장 및 복원하기 위한 비용, 기아 상태, 무한 대기 등의 문제점이 있다.

비선점 조건의 제거

비선점 프로세스에 대해 선점 가능한 프로토콜을 만들어 준다.

순환 대기 조건의 제거

자원 유형에 따라 순서를 매긴다.

이 교착 상태의 해결 방법들은 자원 사용의 효율성이 떨어지고 비용이 많이 드는 문제점이 있다.

교착상태 회피

자원이 어떻게 요청될지에 대한 추가 정보를 제공하도록 요구하는 것으로 시스템에 순환 대기가 발생하지 않도록 자원 할당 상태를 검사한다.

교착 상태 회피하기 위한 알고리즘으로 크게 두 가지가 있다.

자원 할당 그래프 알고리즘 (Resource Allocation Graph Algorithm)은행원 알고리즘 (Banker's algorithm)

교착상태 무시

예방 혹은 회피 기법을 프로그래밍해서 넣으면 성능에 큰 영향을 미칠 수 있게 된다.

그렇기 때문에 교착상태의 발생 확률이 비교적 낮은 경우 별다른 조치를 취하지 않는다.

교착상태가 발생할 수 있는 코드

아래 예제는, 오라클 공식문서에 있는 deadlock에 대한 부분이다.

💡 예제 케이스에 대한 번역

Alphonse와 Gaston은 친구이며 예의를 지키는 위대한 신자입니다.
예의 때문에 친구에게 절을 할 때 친구가 절을 끝낼 때까지 절을 유지해야 합니다.
그러나 이는 두 친구가 동시에 서로에게 절할 가능성을 고려하진 않습니다.
이 예제 애플리케이션인 Deadlock은 이러한 가능성을 보여줍니다.

package com.ssonsh.study.threadtest;
public class Deadlock {
    static class Friend {
        private final String name;
        public Friend(String name) {
            this.name = name;
        }
        public String getName() {
            return this.name;
        }
        public synchronized void bow(Friend bower) {
            System.out.format("%s: %s"
                              + "  has bowed to me!%n",
                              this.name, bower.getName());
            bower.bowBack(this);
        }
        public synchronized void bowBack(Friend bower) {
            System.out.format("%s: %s"
                              + " has bowed back to me!%n",
                              this.name, bower.getName());
        }
    }

    public static void main(String[] args) {
        final Friend alphonse =
            new Friend("Alphonse");
        final Friend gaston =
            new Friend("Gaston");
        new Thread(new Runnable() {
            public void run() { alphonse.bow(gaston); } // 별도의 스레드 생성 후 절
        }).start();
        new Thread(new Runnable() {
            public void run() { gaston.bow(alphonse); } // 별도의 스레드 생성 후 절
        }).start();
    }
}


Alphonse: Gaston  has bowed to me!
Gaston: Alphonse  has bowed to me!

이 케이스에서(Deadlock 이 발생한) bowBack을 호출하려고 할 때 두 스레드가 모두 차단될 가능성이 매우 높다.
각 스레드는 다른 스레드가 절을 종료하기를 기다리고 있기 때문에 어느 블록도 끝나지 않는 상태가 된다.

참고로 VisualVM과 같은 툴을 이용하여 스레드 덤프(Thread Dump)를 떠서 교착상태의 상태를 확인할 수 있다.

💡 스레드 덤프(Thread Dump)

프로세스에 속한 모든 스레드들의 상태를 기록(snapshot)한 것이다.
각 스레드들은 ‘스택 추적(stack trace)’ 형태로 보여진다. 스레드들은 직접 실행시킨 자바 응용 프로그램의 스레드와 JVM 내부적으로 존재하는 스레드로 나뉘게 된다.

출처

교착상태 코드 예제

docs.oracle.com/javase/tutorial/essential/concurrency/deadlock.html

교착상태를 피하는법

docs.oracle.com/cd/E37838_01/html/E61057/guide-35930.html

'운영체제, 컴퓨터구조' 카테고리의 다른 글

콘텍스트 스위칭(Context Switching) (0)	2021.04.18

으뜸별