[week08] PintOS - Project 1(thread) : Priority Scheduling(1)

Project1: priority schedule(1)

문제

현재 PintOS는 scheduling을 어떻게 하고 있을까?

앞선 포스트에서 살펴보았듯이, 현재 PintOS는 Round-Robin방식을 채택하고 있다.

할당된 시간 4 tick이 지나면 running thread는 다른 thread에게 선점당한다.

PintOS는 새로운 thread를 ready_list에 넣을 때 항상 맨 뒤에 넣는다.

그리고 ready_list에서 다음 CPU 할당할 thread를 찾을 때에는 항상 맨 앞에서 꺼낸다.

이 방식은 thread들 간의 우선순위 없이 ready_list에 들어온 순서대로 실행된다.

제대로 된 우선순위 scheduling이 이루어지지 않고 있다!

해결책

우선순위에 따라 scheduling을 하도록 바꿔야 한다.

우선순위에 따라 scheduling 한다는 의미를 코드로 자세하게 구현해보면 지금 running하고 있는 thread의 우선순위가 항상 제일 높아야 하고, ready_list에는 우선순위가 높은 순서대로 정렬이 되어 있어야 한다.

ready_list에 thread를 집어넣을 때 priority 순서에 맞추어 내림차순으로 정렬되도록 삽입하는 방식으로 구현해보자(ready_list에서 thread를 뺄 때는 맨 앞에서부터 빼기 때문에).

그럼 ready_list에 thread를 삽입하는 함수를 변경해야 한다.

그 함수들은 thread_unblock(), thread_yield() 함수다.

그 전에 lib/kernel/list.c에 있는 list_insert_ordered() 함수를 살펴보자. 왜냐하면 이 함수가 내림차순으로 정렬하면서 insert하는데 유용하게 쓰인다.

// lib/kernel/list.c

// 이 함수로 insert를 진행하게 되면 priority schedule을 해결할 수 있다!
// insert할 list, element, less라는 비교함수를 인자로 받음
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))     // less함수가 true가 되면
            break;                 // 멈춘다
    return list_insert(e, elem); // e를 elem 앞에 insert함
}

이 함수에서 less 인자에서는 비교를 진행하는 함수를 받는다.

그러니까 비교 함수를 만들어 보자.

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

이 함수를 적용해서 ready_list에 맨 뒤에 push하던 함수를 list_insert_ordered()로 바꿔주자

// 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);
    // project1: priority schedule
    list_insert_ordered(&ready_list, &t->elem, thread_compare_priority, 0);
    t->status = THREAD_READY; // thread의 status를 ready로 변경
    intr_set_level(old_level);
}

void thread_yield(void)
{
    struct thread *curr = thread_current(); // 현재 thread를 curr이라는 thread 구조체에 넣음
    enum intr_level old_level;

    ASSERT(!intr_context());
    // 인터럽트 끔 - kernel thread를 사용하는 중에 외부 인터럽트 처리기의 interrupt 막기위해
    old_level = intr_disable();
    if (curr != idle_thread) // 현재 thread가 idle thread가 아니면
        // list_push_back(&ready_list, &curr->elem); // ready_list의 맨 끝에 curr.elem을 넣음
        // project1: priority schedule
        // ready_list를 priority 기준 내림차순으로 정렬시킴
        list_insert_ordered(&ready_list, &curr->elem, thread_compare_priority, 0);
    do_schedule(THREAD_READY);
    intr_set_level(old_level); // 인자로 전달된 인터럽트 상태로 인터럽트를 설정하고 이전 인터럽트 상태를 반환
}

우리는 지금까지 ready_list에 삽입하는 방식만 변경해 주었다. 이렇게만 하면 맨 앞에서 설명한 우선순위에 따라 scheduling 하는 것일까?

아니다! 조금 더 생각해 볼 부분이 있다.

running thread가 가장 높은 priority를 가지는 것을 보장하지 못하는 경우가 생긴다.

• 새로운 thread가 생겨서 그 thread의 priority가 현재 running하고 있는 thread보다 우선순위가 높아질 때 ( thread_create() )
• thread의 priority가 변경될 때 ( thread_set_priority() )

두 경우 마지막에 running thread와 비교를 통해 우선순위가 더 높다면 선점(preemption)을 할 수 있게 함수를 추가해 줘야 한다.

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

preemption() 코드를 마지막에 추가해주자.

tid_t thread_create(const char *name, int priority,
                    thread_func *function, void *aux)
{
    struct thread *t;
    tid_t tid;

 ...

    /* Add to ready_list. */
    thread_unblock(t);
    // project1 : priority schedule
    thread_test_preemption(); //우선순위 비교해서 더 높으면 CPU 양보
    return tid;
}

void thread_set_priority(int new_priority)
{
    thread_current()->priority = new_priority;
    // project1 : priority schedule
    thread_test_preemption(); // priority가 변경되었으니까 우선순위 변경 확인
}

참고자료

[Pintos] Project 1 : Thread(스레드) - Priority Scheduling(1)