핵심 질문: 일반적인 병행성 관련 오류들을 어떻게 처리하는가
병행성 버그는 몇개의 전형적인 패턴을 갖고 있다. 튼튼하고 올바른 병행 코드를 작성하기 위한 가장 첫 단계는 어떤 경우들을 피해야 할지 파악하는 것이다.
1. 오류의 종류
복잡한 병행 프로그램에서 발생하는 오류들은 어떤 것들이 있는가? Lu의 연구결과를 보자.
이런 종류의 오류 (비 교착 상태와 교착 상태) 들에 대해 좀 더 자세히 알아보자.
비 교착 상태 오류
Lu의 연구 결과를 따르면, 비 교착 상태 오류가 병행성 관련 오류 과반수를 차지한다. 비 교착 상태 오류의 분류 중 대표적인 원자성 위반과 순서 위반 오류를 살펴보자.
원자성 위반(atomicity violation) 오류
// Thread 1::
if (thd−>proc_info) {
. . .
fputs(thd−>proc_info, . . . ) ;
. . .
}
// Thread 2::
thd−>proc_info = NULL;쓰레드 1은 thd→proc_info가 NULL인지 검사하고 값을 출력한다. 쓰레드 2는 그 값을 NULL로 바꾼다.
쓰레드 1이 NULL인지 검사 후, fputs()를 호출하기 직전에 쓰레드 2로 인터럽트 되어 info가 NULL로 설정될 수 있다. 이후 스레드 1이 실행할 때 NULL 포인터 역참조가 발생해 프로그램이 크래시될 것이다.
다수의 메모리 참조 연산들 간에 있어 예상했던 직렬성(serializability)이 보장되지 않았다. 즉 코드의 일부에 원자성이 요구되었으나, 실행 시에 그 원자성이 위반되었다.
현재 예제 코드는 ”proc_info 필드의 NULL 값 검사와 fputs() 호출 시 proc_info를 인자로 사용”하는 동작이 원자적으로 실행되는 것 (atomicity assumption)을 가정했다. 이 가정이 깨지면, 코드는 의도한 대로 작동하지 않는다.
코드를 어떻게 수정하면 작동할까? 락을 추가하여 어느 쓰레드든 proc_info 필드 접근 시 락을(proc_info_lock) 획득하도록 한다. 이 자료 구조를 사용하는 다른 모든 코드들도 락으로 보호해야 한다.
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);순서 위반(order violation) 오류
// Thread 1::
void init() {
. . .
mThread = PR_CreateThread(mMain, . . . ) ;
. . .
}
// Thread 2::
void mMain ( . . . ) {
. . .
mState = mThread−>State;
. . .
}이 코드에서 쓰레드 2는 mThread 변수가 이미 초기화된 것으로 가정하고 있다. 만약 쓰레드 1이 먼저 실행되지 않았다면 NULL 포인터를 사용하기 때문에 크래시가 일어나거나, 더 최악의 경우 임의의 메모리 주소를 참조하게 된다.
순서 위반의 정의는 다음과 같다.
“두 개의(그룹의) 메모리 참조 간의 순서가 바뀌었다(즉, A가 항상 B보다 먼저 실행되어야 하지만 실행 중에 그 순서가 지켜지지 않았다).”
이러한 오류를 수정하는 법은 순서를 강제하는 것이다. 이전에 논의했던 컨디션 변수가 잘 맞는다. 코드를 재작성해보자.
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;
. . .
}수정된 코드에서는 mtLock이라는 락, 그에 대한 컨디션 변수 mtCond, 그리고 상태 변수 mtInit을 추가하였다. 초기화 코드가 실행되면, mtInit을 1로 설정하고 시그널을 발생시킨다. 쓰레드 2가 이 시점 이전에 실행되었다면 상태 변경을 대기한다.
쓰레드 간의 순서가 문제가 된다면 컨디션 변수(또는 세마포어)를 이용하여 해결할 수 있다.
비 교착 상태 오류: 정리
비 교착 상태 오류의 대부분(97%)은 원자성 또는 순서 위반에 대한 것이었다. 이러한 오류 패턴들을 유의하면 관련 오류들을 좀 더 줄일 수 있다.
3. 교착 상태 오류
복잡한 락 프로토콜을 사용하는 다수의 병행 시스템에서 교착 상태(deadlock) 라는 고전적 문제가 발생한다. 예를 들어 락 L1을 갖고 있는 쓰레드 2가 락 L1이 해제되기를 기다리고 있을 때 교착 상태가 발생한다. 교착 상태가 발생할 가능성이 있는 코드를 보자.
Thread 1: Thread 2:
lock(L1); lock(L2);
lock(L2); lock(L1);쓰레드 1이 락 L1을 획득한 후 문맥 교환이 발생해 쓰레드 2가 락 L2를 획득하고 락 L1을 획득하기 시도할 때 교착 상태가 발생한다.
각 쓰레드가 상대방이 소유하고 있는 락을 대기하여 누구도 실행할 수 없게 된다. 그래프에서는 사이클의 존재는 교착 상태의 발생 가능성을 의미한다.
교착 상태는 왜 발생하는가
쓰레드 1,2가 같은 순서로 락을 획득한다면 교착 상태는 절대 발생하지 않는다. 그러면 교착 상태는 왜 발생할까?
코드가 많아지면서 구성 요소 간에 복잡한 의존성이 발생하기 때문이다. 운영체제를 생각해보면, 가상 메모리 시스템이 디스크 블럭을 가져오기 위해 파일 시스템에 접근한다. 파일 시스템은 디스크 블럭을 메모리에 탑재하기 위해 메모리 페이지를 확보해야 하고, 이를 위해 가상 메모리 시스템에 접근한다. 순환 의존성이 자연스럽게 발생한다.
또 다른 이유는 캡슐화의 성질 때문이다. 소프트웨어 모듈화가 개발을 쉽게 하기 때문에 상세한 구현 내용은 감추도록 구현한다. 하지만 이런 모듈화 때문에 교착 상태가 일어날 수 있다.
자바의 Vector 클래스의 addAll()메서드를 보자.
Vector v1, v2;
v1.addAll(v2);이 메소드는 v1에 대한 락 뿐만 아니라 v2에 대한 락도 획득해야 한다. 하지만 어떤 쓰레드가 v2.addAll(v1)을 호출하면 교착 상태가 발생할 수 있다. 이 모든 상황은 호출한 응용 프로그램이 모르게 진행된다.
교착 상태 발생 조건
교착 상태가 발생하기 위해서는 네 가지 조건이 충족되어야 한다.
- 상호 배제 (Mutual Exclusion): 쓰레드가 자신이 필요로 하는 자원에 대한 독자적인 제어권을 주장한다 (예, 쓰레드가 락을 획득함).
- 점유 및 대기 (Hold-and-wait): 쓰레드가 자신에게 할당된 자원 (예 : 이미 획득한 락)을 점유한 채로 다른 자원 (예 : 획득하고자 하는 락)을 대기한다.
- 비 선점 (No preemption): 자원 (락)을 점유하고 있는 쓰레드로부터 자원을 강제적 으로 빼앗을 수 없다.
- 순환 대기 (Circular wait): 각 쓰레드는 다음 쓰레드가 요청한 하나 또는 그 이상의 자원 (락)을 갖고 있는 쓰레드들의 순환 고리가 있다.
네 조건 중 하나라도 만족시키지 않는다면 교착 상태는 발생하지 않는다.
교착 상태의 예방
순환 대기
아마도 가장 실용적이며 자주 사용되는 교착 상태 예방 기법은 순환 대기가 절대 발생하지 않도록 락 코드를 설정하는 것이다.
락 획득을 하는 전체 순서(total ordering)을 정할 수 있다. 락 L1, L2 두 개만 시스템에 존재한다면, L1은 무조건 L2 이전에 획득하도록 하여 교착 상태를 피할 수 있다.
복잡한 시스템의 경우 두 개 이상의 락이 존재할 것이고, 전체 락의 요청 순서를 정의하는 것이 어려울 것이다. 이를 위해 부분 순서(partial ordering)를 제공하는 것이 락 획득 구조를 만드는데 유용할 것이다.
Linux의 메모리 매핑 코드가 부분 순서를 이용한 좋은 예시이다. 소스 코드를 보면, 열 개의 서로 다른 그룹으로 무묶인 락과 획득 순서가 있다.
- Code
/* * Lock ordering: * * ->i_mmap_rwsem (truncate_pagecache) * ->private_lock (__free_pte->block_dirty_folio) * ->swap_lock (exclusive_swap_page, others) * ->i_pages lock * * ->i_rwsem * ->invalidate_lock (acquired by fs in truncate path) * ->i_mmap_rwsem (truncate->unmap_mapping_range) * * ->mmap_lock * ->i_mmap_rwsem * ->page_table_lock or pte_lock (various, mainly in memory.c) * ->i_pages lock (arch-dependent flush_dcache_mmap_lock) * * ->mmap_lock * ->invalidate_lock (filemap_fault) * ->lock_page (filemap_fault, access_process_vm) * * ->i_rwsem (generic_perform_write) * ->mmap_lock (fault_in_readable->do_page_fault) * * bdi->wb.list_lock * sb_lock (fs/fs-writeback.c) * ->i_pages lock (__sync_single_inode) * * ->i_mmap_rwsem * ->anon_vma.lock (vma_merge) * * ->anon_vma.lock * ->page_table_lock or pte_lock (anon_vma_prepare and various) * * ->page_table_lock or pte_lock * ->swap_lock (try_to_unmap_one) * ->private_lock (try_to_unmap_one) * ->i_pages lock (try_to_unmap_one) * ->lruvec->lru_lock (follow_page_mask->mark_page_accessed) * ->lruvec->lru_lock (check_pte_range->folio_isolate_lru) * ->private_lock (folio_remove_rmap_pte->set_page_dirty) * ->i_pages lock (folio_remove_rmap_pte->set_page_dirty) * bdi.wb->list_lock (folio_remove_rmap_pte->set_page_dirty) * ->inode->i_lock (folio_remove_rmap_pte->set_page_dirty) * bdi.wb->list_lock (zap_pte_range->set_page_dirty) * ->inode->i_lock (zap_pte_range->set_page_dirty) * ->private_lock (zap_pte_range->block_dirty_folio) */
락의 순서를 정의하기 위해서는 코드와 다양한 루틴 간의 상호 호출 관계를 이해해야 한다. 조금만 실수해도 교착 상태가 발생하게 된다.
"락 주소를 사용하여 락 요청 순서를 강제하는 방법도 있다.”
if (m1 > m2) { // 락을 주소의 내림차순으로 획득 pthread_mutex_lock(m1); pthread_mutex_lock(m2); } else { pthread_mutex_lock(m2); pthread_mutex_lock(m1); } // m1 != m2를 가정
점유 및 대기
점유 및 대기는 원자적으로 모든 락을 단번에 획득하도록 하면 예방할 수 있다.
lock(prevention);
lock(L1);
lock(L2);
. . .
unlock(prevention);prevention 락을 획득하여 필요한 락을 원자적으로 획득하도록한다.
이 해법은 문제점이 많다. 캡슐화가 어렵다. 필요한 락들을 정확히 파악해야하고, 그 락들을 미리 획득해야하기 때문이다. 또한 락이 필요할 때 요청하는 것이 아니라 미리 한번에 획득하기 때문에 병행성이 떨어진다.
비선점
일반적으로 락을 해제하기 전까지는 락을 보유하고 있는 것으로 보기 때문에 여러 락을 획득하는 것에는 문제의 소지가 있다. 왜냐하면 락을 이미 보유하고 있는 채로 다른 락을 대기하기 때문이다.
때문에 많은 쓰레드 라이브러리들은 이러한 상황을 피할 수 있도록 유연한 인터페이스 집합을 제공한다. trylock() 루틴의 경우 획득 가능하다면 락을 획득하거나 현재 락이 점유된 상태이니 나중에 다시 시도라하라는 것을 알리는 -1을 리턴한다.
trylock() 인터페이스를 이용하면 교착 상태 가능성이 없고 획득 순서에 영향을 받지 않는 락 획득 방법을 만들 수 있다.
top:
lock(L1);
if (trylock(L2) == −1) {
unlock(L1);
goto top;
}다른 쓰레드가 같은 프로토콜을 사용하면서 락을 다른 순서로 획득하려고 해도 교착 상태는 발생하지 않는다. 하지만 무한반복(livelock) 문제가 생긴다.
두 쓰레드가 이 순서로 계속 시도하면서 락 획득에 실패하는 것도 가능하긴 하다(확률은 낮지만). 반복문에 지연 시간을 무작위로 조절해서 경쟁하는 쓰레드 간의 반복 간섭 확률을 줄일 수 있다.
상호 배제
마지막 예방 기법은 상호 배제 자체를 없애는 방법이다. 일반적인 코드는 모두 임계 영역을 포함하고 있기 때문에 어려운 일이다. 어떻게 할까?
wait-free 자료구조를 고안했다. 명시적 락이 필요없는 강력한 하드웨어 명령어를 사용하여 자료구조를 만들면 된다는 것이다.
Compare-And-Swap 명령이 대표적인 예제이다.
int CompareAndSwap(int *address, int expected, int new) {
if (*address == expected) {
*address = new;
return 1; // 성공
}
return 0; // 실패
}어떤 한 값을 원자적으로 임의의 크기만큼 증가 시키는 경우를 구현하자.
void AtomicIncrement(int *value, int amount) {
do {
int old = *value;
} while (CompareAndSwap(value, old, old + amount) == 0);
}락을 획득하여 갱신한 후 락을 해제하는 대신, CAS 명령어를 사용하여 값을 갱신하기하기를 반복적으로 시도한다. 이 경우 락을 획득할 필요도 없고, 교착 상태가 발생할 일도 없다.(무한 반복은 발생할 수 있지만)
좀 더 복잡한 리스트 삽입 예제를 살펴보자. 리스트 헤드에 개체를 삽입하는 코드이다.
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);
}next 포인터가 현재의 헤드를 가리키도록 갱신하고, 새로 생성된 노드는 리스트의 헤드가 되도록 동작한다. 이 코드를 처리하는 도중 다른 쓰레드가 새로운 헤드를 추가했다면, Compare-And-Swap은 실패하고 삽입 과정을 다시 시도한다.
스케줄링으로 교착 상태 회피하기
교착 상태의 예방보다 회피하는 것이 유용할 때가 있다. 교착 상태를 회피하기 위해서는 여러 쓰레드가 어떤 락을 획득하게 될 것인지에 대해 전반적으로 파악하고 있어야 하며, 그것을 바탕으로 쓰레드들을 스케줄링하여 교착 상태가 발생하지 않도록 그때그때 보장한다.
4개의 쓰레드가 2개의 프로세서에서 스케줄링 된다고 가정하자. 똑똑한 스케줄러라면 T1과 T2가 동시에 실행만 하지 않는다면 교착 상태가 절대로 발생하지 않도록 할 수 있다.
또 다른 예를 살펴보자
이 경우 T1, T2, T3가 동시에 실행되면 안된다.
T1, T2, T3이 모두 한 프로세서에서 실행되도록 보수적인 방법을 택하기 때문에 전체 작업이 끝나기까지 오랜 시간이 걸린다. 때문에 스케줄링으로 교착 상태를 회피하는 것은 보편적으로 사용되는 방법은 아니다.
유명한 예시로 Dijkstra의 Banker’s Alogrithm이 있다. 전체 작업에 대한 모든 지식을 알고있는 임베디드 시스템에서 작업을 실행하며 필요한 락을 획득하는 경우이다.
발견 및 복구
마지막 전략은 교착 상태 발생을 허용하고, 발견하면 복구하도록 하는 방법이다. 예를 들어 운영체제가 1년에 한 번 멈춘다고 했을 때 시원하게 재부팅을 하는 방법이 있다. 교착 상태가 아주 가끔 발생한다면 꽤 유용한 방법이다.
많은 데이터베이스 시스템들이 교착 상태를 발견하고 회복하는 기술을 사용한다. 이는 주기적으로 실행되며 자원 할당 그래프를 그려서 사이클이 생겼는지를 검사한다. 사이클이 발생하는 경우, 시스템은 재부팅되어야 한다.
