[SW 정글 59일차] Pintos Project 1. Priority Scheduling

오늘부터 PintOs project 1. Priority Scheduling 구현에 들어가기 시작했다.

일단은 https://casys-kaist.github.io/pintos-kaist/에 설명되어있는 우리가 해결해야할 과제를 파악했다.

 

 

 

1. 내가 해야할 것은?

기존의 Pintos의 스케쥴링 방식은 아래와 같다.

새로운 스레드가 생성되거나 running 혹은 blocked 상태에서 ready 상태로 전이될 때, 스레드들은 ready_list에 담겨 CPU 선점을 기다린다.

여기서, ready_list에 삽입하는 기준은 따로 없고 그냥 맨 뒤에 넣어준다.

즉, Round Robin 스케쥴링을 사용하는 것이다.

 

그래서 Project1의 2번째 과제로 다른 스레드보다 빨리 CPU를 선점해야하는 스레드를 먼저 선점할 수 있도록 해주기 위해 각 스레드마다 우선순위를 주고 우선순위가 높은 순서대로 CPU를 선점할 수 있게 해주는 Priority Scheduling을 구현하는 것이다.

 

Priority Scheduling을 구현하기 위해 ready_list를 수정하는 것 뿐만 아니라 semaphore, lock 등 synchroinzation preemitive에서 사용되는 ready queue도 수정해주어야한다.

 

 

 

2. 과제 구현

1) ready list Priority Scheduling 구현

일단은 현재 어떠한 상태인지 기존 코드를 보면서 얘기해보자.

/* 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);
	// change list push func because of implementing priority scheduling
	list_push_back (&ready_list, &t->elem);
	t->status = THREAD_READY;
	intr_set_level (old_level);
    

void
thread_yield (void) {
	struct thread *curr = thread_current ();
	enum intr_level old_level;

	ASSERT (!intr_context ());

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

우리가 ready_list에 스레드를 넣어주는 경우는 unblock하는 경우와 yield하는 경우이다.

여기서는 단순히 ready_list의 마지막 부분에 push하는 것으로 구현이 되어있다.

그리고 ready 상태인 스레드 중 running 상태인 스레드로 바꾸기 위해서 ready_list의 맨 앞 스레드를 가지고 나오는 구조로 되어있다.

이 말은 schedule 함수를 보면 이해할 수 있다.

여기서 priority scheduling으로 구현하기 위해서는 ready_list안의 스레드를 우선순위를 기준으로 내림차순 정렬이 된 상태로 만들어주면 되는 것이다.

 

구현하는 방법은 2가지가 있다.

ready_list에 push 할 때 priority 순서에 맞추어 push 하는 방법

ready_list에서 pop 할 때 priority가 가장 높은 스레드를 찾아 pop 하는 방법

 

나는 첫번째 방법으로 구현을 했다.

일단은 pintos에서 제공되는 함수 중에 값을 비교하여 리스트에 넣어주는 기능을 하는 함수가 있는지 찾아보았는데 아래와 같은 함수가 있었다.

/* 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_ordered라는 함수가 있었는데 priority 기준으로 내림차순으로 정렬된 상태를 유지하기 위해서는 적합하지 않은 함수이다.

그 이유는 less라는 define된 함수를 사용하여 대소비교를 하는데 이 함수는 인자를 struct lst_elem으로 받는다.

그래서 우리가 진짜 비교해야할 값은 priority, 즉 int형이므로 적합하지않다.

 

이를 해결하기 위해 아래와 같은 새로운 함수를 만들어줘야한다.

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

두 개의 struct list_elem형 포인터 인자를 받아 priority를 찾아서 대소비교의 결과를 boolean type으로 반환해준다.

그러면 이제 이 함수와 ilst_insert_oredered를 사용하여 thread_unblock함수와 thread_yield 함수를 바꿔주면된다.

 

여기서 추가로 해주어야할 일이 있다.

현재 실행 중인 running 상태 스레드의 priority가 바뀌는 순간이 존재한다.

상식적으로는 이해가 안되겠지만 내일 구현할 donation이 이루어지면 바뀔 수 있고 이외의 경우가 있을 수 있다.

현재 running 상태인 스레드의 priority가 바뀌는 순간은 thread_create()가 호출되었을 때와 thread_set_priority()가 호출되었을 떄이다.

priority가 바뀐다면 ready_list에 존재하는 thread의 priority보다 작은 경우가 생길 수 있으므로 yield를 해주게 하는 함수를 정의해주고 이 함수를 thread_create()와 thread_set_priority()에 넣어주면 된다.

새로 생성한 함수는 아래와 같다.

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

 

 

2) synchronization primitives의 Priority Scheduling 구현

pintos에서 구현된 synchronization primitives는 lock, semaphore, condition variable 총 3가지이다.

condition variable도 priority scheduling을 구현하려고 했는데 아직 이해가 되지 않아 오늘은 일단 lock와 semaphore를 수정했다.

일단은 lock_init을 보면 아래와 같다.

/* Lock. */
struct lock {
	struct thread *holder;      /* Thread holding lock (for debugging). */
	struct semaphore semaphore; /* Binary semaphore controlling access. */
};


void
lock_init (struct lock *lock) {
	ASSERT (lock != NULL);

	lock->holder = NULL;
	sema_init (&lock->semaphore, 1);
}

lock 구조체를 보면 semaphore형 멤버를 가지고 있어서 사실은 semaphore의 value를 1로 init하여 binary semaphore를 이용한 거이다.

즉, semaphore만 수정하면 lock도 priority scheduling 구현이 된다.

 

semaphore를 구현한 함수들 중 sema_down과 sema_up함수를 보면 아래와 같다.

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);
      thread_block ();
    }
  sema->value--;
  intr_set_level (old_level);
}

void
sema_up (struct semaphore *sema) 
{
  enum intr_level old_level;

  ASSERT (sema != NULL);

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

sema_down은 critical section에 들어가기 위해 value가 0이면 들어가지 못하므로 wait_list에서 기다려야한다.

기존에 구현된 것을 보면 스레드를 그냥 wait_list의 마지막에 push를 해주고 있다.

그리고 sema_up을 보면 critical section에서 나온 스레드가 value를 1증가 시켜주고 wait_list에서 기다리는 스레드 중 맨 앞에 것을 unblocked시켜주어 ready상태로 만들어준다.

 

그려먼 이제 priority scheduling을 위해 바꿔주자.

여기서는 1) ready_list에서 구현한 것처럼 sema_down에서 push_back하는 것을 priority 기준으로 내림차순 정렬이 되도록 push해주게 코드를 바꾸면 된다.

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_compare_priority, 0);
		thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

 

그리고 sema_up에서는 unblock해주는 것은 list의 맨 앞 스레드 즉, 우선순위가 가장 높은 것이므로 기존의 코드가 맞다.

하지만, wait_list에 있으면서 스레드들의 우선순위가 바뀌었을 수도 있으므로 sort를 해주어야 한다.

sort를 해주는 것은 pintos에서 이미 구현이 되어있다.

list.c파일에 있는 list_sort()라는 함수인데 코드가 길어서 여기에는 쓰지 않겠다.

 

그리고 추가해주어야할 사항이 unblock된 스레드가 running 스레드보다 우선순위가 높을 수 있으므로 yield가 일어나게 해준다.

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++;
  thread_test_preemption ();
  intr_set_level (old_level);
}

thread_test_preemption()함수는 위 1)ready_list 설명 마지막 부분에 코드가 있다.

 

 

여기까지가 semaphore priority scheduling 구현과정이였다.

내일은 conditional variable 쪽을 수정하고 priority inversion을 해결해주는 방법인 priority donation을 구현하는 것이 목표이다.

---

[오늘의 나는 어땠을까?]

오늘은 priority scheduling 구현에 들어갔다.

일단은 2틀동안 개념을 공부하면서 shceduling에 대해 공부했기에 개념적으로 이해가 안되어 구현하는 것이 어렵다는 느낌은 없었다.

하지만, semaphore의 waiting도 priority scheduling을 따르기 위해 코드를 바꿔줬는데 counting semaphore에 대해 이해가 가지 않았다.

지금 pintos에서 주어지는 것은 binary semaphore만을 고려하기에 내가 이해가 되지 않는 것을 코드로 보며 해결을 할 수 없어 여러 자료들을 보면서 해결해야하는데 명확히 해결해줄 소스가 없다...

내일 권영진 교수님이 오셔서 강의를 해주시는데 질문할 시간이 있으면 꼭 물어봐야겠다.

좋은 질문을 해야 상대방이 의도를 명확히 알 수 있기에 질문을 잘 정리해놔야겠다.

이제서야 왜 pintos를 어려워하는지 이해가 됐다.

열심히 해보자.