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

스케쥴링은 ready 상태에 있는 스레드들의 순서를 관리하여 가장 높은 priority 를 가진 스레드가 running 상태가 될 수 있도록 만들어주는 것이다. 

 

현재상태

우선 현재 pintos 가 스케쥴링을 어떻게 관리하고 있는지 살펴보자. ready_list 에 새로운 스레드가 push 되는 순간을 찾아보면 될 것 같다.

/* 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);	// ready_list 에 스레드 추가
  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);	// ready_list 에 스레드 추가
  cur->status = THREAD_READY;
  schedule ();
  intr_set_level (old_level);
}

ready_list 에 새로운 스레드가 추가되는 두 함수를 찾아냈다. 공통적으로 list_push_back (&ready_list, ... ) 함수가 사용되었고 이 함수는 <lib/kernel/list.c> 에서 찾아볼 수 있는데, 이름에서 알 수 있듯이 새로운 elem 을 리스트의 맨 뒤에 push 하는 함수이다. 즉 현재 pintos 는 새로운 스레드를 ready_list 에 넣을 때 항상 맨 뒤에 넣는다는 것을 볼 수 있다. 그럼 ready_list 에서 스레드를 꺼낼 때는 어떻게 진행되는지도 찾아보자. ready_list 에서 스레드를 꺼내는 순간은 현재 running thread 가 CPU 를 양보하여 새로운 running thread 를 고르는 순간이다. 아래 그림을 보자.

스레드의 흐름

위 그림에서 보면 THREAD_RUNNING 에서 나가는 화살표가 running thread 가 CPU 를 양보하는 순간이다. thread_exit(), thread_yield(), thread_block() 세 경우가 있는 것을 볼 수 있다. 이 세 함수들은 <thread/thread.c> 에 있고, 하나하나 살펴보면 함수의 마지막부분에 schedule() 함수를 호출하고 CPU 소유권을 내려놓는다. 그럼 이 schedule() 를 살펴보아야 한다. 

/* thread/thread.c */
static void
schedule (void) 
{
  struct thread *cur = running_thread ();
  struct thread *next = next_thread_to_run ();
  struct thread *prev = NULL;

  ASSERT (intr_get_level () == INTR_OFF);
  ASSERT (cur->status != THREAD_RUNNING);
  ASSERT (is_thread (next));

  if (cur != next)
    prev = switch_threads (cur, next);
  thread_schedule_tail (prev);
}

schedule() 함수는 switch_threads (cur, next) 함수를 실행하여 CPU 점유권을 cur 에서 next 스레드로 넘긴다. switch_threads 함수의 자세한 설명은 thread background 포스트(poalim.tistory.com/26)에 설명 해놓았으니 확인해보길 바란다. 그럼 여기서 다음으로 CPU 의 점유권을 받는 함수는 next_thread_to_run() 에 의해 결정된다는 것을 알 수 있다. 이 함수 역시 thread.c 에서 찾아볼 수 있다.

static struct thread *
next_thread_to_run (void) 
{
  if (list_empty (&ready_list))
    return idle_thread;
  else
    return list_entry (list_pop_front (&ready_list), struct thread, elem);
}

반환값을 보면 list_pop_front (&ready_list), 즉 ready_list 의 맨 앞의 항목을 반환한다는 것을 알 수 있다.

 

즉, 현재 pintos 는 ready_list 에 push 는 맨 뒤에, pop 은 맨 앞에서 하는 round-robin 방식을 채택하고 있다는 것을 알 수 있다. 이러한 방식은 스레드간의 우선순위 없이 ready_list 에 들어온 순서대로 실행하여 가장 간단하지만 제대로 된 우선순위 스케쥴링이 이루어지고 있지 않다고 할 수 있다.

Priority Scheduling 구현

pintos 가 제대로 우선순위 스케쥴링을 하도록 만들어보자. 두 가지 방법이 가능할 것 같다.

• ready_list 에 push 할 때 priority 순서에 맞추어 push 하는 방법
• ready_list 에서 pop 할 때 priority 가 가장 높은 스레드를 찾아 pop 하는 방법

 

전자는 항상 ready_list 가 정렬된 상태를 유지하기 때문에 새로운 스레드를 push 할 때 list 의 끝까지 모두 확인할 필요가 없지만, 후자는 ready_list 가 정렬된 상태를 유지하지 않으므로 pop 할 때마다 list 의 처음부터 끝까지 모두 훑어야 하기 때문에 전자가 더 효율적이기 때문에 전자의 방법을 사용하기로 한다.

push 할 때 순서에 맞추어 넣기 때문에 꺼낼때는 리스트의 맨 앞에서 꺼내는 현재 방식을 유지하고 정렬 방식을 내림차순으로 설정하면 되기 때문에 next_thread_to_run() 함수는 건드리지 않아도 될 것 같다. 바꾸어야 하는 것은 위에서 살펴본 list_push_back 이 실행되는 thread_unblock(), thread_yield() 함수이다. thread_create() 함수에서도 새로운 스레드가 ready_list 에 추가되지만 thread_create() 함수 자체에서 thread_unblock() 함수를 포함하고 있기 때문에 thread_unblock() 함수를 수정함으로써 동시에 처리된다. 그럼 list_push_back 함수를 내림차순으로 정렬하여 push 하는 함수로 대체하여 보자. <lib/kernel/list.c> 에는 list 를 다루는 여러 함수들이 구현되어 있는데 아주 유용해 보이는 함수를 찾아볼 수 있다.

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

이름에서 볼 수 있듯이 정렬하여 리스트에 insert 하는 함수이다. parameter 는 insert 할 list 와 element 를 받고 비교함수를 받는다. 내용을 보면 for 반복문으로 list 의 첫 e 부터 진행하면서 입력받은 elem 이 less 함수를 통과하는 순간의 e 위치에 해당 element 를 삽입한다. e 위치에 삽입하는 list_insert (e, elem) 함수가 elem 을 e 의 앞에 삽입하는지 뒤에 삽입하는지도 확인해야 한다.

/* lib/kernel/list.c */
void
list_insert (struct list_elem *before, struct list_elem *elem)
{
  ASSERT (is_interior (before) || is_tail (before));
  ASSERT (elem != NULL);
  elem->prev = before->prev;
  elem->next = before;
  before->prev->next = elem;
  before->prev = elem;
}

elem->next = before 이므로 elem 은 e 의 앞에 삽입된다는 것을 확인했다. 우리는 ready_list 에서 스레드를 pop 할 때 가장 앞에서 꺼내기로 하였기 때문에 가장 앞에 priority 가 가장 높은 스레드가 와야 한다. 즉, ready_list 는 내림차순으로 정렬되어야 한다. list_insert 가 일어나는 순간 elem 은 e 의 앞으로 들어가기 때문에 내림차순으로 정렬되기 위해서는 if (less (elem, e, aux)) 가 elem > e 인 순간에 break; 를 실행해주어야 한다. 즉, 우리가 만들어야 하는 함수 less (elem, e, aux) 는 elem > e 일 때 true 를 반환하는 함수이다.

/* thread/thread.c */
bool 
thread_compare_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;
}

위와 같이 비교 함수를 만들어 주었다. 이제 이 함수를 적용하여 list_push_back 을 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);
}

thread_unblock, thread_yield 에서 list_push_back 을 주석처리하고 list_insert_ordered 를 넣어주었다. 세 번째 인자에 위에서 만든 thread_compare_priority 함수를 넣어서 처리해주면 된다.

 

자, 아직 한 가지가 남았다. 현재 실행중인 running 스레드의 priority 가 바뀌는 순간이 있다. 이 때 바뀐 priority 가 ready_list 의 가장 높은 priority 보다 낮다면 CPU 점유를 넘겨주어야 한다. 현재 실행중인 스레드의 priority 가 바뀌는 순간은 두 가지 경우이다.

• thread_create()
• thread_set_priority()

 

위 두 경우의 마지막에 running thread 와 ready_list 의 가장 앞의 thread 의 priority 를 비교하는 코드를 넣어주어야 한다. 

/* thread/thread.c */
void 
thread_test_preemption (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 의 priority 를 비교하고, 만약 ready_list 의 스레드가 더 높은 priority 를 가진다면 thread_yield () 를 실행하여 CPU 점유권을 넘겨주는 함수를 만들었다. 이 함수를 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 ();
}

 

결과

이제 기본적인 priority scheduling 을 구현하였으니 테스트를 해보자.

무려 4개의 테스트를 더 통과했다!! 아직 통과하지 못한 테스트를 보면 priority-donate, priority-sema 등의 항목이 눈에 띈다. pintos 도큐먼트에서도 명시되어 있듯이 priority scheduling 은 priority donate 와 priority sema 까지 구현해야 한다. 이것은 다음 포스트에서 살펴보도록 한다.