잘못된 내용은 댓글 부탁드립니다.
목표
PintOS는 기본적으로 우선순위 기반 스케줄링(Priority Scheduling)을 제공합니다. 하지만 사용자 개입 없이 시스템이 자동으로 우선순위를 조정해야 하는 경우에는 MLFQS(Multi-Level Feedback Queue Scheduler)를 사용해야 합니다.
MLFQS는 nice, recent_cpu, load_avg 값을 기반으로 각 스레드의 우선순위를 동적으로 조정합니다. 이를 통해 기아 현상 방지, CPU 사용량에 따른 공정한 분배, 실시간 반응성 개선이 가능합니다.
수정 파일
/threads/thread.c
/threads/thread.h
/threads/synch.c
/devices/timer.c
/include/threads/fixed_point.h(추가)
구현
1. 고정소수점 연산 구현: fixed_point.h
|
1
2
3
4
5
6
7
8
|
/* include/threads/fixed_point.h */
#define F (1 << 14)
int int_to_fp (int n);
int fp_to_int_round (int x);
...
int mult_fp (int x, int y);
int div_fp (int x, int y);
|
MLFQS는 부동소수점 연산이 허용되지 않기 때문에, load_avg와 recent_cpu, priority 모두 고정소수점 계산을 수행합니다. recent_cpu는 고정소수점 방식으로 표현된 CPU 사용량입니다. int recent_cpu;로 선언되어 있지만, 실제 의미는 fixed-point 표현입니다. 고정소수점 연산을 통해 커널 수준에서 실수 연산과 유사한 계산이 가능합니다.
2. thread 구조체 필드 추가
|
1
2
3
|
/* include/threads/thread.h */
int nice;
int recent_cpu;
|
nice는 CPU 사용 의지를 조절하는 값이며, 높을 수록 우선순위가 낮아집니다. recent_cpu는 해당 스레드가 얼마나 cpu를 사용했는지를 나타냅니다. 또한 전체 스케줄링에 영향을 주는 시스템 전역 변수 load_avg도 thread.c에 전역으로 추가합니다.
recent_cpu는 고정소수점 방식으로 표현된 CPU 사용량입니다. int recent_cpu;로 선언되어 있지만, 실제 의미는 fixed-point 표현입니다.
3. 우선순위 동적 갱신 로직
|
1
2
3
4
5
6
7
8
9
|
/* threads/thread.c */
void
mlfqs_priority (struct thread *t) {
if (t == idle_thread) {
return ;
}
t->priority = fp_to_int (add_mixed (div_mixed (t->recent_cpu, -4), PRI_MAX - t->nice * 2));
}
|
우선순위 계산 공식은 priority = PRI_MAX - (recent_cpu / 4) - (nice * 2) 입니다. idle_thread는 시스템에서 유휴 시간을 처리하기 위한 특수 스레드이기 때문에, priority 갱신 대상에서 제외합니다. recent_cpu, priority가 의미 없고 load_avg 계산 시에도 제외됩니다. 계산된 priority가 PRI_MIN(0)보다 작거나 PRI_MAX(63)를 초과할 경우, 해당 범위로 잘라주는(clamping) 처리를 추가하면 안정적인 우선순위 정책 구현이 가능합니다. recent_cpu가 높거나 nice가 높으면 priority는 낮아집니다.
4. timer_interrupt() 수정
|
1
2
3
4
5
6
7
8
9
10
11
|
/* devices/timer.c */
if (thread_mlfqs) {
mlfqs_increment ();
if (ticks % 4 == 0) {
mlfqs_priority (thread_current ());
if (ticks % TIMER_FREQ == 0) {
mlfqs_load_avg ();
mlfqs_recalc ();
}
}
}
|
4 tick마다 현재 실행 중인 스레드의 priority만 갱신되고, 100 tick마다 `mlfqs_recalc()`가 호출되며, ready_list와 sleep_list의 모든 스레드에 대해 mlfqs_update_thread()를 호출하여 priority와 recent_cpu 값을 동기적으로 갱신합니다. thread_start() 함수 내에서 load_avg를 LOAD_AVG_DEFAULT(=0)로 초기화하며, 이후 매 100 tick마다 갱신됩니다.
5. lock_acquire(), lock_release() 수정
|
1
2
3
4
|
/* threads/synch.c */
if (!thread_mlfqs) {
// priority donation 코드만 적용
}
|
MLFQS는 시스템이 자동으로 priority를 조정하므로, lock_acquire() 및 lock_release()에서 priority donation 관련 로직은 실행되지 않도록 차단합니다. MLFQS가 활성화된 경우, thread_set_priority()로 수동 설정해도 priority 값은 무시됩니다. 이는 시스템이 자동으로 우선순위를 계산·갱신하기 때문입니다. donation은 정적 우선순위 기반에서만 필요합니다.
결과
MLFQS는 부하가 높은 시스템에서도 starvation 없이 공정한 스케줄링을 가능하게 합니다. 이번 구현을 통해 PintOS는 고정된 우선순위에서 벗어나, 스레드의 CPU 사용량과 사용자의 nice 값에 따라 동적으로 우선순위를 계산하는 MLFQ 기반 스케줄링을 완성하게 되었습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
pass tests/threads/mlfqs/mlfqs-block
pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
pass tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
pass tests/threads/priority-change
pass tests/threads/priority-donate-one
pass tests/threads/priority-donate-multiple
pass tests/threads/priority-donate-multiple2
pass tests/threads/priority-donate-nest
pass tests/threads/priority-donate-sema
pass tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
pass tests/threads/priority-sema
pass tests/threads/priority-condvar
pass tests/threads/priority-donate-chain
pass tests/threads/mlfqs/mlfqs-load-1
pass tests/threads/mlfqs/mlfqs-load-60
pass tests/threads/mlfqs/mlfqs-load-avg
pass tests/threads/mlfqs/mlfqs-recent-1
pass tests/threads/mlfqs/mlfqs-fair-2
pass tests/threads/mlfqs/mlfqs-fair-20
pass tests/threads/mlfqs/mlfqs-nice-2
pass tests/threads/mlfqs/mlfqs-nice-10
pass tests/threads/mlfqs/mlfqs-block
All 27 tests passed.
|
GITHUB
깃허브 Merge pull request입니다.
https://github.com/laphayen/pintos-kaist/pull/6
Multi-Level Feedback Queue Scheduler by laphayen · Pull Request #6 · laphayen/pintos-kaist
우선순위 스케줄링은 높은 우선순위의 쓰레드만 CPU를 점유할 경우에 낮은 쓰레드는 대기하는 기아현상이 발생합니다. 이는 자원을 기다리는 쓰레드들이 많아져서 평균 대기 시간이 길어집니다
github.com
댓글