락(Lock)의 구현 및 알고리즘 상세 개요

락(Lock) 개요

락(Lock)은 멀티스레드 또는 멀티프로세스 환경에서 공유 자원에 대한 동시 접근을 제어하는 기술입니다.
동기화(Synchronization) 메커니즘의 일부로 사용되며, 데이터 정합성을 보장하고, 경쟁 조건(Race Condition)을 방지하는 역할을 합니다.

 

락을 구현할 때 고려해야 할 주요 요소는 다음과 같습니다.

1. 상호 배제(Mutual Exclusion) - 동시에 하나의 프로세스/스레드만 자원에 접근할 수 있도록 보장
2. 공정성(Fairness) - 특정 스레드가 계속해서 대기하는 기아 상태(Starvation)를 방지
3. 데드락(Deadlock) 방지 - 여러 개의 스레드가 서로의 락을 기다리는 교착 상태를 예방
4. 성능 및 확장성 - 락이 시스템의 성능 저하를 유발하지 않도록 최적화

 

 

 

락 구현 방식

소프트웨어 기반 락

운영체제나 프로그래밍 언어에서 제공하는 락 메커니즘을 활용하여 구현됩니다.

 

뮤텍스(Mutex, Mutual Exclusion)

뮤텍스는 한 번에 하나의 스레드만 특정 코드 블록을 실행하도록 보호하는 방식입니다.
운영체제에서 제공하는 pthread_mutex_lock() / pthread_mutex_unlock() (POSIX 스레드) 또는 std::mutex (C++)에서 사용됩니다.

뮤텍스 구현 예제 (C++)

#include <iostream>
#include <thread>
#include <mutex>

std::mutex mtx;

void critical_section(int id) {
    mtx.lock();
    std::cout << "스레드 " << id << " 가 임계 영역에 진입\n";
    std::this_thread::sleep_for(std::chrono::seconds(1));
    std::cout << "스레드 " << id << " 가 임계 영역을 벗어남\n";
    mtx.unlock();
}

int main() {
    std::thread t1(critical_section, 1);
    std::thread t2(critical_section, 2);

    t1.join();
    t2.join();
    return 0;
}

특징

• 단순한 구현으로 상호 배제를 보장
• 한 스레드가 락을 해제하지 않으면 데드락(Deadlock) 발생 가능
• 락을 획득할 때 스레드가 블로킹(Block)되어 대기하므로 성능이 저하될 수 있음

 

스핀락(Spinlock)

스핀락은 락이 해제될 때까지 반복적으로 확인(바쁜 대기, Busy Waiting)을 수행하는 방식입니다.
POSIX에서는 pthread_spin_lock()을 지원하며, 짧은 시간 동안 유지되는 락에서 효과적입니다.

스핀락 구현 예제 (C)

#include <pthread.h>
#include <stdio.h>

pthread_spinlock_t spinlock;

void* worker(void* arg) {
    pthread_spin_lock(&spinlock);
    printf("스레드 %ld: 락 획득\n", (long)arg);
    pthread_spin_unlock(&spinlock);
    return NULL;
}

int main() {
    pthread_spin_init(&spinlock, 0);
    pthread_t t1, t2;

    pthread_create(&t1, NULL, worker, (void*)1);
    pthread_create(&t2, NULL, worker, (void*)2);

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    pthread_spin_destroy(&spinlock);
    return 0;
}

특징

• 락을 빠르게 획득할 수 있음
• 짧은 시간 동안 유지되는 락에서 효과적
• CPU 리소스를 지속적으로 사용하므로 장기적인 대기에는 비효율적

 

리더-라이터 락(Read-Write Lock)

리더-라이터 락은 읽기 작업은 여러 프로세스가 동시에 수행 가능하지만, 쓰기 작업은 하나의 프로세스만 수행할 수 있도록 제한하는 방식입니다.
POSIX 스레드에서는 pthread_rwlock_rdlock() / pthread_rwlock_wrlock()으로 구현됩니다.

특징

• 읽기 작업이 많은 경우 성능 최적화 가능
• 쓰기 작업이 많으면 일반 뮤텍스와 성능 차이가 크지 않음
• 기아 상태(Starvation) 발생 가능성 있음 (쓰기 작업이 계속해서 대기할 수도 있음)

 

하드웨어 지원 기반 락

하드웨어에서 제공하는 원자적 연산(Atomic Operation)을 활용하여 락을 구현할 수 있습니다.

 

원자적 연산(Atomic Operation)

• 하드웨어에서 제공하는 Compare-And-Swap (CAS) 또는 Fetch-And-Add (FAA) 명령어를 사용하여 락을 구현할 수 있습니다.

CAS (Compare-And-Swap)

CAS는 기존 값을 예상 값과 비교하고, 같으면 새로운 값으로 교체하는 방식입니다.

#include <atomic>
#include <iostream>

std::atomic<int> lock_flag(0);

void lock() {
    while (!lock_flag.compare_exchange_weak(0, 1));
}

void unlock() {
    lock_flag.store(0);
}

void critical_section() {
    lock();
    std::cout << "임계 영역 실행 중\n";
    unlock();
}

특징

• 락 프리(Lock-Free) 동기화 가능
• 성능이 우수하지만, 올바르게 사용하지 않으면 무한 루프 발생 가능
• 캐시 일관성 문제가 발생할 가능성 있음

 

락 프리(Lock-Free) 알고리즘

락을 사용하지 않고도 동기화를 보장하는 방식으로, 비동기 환경에서 높은 성능을 제공합니다.

 

Lock-Free Queue (CAS 기반)

#include <atomic>
#include <iostream>

struct Node {
    int value;
    Node* next;
};

std::atomic<Node*> head(nullptr);

void push(int value) {
    Node* new_node = new Node{value, nullptr};
    do {
        new_node->next = head.load();
    } while (!head.compare_exchange_weak(new_node->next, new_node));
}

int pop() {
    Node* old_head;
    do {
        old_head = head.load();
        if (!old_head) return -1;
    } while (!head.compare_exchange_weak(old_head, old_head->next));
    int value = old_head->value;
    delete old_head;
    return value;
}

특징

• 동시성이 높고, 데드락이 발생하지 않음
• 비동기 환경에서 성능이 뛰어남
• 메모리 관리가 복잡할 수 있음 (Garbage Collection 고려 필요)

 

 

 

결론

• 락은 데이터 정합성을 유지하고 경쟁 조건을 해결하는 필수적인 기법입니다.
• 뮤텍스, 스핀락, 리더-라이터 락 등 상황에 따라 적절한 락을 선택하는 것이 중요합니다.
• 락 프리(Lock-Free) 알고리즘을 활용하면 성능을 크게 향상시킬 수 있습니다.
• 하지만 과도한 락 사용은 성능 저하, 데드락 발생 가능성 등의 문제를 초래할 수 있으므로 최적의 방식으로 적용해야 합니다.

 

락을 효율적으로 사용하는 것은 성능과 안정성을 동시에 확보하는 핵심 요소가 됩니다.