[동시성 프로그래밍] Ch4. 동시성 프로그래밍 특유의 버그와 문제점

4.1 데드락

식사하는 철학자 문제(dining philosophers problem)는 데드락을 설명하는 유명한 예제이다. 여기서 설명하는 데드락의 원리는 다음과 같다.

1. 왼쪽 포크가 비기를 기다렸다가 왼쪽 포크를 사용할 수 있는 상태가 되면 포크를 든다.
2. 오른쪽 포크가 비기를 기다렸다가 오른쪽 포크를 사용할 수 있는 상태가 되면 포크를 든다.
3. 식사를 한다.
4. 포크를 테이블에 놓는다.
5. 단계 1로 돌아간다.

 

데드락(deadlock) : 서로 자원(포크)이 비는 것을 기다리며 더 이상 처리가 진행되지 않는 상태

 

철학자 2명일 때 데드락

• 동시에 2명의 철학자가 왼쪽 포크를 들어 올린 뒤 오른쪽 포크를 계속 기다리게 되므로 더이상 처리가 진행 X
• 식사하는 철학자 문제는 스테이트 머신(state machine)에서의 상태 전이(state transition)

S3에서는 더 이상 전이할 수 있는 상태가 없음을 알 수 있다. S3는 철학자 1과 철학자 2 모두 왼손에 포크를 들고 있는 데드락 상태다. 즉, 데드락이란 전이 대상이 없는 상태임을 알 수 있다.

 

RW락에서 데드락을 주의해야 한다. 다음 코드는 데드락을 발생시킬 수 있는 예제이다.

use std::sync::{Arc, RwLock};
use std::thread;

fn main() {
    let val = Arc::new(RwLock::new(true));

    let t = thread::spawn(move || {
        let flag = val.read().unwrap(); // Read락 획득
        if *flag {
            *val.write().unwrap() = false; // Read락 획득 상태에서 Write 획득, 데드락
            println!("flag is true");
        }
    });

    t.join().unwrap();
}

이를 회피하는 방법은 다음과 같이

use std::sync::{Arc, RwLock};
use std::thread;

fn main() {
    let val = Arc::new(RwLock::new(true));

    let t = thread::spawn(move || {
        let flag = *val.read().unwrap(); // Read락을 획득하고 값을 꺼낸 후 즉시 Read락을 해제
        if flag {
            *val.write().unwrap() = false; // Write락 획득
            println!("flag is true");
        }
    });

    t.join().unwrap();
}

 

4.2 라이브락과 굶주림

식사하는 철학자 문제를 조금 수정해서

 

오른쪽 포크가 비기를 기다렸다가 일정 시간이 지나도 오른쪽 포크를 들 수 있는 상태가 되지 않으면 왼쪽 포크를 내려놓는다

 

는 식으로 변형해 보면 어떨까?

이렇게 리소스를 획득하는 처리는 수행하지만 리소스를 획득하지 못해 다음 처리를 진행하지 못하는 상태를 라이브락(livelock)이라 부른다. 라이브락은 어떤 두 사람이 좁은 길을 엇갈려 지나갈 때 서로 같은 방향으로 피하는 상태와 같다.

라이브락이 발생하는 스테이트 머신 : 스테이트 머신에서 라이브락이 발생할 가능성이 있다. ↔ 특정한 리소스를 획득하는 상태에는 도달하지만 그 외의 상태에는 절대 도달하지 못하는 무한 전이 사례가 존재한다.

 

라이브락이란 상태 전이는 수행되지만 어떤 리소스 획득 상태로도 전이하지 않는 상태이며,

 

굶주림(starvation)이란 특정 프로세스만 리소스 획득 상태로 전이하지 못하는 상태에 있는 것을 말한다.

 

굶주림이 발생하는 스테이트 머신 : 스테이트 머신에서 굶주림이 발생할 가능성이 있다. ↔ 어떤 프로세스가 존재하고, 항상 리소스 획득 상태로 도달 가능하지만, 그 상태에 결코 도달하지 못하는 무한 전이 사례가 존재하거나 데드락이 되는 스테이트 머신

라이브락은 시스템에 관한 문제, 굶주림은 부분 노드에 관한 문제

 

4.3 은행원 알고리즘

데드락 피하기 위한 알고리즘으로 다익스트라가 고안한 은행원 알고리즘(Banker’s Algorithms)

 

Resource 구조체의 정의

struct Resource<const NRES: usize, const NTH: usize> {
    available: [usize; NRES], // 이용 가능한 리소스
    allocation: [[usize; NRES]; NTH], // 스레드 i가 확보 중인 리소스
    max: [[usize; NRES]; NTH], // 스레드 i가 필요로 하는 리소스의 최댓값
}

Resouce 구조체의 구현

impl<const NRES: usize, const NTH: usize> Resource<NRES, NTH> {
    fn new(available: [usize; NRES], max: [[usize; NRES]; NTH]) -> self {
        Resource {
            available,
            allocation: [[0; NRES]; NTH],
            max,
        }
    }

    // 현재 상태가 데드락을 발생시키지 않는지 확인
    // is_safe 함수. 현재 상태가 안전한 경우 (데드락이나 굶주림에 빠지지 않는 경우) true, 그렇지 않은 경우 false를 반환한다.
    fn is_safe(&self) -> bool {
        let mut finish = [false; NTH]; // 스레드 i는 리소스 획득과 반환에 성공했는가?, finish[i] = true 일 때 스레드 i가 리소스를 확보해 처리를 수행하고, 그 후 모든 리소스를 반환할 수 있음을 나타낸다.
        let mut work = self.available.clone(); // 이용 가능한 리소스의 시뮬레이션 값, work[j]는 시뮬레이션상에서의 은행원이 보유한 리소스 j의 수를 나타낸다.

        loop {
            // 모든 스레드 i와 리소스 j에 대해 finish[i] == false && work[j] >= (self.max[i][j] - self.allocation[i][j])을 만족하는 스레드를 찾는다.
            // 아직 시뮬레이션상에서 리소스를 확보하지 못한 스레드로, 원하는 리소스를 은행원이 보유하고 있는 스레드 중에서 찾는다.
            let mut found = false;
            let mut num_true = 0;
            for (i, alc) in self.allocation.iter().enumerate() {
                if finish[i] {
                    num_true += 1;
                    continue;
                }

                // need[j] = self.max[i][j] - self.allocation[i][j]를 계산하고 모든 리소스 j에 대해 work[j] >= need[j]인지 판정한다., 스레드 i가 원하는 리소스를 은행원이 보유하고 있는지 검사한다.
                let need = self.max[i].iter().zip(alc).map(|(m, a)| m - a);
                let is_avail = work.iter().zip(need).all(|(w, n)| *w >= n);
                if is_avail {
                    // 스레드 i가 리소스 확보 가능
                    found = true;
                    finish[i] = true;
                    for (w, a) in work.iter_mut().zip(alc) {
                        *w += *a // 스레드 i가 현재 확보하고 있는 리소스 반환, 스레드 i가 리소스를 확보할 수 있다면 스레드 i는 무언가 처리를 수행한 뒤 확보하고 있는 리소스를 반환한다.
                    }
                    break;
                }
            }

            if num_true == NTH {
                // 모든 리소스가 확보 가능하면 안전함, 모든 리소스가 리소스를 확보할 수 있는 대출 방법이 존재하면 true를 반환한다.
                return true;
            }

            if !found {
                // 스레드가 리소스를 확보할 수 없음, 리소스를 확보할 수 없는 스레드가 있는 경우는 안전하지 않은 상태다.
                break;
            }
        }
        false
    }

    // id번째 스레드가 resource를 하나 얻음, take 함수. 스레드 id가 resource를 1개만 확보하도록 하기 위한 함수. 단, 확보한 상태를 시뮬레이션해서 안전하다고 판단된 경우에만 실제로 리소스를 확보한다.
    fn take(&mut self, id: usize, resource: usize) -> bool {
        // 스레드 번호, 리소스 번호 검사
        if id >= NTH || resource >= NRES || self.available[resource] == 0 {
            return false;
        }

        // 리소스 확보를 시험해 본다., 스레드 id가 resource를 1개 확보한 상태를 만든다.
        self.allocation[id][resource] += 1;
        self.available[resource] -= 1;

        if self.is_safe() {
            true
        } else {
            // 리소스 확보에 실패했으므로 상태 복원
            self.allocation[id][resource] -= 1;
            self.available[resource] += 1;
            false
        }
    }

    // id번째 스레드가 resource를 하나 반환, release 함수. 스레드 id가 resource를 1개 반환한다.
    fn release(&mut self, id: usize, resource: usize) {
        // 스레드 번호, 리소스 번호 검사
        if id >= NTH || resource >= NRES || self.allocation[id][resource] == 0 {
            return;
        }

        self.allocation[id][resource] -= 1;
        self.available[resource] += 1;
    }
}

is_safe 함수는 대출 가능한 리소스와 대출을 시뮬레이션한다. 대출 가능한 경우 필요한 스레드에 대출하고, 해당 스레드의 리소스를 모두 반환 받는 조작을 반복할 때 모든 스레드가 리소스를 확보할 수 있는지 검사한다.

 

take 함수는 리소스를 1개 확보(은행원 입장에서는 대출)하는 함수이며, 확보를 가정했을 때 안전한지 검사하여 안전하다고 판단되었을 때만 리소스를 확보한다. (안전 : 모든 스레드가 리소스를 확보할 수 있는 상태)

 

이 알고리즘의 핵심은 필요한 리소스를 대출할 수 있는 스레드는 처리를 마치는 즉시 리소스를 반환한다는 제약. 은행원은 보유한 리소스와 각 스레드에서 필요로 하는 리소스를 비교하여 대출할 수 있는 스레드에 리소스를 분배한 뒤 현재 대출한 리소스를 포함한 모든 리소스를 반환받는 상황을 반복해 예측. 만약 대출할 수 없는 상황에 빠지면 데드락이나 굶주림 상태가 된다고 예측

 

4.4 재귀락

재귀락 : 락을 획득한 상태에서 프로세스가 그 락을 해제하기 전에 다시 그 락을 획득하는 것

C언어 등은 재귀락은 비교적 발생하기 쉬운 버그

 

재진입 가능한 락 : 재귀락을 수행해도 데드락 상태에 빠지지 않으며 처리를 계속할 수 있는 락 메커니즘

아래 코드는 C 언어에서의 재진입 가능한 뮤텍스를 구현한 예다.

// 재진입 가능한 뮤텍스용 타입
// 재진입 가능한 뮤텍스용 reent_lock 구조체를 정의. 이 구조체는 스핀락에서 이용하는 변수, 현재 락을 획득 중인 스레드 ID를 나타내는 변수, 재귀락 수행 횟수를 나타내는 카운트용 변수를 정의하고 있다. 변수 id의 값이 0이면 아무도 락을 획득하지 않았음을 의미하고, 0이 아니면 다른 스레드가 락을 획득한 상태임으로 나타낸다. 즉, 각 스레드에 할당된 스레드 ID는 0이 아니어야 한다.
struct reent_lock {
    bool lock; // 락용 공용 변수
    int id; // 현재 락을 획득 중인 스레드 Id, 0이 아니면 락 획득 중임
    int cnt; // 재귀락 카운트
}

// 재귀락 획득 함수
void reentlock_acquire(struct reent_lock *lock, int id) {
    // 락 획득 중이고 자신이 획득 중인지 판정, 만약 자신이 락을 획득한 상태라면 카운트를 증가하고 처리를 종료한다. 반대로 아무도 락을 획득하지 않은 상태이거나 다른 스레드가 락을 획득한 상태면 락을 획득하고 락용 변수에 자신의 스레드 Id를 설정한 뒤 카운트를 증가한다.
    if (lock->lock && lock->id == id) {
        // 자신이 획득 중이면 카운트 증가
        lock->cnt++;
    } else {
        // 어떤 스레드도 락을 획득하지 않았거나
        // 다른 스레드가 락 획득 중이면 락 획득
        spinlock_acquire(&lock->lock);
        // 락을 획득하면 자신의 스레드 Id를 설정하고
        // 카운트 증가
        lock->id = id;
        lock->cnt++;
    }
}

// 재귀락 해제 함수
void reentlock_release(struct reent_lock *lock) {
    // 카운트를 감소하고,
    // 해당 카운트가 0이 되면 락 해제
    lock->cnt--;
    if (lock->cnt == 0) {
        lock->id = 0;
        spinlock_release(&lock->lock);
    }
}

재진입 가능한 뮤텍스에서는 락을 획득할 때 자신이 락을 획득하고 있는지 체크하고 락을 획득했다면 재귀락의 카운트를 증가한다. 락을 해제할 때는 재귀락의 카운트를 감소하고 카운트가 0이 되면 실제 락을 해제한다.

 

4.5 의사 각성

의사 각성의 정의는 다음과 같다.

 

의사 각성 : 특정한 조건이 만족될 때까지 대기 중이어야 하는 프로세스가 해당 조건이 만족되지 않았음에도 불구하고 실행 상태로 변경되는 것

다음 코드는 의사 각성을 일으키는 예를 C언어로 구현한 것. 전형적으로는 wait 안의 시그널에 의한 인터럽트가 그 원인이 되어 의사 각성이 일어난다.

#include <pthread.h>
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

// 시그널 핸들러
void handler(int sig) { printf("received signal: %d\n", sig); }

int main(int argc, char *argv[]) {
    // 프로세스 ID 표시, 표시되는 ID에 시그널 송신
    pid_t pid = getpid();
    printf("pid %d\n", pid);

    // 시그널 핸들러 등록
    signal(SIGUSR1, handler); // SIGUSR1 시그널에 대한 시그널 핸들러 등록

    // wait하고 있지만 누구도 notify를 하지 않으므로 멈춰 있어야 함, wait 처리. 여기에서는 wait를 하고 있지만 notify하는 스레드가 따로 없기 때문에 영원히 대기할 것이다.
    pthread_mutex_lock(&mutex);
    if (pthread_cond_wait(&cond, &mutex) != 0) {
        perror("pthread_cond_wait");
        exit(1);
    }
    printf("sprious wake up\n");
    pthread_mutex_unlock(&mutex);

    return 0;
}

이 코드는 notify하는 스레드가 없으므로 영원히 대기할 것처럼 보일지도 모른다. 그러나 OpenBSD나 macOS 등의 OS에서 이 코드를 컴파일해서 실행하고, 해당 프로세스 ID에 대해 다른 콘솔에서 다음을 실행하면 SIGUSR1 시그널이 송신되고 프로그램이 종료된다.

 

$ kill -s SIGUSR1 pid

 

4.7 메모리 배리어

현대적인 CPU에서는 반드시 기계어 명령 순서대로 처리를 수행하지 않는다. 이런 실행 방법을 아웃 오브 오더(Out-Of-Order) 실행이라 부른다. 아웃 오브 오더 실행을 하는 이유는 파이프라인 처리시 단위 시간당 실행 명령 수(instructions-per-second, IPC)를 높이기 위해서이다.

 

예를 들어 A와 B를 다른 메모리 주소로 하고 read A, read B라는 순서의 기계어가 있을 때 A는 메모리상에만 존재하고, B는 캐시 라인상에 존재한다고 하자. 이 때 A를 읽는 것을 완료한 뒤 B를 읽는 것보다 A를 읽는 것을 완료하기 전의 메모리 페치 중에 B를 읽으면 지연을 줄일 수 있다.

 

이렇게 아웃 오브 오더 실행은 IPC 향상에 기여하나, 몇 가지 다른 문제도 일으킨다.

 

아래 그림은 락용 명령을 넘어 아웃 오브 오더 실행이 되었을 경우를 나타낸다.

프로세스 A와 프로세스 B는 공유 변수에 접근하기 위해 락을 획득하고, 락 획득 중에 공유 변수를 증가한다고 가정한다. 여기에서 만약 프로세스 B의 read 명령이 락용 명령 이전에 실행되면 그림에서 보는 것과 같이 시간적으로 이전의 공유 변수의 값을 획득하게 된다. 그러면 최종적으로는 공유 변수의 값이 2가 되어야 하지만 1이 되어 레이스 컨디션이 된다.

 

단, 실제로는 락용 명령을 사용해도 이런 일은 일어나지 않는다. 이것은 메모리 읽기 쓰기 순서를 보증하는 명령이 사용되고 있기 때문이며 그 명령이 바로 메모리 배리어 명령이 된다.

 

참고자료

<동시성 프로그래밍(Concurrent Programming)> 다카노 유키 저, 한빛미디어