[8] 교착상태

준제로·2023년 8월 28일

운영체제 공룡책 읽기

목록 보기
8/9

다중 프로그래밍 환경에서는 여러 스레드가 한정된 자원을 사용하려고 서로 경쟁할 수 있다.

한 스레드가 자원을 요청했을 때, 그 시각에 그 자원을 사용할 수 없는 상황이 발생할 수 있고, 그때는 스레드가 대기상태로 들어간다.

⇒ 이처럼 대기 중인 스레드들이 결코 다시는 그 상태를 변경시킬 수 없으면 이런 상황을 교착상태라한다. (그들이 요청한 자원들이 다른 스레드들에 의해서 점유되어 있고 그들도 다 대기상태에 있기 떄문에)

교착상태: 프로세스 집합 내의 모든 프로세스가 그 집합의 다른 프로세스에 의해서만 일어날 수 있는 이벤트를 기다리는 상황

이 장에서는 운영체제 개발자 뿐만 아니라 응용 프로그램 개발자들도 교착 상태를 예방하거나 다루기 위해 사용할 수 있는 방법들을 논의한다. 보통 운영체제들은 교착 상태 예방 기능을 제공하지 않기 때문에, 교착 상태가 없는 프로그램을 설계하는 것은 전적으로 프로그래머의 책임으로 남는다.

다중 코어 시스템에서의 병행 및 병렬 처리 증대에 대한 요구가 계속됨에 따라 교착상태 뿐만 아니라 기타 라이브니스 장애 문제가 점점 어려워지고 있다.

8.1 시스템 모델

시스템은 경쟁하는 스레드들 사이에서 분배되어야 할 유한한 수의 자원들로 구성되어있다. Mutex락과 세마포 같이 6장에서 설명한 다양한 동기화 도구도 시스템 자원이며, 현대 컴퓨터 시스템에서는 가장 일반적인 교착 상태의 발원지이다.

⇒ 다중 스레드 응용 개발자는 반드시 교착 상태의 가능성을 염두에 두어야한다. 6장에서 선보인 락킹 도구들은 경쟁 조건을 회피하도록 설계되었다. 그러나 이러한 도구를 사용할 때, 개발자는 락이 획득되고 방출되는 방식에 대해 주의를 기울여야한다. 그렇지 않을 경우, 다음에 설명한 것 처럼 교착 관계가 발생할 수 있다.

8.2 다중 스레드 응용에서의 교착 상태

먼저 POSIX mutex락을 사용하여 다중 스레드 Pthread 프로그램에서 어떻게 교착상태가 발생할 수 있는지를 살펴보자.

  • pthread_mutex_init() 함수는 가용한 mutex를 초기화한다.
  • mutex락은 pthread_mutex_lock()과 pthread_mutex_unlock()함수를 이용하여 획득되고 방출된다.
  • 한 스레드가 잠긴 mutex 락을 획득하려고 시도하면, pthread_mutex_lock() 함수 호출은 mutex 락의 소유주가 pthread_mutex_unlock() 함수를 호출할 때까지 이 스레드를 봉쇄한다.
pthread_mutex_t first_mutex;
pthread_mutex_t second_mutex;

pthread_mutex_init(&first_mutex, NULL);
pthread_mutex_init(&second_mutex, NULL);
  • 두 mutex락이 다음 코드에 의해 생성되고 초기화된다.
/* thread_one은 이 함수를 실행한다 */
void* do_work_one(void* param)
{
    pthread_mutex_lock(&first_mutex);
    pthread_mutex_lock(&second_mutex);
    /**
     * Do some work
     */
    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);
    /**
     * Do some work
     */
    pthread_mutex_unlock(&first_mutex);
    pthread_mutex_unlock(&second_mutex);

    pthread_exit(0);
}

⇒ 그림 8.1 교착 상태 예제

  • 두 스레드가 생성되고 두 스레드는 mutex락에 대한 접근 권한을 가진다.
  • thread_one과 thread_two는 그림 8.1에 보인 것 처럼 각각 do_work_one(), do_work_two() 함수를 실행한다.
  • thread_one이 (1) first_mutex ⇒ (2) second_mutex 순서로 mutex락을 획득하려고 하고
  • 동시에 thread_two는 (1)second_mutex ⇒ (2) first_mutex 순서로 mutex락을 획득하려한다.
  • thread_one이 first_mutex를 획득하고, thread_two가 second_mutex를 획득하게 되면 교착 상태가 가능하다.

⇒ 교착 상태가 가능하더라도 thread_two가 락을 획득하려고 시도하기 전에 thread_one이 first와 second_mutex를 획득하고 방출할 수 있다면 교착상태는 발생하지 않는다.

이처럼 이 예제는 교착상태를 다루는 데에서의 문제를 잘 설명하는데, 어떤 특정 스케줄링 상황에서만 발생할 수 있는 교착상태를 식별하고 검사하는 작업은 어렵다.

8.2.1 Livelock

라이브락은 또 다른 형태의 라이브니스 장애이다. 교착상태와 유사하다.

  • 둘 다 두 개 이상의 스레드가 진행되는 것을 방해하지만 진행할 수 없는 이유가 서로 다르다.
  • 교착 상태가 어떤 스레드 집합의 모든 스레드가 같은 집합에 속한 다른 스레드에 의해서만 발생할 수 있는 이벤트를 기다리면서 봉쇄되면 발생하는 반면,
  • 라이브락은 스레드가 실패한 행동을 계속해서 시도할 때 발생한다.
    • ex) 복도를 지나가려 할 때, 한 사람은 오른쪽으로 움직이고 한 사람은 왼쪽으로 움직이면서 여전히 서로의 진행을 방해한다. 그런 다음 한 사람은 왼쪽으로 이동하고 다른 한 사람은 오른쪽으로 움직인다. ⇒ 봉쇄되진 않았지만 앞으로 진행 x
/* thread_one은 이 함수를 실행한다 */
void* do_work_one(void* param)
{
    int done = 0;

    while (!done) {
    	pthread_mutex_lock(&first_mutex);
    	if (pthread_mutex_trylock(&second_mutex)) {
            /**
             * Do some work
             */
            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)) {
            /**
             * Do some work
             */
            pthread_mutex_unlock(&first_mutex);
            pthread_mutex_unlock(&second_mutex);
            done = 1;
     	} else {
            pthread_mutex_unlock(&second_mutex);
        }
    }

    pthread_exit(0);
}

pthread_mutex_trylock()을 사용하도록 그림 8.1의 예제를 다시 작성했다..

  • 스레드 1이 first_mutex를 획득한 후, 스레드 2가 second_mutex를 획득하면 이 상황은 라이브락으로 이어질 수 있다.
  • 그런 다음 각 스레드는 pthread_mutex_trylock()을 호출하여 실패하고,
  • 각자의 락을 해제한 후 동일한 행동을 무한정 반복한다.

⇒ 라이브락은 일반적으로 스레드가 실패한 작업을 동시에 재시도할때 발생한다. 따라서 일반적으로 각 스레드가 실패한 행동을 재시도하는 시간을 무작위로 정하면 회피가능하다.

이 방법은 정확히 네트워크 충돌이 발생할 때 Ethernet 네트워크가 취하는 접근법이다. (충돌이 발생한 직후 패킷을 재전송하려 시도하는 대신, 충돌한 호스트는 재전송을 시도하기 전 임의의 시간 동안 한 발뒤로 물러난다)

라이브락은 교착 상태만큼 흔히 일어나진 않지만, 병행 응용 프로그램을 설계하는 데 있어 어려운 문제이며 교착 상태와 같이 특정 스케줄링 상황에서만 발생할 수 있다.

8.3 교착 상태 특성

8.3.1 필요조건들

교착 상태는 한 시스템에 다음 네 가지 조건이 동시에 성립될 때 발생할 수 있다.

  1. 상호배제(mutual exclusion): 최소한 하나의 자원이 비공유 모드로 점유되어야한다.

    비공유 모드에서는 한번에 한 스레드만이 그 자원을 사용할 수 있다. 다른 스레드가 그 자원을 요청하면, 요청 스레드는 자원이 방출될 때까지 반드시 지연되어야한다.

  2. 점유하며 대기(hold-and-wait): 스레드는 최소한 하나의 자원을 점유한 채, 현대 다른 스레드에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기해야한다.

  3. 비선점(no preemption): 자원들을 선점할 수 없어야한다.
    즉, 자원이 강제적으로 방출될 수 없고, 점유하고 있는 스레드가 태스크를 종료한 후 그 스레드에 의해 자발적으로만 방출될 수 있다.

  4. 순환 대기(circular wait): 대기하고 있는 스레드의 집합에서 T0 → T1→ T2→ .. → Tn→ T0 이런 식으로 circular하게 다른 스레드가 점유하고 있는 자원을 대기한다.

8.3.2 자원 할당 그래프_Resource-Allocation Graph

교착 상태는 시스템 자원 할당 그래프라고 하는 방향 그래프로 더욱 정확하게 기술할 수 있다.

  • 정점 V집합과 간선 E의 집합으로 구성된다.
  • V집합은 활성 스레드 집합인 T, 자원 유형의 집합인 R 두 가지 유형으로 구분된다.
  • T→ R은 요청 간선(request edge)
  • R → T는 할당간선(assignment edge)


그림 8.3 그림 8.1프로그램의 자원 할당 그래프

위의 자원 할당 그래프는 그림 8.1의 프로그램에서 교착 상태 상황을 보여준다.

⇒ 자원 할당 그래프의 정의로부터 우리는 만일 그래프가 사이클을 포함하지 않으면 시스템 내 어느 스레드도 교착상태가 아니라는 것을 보일 수 있다. 반면, 그래프가 사이클을 포함하면 교착상태가 존재할 수 있다.

  • 만일 각 자원 유형이 정확하게 하나의 인스턴스만 가진다면, 하나의 사이클은 교착 상태가 발생하였음을 암시한다.
    • 이 경우에는 그래프 내의 한 사이클은 교착 상태가 존재하기 위한 필요, 충분 조건이 된다.
  • 만일 각 자원 유형이 여러 개의 인스턴스를 가지며, 사이클이 반드시 교착 상태가 발생했음을 의미하지는 않는다.
    • 이 경우 그래프 내의 한 사이클은 교착 상태가 존재하는 데 필요 조건이며, 충분 조건이 되지는 않는다.


그림 8.6 사이클이 있으면서 교착 상태가 아닌 자원 할당 그래프

T1→ R1→ T3 → R2 → T1의 사이클을 갖는다. 그러나 위 예에서는 교착 상태가 없다. 프로세스 T4가 자원 유형 R2를 방출할 수 있다. → 이어 이 자원이 T3에 할당될 수 있고, 그 경우 사이클이 없어진다.

요약하자면,

  • 자원 할당 그래프에 사이클이 없다면 시스템은 교착 상태가 아니다.
  • 반면에, 사이클이 있다면 시스템은 교착상태일수도 있고 아닐 수도 있다.

8.4 교착 상태 처리 방법

원칙적으로 교착 상태 문제를 처리하는 데는 다음과 같은 세가지 다른 방법이 있다.

  • 문제를 무시하고, 교착상태가 시스템에서 절대 발생하지 않는 척한다.
  • 시스템이 결코 교착 상태가 되지 않도록 보장하기 위하여 교착 상태를 예방하거나 회피하는 프로토콜을 사용한다.
  • 시스템이 교착 상태가 되도록 허용한 다음에 복구시킨다.

첫번째 해결안이 윈도우나 리눅스를 포함한 대부분의 운영체제가 사용하는 방법이다. 이렇다면 교착 상태를 처리하는 프로그램을 작성하는 것은 응용 개발자의 몫이며, 통상 두번째 해결안에 개략적으로 설명된 접근법을 사용한다. 데이터베이스와 같은 일부 시스템은 세번째 해결안을 사용하여 교착 상태의 발생을 허용하고 복구 작업을 수행한다.

8.5 교착 상태 예방

데드락의 필요조건 중 적어도 하나가 성립하지 않도록 보장함으로써, 교착상태의 발생을 예방할 수 있다.

8.5.1 상호배제

8.5.2 점유하며 대기

8.5.3 비선점

8.5.4 순환 대기

8.6 교착 상태 회피

스레드가 평생 요구하고 사용할 자원에 대한 부가적인 정보를 미리 제공할 것을 요구한다. 이런 추가 지식을 가지고 운영체제는 각 요청을 위해 그 스레드가 기다려야할지 말지를 결정할 수 있다.

  • 교착 상태 예방할 때의 부수적인 문제는 장치의 이용률이 저하되고 시스템 총처리율이 감소한다.
  • 교착 상태를 회피하는 다른 대안은 자원이 어떻게 요청될지에 대한 추가정보를 요구하는 것이다.
  • 스레드의 요청과 방출에 대한 완전한 순서를 파악하고 있다면, 우리는 각 요청에 대해 가능한 미래의 교착 상태를 피하고자 스레드의 대기 여부를 결정할 수 있다.

가장 단순하고 제일 유용한 모델은 각 스레드가 자신이 필요로 하는 각 유형의 자원 마다 최대수를 선언하도록 요구하는 것이다.

이를 파악할 수 있으면 시스템이 교착 상태에 들어가지 않을 것을 보장하는 알고리즘을 만들 수 있다.

두개의 교착 상태 회피 알고리즘을 탐구해보자

8.6.1 안전상태_Safe State

8.6.2 자원 할당 그래프 알고리즘

8.6.3 은행원 알고리즘

8.7 교착 상태 탐지

만일 시스템이 교착 상태 예방이나 교착 상태 방지 알고리즘을 사용하지 않는다면 교착 상태가 발생가능하다. 이러한 환경에서는 시스템은 다음 알고리즘들을 반드시 지원해야한다.

  • 교착 상태가 발생했는지 결정하기 위해 시스템의 상태를 검사하는 알고리즘
  • 교착 상태로부터 회복하는 알고리즘

8.7.3 교착 상태 탐지 알고리즘은 언제 돌리는가? 그 대답은 두 가지 관점에 달려있다.

  1. 교착상태가 얼마나 자주 일어나는가?
  2. 교착 상태가 일어나면 통상 몇 개의 스레드가 거기에 연류되는가?

⇒ 교착 상태가 자주 일어난다면 탐지 알고리즘도 자주 돌려야한다. 교착 상태가 된 스레드로부터 자원을 회수하기까지는 그 자원들은 아무도 못 쓰는 자원으로 교착 상태 기간 내내 묶이게 되기 때문이다.

  • 교착 상태 감지 알고리즘은 실행 중인 시스템의 프로세스 및 자원을 평가하여 일련의 프로세스가 교착 상태에 있는지 아닌지 결정한다.

8.8 교착 상태로부터 회복

교착 상태가 발생하면 시스템은 순환 대기 중인 프로세스 중 하나를 중단하거나 교착 상태의 프로세스에 지정된 자원을 선점하여 교착 상태에서 복구를 시도할 수 있다.

8.8.1 프로세스와 스레드의 종료

교착 상태 프로세스를 모두 중지시키는 방법과 교착 상태가 제거될 때까지 한 프로세스 씩 중지 시키는 방법이 있다. 부분 종료 방식을 사용한다면, 교착 상태 프로세스들의 집합 중에서 교착 상태를 깨뜨리기 위해 어느 프로세스를 중지할 지 선택해야한다.

어느 프로레스를 종료시킬 지 결정하는 데는 다음과 같은 많은 요인이 있다.

  1. 프로세스의 우선 순위가 무엇인지
  2. 지금까지 프로세스가 수행된 시간과 지정되 일을 종료하는 데 더 필요한 시간
  3. 프로세스가 사용한 자원 유형과 수(예를들어, 자원들을 선점하기가 단순한지 여부)
  4. 프로세스가 종료하기 위해 더 필요한 자원의 수
  5. 얼마나 많은 수의 프로세스가 종료되어야하는 지

8.8.2 자원 선점

profile
준제로
.....☆
이전 포스트

[7] 동기화 예제

다음 포스트

[9] 메인 메모리

0개의 댓글