앞서 spinlock의 개념과 사용법을 소개하고, 관련 알고리즘이 어떻게 발전했는지 살펴보았다. spinlock은 선점을 비활성화하고, 필요에 따라서 interrupt나 bottom half도 비활성화를 하므로 spinlock은 오랫동안 락을 들고있어선 안된다. 오랫동안 스케줄링과 인터럽트가 처리되지 않는다고 생각하면 정말 끔찍하다. spinlock은 그 특성상 락을 획득한 동안에는 sleep이 불가능하다. 이러한 상황에서는 spinlock 대신, 휴면 가능한 락(sleeping lock)인 semaphore를 사용할 수 있다.
semaphore는 휴면이 가능하므로 interrupt context에서 사용할 수 없으며, 보통 process context에서 락을 오랫동안 들고있는 경우 사용한다. semaphore는 리눅스 커널에서 많이 쓰진 않는 것 같다. 더 성능이 좋은 mutex를 쓰는 것 같은데, 이건 다음에 글로 정리해보겠다.
개념
semaphore란
spinlock은 한 번에 하나의 스레드만 락을 획득할 수 있다. 따라서 상호배제(mutual exclusion, 한 번에 하나의 스레드만 critical section에 들어가는 것)이 가능하다. 이와 달리 semaphore는 그 구조상, 여러 개의 스레드가 critial section에 들어갈 수 있다. 이 개수를 count라고 하자. count > 0이면, 락을 획득할 수 있는 상태이며, count == 0이면, 다른 스레드가 락을 반환할 때까지 대기해야 한다. 락을 획득하여 count를 감소하는 것을 P 연산 (Proberen), 락을 반환하여 count를 증가하는 것을 V 연산 (Verhogen)이라고 한다.
counting semaphore vs binary semaphore
count == 1인 semaphore를 binary semaphore라고 하고, count > 1인 semaphore를 counting semaphore라고 부른다.
자, 근데 상식적으로 생각해봤을 때 count > 1인 semaphore는 mutual exclusion이 불가능하다. 아니, 두 개의 스레드가 동시에 critial section 안에서 실행중이라면, 락을 사용하는 이유가 없지 않나? 그래서 나도 아직 이걸 왜 사용하는지는 잘 모르겠다. 적어도 mutual exclusion을 위해서 사용하지는 않는다.
binary semaphore는 한 번에 하나의 스레드만 critial section에 진입할 수 있다. 따라서 우리가 원하는 동기화 매커니즘을 구현할 수 있다. binary semaphore를 MUTEX (MUTual EXclusion)이라고 부르기도 한다.
semaphore API
semaphore의 구조와 할당
/* Please don't access any members of this structure directly */
struct semaphore {
raw_spinlock_t lock;
unsigned int count;
struct list_head wait_list;
};
semaphore 구조체에는 아까 우리가 이야기한 count와, 락을 기다리는 wait_list, 그리고 semaphore 구조체 자체를 보호하기 위한 spinlock이 존재한다.
/* static allocation (count == 1) */ DEFINE_SEMAPHORE(name); /* dynamic allocation */ semaphore sem; int count = 1; sema_init(&sem, count);
down, down_killable, down_interruptible, down_trylock, down_timeout
리눅스 커널에서 P 연산에 대응되는 함수가 바로 down이다. down은 현재 count가 0이라면 락을 획득할 때까지 대기하며, count > 0이라면 락을 획득하고 count를 감소한다. 그런데 down 함수를 사용하면 TASK_UNINTERRUPTIBLE 상태가 되기 때문에, 시그널 등이 와도 반응하지 않는다. 그래서 죽일 수 없는 프로세스가 만들어지는데, 이를 방지하기 위해서 일반적으로 down_interruptible 또는 down_killable을 사용한다. 그 외에 down_trylock은, 현재 count > 0인 경우에만 락을 획득하며 count == 0이라면 락을 기다리지 않고 바로 함수를 리턴한다. down_timeout은 락을 기다리되 jiffies 동안만 대기한다.
자세한 설명은 kernel/locking/semaphore.c를 참고하자. 정말 문서화가 잘 되어있다.
void down(struct semaphore *sem); int down_interruptible(struct semaphore *sem); int down_killable(struct semaphore *sem); int down_trylock(struct semaphore *sem); int down_timeout(struct semaphore *sem, long jiffies);
up
V 연산에 대응되는 함수는 up이다. down 함수는 변종이 많지만, up 함수는 단 하나뿐이다. up 함수는 획득한 락을 반환한다. up 함수는 락을 획득한 프로세스가 아니더라도 호출할 수 있다. (up를 임의로 호출해서 count를 증가시킬 수 있다.)
void up(struct semaphore *sem)
간단한 예시
DEFINE_SEMAPHORE(sem); down_interruptible(&sem); /* critical section */ up(&sem);
semaphore 분석
semaphore의 매커니즘을 분석해보자. 아래 그림은 코드를 그림으로 옮긴 것이다.
struct semaphore
이전 글에서 살펴본 semaphore 구조체다. 구조체 자체를 보호하기 위한 lock, lock을 획득할 수 있는 스레드 수를 나타내는 count, 대기중인 스레드를 나타내는 wait_list가 있다.
/* Please don't access any members of this structure directly */
struct semaphore {
raw_spinlock_t lock;
unsigned int count;
struct list_head wait_list;
};
struct semaphore_waiter
semaphore 대기를 하기 위해 사용되는 자료구조이다. 매우 직관적이다. list는 list의 시작 노드를, task는 대기중인 프로세스를, up은 해당 프로세스가 락을 획득했는지를 나타낸다. semaphore_waiter 구조체도 락이 필요할거라고 생각했는데, 코드를 잘 분석해보면 semaphore 자체의 spinlock으로 관리된다는걸 알 수 있다.
/* Functions for the contended case */
struct semaphore_waiter {
struct list_head list;
struct task_struct *task;
bool up;
};
down_interruptible 분석
down은 변종이 너무 많으니, 그중 하나인 down_interruptible을 분석해보자. 어차피 모두 내부적으로는 __down_common을 호출하므로 거기서 거기이다.
/**
* down_interruptible - acquire the semaphore unless interrupted
* @sem: the semaphore to be acquired
*
* Attempts to acquire the semaphore. If no more tasks are allowed to
* acquire the semaphore, calling this function will put the task to sleep.
* If the sleep is interrupted by a signal, this function will return -EINTR.
* If the semaphore is successfully acquired, this function returns 0.
*/
int down_interruptible(struct semaphore *sem)
{
unsigned long flags;
int result = 0;
raw_spin_lock_irqsave(&sem->lock, flags);
if (likely(sem->count > 0))
sem->count--;
else
result = __down_interruptible(sem);
raw_spin_unlock_irqrestore(&sem->lock, flags);
return result;
}
EXPORT_SYMBOL(down_interruptible);
down_interruptible은 먼저 인터럽트를 비활성화한다. 그 후 sem->count > 0인 경우, 락을 획득할 수 있다는 것이므로 획득한 후, sem->lock을 반환한다. 만약 sem->count <= 0이어서 획득할 수 없는 경우에는 __down_interruptible를 호출한다.
__down_interruptible
static noinline int __sched __down_interruptible(struct semaphore *sem)
{
return __down_common(sem, TASK_INTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT);
}
/*
* Because this function is inlined, the 'state' parameter will be
* constant, and thus optimised away by the compiler. Likewise the
* 'timeout' parameter for the cases without timeouts.
*/
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);
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)
return 0;
}
timed_out:
list_del(&waiter.list);
return -ETIME;
interrupted:
list_del(&waiter.list);
return -EINTR;
}
__down_interruptible은 내부적으로 __down_common을 호출한다. __down_common은 semaphore 구조체, state (TASK_INTERRUPTIBLE, TASK_UNINTERRUPTIBLE 등 프로세스의 state), 그리고 timeout을 파라미터로 받는다. down_interruptible은 프로세스가 중간에 시그널을 받도록 하므로, state = TASK_INTERRUPTIBLE로 호출한다.
함수의 초반부에서는 sem->wait_list에 현재 프로세스를 넣어서 대기하도록 한다.
그 후에는 무한루프를 돌면서 다음의 작업을 반복한다.
1. 시그널을 받았거나 timeout이 되면 리스트를 제거하고 리턴
2. schedule_timeout으로 sleep한다.
3. 깨어난다. 락을 획득했는가? 획득했다면 탈출한다. 아니면 다시 1번부터 반복
up 분석
up도 구현이 매우 간단하다. wait_list가 비어있는 경우에는 count를 그냥 증가시키고, 비어있지 않은 경우에는 sem->wait_list에서 가장 첫 번째 노드를 가져온다. 그 후 대기중인 프로세스의 waiter->up = true로 변경하고, wake_up_process로 깨운다.
/**
* up - release the semaphore
* @sem: the semaphore to release
*
* Release the semaphore. Unlike mutexes, up() may be called from any
* context and even by tasks which have never called down().
*/
void up(struct semaphore *sem)
{
unsigned long flags;
raw_spin_lock_irqsave(&sem->lock, flags);
if (likely(list_empty(&sem->wait_list)))
sem->count++;
else
__up(sem);
raw_spin_unlock_irqrestore(&sem->lock, flags);
}
EXPORT_SYMBOL(up);
static noinline void __sched __up(struct semaphore *sem)
{
struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list,
struct semaphore_waiter, list);
list_del(&waiter->list);
waiter->up = true;
wake_up_process(waiter->task);
}
semaphore는 공정한가?
wait_list에 진입한 후에는 먼저 들어온 순서대로 깨어나므로 공정하다. 하지만 wait_list에 진입하는 과정 자체는 spinlock 매커니즘에 따라서 공정하지 않을 수 있다.