[PintOS] Project 1.2 Priority Scheduling(1)

1. 과제 소개

1.1 과제 소개

스케줄링이란 대기 중인 스레드 중에 실행할 스레드를 정하는 과정입니다. 현재 PintOS는 Round Robin 방식으로 스케줄링이 구현되어 있습니다.

1.2 목표

스레드마다 중요성이 다르기 때문에 스레드의 우선순위에 따라 실행순서를 결정하는 priority scheduling을 구현할 것입니다.

2. PintOS의 현재상태

2.1 thread_unblock()

/* 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);
  t->status = THREAD_READY;
  intr_set_level (old_level);
}

• 역할: block 상태의 스레드를 대기리스트에 넣고 ready 상태로 변경합니다.

2.2 thread_yield()

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

• 역할: 현재 스레드가 다음 순서의 스레드에게 cpu를 양보하게 합니다.
• 특징: 우선순위와 무관하게 대기리스트에서 다음 순서의 스레드를 선택합니다.

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

• 역할: cpu 점유권을 현재 실행 스레드에서 다음 실행예정 스레드에게 넘기게 합니다.

2.4 next_thread_to_run()

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

• 역할: 다음 실행 예정 스레드의 리스트 요소로서의 주소값을 반환합니다.

3. 구현 코드

3.1 구현방법

ready_list에 priority 순서에 맞춰서 push 하는 방법과 정렬되지 않은 리스트에서 priority 가 가장 높은 스레드를 찾아 pop을 하는 방법이 있습니다. 전자의 방법대로 구현하고자 했습니다.

3.2 도움이 될만한 함수들

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_insert()

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

요소를 리스트에 넣습니다.

3.3 thread_compare_priority() 구현

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

priority를 비교하는 함수입니다.

3.4 thread_unblock() 수정

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

list_push_back() 함수를 주석처리하고 list_insert_ordered()함수를 사용합니다.

3.5 thread_yield() 수정

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

3.6 thread_test_preemption() 수정

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

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

4. 테스트 결과

우선순위 스케줄링과 관련하여 다른 테스트들도 성공하려면 sempahhore, condition variable, donation에 대한 부분도 구현해야합니다.