𝕄𝕃𝔽ℚ𝕊

M이랑 F, S가 들어간 거만 봐도 영 질이 안좋다는 걸 알 수 있다

아무튼, 이번주차의 optional 과제로

사실 이거 말고도 할 거 빡세긴 더럽게 빡세서

optional로 넣은 거 같다

그래도 한번 트라이는 해봐야 하니 책내용 정리하겠다

원본

고급 스케줄러 (Advanced Scheduler)

성능 향상을 꾀하기 위해 4.4BSD 스케줄러와 유사한 다단계 피드백 큐(MLFQS) 스케줄러를 구현하라고 한다

고급 스케줄러도 우선순위에 따라 스레드를 고르지만
우선순위 기부 같은 건 하지 않는다

Pintos 부팅 시점에 스케줄링 정책을 선택 가능해야 한다

기본값은 우선순위 스케줄링이지만 커널 옵션 -mlfqs로
4.4BSD 스케줄러 선택 가능해야 한다

활성화 될시 스레드는 자신의 우선순위 직접 제어 안한다
thread_create(), thread_set_priority()는 무시당한다

…

벌써 쉽지 않다…

4.4BSD 스케줄러

이름이 뭔 의미냐?

UC 버클리에서 만든 유닉스 계열 운영체제 Berkeley Software Distribution(BSD)
의 버전 4.4란 뜻이다

그렇다.

의미없다

지금 설명할건 그 긴거 4.4의 커널의 스케줄링 방식이다

범용 스케줄러의 목표는 다양한 요구를 균형있게 맞추는거다

I/O 중심 스레드는 빠른 응답 시간 필요, CPU 시간 적게 필요

계산 중심 스레드 CPU 시간 필요, 빠른 응답 시간은 필수아님이다

이 두개를 잘 균형맞춰 해야 좋은 스케줄러다

우리가 만들 스케줄러는 [McKusick]에 설명된 다단계 피드백 큐 스케줄러의 한 예라고 한다

이 스케줄러는 실행 준비가 된 스레드를 우선순위별로 여러 개의 큐에 보관한다

특정 시점에는 가장 높은 우선순위의 비어 있지 않은 큐에서 스레드를 선택하여 실행하고
그 큐에 여러 스레드가 있다면, 라운드 로빈¹ 순서로 실행

Niceness (나이스 값)

우선순위는 공식을 통해 동적으로 결정한다

각 스레드는 정수형 nice 값을 가지며, 다른 스레드에게 얼마나 양보적이어야 하는지를 나타낸다

0은 영향없고 양수는 우선순위 낮춰 CPU 시간 덜 갖게 하고 음수는 CPU 시간 더 갖게오려고 한다

범위는 -20 ~ 20 이다

초기 스레드는 nice 값 0으로 시작이고 새로 생기는 이들은 부모에게 nice 값 상속 받는다

뼈대 코드

int thread_get_nice (void);
// 현재 스레드의 nice 값을 반환.

int thread_set_nice (int nice);
// 현재 스레드의 nice 값을 설정하고, 새 값에 따라 우선순위를 재계산.
// 실행 중인 스레드가 더 이상 최고 우선순위가 아니면 즉시 양보.

대충 매너 온도라 생각하면 될 거 같다

우선순위 계산 (Calculating Priority)

64개 우선순위(0~63) 와 그에 대응하는 64개의 준비 큐를 사용해야 한다

숫자가 작을수록 낮은 우선순위이며, 0이 최저, 63이 최고다

스레드의 우선순위는 초기화 시 계산되고, 이후 매 4틱마다 모든 스레드에 대해 다시 계산된다

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

recent_cpu 는 스레드가 최근에 사용한 CPU 시간의 추정치,
nice 는 스레드의 나이스 값이다

결과는 내림해서 정수로 써야 하고 말이다

많이쓰면 우선순위 낮춰 기아 막는 역할을 하는 핵심이다

recent_cpu 계산 (Calculating recent_cpu)

최근에 CPU 쓴애 찾는 역할이다

n초 동안 시간을 배열로 두면 개손해라

지수 가중 이동 평균(EWMA) 이란걸 사용한다

이게 한국어냐???

아무튼, 공식은 이러하다

• 초기값: x(0) = f(0)

• 일반식: x(t) = a x(t−1) + (1−a) f(t), a = k/(k+1), k > 0

여기서 x(t) 는 시각 t ≥ 0 에서의 이동 평균, f(t) 는 평균을 낼 원시 함수값, k 는 감쇠 속도를 제어한다

전개하면

x(1) = f(1)
x(2) = a f(1) + f(2)
...
x(5) = a^4 f(1) + a^3 f(2) + a^2 f(3) + a f(4) + f(5)

t 시점의 f(t)는 그 시점에서 가중치1, t+1 에서 $a$, t+2 에서 $a^2$ … 를 갖는다

f(t) 는 t+k 시점에서 약 $1/e$, t+2k 에서 약 $1/e^2$ 의 가중치가 된다

반대로 f(t) 가 가중치 w 로 감쇠되는 시점은 t + log_a(w)가 된다

recent_cpu 의 초기값은 첫 번째 스레드에서는 0, 다른 새 스레드에서는 부모의 값으로 시작

매 타이머 인터럽트마다, 실행 중인 스레드(idle 스레드 제외)의 recent_cpu 를 1 증가
초당 1회, 모든 스레드(실행/준비/봉쇄 상태 불문)의 recent_cpu 를 다음 공식으로 재계산

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

load_avg는 실행 준비 스레드 수의 이동 평균

경쟁 스레드 수가 많을수록 감쇠가 느려지고 recent_cpu 는 최근 받은 CPU 시간을 경쟁 정도에 비례해 반영

테스트 때문에 이 재계산은 시스템 틱 카운터가 정확히 1초 배수에 도달할 때(즉 timer_ticks() % TIMER_FREQ == 0)만 수행

recent_cpu가 음수가 될 수도 잇다

계산 순서도 고려해야한다 recent_cpu에 곱할 계수를 먼저 계산한 뒤 곱하는 것

thread.c의 뼈대

int thread_get_recent_cpu (void);
// 현재 스레드의 recent_cpu 값에 100을 곱해, 가장 가까운 정수로 반올림하여 반환.

load_avg 계산 (Calculating load_avg)

load_avg(시스템 부하 평균)는 지난 1분간 실행 준비 스레드 수의 평균을 추정

얘도 지수 가중 이동 평균이다

load_avg는 시스템 전체에 대한 값이다

부팅 시 0 으로 초기화하고, 이후 초당 1회 다음 공식으로 갱신

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

ready_threads는 업데이트 시점에 실행 중이거나 실행 준비 상태인 스레드의 개수
(idle 스레드 제외)

얘도 1초 배수 시점에만 갱신해야 한다

thread/thread.c의 뼈대

int thread_get_load_avg (void);
// 현재 시스템 load_avg에 100을 곱해, 가장 가까운 정수로 반올림하여 반환.

요약 (Summary)

아래 공식은 스케줄러 구현에 필요한 계산을 요약한 것입니다(요구사항의 완전한 설명은 아님).

• 모든 스레드는 −20 ~ 20 범위의 nice 값을 직접 가진다.
• 각 스레드는 0(PRI_MIN) ~ 63(PRI_MAX) 범위의 우선순위를 가지며, 매 4틱마다 다음 공식으로 재계산된다:

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

• recent_cpu 는 스레드가 최근에 받은 CPU 시간을 측정한다. 매 틱마다 실행 중인 스레드의 recent_cpu 를 1 증가시킨다. 또한 초당 1회, 모든 스레드의 recent_cpu 를 다음 공식으로 갱신한다:

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

• load_avg 는 지난 1분간 실행 준비 스레드 평균 개수를 추정한다. 부팅 시 0에서 시작하고, 초당 1회 다음 공식으로 갱신된다:

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

여기서 ready_threads 는 업데이트 시점에 실행 중 또는 준비 상태인 스레드 수이며(idle 제외), 위 모든 주기적 갱신은 정확히 1초 배수 시점에 수행되어야 한다.