BSD Scheduler
introduction
보편적인 스케쥴러의 목표는 쓰레드들 간의 스케쥴링 needs를 balance하는 것이다.
많은 I/O를 행하는 쓰레드는 빠른 응답시간을 유지하는 것이 중요하지만, CPU 타임은 적어도 된다. 반대로, compute-bound 쓰레드는 많은 CPU 시간을 필요로 하지만, 빠른 응답시간은 필요로 하지 않을 수 있다. 그 사이에 있는 다른 쓰레드들, compute 시간 중간에 간간히 I/O 들이 끼어드는 애들의 경우, 필요 시간이 결국 다양하게 분포될 수 있다. 잘 디자인된 스케쥴러는 쓰레드들 간의 이런 요구사항을 잘 조정할 수 있다.
Project1에서, 너는 이 appendix에 설명되있는 스케쥴러를 구현해야한다. 우리는 ultilevel feedback queue 스케쥴러 중 하나이고 McK usick에 설명되있는 스케쥴러를 배껴보려고 한다. 이 타입의 스케쥴러는 ready-to-run 쓰레드들의 several queue를 가지고 있는데, 각각은 서로 다른 priority의 쓰레드를 가지고 있다. 만약 가장 높은 우선순위의 큐가 여러 쓰레드를 가지고 있다면, 거기서는 round-robin으로 돌아갈꺼다.
스케쥴러의 여러 측면들은 몇 시간 틱들이 지난 다음에 데이터를 update하도록 요구한다.
In every case, these updates should occur before any ordinary kernel thread has
a chance to run, so that there is no chance that a kernel thread could see a newly increased timer_ticks() value but old scheduler data values.
모든 경우에서, 이런 업데이트들은 커널 쓰레드가 run 되기 전에 일어나기 때문에, 커널 쓰레드들이 새로운 증가된 timer_ticks()의 값이나 이전 스케쥴러의의 데이터 값을 볼 방법은 없다.
Niceness
쓰레드 우선순위는 아래의 공식을 이용하는 스케쥴러에 의해 동적으로 변한다. 그렇지만 각 쓰레드는 각각의 nice 정수를 가지고 있어서, 다른 쓰레드들에게 얼마나 ‘nice’하게 행동하는지를 결정할 수 있다. zero nice는 쓰레드 우선순위에 영향을 미치지 않는다. 최대 20까지 가능한 양의 nice는, 쓰레드의 priority를 감소시키고, 이것은 CPU시간을 감소시킨다. 반면에 -20까지 가능한 음의 nice는 다른 쓰레드들로부터 CPU 시간을 뺏어온다.
초기 쓰레드는 nice 값이 0으로 시작한다. 다른 쓰레드들은 부모 쓰레드들로부터 nice 값을 상속 받아서 진행한다. 아래에 설명되있는 함수들을 implement해야한다. 우리는 thread.c에 스켈레톤 정의를 제공했다.
•
int thread_get_nice(void)
•
void thread_set_nice(int new_nice)
◦
현재 쓰레드의 nice값을 새거로 바꾸고, 쓰레드의 우선순위를 새로운 값으로 설정한다. running 쓰레드가 더 이상 최우선 순위가 아니라면 yield한다.
Calculating Priority
우리의 스케쥴러는 64까지 우선순위가 있기 때문에, 64개의 ready queue가 있다.
낮은 숫자가 낮은 우선순위를 얘기하기에, 0이 제일 낮은거고 63이 제일 높은거다. 쓰레드 우선순위는 맨 처음에 쓰레드 initialization에서 정해진다. 이건 또한 4틱마다 재계산된다. 그리고 각 케이스별로 아래와 같은 공식으로 결정된다.
priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)
JavaScript
복사
여기서 recent_cpu는 쓰레드가 최근에 사용한 CPU 시간의 추정치이고, nice는 쓰레드의 nice 값이다. 이 결과는 정수로 무조건 내린다. 계수로 사용된 1/4와 1/2는 각각 실전에서 잘 사용되는 값이지만, 깊은 의미를 내포하진 않는다. 새로 계산된 priority는 항상 valid range에 놓여진다.
이 공식은 최근에 CPU 시간을 할당받은 쓰레드가 다음 CPU 시간을 재할당 받기 위한 우선순위를 낮추는 결과를 낳는다. 이게 기아를 방지하는 중요한 키이다. 최근에 CPU 시간을 받지 모한 쓰레드는 recent_cpu값이 0이기 때문에, 높은 nice 값이 없다면, 무조건 CPU 시간을 가능한 빨리 받을 수 있을 것을 보장한다.
Calculating recent_cpu
우리는 recent_cpu가 각 프로세스가 최근에 어느 정도의 CPU 시간을 할당 받았는지를 알고 싶은 것이다. 그렇기 때문에, 세밀한 조정이라는 관점에서, 최근에 할당받은 CPU 시간은 그 전에 쓴 CPU 시간보다 더 크게 가중치를 적용해야한다. 가능한 하나의 접근법은 마지막 n초 안에 받은 CPU 시간을 n개의 element를 가진 배열로 저장하는 것이다. 그렇지만 이 방법은 쓰레드당 O(n)의 공간과 새로운 weighted average를 계산하기 위해 O(n) 시간이 필요하다.
대신에 우리는 exponentially weighted moving average를 사용할건데, 이건 다음과 같다.
x(0) = f(0),
x(t) = ax(t-1) + (1-a)f(t);
a = k/(k+1);
JavaScript
복사
x(t)는 정수 시간에서 moving average이고, f(t)는 평균화된 함수이고, k가 감쇠율을 조작한다.
우리는 다음과 같은 스템으로 몇 번 반복할 수 있다.
x(1) = f(1);
x(2) = af(1) + f(2);
x(5) = a^4f(1) + a^3f(2) + a^2f(3) + af(4) + f(5)
f(t)의 가중치가 1/e가 될 때는 대충 t+k쯤까지이고, 1.e^2이려면 t+2k가지이다. 반대방향으로 생각해보면 f(t)의 는 w의 부패율에 대해 대략 t+logaW만큼 이다.
첫 쓰레드가 만들어질 때 recent_cpu 값은 0이거나 부모의 값일 거다. 타이머 인터럽트가 발생하면, recent_cpu는 지금 실행 중인 쓰레드에 한해 1씩 올라갈거다. 추가로, 1초에 한번씩 recent_cpu 값은 모든 쓰레드마다 재계산될거다. (running, ready, block이든 아니든 간에 무조건)
recent_cpu = (2*load_avg)/(2*load_avg + 1) * recent_cpu + nice;
여기서 load_avg가 바로 실행될 준비가 다 된 쓰레드의 이동 평균이다. 만약 load_avg가 1이면, 이건 single thread를 의미하고, recent_cpu가 0.1의 비중을 가지게 되는데는 6초 정도가 걸린다.
load_avg가 2라면, 0.1만큼의 가중치를 가지려면 8초정도 걸린다. 이 효과는 recent_cpu가 최근에 받은 CPU 시간을 역으로 가중치를 주변서 추산한다는 것을 알 수 있다.
몇 개의 테스트가 recent_cpu의 재계산이 시스템 틱 카운터가 multiple of second에 도달했을 때, 그니까 timer_ticks() % TIMER_FREQ == 0일 때, 정확히 계산되기를 가정한다.
recent_cpu의 값은 negative가 될 수 있다. 만약 nice가 음이라면.
너는 또한 이 공식의 계산 순서를 생각해야한다. recent_cpu의 계수부터 계산하고 곱하는 것을 추천한다. load_avg랑 recent_cpu를 바로 곱하는 것은 오버플로우가 날 수 있다.
thread_get_recent_cpu를 구현해라.
•
현재 thread의 recent_cpu 값의 100배를 곱해서 반환하고, 정수 이하는 반올림해라.
load_avg
마지막으로, Load_avg, 시스템 load average로 알려진 것은 지난 시간동안 ready to run할 수 있는 평균 쓰레드의 개수로 주어진다. recent_cpu처럼, 이것은 exponentially weighted moving average이다. priority와 recent_cpu와는 다르게, load_avg는 thread specific하지 않고, system-wide하다. 이건 처음에 0으로 초기화되고, 1초가 지날 때마다, 다음과 같은 공식으로 업데이트 된다.
load_avg = 59/60 * load_Avg + 1/60 * ready_threads
ready_threads가 실행되고 있거나 레디인 상태의 쓰레드의 개수이다.
테스트에서 일어나는 가정들 때문에, load_avg는 시스템 틱 카우터가 초단위로 정확히 맞아떨어질 때, 실행되야한다. thread_get_load_avg()를 구현하면 된다.
Sumary
아래 공식은 스케쥴러를 구현하기 위한 계산을 요약해준다.
완벽한 description은 아니다.
모든 쓰레드는 nice 값을 -20부터 20까지 가지고 있다. 각 쓰레드는 priority를 가지고 있는데 0~63까지를 가지고 있고, 다음과 같은 공식으로 4틱마다 업데이트 된다.
priority = PRI_MAX - (recent_cpu /4) - (nice * 2)
recent_cpu는 쓰레드가 최근에 받은 CPU시간을 계산한다. 매 틱마다, running thread의 recent_cpu는 1만큼 늘어난다. 1초마다 모든 쓰레드의 cpu는 다음과 같은 공식으로 업데이트 된다.
recent_cpu = (2*load_avg)/(2*load_avg + 1) * recent_cpu + nice;
load_avg는 이전 시간동안 실행될 수 있는 thread의 평균 개수를 추산한다. 0으로 초기화되었다가 1초에 한 번씩 다음과 같이 업데이트 된다.
load_avg = (59*60)*load_avg + (1/60)*ready_threads;
ready_thread는 실행되고 있거나, 실행될 애들의 숫자이다.
Fixed-Point Real Arithmetic
위의 공식에서, priority, nice, ready_threads는 정수이지만, recent_cpu와 load_avg는 실수이다. 불행하게도 핀토스는 floating-point arithmetic연산을 커널에서 제공하지 않는다, 왜냐하면 이건 커널에서 복잡하고 느리기 때문이다. 실제 커널은 같은 한계를 똑같이 가지고 있다. 이건 실제 양에 대한 계산이 무조건 정수로 simulated 되야한다는 것을 의미한다. 이건 어렵지 않지만, 많은 학생들이 어떻게 하는지 모른다.
기본적인 아이디어는 정수의 최하단 비트를 fraction을 나타내는 비트로 대우하는 것이다. 예를 들어, 우리는 32비트 정수에서 하위 14비츠를 fixed-point number representation으로 지정할 수 있어서, integer x는 x/2^14를 나타내는 것과 같다. 이것은 17.14 fixed-pont number representation이라 불리는데, 왜냐하면 decimal point이전에 17자리가 있고, 그것 이후에 14자리와 부호 비트가 있기 때문이다. 17.14 format은 (2^31-1)/2^14 ~~ 131,071.999쯤 된다.
만약 우리가 p.q 고정 소수점을 사용하고, f = 2^q라고 한다면, 위의 정의에 의해서 inter나 실수에 f를 곱해서 p.q 포맷으로 만들 수 있다. 예를 들어 59/60은 59/60 * 2^14를 곱해서 16,110으로 나타낼 수 있다. 다시 실수로 바꾸려면 f로 나눠주면 된다. C에서 나눗셈은 0으로 만들어버려서, 양수는 down을 하고 음수는 up시킨다. 그래서 근사를 하려면 f/2를 양의 수에 더하거나 음수에서 빼줘야한다. dividing 하기 전에)
fixed-point 연산은 straightforward하다. x와 y가 고정 소숫점 숫자이고, n이 정수라고 하자. x+y와 x-y는 그냥 하면 되지만, n을 더하려면 x+n*f를 해야하고 빼기는 x-n*f를 해야하고, 곱하기는 x*n, 나누기는 x/n이다.
두 고정소수점 숫자를 곱하는 것은 두 가지 복잡한 점이 있다. 첫째로 결과 소수점 자릿수가 q비트여야하는데, 왼쪽에서 너무 멀다는 것이다. 59/60 * 59/60은 1보다 약간 작지만 16,111 * 16,111은 259,564,321로 2^14보다 훨씬 크다. q비트 만큼 right하면 15,842라는 값이 나오고 이건 0.97로 적당하다.
두 번째로, 곱셈은 답이 표현가능하더라도 overflow를 야기시킬 수 있다. 17.14에서 64는 1,048,576인데, 65의 제곱, 4096은 엄청 커서 32비트 integer 값으로 표현이 안된다. 이런 거는 64비트 operation을 써야한다. x와 y의 곱셈은 ((int64_t)x)*y/f이다.
나누기는 완전히 반대인 문제를 낳는다. decimal point가 오른쪽에서 매우 떨어져있어서, 우리는 나누기를 하기 전에 q비트를 왼쪽으로 옮겨놔야한다. 왼쪽 시프트는 top q bits를 까먹게 되서, 우리는 이거를 64비츠로 나누면서 보정해줘야한다. 따라서 x가 y로 나눠질 때는 ((int64_t) x) * f /y 이다.
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
해야할거
1.
