6.s081 Lab5 Multithreading | 没什么看头的地方

lab

发布日期: 2023-10-30

现在进入操作系统的另一大特性：并发。

线程切换 in xv6

在 xv6 中，每个进程都可以视为有一个主线程，逐行运行指令，享有所有寄存器的使用权。然而，时间片到期，也就是进程收到时钟中断后，会调用 yield() 函数自愿让出 CPU。

该函数会将当前进程运行状态设置为 RUNNABLE，也就是所谓的就绪态，然后调用 sched()。

sched() 进行一些合理性检查后，会调用 switch() 进行上下文的切换：保存当前进程上下文到 proc->context 中，并将寄存器设置为 CPU 调度器线程的上下文（struct context 指明了保存的上下文都有哪些寄存器，基本都是 Callee Saved Register，这里主要关注 ra）。也就是说，调用 swtch() 后，本来 ra 应该为 sched() 中调用 swtch() 处的地址，但 switch() 的一通操作，ra 成为了调度器线程 scheduler() 函数的地址，那么 swtch() 最后的 ret 指令会进入到 scheduler() 开始执行。

scheduler() 本质上是个 for 循环，遍历进程表找到下一个处于就绪态的进程 A，将 A 设置为 RUNNING，即运行态，然后调用 swtch() 保存当前寄存器到调度进程中，然后读 A 的上下文到寄存器中，这样就完成了切换的工作。

如果是首次调度 A，那么由于 A 的 context.ra 会被初始化为 forkret()，直接跳转过去；

反之，A 的 context.ra 因为上次时间片到期而被初始化为 sched() 中调用 swtch() 处的地址，恢复上下文后相当于跟什么都没发生一样，继续执行，退出 sched()，退出 yield()，后面就是到 usertrapret() 返回用户态了。

所以，进程的切换相当于主线程的切换，而在硬件层面，就是几个寄存器的切换，同一个进程切换出去，会在同一位置切换回来继续执行，保证了并发的正确性。

ret 指令会自动设置 PC，也就不用保存。

而页表寄存器的切换与 TLB 的清除工作，是当进程切换后，必然会进入 usertrapret()（forkret() 最后也会进入），这里会进行内核态到用户态页表的切换，而用户态页表地址在 struct proc 中的 pagetable 里，调度到哪个进程自然就会将 SATP 设为对应进程的 proc->pagetable。

Preparation

切换到对应分支

$ git fetch
$ git checkout thread
$ make clean

Task1: Uthread: switching between threads

该任务就是实现线程间的切换，其实现完全可以参考进程切换，毕竟本质上也是主线程的切换。

user/uthread.c
...
// 定义上下文结构体，其实就是直接抄了 proc.h 里的。
struct context {
  uint64 ra;
  uint64 sp;

  // callee-saved
  uint64 s0;
  uint64 s1;
  uint64 s2;
  uint64 s3;
  uint64 s4;
  uint64 s5;
  uint64 s6;
  uint64 s7;
  uint64 s8;
  uint64 s9;
  uint64 s10;
  uint64 s11;
};

struct thread {
  char           stack[STACK_SIZE]; /* the thread's stack */
  int            state;             /* FREE, RUNNING, RUNNABLE */
  struct context ctx;               // (!new)
};
...
void
thread_schedule(void)
{
  struct thread *t, *next_thread;

  /* Find another runnable thread. */
  ...

  if (current_thread != next_thread) {         /* switch threads?  */
    next_thread->state = RUNNING;
    t = current_thread;
    current_thread = next_thread;
    thread_switch((uint64)&t->ctx, (uint64)&next_thread->ctx); // (!new)
  } else {
    next_thread = 0;
  }
}

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;

  memset(&t->ctx, 0, sizeof(struct context)); // (!new)
  t->ctx.ra = (uint64)func;                   // (!new)
  t->ctx.sp = (uint64)&t->stack + STACK_SIZE; // (!new)
}

user/uthread_switch.S
.globl thread_switch
thread_switch:
  sd ra, 0(a0)
  ...
  sd s11, 104(a0)

  ld ra, 0(a1)
  ...
  ld s11, 104(a1)

  ret    /* return to ra */

基本都是参考已有的实现，但关键是弄明白具体发生了什么。

Task2: Using threads

该任务（和下一个任务）是熟悉 pthread.h 库并发编程，场景是对一个哈希表进行并发读写，由于是批量写完再读，所以不用给读操作加锁（读写交错的话就要加锁了）。

这里的哈希表采用最简单的拉链法处理冲突和直接哈希进行映射，一共有 NBUCKETS 个桶，每个桶用链表实现，用 key % NBUCKETS 进行映射，然后插到桶链表的末尾。

最开始我们可以为整个表设置一个大锁，一旦要进行写操作，就上锁，写完放锁。但这样效率很低，毕竟一共有互不干涉的 NBUCKETS 个桶，如果两个 key 分别映射到不同的桶，那就没有必要用大锁来互斥。于是可以考虑开一个锁数组，每个桶对应一个表，根据 key 的映射结果决定给哪个桶上锁放锁，这样效率会比之前快很多。

大锁的设计粒度太粗，无法通过 ph_fast 测试，改为「一桶一锁」方能通过。

notxv6/ph.c
...
pthread_mutex_t locks[NBUCKET];
...
static
void put(int key, int value)
{
  int i = key % NBUCKET;
  pthread_mutex_lock(&locks[i]);
  // insert
  pthread_mutex_unlock(&locks[i]);
}

int
main(int argc, char *argv[])
{
  ...
  // before put
  for (int i = 0; i < NBUCKET; i++) {
    pthread_mutex_init(&locks[i], 0);
  }
  ...
}

Task3: Barrier

这个任务就是用到条件变量相关的库函数了。场景是每个线程都有一个 for 循环，每次循环都要调用 barrier() 进行短暂阻塞，保证每个线程的循环轮次保持一致。

notxv6/barrier.c
static void *
thread(void *xa)
{
  ...
  for (i = 0; i < 20000; i++) {
    int t = bstate.round;
    assert (i == t);
    barrier();
    usleep(random() % 100);
  }
  ...
}

有一个全局结构体 struct barrier bstate，里面设置了一些变量，比如 bstate.nthread 就是当前位于 barrier 的线程数，bstate.round 是当前 barrier 所处的轮次。全局静态变量 nthread 和 round 分别表示总线程数与……这个 round 变量需要我们自己品，暂且不表。

令第 i 次循环调用的阻塞为 barrier_i，不妨考虑 barrier_0。一开始所有线程都会进入 barrier_0，如果不是最后一个进入的，就阻塞，反之，唤醒其他线程。此外，还要有一个线程负责修改 bstate.round，那么由谁来修改呢？是最后一个进入的，还是最后一个离开的？

如果是最后一个出去的进行修改，那就会出问题。

Wrong Case1
static void
barrier()
{
  pthread_mutex_lock(&bstate.barrier_mutex);
  bstate.nthread++;
  if (bstate.nthread < nthread) { // 不是最后一个进来的
    pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
  } else { // 是最后一个进来的
    pthread_cond_broadcast(&bstate.barrier_cond);
  }

  if (--bstate.nthread == 0) { // 是最后一个离开的
    bstate.round++;
  }
  pthread_mutex_unlock(&bstate.barrier_mutex);
}

这里，每个进程在进入后与离开前都会修改 bstate.nthread，如果由最后一个离开的修改 bstate.round，就会导致其他先离开的线程经历短暂的 usleep() 后，进入到下一个循环，此时 bstate.round 为 0，但 i 为 1，断言失败，程序报错。问题的本质在于，bstate.round 没有得到及时修改。那么是不是改完这个问题就没事了呢？当然不是。

Wrong Case2
static void
barrier()
{
  pthread_mutex_lock(&bstate.barrier_mutex);
  bstate.nthread++;
  if (bstate.nthread < nthread) { // 不是最后一个进来的
    pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
  } else { // 是最后一个进来的，也是第一个离开的，毕竟从进来到退出之间一直持有锁
    bstate.round++;
    pthread_cond_broadcast(&bstate.barrier_cond);
  }
  pthread_mutex_unlock(&bstate.barrier_mutex);
}

尽管上面的修改确实解决了断言的问题，但断言之后，线程会进入 barrier_1，获取锁，然后修改 bstate.nthread。然而，还有其他 nthread-1 个线程还逗留在 barrier_0() 中，甚至可能没有走到 if (bstate.nthread-- == nthread) 这一步。

第一个离开的线程会先将 barrier_0 的 bstate.nthread 减少，然后进入 barrier_1 将 bstate.nthread 增加——bstate.nthread 相当于没有变化，这就导致其他线程到了 if (bstate.nthread-- == nthread) 后，会误以为自己是第一个离开的，从而修改 bstate.round。这是个毁灭性的错误！

这个错误的根源在于，后面的 barrier 不应该在 有线程未退出前面的 barrier 的时候 对 bstate.nthread 进行修改。那么如何判断是否所有线程都退出前一个 barrier 了呢？全局变量 round 派上用场了。如果将这个变量解释为，最晚的线程所处的 barrier 轮次，那么只要有线程没有退出 barrier_{i-1}，round 就会停留在 i-1，直到所有线程都阻塞在 barrier_i（或退出 barrier_{i-1}），此时 round 才会被设置为 i。

所以，在修改 bstate.nthread 之前，所有线程都要阻塞，直到 round 被修改为与 bstate.round 一致，然后被修改 round 的那个线程唤醒。

修改 round 的线程其实就是最后一个离开 barrier_{i-1} 的线程。

notxv6/barrier.c
static void
barrier()
{
  pthread_mutex_lock(&bstate.barrier_mutex);

  while (round != bstate.round) { // 等待所有线程退出前一个 barrier
    pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
  }

  bstate.nthread++;
  if (bstate.nthread < nthread) { // 等待所有线程进入当前 barrier
    pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
  } else { // 最后一个进入的，负责修改 bstate.round，并唤醒其他线程
    bstate.round++;
    pthread_cond_broadcast(&bstate.barrier_cond);
  }

  if (--bstate.nthread == 0) { // 最后一个离开的，负责修改 round，并唤醒下一个 barrier 等待的所有线程
    round = bstate.round;
    pthread_cond_broadcast(&bstate.barrier_cond);
  }

  pthread_mutex_unlock(&bstate.barrier_mutex);
}

测试结果

$ make grade
...
== Test uthread ==
$ make qemu-gdb
uthread: OK (3.1s)
== Test answers-thread.txt == answers-thread.txt: OK
== Test ph_safe == make[1]:
ph_safe: OK (14.1s)
== Test ph_fast == make[1]:
ph_fast: OK (32.3s)
== Test barrier == make[1]:
barrier: OK (2.7s)
== Test time ==
time: OK
Score: 60/60

最后的工作

git commit -am "" 将所有修改提交到本地;
执行 make handin。由于 lab0 保存了 APIKey，故直接成功提交；

可选的挑战再说吧，没有什么想做的欲望。

MIT 6.s081

6.s081 Lab6 Networking

这里要我们在软件层面实现数据包的收发操作。

2023-10-31 lab

MIT 6.s081

6.s081 Lab4 Copy-on-Write Fork for Xv6

课上谈了个 COW 优化策略，这里就要具体实现了。

2023-10-30 lab

MIT 6.s081