image.png

补全 uthread.c，完成用户态线程功能的实现。

这里的线程相比现代操作系统中的线程而言，更接近一些语言中的“协程”（coroutine），只用在用户态下切换。原因是这里的“线程”是完全用户态实现的，多个线程也只能运行在一个 CPU 上，并且没有时钟中断来强制执行调度，需要线程函数本身在合适的时候主动 yield 释放 CPU。这样实现起来的线程并不对线程函数透明，所以比起操作系统的线程而言更接近 coroutine。

这个实验其实相当于在用户态重新实现一遍 xv6 kernel 中的 scheduler() 和 swtch() 的功能，所以大多数代码都是可以借鉴的。

函数与寄存器调用关系

函数调用过程通常分为 6 个阶段。

  1. 将参数存储到被调用的函数可以访问到的位置；
  2. 跳转到函数起始位置；
  3. 获取函数需要的局部存储资源，按需保存寄存器(callee saved registers) ；
  4. 执行函数中的指令；
  5. 将返回值存储到调用者能够访问到的位置，恢复寄存器(callee saved registers)，释放局部存储资源；
  6. 返回调用函数的位置。

思路讲解

在调用本函数 uthread_switch() 的过程中，caller-saved registers 已经被调用者保存到栈帧中了，所以这里无需保存这一部分寄存器。

引申：内核调度器无论是通过时钟中断进入（usertrap），还是线程自己主动放弃 CPU（sleep、exit），最终都会调用到 yield 进一步调用 swtch。 由于上下文切换永远都发生在函数调用的边界（swtch 调用的边界），恢复执行相当于是 swtch 的返回过程，会从堆栈中恢复 caller-saved（保存性寄存器） 的寄存器， 所以用于保存上下文的 context 结构体只需保存 callee-saved （恢复性寄存器）寄存器，以及 返回地址 ra、栈指针 sp 即可。恢复后执行到哪里是通过 ra 寄存器来决定的（swtch 末尾的 ret 转跳到 ra）

而 trapframe 则不同，一个中断可能在任何地方发生，不仅仅是函数调用边界，也有可能在函数执行中途，所以恢复的时候需要靠 pc 寄存器来定位。 并且由于切换位置不一定是函数调用边界，所以几乎所有的寄存器都要保存（无论 caller-saved 还是 callee-saved），才能保证正确的恢复执行。 这也是内核代码中 struct trapframe 中保存的寄存器比 struct context 多得多的原因。 另外一个，无论是程序主动 sleep，还是时钟中断，都是通过 trampoline 跳转到内核态 usertrap（保存 trapframe），然后再到达 swtch 保存上下文的。 恢复上下文都是恢复到 swtch 返回前（依然是内核态），然后返回跳转回 usertrap，再继续运行直到 usertrapret 跳转到 trampoline 读取 trapframe，并返回用户态。 也就是上下文恢复并不是直接恢复到用户态，而是恢复到内核态 swtch 刚执行完的状态。负责恢复用户态执行流的其实是 trampoline 以及 trapframe。

Uthread: switching between threads

我们需要在所给的用户态uthread.c文件中添加content去保存恢复性寄存器。然后再创建线程时区把返回点，和栈的寄存器值放进去。
再在thread_schedule切换时，把原先thread的寄存器值赋值给另一个thread

  1. // uthread.c
  2. void 
  3. thread_create(void (*func)())
  4. {
  5.     struct thread *t;
  7.     for (t = all_thread; t < all_thread + MAX_THREAD; t++) {
  8.         if (t->state == FREE) break;
  9.     }
  10.     t->state = RUNNABLE;
  11.     t->ctx.ra = (uint64)func;       // 返回地址
  12.     // thread_switch 的结尾会返回到 ra，从而运行线程代码
  13.     t->ctx.sp = (uint64)&t->stack + (STACK_SIZE - 1);  // 栈指针
  14.     // 将线程的栈指针指向其独立的栈，注意到栈的生长是从高地址到低地址，所以
  15.     // 要将 sp 设置为指向 stack 的最高地址
  16. }

Using threads

分析并解决一个哈希表操作的例子内，由于 race-condition 导致的数据丢失的问题。
如果直接创建一个锁进行添加的话，可以，但是在不同线程之间切换，然后还是加同一把锁，效率很低，所以我们这里采用不同的哈希桶作为锁。
题目给出的线程数为NBUCKET个，我们根据hashKey分在不同的桶中，

pthread_mutex_t locks[NBUCKET]; pthread_mutex_lock(&locks[i]);

Barrier

利用 pthread 提供的条件变量方法，实现同步屏障机制。

自述

首先这里的线程其实更接近于我们所说的协程，因为在切换时，不需要进行内核态和用户态的切换，只在用户态下实现即可。当我们一个线程时钟到了之后，会去thread_switch切换线程，在里面会去yield释放掉自己的CPU，再调用schedule调度器去选择下一个线程，我们也可以就在这里面去采用直接想要的线程切换算法。还有就是寄存器的问题，我们这里的并不需要使用到全部的寄存器，而只需要使用到那些恢复性的寄存器，以及线程返回地址ra，和栈指针sp。因为我们自定义的上下文切换永远都发生在函数调用的边界，恢复执行相当于是swtch的返回过程，会从堆栈中恢复保护性寄存器，不需要我们额外再保存。而真正的trapframe中断，可能发生在任何地方，不仅仅是函数调用边界，也可能在函数执行过程中，所以恢复的时候要考pc寄存器来定位。