Priority scheduling and synchronization

이제 공유 자원을 사용할때 문제가 생기지 않도록 semaphore를 이용하여 구현해볼것이다.

semaphore?

semaphore는 깃발을 의미한다.

위의 이미지에서 겹치는 기차길을 깃발을 통해서 두 기차가 동시에 가지 못하도록 막는다.

똑같다!

두개의 스레드가 하나의 공유자원을 접근하지 못하도록 막는것이다

semaphore를 이용한 코드 구현

이제부터는 waiter리스트라는 것을 하나 만들것이다. 이 리스트는 모든 공유자원이 꽉 찼을때 기다리는 스레드가 들어갈 리스트이다.

여기서 중요한것은 waiter list도 우선순위에 맞게 정렬해야한다는 점이다.

sema_down 함수 수정

waiter 리스트 삽입시에 우선순위대로 삽입되도록 수정해야 한다.

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);
      list_insert_ordered (&sema->waiters, &thread_current ()->elem, thread_compare_priority, 0);
      thread_block ();
    }
  sema->value--;
  intr_set_level (old_level);
}

여기서도 우선순위대로 삽입이 되어야 하므로 list_insert_ordered() 함수를 사용한다.

sema_up 함수 수정

void
sema_up (struct semaphore *sema) 
{
  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++;
  test_max_priority ();
  intr_set_level (old_level);
}

sema_up 함수는 공유 자원의 문을 잠가주는 역할을 한다.

여기서도 waiter_list의 우선순위가 변경될수 있으니 list_sort를 통해 우선순위를 정렬해준다.

그리고 unblock된 스레드가 running스레드보다 우선순위가 높을수있으므로 test_max_priority 함수를 추가해준다.

cmp_sem_priority 함수 추가

이번에는 입력받는 파라미터가 스레드가 아니라 semaphore_elem의 elem으로 들어오므로 새로운 우선순위 비교 함수를 만들어야 한다.

그것이 cmp_sem_priority이다.

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 수정

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);
  list_insert_ordered (&cond->waiters, &waiter.elem, sema_compare_priority, 0);
  lock_release (lock);
  sema_down (&waiter.semaphore);
  lock_acquire (lock);
}

기존의 list_push_back을 list_insert_ordered 함수로 수정한다.

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);
  }
}

condition variable의 waiter리스트를 우선순위로 재정열해야한다.

list_sort함수를 사용하면 재정렬이 가능하다.