priority scheduling

sleep/awake 방식의 한계

sleep/awake 방식으로 구현한 pintos는 스레드의 우선순위가 고려되지 않았다.

void
thread_unblock (struct thread *t) 
{
  enum intr_level old_level;

  ASSERT (is_thread (t));

  old_level = intr_disable ();
  ASSERT (t->status == THREAD_BLOCKED);
  list_push_back (&ready_list, &t->elem);	
  t->status = THREAD_READY;
  intr_set_level (old_level);
}

void
thread_yield (void) 
{
  struct thread *cur = thread_current ();
  enum intr_level old_level;
  
  ASSERT (!intr_context ());

  old_level = intr_disable ();
  if (cur != idle_thread) 
    list_push_back (&ready_list, &cur->elem);	
  cur->status = THREAD_READY;
  schedule ();
  intr_set_level (old_level);
}

즉 위의 함수들을 보면 list_push_back() 함수를 통해 ready_list의 맨 뒤에 넣어주는 방식으로 코드를 작성하였다.

이제 각각의 스레드에게 우선순위를 부여해주고 우선순위에 맞게 running시켜주면 주도록 해보자

priority scheduling 구현

• ready list에 새로 추가된 thread의 우선순위가 현재 CPU를 점유중인 thread의 우선순위보다 높으면 기존 thread를 밀어내고 CPU를 점유하도록 한다.

list_insert_ordered 란

priority scheduling에서는 내장되어있는 함수중에 list_insert_ordered 함수를 사용할 것이다.

/* lib/kernel/list.c */
void
list_insert_ordered (struct list *list, struct list_elem *elem,
                     list_less_func *less, void *aux)
{
  struct list_elem *e;

  ASSERT (list != NULL);
  ASSERT (elem != NULL);
  ASSERT (less != NULL);

  for (e = list_begin (list); e != list_end (list); e = list_next (e))
    if (less (elem, e, aux))
      break;
  return list_insert (e, elem);
}

이 함수는 삽입할 list와 요소를 받고 비교함수를 받아서 그에 맞게 리스트를 정렬해주는 함수이다. 원래 기존 코드의 list_push_back() 함수를 list_insert_ordered 함수로 대체해준다고 생각하자!

일단 그러기위해서는 list_insert_ordered 함수의 인자중에 하나인 비교함수를 만들어야 한다.

비교 함수 구현

/* thread/thread.c */
bool 
thread_cmp_priority (struct list_elem *l, struct list_elem *s, void *aux UNUSED)
{
    return list_entry (l, struct thread, elem)->priority
         > list_entry (s, struct thread, elem)->priority;
}

priority를 비교하여 bool값을 반환해주는 함수이다. 이 함수가 list_insert_ordered 함수의 인자로 들어갈 것이다.

list_insert_ordered 이용

/* thread/thread.c */
void
thread_unblock (struct thread *t) 
{
  enum intr_level old_level;

  ASSERT (is_thread (t));

  old_level = intr_disable ();
  ASSERT (t->status == THREAD_BLOCKED);
  //list_push_back (&ready_list, &t->elem);
  list_insert_ordered (&ready_list, &t->elem, thread_compare_priority, 0);
  t->status = THREAD_READY;
  intr_set_level (old_level);
}

void
thread_yield (void) 
{
  struct thread *cur = thread_current ();
  enum intr_level old_level;
  
  ASSERT (!intr_context ());

  old_level = intr_disable ();
  if (cur != idle_thread) 
    //list_push_back (&ready_list, &cur->elem);
    list_insert_ordered (&ready_list, &cur->elem, thread_compare_priority, 0);
  cur->status = THREAD_READY;
  schedule ();
  intr_set_level (old_level);
}

기존의 list_push_back 함수를 list_insert_ordered 함수로 대체해준다.

그 이유는?

우선순위에 맞게 정렬해주기 위함이다.

thread_create, thread_set_priority 수정

이 두 경우에는 running thread와 ready_list의 가장 앞의 thread의 priority를 비굨하는 코드를 넣어주어야한다.

void test_max_priority(void)
{
	if(!list_empty(&ready_list) && 
			thread_current()->priority < 
			list_entry(list_front(&ready_list), struct thread, elem)->priority)
	{
		thread_yield();
	}
}

위 함수를 통해서 현재 스레드(running thread)의 우선순위와 ready_list의 가장 앞의 스레드의 우선순위를 바교할 수 있다.

이제 이 함수를 thread_create와 thread_set_priority에 넣어보자

/* thread/thread.c */
tid_t
thread_create (const char *name, int priority,
               thread_func *function, void *aux)
{
  ...
  thread_unblock (t);
  thread_test_preemption ();

  return tid;
}

void
thread_set_priority (int new_priority)
{
  thread_current ()->priority = new_priority;
  thread_test_preemption ();
}

참고자료

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