[Pintos-KAIST] Project 1 :: Priority Scheduling

 

Priority Scheduling

💡 우선순위가 높은 스레드가 먼저 CPU를 점유할 수 있도록 Priority Scheduling을 구현한다.

 

Priority Scheduling 구현사항

• 스레드들은 각 우선순위에 따라 ready list에 추가된다.
• 현재 실행 중인 스레드의 우선순위보다 높은 우선순위의 스레드가 ready list에 추가되면, 현재 실행 중인 스레드는 바로 CPU를 양도한다.
• 스레드는 언제든지 자신의 우선순위를 변경할 수 있다.
  • 우선순위를 낮추어 더이상 가장 높은 우선순위가 아니게 된다면, 즉시 CPU를 양도한다.
• lock, semaphore, condition variable을 사용하여 대기하고 있는 스레드가 여러 개인 경우, 우선순위가 가장 높은 스레드가 먼저 깨어나야 한다.

 

구현하기

(1) ready_list 정렬

thread_yield, thread_unblock

• ready_list에 스레드를 삽입할 때 priority가 높은 스레드가 앞부분에 위치하도록 정렬한다.
  • 기존에는 list_push_back을 사용해 FIFO 방식으로 삽입되고 있었다.
  • list_insert_ordered를 활용한다.
  • 정렬에 활용할 cmp_thread_priority() 함수는 아래에서 새로 선언한다.

/* thread.c */

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_insert_ordered(&ready_list, &curr->elem, cmp_thread_priority, NULL);

    do_schedule(THREAD_READY);
    intr_set_level(old_level);
}

/* 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_insert_ordered(&ready_list, &t->elem, cmp_thread_priority, NULL);

    t->status = THREAD_READY;
    intr_set_level(old_level);
}

cmp_thread_priority

• ready_list에 priority가 높은 스레드가 앞부분에 위치하도록 정렬할 때 사용할 정렬 함수를 새로 선언한다.

/* thread.h */

bool cmp_thread_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED);

/* thread.c */

bool cmp_thread_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{
    struct thread *st_a = list_entry(a, struct thread, elem);
    struct thread *st_b = list_entry(b, struct thread, elem);
    return st_a->priority > st_b->priority;
}

 

(2) Preempt

thread_create, thread_wakeup

• ready_list에 스레드가 삽입되고 나면, 현재 실행중인 스레드와 ready_list에 있는 스레드의 priority를 비교한다.
• priority가 더 높은 스레드가 ready_list에 있다면 즉시 CPU를 양보한다. ( preempt_priority() 호출 )
  • 양보 여부를 확인하고 양보하는 preempt_priority() 함수는 아래에서 새로 선언한다.

/* thread.c */

tid_t thread_create(const char *name, int priority,
                    thread_func *function, void *aux)
{

...

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

    return tid;
}

/* thread.c */

void thread_wakeup(int64_t current_ticks)
{
    enum intr_level old_level;
    old_level = intr_disable(); // 인터럽트 비활성

    struct list_elem *curr_elem = list_begin(&sleep_list);
    while (curr_elem != list_end(&sleep_list))
    {
        struct thread *curr_thread = list_entry(curr_elem, struct thread, elem); // 현재 검사중인 elem의 스레드

        if (current_ticks >= curr_thread->wakeup_ticks) // 깰 시간이 됐으면
        {
            curr_elem = list_remove(curr_elem); // sleep_list에서 제거, curr_elem에는 다음 elem이 담김
            thread_unblock(curr_thread);        // ready_list로 이동
            preempt_priority();
        }
        else
            break;
    }
    intr_set_level(old_level); // 인터럽트 상태를 원래 상태로 변경
}

 

thread_set_priority

• 실행중인 thread의 priority를 변경되므로 ready_list에 있는 스레드보다 priority와 비교하여 현재 변경된 priority가 더 낮다면, 즉시 CPU를 양보한다. ( preempt_priority() 호출 )

/* thread.c */

void thread_set_priority(int new_priority)
{
    thread_current()->init_priority = new_priority;
    preempt_priority();
}

 

preempt_priority

• ready_list에 있는 스레드의 priority가 현재 실행중인 스레드의 priority보다 높으면 양보하는 함수를 새로 선언한다.
  • ready_list는 priority를 기준으로 내림차순 정렬되므로, 가장 앞에 있는 스레드만 검사하면 된다.

/* thread.h */

void preempt_priority(void);

/* thread.c */

void preempt_priority(void)
{
    if (thread_current() == idle_thread)
        return;
    if (list_empty(&ready_list))
        return;
    struct thread *curr = thread_current();
    struct thread *ready = list_entry(list_front(&ready_list), struct thread, elem);
    if (curr->priority < ready->priority) // ready_list에 현재 실행중인 스레드보다 우선순위가 높은 스레드가 있으면
        thread_yield();
}

 

Test - Priority 1

/* Test: /threads에서 입력 */

make check

👇🏻 구현 전

👇🏻 구현 후

priority 관련 테스트 4개를 더 통과했다!

 

(3) Lock Waiters 정렬

• lock, semaphore, condition variable을 기다리며 대기하고 있는 스레드가 여러 개인 경우, lock을 획득할 수 있어졌을 때 priority가 가장 높은 스레드가 먼저 깨어나야 한다.
  • lock의 대기자 목록인 waiters도 priority 기준으로 내림차순 정렬로 변경한다.
• 💡 semaphore
  • 세마포어는 양의 정수값과 두 개의 연산자(P와 V)로 구성된 동기화 기법이다.
  • "Down" 또는 "P"
    • 세마포어를 획득하기 위해(공유 자원에 접근하려 할 때) 호출한다.
    • 획득하면 세마포어를 획득했다는 의미로 value를 1 감소시킨다.
    • 세마포어를 획득할 때까지(value가 양수가 될 때까지) 기다린다.(블록된다.)
    • 세마포어를 바로 획득할 수 없을 때는 스레드가 기다리게 되는데(블록됨),
      기다리는 동안(블록되어 있는 동안)에는 다른 스레드가 세마포어를 먼저 해제(UP)하고 나서, 이를 기다리는 스레드가 실행되게 된다.
  • "UP" 또는 "V"
    • 세마포어를 반환할 때(공유 자원 사용을 완료했을 때) 호출한다.
    • 대기 중인 스레드 중 하나를 깨워주고, 세마포어의 value를 반환했다는 의미로 1 증가시킨다.

 

sema_down , cond_wait

• waiters에 스레드를 삽입할 때 priority가 높은 스레드가 앞부분에 위치하도록 정렬한다.
  • list_insert_ordered를 활용한다.
  • sema→waiters를 정렬할 때 사용하는 cmp_thread_priority 함수는 ready_list를 정렬할 때 사용한 함수를 그대로 사용한다.
  • cond→waiters를 정렬할 때 사용하는 cmp_sema_priority 함수는 아래에서 새로 선언한다.

/* 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) // 세마포어 값이 0인 경우, 세마포어 값이 양수가 될 때까지 대기
    {
        list_insert_ordered(&sema->waiters, &thread_current()->elem, cmp_thread_priority, NULL);
        thread_block(); // 스레드는 대기 상태에 들어감
    }
    sema->value--; // 세마포어 값이 양수가 되면, 세마포어 값을 1 감소
    intr_set_level(old_level);
}

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

 

cmp_sema_priority

• cond→waiters를 정렬할 때 사용할 함수를 새로 선언한다.
  • 인자로 전달되는 elem으로 바로 스레드에 접근할 수 없기 때문에, 이전의 cmp_thread_priority를 쓸 수 없어서 새로 선언해야 한다!
• 두 semahore 안의 'waiters 중 제일 높은 priority'를 비교해서 높으면 true를 반환하는 함수

/* thread.h */

bool cmp_sema_priority(const struct list_elem *a, const struct list_elem *b, void *aux);

/* synch.c */

bool cmp_sema_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{
    struct semaphore_elem *sema_a = list_entry(a, struct semaphore_elem, elem);
    struct semaphore_elem *sema_b = list_entry(b, struct semaphore_elem, elem);

    struct list *waiters_a = &(sema_a->semaphore.waiters);
    struct list *waiters_b = &(sema_b->semaphore.waiters);

    struct thread *root_a = list_entry(list_begin(waiters_a), struct thread, elem);
    struct thread *root_b = list_entry(list_begin(waiters_b), struct thread, elem);

    return root_a->priority > root_b->priority;
}

 

sema_up , cond_signal

• waiters에서 스레드를 깨우기 전에 waiters 목록을 다시 한 번 정렬한다.
  • waiters에 들어있는 스레드가 donate를 받아 우선순위가 달라졌을 수 있기 때문이다.
• sema_up에서는 unblock() 함수가 호출되면서 ready_list에 스레드가 삽입되므로, priority가 더 높은 스레드가 ready_list에 있다면 즉시 CPU를 양보한다. ( preempt_priority() 호출 )

/* synch.c */

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

    ASSERT(sema != NULL);

    old_level = intr_disable();
    if (!list_empty(&sema->waiters)) // 대기 중인 스레드를 깨움
    {
        // waiters에 들어있는 스레드가 donate를 받아 우선순위가 달라졌을 수 있기 때문에 재정렬
        list_sort(&sema->waiters, cmp_thread_priority, NULL);
        thread_unblock(list_entry(list_pop_front(&sema->waiters), struct thread, elem));
    }
    sema->value++;
    preempt_priority(); // unblock이 호출되며 ready_list가 수정되었으므로 선점 여부 확인
    intr_set_level(old_level);
}

/* synch.c */

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

 

Test - Priority 2

/* Test: /threads에서 입력 */

make check

👇🏻 구현 전

👇🏻 구현 후

priority - sema, condvar 테스트 2개를 더 통과했다!