운영체제 · Pintos · Project 1 Threads · 3편
Pintos MLFQS: nice, recent_cpu, load_avg로 Project 1 마무리하기
1편에서는 alarm-priority를 통해 ready list의 priority 정렬을 봤고, 2편에서는 기본 Priority Scheduler와 donation을 정리했습니다. 이번 3편은 Project 1 Threads의 마지막 축인 MLFQS(Multi-Level Feedback Queue Scheduler)입니다. 핵심은 단순합니다. 이제 priority를 사람이 직접 정하는 것이 아니라, scheduler가 수식으로 계속 다시 계산합니다.
이번 글에서 다루는 것
- MLFQS가 기본 Priority Scheduler와 어떻게 다른지
nice,recent_cpu,load_avg가 각각 무엇을 의미하는지- 매 tick, 매 4 tick, 매 1초마다 무엇을 갱신해야 하는지
- 커널에서 float을 못 쓰기 때문에 fixed-point 연산을 쓰는 이유
- choihyunjin1 브랜치 기준으로 MLFQS 테스트를 통과한 최소 수정 흐름
- 수정점마다 기존 코드와 바뀐 코드가 어떤 동작 차이를 만드는지
- MLFQS 테스트를 어떤 질문으로 읽어야 하는지
- Project 1 Threads 1주차를 마무리할 때 기억해야 할 기준
검증 기준
이 글의 구현 파트는 choihyunjin1 브랜치 기준 복사본에서 최소 수정으로 MLFQS를 붙이고 테스트를 돌린 결과를 바탕으로 정리했습니다. 글에서는 어떤 기능이 어떤 테스트를 통과시키는지에 집중해서 남깁니다.
| 범위 | 확인 결과 |
|---|---|
| MLFQS 테스트 | mlfqs-load-1, mlfqs-load-60, mlfqs-load-avg, mlfqs-recent-1, mlfqs-fair-2, mlfqs-fair-20, mlfqs-nice-2, mlfqs-nice-10, mlfqs-block PASS |
| 기존 테스트 | alarm-*, priority-* PASS 재확인 |
1. Project 1에서 MLFQS의 위치
Project 1 Threads는 크게 네 단계로 이어집니다. 앞의 세 단계는 thread를 잠들게 하고, 깨우고, priority 순서로 실행하고, lock 때문에 생기는 priority inversion을 donation으로 완화하는 과정이었습니다. MLFQS는 여기서 한 단계 더 나아가 priority 자체를 scheduler가 자동으로 계산합니다.
MLFQS는 Priority Donation과 같이 쓰지 않습니다. 기본 scheduler에서는 donation으로 priority inversion을 다뤘지만, -mlfqs 옵션이 켜지면 priority는 donation이 아니라 계산식으로 결정됩니다.
2. 기본 Priority Scheduler와 MLFQS의 차이
2편의 기본 Priority Scheduler에서는 priority가 비교적 직접적이었습니다. thread를 만들 때 priority를 주고, 필요하면 thread_set_priority()로 바꾸고, lock을 기다릴 때 donation을 했습니다. MLFQS에서는 이 관점이 바뀝니다.
| 구분 | 기본 Priority Scheduler | MLFQS |
|---|---|---|
| priority의 출처 | thread 생성 인자, 직접 설정, donation | scheduler의 계산식 |
| donation | 사용함 | 사용하지 않음 |
thread_set_priority() |
현재 thread의 base priority를 바꿈 | 직접 priority 설정을 무시해야 함 |
| 핵심 상태값 | priority, base_priority, donations, wait_on_lock | nice, recent_cpu, load_avg, priority |
한 줄로 말하면, 기본 scheduler는 누가 priority를 가지고 있느냐가 중요했고, MLFQS는 최근 CPU를 얼마나 썼고, 시스템이 얼마나 바쁜가가 중요합니다.
3. MLFQS를 이해하는 네 가지 값
MLFQS는 이름이 길고 수식도 나오지만, 처음에는 네 값만 잡으면 됩니다. priority, nice, recent_cpu, load_avg입니다.
priority
scheduler가 다음에 실행할 thread를 고르는 기준입니다. MLFQS에서는 수식으로 계속 다시 계산됩니다.
nice
thread가 다른 thread에게 얼마나 양보적인지 나타내는 값입니다. 값이 높을수록 priority가 낮아지고, 값이 낮을수록 CPU를 더 받으려는 성격이 됩니다. 초기 thread는 0으로 시작하고, 새 thread는 부모의 nice 값을 물려받습니다.
recent_cpu
이 thread가 최근에 CPU를 얼마나 사용했는지 추정하는 값입니다. 최근 CPU를 많이 쓴 thread는 priority가 내려갑니다. 처음 만들어지는 thread는 0에서 시작하고, 새 thread는 부모의 recent_cpu 값을 물려받습니다.
load_avg
시스템 전체에서 CPU를 원하고 있는 thread가 평균적으로 얼마나 되는지 나타내는 값입니다. thread마다 있는 값이 아니라 시스템 전체에 하나만 있습니다.
4. 수식은 무엇을 말하고 있는가
공식 GitBook의 핵심 수식은 아래 세 개입니다. 여기서 중요한 것은 수식을 외우는 것이 아니라, 각 항이 priority를 어느 방향으로 밀어내는지 이해하는 것입니다.
| 값이 커지면 | scheduler의 해석 | 결과 |
|---|---|---|
recent_cpu 증가 |
최근 CPU를 많이 썼다 | priority 감소 |
nice 증가 |
다른 thread에게 더 양보적인 thread다 | priority 감소 |
load_avg 증가 |
시스템에 CPU를 원하는 thread가 많다 | recent_cpu가 더 천천히 줄어듦 |
어떤 thread의 recent_cpu가 12이고 nice가 1이라면, priority는 대략 63 - 3 - 2 = 58이 됩니다. 최근 CPU를 더 많이 쓸수록, 또는 nice가 더 높을수록 priority는 내려갑니다.
5. 언제 갱신해야 하는가: tick 기준 흐름
MLFQS에서 가장 많이 틀리는 부분은 수식 자체보다 갱신 타이밍입니다. 공식 요구사항은 timer tick이 특정 시점에 도달했을 때 정확히 값을 갱신하라고 말합니다.
매 tick
현재 running thread의 recent_cpu를 1 증가시킨다. 단, idle thread는 제외한다.
매 4 tick
모든 thread의 priority를 다시 계산한다. 계산 결과는 PRI_MIN과 PRI_MAX 사이로 조정한다.
매 1초
load_avg와 모든 thread의 recent_cpu를 다시 계산한다.
1초 갱신은 timer_ticks() % TIMER_FREQ == 0일 때 정확히 해야 합니다. 이 타이밍이 어긋나면 수식이 맞아도 mlfqs-load-avg, mlfqs-recent-1 같은 테스트가 흔들릴 수 있습니다. 또한 이 갱신은 timer interrupt 흐름 안에서 처리되어야 합니다. 그래야 일반 kernel thread가 새 tick 값은 봤는데 scheduler 데이터는 아직 옛값인 상태를 보지 않습니다.
6. fixed-point가 필요한 이유
MLFQS 수식에는 소수 계산이 들어갑니다. 하지만 Pintos 커널에서는 floating-point 연산을 직접 쓰지 않는 것이 원칙입니다. 그래서 정수 안에 소수부를 흉내 내는 fixed-point arithmetic을 사용합니다.
많이 쓰는 방식은 17.14 fixed-point입니다. 오른쪽 14비트를 소수부처럼 쓰고, 정수 1은 내부적으로 1 << 14로 표현합니다.
#define F (1 << 14)
static int int_to_fp (int n) { return n * F; }
static int fp_to_int_zero (int x) { return x / F; }
static int fp_to_int_nearest (int x) {
return x >= 0 ? (x + F / 2) / F : (x - F / 2) / F;
}
static int fp_add (int x, int y) { return x + y; }
static int fp_sub (int x, int y) { return x - y; }
static int fp_add_int (int x, int n) { return x + n * F; }
static int fp_sub_int (int x, int n) { return x - n * F; }
static int fp_mul (int x, int y) { return ((int64_t) x) * y / F; }
static int fp_div (int x, int y) { return ((int64_t) x) * F / y; }
static int fp_mul_int (int x, int n) { return x * n; }
static int fp_div_int (int x, int n) { return x / n; }곱셈과 나눗셈에서 int64_t를 쓰는 이유는 overflow를 줄이기 위해서입니다. load_avg * recent_cpu처럼 fixed-point끼리 곱할 때 값이 커질 수 있으므로, 중간 계산을 64비트로 올려두는 편이 안전합니다.
7. 테스트를 통과한 최소 수정 컨셉
이제 개념을 코드로 옮겨봅니다. 목표는 기존 Alarm, Priority Scheduling, Donation 테스트를 깨지 않으면서 mlfqs-* 테스트를 통과하는 것입니다. 핵심 수정 파일은 thread.h, thread.c, synch.c 세 곳입니다.
수정 1. thread가 MLFQS 값을 기억하게 만들기
MLFQS는 thread마다 nice와 recent_cpu를 기억해야 합니다. 또 모든 thread를 주기적으로 순회해야 하므로 전체 thread 목록에 들어갈 all_elem도 필요합니다.
기존 코드
int priority; /* 실제 스케줄링에 쓰는 priority. donation 반영값 */
int base_priority; /* 원래 priority. thread_set_priority()가 바꾸는 값 */
struct list donations; /* 나에게 priority를 빌려준 thread들의 목록 */
struct list_elem donation_elem; /* 내가 다른 thread의 donations 목록에 들어갈 때 쓰는 elem */
struct lock *wait_on_lock; /* 내가 지금 기다리는 lock. nested donation 추적용 */
int64_t wakeup_tick; /* timer_sleep() wakeup 기준 tick */바뀐 코드
int priority; /* 실제 스케줄링에 쓰는 priority. donation 반영값 */
int base_priority; /* 원래 priority. thread_set_priority()가 바꾸는 값 */
struct list donations; /* 나에게 priority를 빌려준 thread들의 목록 */
struct list_elem donation_elem; /* 내가 다른 thread의 donations 목록에 들어갈 때 쓰는 elem */
struct lock *wait_on_lock; /* 내가 지금 기다리는 lock. nested donation 추적용 */
int64_t wakeup_tick; /* timer_sleep() wakeup 기준 tick */
int nice; /* MLFQS: 다른 thread에게 얼마나 양보적인지 */
int recent_cpu; /* MLFQS: 최근 CPU 사용량. fixed-point 값 */
struct list_elem all_elem; /* MLFQS: 전체 thread 목록에 들어갈 때 쓰는 elem */| 항목 | 수정 전 | 수정 후 |
|---|---|---|
| thread 상태 | priority, donation, alarm 값만 저장 | MLFQS 계산에 필요한 값도 thread마다 저장 |
| 가능해진 일 | thread별 CPU 사용량을 모름 | 모든 thread의 nice, recent_cpu를 추적 |
수정 2. fixed-point와 all_list 준비하기
MLFQS 공식에는 소수 계산이 들어가지만 커널에서는 float을 쓰지 않습니다. 그래서 fixed-point 매크로를 준비하고, blocked thread까지 포함해 모든 thread를 순회할 all_list를 둡니다.
기존 코드
#include "threads/vaddr.h"
#include "intrinsic.h"
static struct list ready_list;바뀐 코드
#include "threads/vaddr.h"
#include "devices/timer.h" /* TIMER_FREQ, timer_ticks() 사용 */
#include "intrinsic.h"
static struct list ready_list;
static struct list all_list; /* MLFQS: 모든 thread 순회용 목록 */
static int load_avg; /* MLFQS: 시스템 전체 평균 부하 */
#define F (1 << 14)
#define INT_TO_FP(n) ((n) * F)
#define FP_TO_INT_ZERO(x) ((x) / F)
#define FP_TO_INT_NEAREST(x) ((x) >= 0 ? ((x) + F / 2) / F : ((x) - F / 2) / F)
#define FP_ADD(x, y) ((x) + (y))
#define FP_ADD_INT(x, n) ((x) + (n) * F)
#define FP_MUL(x, y) ((int) (((int64_t) (x)) * (y) / F))
#define FP_MUL_INT(x, n) ((x) * (n))
#define FP_DIV(x, y) ((int) (((int64_t) (x)) * F / (y)))
#define FP_DIV_INT(x, n) ((x) / (n))| 항목 | 수정 전 | 수정 후 |
|---|---|---|
| 실수 계산 | 커널에서 float 사용 불가 | fixed-point 정수 계산으로 수식을 구현 |
| 전체 thread 순회 | ready list만 있음 | blocked, running thread까지 all_list로 계산 가능 |
수정 3. MLFQS 전역 상태 초기화하기
Pintos가 시작될 때 ready list만 초기화하면 MLFQS가 전체 thread를 순회할 수 없습니다. all_list와 load_avg를 함께 준비합니다.
기존 코드
lock_init (&tid_lock);
list_init (&ready_list);
list_init (&destruction_req);바뀐 코드
lock_init (&tid_lock);
list_init (&ready_list);
list_init (&all_list); /* MLFQS: 전체 thread 목록 초기화 */
list_init (&destruction_req);
load_avg = 0; /* 부팅 시 load_avg는 0 */| 항목 | 수정 전 | 수정 후 |
|---|---|---|
| load_avg | 값이 없음 | 시스템 부하 평균을 0에서 시작 |
| 전체 thread 목록 | 없음 | 모든 thread 등록 준비 |
수정 4. timer tick마다 MLFQS 값 갱신하기
MLFQS의 핵심은 갱신 타이밍입니다. 매 tick, 매 1초, 매 4 tick에 해야 할 일이 다릅니다.
기존 코드
/* Enforce preemption. */
if (++thread_ticks >= TIME_SLICE)
intr_yield_on_return ();바뀐 코드
if (thread_mlfqs) {
int64_t now = timer_ticks ();
if (t != idle_thread)
t->recent_cpu = FP_ADD_INT (t->recent_cpu, 1);
/* 매 tick마다 현재 CPU를 쓰는 thread의 recent_cpu 증가 */
if (now % TIMER_FREQ == 0) {
mlfqs_update_load_avg ();
mlfqs_update_recent_cpu_all ();
}
/* 매 1초마다 load_avg와 모든 thread의 recent_cpu 갱신 */
if (now % TIME_SLICE == 0)
mlfqs_update_priority_all ();
/* 매 4 ticks마다 모든 thread의 priority 재계산 */
}
if (++thread_ticks >= TIME_SLICE)
intr_yield_on_return ();| 시간 | 하는 일 | 이유 |
|---|---|---|
| 매 tick | running thread의 recent_cpu += 1 |
CPU를 얼마나 썼는지 기록 |
| 매 1초 | load_avg, 모든 recent_cpu 갱신 |
GitBook 공식 요구 |
| 매 4 ticks | 모든 priority 재계산 | priority가 동적으로 바뀌어야 함 |
수정 5. MLFQS에서는 thread_set_priority() 무시하기
MLFQS에서는 priority를 사용자가 직접 바꾸지 않습니다. thread_set_priority()는 기본 scheduler에서는 의미가 있지만, -mlfqs 모드에서는 scheduler 계산이 우선입니다.
기존 코드
void
thread_set_priority (int new_priority) {
struct thread *curr = thread_current ();
curr->base_priority = new_priority;
...
}바뀐 코드
void
thread_set_priority (int new_priority) {
struct thread *curr = thread_current ();
if (thread_mlfqs)
return;
/* MLFQS에서는 priority를 직접 설정하지 않고 scheduler 수식으로만 계산한다. */
curr->base_priority = new_priority;
...
}| 항목 | 수정 전 | 수정 후 |
|---|---|---|
| priority 변경 | 사용자가 직접 변경 가능 | MLFQS 모드에서는 직접 변경 무시 |
| GitBook 요구 | 직접 priority 설정이 남아 있을 수 있음 | -mlfqs에서는 scheduler가 priority를 관리 |
수정 6. nice/load_avg/recent_cpu 인터페이스 구현하기
테스트 프로그램은 kernel 내부 값을 직접 읽지 않습니다. 대신 GitBook이 요구한 public 함수들을 호출합니다. skeleton 함수가 0만 반환하면 MLFQS 테스트는 통과할 수 없습니다.
기존 코드
void thread_set_nice (int nice UNUSED) { }
int thread_get_nice (void) { return 0; }
int thread_get_load_avg (void) { return 0; }
int thread_get_recent_cpu (void) { return 0; }바뀐 코드
void
thread_set_nice (int nice) {
struct thread *curr = thread_current ();
curr->nice = nice;
mlfqs_update_priority (curr);
if (!list_empty (&ready_list)) {
struct thread *front = list_entry (list_front (&ready_list),
struct thread, elem);
if (front->priority > curr->priority)
thread_yield ();
}
}
int
thread_get_nice (void) {
return thread_current ()->nice;
}
int
thread_get_load_avg (void) {
return FP_TO_INT_NEAREST (FP_MUL_INT (load_avg, 100));
}
int
thread_get_recent_cpu (void) {
return FP_TO_INT_NEAREST (FP_MUL_INT (thread_current ()->recent_cpu, 100));
}| 함수 | 수정 전 | 수정 후 |
|---|---|---|
thread_set_nice |
아무 일 안 함 | nice 변경 후 priority 재계산 |
thread_get_load_avg |
항상 0 | load_avg * 100 반환 |
thread_get_recent_cpu |
항상 0 | recent_cpu * 100 반환 |
수정 7. MLFQS 계산 함수 추가하기
갱신 타이밍을 잡았다면 실제 계산 함수가 필요합니다. priority, recent_cpu, load_avg를 각각 GitBook 공식대로 갱신합니다.
static void
mlfqs_update_priority (struct thread *t) {
if (t == idle_thread)
return;
int priority = PRI_MAX
- FP_TO_INT_ZERO (FP_DIV_INT (t->recent_cpu, 4))
- (t->nice * 2);
if (priority > PRI_MAX)
priority = PRI_MAX;
if (priority < PRI_MIN)
priority = PRI_MIN;
t->priority = priority;
}
static void
mlfqs_update_recent_cpu (struct thread *t) {
if (t == idle_thread)
return;
int coef = FP_DIV (FP_MUL_INT (load_avg, 2),
FP_ADD_INT (FP_MUL_INT (load_avg, 2), 1));
t->recent_cpu = FP_ADD_INT (FP_MUL (coef, t->recent_cpu), t->nice);
}
static void
mlfqs_update_load_avg (void) {
int ready_threads = list_size (&ready_list);
if (thread_current () != idle_thread)
ready_threads++;
load_avg = FP_ADD (
FP_MUL (FP_DIV_INT (INT_TO_FP (59), 60), load_avg),
FP_MUL_INT (FP_DIV_INT (INT_TO_FP (1), 60), ready_threads));
}| 계산 함수 | 하는 일 | GitBook 공식 |
|---|---|---|
mlfqs_update_priority |
thread priority 재계산 | PRI_MAX - recent_cpu/4 - nice*2 |
mlfqs_update_recent_cpu |
thread CPU 사용량 감쇠 계산 | (2L)/(2L+1)*recent_cpu+nice |
mlfqs_update_load_avg |
시스템 ready thread 평균 계산 | 59/60*load_avg+1/60*ready_threads |
수정 8. init_thread에서 MLFQS 값 초기화하기
MLFQS에서 새 thread는 부모의 nice와 recent_cpu를 물려받습니다. 그리고 전체 계산 대상이 되도록 all_list에 등록해야 합니다.
기존 코드
t->priority = priority;
t->base_priority = priority;
list_init (&t->donations);
t->wait_on_lock = NULL;
t->magic = THREAD_MAGIC;바뀐 코드
t->priority = priority;
t->base_priority = priority;
list_init (&t->donations);
t->wait_on_lock = NULL;
if (thread_mlfqs) {
if (t == initial_thread) {
t->nice = 0;
t->recent_cpu = 0;
} else {
t->nice = thread_current ()->nice;
t->recent_cpu = thread_current ()->recent_cpu;
}
if (strcmp (name, "idle") != 0)
mlfqs_update_priority (t);
} else {
t->nice = 0;
t->recent_cpu = 0;
}
list_push_back (&all_list, &t->all_elem);
t->magic = THREAD_MAGIC;| 항목 | 수정 전 | 수정 후 |
|---|---|---|
| 새 thread priority | 인자로 받은 priority 사용 | MLFQS에서는 수식으로 계산 |
| nice/recent_cpu | 없음 | 부모 thread 값 상속 |
| 전체 목록 | 없음 | all_list에 등록 |
수정 9. 종료 thread를 all_list에서 제거하기
모든 thread를 all_list에 넣었다면, 종료되는 thread는 목록에서 빼야 합니다. 그렇지 않으면 이미 죽은 thread를 MLFQS 계산 대상으로 볼 수 있습니다.
기존 코드
intr_disable ();
do_schedule (THREAD_DYING);바뀐 코드
intr_disable ();
list_remove (&thread_current ()->all_elem);
/* 종료된 thread를 MLFQS 전체 계산 대상에서 제거 */
do_schedule (THREAD_DYING);| 항목 | 수정 전 | 수정 후 |
|---|---|---|
| 종료 thread | all_list에 남을 수 있음 | 종료 시 all_list에서 제거 |
| 위험 | 죽은 thread를 계산할 수 있음 | 잘못된 thread 접근 위험 감소 |
수정 10. MLFQS에서는 donation 끄기
마지막으로 가장 중요한 분기입니다. 2편에서 구현한 donation은 기본 Priority Scheduler용입니다. MLFQS 모드에서 donation 코드가 priority를 바꾸면 GitBook 요구와 충돌합니다.
기존 코드
if (lock->holder != NULL) {
...
donate_priority ();
}
remove_donations_for_lock (lock);
refresh_priority ();바뀐 코드
if (!thread_mlfqs && lock->holder != NULL) {
...
donate_priority ();
}
if (!thread_mlfqs) {
remove_donations_for_lock (lock);
refresh_priority ();
}| 항목 | 수정 전 | 수정 후 |
|---|---|---|
| priority donation | 항상 사용 | MLFQS 모드에서는 사용 안 함 |
| GitBook 요구 | MLFQS와 donation이 섞일 수 있음 | 4.4BSD scheduler 요구에 맞게 분리 |
8. 테스트 케이스를 어떻게 읽을까
MLFQS 테스트는 수식 하나를 단독으로 묻지 않습니다. 각 테스트는 "이 값이 제때 갱신되는가", "계산 결과가 scheduler 선택에 반영되는가"를 다른 장면에서 확인합니다.
| 테스트 | 묻는 질문 | 먼저 의심할 부분 |
|---|---|---|
mlfqs-load-1 |
ready thread 수가 load_avg에 반영되는가 | ready_threads 계산, idle thread 제외 |
mlfqs-load-avg |
load_avg가 1초마다 정확히 갱신되는가 | timer_ticks() % TIMER_FREQ == 0 타이밍 |
mlfqs-recent-1 |
recent_cpu가 tick과 load_avg에 따라 변하는가 | 매 tick 증가, 1초 갱신 공식, rounding |
mlfqs-nice-2, mlfqs-nice-10 |
nice가 priority 계산에 반영되는가 | thread_set_nice(), priority 재계산 후 yield |
mlfqs-fair-2, mlfqs-fair-20 |
여러 thread가 CPU를 어느 정도 공정하게 나눠 갖는가 | priority 갱신, ready list 정렬, time slice |
mlfqs-block |
blocked thread와 ready thread 계산을 구분하는가 | ready_threads 계산 범위, sleep/block 상태 처리 |
9. 자주 틀리는 지점
MLFQS는 공식이 명확해서 쉬워 보이지만, 실제 테스트에서는 작은 경계 조건이 많이 걸립니다. 아래 항목은 구현 중 계속 체크해야 합니다.
- MLFQS에서 donation을 섞는 실수:
thread_mlfqs가 true일 때는 donation 로직이 priority를 건드리면 안 됩니다. - 직접 priority 설정을 남겨두는 실수:
-mlfqs에서는thread_create()의 priority 인자와thread_set_priority()의 직접 설정을 scheduler 계산보다 앞세우면 안 됩니다. - recent_cpu 음수 clamp: nice가 음수인 thread는 recent_cpu가 음수가 될 수 있습니다. 0으로 강제로 자르면 안 됩니다.
- ready_threads 계산: ready list에 있는 thread 수에 현재 running thread를 더하되, idle thread는 제외해야 합니다.
- 갱신 타이밍: load_avg와 recent_cpu는 정확히 1초 경계에서 갱신해야 합니다.
- rounding 방향: priority 계산은 내림에 가깝게 정수화하고,
thread_get_recent_cpu(),thread_get_load_avg()는 100배 후 nearest rounding을 요구합니다.
10. Project 1 Threads를 이렇게 닫는다
Project 1 Threads를 지나오면 처음에는 thread 하나가 언제 실행되는지도 잘 보이지 않습니다. 하지만 Alarm, Priority Scheduling, Donation, MLFQS를 차례로 보면 scheduler가 보는 세계가 조금씩 구체화됩니다.
Alarm
thread를 재우고 깨우는 상태 전이
Priority
READY 중 누가 먼저 실행되는가
Donation
lock 때문에 막힌 priority를 어떻게 전달하는가
MLFQS
priority를 scheduler가 자동 계산하는가
MLFQS까지 오면 Project 1의 학습 목표가 선명해집니다. 우리는 단순히 테스트를 통과시키는 것이 아니라, thread 상태와 ready list, waiters, lock holder, timer tick이 scheduler 안에서 어떻게 연결되는지 배운 것입니다.
이번 글에서 기억할 것
- MLFQS에서는 donation을 쓰지 않는다.
- priority는
recent_cpu와nice로 계산된다. load_avg는 thread별 값이 아니라 시스템 전체 값이다.- 매 tick, 매 4 tick, 매 1초 갱신 타이밍을 분리해서 생각해야 한다.
- fixed-point 계산에서는 rounding과 overflow를 조심해야 한다.
스스로 점검
- MLFQS에서
thread_set_priority()가 priority를 직접 바꾸면 왜 안 될까? ready_threads를 계산할 때 idle thread를 제외해야 하는 이유는 무엇일까?recent_cpu가 커지면 priority가 왜 낮아질까?- 1초 갱신 타이밍이 조금만 어긋나도 MLFQS 테스트가 실패할 수 있는 이유는 무엇일까?
시리즈 마무리
1편의 Alarm은 thread를 언제 깨울지, 2편의 Priority Scheduler는 누가 먼저 실행될지, 3편의 MLFQS는 그 priority를 scheduler가 어떻게 계속 다시 계산할지를 다뤘습니다. 이 세 글을 묶으면 Project 1 Threads의 큰 흐름은 이렇게 정리됩니다. thread는 상태를 바꾸며 움직이고, scheduler는 그 상태들 사이에서 다음 실행 대상을 고른다.
참고 자료