Semaphore (세마포어)

Dijkstra의 P/V 연산에서 시작된 semaphore의 이론적 배경과 Linux 커널 구현을 분석합니다. struct semaphore의 down/up 경로, Counting Semaphore 패턴, Binary Semaphore와 Mutex의 차이, rw_semaphore의 Optimistic Spinning과 HANDOFF 메커니즘, 레거시 마이그레이션 역사, 리소스 풀 관리 패턴, PREEMPT_RT 영향까지 포괄합니다.

이론적 배경: Dijkstra의 P/V 연산

Semaphore는 1965년 네덜란드 컴퓨터 과학자 Edsger W. Dijkstra가 "Cooperating Sequential Processes"에서 제안한 동기화 프리미티브입니다. 이름은 철도 신호기(semaphore)에서 따왔으며, P와 V 연산은 네덜란드어에서 유래합니다.

P/V 연산의 어원

형식적 정의

/* Dijkstra의 원래 정의 (의사 코드) */

P(S):                          /* proberen — 시도 */
    while (S.count <= 0)
        sleep(S.wait_queue);    /* 카운트가 0이면 대기 */
    S.count--;                   /* 카운트 감소 */

V(S):                          /* verhogen — 증가 */
    S.count++;                   /* 카운트 증가 */
    if (waiters_exist(S))
        wakeup(S.wait_queue);  /* 대기자가 있으면 깨움 */

Semaphore 분류

Semaphore vs Mutex: 차이와 선택 기준

Linux 2.6.16에서 struct mutex가 도입된 이후, semaphore의 대부분 사용처가 mutex로 대체되었습니다. 두 프리미티브의 근본적 차이를 정확히 이해해야 올바른 선택이 가능합니다.

struct semaphore 분석

Linux 커널의 struct semaphore는 놀라울 정도로 단순합니다. 세 개의 필드만으로 구성됩니다.

/* include/linux/semaphore.h */

struct semaphore {
    raw_spinlock_t      lock;       /* 내부 상태 보호용 스핀락 */
    unsigned int        count;      /* 사용 가능한 리소스 수 */
    struct list_head    wait_list;  /* 대기 중인 태스크 목록 */
};

초기화 매크로(Macro)

/* 정적 초기화 */
DEFINE_SEMAPHORE(name, n);           /* count = n으로 초기화 (v6.7+) */

/* 구버전 호환 (count = 1) */
DEFINE_SEMAPHORE(name);               /* 일부 구버전에서 count = 1 */

/* 동적 초기화 */
sema_init(&sem, 5);                  /* count = 5 (Counting Semaphore) */
sema_init(&sem, 1);                  /* count = 1 (Binary Semaphore) */
sema_init(&sem, 0);                  /* count = 0 (완료 신호 패턴) */

Semaphore API 레퍼런스

/* 올바른 사용 예 */

/* down_interruptible — 사용자 공간 프로세스에 적합 */
if (down_interruptible(&my_sem)) {
    /* 시그널에 의해 중단됨 — 정리 후 -EINTR 반환 */
    return -ERESTARTSYS;
}
/* 임계 영역 */
up(&my_sem);

/* down_trylock — 폴링 또는 fallback 경로 */
if (down_trylock(&my_sem) == 0) {
    /* 성공적으로 획득 */
    do_work();
    up(&my_sem);
} else {
    /* 획득 실패 — 대안 경로 */
    try_alternative();
}

down() 구현 분석

down() 함수는 fast path와 slow path로 나뉩니다. fast path에서는 count를 감소시키고 즉시 반환하며, count가 0이면 slow path에서 태스크를 슬립시킵니다.

/* kernel/locking/semaphore.c — down() 구현 */

void down(struct semaphore *sem)
{
    unsigned long flags;

    raw_spin_lock_irqsave(&sem->lock, flags);
    if (likely(sem->count > 0))
        sem->count--;                    /* Fast path: 즉시 획득 */
    else
        __down(sem);                    /* Slow path: 슬립 */
    raw_spin_lock_irqrestore(&sem->lock, flags);
}

/* __down() — slow path */
static noinline void __sched __down(struct semaphore *sem)
{
    __down_common(sem, TASK_UNINTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT);
}

/* __down_common() — 모든 down 변형의 공통 구현 */
static inline int __sched __down_common(
    struct semaphore *sem,
    long state,
    long timeout)
{
    struct semaphore_waiter waiter;

    list_add_tail(&waiter.list, &sem->wait_list); /* FIFO 큐 끝에 추가 */
    waiter.task = current;
    waiter.up = false;

    for (;;) {
        if (signal_pending_state(state, current))
            goto interrupted;
        if (unlikely(timeout <= 0))
            goto timed_out;
        __set_current_state(state);
        raw_spin_unlock_irq(&sem->lock);
        timeout = schedule_timeout(timeout);    /* 슬립! */
        raw_spin_lock_irq(&sem->lock);
        if (waiter.up)                              /* up()이 설정 */
            return 0;
    }

timed_out:
    list_del(&waiter.list);
    return -ETIME;

interrupted:
    list_del(&waiter.list);
    return -EINTR;
}

up() 구현 분석

up()은 대기자가 없으면 count를 증가시키고, 대기자가 있으면 첫 번째 대기자를 깨웁니다. 핵심은 count를 증가시키지 않고 대기자에게 직접 전달한다는 점입니다.

/* kernel/locking/semaphore.c — up() 구현 */

void up(struct semaphore *sem)
{
    unsigned long flags;

    raw_spin_lock_irqsave(&sem->lock, flags);
    if (likely(list_empty(&sem->wait_list)))
        sem->count++;                    /* 대기자 없음: count 증가 */
    else
        __up(sem);                      /* 대기자 있음: 첫 번째 깨움 */
    raw_spin_unlock_irqrestore(&sem->lock, flags);
}

/* __up() — 대기자 웨이크업 */
static noinline void __sched __up(struct semaphore *sem)
{
    struct semaphore_waiter *waiter;

    waiter = list_first_entry(&sem->wait_list,
                              struct semaphore_waiter, list);
    list_del(&waiter->list);         /* 대기 목록에서 제거 */
    waiter->up = true;               /* 깨어날 차례 표시 */
    wake_up_process(waiter->task);   /* 태스크 깨움 */
}

Counting Semaphore 패턴

Counting Semaphore는 count > 1로 초기화하여 동시에 여러 스레드가 공유 리소스에 접근할 수 있게 합니다. 전형적인 사용 사례는 리소스 풀입니다.

/* Counting Semaphore: 동시 접근 수 제한 */

#define MAX_CONNECTIONS  8

static DEFINE_SEMAPHORE(conn_sem, MAX_CONNECTIONS);

static int device_open(struct inode *inode, struct file *filp)
{
    /* 최대 8개 동시 연결 허용 */
    if (down_interruptible(&conn_sem))
        return -ERESTARTSYS;

    /* 연결 설정... count는 0~7 중 하나 */
    return 0;
}

static int device_release(struct inode *inode, struct file *filp)
{
    /* 연결 해제 → 슬롯 반환 */
    up(&conn_sem);
    return 0;
}

Binary Semaphore와 Mutex 비교

count=1인 Binary Semaphore는 표면적으로 mutex와 동일해 보이지만, 근본적인 차이가 있습니다. 이 차이가 mutex 도입의 핵심 동기였습니다.

/* Binary Semaphore: 소유권 없음 — 다른 스레드가 해제 가능 */

static DEFINE_SEMAPHORE(hw_sem, 1);

/* IRQ 핸들러에서 해제 (인터럽트 컨텍스트) */
static irqreturn_t hw_irq_handler(int irq, void *dev)
{
    /* 하드웨어 완료 → semaphore 해제 */
    up(&hw_sem);         /* down()을 호출한 스레드가 아님! */
    return IRQ_HANDLED;
}

/* 프로세스 컨텍스트에서 획득 */
static void hw_submit_and_wait(void)
{
    start_hw_operation();
    down(&hw_sem);        /* IRQ가 up()할 때까지 대기 */
    process_result();
}

/* mutex로는 불가능: */
/* mutex_unlock()을 mutex_lock()을 호출한 스레드가 아닌   */
/* 다른 스레드/컨텍스트에서 호출하면 WARNING + BUG 발생  */

rw_semaphore 구조체(Struct)

struct rw_semaphore는 읽기 병렬성과 쓰기 배타성을 동시에 제공하는 sleeping lock입니다. 커널에서 가장 많이 사용되는 동기화 프리미티브 중 하나로, mmap_lock(이전 mmap_sem)이 대표적인 사용 사례입니다.

/* include/linux/rwsem.h — rw_semaphore 구조체 */

struct rw_semaphore {
    atomic_long_t       count;      /* 상태 인코딩 (비트 필드) */
    atomic_long_t       owner;      /* 현재 라이터 (+ 플래그 비트) */
    struct optimistic_spin_queue osq; /* MCS 기반 spinning 큐 */
    raw_spinlock_t      wait_lock;  /* wait_list 보호 */
    struct list_head    wait_list;  /* 대기 태스크 목록 */
};

rw_semaphore 내부 구현

rw_semaphore의 읽기/쓰기 획득 경로는 각각 fast path, optimistic spin path, slow path의 3단계로 구성됩니다.

읽기 경로: down_read()

/* kernel/locking/rwsem.c — down_read fast path */

static inline int __down_read_trylock(struct rw_semaphore *sem)
{
    long tmp = atomic_long_read(&sem->count);

    while (!(tmp & RWSEM_READ_FAILED_MASK)) {
        /* 라이터 없고, 핸드오프 없으면 → 리더 카운트 증가 */
        if (atomic_long_try_cmpxchg_acquire(
                &sem->count, &tmp,
                tmp + RWSEM_READER_BIAS))
            return 1;  /* 성공 */
    }
    return 0;  /* 실패 → slow path */
}

/* RWSEM_READ_FAILED_MASK:
 *   RWSEM_WRITER_LOCKED | RWSEM_FLAG_WAITERS | RWSEM_FLAG_HANDOFF
 *   → 라이터가 있거나 대기자/핸드오프가 있으면 fast path 실패 */

쓰기 경로: down_write()

/* kernel/locking/rwsem.c — down_write fast path */

static inline int __down_write_trylock(struct rw_semaphore *sem)
{
    long tmp = RWSEM_UNLOCKED_VALUE;  /* 0 */

    /* count가 0(완전 비어있음)일 때만 WRITER_LOCKED 설정 */
    if (atomic_long_try_cmpxchg_acquire(
            &sem->count, &tmp,
            RWSEM_WRITER_LOCKED))
        return 1;  /* 성공 */
    return 0;  /* 실패 → optimistic spin 또는 slow path */
}

rwsem Optimistic Spinning

Optimistic Spinning은 rw_semaphore의 핵심 성능 최적화입니다. 락 소유자가 현재 CPU에서 실행 중이면, 곧 해제할 것으로 "낙관적으로" 기대하고 슬립 대신 spinning합니다.

/* kernel/locking/rwsem.c — rwsem_optimistic_spin() 핵심 루프 */

static bool rwsem_optimistic_spin(struct rw_semaphore *sem)
{
    /* 1. osq_lock: MCS 큐에 진입하여 spinner 정렬 */
    if (!osq_lock(&sem->osq))
        goto done;

    for (;;) {
        struct task_struct *owner;

        /* 2. owner 확인: CPU에서 실행 중인지 체크 */
        owner = rwsem_owner_flags(sem, &flags);
        if (!(flags & RWSEM_NONSPINNABLE)) {
            if (rwsem_try_write_lock_unqueued(sem))
                break;  /* 성공! */
            if (owner && !owner_on_cpu(owner))
                goto done;  /* owner 비실행 → 포기 */
        }

        /* 3. 선점 요청 확인 */
        if (need_resched())
            goto done;  /* 선점 필요 → 포기 */

        cpu_relax();  /* PAUSE/WFE 힌트 */
    }
    osq_unlock(&sem->osq);
    return true;  /* 획득 성공 */

done:
    osq_unlock(&sem->osq);
    return false;  /* slow path로 이동 */
}

rwsem HANDOFF 메커니즘

HANDOFF는 writer starvation을 방지하는 핵심 메커니즘입니다. 대기 중인 첫 번째 writer가 일정 시간 이상 기다리면 HANDOFF 플래그를 설정하여, 새로운 리더/라이터의 fast path 획득을 차단합니다.

/* HANDOFF 동작 시퀀스 */

/* 1. Writer W1이 wait_list의 첫 번째로 대기 중 */
/* 2. 새 리더들이 계속 fast path로 진입 → W1 굶주림 */
/* 3. W1이 한 번 깨어났다가 다시 슬립하면: HANDOFF 설정 */

count |= RWSEM_FLAG_HANDOFF;  /* bit 61 설정 */

/* 4. 이후 새 리더의 fast path 시도: */
/*    RWSEM_READ_FAILED_MASK에 HANDOFF 포함 → CAS 실패 */

/* 5. 기존 리더들이 모두 해제되면: */
/*    up_read()가 W1을 깨움 */
/*    W1이 HANDOFF 비트와 함께 WRITER_LOCKED 설정 */

/* 6. W1 획득 후: HANDOFF 비트 클리어 */

rw_semaphore API 레퍼런스

/* downgrade_write() 패턴: 쓰기 후 읽기 계속 */

down_write(&inode->i_rwsem);
/* 메타데이터 수정 (배타적) */
update_metadata(inode);

/* 수정 완료 후 읽기 모드로 전환 (다른 리더 허용) */
downgrade_write(&inode->i_rwsem);

/* 데이터 읽기 (다른 리더와 병렬) */
read_data(inode);
up_read(&inode->i_rwsem);

레거시 semaphore에서 mutex 마이그레이션

Linux 2.6.16(2006년)에서 Ingo Molnar가 struct mutex를 도입한 이후, 커널 전체에서 대규모 semaphore 교체가 진행되었습니다. 이것은 Linux 커널 역사에서 가장 큰 규모의 동기화 프리미티브 마이그레이션 중 하나입니다.

마이그레이션 체크리스트

/* semaphore → mutex 변환 가능 조건 */

/* 1. count == 1 (Binary만) */
DEFINE_SEMAPHORE(my_sem, 1);        /* → DEFINE_MUTEX(my_mutex); */

/* 2. down()과 up()이 같은 컨텍스트 */
down(&my_sem);                     /* → mutex_lock(&my_mutex); */
/* 임계 영역 */
up(&my_sem);                       /* → mutex_unlock(&my_mutex); */

/* 3. 인터럽트 컨텍스트에서 up()하지 않음 */

/* 변환 불가능한 경우: */
/* - count > 1 (Counting Semaphore) */
/* - 다른 스레드/컨텍스트에서 up() */
/* - 인터럽트 핸들러에서 up() */

리소스 풀 관리 패턴

Counting Semaphore의 가장 실용적인 응용은 한정된 리소스 풀의 동시 접근 제어(Access Control)입니다.

/* 실전 패턴: DMA 채널 풀 관리 */

#define NUM_DMA_CHANNELS  4

struct dma_pool {
    struct semaphore    avail;          /* 사용 가능한 채널 수 */
    spinlock_t          pool_lock;      /* 비트맵 보호 */
    unsigned long       channel_map;    /* 채널 사용 비트맵 */
    struct dma_chan     *channels[NUM_DMA_CHANNELS];
};

static struct dma_pool pool;

static void dma_pool_init(void)
{
    sema_init(&pool.avail, NUM_DMA_CHANNELS);
    spin_lock_init(&pool.pool_lock);
    pool.channel_map = 0;
}

static struct dma_chan *dma_channel_get(void)
{
    int ch;

    /* count > 0이면 즉시 통과, 아니면 슬립 */
    if (down_interruptible(&pool.avail))
        return ERR_PTR(-ERESTARTSYS);

    spin_lock(&pool.pool_lock);
    ch = find_first_zero_bit(&pool.channel_map, NUM_DMA_CHANNELS);
    __set_bit(ch, &pool.channel_map);
    spin_unlock(&pool.pool_lock);

    return pool.channels[ch];
}

static void dma_channel_put(struct dma_chan *chan)
{
    int ch = chan_to_index(chan);

    spin_lock(&pool.pool_lock);
    __clear_bit(ch, &pool.channel_map);
    spin_unlock(&pool.pool_lock);

    up(&pool.avail);  /* 대기자 있으면 깨움 */
}

PREEMPT_RT 영향

PREEMPT_RT 커널에서 semaphore와 rw_semaphore의 동작이 크게 달라집니다. 이 차이를 이해하는 것은 RT 시스템 개발에 필수적입니다.

실전 사용 패턴

현재 커널에서 semaphore가 사용되는 실제 사례와 올바른 사용 패턴을 분석합니다.

패턴 1: Completion 대용 (count=0 초기화)

/* count=0으로 초기화 → 이벤트 대기 패턴 */
/* 주의: 새 코드에서는 struct completion을 사용하세요 */

static DEFINE_SEMAPHORE(firmware_loaded, 0);

/* 로더 스레드 */
static int firmware_loader(void *data)
{
    load_firmware();
    up(&firmware_loaded);     /* 완료 신호 */
    return 0;
}

/* 사용자 스레드 */
static void use_firmware(void)
{
    down(&firmware_loaded);   /* 로딩 완료까지 대기 */
    access_firmware();
}

패턴 2: Producer-Consumer (이중 세마포어)

/* 이중 세마포어: bounded buffer */

#define BUF_SIZE  16

static DEFINE_SEMAPHORE(empty_slots, BUF_SIZE);  /* 빈 슬롯 수 */
static DEFINE_SEMAPHORE(full_slots, 0);          /* 채워진 슬롯 수 */
static DEFINE_MUTEX(buf_mutex);               /* 버퍼 접근 보호 */

static void producer(void)
{
    down(&empty_slots);      /* 빈 슬롯 확보 */
    mutex_lock(&buf_mutex);
    enqueue_item();
    mutex_unlock(&buf_mutex);
    up(&full_slots);         /* 채워진 슬롯 알림 */
}

static void consumer(void)
{
    down(&full_slots);       /* 채워진 슬롯 대기 */
    mutex_lock(&buf_mutex);
    dequeue_item();
    mutex_unlock(&buf_mutex);
    up(&empty_slots);        /* 빈 슬롯 반환 */
}

커널 내 실제 사용 사례

안티패턴

semaphore 사용에서 흔히 발생하는 실수와 안티패턴을 분석합니다.

안티패턴 1: Binary Semaphore를 mutex 대신 사용

/* BAD: mutex가 적합한 곳에 semaphore 사용 */
static DEFINE_SEMAPHORE(my_sem, 1);

static void critical_section(void)
{
    down(&my_sem);
    /* 같은 스레드에서 down/up → mutex 사용해야 함 */
    do_work();
    up(&my_sem);
}

/* GOOD: mutex 사용 */
static DEFINE_MUTEX(my_mutex);

static void critical_section(void)
{
    mutex_lock(&my_mutex);
    do_work();
    mutex_unlock(&my_mutex);
    /* lockdep 검증, optimistic spinning, PI 지원 */
}

안티패턴 2: down_trylock 반환값 오류

/* BAD: mutex_trylock과 혼동 */
if (down_trylock(&sem)) {    /* 1 = 실패인데, 성공으로 착각! */
    do_work();                /* 락 없이 실행 → 레이스! */
    up(&sem);                 /* 이중 up → count 오염 */
}

/* GOOD: 반환값 정확히 확인 */
if (down_trylock(&sem) == 0) {   /* 0 = 성공 */
    do_work();
    up(&sem);
}

안티패턴 3: 인터럽트 컨텍스트에서 down()

/* BAD: 인터럽트 핸들러에서 down() → 슬립 불가! */
static irqreturn_t bad_handler(int irq, void *dev)
{
    down(&sem);     /* BUG: 인터럽트에서 sleep → 시스템 행 */
    do_work();
    up(&sem);
    return IRQ_HANDLED;
}

/* GOOD: down_trylock 또는 spinlock 사용 */
static irqreturn_t good_handler(int irq, void *dev)
{
    if (down_trylock(&sem) == 0) {
        do_work();
        up(&sem);
    } else {
        schedule_work(&deferred_work);  /* 워커로 위임 */
    }
    return IRQ_HANDLED;
}

안티패턴 4: up() 누락 에러 경로

/* BAD: 에러 경로에서 up() 누락 → 영구 잠금 */
static int bad_function(void)
{
    down(&sem);
    if (allocate_resource() < 0)
        return -ENOMEM;  /* up() 호출 안 함! → 데드락 */
    do_work();
    up(&sem);
    return 0;
}

/* GOOD: goto cleanup 패턴 */
static int good_function(void)
{
    int ret;

    down(&sem);
    if (allocate_resource() < 0) {
        ret = -ENOMEM;
        goto out_unlock;
    }
    do_work();
    ret = 0;
out_unlock:
    up(&sem);
    return ret;
}

디버깅(Debugging)

semaphore 관련 문제를 진단하는 도구와 기법을 정리합니다.

Hung Task 탐지

/* CONFIG_DETECT_HUNG_TASK=y */
/* TASK_UNINTERRUPTIBLE 상태로 120초 이상 머무르면 경고 */

INFO: task kworker/0:1:42 blocked for more than 120 seconds.
      Not tainted 6.8.0 #1
"echo 0 > /proc/sys/kernel/hung_task_timeout_secs" disables this message.
task:kworker/0:1     state:D stack:13456 pid:42
Call Trace:
 <TASK>
 __schedule+0x3e8/0x1150
 schedule+0x5e/0xd0
 schedule_timeout+0x118/0x150
 __down+0x5a/0x80            /* ← semaphore down에서 blocked */
 down+0x43/0x50
 my_driver_write+0x2b/0x90
 vfs_write+0x1a5/0x6d0

lockdep으로 교착 탐지

/* semaphore도 lockdep 기본 체크 적용 (제한적) */

/* CONFIG_PROVE_LOCKING=y */
/* 같은 semaphore를 두 번 down() → 자기 교착 탐지 */

============================================
WARNING: possible recursive locking detected
--------------------------------------------
process/1234 is trying to acquire lock:
 (&my_sem){+.+.}-{3:3}, at: my_function+0x20/0x60
but task is already holding lock:
 (&my_sem){+.+.}-{3:3}, at: my_function+0x20/0x60

SysRq로 blocked 태스크 확인

/* Alt+SysRq+W: TASK_UNINTERRUPTIBLE 태스크 표시 */
echo w > /proc/sysrq-trigger

/* 출력 예시 */
SysRq : Show Blocked State
  task                PC stack   pid father
kworker/0:1     D 0000000000000000 13456    42      2
 Call Trace:
  schedule_timeout+0x118/0x150
  __down+0x5a/0x80
  down+0x43/0x50

/* /proc//wchan 으로 개별 확인 */
cat /proc/42/wchan
/* 출력: __down */

ftrace로 semaphore 추적

# function_graph로 down/up 호출 추적
echo function_graph > /sys/kernel/debug/tracing/current_tracer
echo down > /sys/kernel/debug/tracing/set_ftrace_filter
echo up >> /sys/kernel/debug/tracing/set_ftrace_filter
echo __down >> /sys/kernel/debug/tracing/set_ftrace_filter
echo __up >> /sys/kernel/debug/tracing/set_ftrace_filter
echo 1 > /sys/kernel/debug/tracing/tracing_on

# 추적 결과 확인
cat /sys/kernel/debug/tracing/trace

커널 설정

# /proc/lock_stat 출력 예시 (CONFIG_LOCK_STAT=y)

lock_stat version 0.4
---------------------------------------------------------------------------
                              class name    con-bounces    contentions ...
---------------------------------------------------------------------------
                         &sb->s_umount:         1234           5678 ...
                          &mm->mmap_lock:        9012          34567 ...
                        &inode->i_rwsem:          456           7890 ...

down() 소스 코드 심층 분석

앞서 down() 구현 분석에서 전체 흐름을 살펴보았습니다. 이 섹션에서는 __down_common()의 각 코드 라인을 해부하여, waiter list 관리, schedule_timeout 상호작용, 시그널/타임아웃 처리의 미묘한 동기화 문제를 분석합니다.

semaphore_waiter 구조체

/* include/linux/semaphore.h */

struct semaphore_waiter {
    struct list_head list;   /* sem->wait_list에 연결 */
    struct task_struct *task; /* 슬립 중인 태스크 */
    bool up;                   /* up()이 이 waiter를 깨웠는지 */
};

/* 핵심 설계: up 필드가 있는 이유
 * schedule_timeout()에서 깨어난 것이 up()에 의한 것인지,
 * 시그널/타임아웃에 의한 spurious wakeup인지 구분해야 합니다.
 * up()은 waiter.up = true로 설정한 후 wake_up_process()를 호출하므로
 * 깨어난 태스크는 waiter.up 값으로 정당한 wakeup인지 확인합니다. */

__down_common() 라인별 분석

/* kernel/locking/semaphore.c — __down_common() 완전 분석 */

static inline int __sched __down_common(
    struct semaphore *sem,
    long state,       /* TASK_UNINTERRUPTIBLE or TASK_INTERRUPTIBLE or TASK_KILLABLE */
    long timeout)     /* MAX_SCHEDULE_TIMEOUT or jiffies 값 */
{
    struct semaphore_waiter waiter;

    /* 1단계: waiter를 wait_list 끝에 추가 (FIFO 순서 보장)
     * raw_spinlock을 이미 보유하고 있으므로 list 조작은 안전합니다 */
    list_add_tail(&waiter.list, &sem->wait_list);
    waiter.task = current;
    waiter.up = false;

    for (;;) {
        /* 2단계: 시그널 체크 (INTERRUPTIBLE/KILLABLE 경우만 유효)
         * TASK_UNINTERRUPTIBLE이면 signal_pending_state()는 항상 false */
        if (signal_pending_state(state, current))
            goto interrupted;

        /* 3단계: 타임아웃 체크
         * MAX_SCHEDULE_TIMEOUT은 사실상 무한대이므로 여기 걸리지 않음
         * down_timeout()에서만 실질적으로 활성화됩니다 */
        if (unlikely(timeout <= 0))
            goto timed_out;

        /* 4단계: 태스크 상태 설정
         * __set_current_state()는 배리어 없는 버전 — 이미 스핀락 보호 하에 있으므로
         * set_current_state()의 smp_store_mb()가 불필요합니다 */
        __set_current_state(state);

        /* 5단계: 스핀락 해제 후 슬립
         * raw_spin_unlock_irq는 인터럽트를 복원합니다
         * 이 시점에서 up()이 실행될 수 있습니다 (레이스 윈도우) */
        raw_spin_unlock_irq(&sem->lock);

        /* schedule_timeout: 실제 슬립!
         * 반환 값은 남은 timeout jiffies (또는 0) */
        timeout = schedule_timeout(timeout);

        /* 6단계: 깨어남 → 스핀락 재획득
         * 이 시점에서 waiter.up이 true일 수도 있고 아닐 수도 있음 */
        raw_spin_lock_irq(&sem->lock);

        /* 7단계: 정당한 wakeup 확인
         * up()이 waiter.up = true를 설정했으면 세마포어 획득 성공 */
        if (waiter.up)
            return 0;
    }

timed_out:
    /* 타임아웃: wait_list에서 제거하고 -ETIME 반환
     * 아직 스핀락을 보유하고 있으므로 list_del은 안전 */
    list_del(&waiter.list);
    return -ETIME;

interrupted:
    /* 시그널 수신: wait_list에서 제거하고 -EINTR 반환
     * down_interruptible(), down_killable()에서만 도달 */
    list_del(&waiter.list);
    return -EINTR;
}

unlock-schedule 레이스 윈도우

raw_spin_unlock_irq()와 schedule_timeout() 사이에 레이스 윈도우가 존재합니다. 이 구간에서 up()이 실행되면 어떻게 되는지 분석합니다.

/* 레이스 시나리오:
 *
 * CPU 0 (down)                    CPU 1 (up)
 * ─────────────────               ─────────────────
 * __set_current_state(UNINTERRUPTIBLE)
 * raw_spin_unlock_irq()
 *                                 raw_spin_lock_irq()
 *                                 waiter.up = true
 *                                 wake_up_process(task)
 *                                 raw_spin_unlock_irq()
 * schedule_timeout()
 *   → try_to_wake_up()가 이미 실행됨
 *   → task 상태가 RUNNING으로 변경됨
 *   → schedule()은 즉시 반환
 * raw_spin_lock_irq()
 * waiter.up == true → return 0
 *
 * 안전한 이유:
 * __set_current_state()가 spin_unlock 이전에 호출되므로
 * up()의 wake_up_process()가 태스크를 정확히 깨울 수 있습니다.
 * schedule()이 호출되더라도 이미 RUNNING 상태이므로 즉시 반환합니다. */

down 변형별 차이

rwsem 소스 코드 심층 분석

rw_semaphore의 핵심은 64비트 count 필드의 비트 인코딩과, 이를 기반으로 한 rwsem_down_read_slowpath()/rwsem_down_write_slowpath()의 정교한 상태 머신입니다.

count 비트 필드 상세 인코딩

/* kernel/locking/rwsem.c — count 비트 레이아웃 (64비트) */

/*
 * 비트 63                                            비트 0
 * ┌─────────────────────────────────────────────────────────┐
 * │ READER_COUNT (비트 8~63)  │ FLAGS (비트 1~7) │ WRITER (비트 0) │
 * └─────────────────────────────────────────────────────────┘
 *
 * RWSEM_WRITER_LOCKED  = 1 << 0        (비트 0)
 * RWSEM_FLAG_WAITERS   = 1 << 1        (비트 1)
 * RWSEM_FLAG_HANDOFF   = 1 << 2        (비트 2)
 * RWSEM_READER_BIAS    = 1 << 8        (비트 8~63 = 리더 수)
 */

#define RWSEM_WRITER_LOCKED  (1UL << 0)
#define RWSEM_FLAG_WAITERS   (1UL << 1)
#define RWSEM_FLAG_HANDOFF   (1UL << 2)
#define RWSEM_READER_BIAS    (1UL << 8)

/* 리더 수 추출 */
#define RWSEM_READER_SHIFT   8
#define rwsem_reader_count(c) ((c) >> RWSEM_READER_SHIFT)

/* Fast path 실패 조건 마스크:
 * 라이터 보유 중이거나, 대기자 있거나, 핸드오프 진행 중이면 fast path 불가 */
#define RWSEM_READ_FAILED_MASK  \
    (RWSEM_WRITER_LOCKED | RWSEM_FLAG_WAITERS | RWSEM_FLAG_HANDOFF)

rwsem_down_read_slowpath() 분석

/* kernel/locking/rwsem.c — 읽기 slow path 핵심 */

static struct rw_semaphore *
rwsem_down_read_slowpath(struct rw_semaphore *sem, long count, unsigned int state)
{
    struct rwsem_waiter waiter;
    DEFINE_WAKE_Q(wake_q);

    /* 1. 라이터가 없고 핸드오프가 없으면 리더 바이어스 시도
     * 이미 READER_BIAS를 더한 상태(fast path 시도 흔적)이므로
     * 조건이 맞으면 그대로 리더로 진입 가능 */
    if (!(count & (RWSEM_WRITER_LOCKED | RWSEM_FLAG_HANDOFF))) {
        rwsem_set_reader_owned(sem);
        lockevent_inc(rwsem_rlock_fast);
        return sem;  /* 리더 직접 획득! */
    }

    /* 2. fast path 실패 → READER_BIAS 복원 (나중에 다시 설정) */
    atomic_long_add(-RWSEM_READER_BIAS, &sem->count);

    /* 3. waiter 구성 및 wait_list 추가 */
    waiter.task = current;
    waiter.type = RWSEM_WAITING_FOR_READ;
    waiter.timeout = jiffies + RWSEM_WAIT_TIMEOUT;
    waiter.handoff_set = false;

    raw_spin_lock_irq(&sem->wait_lock);
    list_add_tail(&waiter.list, &sem->wait_list);

    /* 4. WAITERS 플래그 설정 */
    rwsem_add_waiter(sem, &waiter);

    /* 5. 슬립 루프 */
    for (;;) {
        set_current_state(state);
        if (!smp_load_acquire(&waiter.task))
            break;  /* wakeup 수신! task가 NULL로 설정됨 */
        raw_spin_unlock_irq(&sem->wait_lock);
        schedule_preempt_disabled();
        raw_spin_lock_irq(&sem->wait_lock);
    }
    __set_current_state(TASK_RUNNING);
    raw_spin_unlock_irq(&sem->wait_lock);
    lockevent_inc(rwsem_rlock);
    return sem;
}

rwsem_down_write_slowpath() 핵심

/* kernel/locking/rwsem.c — 쓰기 slow path 핵심 흐름 */

static struct rw_semaphore *
rwsem_down_write_slowpath(struct rw_semaphore *sem, int state)
{
    struct rwsem_waiter waiter;

    /* 1. Optimistic Spinning 시도 (CONFIG_RWSEM_SPIN_ON_OWNER)
     * owner가 CPU에서 실행 중이면 spinning으로 빠르게 획득 */
    if (rwsem_can_spin_on_owner(sem))
        if (rwsem_optimistic_spin(sem))
            return sem;  /* spinning 성공! */

    /* 2. wait_list에 추가 */
    waiter.task = current;
    waiter.type = RWSEM_WAITING_FOR_WRITE;
    waiter.timeout = jiffies + RWSEM_WAIT_TIMEOUT;
    waiter.handoff_set = false;

    raw_spin_lock_irq(&sem->wait_lock);
    rwsem_add_waiter(sem, &waiter);

    /* 3. 슬립 루프 — HANDOFF 처리 포함 */
    for (;;) {
        if (rwsem_try_write_lock(sem, &waiter)) {
            /* HANDOFF가 설정된 상태에서 첫 번째 waiter만 획득 가능 */
            break;
        }

        set_current_state(state);
        raw_spin_unlock_irq(&sem->wait_lock);

        /* HANDOFF 설정: 대기 시간이 RWSEM_WAIT_TIMEOUT 초과 시 */
        if (!waiter.handoff_set &&
            time_after(jiffies, waiter.timeout)) {
            atomic_long_or(RWSEM_FLAG_HANDOFF, &sem->count);
            waiter.handoff_set = true;
        }

        schedule_preempt_disabled();
        raw_spin_lock_irq(&sem->wait_lock);
    }
    __set_current_state(TASK_RUNNING);
    raw_spin_unlock_irq(&sem->wait_lock);
    return sem;
}

percpu_rw_semaphore 심층 분석

percpu_rw_semaphore는 읽기 경로를 극단적으로 최적화한 rw_semaphore 변형입니다. 각 CPU마다 독립적인 리더 카운터를 유지하여 읽기 경로에서 캐시 라인(Cache Line) 바운싱이 전혀 없습니다. 대신 쓰기 경로는 매우 비용이 큽니다.

구조체 분석

/* include/linux/percpu-rwsem.h */

struct percpu_rw_semaphore {
    struct rcu_sync rss;         /* RCU 동기화 상태 추적 */
    unsigned int __percpu *read_count;  /* per-CPU 리더 카운터 */
    struct rcuwait writer;      /* 라이터 대기 */
    wait_queue_head_t waiters;  /* 리더 대기 큐 (slow path) */
    atomic_t block;              /* 리더 차단 플래그 */
};

읽기 Fast Path: __percpu_down_read()

/* kernel/locking/percpu-rwsem.c — 읽기 fast path */

bool __percpu_down_read(struct percpu_rw_semaphore *sem, bool try)
{
    /* 1. RCU read-side critical section 진입
     * preempt_disable()과 동일 — 매우 가벼움 */
    rcu_read_lock();

    /* 2. rcu_sync가 idle 상태면 → 라이터 없음 → fast path
     * __rcu_sync_is_idle()는 단순 변수 읽기 (atomic 불필요) */
    if (likely(__rcu_sync_is_idle(&sem->rss))) {
        /* 3. per-CPU 카운터 증가
         * this_cpu_inc는 로컬 CPU 변수 조작이므로 atomic 불필요
         * 캐시 라인 바운싱 없음! */
        this_cpu_inc(*sem->read_count);
        rcu_read_unlock();

        /* 4. 카운터 증가 후 block 플래그 재확인
         * 라이터가 카운터 증가와 동시에 진입했을 수 있으므로 */
        if (likely(!atomic_read(&sem->block)))
            return true;  /* Fast path 성공! */

        /* 라이터가 진입 중 → 카운터 복원 후 slow path */
        __percpu_up_read(sem);
        return false;  /* → slow path */
    }

    rcu_read_unlock();
    return false;  /* 라이터 활동 중 → slow path */
}

쓰기 경로: percpu_down_write()

/* kernel/locking/percpu-rwsem.c — 쓰기 경로 (매우 비용이 큼) */

void percpu_down_write(struct percpu_rw_semaphore *sem)
{
    /* 1단계: rcu_sync를 "enter" 상태로 전환
     * 이후 새로운 리더는 fast path를 사용할 수 없음
     * synchronize_rcu()를 내부적으로 호출 → 매우 느림 (수 ms) */
    rcu_sync_enter(&sem->rss);

    /* 2단계: block 플래그 설정 → 새 리더 진입 차단 */
    atomic_set(&sem->block, 1);
    smp_mb();  /* block 설정이 모든 CPU에서 보이도록 */

    /* 3단계: 모든 CPU의 read_count를 합산하여 0이 될 때까지 대기
     * 기존 리더들이 모두 나갈 때까지 기다림 */
    wait_event(sem->waiters,
        readers_active_check(sem) == 0);

    /* 4단계: 모든 리더가 나감 → 라이터 독점 진입 */
}

대표 사용처

아키텍처별 구현 차이

semaphore의 down()/up()은 raw_spinlock으로 보호되므로, 성능 차이는 결국 아키텍처별 atomic 연산 구현에 달려 있습니다. rw_semaphore의 fast path는 atomic_long_try_cmpxchg_acquire()를 사용하므로 아키텍처별 차이가 더 두드러집니다.

x86: LOCK CMPXCHG

/* arch/x86 — atomic_long_try_cmpxchg_acquire() 하위 구현 */

/* x86는 LOCK prefix로 bus lock 또는 cache lock을 수행합니다
 * LOCK CMPXCHG는 implicit full barrier — acquire/release 구분이 불필요
 *
 * 특징:
 * - LOCK prefix는 #LOCK 시그널로 캐시 라인 독점 보장
 * - 최신 CPU는 cache lock (캐시 라인이 L1에 있으면 bus lock 불필요)
 * - 비용: ~20 사이클 (비경합), ~100+ 사이클 (경합) */

static __always_inline bool
arch_try_cmpxchg(atomic_t *v, int *old, int new)
{
    return try_cmpxchg(&v->counter, old, new);
    /* → LOCK CMPXCHG [mem], new
     *    ZF=1이면 교환 성공 (old == *mem → *mem = new)
     *    ZF=0이면 실패 (*old = *mem 현재 값으로 갱신) */
}

ARM64: LDXR/STXR (LL/SC)

/* arch/arm64 — atomic_long_try_cmpxchg_acquire() 하위 구현 */

/* ARM64는 LL/SC (Load-Link/Store-Conditional) 패턴을 사용합니다
 * LDAXR: Load-Acquire Exclusive Register (acquire 의미론)
 * STXR:  Store Exclusive Register (조건부 저장)
 *
 * ARMv8.1부터 CAS 명령어 추가 (LSE: Large System Extensions)
 * CASAL: Compare-And-Swap with Acquire-reLease
 *
 * 차이점:
 * - acquire만 필요하면 LDAXR + STXR (release 없음)
 * - full barrier 필요하면 LDAXR + STLXR
 * - LSE CAS는 단일 명령어로 더 효율적 (대형 시스템) */

/* LL/SC 방식 (ARMv8.0) */
1: ldaxr   x0, [x1]        // Load-Acquire Exclusive
   cmp     x0, x2          // old 값과 비교
   b.ne    2f              // 다르면 실패
   stxr    w3, x4, [x1]    // Store Exclusive (조건부)
   cbnz    w3, 1b          // 실패하면 재시도
2:

/* LSE CAS 방식 (ARMv8.1+) */
   casa    x0, x4, [x1]    // Compare-And-Swap Acquire

RISC-V: AMO / LR/SC

/* arch/riscv — atomic 연산 구현 */

/* RISC-V는 두 가지 방식을 제공합니다:
 * 1. LR/SC (Load-Reserved/Store-Conditional) — ARM의 LL/SC와 유사
 * 2. AMO (Atomic Memory Operations) — amoswap, amoadd 등
 *
 * acquire/release 의미론:
 * - .aq 접미사: acquire barrier
 * - .rl 접미사: release barrier
 * - .aqrl: full barrier */

/* LR/SC 방식 */
1: lr.d.aq  a0, (a1)       // Load-Reserved with Acquire
   bne      a0, a2, 2f    // 비교 실패 → 분기
   sc.d     a3, a4, (a1)   // Store-Conditional
   bnez     a3, 1b        // SC 실패 → 재시도
2:

/* AMO 방식 (단순 덧셈 — rwsem READER_BIAS 추가에 사용) */
   amoadd.d.aq  a0, a2, (a1)  // *a1 += a2, old value → a0 (acquire)

아키텍처 비교 표

벤치마크: semaphore 계열 성능 비교

semaphore, mutex, rw_semaphore, percpu_rw_semaphore의 성능을 비경합(uncontended)과 경합(contended) 조건에서 비교합니다. 테스트는 커널 모듈(Kernel Module)에서 수행하며, ktime_get_ns()로 측정합니다.

벤치마크 커널 모듈

/* 벤치마크 커널 모듈 핵심 부분 */

static void bench_semaphore(void)
{
    struct semaphore sem;
    u64 start, elapsed;
    int i;

    sema_init(&sem, 1);
    start = ktime_get_ns();

    for (i = 0; i < ITERATIONS; i++) {
        down(&sem);
        up(&sem);
    }

    elapsed = ktime_get_ns() - start;
    pr_info("semaphore: %llu ns/op\n", elapsed / ITERATIONS);
}

static void bench_mutex(void)
{
    DEFINE_MUTEX(mtx);
    u64 start, elapsed;
    int i;

    start = ktime_get_ns();

    for (i = 0; i < ITERATIONS; i++) {
        mutex_lock(&mtx);
        mutex_unlock(&mtx);
    }

    elapsed = ktime_get_ns() - start;
    pr_info("mutex: %llu ns/op\n", elapsed / ITERATIONS);
}

비경합(Uncontended) 성능

경합(Contended) 성능 — 8 CPU 동시 접근

선택 가이드

메모리 순서와 배리어

semaphore와 rw_semaphore의 정확성은 메모리 순서 보장(Ordering)에 달려 있습니다. down()은 ACQUIRE 의미론, up()은 RELEASE 의미론을 구현해야 합니다. 이 섹션에서는 각 프리미티브가 어떻게 메모리 순서를 보장하는지 분석합니다.

ACQUIRE/RELEASE 의미론

/* 메모리 순서 규칙:
 *
 * ACQUIRE (down/lock):
 *   임계 영역 내의 메모리 접근이 lock 획득 이전으로 재배치되지 않음
 *   → lock 이후의 load/store가 lock 이전으로 올라가지 않음
 *
 * RELEASE (up/unlock):
 *   임계 영역 내의 메모리 접근이 lock 해제 이후로 재배치되지 않음
 *   → lock 이전의 load/store가 unlock 이후로 내려가지 않음
 *
 * 조합 효과:
 *   CPU 0: down()  →  critical section  →  up()
 *           ACQUIRE    (순서 보장)          RELEASE
 *   CPU 1:           down()  →  critical section  →  up()
 *                    ACQUIRE    (CPU 0의 변경이 보임)
 */

semaphore의 배리어 분석

/* semaphore의 ACQUIRE/RELEASE는 raw_spinlock이 제공합니다 */

void down(struct semaphore *sem)
{
    raw_spin_lock_irqsave(&sem->lock, flags);
    /* ↑ ACQUIRE barrier 포함 (spin_lock은 ACQUIRE)
     * x86: LOCK 명령의 implicit barrier
     * ARM64: LDAXR의 acquire 의미론 */

    if (sem->count > 0)
        sem->count--;

    raw_spin_unlock_irqrestore(&sem->lock, flags);
    /* ↑ RELEASE barrier 포함 (spin_unlock은 RELEASE)
     * x86: MOV의 store buffer flush (TSO 보장)
     * ARM64: STLXR의 release 의미론 */
}

/* 문제: spin_unlock이 RELEASE를 제공하지만,
 * 이는 semaphore의 RELEASE가 아닌 spinlock의 RELEASE입니다.
 * down()에서 spin_lock이 ACQUIRE를 제공하므로
 * 전체적으로 semaphore의 ACQUIRE는 보장됩니다.
 *
 * 그러나 이 설계는 불필요한 spinlock 오버헤드를 수반합니다.
 * mutex는 atomic_long_try_cmpxchg_acquire()만으로
 * ACQUIRE를 구현하여 spinlock이 필요 없습니다. */

rw_semaphore의 배리어 분석

/* rw_semaphore fast path의 메모리 순서 */

/* 읽기 ACQUIRE:
 * atomic_long_try_cmpxchg_acquire() — 이름에 _acquire가 있음
 * → CAS 성공 시 ACQUIRE barrier 보장
 * → 임계 영역의 읽기가 lock 이전으로 재배치되지 않음 */
if (atomic_long_try_cmpxchg_acquire(
        &sem->count, &tmp,
        tmp + RWSEM_READER_BIAS))
    return 1;

/* 읽기 RELEASE (up_read):
 * atomic_long_add_return_release() — _release 접미사
 * → READER_BIAS를 빼면서 RELEASE barrier 보장 */
tmp = atomic_long_add_return_release(
        -RWSEM_READER_BIAS, &sem->count);

/* 쓰기 ACQUIRE/RELEASE도 동일한 패턴:
 * down_write: _acquire 접미사 CAS
 * up_write:   _release 접미사 atomic 연산 */

smp_mb()가 필요한 경우

/* rwsem에서 명시적 smp_mb()가 필요한 경우:
 * HANDOFF 플래그 설정 시, 다른 CPU가 즉시 볼 수 있어야 합니다 */

atomic_long_or(RWSEM_FLAG_HANDOFF, &sem->count);
/* atomic_long_or는 relaxed 의미론일 수 있음 (아키텍처 의존)
 * 따라서 필요 시 별도의 smp_mb()가 뒤따릅니다 */

/* percpu_rw_semaphore에서도:
 * block 플래그 설정 후 명시적 smp_mb()로
 * 모든 CPU에서 즉시 보이도록 보장 */
atomic_set(&sem->block, 1);
smp_mb();  /* 필수! — block 설정이 read_count 읽기보다 먼저 보여야 */

서브시스템: mmap_lock (rw_semaphore)

mmap_lock은 리눅스 커널에서 가장 경합이 심한 rw_semaphore 중 하나입니다. 프로세스의 가상 메모리(Virtual Memory) 영역(VMA)을 보호하며, 페이지 폴트(Page Fault), mmap(), munmap(), /proc/pid/maps 읽기 등 거의 모든 메모리 연산에서 사용됩니다.

mmap_sem에서 mmap_lock으로의 전환

/* mm_struct에서의 mmap_lock 선언 변천사 */

/* v2.6 ~ v5.7: mmap_sem (struct rw_semaphore) */
struct mm_struct {
    struct rw_semaphore mmap_sem;  /* 직접 접근 */
};

/* v5.8+: mmap_lock (래퍼 함수 도입)
 * Michel Lespinasse의 패치 시리즈 (2020)
 * 목적: 향후 lock splitting/replacing을 용이하게 하기 위한 추상화 */
struct mm_struct {
    struct rw_semaphore mmap_lock;  /* 이름 변경 */
};

/* 래퍼 함수 (include/linux/mmap_lock.h) */
static inline void mmap_read_lock(struct mm_struct *mm)
{
    down_read(&mm->mmap_lock);
}
static inline void mmap_write_lock(struct mm_struct *mm)
{
    down_write(&mm->mmap_lock);
}
static inline bool mmap_read_trylock(struct mm_struct *mm)
{
    return down_read_trylock(&mm->mmap_lock);
}

mmap_lock 경합 문제

per-VMA lock (v6.4+)

/* v6.4+: per-VMA lock으로 mmap_lock 경합 완화
 * Suren Baghdasaryan의 패치 시리즈
 *
 * 핵심 아이디어: 페이지 폴트 시 mmap_lock read 대신
 * 해당 VMA의 per-VMA lock만 획득하여 병렬성 극대화 */

struct vm_area_struct {
    struct rw_semaphore lock;    /* per-VMA lock (v6.4+) */
    /* ... */
};

/* lock_mm_and_find_vma() — per-VMA lock 획득 흐름 */
struct vm_area_struct *
lock_mm_and_find_vma(struct mm_struct *mm,
                     unsigned long addr,
                     struct pt_regs *regs)
{
    struct vm_area_struct *vma;

    /* 1. per-VMA lock 먼저 시도 (빠른 경로) */
    if (!mmap_read_trylock(mm)) {
        /* mmap_lock 없이 VMA 검색 (RCU 보호) */
        vma = find_vma(mm, addr);
        if (vma && vma_start_read(vma))
            return vma;  /* per-VMA lock 성공! */
    }

    /* 2. 실패 시 fallback: mmap_lock read */
    mmap_read_lock(mm);
    vma = find_vma(mm, addr);
    return vma;
}

서브시스템: TTY 세마포어

TTY 서브시스템은 Linux 커널에서 레거시 semaphore가 아직 남아있는 대표적인 영역입니다. Line Discipline(ldisc) 관리에서 소유권 없는 동기화가 필요하기 때문에 mutex로 완전히 대체하기 어렵습니다.

tty_struct의 ldisc_sem

/* include/linux/tty.h — TTY 구조체의 동기화 필드 */

struct tty_struct {
    /* ... */
    struct ld_semaphore ldisc_sem;  /* ldisc 접근 보호 */
    struct tty_ldisc *ldisc;        /* 현재 line discipline */
    struct mutex atomic_write_lock; /* 쓰기 직렬화 */
    /* ... */
};

/* ld_semaphore — TTY 전용 rw_semaphore 변형
 * include/linux/tty_ldisc.h */
struct ld_semaphore {
    atomic_long_t count;      /* reader/writer 카운터 */
    wait_queue_head_t read_wait;  /* 리더 대기 큐 */
    wait_queue_head_t write_wait; /* 라이터 대기 큐 */
};

ldisc_sem 사용 패턴

/* drivers/tty/tty_ldisc.c — ldisc 접근 패턴 */

/* 1. ldisc 읽기 참조 획득 (read path — 매우 빈번)
 * tty_read(), tty_write(), tty_ioctl() 등에서 호출 */
struct tty_ldisc *tty_ldisc_ref_wait(struct tty_struct *tty)
{
    ldsem_down_read(&tty->ldisc_sem, MAX_SCHEDULE_TIMEOUT);
    if (tty->ldisc)
        return tty->ldisc;
    ldsem_up_read(&tty->ldisc_sem);
    return NULL;
}

/* 2. ldisc 교체 (write path — 드물지만 배타적)
 * TIOCSETD ioctl로 line discipline 변경 시 */
int tty_set_ldisc(struct tty_struct *tty, int disc)
{
    /* 모든 리더가 빠져나갈 때까지 대기 */
    tty_ldisc_lock(tty, MAX_SCHEDULE_TIMEOUT);  /* write lock */

    /* 이전 ldisc 제거, 새 ldisc 설치 */
    old_ldisc = tty->ldisc;
    tty->ldisc = new_ldisc;

    tty_ldisc_unlock(tty);  /* write unlock */
}

TTY의 레거시 semaphore 잔존 이유

TTY의 기타 동기화 프리미티브

/* TTY 서브시스템의 동기화 계층 */

struct tty_struct {
    struct ld_semaphore ldisc_sem;  /* ldisc 읽기/쓰기 보호 */
    struct mutex atomic_write_lock; /* 쓰기 직렬화 (단일 writer) */
    struct mutex legacy_mutex;     /* 레거시 ioctl 보호 */
    spinlock_t flow_lock;          /* 흐름 제어 */
    spinlock_t ctrl_lock;          /* 제어 문자 */
    wait_queue_head_t write_wait;  /* 쓰기 대기 */
    wait_queue_head_t read_wait;   /* 읽기 대기 */
};

/* 잠금 순서 (lockdep 규칙):
 * 1. tty->ldisc_sem (outermost)
 * 2. tty->atomic_write_lock
 * 3. tty->legacy_mutex
 * 4. tty->ctrl_lock / flow_lock (innermost) */

커널 버전별 진화

semaphore 계열 프리미티브는 커널 역사에서 가장 많이 변화한 동기화 메커니즘 중 하나입니다. v1.0의 단순한 구현에서 v6.x의 정교한 per-VMA lock까지, 각 버전별 핵심 변화를 추적합니다.

주요 버전별 변화

핵심 커밋 분석

# v2.6.16: mutex 도입 (Ingo Molnar)
commit 6053ee3b32e3 ("mutex: implement adaptive spinning")
# 영향: 수천 개의 semaphore가 mutex로 변환되기 시작

# v3.10: rwsem optimistic spinning (Tim Chen)
commit 4fc828e24896 ("rwsem: implement optimistic spinning")
# 영향: rwsem 경합 시 성능 2-3배 향상

# v4.15: rwsem HANDOFF (Waiman Long)
commit 617f3ef95177 ("locking/rwsem: Add writer HANDOFF")
# 영향: writer starvation 문제 해결

# v4.17: rwsem count 재설계 (Waiman Long)
commit a15ea1a35483 ("locking/rwsem: Rework rwsem count")
# 영향: 64비트 count로 리더/라이터 상태를 단일 atomic으로 관리

# v5.8: mmap_sem → mmap_lock (Michel Lespinasse)
commit 29a40ace841c ("mmap locking API: initial implementation")
# 영향: per-VMA lock을 위한 추상화 기반 마련

# v6.4: per-VMA lock (Suren Baghdasaryan)
commit 0b57d6ba064f ("mm: introduce per-VMA lock")
# 영향: 멀티스레드 페이지 폴트 처리량 ~75% 향상

실전 디버깅 시나리오

semaphore 관련 버그는 hung_task, lockdep splat, rwsem reader starvation 등의 형태로 나타납니다. 각 시나리오의 증상, 원인, 진단 절차를 분석합니다.

시나리오 1: down()에서 hung_task 발생

# 증상: dmesg에 hung_task 경고
INFO: task kworker/2:1:1234 blocked for more than 120 seconds.
      Not tainted 6.1.0 #1
"echo 0 > /proc/sys/kernel/hung_task_timeout_secs" disables this message.
task:kworker/2:1     state:D stack:12000 pid:1234 ppid:2 flags:0x00004000
Call Trace:
 <TASK>
 __schedule+0x2eb/0x8a0
 schedule+0x5e/0xd0
 schedule_timeout+0x98/0x160
 __down+0x5a/0x90          ← semaphore slow path에서 멈춤
 down+0x4b/0x60
 my_driver_probe+0x123/0x456  ← 드라이버 코드
 ...
 </TASK>

# 진단 절차

# 1. 어떤 semaphore에서 멈췄는지 확인
# __down의 인자(sem)를 crashdump에서 확인
crash> struct semaphore 0xffff8881234abcd0
struct semaphore {
  lock = { ... },
  count = 0,              ← count가 0 → 누군가 보유 중
  wait_list = {
    next = 0xffffc900001bfd30,  ← 대기자가 있음
    prev = 0xffffc900001bfd30
  }
}

# 2. wait_list에서 대기 중인 태스크 확인
crash> list semaphore_waiter.list -s semaphore_waiter.task 0xffffc900001bfd30
  task = 0xffff888123456780   ← 대기 중인 태스크

# 3. up()을 호출해야 할 태스크 추적
# semaphore는 owner가 없으므로 코드 분석이 필요
# → down()을 호출한 코드 경로를 역추적하여 up() 호출 위치 확인

시나리오 2: lockdep splat 분석

# 증상: rwsem 교착 경고
======================================================
WARNING: possible circular locking dependency detected
6.1.0 #1 Not tainted
------------------------------------------------------
modprobe/5678 is trying to acquire lock:
ffff8881aaaaa000 (&mm->mmap_lock){++++}-{3:3}, at: do_mmap+0x123

but task is already holding lock:
ffff8881bbbbb000 (&sb->s_umount){.+.+}-{3:3}, at: freeze_super+0x45

which lock already depends on the new lock.

the existing dependency chain (in reverse order) is:

-> #1 (&sb->s_umount){.+.+}-{3:3}:
       down_read+0x3e/0x50
       lookup_open+0x234/0x560
       ...

-> #0 (&mm->mmap_lock){++++}-{3:3}:
       down_write+0x3e/0x80
       do_mmap+0x123/0x456

# 해석:
# 경로 A: mmap_lock → s_umount (lookup_open에서 발생)
# 경로 B: s_umount → mmap_lock (freeze_super에서 시도)
# → AB / BA 교착 가능성!
#
# {++++}: 4가지 컨텍스트 모두 허용 (read-recur, read, write-recur, write)
# {.+.+}: read만 허용 (read-recur 불가, write-recur 불가)
# {3:3}: lock class의 subclass

시나리오 3: rwsem reader starvation 진단

# 증상: 시스템 전체 응답 느림, 특정 rwsem에서 다수 태스크 D 상태
# /proc/lock_stat로 경합 확인

$ cat /proc/lock_stat | grep mmap_lock
                          &mm->mmap_lock-R:  123456    234567   ...
                          &mm->mmap_lock-W:       5        10   ...

# W(writer) 경합은 적지만 R(reader) 경합이 극심
# → writer가 HANDOFF를 설정하여 모든 reader를 차단하는 경우

# 진단: ftrace로 rwsem_down_read_slowpath 추적
echo rwsem_down_read_slowpath > /sys/kernel/debug/tracing/set_ftrace_filter
echo rwsem_down_write_slowpath >> /sys/kernel/debug/tracing/set_ftrace_filter
echo function > /sys/kernel/debug/tracing/current_tracer
echo 1 > /sys/kernel/debug/tracing/tracing_on

# 30초 후 확인
cat /sys/kernel/debug/tracing/trace

# 결과 분석 예시:
# kworker-1234  [002] d..1  1234.567: rwsem_down_write_slowpath <-down_write
# reader-5678   [003] d..1  1234.568: rwsem_down_read_slowpath  <-down_read
# reader-5679   [004] d..1  1234.568: rwsem_down_read_slowpath  <-down_read
# ...
# → writer가 HANDOFF 설정 후 reader들이 slow path로 진입하고 있음

디버깅 체크리스트

유용한 디버깅 명령어 모음

# 1. D 상태(TASK_UNINTERRUPTIBLE) 태스크 확인
ps aux | awk '$8 ~ /D/'

# 2. 특정 태스크의 커널 스택 확인
cat /proc/<pid>/stack

# 3. lock_stat으로 경합이 심한 잠금 찾기
echo 1 > /proc/lock_stat
# (부하 발생 후)
sort -k2 -rn /proc/lock_stat | head -20

# 4. perf로 semaphore 경합 프로파일링
perf lock record -a -- sleep 10
perf lock report --sort acquired,contended,avg_wait

# 5. BPF로 down() 지연 시간 측정
bpftrace -e '
kprobe:down {
    @start[tid] = nsecs;
}
kretprobe:down /@start[tid]/ {
    @latency = hist(nsecs - @start[tid]);
    delete(@start[tid]);
}'

# 6. crashdump에서 semaphore 상태 확인
crash> struct semaphore <addr>
crash> list semaphore_waiter.list -s semaphore_waiter.task <wait_list_addr>

참고 자료

커널 공식 문서

• Generic Mutex Subsystem — mutex가 semaphore를 대체한 설계 배경과 성능 비교
• Lock types and their rules — 커널 잠금 유형 분류에서 semaphore의 위치
• Driver Basics — 드라이버에서의 semaphore 사용 (레거시 패턴)

LWN.net 심층 기사

• The mutex API (2013) — semaphore에서 mutex로의 전환 역사와 이유
• The new mutex (2006) — Ingo Molnár의 mutex 도입과 semaphore 대체 제안
• Optimistic spinning for mutexes (2013) — mutex가 semaphore보다 우수한 성능을 보이는 이유

학술 자료 및 외부 참고

• Edsger W. Dijkstra — "Cooperating Sequential Processes" (1965) — semaphore(P/V 연산)의 원조 논문
• Paul McKenney — "Is Parallel Programming Hard?" — 동기화 프리미티브 비교 (semaphore 포함)
• 커널 소스: kernel/locking/semaphore.c, include/linux/semaphore.h
• rw_semaphore 구현: kernel/locking/rwsem.c, include/linux/rwsem.h

관련 문서

Semaphore와 관련된 다른 동기화 주제를 더 깊이 이해하고 싶다면 다음 문서를 참고하세요.

• 동기화 기법 -- 전체 동기화 프리미티브 비교 및 선택 가이드
• 동기화 기법 -- Semaphore 섹션 -- semaphore 개요와 비교표
• Mutex -- adaptive spinning, osq_lock, 3단계 fastpath/midpath/slowpath
• Spinlock -- busy-wait 동기화, qspinlock 내부 구현
• Reader-Writer Lock -- qrwlock, rw_semaphore, percpu_rw_semaphore
• Completion -- semaphore 대용 이벤트 대기 프리미티브
• Wait Queue -- 슬립/웨이크업 메커니즘의 기반
• Atomic 연산 -- CAS/cmpxchg, 메모리 순서 의미론
• 메모리 배리어(Memory Barrier) -- acquire/release 의미론
• 동시성 디버깅 -- lockdep, KCSAN, perf lock 통합 가이드
• preempt_count -- 선점(Preemption) 모델과 컨텍스트 판별
• Futex -- 유저스페이스 동기화, PI Futex