개발 공부
[운영체제][OSTEP] 락 기반의 병행 자료 구조
자료 구조에 락을 추가하여 쓰레드 사용에 안전한 구조를 만드는 방법에 대해 공부해봅니다.
![[운영체제][OSTEP] 락 기반의 병행 자료 구조](https://www.datocms-assets.com/66479/1686988115-ostep.jpg?auto=format&w=860)
🚪 들어가며
💡 쓰레드 사용에 안전(쓰레드 안전, thread safe)한 구조
자료 구조에 락을 추가하여 쓰레드가 사용할 수 있도록 만든 것
이번 챕터에서는 특정 자료 구조에 어떤 방식으로 락을 추가해야 그 자료 구조가 정확하게 동작하게 만들 수 있을지, 자료 구조에 락을 추가하여 여러 쓰레드가 그 자료 구조를 동시 사용(병행성) 가능하도록 하는 방법에 대해 알아보자.
1️⃣ 병행 카운터
카운터: 가장 간단한 자료 구조 중 하나(특정 원소가 몇 개 있는지 카운팅)
먼저 병행이 불가능한 카운터를 살펴보자.
typedef struct __counter_t {
int value;
} counter_t;
void init(counter_t *c) {
c−>value = 0;
}
void increment(counter_t *c) {
c−>value++;
}
void decrement(counter_t *c) {
c−>value−−;
}
int get(counter_t *c) {
return c−>value;
}다음은 락이 있는(쓰레드 안전(thread safe)한) 카운터이다.
typedef struct __counter_t {
int value;
pthread_mutex_t lock;
} counter_t;
void init(counter_t *c) {
c−>value = 0;
Pthread_mutex_init(&c−>lock, NULL);
}
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);
}
int get(counter_t *c) {
Pthread_mutex_lock(&c−>lock);
int rc = c−>value;
Pthread_mutex_unlock(&c−>lock);
return rc;
}위에서 우리는 다음을 확인할 수 있다.
자료 구조를 조작하는 루틴을 호출할 때 락을 추가한다.
루틴 호출 후 리턴 시 락이 해제된다.
위 방식은 모니터(monitor)를 사용하여 만든 자료 구조와 유사하다.
🔖 모니터 기법: 객체에 대한 메소드를 호출하고 리턴할 때 자동적으로 락을 획득하고 해제
이 방식을 통해 제대로 동작하는 병행 자료 구조를 가질 수 있지만, 성능 개선이 필요하다.
이상적으로는 하나의 쓰레드가 하나의 CPU에서 작업을 끝내는 것처럼 멀티프로세서에서 실행되는 쓰레드들도 빠르게 작업을 처리하고 싶음.
➡️ 이와 같은 것을 완벽한 확장성(perfect scaling)이라고 한다.
확장성 있는 카운팅
확장성 있는 카운터는 중요한 의미를 갖는다.
➡️ 확장 가능한 카운터가 없으면 Linux의 몇몇 작업은 멀티코어 기기에서 심각한 확장성 문제를 겪을 수 있음.
이러한 기법들 중 엉성한 카운터(sloppy counter)라는 것을 살펴보자.
엉성한 카운터는 하나의 논리적 카운터로 표현됨.
CPU 코어마다 존재하는 물리적인 지역 카운터와 하나의 전역 카운터로 구성
이 카운터들 외에 지역 카운터를 위한 락들과 전역 카운터를 위한 락이 존재
엉성한 카운터의 기본 개념은 다음과 같다.
쓰레드는 지역 카운터를 증가시킨다.
해당 지역 카운터는 지역 락에 의해 보호된다.
각 CPU 마다 지역 카운터가 존재하므로 CPU들에 분산된 쓰레드들은 지역 카운터를 경쟁 없이 갱신
➡️ 카운터 갱신은 확장성이 있음.
👀 쓰레드가 카운터의 값을 읽을 수 있음. ➡️ 전역 카운터를 최신 최신으로 갱신해야 함.
🛒 그러기 위해 지역 카운터의 값은 주기적으로 전역 카운터로 전달
➡️ 전역 락을 사용하여 지역 카운터의 값을 전역 카운터의 값에 더함.
➡️ 해당 지역 카운터의 값은 0으로 초기화
지역에서 전역으로 값을 전달하는 빈도는 정해 놓은 S(sloppiness의 앞 글자) 값에 의해 결정
➡️ S의 값이 작을수록 확장성 없는 카운터처럼 동작
➡️ 커질수록 전역 카운터의 값은 실제 값과 차이가 있게 됨.(CPU 개수 * S만큼 뒤처짐.)
정확한 카운터 값을 얻기 위해서는 모든 지역 락과 전역 락을 획득한 후 계산해야 함.
➡️ ⚠️ 이 경우 확장성이 없게 됨.
➡️ 지역 락을 획득하는 순서를 적절히 제어하지 않으면 교착 상태가 발생
다음의 예시와 함께 이를 조금 더 살펴보자.
Time │ L1 L2 L3 L4 │ G
─────┼──────────────────────────┼───────
0 │ 0 0 0 0 │ 0
1 │ 0 0 1 1 │ 0
2 │ 1 0 2 1 │ 0
3 │ 2 0 3 1 │ 0
4 │ 3 0 3 2 │ 0
5 │ 4 1 3 3 │ 0
6 │ 5→0 1 3 4 │ 5(from L1)
7 │ 0 2 4 5→0 │ 10(from L4)위의 예시에서는 한계치를 5로 설정하였고 네 개의 CPU에 각각의 지역 카운터 L1 ... L4를 갱신하는 쓰레드들이 있다.
만약 지역 카운터가 한계치 S에 도달하면 지역 값은 전역 카운터에 반영되고 지역 카운터의 값은 초기화된다.
💡 엉성한 카운터는 정확도(낮은 S값)와 성능(높은 S값)의 균형을 조절할 수 있다.
다음은 엉성한 카운터의 대략적인 코드이다.
typedef struct __counter_t {
int global; // 전역 카운터
pthread_mutex_t glock; // 전역 카운터
int local[NUMCPUS]; // 지역 카운터(cpu당)
pthread_mutex_t llock[NUMCPUS]; // ... 그리고 락들
int threshold; // 갱신 빈도
} counter_t;
// init: 한계치를 기록하고 락과 지역 카운터
// 그리고 전역 카운터의 값들을 초기화함
void init(counter_t *c, int threshold) {
c−>threshold = threshold;
c−>global = 0;
pthread_mutex_init(&c−>glock, NULL);
int i;
for (i = 0; i < NUMCPUS; i++) {
c−>local[i] = 0;
pthread_mutex_init(&c−>llock[i], NULL);
}
}
// update: 보통은 지역 락을 획득한 후 지역 값을 갱신함
// '한계치'까지 지역 카운터의 값이 커지면,
// 전역 락을 획득하고 지역 값을 전역 카운터에 전달함
void update(counter_t *c, int threadID, int amt) {
pthread_mutex_lock(&c−>llock[threadID]);
c−>local[threadID] += amt; // amt > 0을 가정
if (c−>local[threadID] >= c−>threshold) { // 전역으로 전달
pthread_mutex_lock(&c−>glock);
c−>global += c−>local[threadID];
pthread_mutex_unlock(&c−>glock);
c−>local[threadID] = 0;
}
pthread_mutex_unlock(&c−>llock[threadID]);
}
// get: 전역 카운터의 값을 리턴(정확하지 않을 수 있음)
int get(counter_t *c) {
pthread_mutex_lock(&c−>glock);
int val = c−>global;
pthread_mutex_unlock(&c−>glock);
return val; // 대략의 값임!
}2️⃣ 병행 연결 리스트
병행 삽입 연산을 중점적으로 살펴보도록 하자.
// 기본 노드 구조
typedef struct __node_t {
int key;
struct __node_t *next;
} node_t;
// 기본 리스트 구조(리스트마다 하나씩 사용)
typedef struct __list_t {
node_t *head;
pthread_mutex_t lock;
} list_t;
void List_Init(list_t *L) {
L−>head = NULL;
pthread_mutex_init(&L−>lock, NULL);
}
int List_Insert(list_t *L, int key) {
pthread_mutex_lock(&L−>lock);
node_t *new = malloc(sizeof(node_t));
if (new == NULL) {
perror("malloc");
pthread_mutex_unlock(&L−>lock);
return −1; // 실패
}
new−>key = key;
new−>next = L−>head;
L−>head = new;
pthread_mutex_unlock(&L−>lock);
return 0; // 성공
}
int List_Lookup(list_t *L, int key) {
pthread_mutex_lock(&L−>lock);
node_t *curr = L−>head;
while (curr) {
if (curr−>key == key) {
pthread_mutex_unlock(&L−>lock);
return 0; // 성공
}
curr = curr−>next;
}
pthread_mutex_unlock(&L−>lock);
return −1; // 오류
}삽입 연산을 시작하기 전에 락을 획득하고 리턴 직전에 해제함.
매우 드물게 malloc()이 실패할 경우 미묘한 문제가 생길 수 있음.
➡️ 그러한 경우 실패를 처리하기 전에 락을 해제해야 함.
🤔 삽입 연산이 병행하여 진행되는 상황에서 실패를 하더라도 락 해제를 호출하지 않으면서 삽입과 검색이 올바르게 동작하도록 수정할 수 있을까?
➡️ ✅ 가능하다.
➡️ 삽입 코드에서 임계 영역을 처리하는 부분만 락으로 감싸도록 코드 순서를 변경하고, 검색 코드의 종료는 검색과 삽입 모두 동일한 코드 패스를 사용하도록 할 수 있음.
➡️ 검색 코드의 일부는 사실 락이 필요 없기 때문
개선된 다음의 코드를 살펴보자.
void List_Init(list_t *L) {
L−>head = NULL;
pthread_mutex_init(&L−>lock, NULL);
}
void List_Insert(list_t *L, int key) {
// 동기화할 필요 없음
node_t *new = malloc(sizeof(node_t));
if (new == NULL) {
perror(“malloc ”);
return;
}
new−>key = key;
// 임계 영역만 락으로 보호
pthread_mutex_lock(&L−>lock);
new−>next = L−>head;
L−>head = new;
pthread_mutex_unlock(&L−>lock);
}
int List_Lookup(list_t *L, int key) {
int rv = −1;
pthread_mutex_lock(&L−>lock);
node_t *curr = L−>head;
while (curr) {
if (curr−>key == key) {
rv = 0;
break;
}
curr = curr−>next;
}
pthread_mutex_unlock(&L−>lock);
return rv; // 성공과 실패를 나타냄
}검색 루틴의 while 문 안에 break를 삽입하여 검색이 성공하면 바로 빠져나오게 수정
➡️ 검색 성공/실패 경우 모두 동일한 리턴 코드를 실행
위와 같이 작성 시 코드에서 락을 획득하고 해제하는 문장 수를 줄일 수 있음.
➡️ 버그(락 해제 없이 리턴 등) 발생 여지가 줄어 듦.
확장성 있는 연결 리스트
병행성을 개선하는 방법 중 하나로 hand-over-hand locking(또는 lock coupling)이라는 기법을 개발함.
➡️ 💡 전체 리스트에 하나의 락이 있는 것이 아니라 개별 노드마다 락을 추가
🚋 리스트를 순회할 때 다음 노드의 락을 먼저 획득하고 지금 노드의 락을 해제
⚠️ 실제로는 간단한 락 방법(한 개의 락)에 비해 속도 개선을 기대하기가 쉽지 않음.
➡️ 각 노드의 락 획득/해제 시 큰 오버헤드 발생
💡 일정 개수의 노드를 처리할 때마다 하나의 새로운 락을 획득하는 하이브리드 방식이 더 가치 있어 보임.
락과 제어 흐름을 경계하자
⚠️ 함수의 흐름이 바뀌는 부분(return, exit, 에러)으로 인한 실행 중지에 매우 세심한 주의를 기울여야 함.
➡️ 많은 함수들이 락 획득, 메모리 할당, 상태 변경 연산들을 실행하는 데 에러가 발생하면 리턴하기 전에 이들을 이전 상태로 복구해야 하기 때문
➡️ ☄️ 이 과정에서 에러가 발생하기 쉬움.
3️⃣ 병행 큐
큰 락을 사용하는 것이 병행 자료 구조를 만들기에 표준임.
➡️ 큐에서는 이 방법을 사용하지 않을 것임.
다음은 Michael과 Scott이 설계한 조금 더 병행성이 좋은 큐의 코드이다.
typedef struct __node_t {
int value;
struct __node_t *next;
} node_t;
typedef struct __queue_t {
node_t *head;
node_t *tail;
pthread_mutex_t headLock;
pthread_mutex_t tailLock;
} queue_t;
void Queue_Init(queue_t *q) {
node_t *tmp = malloc(sizeof(node_t));
tmp−>next = NULL;
q−>head = q−>tail = tmp;
pthread_mutex_init(&q−>headLock, NULL);
pthread_mutex_init(&q−>tailLock, NULL);
}
void Queue_Enqueue(queue_t *q, int value) {
node_t *tmp = malloc(sizeof(node_t));
assert(tmp != NULL);
tmp−>value = value;
tmp−>next = NULL;
pthread_mutex_lock(&q−>tailLock);
q−>tail−>next = tmp;
q−>tail = tmp;
pthread_mutex_unlock(&q−>tailLock);
}
int Queue_Dequeue(queue_t *q, int *value) {
pthread_mutex_lock(&q−>headLock);
node_t *tmp = q−>head;
node_t *newHead = tmp−>next;
if (newHead == NULL) {
pthread_mutex_unlock(&q−>headLock);
return −1; // 큐가 비어 있음
}
*value = newHead−>value;
q−>head = newHead;
pthread_mutex_unlock(&q−>headLock);
free(tmp);
return 0;
}🔒 위의 코드에는 두 개의 락이 있음.
큐의 헤드
큐의 테일
이 두 개의 락은 큐에 삽입과 추출 연산에 병행성을 부여하는 것이 목적
➡️ 일반적인 경우에는 삽입 루틴이 테일 락을 접근하고 추출 연산이 헤드 락만을 다룸.
Michael과 Scott은 큐 초기화 코드에 더미(dummy) 노드 하나를 추가함.
➡️ 헤드와 테일 연산을 구분하는 데 사용
🧵 큐는 멀티 쓰레드 프로그램에서 자주 사용됨.
➡️ 🚫 위의 락만 있는 큐는 그런 프로그램에서 사용할 수 없음.
➡️ 🚧 큐가 비었거나 가득 찬 경우, 쓰레드가 대기하도록 하는 기능이 필요
4️⃣ 병행 해시 테이블
#define BUCKETS ()
typedef struct __hash_t {
list_t lists[BUCKETS];
} hash_t;
void Hash_Init(hash_t *H) {
int i;
for (i = ; i < BUCKETS; i++) {
List_Init(&H−>lists[i]);
}
}
int Hash_Insert(hash_t *H, int key) {
int bucket = key % BUCKETS;
return List_Insert(&H−>lists[bucket], key);
}
int Hash_Lookup(hash_t *H, int key) {
int bucket = key % BUCKETS;
return List_Lookup(&H−>lists[bucket], key);
}위의 코드는 앞선 병행 리스트를 사용하여 구현한 확장 되지 않는 간단한 해시 테이블의 코드이다.
전체 자료 구조에 하나의 락을 사용한 것이 아니라 리스트로 구현된 해시 버켓마다 락을 사용함.
➡️ 병행성이 좋아짐.
🧺 락 기반의 병행 자료 구조 정리하기
⚠️ 락의 획득과 해제 시 코드의 흐름에 매우 주의를 기울여야 함.
병행성 개선이 반드시 성능 개선으로 이어지는 것은 아님.
➡️ 성능 개선은 성능에 문제가 생길 경우에만 해결책을 간구해야 함.미숙한 최적화(premature optimization)를 피하자.
➡️ 부분적인 성능 개선 시도가 응용 프로그램의 전체 성능을 개선하지 못하면 아무 의미가 없음.
🔖 미숙한 최적화를 피하자(Knuth's Law)
Sun 운영체제와 Linux를 포함한 많은 운영체제가 처음 멀티프로세서 용으로 변화할 때 하나의 락을 사용했었음.
➡️ 큰 커널 락(big kernal lock, BKL)
➡️ 오랫동안 이 기법만으로 충분했으나, 멀티 CPU 시스템이 대중화되면서 개선 작업이 이루어짐.
📚 참고 문헌
Operating Systems: Three Easy Pieces ― 29: Lock-based Concurrent Data Structures
![[운영체제][OSTEP] 락](https://www.datocms-assets.com/66479/1686988115-ostep.jpg?ar=1&auto=format&crop=focalpoint&dpr=0.47&fit=crop&fp-x=0.5&fp-y=0.5&w=430)