B. 4.4BSD Scheduler#
通用调度程序的目标是平衡线程的不同调度需求。那些执行大量I/O操作的线程需要快速的响应时间，以保持输入和输出设备繁忙，但只需很少的CPU时间。另一方面，计算密集的线程需要接收大量CPU时间完成计算，但无需快速的响应时间。其他线程介于两者之间，I/O周期和计算周期交替执行，因此随着时间变化会有不同需求。设计良好的调度程序通常可以接纳所有不同要求类型的线程。
对于项目1，您必须实现本附录中描述的调度程序。我们的调度程序类似于McKusick中描述的调度程序，它是多级反馈队列调度程序的一个示例。这种类型的调度程序维护着几个准备运行的线程队列，其中每个队列包含具有不同优先级的线程。在任何给定时间，调度程序都会从优先级最高的非空队列中选择一个线程。如果最高优先级队列包含多个线程，则它们以“轮转(round robin)”顺序运行。
调度程序有几处要求在一定数量的计时器滴答之后更新数据。在每种情况下，这些更新应在任何普通内核线程有机会运行之前进行，这样内核线程就不可能看到新增加的“timer_ticks()”值,只能看到旧的调度程序数据值。
4.4BSD调度程序不包括优先级捐赠。
B.1 Niceness#
线程优先级由调度程序使用下面给出的公式动态确定。但是，每个线程还有一个整数nice值，该值确定该线程与其他线程应该有多“不错”。nice为零不会影响线程优先级。正的nice（最大值为20）会降低线程的优先级，并导致该线程放弃原本可以接收的CPU时间。另一方面，负的nice，最小为-20，往往会占用其他线程的CPU时间。
初始线程以nice值为零开始。其他线程以从其父线程继承的nice值开始。您必须实现下面描述的功能，供测试程序使用。我们已经在“threads/thread.c”中为其提供了骨架定义。
Function: int thread_get_nice (void)
返回当前线程的nice值。
Function: void thread_set_nice (int new_nice)
将当前线程的nice值设置为new_nice，并根据新值重新计算线程的优先级（请参阅B.2计算优先级）。如果正在运行的线程不再具有最高优先级，则让出。
B.2 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和nice上分别为1/4和2的系数在实践中效果很好，但缺乏更深层的含义。计算得到的priority将始终调整为处于PRI_MIN至PRI_MAX的范围内。
该公式把最近获得CPU时间的线程赋予较低的优先级，以便在下次调度程序运行时重新分配CPU。这是防止饥饿的关键：最近未获得任何CPU时间的线程的recent_cpu为0，除非高nice值，否则它很快会获得CPU时间。
B.3 计算recent_cpu#
我们希望recent_cpu测量每个进程“最近”获得了多少CPU时间。此外，作为改进，距离现在更近的CPU时间应比相对较旧的CPU时间拥有更大的权重。一种方法是使用n个元素的数组来跟踪最近n秒中的每秒钟收到的CPU时间。但是，这种方法每个线程需要O（n）个空间，并且每次计算新的加权平均值都需要O（n）个时间。
相反，我们使用指数加权移动平均值，它采用以下一般形式：
其中x(t)是整数时间t>=0时的移动平均值，f(t)是要平均的函数，而k>0控制衰减率。我们可以按照以下步骤迭代公式：
f(t)的值在时间t的权重为1，在时间t+1的权重为a，在时间t+2的权重为a**2，依此类推。我们还可以将x(t)与k关联：f(t)在时间t+k时权重约为1/e，在时间t+2*k时权重约为1/e**2，依此类推 。从相反的方向，f(t)在时间t+ln(w)/ln(a)衰减到权重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的当前值衰减到权重0.1的时间为 ln（.1）/ln（2/3）= 约6秒；如果load_avg为2，则衰减到0.1的权重大约需要ln(.1)/ln(3/4)= 约8秒。结果是recent_cpu估计线程“最近”接收到的CPU时间，衰减率与争用CPU的线程数成反比。
某些测试所作的假设要求，当系统刻度计数器达到一秒的倍数时，即，当timer_ticks()％TIMER_FREQ == 0时，准确地进行recent_cpu 的重新计算。而不是其他任何时间。
对于nice值为负的线程，recent_cpu的值可以为负。不要将负的recent_cpu强制设为0。
您可能需要考虑此公式中的计算顺序。我们建议先计算recent_cpu的系数，然后相乘。一些学生报告说，将load_avg与recent_cpu直接相乘会导致溢出。
您必须实现“thread_get_recent_cpu()”，代码框架在“threads/thread.c”。
Function: int thread_get_recent_cpu (void)
返回当前线程的recent_cpu值的100倍，四舍五入到最接近的整数。
B.4 计算 load_avg#
最后，load_avg（通常称为系统平均负载）估计过去一分钟准备运行的线程的平均值。与recent_cpu一样，它是指数加权的移动平均值。与priority和recent_cpu不同，load_avg是系统级的，而不是特定于线程的。在系统引导时，它将初始化为0。此后每秒一次，将根据以下公式进行更新：
load_avg = (59/60)*load_avg + (1/60)*ready_threads
其中ready_threads是在更新时正在运行或准备运行的线程数（不包括空闲线程）。
由于某些测试的假设，load_avg必须在系统滴答计数器达到一秒的倍数时（即，当timer_ticks()％TIMER_FREQ == 0 时准确更新，而不是其他任何时间。
您必须实现thread_get_load_avg()，在threads/thread.c中提供了代码框架。
Function: int thread_get_load_avg (void)
返回当前系统平均负载的100倍，四舍五入到最接近的整数。
B.5 小结#
以下公式总结了实现调度程序所需的计算。它们不是调度程序要求的完整描述。
每个线程直接在其控制下的nice值在-20和20之间。每个线程还有一个优先级，介于0（PRI_MIN）到63（PRI_MAX）之间，每四个刻度使用以下公式重新计算一次：
priority = PRI_MAX - (recent_cpu / 4) - (nice * 2).
recent_cpu测量线程“最近”接收到的CPU时间。在每个计时器滴答中，运行线程的recent_cpu递增1。每秒一次，每个线程的recent_cpu都以这种方式更新：
recent_cpu = (2*load_avg)/(2*load_avg + 1) * recent_cpu + nice.
load_avg估计过去一分钟准备运行的平均线程数。它在引导时初始化为0，并每秒重新计算一次，如下所示：
load_avg = (59/60)*load_avg + (1/60)*ready_threads.
其中ready_threads是在更新时正在运行或准备运行的线程数（不包括空闲线程）。
B.6 Fixed-Point Real Arithmetic#
在上面的公式中，priority，nice和ready_threads是整数，而recent_cpu和load_avg 是实数。不幸的是，Pintos在内核中不支持浮点运算，因为它会使内核复杂化并减慢其速度。出于相同的原因，实际内核通常具有相同的限制。这意味着必须使用整数来模拟实际数量的计算。这并不困难，但是许多学生不知道该怎么做。本节介绍基本知识。
基本思想是将一个整数的最右边位用来表示小数。例如，我们可以将带符号的32位整数的最低14位指定为小数位，这样整数x就表示实数x/2**14），其中**表示幂。这被称为17.14定点数字表示形式，因为小数点前有17位，小数点后有14位，还有一个符号位。[(7)] 以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中的常规“/”运算符会四舍五入为零，即将正数向下舍入，将负数向上舍入。要舍入到最接近的值，请将f/2加到正数或减去它从负数开始，然后除。）
定点数字上的许多操作都很简单。设x和y为定点数，设n为整数。那么x和y的和就是x + y，它们的差就是x-y。x和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 = 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”。
由于两个原因，本节始终使用乘或除以f而不是q位移位。首先，乘法和除法没有C移位运算符的令人惊讶的运算符优先级。 其次，乘法和除法在负操作数上定义明确，但C移位运算符则没有。在实施中请注意这些问题。
下表总结了如何在C中实现定点算术运算。在该表中，“x”和“y”是定点数，“n”是整数，定点数采用带符号pq格式，其中 p + q = 31，而f为1 << q：
------------------------------------------------ -----------------------------------
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`
------------------------------------------------ -----------------------------------