semaphore, lock, condition variable 간략한 설명

pintos 초기 코드를 기준.

void sema_init (struct semaphore *, unsigned value);
void sema_down (struct semaphore *);
void sema_up (struct semaphore *);

void lock_init (struct lock *);
void lock_acquire (struct lock *);
void lock_release (struct lock *);

void cond_init (struct condition *);
void cond_wait (struct condition *, struct lock *);
void cond_signal (struct condition *, struct lock *);

짜잘한 함수들을 생략했다. 선 작업중인 것이 있는경우 waiting하는것, 일반적인 순서로 대기할 수 있고 먼저 실행되어야하는 것들은

  • sema_down
  • lock_acquire

가 된다.

semaphore

원자적으로 조절되는 value로 wating을 조절한다. value는 여러 thread에 의해서 덮어쓰기가 되지않는다.

struct semaphore 
  {
    unsigned value;             /* Current value. */
    struct list waiters;        /* List of waiting threads. */
  };

void sema_down (struct semaphore *sema) 
{
  enum intr_level old_level;

  ASSERT (sema != NULL);
  ASSERT (!intr_context ());

  old_level = intr_disable ();
  while (sema->value == 0) 
    {
      list_push_back (&sema->waiters, &thread_current ()->elem);
      thread_block ();
    }
  sema->value--;
  intr_set_level (old_level);
}

void sema_up (struct semaphore *sema) 
{
  enum intr_level old_level;

  ASSERT (sema != NULL);

  old_level = intr_disable ();
  if (!list_empty (&sema->waiters)) 
    thread_unblock (list_entry (list_pop_front (&sema->waiters),
                                struct thread, elem));
  sema->value++;
  intr_set_level (old_level);
}

down에서 value 값이 0일때는 무한히 기다리며 waiting list에 순서대로 등록을 한다. up에서는 value 값을 증가시킨다.(1이 된다.) waiting list에 등록되어있는 thread를 앞에서부터 뽑아내고 unblock을 한다 그러면 waiting list에 등록 된 순서대로 실행된다.

lock

/* Lock. */
struct lock 
  {
    struct thread *holder;      /* Thread holding lock (for debugging). */
    struct semaphore semaphore; /* Binary semaphore controlling access. */
  };

void lock_acquire (struct lock *lock)
{
  ASSERT (lock != NULL);
  ASSERT (!intr_context ());
  ASSERT (!lock_held_by_current_thread (lock));

  sema_down (&lock->semaphore);
  lock->holder = thread_current ();
}

void lock_release (struct lock *lock) 
{
  ASSERT (lock != NULL);
  ASSERT (lock_held_by_current_thread (lock));

  lock->holder = NULL;
  sema_up (&lock->semaphore);
}

보통 뮤텍스라고 많이 불린다. 사실 세마포어를 내부적으로 사용하여 사실상 차이가 없다.

condition variable

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

struct condition 
  {
    struct list waiters;        /* List of waiting threads. */
  };

struct semaphore_elem 
  {
    struct list_elem elem;              /* List element. */
    struct semaphore semaphore;         /* This semaphore. */
  };

void cond_wait (struct condition *cond, struct lock *lock) 
{
  struct semaphore_elem waiter;

  ASSERT (cond != NULL);
  ASSERT (lock != NULL);
  ASSERT (!intr_context ());
  ASSERT (lock_held_by_current_thread (lock));
  
  sema_init (&waiter.semaphore, 0);
  list_push_back (&cond->waiters, &waiter.elem);
  lock_release (lock);
  sema_down (&waiter.semaphore);
  lock_acquire (lock);
}

void cond_signal (struct condition *cond, struct lock *lock UNUSED) 
{
  ASSERT (cond != NULL);
  ASSERT (lock != NULL);
  ASSERT (!intr_context ());
  ASSERT (lock_held_by_current_thread (lock));

  if (!list_empty (&cond->waiters)) 
    sema_up (&list_entry (list_pop_front (&cond->waiters),
                          struct semaphore_elem, elem)->semaphore);
}

monitor로도 불린다. cond 쪽의 구조

가 상당히 복잡하다. semaphore_elem이란 구조체를 추가로 내부적으로 사용한다. semaphore_elem은 세마포어를 list에 올리기 위해서 elem 멤버를 넣은 구조체이다.

assert를 보면 한가지 알 수 있는것이 cond_wait는 일단 현재 thread에서 lock_acquire를 통해 대기가 아닌 holder가 현재 thread로 지정된 실행하여야 한다. 이로서 lock_acquire 다음의 실행 코드에서 사용되며 lock에 대한 해제는 따로 해줘야한다.

내부 세마포어 원소는 세마를 0으로 설정한후 down을 해버림으로 무한히 대기를 한다. 이때 down전후로 lock_release와 lock_acquire을 하는데 이는 해당 lock에 대해서 deadlock을 피하기 위함으로 파악된다.

cond_signal은 말그대로 cond->waiters list에 들어가있는 순서대로 뽑아 sema_up을 통해 cond_wait에서 대기중인 상태를 풀어버린다.

한가지의 lock에 대해서 다수의 codition을 세팅 할 수 있으며 개별 condition에 대해서 waiting하는 각 thread마다 개인의 semaphore를 가진다.

Posted 2021-02-19
pintos