운영체제 아주 쉬운 세가지 이야기 책에 대한 스터디를 진행한다.
이 글에서는 병행성에 대해 다룬 29장부터 34장까지의 내용을 정리한다.
29장. 락 기반의 병행 자료 구조
자료 구조에 락을 추가하면 경쟁조건으로 부터 안전한 쓰레드 안전(thread safe) 자료 구조로 만들 수 있다.
어떤 방식으로 병행 자료 구조를 다뤄야하는지 알아본다.
29.1 병행 카운터
카운터는 보편적으로 사용되면서 가장 간단한 자료 구조이다.
간단하지만 확장성이 없음
typedef struct __counter_t {
int value;
pthread_mutex_t lock;
} counter_t;
void increment(counter_t *c) {
Pthread_mutex_lock(&c->lock);
c->value++;
Pthread_mutex_unlock(&c->lock);
}
void decrement(counter_t *c) {
Pthread_mutex_lock(&c->lock);
c->value++;
Pthread_mutex_unlock(&c->lock);
}
void get(counter_t *c) {
Pthread_mutex_lock(&c->lock);
int rc = c->value;
Pthread_mutex_unlock(&c->lock);
return rc;
}
- 간단하지만 정확하게 동작, 병행 자료 구조의 보편적인 디자인 패턴
- 모니터(monitor) 를 사용하여 만든 자료구조와 유사
- 쓰레드 개수가 늘어날 수록 성능이 나빠짐
완벽한 확장성(perfect scaling) 이 보장된 환경에서는 작업양이 CPU 개수에 비례해서 증가해도 전체 완료 시간이 늘어나지 않는다.
확장성 있는 카운팅
확장성 있는 카운터를 만들기 위해 근사 카운터(approximate counter) 기법을 사용한다.
근사 카운터는 하나의 논리적 카운터로 표현되는데 CPU 코어마다 하나의 물리적인 지역 카운터와 하나의 전역 카운터로 구성되어있다.
쓰레드는 지역 카운터를 증가시켜 지역 락으로 보호한다.
CPU 마다 지역 카운터를 갖기 때문에 CPU 들에 분산된 쓰레드들은 지역 카운터를 경쟁 없이 갱신할 수 있다. (확장성)
주기적으로 지역 카운터 값을 전역 카운터에 반영하고 쓰레드는 전역 카운터를 읽어 카운터 값을 판단한다.
전역 락을 사용하면 지역 카운터의 값을 전역 카운터 값에 더하고, 지역 카운터의 값은 0으로 초기화 한다.
29.2 병행 연결 리스트
연결 리스트를 병행적으로 다루기 위해 삽입 연산을 시작하기 전에 락을 획득하고 리턴 직전에 해제한다.
확장성 있는 연결리스트
병행 가능한 연결 리스트는 확장성이 좋지 않다.
이를 개선하기 위해 hand-over-hand locking (또는 lock coupling) 기법 개발
전체 리스트에 하나의 락이 아니라 노드마다 락을 추가하는 것이다.
리스트를 순회하면서 다음 노드의 락을 획득하고 지금 노드의 락을 해제한다.
하지만 락을 획득하고 해제하는 오버헤드가 크기 때문에 속도 개선이 쉽지 않다.
29.3 병행 큐
병행 큐는 큐의 헤드와 테일에 락을 사용한다.
큐에 삽입과 추출 연산에 병행성을 부여하는 것이다.
하지만 이 락만 존재하는 큐는 쓰레드가 대기하는 기능이 없기 때문에 실제로 사용할 수 없다.
29.4 병행 해시 테이블
병행 해시 테이블은 전체 자료 구조에 하나의 락이 아닌 해시 버켓마다 락을 사용했기 때문에 병행 리스트에 비해 병행성이 좋다.
29.5 요약
카운터, 리스트, 큐 해시 테이블 병행 자료 구조들을 소개했다.
락 획득과 해제 코드에 대해 주의를 기울여야 하는데,
성능 개선은 미숙한 최적화(premature optimization) 를 피하기 위해 성능에 문제가 생길 경우에만 고려해야 한다.
30장. 컨디션 변수
병행 프로그램을 제작하는데 락 이외에도 특정 조건 의 만족 여부를 검사하는 기법도 존재한다.
30.1 컨디션 변수의 개념과 관련 루틴
쓰레드 실행 시, 특정 조건이 만족될 때까지 대기를 위해 컨디션 변수(conditional variable) 를 사용할 수 있다.
컨디션 변수는 쓰레드 실행에서 특정 조건이 만족되기를 대기하는 큐 자료 구조다.
슬립에서 깨어난 프로세스는 리턴하기 전에 락을 재획득 해야 한다.
대기상태에서 깨어났어도 락 획득에 실패하면 다시 sleep 상태로 들어간다.
30.2 생산자/소비자(유한 버퍼) 문제
동기화 문제인 생산자/소비자(producer/consumer) 또는 유한 버퍼(bounded 버퍼) 문제에 대해 살펴본다.
생산자 쓰레드는 데이터 만들어 버퍼에 넣고, 소비자 쓰레드는 버퍼에서 데이터를 꺼내 사용한다.
유한 버퍼는 공유 자원으로 경쟁 조건이 발생되지 않도록 동기화가 필요하다.
30.3 포함 조건(Covering Condition)
다수의 쓰레드가 메모리 공간의 발생을 대기하고 있는 경우 어떤 쓰레드를 깨워야할지 선택해야 한다.
이 문제를 해결하기 위해 대기 중인 모든 쓰레드에게 시그널을 보내 대기상태에서 준비상태로 전이하여 모든 쓰레드를 깨워서 실행한다.
깨어난 쓰레드들은 조건을 검사하고 만족하지 않으면 다시 대기모드로 들어가고 만족하면 실행을 계속한다.
이러한 방식을 포함 조건(Covering Condition) 이라고 한다.
하지만 불필요하게 많은 쓰레드를 깨우기 때문에 불필요한 문맥 전환이 발생될 수 있다는 것이 단점이다.
31장. 세마포어
세마포어(semaphore) 는 락과 컨디션 변수로 모두 사용할 수 있다.
31.1 세마포어: 정의
세마포어는 정수 값을 갖는 객체로 sem_wait() 와 sem_post() 루틴으로 조작할 수 있다.
세마포어는 초기값에 의해 동작이 결정되기 때문에 사용하기 전에 초기화를 해야 한다.
sem_wait()함수는 즉시 리턴하거나, 세마포어 값이 1이상이 될 때까지 호출자를 대기(spin or sleep)시킨다.sem_post()함수는 대기하지 않고 세마포어 값을 증가시키고 쓰레드 하나를 깨운다- 세마포어가 음수라면 그 값은 현재 대기 중인 쓰레드의 갯수와 같다.
31.2 이진 세마포어(락)
세마포어를 락에 적용해본다.
sem_wait() / sem_post() 쌍으로 임계 영역 부분을 둘러싼다.
sem_t m;
sem_init(&m, 0, X); // X 로 초기화, 초기 값은 1이 되어야 함
sem_wait(&m);
//임계 영역
sem_post(&m);
세마 포어를 락으로 사용할 수 있는데,
락은 두 개의 상태(사용 가능, 사용중)만 존재하므로 이진 세마포어(binary semaphore) 라고도 한다.
31.3 순서 보장을 위한 세마포어
세마포어는 사건들의 순서를 정하는데도 유용하다.
컨디션 변수를 사용했던 것과 유사하게 세마포어를 순서를 위한 도구로 사용할 수 있다.
부모 프로세스에서 자식 프로세스를 생성 후 sem_wait() 를 호출하여 자식 종료를 대기하고,
자식에서는 sem_post() 호출하여 종료를 알리면 된다.
여기서 세마포어 초기값은 0으로 설정하면 된다.
31.4 생산자/소비자 (유한 버퍼) 문제
다수의 생산자 쓰레드나 소비자 쓰레드가 존재할 경우 교착 상태가 발생되지 않도록 세심한 주의가 필요하다.
교착 상태 문제를 해결하기 위해서는 락의 범위(scope)를 줄여야 한다.
void *producer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
sem_wait(&empty);
sem_wait(&mutex);
put(i);
sem_post(&mutex);
sem_post(&full);
}
}
void *consumer(void *arg) {
int i;
for (i = 0; i < loops; i++) {
sem_wait(&full);
sem_wait(&mutex);
int tmp = get();
sem_post(&mutex);
sem_post(&empty);
printf("%d\n", tmp);
}
}
31.5 Reader-Writer 락
다수의 쓰레드가 연렬 리스트에 노드를 삽입하고 검색하는 상황을 가정한다.
이를 위해 만들어진 락이 reader-writer 락 이다.
이 기법에서는 자료구조를 갱신하려면 배타적 접근권한을 갖는 락을 사용하도록 한다.
하지만 쓰기 쓰레드에게 기아 현상이 발생하기 쉬워 공정성에 문제가 있는데,
이는 쓰기 쓰레드가 대기중일 때 읽기 쓰레드가 락을 획득하지 못하도록 해야 한다.
31.6 식사하는 철학자
다섯명의 철학자가 식탁 주위를 둘러 앉았고, 총 다섯 개의 포크가 철학자 사이에 하나씩 놓여있는 문제다.
철학자는 양쪽의 포크를 들어야 식사를 할 수 있다.
void get_forks(int p) {
if (p == 4) {
sem_wait(forks[right(p)]);
sem_wait(forks[left(p)]);
} else {
sem_wait(forks[left(p)]);
sem_wait(forks[right(p)]);
}
}
31.7 쓰레드 제어
과하게 많은 쓰레드가 동시에 수행되면 효율이 나빠진다.
이 현상을 방지하기 위해 세마포어를 사용하여 쓰레드 개수를 제한한다.
이러한 접근법을 제어(throttling) 이라 하며 수락 제어의 한 형태로 간주한다.
세마포어의 값을 메모리-집약 영역에 동시에 들어갈 수 있는 최대 쓰레드 개수로 초기화하고,
sem_wait() 와 sem_post()를 각각 추가하면서 쓰레드 개수를 통제한다.
31.8 세마포어 구현
락과 컨디션 변수를 사용하여 세마포어인 제마포어(Zemaphore) 를 구현해본다.
typedef struct __Zem_t {
int value;
pthread_cond_t cond;
pthread_mutex_t lock;
} Zem_t;
void Zem_init(Zem_t *s, int value) {
s->value = value;
Cond_init(&s->cond);
Mutex_init(&s->lock);
}
void Zem_wait(Zem_t *s) {
Mutex_lock(&s->lock);
while (s->value <= 0)
Cond_wait(&s->cond, &s->lock);
s->value--;
Mutex_unlock(&s->lock);
}
void Zem_post(Zem_t *s) {
Mutex_lock(&s->lock);
s->value++;
Cond_signal(&s->cond);
Mutex_unlock(&s->lock);
}
31.9 요약
세마포어는 병행 프로그램 작성을 위한 강력하고 유연한 기법이다.
32장. 병행성 관련 버그
교착 상태(deadlock) 를 비롯한 병행성 관련 오류를 자세하게 알아본다.
32.1 오류의 종류
32.2 비 교착 상태 오류
비 교착 상태 오류는 대표적으로 원자성 위반(atomicity violation) 오류와 순서 위반(order violation) 이 있다.
원자성 위반 오류
Thread 1::
if (thd->proc_info) {
fputs(thd->proc_info, ...);
}
Thread 2::
thd->proc_info = NULL;
첫번째 쓰레드에서 값을 검사한 후 fputs() 호출하기 전에 두 번째 쓰레드가 실행되면 NULL 포인터 참조 오류가 발생한다.
공유 변수 참조 앞 뒤에 락을 추가하여 proc_info 필드 NULL 검사와 fputs() 호출이 원자적으로 수행되어야 한다.
순서 위반 오류
Thread 1::
void init() {
mThread = PR_CreateThread(mMain, ...);
}
Thread 2::
void mMain(...) {
mState = mThread->State;
}
쓰레드 2의 코드는 mThread 변수가 이미 초기화 된 것을 가정하지만,
쓰레드 1이 먼저 실행되지 않으면 NULL 포인터 참조 오류가 발생한다.
이러한 오류는 컨디션 변수 를 활용하여 순서를 강제해야 한다.
비 교착 상태 오류: 정리
비 교착 상태 오류가 전체 오류 분포에서 많은 비중을 차지하기 때문에,
이러한 오류에 대해 초점을 맞춰야 한다.
32.3 교착 상태 오류
많은 병행 시스템에서는 교착 상태(deadlock) 문제가 발생된다.
아래 그래프에서 사이클(cycle) 의 존재는 교착 상태 발생 가능성을 의미한다.
교착 상태는 왜 발생하는가
- 구성 요소 간에 복잡한 의존성
- 캡슐화(encapsulation) 의 성질
- 모듈화와 락은 잘 조화되지 않음
- 호출한 응용 프로그램은 모르게 교착 상태 발생 될 수 있음
교착 상태 발생 조건
교착 상태가 발생하기 위해서는 아래 네 가지 조건이 모두 충족되어야 한다.
- 상호 배제(Mutual Exclusion)
- 쓰레드가 자신이 필요로 하는 자원에 대한 독자적인 제어권 주장
- 점유 및 대기(Hold-and-wait)
- 쓰레드가 자신에게 할당된 자원을 점유한 채로 다른 자원을 대기
- 비 선점(No preemption)
- 락을 점유하고 있는 쓰레드로부터 자원을 강제적으로 빼앗을 수 없음
- 환형 대기(Circular wait)
- 각 쓰레드는 다음 쓰레드가 요청한 하나 또는 그 이상의 락을 갖고 있는 쓰레드들의 순환 고리 존재
교착 상태의 예방
- 순환 대기(Circular Wait)
- 순환 대기가 발생하지 않도록 락 획득을 하는 전체 순서(total ordering) 을 정함
- 교착 상태를 피하기 위해 부분 순서(partial ordering) 만 정의할 수도 있음
- 점유 및 대기(Hold-and-Wait)
- 원자적으로 모든 락을 단번에 획득하도록 하여 예방
- 캡슐화로 인해 필요한 락들을 정확하게 파악하고 획득해야 하는 문제가 있음 (병행성 저하)
- 비선점(No Preemption)
- 다른 쓰레드에서 락이 점유되었다면 다시 획득을 시도하는 유연한 인터페이스 사용
- 무한반복(livelock) 이라는 문제가 발생 됨 (두 쓰레드 모두 락을 획득하지 못하여 진척이 안되는 경우)
- 상호 배제(Mutual Exclusion)
- 상호 배제를 없애기 위해 락이 없는(lock-free) 자교 구조 접근법
- 여러 쓰레드에 의해 동시에 호출 되면 경쟁 조건이 발생됨
- 스케줄링으로 교착 상태 회피하기
- 교착 상태를 예방하는 대신 회피가 더 유용할 수 있음
- 여러 쓰레드가 어떤 락을 획득할 것인지 파악하고 쓰레드들을 스케줄링하여 교착 상태가 발생되지 않도록 보장 필요
- 병행성에 제약이 생길 수 있음 (보편적인 방법은 아님)
- 발견 및 복구
- 교착 상태 발생을 허용하고 복구하는 방법
32.4 요약
- 비 교착 상태 오류
- 흔하지만 대체적으로 고치기 쉬운 오류들
- 원자성 위반, 순서 위반 오류 포함
- 교착 상태 오류
- 락 획득 순서를 정해서 애초에 교착 상태가 발생하지 않도록 예방 필요
33장. 이벤트 기반의 병행성(고급)
병행 프로그램을 제작하는 도구로 쓰레드뿐만 아니라 이벤트 기반의 병행성(event-based concurrency) 스타일도 있다. (node.js 서버 프레이뭐크에서 사용) 이벤트 기반의 프로그래밍으로 쓰레드 기반의 병령 프로그래밍의 두가지 문제를 해결할 수 있다.
- 멀티 쓰레드 기반 프로그래밍은 어려움
- 락 보호, 교착 상태 등 문제
- 개발자가 쓰레드 스케줄링에 대한 제어권이 없음
- 운영체제가 합리적으로 쓰레드들의 실행 순서를 결정하기만을 기대해야 함
33.1 기본 개념: 이벤트 루프
이벤트 기반의 병행성 접근 방법은 다음과 같다.
이벤트의 발생 대기 → 이벤트가 종류 파악 → I/O 요청 또는 추후 처리를 위한 다른 이벤트 발생 등의 작업
이벤트 기반의 서버는 이벤트 루프(event loop) 라는 단순한 구조를 갖는다.
루프내에서 이벤트 발생을 하나씩 처리하는데 이 처리하는 코드를 이벤트 핸들러(event handler) 라고 부른다.
while(1) {
events = getEvents();
for (e in events) {
processEvent(e);
}
}
33.2 중요 API: select() (또는 poll())
이벤트 발생은 select() 또는 poll() 시스템 콜을 통해 감지한다.
이 인터페이스들은 처리가 필요한 것들이 있는지 검사한다.
select()- 전체 집합에서 준비된 디스크립터(descriptor)들의 총 개수를 반환
- 디스크립터에 대한 읽기 또는 쓰기 가능여부 파악 가능
timeout디스크립터에 상태가 변경할 때까지 무한정 대기하거나 즉시 리턴하도록 설정 가능 (널리 0 으로 설정하여 즉시 리턴)
poll()select()시스템 콜과 유사
33.3 select() 의 사용
int main(void) {
while() {
// fd_set 를 모두 0으로 초기화
fd_set readFDs;
FD_ZERO(&readFDs);
// 서버가 관심 있어 하는 디스크립터들의 bit 설정
int fd;
for (fd = minFD; fd < maxFD; fd++) {
FD_SET(fd, &readFDs);
}
// 선택
int rc = select(maxFD+, &readFDs, NULL, NULL, NULL);
// FD_ISSET() 를 사용하여 실제 데이터 사용 여부 검사
int fd;
for (fd = minFD; fd < maxFD; fd++) {
if (FD_ISSET(fd, &readFDs)) {
processFD(fd);
}
}
}
}
33.4 왜 간단한가? 락이 필요 없음
쓰레드 기반 병행 프로그램의 문제점들이 발생되지 않음
한번에 하나의 이벤트만 처리하기 때문에 락 획득, 해제가 필요 없음 (단일 쓰레드 구성)
33.5 문제점: 블로킹 시스템 콜(Blocking System Call)
이벤트 기반의 접근법에서는 쓰레드가 없고 이벤트 루프만 존재한다.
이벤트 핸들러가 블로킹 콜을 호출하면 서버 전체가 그 일을 처리하기 위해 정지된다. (자원 낭비)
33.6 해법: 비동기 I/O
이벤트 기반 서버의 한계를 극복하기 위해 비동기 I/O(asynchronous I/O) 방법 개발
폴링(poll) 또는 인터럽트 기반의 시스템에서 시그널(signal) 을 사용하여 I/O 가 완료되었다고 프로그램에게 알린다.
33.7 또 다른 문제점: 상태관리
이벤트 기반 접근법은 이벤트 핸들러가 비동기 I/O 를 발생시킬 때 프로그램 상태를 관리해야 하기 때문에 일반적으로 쓰레드 기반 코드보다 복잡하다.
쓰레드 기반 프로그램에는 쓰레드 스택에 정보들이 들어있는데 이벤트 기반 프로그램에서는 이 정보들을 관리해야 한다.
이를 수동 스택 관리(manual stack management) 라고 한다.
이벤트 기반 서버에서는 continuation 개념을 사용하여,
이벤트 종료하는 데에 필요한 자료들을 한곳에 저장해두고 이벤트가 발생하면 이벤트를 처리한다.
33.8 이벤트 사용의 어려움
- 멀티 CPU 의 경우 복잡해짐
- 다수의 CPU 를 활용하기 위해 다수의 이벤트 핸들러를 병렬 실행
- 동기화 문제 발생하여 락과 같은 기법 필요
- 페이징(paging) 같은 시스템 작업과 조화롭게 실행 불가능
- 운영체제 내부적으로 발생하는 페이지 폴트 같은 경우에는 이벤트 서버가 블럭
- 루틴들의 작동 방식 변화
- 소프트웨어가 개성되고 갱신되면 루틴들의 특성이 변경될 수 있음
- 비동기 디스크 I/O 의 사용가능 여부
- 아직까지도 비동기 I/O 는 일관성 있게 적용되어 있지 않음
34장. 병랭성을 정리하는 대화
- 병행성은 가능하다면 피해야 함
- 어설프게 최적화된 프로그램은 더 좋지 않음