[OS] 병행성 관련 오류

장선규·2023년 9월 25일
Concurrency BugsOSOSTEPconcurrency병행성운영체제
1

[OS] OSTEP Study

목록 보기
22/28

병행성 관련 오류

이번 장에서는 실제 코드들을 예로 사용하여 병행성 문제들을 살펴보고 어떤 문제들을 조심해야 하는지 보도록 하겠다.

  • 참고) 대부분 초기 연구는 교착상태(deadlock)에 초점

핵심 질문: 일반적인 병행성 관련 오류들을 어떻게 처리하는가
병행성 버그는 몇 개의 전형적인 패턴을 갖고 있다.
튼튼하고 올바른 병행 코드를 작성하기 위한 가장 첫 단계는 어떤 경우들을 피해야 할지 파악하는 것이다.

1. 오류의 종류

복잡한 병행 프로그램에서 발생하는 병행성 오류들은 어떤 것들이 있는가?

  • 유명한 오픈소스 프로그램 4개를 분석한 결과 총 105개 정도의 오류가 발견되었다.
  • 그 중 비 교착상태 오류는 74건, 교착상태 오류는 31건
  • 이 장에서 두 종류의 오류 모두 다룰 것

2. 비 교착 상태 오류

원자성 위반 오류

// Thread 1::
if (thd−>proc_info) {
    ...
    fputs(thd−>proc_info, ...) ;
    ...
}
// Thread 2::
thd−>proc_info = NULL;
  • 위의 코드에서 thd 자료구조의 proc_info 필드를 두개의 다른 쓰레드가 접근한다.
  • Thread 1에서 proc_info가 NULL 인지 검사를 하긴 하지만, fputs가 실행되기 직전에 인터럽트가 될 수 있다.
  • 인터럽트가 되었다고 하고 Thread 2가 실행되어 proc_info를 NULL로 처리하면 Tread 1로 돌아왔을 때 NPE가 발생할 수 있다.

원자성 위반

  • "다수의 메모리 참조 연산들 간에 있어 예상했던 직렬성(serializability)이 보장되지 않았다."

  • 즉, 코드의 일부에 원자성이 요구되었으나, 실행 시 그 원자성이 위배되었다.

  • proc_info 필드에 접근할 때 락을 추가하면 된다.

    pthread_mutex_t proc_info_lock = PTHREAD_MUTEX_INITIALIZER;
// Thread 1::
pthread_mutex_lock(&proc_info_lock);
if (thd−>proc_info) {
    ...
    fputs(thd−>proc_info, ...) ;
    ...
}
pthread_mutex_unlock(&proc_info_lock);

// Thread 2::
pthread_mutex_lock(&proc_info_lock);
thd−>proc_info = NULL;
pthread_mutex_unlock(&proc_info_lock);

순서 위반 오류

// Thread 1::
void init() {
	...
    mThread = PR_CreateThread(mMain , ...) ;
	...
}

// Thread 2::
void mMain (...) {
	...
    mState = mThread−>State;
	...
}

  • 위의 예에서 Thread 2는 Thread 1이 실행되었음을 가정한다.

  • 만약 Thread 1이 먼저 실행되지 않았다면 Thread 2에서는 NPE, 또는 임의의 메모리 주소에 접근하게 된다.

  • 해결 방법: 컨디션 변수를 사용하여 "순서를 강제"

    pthread_mutex_t mtLock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t mtCond = PTHREAD_COND_INITIALIZER;
int mtInit = 0;

// Thread 1::
void init() {
    ...
    mThread = PR_CreateThread(mMain, ...) ;
    // 쓰레드가 생성되었다는 것을 알리는 시그널 전달...
    pthread_mutex_lock(&mtLock);
    mtInit = 1;
    pthread_cond_signal(&mtCond);
    pthread_mutex_unlock(&mtLock);
    ...
}

// Thread 2::
void mMain (...) {
    ...
    // 쓰레드가 초기화되기를 대기...
    pthread_mutex_lock(&mtLock);
    while (mtInit == 0)
        pthread_cond_wait(&mtCond , &mtLock);
    pthread_mutex_unlock(&mtLock);
    mState = mThread−>State;
    ...
}
    • Thread 1이 먼저 실행되면 mtInit이 1이 되므로 정상적으로 실행된다.
    • Thread 2가 먼저 실행되면 mtInit이 0이라 wait() 루틴이 실행되어 초기화되기를 대기한다. 이후 Thread 1에서 초기화가 되면 잠든 쓰레드를 깨우며 잘 작동한다.

참고) 비 교착 상태 오류의 대부분(97%)은 원자성 또는 순서 위반에 대한 것이었다.

3. 교착 상태 오류

교착상태(Deadlock): 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태

  • 예시
    • 이 예에서, 쓰레드 1이 L1락을 획득하고 문맥 교환이 되었다고 하자.
    • 이후 쓰레드 2에서 L2락을 획득하고, L1락을 획득하려고 하면 교착상태가 발생한다.
    • 쓰레드 1은 L2를 기다리고, 쓰레드 2는 L1을 영원히 기다리게 된다.
    • 교착상태 의존성 그래프

그렇다면 교착상태를 방지하기 위해서는 어떻게 코드를 작성해야 할까?

교착상태는 왜 발생하는가

교착상태는 왜 발생할까?

  • 코드가 많아지면서 구성 요소 간에 복잡한 의존성이 발생하기 때문
  • 캡슐화(encapsulation)의 성질 때문에, 모듈화된 인터페이스에서 교착상태가 일어나기 때문
    • 특히 모듈화와 락은 잘 조화되지 않고, 교착 상황은 응용 프로그램이 모르게 진행된다.

교착상태 발생 조건

  • 상호 배제(Mutual Exclusion): 쓰레드가 자신이 필요로 하는 자원에 대한 독자적인 제어권을 주장한다
    • ex) 쓰레드가 락을 획득
  • 점유 및 대기(Hold-and-wait): 쓰레드가 자신에게 할당된 자원을 점유한 채로 다른 자원을 대기한다.
    • ex) 쓰레드가 이미 어떤 락을 획득한 채로 또다른 락을 획득하고자 대기
  • 비선점(No preemption): 자원을 점유하고 있는 쓰레드로부터 자원을 강제적으로 빼앗을 수 없다.
  • 환형 대기(Circular wait): 각 쓰레드는 다음 쓰레드가 요청한 하나 또는 그 이상의 자원을 갖고 있는 쓰레드들의 순환 고리가 있다.

이 네 조건이 모두 만족해야 교착상태가 발생한다. 하나라도 만족시키지 않는다면 교착상태는 발생하지 않는다.

교착상태의 예방

먼저 교착 상태를 예방할 수 있는 기술들을 먼저 살펴보자. 각 전략들은 위의 조건들이 발생하는 것을 막는다.

1) 순환 대기(Circular wait)

  • 가장 실용적이고 가장 자주 사용되는 예방 기법!
  • 락 획득을 하는 전체 순서(total ordering)를 정하는 것
    • ex) L1,L2라는 두 락에 대해, L1을 무조건 L2전에 획득하도록 하면 교착상태를 피할 수 있다.
    • 이 순서를 따르면 순환 대기는 발생하지 않고, 교착상태도 발생하지 않는다.
  • 두개 이상의 락이 존재하는 복잡한 시스템에서는 부분 순서(partial ordering)을 제공하여 안전한 락 획득 구조를 만들 수 있다.
    • ex) Linux의 메모리 매핑 코드
      • 그룹별로 묶여있는 락과, 그 락에 대한 획득 순서 정의됨
      • mapping->tree_lock 획득 전에 swap_lock 획득해야 함
      • swap_lock 획득 전에 private_lock 획득해야 함
      • private_lock 획득 전에 i_mmap_mutex 획득해야 함
      • i_mmap_mutex 획득 전에 i_mutex 획득해야함

2) 점유 및 대기(Hold-and-wait)

  • 원자적으로 모든 락을 단번에 획득하도록 하여 교착상태 예방
    lock(prevention);
lock(L1);
lock(L2);
...
unlock(prevention);
    • 미리 prevention 락을 획득하고, 그 후에 L1,L2... 락들을 획득
    • 순서 바뀌어도 상관 없음, 이미 prevention` 락이 걸려있기 때문
  • 문제점
    • 필요한 락들을 정확히 파악해야 하고, 그 락들을 미리 획득해야 한다.
    • 락을 미리 획득하기 때문에 병행성이 저하된다.

3) 비선점(No preemption)

여러 락을 획득하는 것에는 문제의 소지가 있다. 왜냐하면 락을 보유한 채로 다른 락을 대기하기 때문이다.

많은 쓰레드 라이브러리들은 이러한 상황을 피할 수 있도록 유연한 인터페이스들을 만들어 놓았다.

trylock()루틴

  • 락을 획득, 획득 실패시 -1 반환 (나중에 다시 시도하세요~)
  • 해당 인터페이스를 이용하면 교착상태 가능성이 없고 획득 순서에 영향을 받지 않는 락 획득 방법을 만들 수 있다.
    top:
    lock(L1);
    if (trylock(L2) == −1) {
        unlock(L1);
        goto top;
    }
    • 다른 쓰레드가 같은 프로토콜을 사용하면서 락을 다른 순서(L2 먼저)로 획득하려고 해도 교착상태는 발생하지 않는다.
    • 문제점: 두 쓰레드가 이 순서(L2 먼저, 그다음 L1)대로 시도하기를 반복하면서 획득에 실패하는 무한반복(livelock) 문제 발생 가능
      • 반복문에 지연 시간을 무작위로 주면 경쟁하는 쓰레드 간의 반복 간섭 확률을 줄일 수 있음
  • 캡슐화 문제: 만약 사용하려는 락이 호출되는 루틴 깊숙한 곳에 존재한다면, 처음 부분으로 되돌아가야 하는데, 쉽지 않음
    • 코드 실행 중 L1락이 아닌 다른 자원도 획득했다면, 이 역시 반납해야한다.

4) 상호 배제(Mutual Exclusion)

상호 배제 자체를 없애는 기법... 어떻게?

Wait-free 자료구조

  • 아이디어 - 명시적 락이 필요없는 강력한 하드웨어 명령어를 사용하여 자료구조를 만들자
  • 예제 1)
    // Compare-And-Swap 명령어
int CompareAndSwap(int *address, int expected, int new) {
    if (*address == expected) {
    	*address = new;
    	return 1; // 성공
    }
    return 0; // 실패
}
    // 값을 amount 만큼 증가시키는 함수
void AtomicIncrement(int *value , int amount) {
    do {
    	int old = *value;
    } while (CompareAndSwap(value, old, old + amount) == 0);
}
    • Compare-And-Swap 명령어를 사용하여 새로운 값을 갱신하도록 반복적으로 시도한다.
    • 만약 다른 쓰레드에서 old의 값을 바꿨다면, expected 값이 실제 값과 다를 것이므로 실패한다. (교착상태 X)
  • 예제 2) - 리스트 헤드에 노드를 삽입하는 상황
    void insert(int value) {
    node_t *n = malloc(sizeof(node_t));
    assert(n != NULL);
    n−>value = value;
    // 여기에 락을 걸면 되긴함
    n−>next = head;
    head = n;
    // 여기에 락을 걸면 되긴함
}
    • 문제점
      • [A, B, C] 가 있고, 쓰레드 1에서 X를, 쓰레드 2에서 Y를 insert 한다고 하자.
      • 쓰레드 1에서 노드 X의 next값은 head인 A를 갖게 될 것이다.
      • 쓰레드 1에서 head = n이 실행되기 전에 인터럽트 발생!
      • 쓰레드 2에서 모든 작업이 완료되어 리스트는 [Y, A, B, C]가 되고, head는 Y가 될 것이다.
      • 다시 쓰레드 1로 돌아와 head = n이 수행되면 [X, A, B, C]가 되어 Y가 사라진다.
    • 락을 걸어서 해결할 수도 있다.
    • 락 없이 Compare-And-Swap 명령어로 해결
      void insert(int value) {
    node_t *n = malloc(sizeof(node_t));
    assert(n != NULL);
    n−>value = value;
    do {
    	n−>next = head;
    } while (CompareAndSwap(&head , n−>next , n) == 0);
}
      • 만약 처리 도중 다른 쓰레드가 새로운 헤드를 추가하면, Compare-And-Swap는 실패하고 쓰레드는 삽입과정을 재시도한다.

스케줄링으로 교착상태 회피하기

어떤 상황에서는 교착 상태를 예방하는 대신 회피하는 것이 더 유용할 때가 있다.

  • 회피하기 위해서는 실행 중인 여러 쓰레드가 어떤 락을 획득하게 될 것인지에 대해 전반적으로 파악해야 한다.
  • 그것을 바탕으로 쓰레드들을 스케줄링하여 교착상태가 발생하지 않도록 그때그때 보장한다.
  • 예제 1)
    • 4개의 쓰레드가 2개의 프로세서에 스케줄링되는 상황
    • 각 쓰레드들(Tn)이 필요한 락(L1,L2) 유무
    • T1과 T2가 동시에 실행되지만 않으면 교착상태가 절대 일어나지 않는다.
    • T3는 락을 하나만 필요로하기 때문에 교착상태를 유발하지 않는다.
    • 잘 스케줄링 된 경우
  • 예제 2)
    • 동일하게 4개의 쓰레드, 2개의 프로세서
    • 이번에는 T1,2,3 모두 L1,L2를 필요로 하므로, 아까처럼 안 겹치게 스케줄링 한다면 다음과 같이 된다.
      • 딱 봐도 안 좋아 보인다. 어쩔수 없는 성능 하락이다.

이 방법은 병행성 제약을 가져올 수 있기도 하고, 상당히 제한적인 환경에서만 유용한 방법이다.

발견 및 복구

교착상태 발생을 허용하고, 교착 상태를 발견하면 복구하도록 하는 방법이다.

  • ex) 일년에 한번 멈추는 프로그램 -> 그냥 시원하게 재부팅 후 다시 작업 처리
  • 많은 데이터베이스 시스템들이 교착 상태를 발견하고 회복하는 기술을 사용한다.
  • 교착 상태 발견은 주기적으로 실행되며 자원 할당 그래프를 그려서 사이클이 생겼는지를 검사한다.
    • 사이클 발생시(교착상태인 경우) 시스템 재부팅
    • 복잡한 자료구조 복구를 사람이 직접 수행할 수도 있음

4. 요약

  • 비 교착상태 오류는 대체로 고치기 쉬운 오류
    • 원자성 위반 오류 & 쓰레드 실행 순서 위반 오류
  • 교착상태 오류
    • 교착상태 예방
      1. 순환대기
      2. 점유대기
      3. 비선점
      4. 상호배제
    • 교착상태 회피 (스케줄링)
    • 발견 및 복구
  • 가장 좋은 해법은 조심하는 것과 락 획득 순서를 정해서 애초에 교착 상태가 발생하지 않도록 예방하는 것이다.
  • 락은 원천적으로 문제점을 수반하기 때문에 반드시 필요한 경우가 아니면 사용을 피하도록 노력해야 한다.
profile
장선규
코딩연습
이전 포스트

[OS] 세마포어

다음 포스트

[OS] 이벤트 기반의 병행성

0개의 댓글