[pintos] Project1:Threads - Priority Scheduling (1)

기존의 pintos의 경우 Round Robin 기법으로 priority에 상관없이 ready_list에 들어온 순서대로 프로세스들이 일정 시간동안 돌아가며 실행된다. 여기에 이제 priority를 고려해 priority가 높은 process부터 일정 시간동안 실행될 수 있도록 Priority Scheduling을 추가할 예정이다.

핀토스 메뉴얼에 따르면 Priority Scheduling을 위해 구현해야 할 내용은 아래와 같다.

1. priority preemptive scheduling
2. lock, semaphore, condition variable에서 깨어날 때 priority가 제일 높은 thread가 먼저 깨어나야 함
3. priority donation

priority preemptive scheduling

핀토스 메뉴얼에 따르면 새로운 thread가 ready_list에 추가될 때 currently running thread보다 priority가 높을 경우, 새로운 thread가 실행될 수 있도록 해야 한다.

thread를 CPU에 할당하는 함수는 thread_yield() 함수인데 현재 실행중인 thread를 ready_list에 push하고 schedule() 함수를 실행하는 함수이다.

schedule() 함수는 next_thread_to_run() 함수를 실행해서 다음에 실행될 thread를 가져오고 swtich_threads(cur, next) 함수 실행을 통해 context switching을 진행한다.

이런 과정에서 priority가 제일 높은 thread를 ready_list에서 가져오는 방법은

1. ready_list에 thread가 push 될 때 priority가 높은 순서대로 insert될 수 있도록 하기
2. ready_list에서 thread를 pop해올 때 priority를 기준으로 pop 해오기

이렇게 두 가지 방법이 있다. 1의 방법으로 하면 기존의 list_pop_front 함수를 그대로 유지해도 되고 2의 방법을 쓰면 list_push_back 함수를 그대로 유지해도 된다. 물론 둘 다 해도 됨... 나는 1의 방법으로 구현하였다.

ready_list에 thread가 push back되는 경우는

1. thread_unblock()에서 THREAD_BLOCKED 상태의 thread가 ready_list에 들어가면서 THREAD_READY 상태가 될 때
2. thread_yield() 함수에서 현재 running 상태인 thread를 ready_list에 넣을 때

이렇게 두 가지가 있다.

lib/kernel/list.c의 list_insert_ordered (struct list *list, struct list_elem *elem, list_less_func *less, void *aux) 함수를 이용하면
priority 를 기준으로 sorting하면서 list에 insert하는 함수를 구현할 수 있다. 해당 함수는 인자로 넘어온 less 함수를 기준으로 elem을 list에 정렬 삽입하는 함수이다.

list_less_func 함수 설명을 살펴보면 $A<B$일 경우 True를 반환하는 오름차순 정렬 함수인데 우리는 priority 값을 기준으로 내림차순 정렬할 것이기 때문에 두 thread A,B의 priority에 대해 A의 priority가 더 클 경우 True를 반환하도록 less function thread_priority_compare(const struct list_elem *a, const struct list_elem *b, void *aux) 함수를 선언하였다.

bool 
thread_priority_compare (const struct list_elem *a, const struct list_elem *b, void *aux)
{
  struct thread *A = list_entry(a, struct thread, elem);
  struct thread *B = list_entry(b, struct thread, elem);

  if (A->priority > B->priority) return true;
  return false;
}

그리고 나서 thread_unblock()와 thread_yield()를 아래와 같이 바꿔주었다.

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_insert_ordered (&ready_list, &t->elem, thread_priority_compare, NULL);
  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_insert_ordered (&ready_list, &cur->elem, thread_priority_compare, NULL);
  cur->status = THREAD_READY;
  schedule ();
  intr_set_level (old_level);
}

추가로 schedule() 함수를 보면 next_thread_to_run() 함수를 통해 다음에 실행할 thread를 가져오는데 이때 중간에 prority가 바뀔 수도 있기 때문에 list_sort() 함수를 실행해 한 번 정렬해주고 list_pop_front()를 실행해주었다.

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

thread_create() 수정

thread를 priority 기준으로 내림차순 정렬해 ready_list에 넣어줬으니 이제 priority preemptive scheduling을 구현할 차례이다. 해당 scheduling은 ready_list에 들어오는 thread가 생기거나 현재 running thread의 priority가 바뀔 때 실행되어야 한다.

먼저 priority_preemptive_check() 함수를 아래와 같이 구현해 ready_list의 바로 앞 thread와 thread_current()의 priority를 비교해 ready_list의 바로 앞 thread의 priority가 더 크면 thread_yield() 함수가 실행되도록 하였다.

void 
priority_preemptive_check(void)
{
  if(thread_current()->priority < list_entry(list_begin(&ready_list), struct thread, elem)->priority)
    thread_yield();
}

thread_create()에서 thread_unblock(t) 를 통해 새로운 thread t가 ready_list에 삽입되었으므로 thread_unblock(t) 뒤에 priority_preemptive_check() 함수를 실행시켜주었다.

tid_t
thread_create (const char *name, int priority,
               thread_func *function, void *aux) 
{
  struct thread *t;
  struct kernel_thread_frame *kf;
  struct switch_entry_frame *ef;
  struct switch_threads_frame *sf;
  tid_t tid;

 // ...

  /* Add to run queue. */
  thread_unblock (t);

  // prj1
  priority_preemptive_check();

  return tid;
}

thread_set_priority() 수정

thread_create()와 마찬가지로 새 priority를 thread_current()의 priority로 할당한 뒤, priority_preemptive_check() 함수를 실행시켜주었다.

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

lock, semaphore, condition variable에서 priority scheduling

lock, semaphore, condition variable에서 thread를 깨울 때도 잠들어 있는 thread들 중 priority가 높은 thread를 깨워주어야 한다. 위의 preemptive scheduling 구현과 마찬가지로 watier에 thread를 넣을 때 list_insert_ordered (struct list *list, struct list_elem *elem, list_less_func *less, void *aux) 함수를 이용해 prioirty 기준으로 내림차순 정렬해주었다.

semaphore, lock

semaphore와 lock의 경우 sema_down() 함수를 이용해 semaphore 구조체의 waiter 변수에 thread를 push back 하므로 sema_down() 함수의 list_push_back(&sema->waiters, &thread_current ()->elem) 부분을 아래와 같이 바꾸어 주었다.

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_insert_ordered (&sema->waiters, &thread_current ()->elem, thread_priority_compare, NULL);
      thread_block ();
    }
  sema->value--;
  intr_set_level (old_level);
}

sema_up()에서 중간에 리스트 안의 thread들의 priority가 바뀌었을 수도 있으므로 list_sort()를 실행해주고 list_pop_front() 함수를 실행해주었다.

void
sema_up (struct semaphore *sema) 
{
  enum intr_level old_level;
  struct thread *t = NULL;

  ASSERT (sema != NULL);

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

  sema->value++;

  priority_preemptive_check();

  intr_set_level (old_level);
}

또한 ready_list에 추가되는 thread의 priority가 thread_current()보다 높을 수 있기 때문에 priority_preemptive_check() 함수도 추가로 실행해주었다.

condition variable

condition variable의 경우 기존의 cond_wait()함수를 보면 인자로 넘어온 conditional varialbe cond의 waiter 리스트에 semaphore_elem waiter를 push하는데 waiter 리스트에 속한 semaphore들의 waiter 리스트에는 thread가 priority 값 내림차순으로 정렬되어 있기 때문에 semaphore를 priority 기준으로 insert할 때 semaphore의 waiter 리스트의 제일 앞 thread 기준으로 priority를 비교하여 insert 될 수 있도록 비교함수를 구현하였다.

bool 
sema_priority_compare (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{
  struct semaphore_elem *A = list_entry(a, struct semaphore_elem, elem);
  struct semaphore_elem *B = list_entry(b, struct semaphore_elem, elem);

  struct thread *A_thread = list_entry(list_begin(&((A->semaphore).waiters)), struct thread, elem);
  struct thread *B_thread = list_entry(list_begin(&((B->semaphore).waiters)), struct thread, elem);

  if (A_thread->priority > B_thread->priority) return true;
  return false;
}

condition variable은 구조가 struct semaphore_elem에 포함된 struct list_elem elem을 list element로 갖는 struct list waiters를 멤버 변수로 갖는 struct condition으로 이뤄져 있고 비교는 struct semaphore_elem에 있는 멤버 변수 struct semaphore semaphore의 waiters의 첫번째 element가 가지는 thread의 priority로 이루어져야 하기 때문에 위와 같이 비교함수를 작성할 수 있다.

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

conda_wait() 함수에 list_push_back() 대신 list_insert_ordered() 함수를 넣어주었고 conda_signal() 함수는 중간에 리스트 안의 thread들이 바뀌거나 thread의 priority가 바뀌었을 수도 있으므로 list_sort() 함수를 실행하고 list_pop_front()가 실행될 수 있도록 함수를 변경해주었다.

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_priority_compare, NULL);
    sema_up (&list_entry (list_pop_front (&cond->waiters),
                          struct semaphore_elem, elem)->semaphore);
  } 

}

개발로그

thread_set_priority() 놓침

처음에 짜고 테스트를 돌렸을 때 'priority-change' test가 fail이 떠서 해당 테스트 파일을 들어가보니까 thread_set_priority()함수를 발견했다.. 현재 thread의 priority가 바뀌어서 더 작아질 경우에도 thread_yield()를 실행해줬어야 했는데 thread_create() 부분만 생각하고 이걸 생각 못했다.

void
thread_set_priority (int new_priority) 
{
  thread_current ()->priority = new_priority;
  if(new_priority < list_entry (list_begin(&ready_list), struct thread, elem)->priority)
    thread_yield();
}

'priority-sema' test 통과시키기

thread를 깨우기 위해 waiter 리스트에서 list_front_pop()을 해올 때 priority가 제일 큰 thread가 앞에 있으면 되는 것만 생각해서 단순히 sema_down() 함수에서 list_push_back() 함수를 list_insert_ordered() 함수로 바꿨는데 'priority-sema' 테스트가 계속 fail이 뜨는 것이다. 그래서 생각해보니까 깨운 thread가 현재 thread보다 priority가 높으면 깨운 thread가 running thread로 바뀌어야 하는데 그렇게 해주는 장치가 없었다...
그래서 처음에는 thread_unblock() 함수 안에 인자로 넘어온 sturct thread *t의 priority가 thread_current()->priority보다 크면 thread_yield()를 실행할 수 있도록 코드를 짜고 thread_create() 함수 안에 추가했던 preemptive 파트를 지웠는데 그냥.. 실행이 안됐다.. 그래서 thread_create()에서 thread_unblock()을 실행하고, 인자로 넘어온 priority가 thread_current()->priority보다 크면 thread_yield()를 실행했던 것처럼 sema_up()에도 thread_unblock()을 통해 ready_list에 thread를 넣고 sema->value++까지 실행하고 난 뒤, ready_list에 추가되는 thread가 thread_current()->priority보다 크면 thread_yield()를 실행될 수 있도록 코드를 짰다.

void
sema_up (struct semaphore *sema) 
{
  enum intr_level old_level;
  struct thread *t = NULL;

  ASSERT (sema != NULL);

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

  sema->value++;

  if(t!= NULL && t->priority > thread_current()->priority) thread_yield();

  intr_set_level (old_level);
}

priority preemptive check가 필요한 부분 하나의 함수로 통일하기

위의 삽질을 통해 생각해보니 preemptive check가 필요한 부분들에 대해 하나의 함수로 통일해서 앞으로 편하게 다뤄야겠다는 생각을 했다. 그래서 위처럼 priority_preemptive_check() 함수를 만들어서 필요한 부분에 해당 함수를 호출하였다.

'priority-condvar' test 통과하기

위에 test log를 보면 초반에 thread가 깨어나는게 굉장히 이상한데 왜 그런지 여기저기 검색도 해보고 생각해보니 semaphore 안에는 여러 thread가 존재하고 그 안에서 thread가 추가되고 삭제되고 하면서 semaphore들을 가장 앞 thread 기준 priority로 정렬 삽입해도 중간에 순서가 바뀔 수도 있는 가능성이 존재했다. 그래서 cond_signal()에 list_sort()함수를 넣어 한 번 정렬해주고 가장 앞 thread를 뽑아왔다. 그 김에 thread를 뽑아오는 sema_up()이나 next_thread_to_run()에도 list_sort() 함수를 추가해주었다. 사실상.. insert, pop 둘 다 고려해 코드를 짠...

Alarm Clock, Priority Scheduling(1) 결과

Priority Scheduling은 priority donation만 남았다..