210203 개발일지(58일차) - 운영체제(OS) 프로젝트 #1-3 : Priority Scheduling 개념 및 구현

pintOS 프로젝트 중 #1은 스레드와 관련된 과제다. 앞에서 Alarm Clock 과제를 진행했고, 남은 #1과제에서는 Priority Scheduling과 관련된 과제를 순서대로 진행할 것이다.

앞 포스팅에서 살펴본, 스케쥴링에 대해 시간순으로 하는 것이 아니라 우선순위 별로 진행할 수 있도록 짜는 것이 목표다.

Priority Scheduling

개념

앞에서 살펴본 그림에서 처럼, cpu에서 running할 스레드는 ready_list에 순서대로 놓여있었다. 이제 ready_list 안에 배치되는 스레드들에 대해 우선순위를 설정하고, 우선순위 순으로 정렬되어 대기할 수 있도록 구현해보자. 그러면 자연스레 우선순위 가 높은 스레드 순서대로 running될 것이다.

구현하기

0. 아래 함수 및 변수들을 각 c파일과 h파일에 추가해줘야 한다.

1. 먼저 ready_list안에 스레드들이 우선순위 순으로 정렬되도록 하기 위해 핀토스 내장 함수인 list_insert_ordered 함수를 사용하면 된다. 이 때 세 번째 인자인 함수가 필요한데, 함수 cmp_priority()를 를 만들어야 한다.

bool
cmp_priority (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED){
    int priority_a = list_entry(a, struct thread, elem)->priority;
    int priority_b = list_entry(b, struct thread, elem)->priority;
    return (priority_a > priority_b);
}

2. thread가 unblock(ready_list에 넣는 과정)될 때, 우선순위 순으로 ready_list가 정렬될 수 있도록 함수 thread_unblock()를 수정한다.

voidthread_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_priority, NULL);        
    // list_push_back (&ready_list, &t->elem); 기존에 구현 돼 있었던 걸 수정해야 한다.

    t->status = THREAD_READY;
    intr_set_level (old_level);     // thread_create에서 unblock시켜주고.. idle thread가 cpu를 점유할 수 있게 해준다??
}

3. 2번에서와 마찬가지로 ready_list에 들어가는 단계가 있는 함수 thread_yield()를 바꿔준다.

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_priority, NULL);     // 2번에서와 마찬가지로 수정
    do_schedule (THREAD_READY);
    intr_set_level (old_level);
}

4. 새로 스레드가 만들어지는 함수 thread_create()를 내부에 내용을 추가해준다. 새로 만들어진 스레드의 우선순위가 기존에 running중인 스레드보다 높을 수 있기 때문이다.

tid_t thread_create (const char *name, int priority, thread_func *function, void *aux) {
...
    thread_unblock(t);
   
    // (thread_unblock 함수 아래)
    // 아래 내용을 추가 : 새로 만들어진 스레드의 우선순위가 높을 수 있으므로!
    int curr_priority = thread_get_priority();
    if (priority > curr_priority){
        thread_yield();         
    }

5. 핀토스 내부 함수에는 running중인 thread의 우선순위(priority)를 수정해주는 함수 thread_set_priority()가 있다. 이 것도 수정해줘야 한다. 그 이유는 새로운 thread에 우선순위가 ready_list의 첫 thread의 우선순위보다 작아진다면, running thread를 바꿔줘야하기 때문이다. → 6번에서 test_max_priority()함수 구현

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

    // 여기에 아래서 구현할 test_max_priority() 함수를 넣어준다.
    test_max_priority();
}

6. 5번에서 설명한 test_max_priority() 함수를 구현해보자.

void test_max_priority (void){
    if (! list_empty(&ready_list)){
        struct thread *king_ready = list_entry(list_front(&ready_list), struct thread, elem);
        if( thread_get_priority() < king_ready ->priority){
            thread_yield();
        }
    }
}

다음 포스팅에서는 Priority Scheduling and(with) Synchronization(우선순위 스케쥴링과 동기화)과 그로 인해 발생하는 Priority Inversion Problem(우선순위 역전현상 문제)를 알아보자~!