xv6-2020-lab7解析

先导知识

在Linux中，一个进程可以有多个用户态的线程；但是在xv6中，只有一个用户态的线程；xv6只有两个线程，分别是用户态的线程和内核态的线程。

xv6在两种情况下，会切换CPU从一个进程到另外一个进程，第一种是当进程等待IO的时候，等待子进程退出的时候，或者是调用sleep系统调用的时候。第二种就是强制一些长时间占用CPU的进程切换，也就是利用时钟中断强制切换。

在设计xv6的时候，考虑到了多核的情况，它每一个CPU的核心会有一个调度器线程——scheduler thread，且每一个调度器线程都具有一个栈和context。

进行进程切换的时候，还是比较复杂的。首先是通过系统调用或者是中断进入到内核线程，然后通过上下文切换到当前CPU的调度程序线程（scheduler thread），然后上下文切换到新进程的内核线程，最后通过trap返回到用户级进程。每一个CPU都会有自己的调度线程。假设从进程A切换到进程B，下图是xv6中如何进行切换的：

在进行切换的时候其实最重要的就是栈的切换和PC计数器（但是你会发现代码中，其实我们并没有保存PC寄存器23333）的切换。在xv6中的swtch是用汇编代码写的，本质上就是保存第一个参数所指的所有寄存器，恢复第二个参数所指的寄存器。swtch的函数声明是这样子的：

1	void swtch(struct context, struct context);

也就是把当前寄存器的值放入第一个context中，把第二个context指向的寄存器的值放入当前的寄存器中。

usertrap可能会调用yeild（当时钟中断发生的时候，内核主动放弃了CPU，转而调用yeild），而在yeild中则是会使用sched()，然后在sched()之中会调用swtch，swtch即是核心函数，把当前的进程的context存起来，并且恢复mycpu()->context，也就是说当调用完swtch之后，接下来就会执行上一次保存在cpu->context的ra寄存器中的地址的代码了。并且此时用的是上一次调用swtch的内核栈。

每个进程至少有两个线程，一个用户线程，一个内核线程。进程要么正在执行其用户线程，要么就是在内核线程中处理系统调用或中断。

trapframe中存的是用户的寄存器，而context存放的则是RISC-V的寄存器。从一个进程切换到另外一个进程，大致需要以下过程：

首先需要先进入到内核（线程），那么就需要把用户的寄存器保存到p->trapframe。
然后从内核线程切换到scheduler thread，然后把内核线程的寄存器保存到p->context中。
scheduler thread到另外一个内核线程，从p->context中恢复到内核线程的寄存器。
从内核恢复到用户线程，从p->trapframe中恢复。

追踪一下

写了一个最简单的死循环函数：

#include "kernel/types.h"
#include "user/user.h"

int main(int argc, char const *argv[])
{
    int pid;
    char c;

    pid = fork();
    if (pid == 0)
    {
        c = 's';
    }
    else
    {
        c = 'f';
    }

    // 无限循环
    for (int i = 0;; i++)
    {
        if (i % 6000000 == 0)
        {
            write(2, &c, 1);
        }
    }

    return 0;
}

这个程序就是两个父子进程轮流打印一下字符，父进程打印f，子进程打印s。

然后记得把qemu的核心数设置成1来模拟单核。

如果希望能够追踪时钟中断，那么显然应该在devintr这个函数返回2的时候下断点，所以我挑选了一下，就把断点下在了b trap.c:207，然后使用finish完成当前的函数，这个时候就会发现此时到了usertrap，因为我们写的是死循环，而此时必然是时间到了，所以触发的是timer interrupt，所以会触发一个yeild来强制其进行进程的切换。

此时打印一下，p->name = “spin”，pid = 3（如果是4，推荐换成继续执行变成3，这样之后会比较方便，当然本质上没有区别）。紧接着我们跟着进入yeild里面。发现yeild本身首先会获取当前的进程，并且它会给当前的进程上锁，然后把当前的进程修改成RUNNABLE状态（其实此时还是进程自己在执行，相当于进程自己把自己的状态从RUNNING切换到了RUNNABLE，但是由于有锁，所以不需要担心）。

改完状态之后就会进入到sched，这里才是切换的关键。核心的一句其实就是swtch(&p->context, &mycpu()->context);，即把当前的寄存器的值放入到进程的context中，然后把调度线程的context加载到当前寄存器中，而这里是不需要修改pc的，因为return address已经修改了，只需要一个ret指令就可以回去。

此时的mycpu()->context可能还不太明确，这里面到底是什么，这里可以先放一放，跟踪下去就知道了。

之后就进入到kernel/proc.c的scheduler()函数中了。这是因为mycpu()->context中的ra指向的就是这里。

此时此刻还没有切换好，因为进来的时候拿了锁，但是还没有释放，所以第一件事情就是释放锁。此时此刻其实已经没有在任何进程中运行了，而是在CPU的调度器线程中执行了。然后调度器线程会从列表中找到一个RUNNABLE的进程（会先持有锁），然后又开始了。

首先把这个进程的状态设置成RUNNING，然后开始调用swtch(&c->context, &p->context);，这里是核心。

这里的这一句，把当前的cpu的寄存器放到了调度器线程的context中，然后把即将运行的这个进程的上下文加载进来，然后一调用ret就会跳转到当时进程离开的地方继续执行，其实就是当时swtch的下一句，然后就可以正常通过usertrap中返回了。

而调度器线程中的context也保证了，下一次调度的时候返回的时候仍然会回到scheduler中的swtch下一句继续执行。

Uthread: switching between threads（中等）

在这个练习中，你需要自己设计一套用户线程的切换。现在已经有了两个实现的文件，分别是user/uthread.c和user/uthread_switch.S。

然后你需要完成user/uthread.c中的函数thread_create() 和 thread_schedule() ；以及 user/uthread_switch.S中的thread_switch 。其中的一点是，thread_schedule()调度第一个线程的时候，线程需要执行对应的create函数中传递进来的函数，而且需要在自己的栈中执行。同时还需要确保在切换线程的时候，能够保存寄存器和恢复寄存器，那么应该把这些寄存器的信息放在哪里呢？

hints：

thread_switch需要保存寄存器，保存那些callee-save寄存器即可，为什么？
user/uthread.asm对于debug来说很有用。

其实就是类似在已经提供好的代码之上进行一点代码的填写，然后就完成了，仿照的是POSIX标准写的pthread代码。

确定线程的结构体

由于线程切换需要保存它需要寄存器，所以必然需要一个数据结构来保存寄存器内容，而正好proc.h里面有对应的结构，所以直接引入头文件然后就可以开始使用了。

struct thread {
  char       stack[STACK_SIZE]; /* the thread's stack */
  int        state;             /* FREE, RUNNING, RUNNABLE */
  struct     context context;   /* 上下文  */
};

修改创建线程函数

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
  // 使ra指向开始的func地址，这样调度完成直接就去执行func了
  t->context.ra = (uint64)func;
  // 设置好对应的栈地址，这里注意需要让栈指向地址最大处
  t->context.sp = (uint64)t->stack+STACK_SIZE;
}

修改线程切换函数

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(??, ??);
     */
  thread_switch(&t->context,&next_thread->context);
} else
  next_thread = 0;

就是最基本的线程切换函数，把当前的线程保存到t中（此时t是当前的线程），然后切换到新的线程中。

汇编代码

其实就是抄袭之前的swtch的代码，真的是一模一样的抄。

结果

然后就这样过了…..但是不得不说，这里的代码确实值得好好学一学，因为这些代码就是用户级线程的精华。

Using threads（中等）

这个作业不需要在xv6中完成，而是需要在真正具有多核处理器上运行。这一部分探索一下Unix自带的pthread函数库，notxv6/ph.c包含了一个简单的hash table，如果是单线程中使用是正确的，但是多线程就会有问题。

这个作业其实就是给一个hashtable，然后把它改装成concurrent hashtable（简化版的），并且要保证正确性和快速性。

如果要保证正确性，那直接在put前面加个锁，就完事儿了，正确性肯定没问题；但是如果为了速度，就需要把整个hashtable切分成几个桶，这样相当于把锁的粒度给细化了。

实在是太简单了，就不贴代码了。

Barrier（中等）

类似java中的CountDownLatch，在代码中设置一个点，当所有的线程都到达这个点之后，才开始继续执行。需要用到条件变量。同样这个实现需要在真实的设备上做，不要在xv6中实现。

提示，可以使用下面的函数：

1 2	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

总结

如果了解了xv6中的进程切换，那么实现一个用户线程真的是轻而易举；同时如果有一点点并发的经验，那么实现这两个实验也是轻而易举。