[Linux Kernel] semaphore (2) - 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 매커니즘에 따라서 공정하지 않을 수 있다.