[Pintos] Threads: Advanced Scheduler - 핵심 로직 구현 및 통합된 코드 디버깅하기

Threads: Advanced Scheduler - 핵심 로직 구현 및 통합된 코드 디버깅하기

이전 준비 세션을 통해 Pintos Project 1의 MLFQS(Multi-Level Feedback Queue Scheduler)에 대한 큰 그림을 그리고 공유 코드 템플릿을 만든 뒤, 본격적으로 역할을 나누어 구현을 시작하게 되었습니다. 저는 이번에 MLFQS의 핵심 로직 구현을 담당했는데요. 곧 스레드의 recent_cpu 및 priority를 동적으로 갱신하고, 시스템 전체 부하(load_avg)를 반영하도록 로직을 작성해야 했습니다.

 

이번 글에서는 구체적으로 핵심 갱신 흐름을 담당하는 5개의 함수들과 이를 도와주는 2개의 함수에 대한 구현 과정을 정리하고, 팀원들과 모든 구현을 마친 뒤 통합된 코드에 대해 디버깅했던 내용들을 공유해보려고 합니다.

 

 

구현 흐름 요약

전체 tick 흐름에 따라 주기적으로 동작하는 갱신 함수들을 정리하면 다음과 같습니다.

Tick 주기	실행 내용
매 tick마다	recent_cpu++ (idle 제외)
매 1초마다	update_load_avg(), update_all_recent_cpu()
매 4 tick마다	update_all_priority(), 필요시 선점

이 흐름은 mlfqs_on_tick() 함수를 통해 통합되며, timer_interrupt() 내부에서 호출됩니다.

 

 

update_load_avg() – 시스템 부하 계산

시스템의 load average를 지수 이동 평균(EMA) 방식으로 계산하는 함수인데요. 단순한 ready_list 크기만이 아니라, 최근 경향을 반영해 값이 부드럽게 변화하도록 설계됐습니다.

 

참고로 fixed_t 형식은 고정 소수점을 다루기 때문에 기본 연산자 +, -, /, *가 아니라, fixed-point.h에 정의한 전용 함수를 통해 계산해야 합니다.

계산 공식

load_avg = (59/60) * load_avg + (1/60) * ready_threads

구현 코드

// 시스템 전체의 평균적인 부하(load_avg)를 갱신하는 함수
// 1초(100 tick)마다 호출되며, 스레드의 recent_cpu와 priority 계산에 영향을 준다.
static void update_load_avg(void) {
    // 현재 ready 상태에 있는 스레드 수 가져오기 (idle_thread 제외)
    int ready_threads = list_size(&ready_list);

    // 현재 실행 중인 스레드가 idle_thread가 아니라면,
    // 현재 CPU를 점유 중인 스레드도 포함해주기 위해 +1
    if (thread_current() != idle_thread)
        ready_threads += 1;

    // 59/60과 1/60을 fixed-point 형식으로 만들기
    fixed_t coeff_59_60 = div_fixed(int_to_fixed(59), int_to_fixed(60));
    fixed_t coeff_1_60  = div_fixed(int_to_fixed(1),  int_to_fixed(60));

    // 공식: load_avg = (59/60) * load_avg + (1/60) * ready_threads
    // 지난 load_avg의 영향을 더 많이 반영하고,
    // 현재 ready 상태인 스레드 수의 영향을 약간 반영한다.
    LOAD_AVG = add_fixed(
        mul_fixed(coeff_59_60, LOAD_AVG),       // 지난 load_avg의 59/60
        fixed_mul_int(coeff_1_60, ready_threads) // 현재 ready_threads의 1/60
    );
}

• 실행 중인 스레드가 idle이 아니면 ready_threads에 1을 더해줘야 함
• load_avg는 모든 스레드의 priority에 영향을 주는 중요 요소

 

update_recent_cpu() – CPU 사용량 누적

각 스레드에 대해 얼마나 CPU를 점유했는지를 나타내는 수치인 recent_cpu를 갱신해주는 함수입니다. 이 값이 높을수록 우선순위에서 불이익을 받게 되지요.

계산 공식

recent_cpu = (2 * load_avg) / (2 * load_avg + 1) * recent_cpu + nice

구현 코드

// 특정 스레드 t의 recent_cpu 값을 갱신하는 함수
// recent_cpu는 해당 스레드가 최근 얼마나 CPU를 사용했는지를 나타내며,
// 스레드의 우선순위(priority) 계산에 영향을 준다.
static void update_recent_cpu(struct thread *t) {
    // idle_thread는 CPU 사용량 계산에서 제외되므로 return
    if (t == idle_thread) return;

    // 공식: recent_cpu = (2*load_avg) / (2*load_avg + 1) * recent_cpu + nice
    // 비율 계수(coeff) 계산
    // coeff = (2 * load_avg) / (2 * load_avg + 1)
    fixed_t coeff = div_fixed(
        fixed_mul_int(LOAD_AVG, 2),                      // 분자: 2 * load_avg
        add_fixed(fixed_mul_int(LOAD_AVG, 2), int_to_fixed(1)) // 분모: 2 * load_avg + 1
    );

    // 계산된 계수를 이용해 recent_cpu 갱신
    // new_recent_cpu = coeff * old_recent_cpu + nice
    t->recent_cpu = add_fixed(
        mul_fixed(coeff, t->recent_cpu), // 과거 CPU 사용량에 대한 가중치 반영
        int_to_fixed(t->nice)            // nice 값(스레드의 '느긋함')도 반영
    );
}

 

 

thread_foreach() – 모든  스레드에 대해 지정한 함수 호출

모든 스레드에 대해 어떤 작업을 반복적으로 수행할 때 사용되는 함수입니다. 다만 이 함수를 사용하기 위해서는 all_list에 모든 스레드가 list_elem 형태로 존재해야 하는데요. 그래서 아래의 과정을 통해 함수를 호출하기 위한 준비를 해줘야 합니다.

(1) 정적 전역 변수 all_list 생성 (thread.c)

static struct list all_list;

(2) all_list 초기화 (thread.c - thread_init() 내부)

list_init(&all_list);

(3) 스레드 생성 시 all_list에 등록되도록 변경 (thread.c - init_thread())

list_push_back(&all_list, &t->allelem);

(4) thread_foreach 함수 선언 및 struct thread에 allelem 필드 추가 (thread.h)

void thread_foreach(void (*func)(struct thread *, void *), void *aux);

// struct thread 내부
struct list_elem allelem;

 

구현 코드

// 모든 스레드에 대해 주어진 함수를 반복적으로 호출하는 함수
// all_list에 존재하는 모든 스레드에 대해 func(t, aux)를 호출한다.
//
// 매개변수:
// - func: 각 스레드에 대해 호출할 함수 포인터 (예: recent_cpu나 priority 갱신 함수)
// - aux : 추가로 전달할 인자 (함수 내부에서 사용하고 싶을 때 사용)
void thread_foreach(void (*func)(struct thread *t, void *aux), void *aux)
{
    // 전달받은 함수 포인터가 NULL이 아니어야 함 (즉, 유효한 함수여야 함)
    ASSERT(func != NULL);

    struct list_elem *e;

    // all_list는 현재 존재하는 모든 스레드의 리스트
    // 리스트의 첫 번째 요소부터 끝까지 순회하면서 각 스레드에 대해 함수를 호출
    for (e = list_begin(&all_list); e != list_end(&all_list); e = list_next(e))
    {
        // 리스트 요소를 thread 구조체로 변환
        struct thread *t = list_entry(e, struct thread, allelem);

        // 해당 스레드에 대해 func 함수를 호출
        func(t, aux);
    }
}

 

 

update_all_recent_cpu() – 전체 스레드 갱신

모든 스레드에 대해 update_recent_cpu()를 호출하는 함수입니다.

static void update_all_recent_cpu(void) {
	// idle을 제외한 모든 스레드에 대해 update_recent_cpu 실행
    thread_foreach(update_recent_cpu, NULL);
}

thread_foreach()는 all_list에 있는 모든 스레드를 순회하면서 전달된 함수를 적용합니다.

 

 

update_priority() – 우선순위 계산

특정 스레드의 우선순위를 계산해 priority 값을 갱신하는 함수입니다. 우선순위는 다음 공식으로 계산되며, 항상 PRI_MIN ~ PRI_MAX 범위로 clamp(한정)해야 합니다.

 

계산 공식

priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)

구현 코드

// 주어진 스레드 t의 우선순위(priority)를 갱신하는 함수
static void update_priority(struct thread *t) {
    // idle_thread는 스케줄링 대상이 아니므로 return
    if (t == idle_thread) return;

    // 공식: priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)
    // CPU를 많이 쓴 스레드는 우선순위가 낮아지고,
    // nice 값이 클수록(더 '양보'하는 성향) 우선순위가 낮아진다.
    int priority = PRI_MAX
    	// recent_cpu / 4, fixed-point를 정수로 반올림 변환
        - fixed_to_int_round(fixed_div_int(t->recent_cpu, 4))
        // nice의 영향 반영 
        - t->nice * 2;

    // 계산된 우선순위가 허용 범위를 벗어나지 않도록 보정
    if (priority < PRI_MIN) priority = PRI_MIN;
    else if (priority > PRI_MAX) priority = PRI_MAX;

    // 스레드의 priority 값 갱신
    t->priority = priority;
}

 

 

update_all_priority() – 전체 우선순위 갱신

모든 스레드에 대해 update_priority()를 호출하는 함수입니다.

static void update_all_priority(void) {
	// idle을 제외한 모든 스레드에 대해 update_priority 실행
    thread_foreach(update_priority, NULL);
}

 

 

mlfqs_on_tick() – 전체 흐름 통합

위에서 구현한 모든 로직을 tick 주기에 따라 통합해 호출하는 함수인데요. 이는 실제 timer_interrupt() 에서 mlfqs 플래그가 켜져있을 때 tick 단위로 시스템 상태를 갱신하게 됩니다.

// 매 tick마다 호출되어 MLFQS 관련 정보를 갱신하는 함수
// timer_interrupt() 내부에서 호출되며, recent_cpu, load_avg, priority를 주기적으로 갱신
void mlfqs_on_tick(void) {
    // 현재 실행 중인 스레드가 idle_thread가 아니라면 recent_cpu를 1 증가
    if (thread_current() != idle_thread)
        thread_current()->recent_cpu = add_fixed(thread_current()->recent_cpu, int_to_fixed(1));

    // 매 100tick(=1초)마다 시스템 부하(load_avg)와 모든 스레드의 recent_cpu 값을 갱신
    if (timer_ticks() % TIMER_FREQ == 0) {
        update_load_avg();          // 시스템 부하(load_avg) 업데이트
        update_all_recent_cpu();    // 모든 스레드의 recent_cpu 업데이트
    }

    // 매 4tick마다 모든 스레드의 우선순위를 갱신하고,
    // 만약 더 높은 우선순위의 스레드가 있다면 양보(preemption) 시도
    if (timer_ticks() % 4 == 0) {
        update_all_priority();      // 모든 스레드의 priority 업데이트
        list_sort(&ready_list, cmp_priority, NULL);	// ready_list를 우선순위 별로 정렬
    }
}

 

 

🐛 디버깅 에피소드

mlfqs-load-1

• 테스트 중간에 thread_sleep을 통해 ready_threads를 0으로 만들어 감소 추이를 보는 부분이 있었는데, alarm_clock이 merge되지 않아 busy wait을 하면서 ready_threads가 계속 1로 유지되어 테스트 실패
• 기존 Priority Scheduling에 대한 merge 후 이유는 알 수 없지만 alarm 테스트까지 모두 통과되고 있었기에 이를 알기가 쉽지 않았음
• main 브랜치에 alarm_clock을 다시 반영해 해결

mlfqs-load-60

• 종료된 스레드가 all_list에 남아 있어 이미 해제된 스레드의 allelem 참조 (dangling pointer) → 커널 패닉 발생
• schedule()에서 dying 스레드의 allelem을 제거함으로써 해결

mlfqs-recent-1

• thread_get_recent_cpu()에서 100배 보정 누락 → 값이 작게 나와 테스트 실패
• mul_fixed_int(값, 100) 적용으로 해결
• 참고로 thread_get_nice() 도 마찬가지로 100배로 보정해야 nice 관련 테스트 통과 가능

 

마치면서

이번 구현을 통해 MLFQS의 핵심 흐름인 load_avg, recent_cpu, priority 계산이 어떻게 연결되는지를 직접 체감할 수 있었는데요. 우리가 늘상 쓰는 운영체제가 실제로는 이것보다 더 복잡한 로직을 통해 스케줄링을 수행하고 있다니 정말 놀랍습니다. 시스템 수준에서 운영체제가 하는 일을 직접 느껴보면서 많은 걸 느꼈고, 다음에 있을 다른 구현들도 기대되는 것 같습니다. 아래에 같은 조원들의 구현 기록을 공유하면서 이만 마치겠습니다. 감사합니다.

• (박은범 학우) [PintOS] Project 1 : Thread - Multilevel Feedback Queue Scheduler - 2