PintOS-jungle) Priority Scheduling

PintOS project01-2) priority scheduling

현재 상황

기존 pintos 스케쥴러는 라운드 로빈으로 구현되어있다.

라운드 로빈(Round Robin)
시분할 시스템을 위해 설계된 선점형 스케줄링의 하나로서, 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위(Time Quantum/Slice)로 CPU를 할당하는 방식의 CPU 스케줄링 알고리즘.
https://jwprogramming.tistory.com/17

우선순위를 고려하지 않고 먼저 들어온 순서대로 CPU를 할당받는 방식이다. CPU를 점유할 수 있는 최대 시간이 지날 경우 다음 스레드에게 차례가 넘어가고 작업을 마치치 못한 스레드는 다시 ready list에 들어가게된다. 실시간 시스템이나 응답 시간이 짧은 대화형 시스템에 적절하다.

구현 목표 : Priority Scheduling

그림에서 1번 ready_list 우선순위 정렬에 해당하는 작업을 먼저 수행할 것이다.

thread의 우선순위를 고려하여 스케쥴링 하도록 수정해야한다.

Ready list에 새로 추가된 스레드의 우선순위가 현재 CPU를 점유 중인 스레드의 우선순위보다 높으면, 기존 스레드를 밀어내고 CPU를 점유하게 한다.

1. priority scheduling (ready_list)

1-1 구현해야 하는 함수

1. 현재 수행 중인 스레드와 ready list에서 우선순위가 가장 높은 스레드의 우선순위를 비교하여 후자가 더 높으면 ready list에서 우선순위가 제일 높은 스레드가 CPU를 점유하고 CPU를 점유하고있었던 스레드가 ready list로 들어오게 만들어야한다.

bool thread_compare_priority(struct list_elem *a, struct list_elem *b, void *aux UNUSED)

2. 스레드의 우선순위를 비교하는 기능을 하는 함수를 만들어야한다.

void test_max_priority(void)

1-2 우선순위를 비교해야하는 시점 찾기

thread_create()

• 스레드를 생성하여 ready_list에 삽입할 때, 실행 중인 스레드와 새로 생성된 스레드의 우선 순위를 비교하여 새로 생성되 스레드의 우선순위가 높다면 새로운 스레드가 CPU를 점유해야한다.
• thread_yield() 함수를 통해서 CPU를 점유하는 스레드를 바꿔줄 수 있다.

if (priority > thread_current()->priority)
    {
        thread_yield();
    }

thread_unblock()

• blocked 상태였던 스레드가 unblock 될 때 ready_list에 우선순위 순으로 정렬되어 삽입되어야한다.
• list_insert_ordered() 함수를 이용할 수 있다.

    //list_push_back(&ready_list, &t->elem);
    list_insert_ordered(&ready_list, &t->elem, thread_compare_priority, 0);

thread_yield()

• 현재 CPU를 점유하고 있던 스레드가 우선 순위가 더 높은 스레드에게 CPU를 빼앗기고 ready_list에 들어가게될 때, 우선순위로 정렬되어 삽입되어야한다.
• list_insert_ordered() 함수를 이용할 수 있다.

    if (curr != idle_thread)
        list_insert_ordered(&ready_list, &curr->elem, thread_compare_priority, 0);
        //list_push_back(&ready_list, &curr->elem);
    do_schedule(THREAD_READY);

1-3 추가적으로 고려해야하는 부분

thread_set_priority() 함수는 이미 생성된 스레드의 우선순위를 변경시키는 기능을 한다.

이 함수에 의해서 스레드의 우선순위가 변경되어을 때, 변경된 우선순위가 ready_list에서 우선순위가 가장 큰 스레드보다 작아지는 경우가 생길 수 있다.

이 경우를 대비하여 현재 스레드의 우선순위와 ready_list에 있는 스레드의 우선순위를 비교해줘야한다.

앞서 구현해놓은 test_max_priority() 함수를 이용할 수 있다.

thread_current()->priority = new_priority;
    test_max_priority();

2. priority scheduling (waiters)

그림에서 2번에 해당하는 sema를 기다리는 waiters의 스레드들도 우선순위로 정렬시켜줘야한다.

2-1 sema_down

공유자원을 점유하려고 sema_down 함수에 들어갔는데 이미 누가 공유 자원에 들어가있어서 sema->value가 0이면 waiters 리스트에 들어가게 한다. 이때 waiters에 우선순위로 정렬하면서 들어가게 해야한다.

while (sema->value == 0)
    {
        //list_push_back (&sema->waiters, &thread_current ()->elem);
        list_insert_ordered(&sema->waiters, &thread_current()->elem, thread_compare_priority, NULL); 
        thread_block();
    }
    sema->value--;

2-2 sema_up

스레드가 waiters 리스트에 있는 동안 우선순위가 변경되었을 경우를 고려해서 waiters 리스트를 정렬해준다.
그리고 현재 waiters 리스트에 있는 스레드와 ready_list에 있는 스레드 중 더 우선순위가 높은 스레드가 공유자원을 점유할 수 있도록 한다.

if (!list_empty(&sema->waiters))
    {
        list_sort((&sema->waiters), thread_compare_priority, NULL); 

        thread_unblock(list_entry(list_pop_front(&sema->waiters),
                                  struct thread, elem));
    }

    sema->value++;
    thread_yield();

전체 코드 : Git repository