개발 공부

손승열(Son Seungyeol)

[운영체제][OSTEP] 병행성 관련 오류

일반적인 병행성 관련 오류들을 어떻게 처리하는지 공부해봅니다.

손승열(Son Seungyeol)
[운영체제][OSTEP] 병행성 관련 오류

1️⃣ 오류의 종류

복잡한 병행 프로그램에서 발생하는 병행성 오류들은 어떤 것들이 있을까?
➡️ 대표적인 오픈소스 프로그램 4개(MySQL, Apache, Mozilla, OpenOffice)를 분석한 결과를 살펴보자.

105개의 오류 중 대부분(74개)의 오류는 교착 상태와 무관한 오류였음.

Application     What it does     Non-Deadlock     Deadlock
──────────────────────────────────────────────────────────
MySQL           Database Server            14            9
Apache          Web Server                 13            4
Mozilla         Web Browser                41           16
OpenOffice      Office Suite                6            2
Total                                      74           31

이제 비 교착 상태와 교착 상태 관련 오류들에 대해 조금 더 자세히 알아보자.

교착 상태 오류들을 다룰 때에는 예방(prevention), 회피(avoidence), 또는 교착 상태를 해결/관리하는 연구들을 논의해보자.

2️⃣ 비 교착 상태 오류

Lu의 연구 결과에 따르면 비 교착 상태 오류는 병행성 관련 오류의 과반수를 차지

다음에서 비 교착 상태 오류 중 대표적인 두 종류를 살펴보자.

원자성 위반 오류

MySQL에서 발견한 간단한 예시를 살펴보자.

c
Thread 1::
if (thd−>proc_info) {
  ...
  fputs(thd−>proc_info, ...) ;
  ...
}

Thread 2::
thd−>proc_info = NULL;

thd 자료 구조의 proc_info 필드를 두 개의 다른 쓰레드가 접근하고 있다.

  • Thread 1: chd->proc_info 값이 NULL인지 검사하고 값을 출력

  • Thread 2: chd->proc_info 값을 NULL로 설정

Thread 1이 검사 완료 후 fputs를 호출하기 전 인터럽트로 인해 Thread 2가 실행되는 경우
➡️ 🚫 fputs 함수가 NULL 포인터 역참조를 하게 되어 프로그램이 크래시됨.

Lu 등이 기술한 원자성 위반에 대한 정의는 다음과 같다.

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

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

그렇다면 코드를 어떻게 수정하면 될까?
➡️ 🔒 락을 추가하여 어느 쓰레드든 proc_info 필드 접근 시, proc_info_lock 이라는 락 변수를 획득하도록 함.

c
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);

순서 위반 오류

다음 예시를 살펴보자.

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

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

위 코드에서 Thread 2는 mThread 변수가 이미 초기화되고 NULL이 아닌 것을 가정하고 있다.

Thread 1이 먼저 실행되지 않는 경우
➡️ 🚫 Thread 2는 NULL 포인터를 사용하기 때문에 크래시됨.

순서 위반의 정의는 다음과 같다.

"두 개의(그룹의) 메모리 참조 간의 순서가 바뀌었다."

⚠️ 즉, A가 항상 B보다 먼저 실행되어야 하지만 실행 중에 그 순서가 지켜지지 않았다.

그렇다면 코드를 어떻게 수정하면 될까?
➡️ 🚦 컨디션 변수(또는 세마포어)를 사용하여 순서를 강제한다.

cpp
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;
  ...
}

3️⃣ 교착 상태 오류

복잡한 락 프로토콜을 사용하는 다수의 병행 시스템에서 교착 상태(deadlock)라는 고전적 문제가 발생

다음 그림과 같이 그래프에서 사이클(cycle)의 존재는 교착 상태 발생 가능성을 의미한다.

deadlock graph

그렇다면 교착 상태는 왜 발생하는 것일까?

  • 코드의 증가에 따른 구성 요소 간 복잡한 의존성 발생

    ➡️ 대형 시스템의 락 사용 전략의 설계는 매우 신중해야 함.

  • 캡슐화(encapsulation)의 성질 때문

    ➡️ 모듈화와 락은 잘 조화되지 않음.

위의 상황을 예시를 통해 조금 더 이해해보자.

[복잡한 의존성]

< 운영체제 >
1. 가상 메모리 시스템이 디스크 블럭을 가져오기 위해 파일 시스템 접근
2. 파일 시스템은 디스크 블럭을 메모리에 탑재하기 위해 메모리 페이지 확보
3. 이를 위해 파일 시스템은 가상 메모리 시스템에 접근

[캡슐화]

java
Vector v1, v2;
v1.AddAll(v2); // 어떤 쓰레드가 v2.AddAll(v1)을 거의 동시에 호출하는 경우

교착 상태 발생 조건

교착 상태가 발생하기 위해서는 네 가지 조건이 충족되어야 함.

  • 상호 배제(Mutual Exclusion)

    ➡️ 쓰레드가 자신이 필요로 하는 자원에 대한 독자적인 제어권을 주장

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

    ➡️ 쓰레드가 자신에게 할당된 자원을 점유한 채로 다른 자원을 대기

  • 비 선점(No preemption)

    ➡️ 자원(락)을 점유하고 있는 쓰레드로부터 자원을 강제적으로 빼앗을 수 없음.

  • 환형 대기(Circular wait)

    ➡️ 각 쓰레드는 다음 쓰레드가 요청한 하나 또는 그 이상의 자원(락)을 갖고 있는 쓰레드들의 순환 고리가 있음.

위 네 조건 중 하나라도 만족시키지 않는다면 교착 상태는 발생하지 않음.

교착 상태의 예방 - 순환 대기(Circular Wait)

가장 간단한 방법: 락 획득을 하는 전체 순서(total ordering)를 정하기

복잡한 시스템(두 개 이상의 락 존재)의 경우 전체 락의 요청 순서를 정의하는 것이 어렵거나 불필요할 수 있음.
➡️ 부분 순서(partial ordering)를 제공하는 것이 락 획득 구조를 만드는 데 유용

전체 또는 부분 순서를 제공하기 위해서는 세심하게 락 획득 전략을 설계해야 함.

순서라는 것은 단순히 관례이므로 숙련되지 않은 개발자들이 이 관례를 무시하고 코드를 개발할 경우, 교착 상태가 발생할 수 있음.

락의 순서를 정의하기 위해서는 코드와 다양한 루틴 간의 상호 호출 관계를 이해해야 함.

💡 락 주소를 사용하여 락 요청 순서 강제하기

do_something(mutex_t *m1, mutex_t *m2)
// 와 같이 호출되는 함수가 있을 때

// 한 쓰레드가 다음과 같이 호출
do_something(L1, L2)
// 다른 쓰레드가 다음과 같이 호출
do_something(L2, L1)
// 이 경우 교착 상태가 될 수 있음.

위와 같은 경우를 피하기 위해 주소의 값을 사용하여 락 획득의 순서를 정하기도 함.
➡️ do_something() 문장에 인자를 어떤 순서로 넣어 호출하든 락의 획득 순서는 동일

cpp
if (m1 > m2) { // 락을 주소의 내림차순으로 획득하기
  pthread_mutex_lock(m1);
  pthread_mutex_lock(m2);
} else {
  pthread_mutex_lock(m2);
  pthread_mutex_lock(m1);
}
// 코드는 m1 != m2를 가정함(서로 같은 락이 아님)

이 간단한 기법을 사용하여 개발자는 멀티 락 획득 상황에서 간단하고 효율적으로 교착 상태를 방지할 수 있음.

교착 상태의 예방 - 점유 및 대기(Hold-and-Wait)

💡 원자적으로 모든 락을 단번에 획득하도록 하면 예방할 수 있음.

c
lock(prevention);
lock(L1);
lock(L2);
...
unlock(prevention);

위 코드에서는 제일 먼저 prevention 락을 획득하여, 락을 획득하는 과정 중에 쓰레드의 문맥 교환이 발생하는 것을 방지
➡️ 교착 상태의 발생 가능성을 차단

⚠️ 이 해법은 문제점이 많음.

  1. 필요한 락들을 정확히 파악해야 함.

  2. 그 락들을 미리 획득해야 함.

  3. 락이 실제 필요할 때 요청하는 것이 아니라 미리 모든 락을 획득하므로 병행성이 저하됨.

교착 상태의 예방 - 비선점(No Preemption)

일반적으로 락을 해제하기 전까지는 락을 보유하고 있는 것으로 봄.
➡️ 락을 이미 보유한 채로 다른 락을 대기하므로 여러 락 획득 시 문제의 소지가 있음.
➡️ 많은 쓰레드 라이브러리들은 이러한 상황을 피할 수 있도록 유연한 인터페이스 집합 제공

trylock() 루틴

  • 락이 획득한 경우: 락 획득

  • 락이 점유된 경우: -1 리턴

이를 이용하면 교착 상태 가능성이 없고 획득 순서에 영향을 받지 않는 락 획득 방법을 만들 수 있음.

c
top:
  lock(L1);
  if (trylock(L2) == −1) {
    unlock(L1);
    goto top;
  }

⚠️ 무한반복(livelock) 문제가 발생할 수 있음.
➡️두 개의 쓰레드가 이 순서대로 시도하기를 반복하면서 락 획득에 실패할 수 있음.

💡 이 경우 반복문에 지연 시간을 무작위로 조절하여 경쟁 쓰레드 간의 반복 간섭 확률을 줄일 수 있음.

trylock() 방식의 어려운 점: 만약 사용하려는 락이 호출되는 루틴 깊숙한 곳에 존재한다면?
➡️ L1획득 후에 획득한 다른 모든 자원(할당받은 메모리가 있다면 그것도)을 반납해야하는 데, 이러한 구현이 쉽지 않음.

앞서 살펴본 Java의 벡터 메소드와 같이 제한된 경우에서는 이러한 접근이 제대로 동작

교착 상태의 예방 - 상호 배제(Mutual Exclusion)

일반적 코드는 모두 임계 영역을 포함하고 있으므로 상호 배제 자체를 없애는 것은 어려운 일임.
➡️ Herlihy는 대기없는(wait-free) 자료 구조를 고안했음.
➡️ 명시적 락이 필요 없는 강력한 하드웨어 명령어를 사용하여 자료 구조를 만드는 것

다음과 같이 Compare-And-Swap 명령어를 가정하자.

c
int CompareAndSwap(int *address, int expected, int new) {
  if (*address == expected) {
    *address = new;
    return 1; // 성공
  }
  return 0; // 실패
}

또한 어떤 한 값을 원자적으로 임의의 크기만큼 증가하는 경우를 생각해보자.

c
void AtomicIncrement(int *value, int amount) {
  do {
    int old = *value;
  } while (CompareAndSwap(value, old, old + amount) == 0);
}

락을 획득하여 값을 갱신한 후 락을 해제하는 대신, Compare-And-Swap 명령어를 사용하여 값에 새로운 값을 갱신하도록 반복적으로 시도한다.

💡 이 경우 락을 획득할 필요가 없으며 교착 상태가 발생할 수도 없다.
➡️ 무한반복은 여전히 발생 가능성이 있기는 함.

리스트 헤드에 개체를 삽입하는 좀 더 복잡한 예시를 살펴보자.

c
void insert(int value) {
  node_t *n = malloc(sizeof(node_t));
  assert(n != NULL);
  n−>value = value;
  n−>next = head;
  head = n;
}

만약 이 코드가 여러 쓰레드에 의해 "동시에" 호출될 경우 경쟁 조건(race condition)이 발생된다.

✅ 해법1: 락 추가

void insert(int value) {
  node_t *n = malloc(sizeof(node_t));
  assert(n != NULL);
  n−>value = value;
  lock(listlock); // 임계 영역의 시작
  n−>next = head;
  head = n;
  unlock(listlock); // 임계 영역의 끝
}

✅ 해법2: Compare-And-Swap 명령어 사용

c
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은 실패하게 되고 삽입과정을 재시도함.

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

💡 어떤 시나리오에서는 교착 상태를 예방하는 대신 회피하는 것이 더 유용할 수 있음.
➡️ 이를 위해서는 실행 중인 여러 쓰레드가 어떤 락을 획득하게 될 것인지에 대해 전반적으로 파악하고 있어야 함.

다음과 같은 상황의 예시를 살펴보자.

  • 쓰레드 4개(T1-T4)가 프로세서 2개에서 스케줄링됨.

  • 두 종류의 락 L1, L2이 있으며 이를 필요로 하는 쓰레드들이 있음.

위 락을 필요로 하는 쓰레드를 O, 필요로 하지 않는 쓰레드를 X를 표현하면 다음과 같다.

     T1     T2     T3     T4
────────────────────────────
L1   O      O      X      X
L2   O      O      O      X

만약 다음과 같이 실행된다면 교착 상태가 절대로 발생하지 않는다.
➡️ T1과 T2가 동시에 실행만 하지 않으면 됨.

CPU1   [  T3  ][  T4  ]
CPU2   [   T1   ][  T2  ]

다음의 예시도 살펴보자.

     T1     T2     T3     T4
────────────────────────────
L1   O      O      O      X
L2   O      O      O      X

이 경우에는 다음과 같이 실행된다면 교착 상태가 절대로 발생하지 않는다.

CPU1   [  T4  ]
CPU2   [   T1   ][  T2  ][  T3  ]

위처럼 정적 스케줄링은 T1, T2, T3이 모두 한 프로세서에서 실행되도록 하므로 전체 작업이 끝나기까지 상당히 오랜 시간이 소요됨.
➡️ 교착 상태는 피할 수 있지만 어쩔 수 없이 성능 하락 수반

유명한 예로 Dijkstra의 은행원 알고리즘(Banker's Algorithm) 등이 있음.
➡️ 상당히 제한적인 환경에서만 유용한 방법들임.
➡️ 예를 들어 전체 작업에 대한 모든 지식을 알고 있는 임베디드 시스템 등

✅ 이러한 회피 방법은 병행성에 제약을 가져 올 수도 있으므로 스케줄링으로 보편적인 방법은 아님.

발견 및 복구

마지막 전략은 교착 상태 발생을 허용하고, 교착 상태를 발견하면 복구하도록 하는 방법임.
➡️ 교착 상태가 아주 가끔 발생한다면 꽤 유용한 방법

💡 많은 데이터베이스 시스템들이 교착 상태를 발견하고 회복하는 기술을 사용

✅ 교착 상태 발견은 주기적으로 실행되며 자원 할당 그래프를 그려서 사이클이 생겼는지를 검사
➡️ 사이클이 발생하는 경우(교착 상태인 경우) 시스템은 재부팅되어야 함.

🛠️ 자료 구조에 대한 복잡한 복구가 필요할 경우, 사람이 직접 복구 작업을 수행할 수도 있음.

💡 항상 완벽을 추구하지는 말자(Tom West's Law)
➡️ "해야하는 한 모든 일이 모두 다 잘해야 하는 일은 아니다."
➡️ 만약 안 좋은 일이 아주 가끔 일어난다면 그 일을 방지하기 위해 아주 많은 시간을 들일 필요X
➡️ 특히, 그 안 좋은 일에 대한 대가가 작다면 더욱

🧺 병행성 관련 오류 정리 하기

비 교착 상태 오류

  • 상당히 흔하지만 대체적으로 고치기 쉬운 오류

  • 원자성 위반 오류 - 함께 실행해야 하는 명령어들이 함께 실행이 안되어 발생

  • 순서 위반 오류 - 두 쓰레드 간의 실행 순서가 지켜지지 않아 발생

교착 상태 오류

  • 조심하는 것 & 락 획득 순서를 정해서 교착 상태 예방 - 가장 좋은 해법

  • 대기 없는 자료 구조

    • Linux를 포함해서 보편적으로 사용되는 라이브러리나 중요한 시스템에서 사용

      ➡️ 보편성이 부족하고 새로운 대기 없는 자료 구조를 만드는 것이 복잡하므로 제한적으로 사용

  • 새로운 병행 프로그래밍 방법론 개발 - 최선의 해법으로 생각됨.

  • 구글의 맵리듀스(MapReduce): 락을 전혀 사용하지 않고도 개발자가 특정한 병렬 연산을 처리할 수 있도록 해줌.

  • 락은 원천적으로 문제점을 수반하므로 반드시 필요한 경우가 아니면 사용을 피하도록 노력

📚 참고 문헌

Operating Systems: Three Easy Pieces ― 32: Common Concurrency Problems

운영체제 아주 쉬운 세 가지 이야기 ― 35: 병행성 관련 오류

관련있는 게시물

[운영체제][OSTEP] 세마포어
개발 공부

[운영체제][OSTEP] 세마포어

세마포어가 무엇인지, 락과 컨디션 변수 대신 세마포어를 사용하는 방법은 무엇인지에 대해 공부해봅니다.

손승열(Son Seungyeol)
손승열(Son Seungyeol)
[운영체제][OSTEP] 이벤트 기반의 병행성
개발 공부

[운영체제][OSTEP] 이벤트 기반의 병행성

쓰레드 없이 병행 서버를 개발하는 방법에 대해 공부해봅니다.

손승열(Son Seungyeol)
손승열(Son Seungyeol)

Made with React, Gatsby and DatoCMS by @smastrom

Contribute or star on GitHub

© 2022-2023 손승열 for 🅒🅞🅝🅣🅔🅝🅣🅢

모두 좋은 하루 보내세요! 😊