[PintOS] Project 1 : Priority Scheduling 구현

Priority Scheduling

더 높은 우선순위의 스레드가 ready_list에 추가되면 현재 실행중인 스레드는 즉시 CPU를 양보해야 한다. 우선순위는 PRI_MIN (0) 부터 PRI_MAX (63)까지의 범위를 가지며, 숫자가 클수록 높은 우선순위이다.

Round Robin Scheduling (RR)

돌아가면서 CPU를 나눠주는 방식으로, 공정성을 중시한다.

• 각 스레드는 “동일한 시간 할당(time slice or quantum)을 받는다.
• 시간이 다 지나면 강제로 스레드를 CPU에서 내보내고 다음 스레드에게 기회를 준다.
• 우선순위를 고려하지 않는다. → 실시간 성능에서는 불리할 수 있다.
• 기아 상태가 발생하지 않는다.

동작 방식

1. ready_list 에서 스레드를 꺼냄
2. 정해진 시간 (TIME_SLICE, 보통 4 tick)이 지나면 타이머 인터럽트 발생
3. 현재 스레드는 다시 ready_list에 넣고 다음 스레드로 전환

구현 목표

• ready_list 를 정렬하여 우선순위가 제일 높은 스레드가 항상 맨 앞에 오도록한다.
• 현재 스레드보다 우선순위가 높은 스레드가 생성된 경우, 즉시 CPU를 양보한다.
• 실행 중인 스레드의 우선순위가 낮아진 경우, ready_list 에 더 높은 우선순위 스레드가 있다면 즉시 양보한다.

구현

수정 함수 구현

모든 함수는 threads/thread.c 파일 내에서 수정, 추가 되었습니다.

 

thread_create()

• thread_unblock 호출 시 BLOCKED 상태에서 READY 상태로 바뀐다
• 새로운 스레드가 생성되면 ready_list에 넣고
• 새 스레드의 우선순위가 현재 스레드보다 높다면, 현재 스레드가 CPU를 양보해서 더 급한 스레드가 실행되도록 한다.

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

    ASSERT (function != NULL);

    /* Allocate thread. */
    t = palloc_get_page (PAL_ZERO);
    if (t == NULL)
        return TID_ERROR;

    /* Initialize thread. */
    init_thread (t, name, priority);
    tid = t->tid = allocate_tid ();

    /* Call the kernel_thread if it scheduled.
     * Note) rdi is 1st argument, and rsi is 2nd argument. */
    t->tf.rip = (uintptr_t) kernel_thread;
    t->tf.R.rdi = (uint64_t) function;
    t->tf.R.rsi = (uint64_t) aux;
    t->tf.ds = SEL_KDSEG;    // data segment
    t->tf.es = SEL_KDSEG;
    t->tf.ss = SEL_KDSEG;
    t->tf.cs = SEL_KCSEG;   // code segment
    t->tf.eflags = FLAG_IF; // Turn on Interrupt enable bit

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

    /* Project 1 - priority */
    if((t->priority > thread_current()->priority) && thread_current != idle_thread){
        thread_yield();
    }

    return tid;
}

 

thread_unblock()

• 기존의 push_back으로 삽입하는 방식이 아닌, 새로운 스레드가 ready_list에 우선순위에 따라 추가될 수 있도록 한다.
• cmp_priority 함수를 추가로 구현한다.

void
thread_unblock (struct thread *t) {
    enum intr_level old_level;

    ASSERT (is_thread (t));

    old_level = intr_disable ();
    ASSERT (t->status == THREAD_BLOCKED);

    /* Project 1 : priority */
    // list_push_back (&ready_list, &t->elem);
    list_insert_ordered(&ready_list, &t->elem, cmp_priority, NULL);

    t->status = THREAD_READY;

    intr_set_level (old_level);
}

 

thread_yield()

• 현재 실행 중인 스레드가 CPU를 포기하고, 준비 상태(READY)로 돌아가 다른 스레드에게 CPU를 양보한다.
• ready_list를 조작하는 것은 임계 구역에 진입하는 것으로, 인터럽트를 비활성화 후 실행한다.
• idle은 ready_list에 진입하면 안되기 때문에, 조건문으로 예외 처리한다.
• 현재 스레드를 ready_list에 넣을 때, 우선순위 순으로 정렬해서 삽입한다.

void
thread_yield (void) {
    struct thread *curr = thread_current ();
    enum intr_level old_level;

    ASSERT (!intr_context ());        // Do Not yield in interrupt context

    old_level = intr_disable ();    // Disable interrupt to protect critical section
    if (curr != idle_thread)
        // list_push_back (&ready_list, &curr->elem);
        list_insert_ordered(&ready_list, &curr->elem, cmp_priority, NULL);
    do_schedule (THREAD_READY);
    intr_set_level (old_level);
}

추가 함수 구현

threads/thread.c : cmp_priority

• ready_list에 정렬된 순서로 삽입하기 위해, 각 element를 비교하여 삽입할 위치를 찾는다.

bool
cmp_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED){
    struct thread *t_a = list_entry(a, struct thread, elem);
    struct thread *t_b = list_entry(b, struct thread, elem);

    return t_a->priority > t_b->priority;
}

Trouble Shooting

1. thread_create에서 thread_yield 시점에 대한 고민

if((t->priority > thread_current()->priority) && thread_current != idle_thread){
        thread_yield();
}

• 처음에는 thread_create 의 위 함수 호출을 thread_unblock 에서 했었으나, 인터럽트 처리가 제대로 되지 않아 테스트 통과가 되지 않았다.
• 예상되는 문제로는, thread가 준비되지 않은 상황에서 컨텍스트 스위칭이 발생할 수 있고, 호출자의 의도와 다른 스케줄링이 발생할 수 있다. 스레드를 깨우는 과정에서 다른 인터럽트가 발생하여 커널 패닉이 발생한 것으로 예상된다.
• thread_create 으로 함수 위치를 변경하여 해결하였다.
• 추가로 if 조건문에 현재 스레드가 idle_thread가 아닌 경우를 반영해주어야 한다. idle 스레드는 ready_list에 스레드가 있는 경우 바로 CPU를 양보하도록 설계되어있다.

2. intr_disable 의 시점에 대한 고민

• PintOS와 같은 커널 환경에서는 스레드 간의 선점(preemption)이나 인터럽트가 언제든지 발생할 수 있다.
• 그래서 임계 구역에서 인터럽트나 스케줄링으로 다른 스레드에게 CPU를 양보하면, 잘못된 스레드가 실행 되거나, 공유 자원이 손상될 수 있다.

언제 인터럽트를 비활성화 해야 할까?

1. 공유 자료구조 접근 직전
   • ready_list에 삽입, 삭제를 하기 전에는 인터럽트를 끄고 조작해야 한다.
   • 커널에서는 리스트 연산이 비원자적(non-atomic)이기 때문이다.
2. thread의 상태 변경
3. 컨텍스트 스위치가 일어나기 전
   • do_schedule 함수 호출 전에 인터럽트를 비활성화 해야한다.
   • 인터럽트 중에 다른 컨텍스트 스위치가 발생하면 동기화가 깨질 수 있다.

테스트 결과

통과 되어야 하는 테스트를 별도로 표기해두었다.