本实验将让你熟悉多线程。你将 实现用户级线程包中的线程切换， 使用多线程加速程序，并实现一个屏障。
在编写代码之前，你应该确保已经阅读了xv6手册中的"第7章：调度"并研究了相应的代码。
开始实验前，切换到 thread 分支：
$ git fetch $ git checkout thread $ make clean
在本练习中，你将设计并实现一个用户级线程系统的上下文切换机制。为了帮助你入门，你的 xv6 有两个文件 user/uthread.c 和 user/uthread_switch.S，以及 Makefile 中用于构建 uthread 程序的一条规则。uthread.c 包含了用户级线程包的大部分代码，以及三个简单测试线程的代码。 该线程包缺少一些用于创建线程和在线程之间切换的代码。
你的任务是制定一个创建线程以及保存/恢复寄存器以在线程之间切换的方案，并实现该方案。 完成后， make grade 应该显示你的解决方案通过了 uthread 测试。
$ make qemu ... $ uthread thread_a started thread_b started thread_c started thread_c 0 thread_a 0 thread_b 0 thread_c 1 thread_a 1 thread_b 1 ... thread_c 99 thread_a 99 thread_b 99 thread_c: exit after 100 thread_a: exit after 100 thread_b: exit after 100 thread_schedule: no runnable threads $
这些输出来自三个测试线程，每个线程都有一个循环，打印一行内容然后让出 CPU 给其他线程。
然而，此时由于没有上下文切换代码，你将看不到任何输出。
你需要在 user/uthread.c 中的 thread_create() 和 thread_schedule() 中添加代码，以及在 user/uthread_switch.S 中的 thread_switch 中添加代码。 一个目标是确保当 thread_schedule() 第一次运行某个线程时，该线程在自己的栈上执行传递给 thread_create() 的函数。 另一个目标是确保 thread_switch 保存被切换出去的线程的寄存器，恢复被切换进来的线程的寄存器，并返回到后者的指令中上次离开的位置。 你将需要决定在哪里保存/恢复寄存器；修改 struct thread 以保存寄存器是一个好方案。 你需要在 thread_schedule 中添加对 thread_switch 的调用； 你可以向 thread_switch 传递任何你需要的参数， 但目的是从线程 t 切换到 next_thread。
一些提示：
(gdb) file user/_uthread Reading symbols from user/_uthread... (gdb) b uthread.c:60
这在 uthread.c 的第 60 行设置了一个断点。 这个断点可能在你运行 uthread 之前就被触发（也可能不会）。这是怎么发生的？
当你的 xv6 shell 运行后，输入 "uthread"，gdb 将在第 60 行中断。 现在你可以输入如下命令来检查 uthread 的状态：
(gdb) p/x *next_thread使用 "x"，你可以检查内存位置的内容：
(gdb) x/x next_thread->stack
你可以这样跳到 thread_switch 的开头：
(gdb) b thread_switch (gdb) c
你可以使用以下命令单步执行汇编指令：
(gdb) si
gdb 的在线文档在这里。
在本作业中，你将使用哈希表探索线程和锁的并行编程。你应该在一台具有多核的真实 Linux 或 MacOS 计算机（不是 xv6，不是 qemu）上完成本作业。大多数最近的笔记本电脑都有多核处理器。
本作业使用 UNIX pthread 线程库。 你可以从手册页中获取相关信息，使用 man pthreads，也可以在网上查找，例如 这里、 这里和 这里。
文件 notxv6/ph.c 包含一个简单的哈希表，如果从单线程使用是正确的，但从多线程使用时则不正确。 在你的 xv6 主目录中（可能是 ~/xv6-labs-2020），输入以下内容：
$ make ph $ ./ph 1注意，构建 ph 时 Makefile 使用的是你操作系统的 gcc，而不是 6.S081 的工具。 ph 的参数指定执行哈希表 put 和 get 操作的线程数。 运行一段时间后，ph 1 将产生类似以下的输出：
100000 puts, 3.991 seconds, 25056 puts/second 0: 0 keys missing 100000 gets, 3.981 seconds, 25118 gets/second
你看到的数字可能与示例输出相差两倍以上，这取决于你的计算机速度、是否有多核以及是否正在忙于处理其他事情。
ph 运行两个基准测试。首先通过调用 put() 将大量键添加到哈希表中，并打印每秒 put 操作的速率。然后使用 get() 从哈希表中获取键。它打印出由于 put 操作应该存在于哈希表中但缺失的键数（此情况下为零），以及每秒 get 操作的速率。
你可以通过给 ph 一个大于 1 的参数来让它同时使用多个线程操作哈希表。试试 ph 2：
$ ./ph 2 100000 puts, 1.885 seconds, 53044 puts/second 1: 16579 keys missing 0: 16579 keys missing 200000 gets, 4.322 seconds, 46274 gets/second
ph 2 输出的第一行表明，当两个线程同时向哈希表添加条目时，它们达到了每秒 53,044 次插入的总速率。这大约是运行 ph 1 单线程速率的两倍。这是一个很好的"并行加速"，大约 2 倍，是所能期望的最大加速（即两倍的核心产生两倍的工作量）。
然而，显示 16579 keys missing 的两行表明，大量应该存在于哈希表中的键不在其中。也就是说，put 操作本应将那些键添加到哈希表中，但出了些问题。 请查看 notxv6/ph.c，特别是 put() 和 insert()。
为了避免这种事件序列，在 notxv6/ph.c 中的 put 和 get 中插入 lock 和 unlock 语句，使得在两个线程时缺失的键数始终为 0。相关的 pthread 调用有：
pthread_mutex_t lock; // declare a lock pthread_mutex_init(&lock, NULL); // initialize the lock pthread_mutex_lock(&lock); // acquire lock pthread_mutex_unlock(&lock); // release lock
当 make grade 显示你的代码通过了 ph_safe 测试时，你就完成了，该测试要求两个线程时缺失的键数为零。 此时 ph_fast 测试失败是可以的。
不要忘记调用 pthread_mutex_init()。 先用 1 个线程测试你的代码，然后用 2 个线程测试。 它是否正确（即你是否消除了缺失的键？）？ 双线程版本相对于单线程版本是否实现了并行加速（即每单位时间更多的总工作量）？
在某些情况下，并发的 put() 在哈希表中读写内存时没有重叠，因此不需要锁来相互保护。 你能否修改 ph.c 以利用这种情况来获得某些 put() 的并行加速？ 提示：每个哈希桶使用一个锁怎么样？
修改你的代码，使得某些 put 操作可以并行运行，同时保持正确性。 当 make grade 显示你的代码同时通过了 ph_safe 和 ph_fast 测试时，你就完成了。 ph_fast 测试要求两个线程每秒产生的 put 操作数至少是单线程的 1.25 倍。
在本作业中，你将实现一个屏障： 应用程序中的一个点，所有参与的线程必须等待，直到所有其他参与的线程也到达该点。你将使用 pthread 条件变量，这是一种类似于 xv6 的 sleep 和 wakeup 的序列协调技术。
你应该在真实计算机上完成本作业（不是 xv6，不是 qemu）。
文件 notxv6/barrier.c 包含一个有缺陷的屏障。
$ make barrier $ ./barrier 2 barrier: notxv6/barrier.c:42: thread: Assertion `i == t' failed.2 指定了在屏障上同步的线程数（barrier.c 中的 nthread）。每个线程执行一个循环。在每次循环迭代中，线程调用 barrier() 然后随机休眠若干微秒。断言触发了，因为一个线程在另一个线程到达屏障之前就离开了屏障。期望的行为是每个线程在 barrier() 中阻塞，直到所有 nthreads 个线程都调用了 barrier()。
你的目标是实现期望的屏障行为。除了你在 ph 作业中见过的锁原语之外，你还需要以下新的 pthread 原语；详情请查看这里和这里。
pthread_cond_wait(&cond, &mutex); // go to sleep on cond, releasing lock mutex, acquiring upon wake up pthread_cond_broadcast(&cond); // wake up every thread sleeping on cond
确保你的解决方案通过 make grade 的 barrier 测试。
我们已经提供了 barrier_init()。你的任务是实现 barrier()，使得 panic 不会发生。 我们已经为你定义了 struct barrier；其字段供你使用。
有两个问题使你的任务变得复杂：
使用一个、两个和两个以上的线程测试你的代码。
实验到此完成。确保你通过了所有 make grade 测试。如果本实验有问题，不要忘记将你的答案写入 answers-lab-name.txt。提交你的更改（包括添加 answers-lab-name.txt）并在实验目录中输入 make handin 来提交你的实验。
创建一个新文件 time.txt，在其中放入一个整数，表示你在本实验上花费的小时数。不要忘记 git add 和 git commit 该文件。
提交实验
花费时间
提交
你将使用提交网站提交你的作业。在提交任何作业或实验之前，你需要从提交网站申请一次 API 密钥。
在提交你对实验的最终更改后，输入 make handin 来提交你的实验。
$ git commit -am "ready to submit my lab"
[util c2e3c8b] ready to submit my lab
2 files changed, 18 insertions(+), 2 deletions(-)
$ make handin
tar: Removing leading `/' from member names
Get an API key for yourself by visiting https://6828.scripts.mit.edu/2020/handin.py/
Please enter your API key: XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
% Total % Received % Xferd Average Speed Time Time Time Current
Dload Upload Total Spent Left Speed
100 79258 100 239 100 79019 853 275k --:--:-- --:--:-- --:--:-- 276k
$
make handin 会将你的 API 密钥存储在 myapi.key 中。如果你需要更改 API 密钥，只需删除此文件并让 make handin 重新生成（myapi.key 不能包含换行符）。
如果你运行 make handin 时有未提交的更改或未跟踪的文件，你将看到类似以下的输出：
M hello.c ?? bar.c ?? foo.pyc Untracked files will not be handed in. Continue? [y/N]检查上述行，确保你的实验解决方案所需的所有文件都已跟踪，即不在以 ?? 开头的行中列出。 你可以使用 git add filename 让 git 跟踪你创建的新文件。
如果 make handin 无法正常工作， 尝试修复 curl 或 Git 命令的问题。 或者你可以运行 make tarball。 这将为你生成一个 tar 文件，然后你可以通过我们的网页界面上传。
用户级线程包与操作系统在多个方面交互不良。例如，如果一个用户级线程在系统调用中阻塞，另一个用户级线程将不会运行，因为用户级线程调度器不知道其中一个线程已被 xv6 调度器取消调度。又如，两个用户级线程不会在不同的核心上并发运行，因为 xv6 调度器不知道有多个线程可以并行运行。注意，如果两个用户级线程真正并行运行，这个实现将无法工作，因为存在多个竞争条件（例如，不同处理器上的两个线程可能同时调用 thread_schedule，选择同一个可运行线程，并在不同处理器上运行它）。
有几种方法可以解决这些问题。一种是使用调度器激活，另一种是每个用户级线程使用一个内核线程（如 Linux 内核所做的那样）。在 xv6 中实现其中一种方法。这不容易做对；例如，当为多线程用户进程更新页表时，你将需要实现 TLB 刷新。
向你的线程包添加锁、条件变量、屏障等。