ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Pintos] Project 1 : Thread(스레드) - Priority Scheduling(2)
    프로젝트/Pintos 2021. 4. 30. 09:23

    이번에는 동기화 도구들의 스케쥴링 방식을 살펴보자. 스케쥴링 도구들의 코드는 thread 폴더의 synch.h, synch.c 에 구현되어 있다. 우리가 다루어야 할 동기화 도구는 lock, semaphore, condition variable 3가지이다. 하나씩 살펴보자.

    /* thread/synch.h */
    struct semaphore 
      {
        unsigned value;             /* Current value. */
        struct list waiters;        /* List of waiting threads. */
      };
      
    struct lock 
      {
        struct thread *holder;      /* Thread holding lock (for debugging). */
        struct semaphore semaphore; /* Binary semaphore controlling access. */
      };
      
    struct condition 
      {
        struct list waiters;        /* List of waiting threads. */
      };

    semaphore 은 공유 자원의 개수를 나타내는 value 와 공유 자원을 사용하기 위해 대기하는 waiters 의 리스트를 가진다. lock 은 value = 1인 특별한 semaphore 로 구현되어 있고, 현재 lock 을 가지고 있는 thread 정보와 semaphore 를 멤버로 가진다. condition 은 condition variables 가 만족하기를 기다리는 waiters 의 리스트를 가진다.

     

    Semaphore

    semaphore 를 예로 들면, 하나의 공유자원을 사용하기 위해 여러 스레드가 sema_down 되어 대기하고 있다고 할 때, 이 공유자원을 사용하던 스레드가 공유자원의 사용을 마치고 sema_up 할 때 어떤 스레드가 가장 먼저 이 공유자원을 차지할 것인가에 대한 문제가 스케쥴링에서 해결해야 하는 것이다. 그럼 현재 어떻게 이루어져 있는지 코드를 살펴보자.

    /* thread/synch.c */
    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);
    }

    semaphore 를 다루는 함수는 sema_down, sema_up 두 가지이다. 공유 자원을 사용하고자 하는 스레드는 sema_down 을 실행하고, 사용 가능한 공유자원이 없다면 sema->waiters 리스트에 list_push_back 함수로 맨 뒤에 추가된다. 공유자원의 사용을 마친 스레드가 sema_up 을 하면 thread_unblock 을 하는데, list_pop_front 함수로 sema->waiters 리스트의 맨 앞에서 꺼내는 것을 볼 수 있다. 이전 포스트에서 봤던 ready_list 와 똑같이 리스트에 들어온 순서대로 차례로 실행되는 방식을 따르는 것을 알 수 있다. ready_list 에서 했던 것처럼 이번에도 priority 에 따라 자원을 할당받도록 만들어보자. 추가할 때는 priority 에 내림차순으로 리스트에 추가하고 꺼낼 때는 그대로 맨 앞에서 꺼내면 된다.

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

    while 문장 안에 있던 list_push_back 을 list_insert_ordered 을 사용하여 내림차순으로 정렬되도록 추가하였다. semaphore 에 추가되는 element 들은 스레드이므로 스레드에서 사용하였던 thread_compare_priority 함수를 그대로 사용하면 된다.

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

    sema_up 에서는 waiters 리스트에 있던 동안 우선순위에 변경이 생겼을 수도 있으므로 waiters 리스트를 내림차순으로 정렬하여 준다. <lib/kernel/list.c> 에 있는 list_sort 함수를 사용하면 간단하게 가능하다. 그 후 unblock 된 스레드가 running 스레드보다 우선순위가 높을 수 있으므로 thread_test_preemption () 함수를 실행하여 CPU 선점이 일어나게 해준다.

     

    이렇게 하면 semaphore 에 대한 작업은 끝이났다. 다음은 lock 의 구조를 살펴보자.

    /* thread/synch.c */
    void
    lock_acquire (struct lock *lock)
    {
      ASSERT (lock != NULL);
      ASSERT (!intr_context ());
      ASSERT (!lock_held_by_current_thread (lock));
    
      sema_down (&lock->semaphore);
      lock->holder = thread_current ();
    }
    
    void
    lock_release (struct lock *lock) 
    {
      ASSERT (lock != NULL);
      ASSERT (lock_held_by_current_thread (lock));
    
      lock->holder = NULL;
      sema_up (&lock->semaphore);
    }

    lock 을 다루는 두 함수를 살펴보면 알 수 있듯이 마지막이 sema_down, sema_up 으로 끝난다. 즉 lock 은 value = 1 이고, holder 정보를 가지고 있다는 것을 제외하고는 semaphore 와 동일하게 동작하기 때문에 sema_down, sema_up 을 이미 처리해주었으므로 lock 은 따로 처리해 줄 필요가 없다는 것을 알 수 있다.

    Condition variables

    우선 condition variables 을 다루는 cond_wait, cond_signal 함수를 살펴보자.

    /* thread/synch.c */
    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_push_back (&cond->waiters, &waiter.elem);
      lock_release (lock);
      sema_down (&waiter.semaphore);
      lock_acquire (lock);
    }
    
    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))
      {
        sema_up (&list_entry (list_pop_front (&cond->waiters),
                              struct semaphore_elem, elem)->semaphore);
      }
    }

    condition variables 도 마찬가지로 waiters 리스트를 가지고 있는데, semaphore 와 다른 점이 하나가 있다. semaphore 는 waiters 가 스레드들의 리스트였다면 condition variables 의 waiters 는 세마포들의 리스트라는 점이다. cond_wait 함수의 list_push_back 부분을 보면 알 수 있는데, cond->waiters 리스트에 waiter.elem 을 추가하는데 여기서 waiter 는 함수의 맨 위에서 선언한 세마포 element 이다. 이 점을 유의하면서 진행하여 보자. 이 condition variables 에 묶여있는 여러 세마포들의 리스트 중에서 가장 우선순위가 높은 하나의 세마포를 깨워야 하는데, 이미 각 세마포의 waiters 리스트는 위의 세마포를 다루는 함수에서 내림차순으로 정렬되게 하였으므로 각 세마포의 waiters 리스트의 맨 앞의 element 가 각 세마포에서 가장 priority 가 큰 스레드이고 이들을 비교하여 가장 큰 priority 를 가진 스레드를 가진 세마포를 깨우면 된다.

     

    여기서도 마찬가지로 list_push_back 함수를 list_insert_ordered 로 바꾸어주는 것이 거의 전부이다. 이번에는 입력받는 파라미터가 스레드가 아니라 semaphore_elem.elem 로 들어오기 때문에 thread_compare_priority 함수는 사용하지 못하고, semaphore_elem 가 나타내는 세마포의 waiters 리스트의 맨 앞 thread 끼리 priority 를 비교하는 함수가 필요하다. (semaphore_elem 구조체는 synch.c 에 선언되어 있다.)

    /* thread/synch.c */
    bool 
    sema_compare_priority (const struct list_elem *l, const struct list_elem *s, void *aux UNUSED)
    {
    	struct semaphore_elem *l_sema = list_entry (l, struct semaphore_elem, elem);
    	struct semaphore_elem *s_sema = list_entry (s, struct semaphore_elem, elem);
    
    	struct list *waiter_l_sema = &(l_sema->semaphore.waiters);
    	struct list *waiter_s_sema = &(s_sema->semaphore.waiters);
    
    	return list_entry (list_begin (waiter_l_sema), struct thread, elem)->priority
    		 > list_entry (list_begin (waiter_s_sema), struct thread, elem)->priority;
    }

    semaphore_elem.elem 을 입력받으면 list_entry 로 semaphore_elem 구조체를 구하여 저장하고 이 구조체가 가지는 semaphore 의 waiters 리스트를 받아온다. 이 waiters 리스트의 맨 앞 element 스레드의 priority 끼리 비교하여 반환하면 된다. 얼핏 복잡해 보이지만 천천히 따라가며 이해해보길 바란다.

     

    비교함수를 만들었으니 cond_wait 를 완성할 수 있다.

    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_compare_priority, 0);
      lock_release (lock);
      sema_down (&waiter.semaphore);
      lock_acquire (lock);
    }

    list_push_back 대신에 list_insert_ordered 함수에 sema_compare_priority 를 사용해서 가장 높은 priority 를 가지는 스레드가 묶어있는 세마포가 가장 앞으로 오도록 내림차순으로 cond->waiters 리스트에 push 한다.

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

    깨울 때도 마찬가지로, wait 도중에 priority 가 바뀌었을 수 있으니 list_sort 로 내림차순으로 정렬해주고, sema_up 은 그대로 맨 앞에서 꺼내도록 둔다.

     

    결과

    2개의 테스트를 더 통과한 것을 볼 수 있다. 방금 우리가 구현한 priority-sema, priority-condvar 가 pass 가 나왔다. FAIL 의 숫자가 빠르게 줄어가는 것이 보기 좋다. 다음 시간에는 priority-donate 문제를 풀어보도록 한다.

Designed by Tistory.