Pintos-kaist Guide - PROJECT 1: THREADS - Advanced Scheduler, FAQ

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()는 스케줄러에 의해 설정된 스레드의 현재 우선순위를 반환해야 한다. 고급 스케줄러는 이후 프로젝트에서 사용되지 않는다.

 

4.4BSD Scheduler

일반 목적의 스케줄러의 목표는 서로 다른 스케줄링 요구사항을 가진 스레드들의 균형을 맞추는 것이다. 많은 입출력(I/O) 작업을 수행하는 스레드는 입력과 출력 장치를 바쁘게 유지하기 위해 빠른 응답 시간이 필요하지만, CPU 시간은 거의 필요하지 않는다. 반면에, 계산 작업이 많은 스레드는 작업을 완료하기 위해 많은 CPU 시간을 필요로 하지만, 빠른 응답 시간은 요구하지 않는다. 다른 스레드들은 입출력과 계산 기간이 번갈아 가면서 나타나므로, 시간에 따라 요구사항이 변한다. 잘 설계된 스케줄러는 이러한 모든 요구사항을 동시에 충족시킬 수 있는다.

 

프로젝트 1에서는 이 부록에서 설명된 스케줄러를 구현해야 한다. 우리의 스케줄러는 [McKusick]에서 설명된 스케줄러와 유사하며, 이는 다중 레벨 피드백 큐 스케줄러의 한 예. 이 유형의 스케줄러는 다른 우선순위를 가진 스레드들을 담고 있는 여러 개의 준비 큐를 유지한다. 어떤 시점에서든, 스케줄러는 가장 높은 우선순위의 비어 있지 않은 큐에서 스레드를 선택한다. 만약 가장 높은 우선순위의 큐에 여러 스레드가 포함되어 있다면, 그들은 "라운드 로빈" 순서로 실행된다.

 

스케줄러의 여러 측면은 일정 수의 타이머 틱 후에 데이터를 업데이트해야 한다. 모든 경우에서, 이러한 업데이트는 어떤 일반 커널 스레드도 실행되기 전에 발생해야 하므로, 커널 스레드가 새롭게 증가된 timer_ticks() 값을 보았지만 오래된 스케줄러 데이터 값을 볼 수 있는 상황이 발생하지 않도록 해야 한다.

 

4.4BSD 스케줄러는 우선순위 기부를 포함하지 않는다.

 

Niceness

스레드 우선순위는 스케줄러에 의해 아래에 제시된 수식을 사용하여 동적으로 결정된다. 그러나, 각 스레드는 다른 스레드에 대해 얼마나 "친절"해야 하는지를 결정하는 정수형 nice 값도 가지고 있다. 0의 nice 값은 스레드 우선순위에 영향을 주지 않는다. 최대 20까지의 양수 nice 값은 스레드의 우선순위를 낮추어 그렇지 않았다면 받게 될 CPU 시간의 일부를 포기하게 한다. 반면에, 최소 -20까지의 음수 nice 값은 다른 스레드로부터 CPU 시간을 빼앗으려는 경향이 있다.

 

초기 스레드는 nice 값이 0으로 시작한다. 다른 스레드는 부모 스레드로부터 상속받은 nice 값으로 시작한다. 아래에 설명된 함수들을 구현해야 하며, 이는 테스트 프로그램에서 사용된다. 우리는 이들을 threads/thread.c에서 스켈레톤 정의로 제공했다.

int thread_get_nice (void);

현재 스레드의 nice값을 반환한다.

int thread_set_nice (int nice);

현재 스레드의 좋은 값을 새 좋은 값으로 설정하고 새 값에 따라 스레드의 우선순위를 다시 계산한다.(우선순위 계산하기(Calculating Priority 참조). 실행 중인 스레드의 우선순위가 더 이상 높지 않으면 양보한다.

 

Calculating Priority

우리의 스케줄러는 64개의 우선순위와 그에 따른 64개의 준비 큐를 가지고 있으며, 이는 0(PRI_MIN)부터 63(PRI_MAX)까지 번호가 매겨진다. 낮은 번호는 낮은 우선순위를 나타내므로, 우선순위 0은 가장 낮은 우선순위이며 우선순위 63은 가장 높은 우선순위이다. 스레드 우선순위는 스레드 초기화 시 처음 계산되며 또한, 모든 스레드에 대해 네 번째 클록 틱마다 다시 계산된다. 어느 경우든, 그것은 다음 공식에 의해 결정된다.:

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

 

여기서 recent cpu는 스레드가 최근에 사용한 CPU 시간의 추정치이며(아래 참조) 그리고 nice는 스레드의 nice 값이다. 결과는 가장 가까운 정수로 내림(절삭)되어야 한다. recent cpu에 대한 계수 1/4과 nice에 대한 계수 2는 실제로 잘 작동하지만, 더 깊은 의미는 없으며, 계산된 우선순위는 항상 유효 범위 PRI_MIN에서 PRI_MAX 사이로 조정된다.

 

이 공식은 최근에 CPU 시간을 받은 스레드에게 다음 번 스케줄러가 실행될 때 CPU를 재할당받는 것에 대해 더 낮은 우선순위를 부여하는데, 이는 기아(starvation)를 방지하는 핵심이다: 최근에 어떤 CPU 시간도 받지 않은 스레드는 recent cpu가 0이 될 것이며, 높은 nice 값이 없는 한 곧 CPU 시간을 받아야 한다.

 

Calculating recent_cpu

우리는 recent cpu가 각 프로세스가 "최근"에 받은 CPU 시간을 얼마나 측정하는지 알고자 하며, 더 나아가, 더 최근의 CPU 시간을 덜 최근의 CPU 시간보다 더 무겁게 가중하는 것으로 개선하고자 한다. 한 가지 접근 방식은 지난 n초 동안 받은 CPU 시간을 추적하기 위해 n개의 요소를 가진 배열을 사용하는 것이지만, 이 접근 방식은 스레드당 O(n)의 공간과 새로운 가중 평균을 계산할 때 O(n)의 시간을 요구한다.

 

대신, 우리는 지수 가중 이동 평균을 사용하는데, 이는 다음과 같은 일반 형태를 취한다:

x(0) = f(0),
x(t) = ax(t − 1) + (1 − a)f(t),
a = k/(k + 1),

 

여기서 x(t)는 정수 시간 t ≥ 0에서의 이동 평균이며, f(t)는 평균화되는 함수이고, k > 0은 감쇠율을 조절한다. 우리는 몇 단계에 걸쳐 다음과 같이 공식을 반복할 수 있다:

x(1) = f(1),
x(2) = af(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가 되고, 이런 식으로 계속된다. 우리는 또한 x(t)를 k와 관련지을 수 있다: 시간 t + k에서 f(t)의 가중치는 대략 1/e이고, 시간 t + 2k에서는 대략 1/(e^2)이고, 이런 식으로 계속 되며, 반대 방향에서는 f(t)는 시간 t + log_a(w)에서 가중치 w로 감소한다.

 

첫 번째 생성된 스레드에서 recent_cpu의 초기 값은 0이고, 다른 새 스레드에서는 부모 스레드의 값이다. 타이머 인터럽트가 발생할 때마다, 실행 중인 스레드에 대해서만 recent_cpu가 1씩 증가한다. 단, 아이들 스레드가 실행 중일 때는 제외이며, 또한, 매초마다 실행 중이든, 준비 중이든, 또는 차단된 상태이든 모든 스레드에 대해 recent_cpu의 값이 다음 공식을 사용하여 다시 계산된다:

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

 

load_avg는 실행 준비가 된 스레드 수의 이동 평균이다(아래 참조). 만약 load_avg가 1이라면, 평균적으로 단일 스레드가 CPU를 경쟁하고 있다는 것을 나타내며, 이 경우 recent_cpu의 현재 값은 log_(2/3) .1 ≈ 6초 안에 가중치 .1로 감소한다: 만약 load_avg가 2라면, 가중치 .1으로 감소하는 데 log_(3/4) .1 ≈ 8초가 걸리지만, 이 효과는 recent_cpu가 스레드가 "최근"에 받은 CPU 시간의 양을 추정하며, 감소율은 CPU를 경쟁하는 스레드 수에 반비례한다는 것을 의미한다.

 

일부 테스트에서 가정하는 바에 따르면, recent_cpu의 재계산은 시스템 틱 카운터가 1초의 배수에 도달했을 때, 즉 timer_ticks() % TIMER_FREQ == 0일 때 정확히 이루어져야 하며, 다른 시간에는 이루어지지 않아야 한다.

 

음수 nice 값을 가진 스레드의 경우 recent_cpu의 값이 음수가 될 수 있기 때문에. 음수 recent_cpu를 0으로 제한하지 않아야 한다.

 

이 공식에서 계산 순서를 고민해야 할 수 있다. 우리는 recent_cpu의 계수를 먼저 계산한 다음 곱하는 것을 추천하는데, 일부 학생들은 load_avg를 recent_cpu에 직접 곱하면 오버플로우가 발생할 수 있다고 보고했다

 

threads/thread.c에 있는 스켈레톤을 이용하여 thread_get_recent_cpu()를 구현해야 한다.

int thread_get_recent_cpu (void);

현재 스레드의 최근 CPU 값의 100배를 가장 가까운 정수로 반올림하여 반환한다.

 

Calculating load_avg

마지막으로, 시스템 로드 평균이라고도 하는 load avg는 지난 1분 동안 실행할 준비가 된 스레드의 평균 수를 추정한다. recent_cpu와 마찬가지로 기하급수적으로 가중치가 부여된 이동 평균이며, 우선순위 및 recent_cpu와 달리 load_avg는 스레드별이 아닌 시스템 전체에 적용된다. 시스템 부팅 시 0으로 초기화되며, 그 후 초당 한 번씩 다음 공식에 따라 업데이트된다.:

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

 

업데이트 시점에서 실행 중이거나 실행 준비가 된 스레드 수(유휴 스레드 제외)를 준비 스레드라고 한다.

 

일부 테스트에 의해 가정된 바에 따르면, load_avg는 시스템 틱 카운터가 1초의 배수에 도달했을 때, 즉 timer_ticks() % TIMER_FREQ == 0일 때 정확히 업데이트되어야 하며, 다른 시간에는 업데이트되지 않아야 한다. threads/thread.c에 있는 스켈레톤을 이용하여 thread_get_load_avg()를 구현해야 한다.

int thread_get_load_avg (void)

현재 시스템 부하 평균의 100배를 가장 가까운 정수로 반올림하여 반환한다.

 

Summary

다음 공식은 스케줄러를 구현하는 데 필요한 계산을 요약한 것이며, 스케줄러 요구 사항에 대한 완전한 설명은 아니다.

 

모든 스레드는 -20에서 20 사이의 값을 직접 제어할 수 있다. 또한 각 스레드에는 0(PRI_MIN)에서 63(PRI_MAX) 사이의 우선 순위가 있으며, 이는 매 4번째 틱마다 다음 공식을 사용하여 다시 계산된다:

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

 

 

recent_cpu는 스레드가 최근에 받은 CPU 시간을 측정한다. 타이머가 틱될 때마다 실행 중인 스레드의 최근 CPU가 1씩 증가하며, 초당 한 번, 모든 스레드의 최근 CPU가 이런 방식으로 업데이트된다:

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

 

load_avg는 지난 1분 동안 실행할 준비가 된 평균 스레드 수를 추정한다. 부팅 시 0으로 초기화되며 다음과 같이 초당 한 번씩 다시 계산된다:

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

 

여기서 ready_threads는 업데이트 시점에 실행 중이거나 실행할 준비가 된 스레드의 수이다.(유휴 스레드 제외).

 

Fixed-Point Real Arithmetic

위의 공식에서 priority, nice, ready_threads는 정수이지만 recent_cpu와 load_avg는 실수이다. 안타깝게도 핀토스는 커널에서 부동 소수점 연산을 지원하지 않는데, 이는 커널이 복잡해지고 속도가 느려지기 때문이다. 실제 커널도 같은 이유로 동일한 제한이 있는 경우가 많다.

즉, 실제 수량에 대한 계산은 정수를 사용하여 시뮬레이션해야 하는데, 이것은 어렵지 않지만 많은 학생들이 그 방법을 모르기 때문에 이 섹션에서는 기본 사항을 설명한다.

 

기본 개념은 정수의 가장 오른쪽 비트를 분수를 나타내는 것으로 취급하는 것이다. 예를 들어, 부호 있는 32비트 정수의 최하위 14비트를 분수 비트로 지정하여 정수 x가 실수 x/(2^14)를 나타내도록 할 수 있다.

소수점 앞에 17비트, 뒤에 14비트, 부호 비트가 하나씩 있기 때문에 이를 17.14 고정 소수점 숫자 표현이라고 한다. 17.14 형식의 숫자는 최대 (2^31 - 1)/(2^14) ≈ 131,071.999의 값을 나타낸다.

 

p.q 고정 소수점 형식을 사용한다고 가정하고 f = 2^q라고 가정할 때, 위의 정의에 따라 정수 또는 실수에 f를 곱하여 p.q 형식으로 변환할 수 있다. 예를 들어, 17.14 형식에서 위의 load_avg 계산에 사용된 분수 59/60은 (59/60)2^14 = 16,110이며,  고정 소수점 값을 정수로 다시 변환하려면 f로 나눈다. (C의 정규 / 연산자는 0을 향해 반올림, 즉 양수를 내림하고 음수를 올림한다. 가장 가까운 값으로 반올림하려면 나누기 전에 양수에 f / 2를 더하거나 음수에서 빼면 된다.)

 

고정 소수점 수에 대한 많은 연산은 간단한데, x와 y를 고정 소수점 수로 하고 n을 정수로 하자. 그러면 x와 y의 합은 x + y이고 그 차는 x - y이다. x와 n의 합은 x + n * f;, 차는 x - n * f;, 곱은 x * n;, 몫은 x / n이다.

 

두 개의 고정 소수점 값을 곱하는 데는 두 가지 복잡한 문제가 있다.

• 첫째, 결과의 소수점이 왼쪽으로 너무 멀리 떨어져 있다.
  • (59/60)(59/60)은 1보다 약간 작아야 하지만 16,111 × 16,111 = 259,564,321이 2^14 = 16,384보다 훨씬 크다고 생각해보아라. q 비트를 오른쪽으로 이동하면 259,564,321/2^14 = 15,842, 즉 약 0.97이 정답이 된다.
• 둘째, 답이 표현 가능한데도 곱셈이 넘칠 수 있다.
  • 예를 들어 17.14 형식의 64는 64 × 2^14 = 1,048,576이고 그 제곱 64^2 = 4,096은 17.14 범위 내에 있지만 1,048,576^2 = 2^40으로 최대 부호 32비트 정수 값 2^31 - 1보다 크다. 쉬운 해결책은 곱셈을 64비트 연산으로 하는 것인데, 그러면 x와 y의 곱은 ((int64_t) x) * y / f이 된다.

 

두 개의 고정 소수점 값을 나누면 정반대의 문제가 발생한다. 소수점이 너무 오른쪽에 위치하게 되는데, 이는 나누기 전에 나누기 q 비트를 왼쪽으로 이동하여 해결할 수 있다. 왼쪽으로 이동하면 나눗셈의 상위 q 비트가 버려지는데, 이를 다시 64비트로 나눗셈을 수행하여 해결할 수 있다. 따라서 x를 y로 나눌 때의 몫은 ((int64_t) x) * f / y.

 

이 섹션에서는 두 가지 이유로 q-bit 시프트 대신 곱셈 또는 나눗셈을 일관되게 사용했다.

• 첫째, 곱셈과 나눗셈은 C 시프트 연산자처럼 놀라운 연산자 우선순위를 갖지 않는다.
• 둘째, 곱셈과 나눗셈은 음의 피연산자에 대해 잘 정의되어 있지만 C 시프트 연산자는 그렇지 않다. 구현할 때 이러한 문제에 주의해야 한다.

 

다음 표는 C에서 고정 소수점 산술 연산을 구현하는 방법을 요약한 것이다. 표에서 x와 y는 고정 소수점 숫자, n은 정수, 고정 소수점은 부호가 있는 p.q 형식(p + q = 31), f는 1 << q이다.

 

Arithmetic	C
Convert n to fixed point	n * f
Convert x to integer (rounding toward zero)	x / f
Convert x to integer (rounding to nearest)	(x + f / 2) / f if x >= 0
	(x - f / 2) / f if x <= 0
Add x and y	x + y
Subtract y from x	x - y
Add x and n	x + n * f
Subtract n from x	x - n * f
Multiply x by y	((int64_t) x) * y / f
Multiply x by n	x * n
Divide x by y	((int64_t) x) * f / y
Divide x by n	x / n