Lab7: Multithreading

Uthread: switching between threads

本实验是在给定的代码基础上实现用户级线程切换，相比于XV6中实现的内核级线程，这个要简单许多。因为是用户级线程，不需要设计用户栈和内核栈，用户页表和内核页表等等切换，所以本实验中只需要一个类似于context的结构，而不需要费尽心机的维护trapframe

(1). 定义存储上下文的结构体tcontext

  1. // 用户线程的上下文结构体
  2. struct tcontext {
  3.   uint64 ra;
  4.   uint64 sp;
  6.   // callee-saved
  7.   uint64 s0;
  8.   uint64 s1;
  9.   uint64 s2;
  10.   uint64 s3;
  11.   uint64 s4;
  12.   uint64 s5;
  13.   uint64 s6;
  14.   uint64 s7;
  15.   uint64 s8;
  16.   uint64 s9;
  17.   uint64 s10;
  18.   uint64 s11;
  19. };

(2). 修改thread结构体，添加context字段

  1. struct thread {
  2.   char            stack[STACK_SIZE];  /* the thread's stack */
  3.   int             state;              /* FREE, RUNNING, RUNNABLE */
  4.   struct tcontext context;            /* 用户进程上下文 */
  5. };

(3). 模仿kernel/swtch.S，在kernel/uthread_switch.S中写入如下代码

  1. .text
  3. /*
  4. * save the old thread's registers,
  5. * restore the new thread's registers.
  6. */
  8. .globl thread_switch
  9. thread_switch:
  10.     /* YOUR CODE HERE */
  11.     sd ra, 0(a0)
  12.     sd sp, 8(a0)
  13.     sd s0, 16(a0)
  14.     sd s1, 24(a0)
  15.     sd s2, 32(a0)
  16.     sd s3, 40(a0)
  17.     sd s4, 48(a0)
  18.     sd s5, 56(a0)
  19.     sd s6, 64(a0)
  20.     sd s7, 72(a0)
  21.     sd s8, 80(a0)
  22.     sd s9, 88(a0)
  23.     sd s10, 96(a0)
  24.     sd s11, 104(a0)
  26.     ld ra, 0(a1)
  27.     ld sp, 8(a1)
  28.     ld s0, 16(a1)
  29.     ld s1, 24(a1)
  30.     ld s2, 32(a1)
  31.     ld s3, 40(a1)
  32.     ld s4, 48(a1)
  33.     ld s5, 56(a1)
  34.     ld s6, 64(a1)
  35.     ld s7, 72(a1)
  36.     ld s8, 80(a1)
  37.     ld s9, 88(a1)
  38.     ld s10, 96(a1)
  39.     ld s11, 104(a1)
  40.     ret    /* return to ra */

(4). 修改thread_scheduler，添加线程切换语句

  1. ...
  2. if (current_thread != next_thread) {         /* switch threads?  */
  3.   ...
  4.   /* YOUR CODE HERE */
  5.   thread_switch((uint64)&t->context, (uint64)&current_thread->context);
  6. } else
  7.   next_thread = 0;

(5). 在thread_create中对thread结构体做一些初始化设定，主要是ra返回地址和sp栈指针，其他的都不重要

  1. // YOUR CODE HERE
  2. t->context.ra = (uint64)func;                   // 设定函数返回地址
  3. t->context.sp = (uint64)t->stack + STACK_SIZE;  // 设定栈指针

Using threads

来看一下程序的运行过程：设定了五个散列桶，根据键除以5的余数决定插入到哪一个散列桶中，插入方法是头插法，下面是图示

不支持在 Docs 外粘贴 block

这个实验比较简单，首先是问为什么为造成数据丢失：

假设现在有两个线程T1和T2，两个线程都走到put函数，且假设两个线程中key%NBUCKET相等，即要插入同一个散列桶中。两个线程同时调用insert(key, value, &table[i], table[i])，insert是通过头插法实现的。如果先insert的线程还未返回另一个线程就开始insert，那么前面的数据会被覆盖

因此只需要对插入操作上锁即可

(1). 为每个散列桶定义一个锁，将五个锁放在一个数组中，并进行初始化

  1. pthread_mutex_t lock[NBUCKET] = { PTHREAD_MUTEX_INITIALIZER }; // 每个散列桶一把锁

(2). 在put函数中对insert上锁

  1. if(e){
  2.     // update the existing key.
  3.     e->value = value;
  4. } else {
  5.     pthread_mutex_lock(&lock[i]);
  6.     // the new is new.
  7.     insert(key, value, &table[i], table[i]);
  8.     pthread_mutex_unlock(&lock[i]);
  9. }

Barrier

额。。。这个也比较简单，只要保证下一个round的操作不会影响到上一个还未结束的round中的数据就可

  1. static void 
  2. barrier()
  3. {
  4.   // 申请持有锁
  5.   pthread_mutex_lock(&bstate.barrier_mutex);
  7.   bstate.nthread++;
  8.   if(bstate.nthread == nthread) {
  9.     // 所有线程已到达
  10.     bstate.round++;
  11.     bstate.nthread = 0;
  12.     pthread_cond_broadcast(&bstate.barrier_cond);
  13.   } else {
  14.     // 等待其他线程
  15.     // 调用pthread_cond_wait时，mutex必须已经持有
  16.     pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
  17.   }
  18.   // 释放锁
  19.   pthread_mutex_unlock(&bstate.barrier_mutex);
  20. }