Advanced Scheduler
4.4BSD 스케줄러와 유사한 다단계 피드백 큐 스케줄러를 구현하여 시스템에서 실행 중인 작업들의 평균 응답 시간을 줄이세요.
우선순위 스케줄러와 마찬가지로 다단계 피드백 큐 스케줄러는 우선순위를 기반으로 실행할 스레드를 선택합니다. 그러나 다단계 피드백 큐 스케줄러는 우선순위 기부를 수행하지 않습니다. 따라서 다단계 피드백 큐 스케줄러에 대한 작업을 시작하기 전에 우선순위 스케줄러가 작동하고 있는 것이 좋습니다. (우선순위 기부에 대해서는 필요에 따라 구현하지 않았더라도)
시작 시간에 Pintos에서 스케줄링 알고리즘 정책을 선택할 수 있도록 코드를 작성해야 합니다. 기본적으로 우선순위 스케줄러가 활성화되어야 하지만 -mlfqs 커널 옵션을 사용하여 4.4BSD 스케줄러를 선택할 수 있어야 합니다. 이 옵션을 전달하면 main()에서 일찍 호출되는 parse_options()에 의해 구문 분석될 때 threads/thread.h에 선언된 thread_mlfqs가 true로 설정됩니다.
4.4BSD 스케줄러가 활성화되면 스레드는 더 이상 직접 자신의 우선순위를 제어하지 않습니다. thread_create()에 대한 우선순위 인자는 무시되어야 하며, thread_set_priority() 호출 및 thread_get_priority()는 스케줄러에 의해 설정된 스레드의 현재 우선순위를 반환해야 합니다. 다단계 피드백 큐 스케줄러는 이후의 프로젝트에서 사용되지 않습니다.
void thread_set_priority(int new_priority) {
if (thread_mlfqs) return; // mlfqs에서는 해당 함수 비활성화, 다른 코드의 donation 시스템도 비활성화 처리
if (list_empty(&thread_current()->donations)) {
thread_current()->priority = new_priority;
}
thread_current()->init_priority = new_priority;
execute_max_priority();
}
void thread_tick(void) {
struct thread *t = thread_current();
/* Update statistics. */
if (t == idle_thread)
idle_ticks++;
#ifdef USERPROG
else if (t->pml4 != NULL)
user_ticks++;
#endif
else
kernel_ticks++;
if (thread_mlfqs) {
mlfqs_increment();
if (timer_ticks() % 4 == 0) // 4틱마다
mlfqs_recalc_priority(); // 우선순위 재설정
if (timer_ticks() % 100 == 0) { // 100틱마다
mlfqs_load_avg(); // load_avg 재설정
mlfqs_recalc_recent_cpu(); // recent_cpu 재설정
}
}
/* Enforce preemption. */
if (++thread_ticks >= TIME_SLICE) {
intr_yield_on_return();
}
}
// 고정소수점 계산을 위한 함수 헤더 파일 생성
#include <stdint.h>
#define F (1 << 14) //fixed point 1
#define INT_MAX ((1 << 31) - 1)
#define INT_MIN (-(1 << 31))
// x and y denote fixed_point numbers in 17.14 format
// n is an integer
int int_to_fp(int n); /* integer를 fixed point로 전환 */
int fp_to_int_round(int x); /* FP를 int로 전환(round toward zero) */
int fp_to_int(int x); /* FP를 int로 전환(round to nearest) */
int add_fp(int x, int y); /* FP의 덧셈 */
int add_mixed(int x, int n); /* FP와 int의 덧셈 */
int sub_fp(int x, int y); /* FP의 뺄셈(x-y) */
int sub_mixed(int x, int n); /* FP와 int의 뺄셈(x-n) */
int mult_fp(int x, int y); /* FP의 곱셈 */
int mult_mixed(int x, int n); /* FP와 int의 곱셈 */
int div_fp(int x, int y); /* FP의 나눗셈(x/y) */
int div_mixed(int x, int n); /* FP와 int 나눗셈(x/n) */
int int_to_fp(int n) {
return n * F;
}
int fp_to_int_round(int x) {
return x / F;
}
int fp_to_int(int x) {
if (x >= 0)
return (x + F / 2) / F;
else if (x <= 0)
return (x - F / 2) / F;
}
int add_fp(int x, int y) {
return x + y;
}
int add_mixed(int x, int n) {
return x + n * F;
}
int sub_fp(int x, int y) {
return x - y;
}
int sub_mixed(int x, int n) {
return x - n * F;
}
int mult_fp(int x, int y) {
return (int)((((int64_t)x) * y) / F);
}
int mult_mixed(int x, int n) {
return x * n;
}
int div_fp(int x, int y) {
return (int)((((int64_t)x) * F) / y);
}
int div_mixed(int x, int n) {
return x / n;
}
void mlfqs_load_avg(void) { // load_avg 계산
int a = div_fp(int_to_fp(59), int_to_fp(60));
int b = div_fp(int_to_fp(1), int_to_fp(60));
int load_avg2 = mult_fp(a, load_avg);
int ready_thread = (int)list_size(&ready_list);
ready_thread = (thread_current() == idle_thread) ? ready_thread : ready_thread + 1;
int ready_thread2 = mult_mixed(b, ready_thread);
int result = add_fp(load_avg2, ready_thread2);
load_avg = result;
}
void mlfqs_increment(void) {
if (thread_current() != idle_thread) {
int cur_recent_cpu = thread_current()->recent_cpu;
thread_current()->recent_cpu = add_mixed(cur_recent_cpu, 1); // recent_cpu는 매 틱마다 증가
}
}
void mlfqs_recalc_recent_cpu(void) { // recent_cpu 재설정
for (struct list_elem *tmp = list_begin(&all_list); tmp != list_end(&all_list); tmp = list_next(tmp)) {
mlfqs_recent_cpu(list_entry(tmp, struct thread, all_elem));
}
}
void mlfqs_recalc_priority(void) { // 우선순위 재설정
for (struct list_elem *tmp = list_begin(&all_list); tmp != list_end(&all_list); tmp = list_next(tmp)) {
mlfqs_priority(list_entry(tmp, struct thread, all_elem));
}
}
int thread_get_nice (void);
현재 스레드의 nice 값을 반환합니다.
int thread_get_nice(void) {
/* TODO: Your implementation goes here */
enum intr_level old_level;
old_level = intr_disable();
int nice_val = thread_current()->nice;
intr_set_level(old_level);
return nice_val; // 해당 스레드의 nice 값을 반환
}
int thread_set_nice (int nice);
현재 스레드의 nice 값을 `new_nice`로 설정하고, 새 값에 따라 스레드의 우선순위를 다시 계산합니다 (우선순위 계산 참조). 실행 중인 스레드가 더 이상 가장 높은 우선순위를 가지지 않으면 양보합니다.
void thread_set_nice(int nice UNUSED) {
/* TODO: Your implementation goes here */
ASSERT(nice >= -20 && nice <= 20);
enum intr_level old_level;
old_level = intr_disable();
thread_current()->nice = nice;
mlfqs_priority(thread_current());
list_sort(&ready_list, priority_less, NULL);
execute_max_priority();
intr_set_level(old_level);
}
`thread_get_recent_cpu()` 함수를 구현해야 합니다. 해당 함수에 대한 템플릿이 `threads/thread.c` 파일에 제공되어 있습니다.
int thread_get_recent_cpu (void);
현재 스레드의 최근 CPU 값을 100배 한 값을 반환하며, 가장 가까운 정수로 반올림합니다.
int thread_get_recent_cpu(void) { // recent_cpu 산출식에 따라 계산
/* TODO: Your implementation goes here */
enum intr_level old_level;
old_level = intr_disable();
int result = fp_to_int(mult_mixed(thread_current()->recent_cpu, 100));
intr_set_level(old_level);
return result;
}
Calculating load_avg
마지막으로 로드 평균은 종종 시스템 로드 평균으로 알려져 있으며, 지난 1분 동안 실행 준비 상태에 있는 스레드의 평균 수를 추정합니다. 최근 CPU와 마찬가지로 지수 가중 이동 평균입니다. 우선순위 및 최근 CPU와 달리 load_avg는 스레드별이 아닌 시스템 전체적인 값입니다. 시스템 부팅 시 0으로 초기화되며, 이후 1초에 한 번씩 다음과 같은 공식에 따라 업데이트됩니다:
load_avg = (59/60) * load_avg + (1/60) * ready_threads
여기서 "ready threads"는 업데이트 시점에 실행 중이거나 실행 준비가 된 스레드의 수를 나타냅니다. (idle 스레드는 제외합니다.)테스트에서 몇 가지 가정이 있기 때문에 load_avg는 정확히 시스템 틱 카운터가 초의 배수가 될 때, 즉, timer_ticks () % TIMER_FREQ == 0 일 때에만 업데이트되어야 합니다. 이를 위해 thread_get_load_avg()를 구현해야 하며, threads/thread.c에 이를 위한 뼈대가 제공됩니다.
int thread_get_load_avg (void)
현재 시스템 로드 평균의 100배 값을 반환하며, 가장 가까운 정수로 반올림합니다.
int thread_get_load_avg(void) { // load_avg 산출식에 따라 계산
/* TODO: Your implementation goes here */
enum intr_level old_level;
old_level = intr_disable();
int result = fp_to_int(mult_mixed(load_avg, 100));
intr_set_level(old_level);
return result;
}
