2. Project 1: Threads#
在此作业中，我们为您提供最小功能线程系统。您的工作是扩展此系统的功能，以更好地了解同步问题。
您将主要在此任务的“threads”目录中工作，同时在“devices”目录中进行一些工作。编译应在“threads”目录中进行。
在阅读该项目的描述之前，您应该阅读以下所有部分：1.简介，C.编码标准，E.调试工具和F.开发工具。 您至少应阅读从A.1加载到A.5 内存分配的内容，尤其是[A.3 同步]。要完成此项目，您还需要阅读B. 4.4BSD Scheduler.
2.1 背景知识#
2.1.1 理解线程#
第一步是阅读和理解初始线程系统的代码。Pintos已经实现了线程创建和线程结束、一个在线程之间切换的简单调度程序、以及同步原语（信号量、锁、条件变量和优化屏障）。
某些代码似乎有些神秘。如果您尚未按照引言中的说明进行编译和运行基本系统（请参阅1.Introduction小节，则现在应该这样做。您可以通读部分源代码以了解发生了什么。如果愿意，您可以在几乎任何地方添加对printf()的调用，然后重新编译并运行以查看发生的情况和顺序。 您还可以在调试器中运行内核，并在感兴趣的地方设置断点，单步执行代码并检查数据，等等。
当线程创建后，您需要创建一个新的上下文用于调度。您提供一个将在此上下文中运行的函数，作为thread_create()的参数。线程第一次被调度并运行时，它从该函数的开头开始并在该上下文中执行。当函数返回时，线程终止。因此，每个线程的行为就像在Pintos中运行的小程序一样，传递给thread_create()的函数的行为就像main()一样。
在任意一个给定的时刻，只有一个线程在运行，其余线程（如果有的话）变为非活动状态。调度程序决定下一步运行哪个线程。（如果在某个给定时刻没有线程是就绪的，则运行在idle()中实现的特殊“idle”线程。）当一个线程需要等待另一个线程执行某个操作时，同步原语可以强制上下文切换.
上下文切换的机制位于“threads/switch.S”中，这是80x86的汇编代码。（您不必理解它。）它可以保存当前正在运行的线程的状态并恢复我们要切换的线程的状态。
使用GDB调试器，缓慢地跟踪上下文切换以查看发生了什么（请参见E.5 GDB部分。可以在schedule()上设置断点，然后从那里开始单步执行。(2)请确保跟踪每个线程的地址和状态，以及每个线程的调用堆栈上有哪些过程。您会注意到，当一个线程调用switch_threads()时，另一个线程开始运行，新线程要做的第一件事是从switch_threads()返回。一旦了解了为什么以及为什么调用的switch_threads()与返回的switch_threads())不同，您将了解线程系统。有关更多信息，请参见A.2.3线程切换部分。
警告：在Pintos中，为每个线程分配了一个大小小于4kB的小型固定大小的执行堆栈。内核试图检测堆栈溢出，但是不能完美地做到这一点。如果您将大型数据结构声明为非静态局部变量，例如“int buf[1000];”，可能会引起奇怪的问题，例如神秘的内核panic。堆栈分配的替代方法包括页面分配器和块分配器（请参阅A.5内存分配部分）。
2.1.2 源文件#
这是“threads”目录中文件的简要概述。您无需修改其中的大部分代码，但我们希望通过这个概述能使您了解从哪个代码入手。
“loader.S”\
“loader.h”\
内核加载器。组装成512字节的代码和数据，这些代码和数据将PC BIOS加载到内存中，然后依次在磁盘上找到内核、将其加载到内存中，并跳转到“start.S”中的“start()”。 有关详细信息，请参见A.1.1加载程序节。您无需完全弄懂这部分代码或对其进行修改。
start.S\
决定是否在80x86 CPU上进行内存保护和32位操作所需的基本设置。与加载程序不同，此代码实际上是内核的一部分。 有关详细信息，请参见A.1.2低级内核初始化。
kernel.lds.S\
用于链接内核的链接描述文件。设置内核的加载地址，并将start.S安排在内核映像的开头附近。有关详细信息，请参见A.1.1 加载程序部分。同样，您无需弄懂或修改此代码，但是如果你很好奇,你可以在这里查看。
init.c\
init.h\
内核初始化，包括内核的“主程序”, main()。您至少应查看main()以了解初始化了什么。您可能要在此处添加自己的初始化代码。有关详细信息，请参见A.1.3高级内核初始化部分。
thread.c\
thread.h\
基本线程支持。您的大部分工作将在这些文件中进行。thread.h定义了struct thread，您可能会在所有四个项目中对其进行修改。有关更多信息，请参见A.2.1 struct thread和A.2线程。
switch.S\
switch.h\
用于切换线程的汇编语言例程。上面已经讨论过了。有关更多信息，请参见A.2.2线程函数)部分。
palloc.c\
palloc.h\
页面分配器，以4kB页面的倍数分配系统内存。有关更多信息，请参见A.5.1页面分配器部分。
malloc.c\
malloc.h:\
内核的malloc()和free()的简单实现。 有关更多信息，请参见A.5.2块分配器部分。
interrupt.c\
interrupt.h\
基本中断处理和用于打开和关闭中断的功能。 有关更多信息，请参见A.4中断处理部分。
intr-stubs.S\
intr-stubs.h\
用于低级中断处理的汇编代码。 有关更多信息，请参见A.4.1 中断基础架构。
synch.c\
synch.h\
基本同步原语：信号量、锁、条件变量和优化屏障。您将需要在所有四个项目中使用它们进行同步。 有关更多信息，请参见A.3同步部分。
io.h\
I/O端口访问的函数。它主要由设备目录中的源代码使用，您暂时不用接触它们。
vaddr.h\
pte.h\
用于处理虚拟地址和页表条目的函数和宏。 在项目3中，这些对您而言将更为重要。现在，您可以忽略它们。
flags.h\
在80x86“标志”寄存器中定义几个位的宏。你可能不感兴趣。有关更多信息，请参见IA32-v1，第3.4.3节“EFLAGS寄存器”。
2.1.2.1 'devices' code#
基本的线程内核还包含在“devices”目录中的文件:
“timer.c”\
“timer.h”
默认情况下，每秒触发100次的系统计时器。 您将在此项目中修改此代码。
“vga.c”\
“vga.h”\
VGA显示驱动程序。 负责将文本写入屏幕。 您无需查看此代码。 printf()会为您调用VGA显示驱动程序，因此没有理由自己调用此代码。
“serial.c”\
“serial.h”
串行端口驱动程序。 同样，printf()会为您调用此代码，因此您无需自己这样做。 它通过将串行输入传递到输入层来对其进行处理（请参见下文）。
“block.c”\
“block.h”\
_block devices_的抽象层，即组织为固定大小的块数组的随机访问，类似磁盘的设备。 开箱即用，Pintos支持两种类型的块设备：IDE磁盘和分区。 块设备，无论类型如何，直到项目2才会真正使用。
“ide.c”\
“ide.h”\
支持最多4个IDE磁盘上的读写扇区。
“partition.c”\
“partition.h”\
了解磁盘上分区的结构，允许将单个磁盘划分为多个区域（分区）以供独立使用。
“kbd.c”\
“kbd.h”\
键盘驱动程序。 处理将击键传递到输入层的击键（请参见下文）。
“input.c”\
“input.h”\
输入层。 将键盘或串行驱动程序传递的输入字符放入队列。
“intq.c”\
“intq.h”\
中断队列，用于管理内核线程和中断处理程序都希望访问的循环队列。由键盘和串行驱动程序使用。
“rtc.c”\
“rtc.h”\
实时时钟驱动程序，使内核能够确定当前日期和时间。 默认情况下，“thread/init.c”仅使用它为随机数生成器选择初始种子。
“speaker.c”\
“speaker.h”\
可以在PC扬声器上产生声音的驱动程序。
“pit.c”\
“pit.h”\
用于配置8254可编程中断定时器的代码。 “devices/timer.c”和“devices/speaker.c”都使用此代码，因为每个设备都使用PIT的输出通道之一。
2.1.2.2 'lib' files#
最后，“lib”和“lib/kernel”包含有用的库例程。（“lib/user”将从项目2开始由用户程序使用，但它不是内核的一部分。）以下是一些详细信息：
“ctype.h”\
“inttypes.h”\
“limits.h”\
“stdarg.h”\
“stdbool.h”\
“stddef.h”\
“stdint.h”\
“stdio.c”\
“stdio.h”\
“stdlib.c”\
“stdlib.h”\
“string.c”\
“string.h”\
标准C库的子集。 请参阅C.2 C99部分，以获取您之前可能从未遇到过的C库的一些最新介绍的信息。请参阅C.3不安全的字符串函数，以获取有关出于安全考虑故意遗漏的信息。
“debug.c”\
“debug.h”\
函数和宏有助于调试。 参见E.调试工具，以获取更多信息。
“random.c”\
“random.h”\
伪随机数生成器。 除非您执行以下三种操作之一，否则从一次Pintos运行到另一次Pintos运行，实际的随机值序列不会改变：在每次运行时用"-rs"内核命令行选项上指定一个新的随机种子值、使用除Bochs外的其他模拟器，或在pintos中指定'-r'选项。
“round.h”\
用于取整的宏.
“syscall-nr.h”\
系统调用编号. 从项目2开始才用到.
“kernel/list.c”\
“kernel/list.h”\
双链表实现。 在所有Pintos代码中使用了该代码，您可能想在项目1中的一些地方使用它。
“kernel/bitmap.c”\
“kernel/bitmap.h”\
位图实现。 如果愿意，可以在代码中使用它，但是在项目1中可能不需要它。
“kernel/hash.c”\
“kernel/hash.h”\
哈希表的实现。 可能会在项目3中派上用场。
“kernel/console.c”\
“kernel/console.h”\
“kernel/stdio.h”\
实现printf()和其他一些函数。
2.1.3 Synchronization#
正确的同步是解决大部分问题的重要组成部分。通过关闭中断可以轻松解决任何同步问题：中断关闭时，没有并发性，因此没有竞争条件的可能性。所以，以这种方式解决所有同步问题很诱人，但是“不要”这样做。应该使用信号量、锁和条件变量来解决大部分同步问题。阅读同步部分的内容（请参见A.3 Synchronization部分.如果不确定在什么情况下可以使用什么同步原语，请参阅“threads/synch.c”中的注释。
在Pintos项目中，通过禁用中断解决同步的唯一一类问题是协调内核线程和中断处理程序之间共享数据。因为中断处理程序无法sleep，所以它们无法获取锁。这意味着必须通过关闭中断来保护内核线程和中断处理程序之间共享的数据。
本项目仅需要从中断处理程序访问一点线程状态。对于闹钟程序，计时器中断需要唤醒睡眠线程。在高级调度程序中，计时器中断需要访问一些全局变量和每个线程的变量。 当您从内核线程访问这些变量时，您将需要禁用中断以防止受到计时器中断的干扰。
当您关闭中断时，请注意，尽量减少代码量，否则将会丢失重要信息，例如计时器滴答声或输入事件。关闭中断还会增加中断处理延迟，如果中断处理的时间太长，可能会使机器呆滞。
“synch.c”中的同步原语本身通过禁用中断来实现。 您可能需要增加在此处禁用中断的情况下运行的代码量，但仍应尝试将其保持在最低水平。
禁用中断对于调试很有用，特别是你想要确保某段代码段不被打断的时候。在上交项目之前，应删除这些调试代码。（不要只注释掉它，因为那样会使代码难以阅读。）
您的提交中不应有忙-等待。 调用thread_yield()的循环是实现忙等待的一种形式。
2.1.4 Development Suggestions#
过去，许多小组将作业分成几部分，然后每个小组成员都按自己的方式工作，直到截止日期之前，这时该小组重新开会以合并其代码并提交。 这是一个坏主意。 我们不建议您使用这种方法。执行此操作的组通常会发现两个更改彼此冲突，因此需要大量的最后一刻调试。一些这样做的小组提交了甚至没有编译或引导的代码，更不用说通过任何测试了。
相反，我们建议您使用git之类的源代码控制系统，尽早并经常整合您团队的变更。这不太可能产生意外，因为每个人都可以在编写代码时看到其他人的代码，而不仅是在完成时。这些系统还使您可以检查更改，并且当更改引入错误时，可以恢复到正常的代码版本。
在完成此项目和后续项目时，你将会遇到很多无法理解的错误。如果是，请重新阅读调试工具的附录，其中包含了有用的调试技巧，这些技巧可以帮助您快速入门（请参见E. Debugging Tools。请务必阅读Backtrace部分（请参见E.4 Backtraces，这将帮助您最大程度地避免每次内核崩溃或断言失败。
2.2 Requirements#
2.2.1 Design Document#
在上交项目之前，必须将project 1设计文档模板复制到源代码树中，其名称为“pintos/src/threads/DESIGNDOC”并填写.我们建议您在开始进行项目之前阅读设计文档模板。有关示例，请参阅D.项目文档部分。 一个虚拟项目的设计文档。
2.2.2 Alarm Clock#
重新实现在“devices/timer.c”中定义的“timer_sleep()”。 尽管提供了一个可行的实现，但是它是“忙-等待”的，也就是说，它循环检查当前时间并调用thread_yield()直到足够的时间过去。重新实现它以避免忙等待。
Function: void timer_sleep (int64_t ticks)
-
暂停执行调用线程，直到时间提前至少x个计时器滴答为止。除非系统处于空闲状态，否则线程无需在精确的x滴答之后唤醒。他们等待正确的时间后，只需将其放在准备好的队列中即可。
-
timer_sleep()对于实时运行的线程很有用，例如 每秒闪烁一次光标。 -
“timer_sleep()”的参数以计时器刻度表示，而不是以毫秒或任何其他单位表示。每秒有TIMER_FREQ定时器滴答，其中TIMER_FREQ是在“devices/timer.h”中定义的宏。默认值为100。我们不建议更改此值，因为任何更改都可能导致许多测试失败.
确实有单独的函数“timer_msleep()”，“timer_usleep()”和“timer_nsleep()”，分别用于睡眠特定数量的毫秒，微秒或纳秒，但是这些函数会在必要时自动调用“timer_sleep()”。您不需要修改它们。
如果延迟似乎太短或太长，请重新阅读“pintos”中“-r”选项的说明(请参阅1.1.4调试与测试)。
后续项目不需要实现闹钟，尽管它可能对项目4很有用。
2.2.3 Priority Scheduling#
在Pintos中实施优先级调度。当将一个线程添加到具有比当前正在运行的线程更高的优先级的就绪列表时，当前线程应立即将处理器移交给新线程。同样，当线程正在等待锁、信号量或条件变量时，应首先唤醒优先级最高的线程。线程可以随时提高或降低其自身的优先级，但是降低其优先级以使其不再具有最高优先级时，则必须立即让出CPU。
线程优先级的范围是从PRI_MIN(0)到PRI_MAX(63)。较低的数字对应较低的优先级，因此优先级0是最低优先级，优先级63是最高优先级。 初始线程优先级作为参数传递给“ thread_create()”。如果没有理由选择其他优先级，则使用PRI_DEFAULT(31)。PRI_宏是在“threads/thread.h”中定义的，您不应更改其值。
优先级调度的一个问题是“优先级反转”。分别考虑高、中和低优先级线程H，M和L。如果H需要等待L（例如，对于由L持有的锁），而M在就绪列表中，然后H将永远无法获得CPU，因为低优先级线程不会获得任何CPU时间。解决此问题的部分方法是，当L持有锁时，H将其优先级“捐赠”给L。L释放（这样H可以获得）锁。
实施优先级捐赠。您将需要考虑适用于需要优先捐赠的所有不同情况。确保处理多个捐赠，其中将多个优先级捐赠给单个线程。您还必须处理嵌套捐赠：如果H正在等待M持有的锁，而M正在等待L持有的锁，则M和L都应提升为H的优先级。如有必要，您可以对嵌套优先级捐赠的深度进行合理假设，例如8个级别。
您必须实现锁的优先级捐赠。您无需为其他Pintos同步结构实现优先级捐赠。但需要在所有情况下都实施优先级调度。
最后，实现以下函数，这些函数允许线程检查和修改其自身的优先级。这些功能的框架在“threads/thread.c”中提供。
Function: void thread_set_priority (int new_priority )\ 将当前线程的优先级设置为new_priority。 如果当前线程不再具有最高优先级，则让出CPU。
Function: int thread_get_priority (void)\ 返回当前线程的优先级。 在存在优先级捐赠的情况下，返回较高（捐赠的）优先级。
您无需提供任何接口即可允许线程直接修改其他线程的优先级。
优先级调度程序在以后的项目中不再使用。
2.2.4 Advanced Scheduler#
实现类似于4.4BSD调度器的多级反馈队列调度程序，以减少在系统上运行作业的平均响应时间。 有关详细要求，请参见B.4.4BSD Scheduler节。
与优先级调度程序类似，高级调度程序根据优先级选择要运行的线程。但是，高级调度程序不会进行优先级捐赠。因此，我们建议您在开始使用高级调度程序之前，先进行优先级调度程序的工作，但可能需要优先级捐赠。
您必须编写代码，以允许我们在Pintos启动时选择调度算法策略。默认情况下，优先级调度程序必须处于活动状态，但是我们必须能够通过“-mlfqs”内核选项选择4.4BSD调度程序。传递此选项会将在“threads/thread.h”中声明的“thread_mlfqs”设置为true，当由parse_options()解析选项时会发生这种情况，这发生在main()的启动部分。
启用4.4BSD调度程序后，线程不再直接控制自己的优先级。 应该忽略对thread_create()的优先级参数以及对thread_set_priority()的任何调用，而对thread_get_priority()的调用应返回调度程序设置的线程的当前优先级。
在以后的任何项目中都不会使用高级调度程序。
2.3 FAQ#
我需要写多少代码?
-
这是由diffstat程序生成的参考解决方案的摘要。 最后一行给出了插入和删除的总行数； 更改的行将同时算作插入和删除。
-
参考解决方案仅代表一种可能的解决方案。其他解决方案也是可能的，其中许多与参考解决方案有很大不同。某些优秀的解决方案可能不会修改参考解决方案修改的所有文件，而某些解决方案可能会修改参考解决方案未修改的文件。
devices/timer.c | 42 +++++-
threads/synch.c | 88 +++++++++-
threads/thread.c | 196 ++++++++++++++++++++++++++----
threads/thread.h | 23 +++
4 files changed, 320 insertions(+), 29 deletions(-)
添加新的源文件时，如何更新“Makefile”？
-
要添加“.c”文件，请编辑顶层“
Makefile.build”。将新文件添加到变量dir_SRC中，其中dir是添加文件的目录。对于本项目，这意味着您应该将其添加到“threads_SRC”或“devices_SRC”中。然后运行make。如果您的新文件没有被编译，请运行“make clean”，然后重试。 -
当您修改顶层Makefile.build并重新运行make时，修改后的版本应自动复制到“threads/build/Makefile”中。反之则不成立，因此下次您从“threads”目录运行“make clean”时，所有更改都将丢失。除非您所做的更改确实是暂时的，否则您应该选择编辑“Makefile.build”.
-
新建“.h”文件不需要编辑“Makefile”.
出现 warning: no previous prototype for 'func' 是什么意思? \
+ 这意味着您定义了一个非静态函数，但没有原型。由于非静态函数旨在供其他.c文件使用，因此出于安全考虑，应在定义它们之前在头文件中对它们进行原型化。要解决此问题，请在您包含的头文件中添加一个原型，或者，如果该功能实际上未被其他“.c”文件使用，则使其成为静态函数。
定时器中断之间的间隔是多少? \ + 定时器中断每秒发生“TIMER_FREQ”次。 您可以通过编辑devices/timer.h来调整此值。默认值为100Hz。
- 我们不建议更改此值，因为任何更改都可能导致许多测试失败。
时间片多长时间? \ + 每个时间片都有“TIME_SLICE”个滴答。该宏在threads/thread.c中声明。默认值为4个滴答。
- 我们不建议更改此值，因为任何更改都可能导致许多测试失败.
如何运行测试? \ + 参见 1.2.1 Testing.
为什么我测试pass()失败了? \
+ 您可能碰到一个类似这样的回溯:
0xc0108810: debug_panic (lib/kernel/debug.c:32) \
0xc010a99f: pass (tests/threads/testsc:93) \
0xc010bdd3: test_mlfqs_load_1(...threads/mlfqs-load-1.c:33) \
0xc010a8cf: run_test (tests/threads/tests.c:51)\
0xc0100452: run_task (threads/init.c:283) \
0xc0100536: run_actions (threads/init.c:333) \
0xc01000bb: main (threads/init.c:137)
-
这其实是因为backtrace程序输出了令人困惑的内容。实际上并不意味着pass()调用了debug_panic()。实际上，是fail()调用了debug_panic()（通过PANIC()宏）。GCC知道debug_panic()不返回，因为它被声明为NO_RETURN（请参阅E.3函数和参数属性)”部分），因此在fail()中不包含任何代码能在debug_panic()返回时获得控制权，这意味着堆栈上的返回地址看起来就像是函数的开头，恰好跟随在内存中的fail()之后，在这种情况下恰好是pass()。
-
参见E.4 Backtraces部分，以获取更多信息。
schedule()之后的新线程是如何重新启用中断的? \
进入“schedule()”的每条路径均禁用中断。最终，它们将由要调度的下一个线程重新启用。考虑一下可能性：新线程正在switch_thread()中运行（但请参见下文），由schedule()调用，该函数可能被以下函数之一调用:
- thread_exit(), 但是我们永远不会切换回这样的线程，所以这个没什么意义.
- thread_yield(), 立即恢复从“schedule()”返回的中断级别.
- thread_block(), 它可以从好几个地方被调用:
-
- sema_down(), 返回前恢复中断级别.
-
- idle(), 用一条显式的汇编STI指令使能中断.
-
- wait() 在"devices/intq.c"中,其调用者负责重新启用中断.
- 特殊情况是新创建的线程首次运行时。这样的线程将intr_enable()作为kernel_thread()中的第一个操作，该操作位于每个内核线程（而不是第一个）的调用堆栈的底部。
2.3.1 Alarm Clock FAQ#
我是否需要考虑定时器值溢出? \ 不必担心定时器值溢出的可能性。计时器值表示为带符号的64位数字，以每秒100个滴答的速度运行将近2,924,712,087年。届时，我们希望Pintos已被CS140课程逐步淘汰.
2.3.2 Priority Scheduling FAQ#
优先级调度不会导致饥饿吗？
是的，严格的优先级调度可能会导致饥饿，因为如果有任何更高优先级的线程可运行，则该线程将不会运行。高级调度程序引入了一种用于动态更改线程优先级的机制。
严格的优先级调度在实时系统中非常重要，因为它为程序员提供了更多控制权，让他们可以控制哪些作业获得处理时间。通常将高优先级保留给时间紧迫的任务。这不是“公平的”，但是它解决了不适用于通用操作系统的其他问题。
锁释放后应该运行什么线程?
释放锁后，等待该锁的优先级最高的线程应解除阻止,并放在就绪线程列表中。然后，调度程序应在就绪列表上运行优先级最高的线程。
如果优先级最高的线程让出CPU(yield)，它将继续运行吗?
是。如果只有一个优先级最高的线程，则即使调用thread_yield()，它也会继续运行直到阻塞或完成。如果多个线程具有相同的最高优先级，thread_yield()应该以“round robin”顺序在它们之间切换。
捐赠线程的优先级发生了什么?
优先级捐赠仅会更改被捐赠线程的优先级。捐献者线程的优先级保持不变。优先级捐赠不是累加的：如果线程A（优先级5）捐赠给线程B（优先级3），则B的新优先级是5，而不是8。
就绪队列中的线程的优先级可以更改吗? 是。考虑一个就绪的，低优先级的线程L，它持有一个锁。 高优先级线程H尝试获取锁并但被阻塞，从而将其优先级捐赠给就绪线程L。
线程被阻止时，其优先级是否可以更改?
是。当已获得锁L的线程由于任何原因而被阻塞，但是如果此时优先级较高的线程尝试获取L，则其优先级可以通过优先级捐赠来增加。通过“priority-donate-sema”测试来检查这种情况。
添加到就绪列表的线程是否可以抢占处理器?
是。 如果添加到就绪列表的线程比正在运行的线程具有更高的优先级，则正确的行为是立即让处理器退出。 等待下一个定时器中断是不可接受的。 优先级最高的线程应尽快运行，以抢占当前正在运行的任何线程。
thread_set_priority() 如何影响接受捐赠的线程?
它设置线程的基本优先级。线程的有效优先级变为新设置的优先级或最高捐赠优先级中的较高者。释放捐赠后，线程的优先级将成为通过函数调用设置的优先级。此行为在priority-donate-lower中测试.
Doubled test names in output make them fail.
假设您看到这样的输出，其中一些测试名称被输出两次，像这样:
(alarm-priority) begin
(alarm-priority) (alarm-priority) Thread priority 30 woke up.
Thread priority 29 woke up.
(alarm-priority) Thread priority 28 woke up.
发生的情况是两个线程的输出被交错。即，一个线程正在打印"(alarm-priority) Thread priority 29 woke up.\n" 同时另一个线程正在打印 "(alarm-priority) Thread priority 30 woke up.\n", 但是第一个线程在其输出中间被第二个线程抢占。
此问题表明优先级调度程序中存在错误。 毕竟，当优先级为30的线程有工作要做时，优先级为29的线程应该无法运行。
通常，Pintos内核中printf()函数的实现试图通过在printf调用期间获取控制台锁并随后释放它来防止这种交错输出。但是，使用两次对printf的调用来输出测试名称（例如(alarm-priority),及其后的消息的输出，导致控制台锁被获取并释放两次。
2.3.3 Advanced Scheduler FAQ#
优先级捐赠如何与高级调度程序交互? \ 不必。我们不会同时测试优先级捐赠和高级调度程序。
我可以使用一个队列而不是64个队列吗? \ 是。 通常，您的实现可以与描述不同，只要其行为相同即可。
一些调度程序测试失败，我不明白为什么。救命! \ 如果您的高级调度程序的实现有一些神秘的测试失败，请尝试以下操作： - 阅读失败的测试的源文件，以确保您了解正在发生的事情。每个文件在顶部都有一条注释，解释其目的和预期结果。 - 仔细检查定点算术例程，并在调度程序例程中使用它们。 - 检查一下您的实现中，计时器中断做了哪些工作。如果计时器中断处理程序花费的时间太长，那么被计时器中断抢占的线程就会丢失大量的计时器滴答。当将控制权交回给该线程时，在下一个计时器中断到达之前，该线程将不会做很多工作。因此，该线程将因得到更多的CPU时间而受到指责，但实际上它并没有使用那么多。这会增加被中断线程的最近CPU计数，从而降低其优先级。这可能导致调度策略发生变化。同时这也会提高平均负载。