참고

https://os2024.jeju.ai/week11/threads-locks.html

https://os2024.jeju.ai/week11/threads-locks-usage.html

락

락(Lock)은 코드의 특정 영역을 감싸서 한 순간에 오로지 한 스레드만 이 영역에 접근할 수 있도록 해주는 동기화 메커니즘입니다. 즉, 락은 여러 스레드가 공유 자원에 동시에 접근하는 것을 제어하여 상호 배제(Mutual Exclusion)를 보장합니다.

락의 개념

예를 들어, 다음과 같은 공유 자원에 대한 연산이 있다고 가정해봅시다.

balance = balance + 1;

이 코드를 임계 영역(Critical Section)이라고 하며, 락을 사용하여 다음과 같이 보호할 수 있습니다.

lock_t mutex; // 전역 변수로 선언된 락
...
lock(&mutex);
balance = balance + 1;
unlock(&mutex);

락은 하나의 변수로 표현되며, 사용하기 전에 먼저 선언해야 합니다. 이 락 변수는 두 가지 상태를 가질 수 있습니다.

1. 사용 가능 상태: 어느 스레드도 락을 가지고 있지 않은 상태
2. 사용 중 상태: 임계 영역에서 정확히 하나의 스레드가 락을 획득한 상태

lock() 함수는 락을 획득하려고 시도하고, unlock() 함수는 획득한 락을 해제합니다. 어떤 스레드가 lock() 함수를 호출하여 락을 획득하면, 해당 스레드를 락의 소유자(Owner)라고 부릅니다. 락이 이미 다른 스레드에 의해 사용 중인 경우, lock() 함수는 해당 락이 해제될 때까지 대기합니다.

락의 소유자가 unlock() 함수를 호출하면 락은 다시 사용 가능한 상태가 됩니다. 만약 어떤 스레드도 해당 락을 기다리고 있지 않다면, 락은 사용 가능한 상태로 유지됩니다.

락은 프로그래머에게 스케줄링에 대한 제어권을 제공하여 특정 코드 영역 내에서 한 번에 하나의 스레드만 실행되도록 보장합니다. 이를 통해 스레드 간의 잘못된 실행 순서로 인한 문제를 예방할 수 있습니다.

락 기반 병행 자료 구조

병행 자료 구조(Concurrent Data Structures)란 다수의 스레드가 동시에 접근할 수 있는 자료 구조를 말합니다. 이러한 자료 구조는 병행성(Concurrency) 문제를 해결하기 위해 락(Lock)을 사용하여 데이터의 일관성(Consistency)을 유지합니다.

병행 카운터

여러 스레드가 동시에 카운터 값을 변경할 때도 그 값이 정확하게 유지되어야 한다.

pthread_mutex_t lock;
int counter = 0;

void increment() {
    pthread_mutex_lock(&lock);  // 락 획득
    counter++;                  // 카운터 증가
    pthread_mutex_unlock(&lock);  // 락 해제
}

void decrement() {
    pthread_mutex_lock(&lock);  // 락 획득
    counter--;                  // 카운터 감소
    pthread_mutex_unlock(&lock);  // 락 해제
}

increment()와 decrement() 함수를 사용하여 락을 획득한 후 카운터 값을 변경하고, 마지막에 락을 해제하는 방법을 통해 카운터 값의 일관성을 유지한다. 간단하게 구현할 수 있지만 단점으로는 모든 연산에 락을 사용하므로 성능 저하가 발생할 수 있다.

병행 카운터는 웹 서버에서 활성 사용자 수를 추적하거나, 데이터베이스에서 특정 이벤트 발생 횟수를 기록하는 등 다양한 응용 프로그램에서 사용됩니다.

병행 연결 리스트

typedef struct Node {
    int data;
    struct Node* next;
    pthread_mutex_t lock;
} Node;

Node* head = NULL;
pthread_mutex_t list_lock = PTHREAD_MUTEX_INITIALIZER;

void add_node(int value) {
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = value;
    pthread_mutex_init(&new_node->lock, NULL);

    pthread_mutex_lock(&list_lock);  // 리스트 락 획득
    new_node->next = head;
    head = new_node;
    pthread_mutex_unlock(&list_lock);  // 리스트 락 해제
}

void remove_node(int value) {
    pthread_mutex_lock(&list_lock);  // 리스트 락 획득
    Node* current = head;
    Node* prev = NULL;

    while (current != NULL) {
        if (current->data == value) {
            if (prev == NULL) {
                head = current->next;
            } else {
                prev->next = current->next;
            }
            pthread_mutex_destroy(&current->lock);
            free(current);
            break;
        }
        prev = current;
        current = current->next;
    }
    pthread_mutex_unlock(&list_lock);  // 리스트 락 해제
}

• 연결 리스트 전체에 대한 하나의 락(list_lock)을 사용하여 노드 추가와 삭제 연산을 제어.
• 노드 추가 시에는 새로운 노드를 생성하고 락을 초기화한 후, 리스트 락을 획득하여 새 노드를 리스트의 head에 추가.
• 노드 삭제 시에는 리스트 락을 획득한 후 리스트를 탐색하여 해당 노드를 찾아 제거.

병행 연결 리스트란?

다수의 스레드가 동시에 노드를 추가하거나 삭제할 수 있는 연결 리스트입니다. 이때 락을 사용하여 스레드 간의 노드 접근을 안전하게 제어한다.

병행 연결 리스트는 노드별로 락을 사용하거나, 전체 리스트에 대한 하나의 락을 사용할 수 있습니다.

스레드가 노드에 접근하려는 이유가 뭐지?

병행 연결 리스트에서 전체 리스트 락(one-lock) 방식과 노드별 락(per-node lock) 방식의 차이는 무엇인가?

병행 리스트 vs 병행 카운터

병행 리스트의 단점으로 카운트 값을 변경할 때마다 락을 걸어야 하는 문제로 인해 성능 저하가 발생한다고 했는데 병행 리스트는 병행 카운터보다 얼마만큼의 성능 향상이 발생하는 걸까?
예를 들어, 병행 카운터는 카운터 값을 변경할 때마다 락을 걸어줘야 해서 성능 저하가 발생할 수 있지만 병행 리스트는 전체 리스트에 대한 하나의 락을 사용할 수 있으니까 병행 카운터보다는 더 좋은 퍼포먼스를 낼 수 있지 않을까?

병행 연결 리스트를 사용하는 이유가 뭘까?

운영체제의 스케줄러, 메모리 할당기, 네트워크 프로토콜 스택 등 다양한 시스템 소프트웨어에서 사용됩니다. 예를 들어, 스케줄러는 실행 중인 프로세스나 스레드의 목록을 관리하기 위해 병행 연결 리스트를 활용할 수 있습니다.

병행 큐

typedef struct QueueNode {
    int data;
    struct QueueNode* next;
} QueueNode;

typedef struct {
    QueueNode* front;
    QueueNode* rear;
    pthread_mutex_t lock;
    pthread_cond_t cond;
} Queue;

void enqueue(Queue* q, int value) {
    QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
    new_node->data = value;
    new_node->next = NULL;

    pthread_mutex_lock(&q->lock);  // 큐 락 획득
    if (q->rear == NULL) {
        q->front = new_node;
        q->rear = new_node;
    } else {
        q->rear->next = new_node;
        q->rear = new_node;
    }
    pthread_cond_signal(&q->cond);  // 대기 중인 스레드에 시그널 전송
    pthread_mutex_unlock(&q->lock);  // 큐 락 해제
}

int dequeue(Queue* q) {
    pthread_mutex_lock(&q->lock);  // 큐 락 획득
    while (q->front == NULL) {
        pthread_cond_wait(&q->cond, &q->lock);  // 조건 변수를 사용하여 대기
    }
    QueueNode* temp = q->front;
    int value = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    pthread_mutex_unlock(&q->lock);  // 큐 락 해제
    return value;
}

대기 중인 스레드에 시그널을 전송한다?

dequeue 부분에서 조건 변수를 사용하여 대기할 때 큐가 비어있다면 새로운 노드가 생성될 때까지 스레드를 대기시키는 건가?

큐 전체에 대한 하나의 락(lock)과 조건 변수(cond)를 사용합니다. enqueue() 함수에서는 큐 락을 획득한 후 새로운 노드를 큐의 rear에 추가하고, 대기 중인 스레드에 시그널을 보냅니다. dequeue() 함수에서는 큐 락을 획득하고, 큐가 비어 있는 경우 조건 변수를 사용하여 대기합니다. 큐에 요소가 있으면 front 노드를 제거하고 해당 값을 반환합니다.

병행 큐란?

다수의 스레드가 동시에 요소를 삽입하거나 제거할 수 있는 큐.

병행 큐를 사용하는 이유가 뭘까?

병행 큐는 삽입 연산과 제거 연산에 대해 별도의 락을 사용할 수 있습니다. 이를 통해 삽입과 제거가 동시에 이루어질 수 있어 성능이 향상.

로그 시스템, 작업 스케줄러, 메시지 전달 시스템 등 생산자-소비자 패턴이 필요한 다양한 응용 프로그램에서 사용될 수 있음.

삽입과 제거 연산에 별도의 락을 사용할 수 있다는 것은 병행 카운터처럼 모든 연산에 락을 사용하는 것이고, 결국 성능 저하가 발생한다는 말이 아닌가?

삽입과 제거가 동시에 이루어진다는 게 무슨 말이지?

병행 리스트 vs 병행 큐

병행 리스트는 병행 큐처럼 동시에 삽입 삭제가 불가능할까?

병행 해시 테이블

#define HASH_SIZE 101

typedef struct HashNode {
    int key;
    int value;
    struct HashNode* next;
    pthread_mutex_t lock;
} HashNode;

typedef struct {
    HashNode* buckets[HASH_SIZE];
    pthread_mutex_t table_lock;
} HashTable;

unsigned int hash(int key) {
    return key % HASH_SIZE;
}

void insert(HashTable* table, int key, int value) {
    unsigned int index = hash(key);
    pthread_mutex_lock(&table->table_lock);  // 테이블 락 획득

    HashNode* new_node = (HashNode*)malloc(sizeof(HashNode));
    new_node->key = key;
    new_node->value = value;
    pthread_mutex_init(&new_node->lock, NULL);

    new_node->next = table->buckets[index];
    table->buckets[index] = new_node;

    pthread_mutex_unlock(&table->table_lock);  // 테이블 락 해제
}

int lookup(HashTable* table, int key) {
    unsigned int index = hash(key);
    pthread_mutex_lock(&table->table_lock);  // 테이블 락 획득

    HashNode* current = table->buckets[index];
    while (current != NULL) {
        if (current->key == key) {
            pthread_mutex_unlock(&table->table_lock);  // 테이블 락 해제
            return current->value;
        }
        current = current->next;
    }

    pthread_mutex_unlock(&table->table_lock);  // 테이블 락 해제
    return -1; // 키를 찾지 못한 경우
}

병행 해시 테이블이란?

병행 해시 테이블은 다수의 스레드가 동시에 키-값 쌍을 삽입, 삭제 또는 조회할 수 있는 해시 테이블입니다. 병행 해시 테이블은 성능 향상을 위해 버킷(Bucket) 단위로 락을 사용할 수 있습니다.

각 버킷에 대해 개별적인 락을 사용하면 서로 다른 버킷에 대한 연산이 동시에 이루어질 수 있어 성능이 크게 향상.

버킷 단위로 락을 사용할 수 있다는 게 무슨 말일까? 그리고 이게 성능 향상과 연관되어 있는 이유는 뭘까?

병행 해시 테이블은 어디에 사용될까?

웹 서버의 세션 관리 시스템에서는 세션 정보를 병행 해시 테이블에 저장하여 여러 스레드가 동시에 세션 정보를 효율적으로 조회하고 갱신할 수 있어서 데이터베이스 시스템, 캐시 시스템, 네트워크 라우팅 테이블 등 다양한 응용 프로그램에서 사용됩니다.

여러 스레드가 동시에 세션 정보에 접근하는 경우가 어떤 게 있을까?

병행 해시 테이블은 병행 리스트, 병행 큐와 어떤 다른 점은 뭐지?

락 기반 병행 자료 구조의 장단점

락 기반의 병행 자료 구조는 다음과 같은 장단점을 가지고 있습니다.

장점:

• 구현이 비교적 간단하고 직관적입니다.
• 데이터의 일관성을 보장할 수 있습니다.
• 다양한 자료 구조에 적용할 수 있습니다.

단점:

• 락 사용으로 인한 성능 저하가 발생할 수 있습니다.
• 락 경합이 발생하면 효율이 크게 떨어질 수 있습니다.
• 데드락이나 라이브락 등의 문제가 발생할 수 있습니다.
• 락의 개수가 많아질수록 메모리 오버헤드가 증가합니다.

질문

1. 병행 자료 구조(Concurrent Data Structure)란 무엇이며, 왜 락(Lock)을 사용하는가?
2. 병행 카운터(Concurrent Counter)를 락 기반으로 구현했을 때의 장점과 단점은 무엇인가?
3. 락의 granularity(범위) 조절이 왜 중요한가?
4. 락 기반 병행 자료 구조의 장점은 무엇이며, 반대로 어떤 단점이 존재하는가?
5. 병행 연결 리스트에서 전체 리스트 락(one-lock) 방식과 노드별 락(per-node lock) 방식의 차이는 무엇인가?
6. 노드별 락을 사용할 때 생길 수 있는 데드락(Deadlock) 또는 라이브락(Livelock)의 시나리오를 예로 들어 설명해 보라.
7. 병행 해시 테이블(Concurrent Hash Table)을 버킷 단위 락(bucket-level lock)로 구현하는 것과 테이블 전체 락(table-level lock) 방식의 차이점은 무엇인가?
8. 왜 “락 없는(Lock-Free)” 병행 자료 구조가 대안으로 제시되었으며, 그 방식이 락 기반 방식에 비해 가지는 장점과 단점은 무엇인가?
9. 실제 시스템(예: 웹 서버, 데이터베이스, 네트워크 라우팅 테이블)에서 병행 자료 구조가 어떤 용도로 사용되는지 예를 들어 설명하라.
10. 데드락, 라이브락, 락 경합(Lock Contention) 등의 문제가 병행 자료 구조에서 어떻게 발생할 수 있는가?