本实验前去看《操作系统导论》第29章基于锁的并发数据结构，将会是很有帮助的。

前言

在做MIT 6.S081的实验过程中，每看一些讲座(lecture)和xv6 book就来做相应的实验。这个实验是让我最爽的两个实验之一（还有一个是trap），因为其他大多c语言，在我已经有了很多关于操作系统的知识的情况下，实现并没有那么的让人惊艳，但是这个实验确实让人非常惊艳。

这个实验里面的进程切换、线程切换，以前我确实知道怎么做的，但是像这样通过改变寄存器的值，以前我是没有想到的，所以以前只知道要保存状态，但是对于如何保存不知道原理，这次实验的过程中，通过理解源码，懂了这个，很神奇的东西。

调度

实现多路复用（multiplexing）的挑战：

1. 如何从一个进程切换到另一个进程？尽管上下文切换的思想很简单，但它的实现是xv6中最不透明的代码之一
2. 如何以对用户进程透明的方式强制切换？xv6使用标准技术，通过定时器终端驱动上下文切换
3. 许多CPU可能同时在进程之间切换，使用一个锁方案来避免争用是很有必要的
4. 进程退出时必须释放进程的内存以及其他资源，但它不能自己完成所有这一切，因为它不能在仍然使用自己内核栈的情况下释放它
5. 多核机器的每个核心都必须记住它正在执行哪个进程，以便系统调用正确影响对应进程的内核状态
6. sleep运行一个进程放弃CPU，wakeup允许另一个进程唤醒第一个进程。需要小心避免唤醒通知丢失的竞争。

Uthread: switching between threads (moderate)

在本练习中，您将为用户级线程系统设计上下文切换机制，然后实现它。首先，您的xv6有两个文件user/uthread.c和user/uthread_switch.S，并且Makefile中有一个规则来构建uthread程序。uthread.c包含大部分用户级线程包，以及三个简单测试线程的代码。线程程序包缺少一些用于创建线程和在线程之间切换的代码。

实验任务

您的工作是制定一个创建线程和保存/恢复寄存器以在线程之间切换的计划，并实现该计划。完成后，make grade应该表明您的解决方案通过了uthread测试。

完成后，当您在xv6上运行uthread时，您应该会看到以下输出（这三个线程可能以不同的顺序启动）：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KHSla5rT-1690632901891)(Images/Screenshot from 2023-07-27 18-43-03.png)]

这个输出来自三个测试线程，每个线程都有一个循环，打印一行，然后将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的调用；您可以向threadswitch传递所需的任何参数，但目的是从threadt切换到nextthread。

Hints

• thread_switch仅仅需要保存被调用者保存寄存器吗，为什么？

  答：是，其他调用者保存寄存器已经在调用thread_swtich时保存在当前线程的栈上。

• 你能在user/uthread.asm中看到uthread的汇编代码，可能更方便调试

• 为了测试你的代码，使用gdb单步调试thread_switch将是有用的，你可以通过这种方式开始：

  (gdb) file user/_uthread
  Reading symbols from user/_uthread...
  (gdb) b uthread.c:60
  

  这将在uthread.c的第60行设置断点。断点可能（也可能不）在您运行uthread之前被触发。这怎么可能发生？

  一旦xv6shell运行，键入“uthread”，gdb将在第60行中断。如果您从另一个进程中遇到了断点，请继续进行，直到您在uthread进程中遇到断点为止。现在，您可以键入以下命令来检查uthread的状态：

  (gdb) p/x *next_thread
  

  使用“x”，您可以检查内存位置的内容：

  (gdb) x/x next_thread->stack
  

  您可以跳到thread_switch的开头，这样：

  (gdb) b thread_switch
  (gdb) c
  

  单步执行汇编代码

  (gdb) si
  

  gdb的在线文档 is here.

解决方案

thread_switch

  .text/** save the old thread's registers,* restore the new thread's registers.*/.globl thread_switch
thread_switch:/* YOUR CODE HERE */sd ra, 0(a0)sd sp, 8(a0)sd s0, 16(a0)sd s1, 24(a0)sd s2, 32(a0)sd s3, 40(a0)sd s4, 48(a0)sd s5, 56(a0)sd s6, 64(a0)sd s7, 72(a0)sd s8, 80(a0)sd s9, 88(a0)sd s10, 96(a0)sd s11, 104(a0)ld ra, 0(a1)ld sp, 8(a1)ld s0, 16(a1)ld s1, 24(a1)ld s2, 32(a1)ld s3, 40(a1)ld s4, 48(a1)ld s5, 56(a1)ld s6, 64(a1)ld s7, 72(a1)ld s8, 80(a1)ld s9, 88(a1)ld s10, 96(a1)ld s11, 104(a1)ret    /* return to ra */

thread_create()

void 
thread_create(void (*func)())
{struct thread *t;for (t = all_thread; t < all_thread + MAX_THREAD; t++) {if (t->state == FREE) break;}t->state = RUNNABLE;// YOUR CODE HERE// 设置线程栈，设置返回返回地址，调用线程调度函数t->context.sp = (uint64)(t->stack + STACK_SIZE);t->context.ra = (uint64)func;     // 使得在func处返回
}

thread_schedule()

void 
thread_schedule(void)
{...if (current_thread != next_thread) {         /* switch threads?  */next_thread->state = RUNNING;t = current_thread;current_thread = next_thread;/* YOUR CODE HERE* Invoke thread_switch to switch from t to next_thread:* thread_switch(??, ??);*/// 恢复当前进程的上下文，保存上一个进程t的上下文，此时会自动从上一个切换的上下文位置切换// 这里会破坏a0和a1thread_switch((uint64)&t->context, (uint64)&current_thread->context);} elsenext_thread = 0;
}

Using threads (moderate)

在本次作业中，您将探索使用哈希表使用线程和锁进行并行编程。您应该在具有多个核心的真实Linux或MacOS计算机（不是xv6，不是qemu）上执行此任务。最新的笔记本电脑都有多核处理器。

此作业使用UNIX pthread线程库。您可以通过man phreads从手册页中找到有关它的信息，也可以在网上查看，例如here, here, and here.

文件notxv6/ph.c包含一个简单的哈希表，如果从单个线程使用，该哈希表是正确的，但如果从多个线程使用，则该哈希表不正确。在您的xv6主目录（可能~/xv6-labs-2021）中，键入以下内容：

$ 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（）将大量键添加到哈希表中，并以每秒puts为单位打印实现的速率。它使用get（）从哈希表中获取密钥。它打印由于put而应该在哈希表中但丢失的数字键（在这种情况下为零），并打印每秒获得的次数。

您可以告诉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

该ph2输出的第一行表明，当两个线程同时向哈希表添加条目时，它们的总插入率为每秒53044次。这大约是运行ph1的单个线程的速率的两倍。这是一个大约2倍的出色“并行加速”，这是人们所希望的（即每单位时间产生两倍功的两倍内核）。

然而，缺少16579个键的两行表示哈希表中不存在大量本应存在的键。也就是说，puts本应将这些键添加到哈希表中，但出现了问题。看看notxv6/ph.c，特别是put（）和insert（）。

实验任务

• 为什么2个线程的时会缺少一些key，而1个线程时没有缺少key？识别能在两个线程时导致键缺失的代码片。在answers-thread.txt中提交您的序列并附上简短解释

  答：在put和insert函数中都可能发生错误

  static void 
  insert(int key, int value, struct entry **p, struct entry *n)
  {struct entry *e = malloc(sizeof(struct entry));e->key = key;e->value = value;e->next = n;*p = e;
  }static 
  void put(int key, int value)
  {int i = key % NBUCKET;// is the key already present?struct entry *e = 0;for (e = table[i]; e != 0; e = e->next) {if (e->key == key)break;}if(e){// update the existing key.e->value = value;} else {// the new is new.insert(key, value, &table[i], table[i]);}
  }
  

  假设现在有一个线程运行到第7行，此时添加的key为1，在执行第八行前，另一个线程刚好在put中搜索key=1是否存在，当然此时的结果是不存在，所以会被插入，此时key=1被重复插入了导致错误。

  另一个问题是，同样假设当前两个线程均运行到第7行，此时会导致×p的更新只有一个更新有效，导致key缺失。

• 为了避免这种事件序列，请在notxv6/ph.c中的put和get中插入lock和unlock语句，以便在两个线程中丢失的key数始终为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测试是可以的（也就是说只要我们自己测试，没有missing就行）。

解决方案

在原始代码单线程情况下，我的机器的输出如下

$ ./ph 1
100000 puts, 10.889 seconds, 9183 puts/second
0: 0 keys missing
100000 gets, 11.494 seconds, 8700 gets/second

在修改后，给每个table一个锁，加在上面展现的代码的地16行和第28行的位置，编译程序，得到的双线程结果是

$ ./ph 2
100000 puts, 5.834 seconds, 17140 puts/second
0: 0 keys missing
1: 0 keys missing
200000 gets, 10.783 seconds, 18547 gets/second

修改代码，使一些put操作在保持正确性的同时并行运行。当make grade表示您的代码通过了ph_safe和ph_fast测试时，您就完成了。ph_fast测试要求两个线程每秒的输出量至少是一个线程的1.25倍。（这里我用的小粒度的锁，基本达到了两倍速度，所以make grade相应测试肯定通过）

Barrier (moderate)

在这项任务中，您将实现一个屏障：应用程序中的一个点，所有参与线程都必须等待，直到所有其他参与线程也到达该点。您将使用pthread条件变量，这是一种类似于xv6的睡眠和唤醒的序列协调技术。

您应该在真实的计算机上（不是xv6，也不是qemu）执行此任务。

文件notxv6/barrier.c包含一个损坏的屏障。

$ make barrier
$ ./barrier 2
barrier: notxv6/barrier.c:42: thread: Assertion `i == t' failed.

2指定在barrier.c中同步的线程数。每个线程执行一个循环。在每次循环迭代中，线程都会调用barrier（），然后休眠随机微秒。assert触发，因为一个线程在另一个线程到达屏障之前就离开了屏障。所需的行为是，每个线程在barrier（）中阻塞，直到所有线程都调用了barrier()

实验任务

您的目标是实现所需的障碍行为。除了您在ph赋值中看到的锁基元之外，您还需要以下新的pthread基元；请看这里和这里了解详细信息。

pthread_cond_wait（&cond，&mutex）；//在cond上进入睡眠，释放锁互斥，在唤醒时获取
pthread_cond_broadcast（&cond）；//唤醒每一个睡在cond上的线程

确保你的解决方案通过make grade的barrier测试。

pthread_cond_wait 被调用的时候释放mutex，在返回时重新获得mutex

我们已经给你barrier_init()。你的任务是执行barrier()，以便于panic不发生。我们已经为你定义struct barrier，他的一些字段对你有用

有两个问题使您的任务复杂化：

• 你必须处理一系列的障碍调用，每一次我们都会调用一轮。bstate.round记录本轮。每次所有线程到达屏障时，都应该增加bstate.round。
• 您必须处理这样一种情况，即一个线程在其他线程退出屏障之前围绕循环进行竞争。特别是，从一轮到下一轮都在重新使用bstate.nthread变量。确保在上一轮仍在使用bstate.nthread时，离开障碍并在循环中奔跑的线程不会增加bstate.nhread。

使用一个、两个或两个以上的线程测试代码。

解决方案

对进入barrier的线程数计数，一旦最后一个线程到达了，那么不要再

static void 
barrier()
{// YOUR CODE HERE//// Block until all threads have called barrier() and// then increment bstate.round.//pthread_mutex_lock(&bstate.barrier_mutex);    // 进入临界区bstate.nthread++;if (bstate.nthread != nthread) {pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);   // 在这里等待其他的进入} else {    // 所有的线程都到这里了bstate.nthread = 0;bstate.round++;// 一定要在round、nthread更新后才能唤醒，因为如果先唤醒，此时别的线程执行，到t=bstate.round，但是没有更新，导致t！=i，会assertpthread_cond_broadcast(&bstate.barrier_cond);}pthread_mutex_unlock(&bstate.barrier_mutex); 
}