Project1: Threads - Priority Scheduling

⏰ Priority Scheduling 구현

1. 목표

선점형 우선순위 스케줄링(Preemptive Priority Scheduling)을 구현합니다.

---

2. 핵심 아이디어

우선순위 스케줄링의 목표는 "가장 높은 우선순위의 스레드가 항상 즉시 실행되도록 보장"하는 것입니다. 이를 위해 두 가지 핵심 전략을 사용합니다.

1. Ready List의 정렬 (자료구조)

• ready_list를 단순한 큐(FIFO)가 아닌 우선순위 큐로 관리합니다.
• 스레드를 ready_list에 추가할 때마다(unblock 또는 yield) 항상 우선순위가 높은 순서대로 정렬하여 삽입합니다.
• 결과: ready_list의 맨 앞(list_begin)에는 "대기 중인 스레드 중 가장 우선순위가 높은 스레드"가 항상 위치하게 됩니다.

2. 즉각적인 선점 (스케줄링 로직)

현재 실행 중인 스레드보다 더 높은 우선순위의 스레드가 나타나면, 즉시 CPU를 빼앗아(선점)와야 합니다. 이 검사는 2가지 시점에 필요합니다.

• Case 1: (새로운 경쟁자 등장)
  • timer_sleep이나 lock 대기에서 깨어난 스레드가 ready_list에 삽입될 때,
  • 이 스레드의 우선순위가 '현재 실행 중인 스레드'보다 높다면, 즉시 CPU를 선점합니다.
• Case 2: (현재 스레드가 약해짐)
  • '현재 실행 중인 스레드'가 스스로의 우선순위를 낮출 때(thread_set_priority),
  • ready_list의 맨 앞(대기 중인 1등)보다 우선순위가 낮아진다면, 즉시 CPU를 양보(선점)당합니다.

---

3. 구현 과정

1. ready_list 정렬 삽입 (in thread_unblock)

BLOCKED 상태의 스레드가 READY 상태가 될 때(e.g., lock_release, timer_sleep 종료), ready_list의 맨 뒤에 추가(list_push_back)하는 대신, 우선순위에 맞게 정렬 삽입(list_insert_ordered)하도록 수정합니다.

비교 함수 (priority_less):

/* 'b'보다 'a'의 우선순위가 높으면 true(1)를 반환하여 리스트 앞에 위치시킴 */
bool 
priority_less (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);

  // t_a의 우선순위가 더 크면 'true'를 반환
  return t_a->priority > t_b->priority;
}

thread_unblock 수정:

// 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 대신 정렬 삽입 함수 사용
    list_insert_ordered(&ready_list, &t->elem, priority_less, NULL);

    t->status = THREAD_READY;
    
    /* * [선점 로직 1]
     * 새로 READY가 된 스레드(t)의 우선순위가
     * 현재 실행 중인 스레드보다 높다면 CPU를 양보(선점)해야 함.
     */
    if (t->priority > thread_current()->priority) {
        
        // 현재 인터럽트 컨텍스트(e.g., timer_interrupt)에서 호출된 경우
        if (intr_context()) {
            // 인터럽트가 끝나자마자 yield가 호출되도록 플래그만 설정
            intr_yield_on_return();
        } 
        // 일반 컨텍스트(e.g., lock_release)에서 호출된 경우
        else {
            // 즉시 yield 호출
            thread_yield();
        }
    }
    
    intr_set_level (old_level);
}

2. ready_list 정렬 삽입 (in thread_yield)

스레드가 스스로 CPU를 양보(thread_yield)할 때도 ready_list에 정렬 삽입되도록 수정합니다.

thread_yield 수정:

// 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_push_back 대신 정렬 삽입 함수 사용
        list_insert_ordered(&ready_list, &curr->elem, priority_less, NULL);
    }
    
    /* * [버그 수정]
     * do_schedule()은 'if' 블록 밖에 있어야 함.
     * idle_thread가 yield 할 때도 스케줄링이 일어나야
     * ready_list에 있는 새 스레드가 실행될 수 있음.
     */
    do_schedule(THREAD_READY); 
    
    intr_set_level(old_level);
}

3. 선점 로직 (in thread_set_priority)

현재 실행 중인 스레드가 자신의 우선순위(thread_set_priority)를 변경할 때 선점이 발생할 수 있습니다.

thread_set_priority 수정:

// thread.c
void 
thread_set_priority(int new_priority) {

    thread_current()->priority = new_priority;
    
    /*
     * [선점 로직 2]
     * 만약 ready_list가 비어있지 않다면,
     * 우선순위를 낮춘 현재 스레드가
     * ready_list의 대기 중인 최고 우선순위 스레드보다
     * 우선순위가 낮아졌는지 확인해야 함.
     */
    if (!list_empty(&ready_list))
    {
        // ready_list의 맨 앞(최고 우선순위 스레드)을 가져옴
        struct thread *front_thread = list_entry(list_begin(&ready_list), struct thread, elem);
        
        // 만약 내(current)가 맨 앞의 스레드보다 우선순위가 낮다면
        if (thread_current()->priority < front_thread->priority) {
            // 즉시 CPU를 양보
            thread_yield();
        }
    }
}