[week08] PintOS - Project 1(thread) : Priority Scheduling(2)

Project1: priority schedule(2)

이번엔 무엇을 바꿔볼까?

이번에는 Synchronization과 관련된 도구들의 scheduling 방식을 살펴보자.

그 도구들은 semaphore, lock, condition variables가 존재한다.

그런데 현재 PintOS는 여러 thread들이 semaphore, lock, condition variables를 얻기 위해 기다릴 경우 먼저 온 놈이 먼저 사용하는 FIFO 방식을 사용하고 있다.

Synchronization 도구들을 기다릴 때, 우선순위가 가장 높은 therad가 CPU를 점유하도록 구현해보자.

Semaphore

하나의 공유자원을 사용하기 위해 여러 thread가 sema_down 되어 대기하고 있다고 할 때, 이 공유자원을 사용하던 thread가 공유자원의 사용을 마치고 sema_up 할 때 어떤 thread가 가장 먼저 이 공유자원을 차지할 것인가?

현재 PintOS에 구현되어있는 방식은 다음과 같다.

Semaphore 해결책

우선순위를 부여해서 정렬하는 방식으로 바꾸자!

ready_list를 변경했던 것처럼 이번에도 비슷한 방식으로 바꾸면 된다(thread를 대기하는 곳에 넣을 때는 priority가 큰 순서대로 정렬하고, 꺼낼 때는 맨 앞에서 꺼내는 방식).

sema_down 함수를 수정해보자.

// thread/synch.c

void sema_down(struct semaphore *sema)
{ // "P"(down)연산 - 값이 양수가 될 때까지 기다렸다가 1씩 감소
   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);
      list_insert_ordered(&sema->waiters, &thread_current()->elem, thread_compare_priority, 0);
      thread_block();
   }
   sema->value--;
   intr_set_level(old_level);
}

여기서 사용한 thread_compare_priority는 이전 포스트에서 만들어 주었던 것을 그대로 사용한 것이다.

sema_up() 함수에서는 waiters 리스트에 있던 동안 우선순위의 변경이 생겼을 수 있으므로 waiters 리스트를 정렬해 준다. 그리고 unblock 된 thread가 running 상태의 thread보다 높은 priority를 가질 수도 있으니까 thread_test_preemption()을 사용해서 선점 가능하게 해준다.

// thread/synch.c

void sema_up(struct semaphore *sema)
{ // "V"(up)연산. thread가 sema를 기다리고 있으면 그 중 하나 깨움(1증가).
   enum intr_level old_level;

   ASSERT(sema != NULL);

   old_level = intr_disable();
   if (!list_empty(&sema->waiters))
   {
      list_sort(&sema->waiters, thread_compare_priority, 0);
      thread_unblock(list_entry(list_pop_front(&sema->waiters),
                                struct thread, elem));
   }

   sema->value++;
   thread_test_preemption();
   intr_set_level(old_level);
}

lock

lock은 semaphore의 부분집합으로 semaphore의 initial value가 1이라는 점(binary semaphore)과 lock을 acquire 한 thread만 release가 가능하다는 제약조건만 제외하면 semaphore와 동일하므로 semaphore를 해결하면 자동으로 lock도 해결된다.

미심쩍은 사람들을 위해 코드도 첨부한다.

// threads/synch.c

void lock_init(struct lock *lock)
{ // 잠금 초기화 - 잠금은 처음에 어떤 thread에서도 소유하지 않음
   ASSERT(lock != NULL);

   lock->holder = NULL;
   sema_init(&lock->semaphore, 1);
}

void lock_acquire(struct lock *lock)
{ // 현재 thread에 대한 잠금을 획득하고 필요한 경우 current owner가 release하기를 기다림
   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);
}

위의 코드에서 acquire에는 sema_down, relase에는 sema_up이 들어가 있는 것을 볼 수 있다.

Condition variables(Monitors)

Monitor는 semaphore나 lock보다 상위 수준의 Synchronization 형태이다.

보호된 data로 접근하기 전에 thread는 monitor lock 을 획득한다. 이 것을 “in the monitor”라고 한다. “in the monitor”상태에서는 thread는 모든 보호받는 데이터에 자유롭게 접근이 가능하다. 다른 thread의 접근은 금지된다. 작업이 끝나면 monitor lock을 해제(release)한다.

조건변수(condition variable)는 특정 conditon이 참이 될때까지 기다리는 thread들의 컨테이너다.

“in the monitor”의 코드가 특정 상태가 참이 될때까지 기다릴 때, 그 코드는 연관된 condition variable 위에서 기다린다. 여기서 연관된 condition variable은 lock을 release하고 wait을 해제할 signal을 보내는 condition variable이다.

여기서도 semaphore와 마찬가지로 list_push_back() 함수를 list_insert_ordered() 함수로 바꾸어주면 된다.

그런데 한 가지 문제점이 존재한다.

condition variable도 waiters list를 가지고 있는데 이 waiters는 semaphore의 list이다. semaphore에는 thread들의 list가 기다리고 있기 때문에 이 부분이 약간 복잡하다.

semaphore에서는 therad_compare_priority() 함수를 사용했지만, 이번에는 구조가 다르기 때문에 semaphore_elem이 나타내는 semaphore의 waiters 리스트의 맨 앞 thread끼리 priority를 비교해주는 함수를 새로 만들어야 한다.

// thread/synch.c

bool 
sema_compare_priority (const struct list_elem *l, const struct list_elem *s, void *aux UNUSED)
{
    struct semaphore_elem *l_sema = list_entry (l, struct semaphore_elem, elem);
    struct semaphore_elem *s_sema = list_entry (s, struct semaphore_elem, elem);

    struct list *waiter_l_sema = &(l_sema->semaphore.waiters);
    struct list *waiter_s_sema = &(s_sema->semaphore.waiters);

    return list_entry (list_begin (waiter_l_sema), struct thread, elem)->priority
         > list_entry (list_begin (waiter_s_sema), struct thread, elem)->priority;
}

cond_wait()과 cond_signal() 함수가 있는데, 우리는 cond_signal() 함수만 바꿔주면 된다.

왜냐하면 cond_signal() 함수에서 우선순위에 따라 sorting을 해주기 때문이다.

// thread/synch.c

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))
  {
    list_sort (&cond->waiters, sema_compare_priority, 0);
    sema_up (&list_entry (list_pop_front (&cond->waiters),
                          struct semaphore_elem, elem)->semaphore);
  }
}

참고자료

[Pintos] Project 1 : Thread(스레드) - Priority Scheduling(2)

한양대학교 핀토스 운영체제 실습자료 (youjip Won)

Monitor(모니터)에 대해 알아보고 동기화를 이해하기