xv6 Lab6: Multithreading

这个实验是熟悉多线程。需要实现在一个用户态的线程切换，使用多个线程来加速程序，并实现一个屏障。

uthread

打开 user/uthread.c 文件，观察 uthread 的数据结构以及部分函数实现能帮我们快速理清思路。

关键实现

struct context / thread_switch

一个是上下文，一个是线程切换对应的底层汇编。如介绍所言，从内核部分复制过来就行了。

thread_schedule

线程上下文切换，传入上下文 ctx 即可，其他状态的切换代码已经有了。

thread_create

线程创建，创建时，只需要指定 ra 和 sp 两个寄存器即可，ra 指向需要执行的 func，sp 指向栈低(高地址)，栈是从高往低增长的，故需指向高地址的栈底。

Show me the code

diff --git a/user/uthread.c b/user/uthread.c
index f9795ab..0ed406a 100644
--- a/user/uthread.c
+++ b/user/uthread.c
@@ -10,9 +10,31 @@
 #define STACK_SIZE 8192
 #define MAX_THREAD 4
 
+// Saved registers for uthread context switches.
+// Copy from kernel/proc.h
+struct context {
+  uint64 ra; /* return address */
+  uint64 sp; /* stack pointer */
+
+  // 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;
 };
 struct thread all_thread[MAX_THREAD];
 struct thread *current_thread;
@@ -55,10 +77,7 @@ thread_schedule(void)
     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((uint64)&t->ctx, (uint64)&current_thread->ctx);
   }
   else
     next_thread = 0;
@@ -74,7 +93,8 @@ thread_create(void (*func)())
       break;
   }
   t->state = RUNNABLE;
-  // YOUR CODE HERE
+  t->ctx.ra = (uint64)func;
+  t->ctx.sp = (uint64)&t->stack[STACK_SIZE - 1];
 }
 
 void
diff --git a/user/uthread_switch.S b/user/uthread_switch.S
index 5defb12..8deb723 100644
--- a/user/uthread_switch.S
+++ b/user/uthread_switch.S
@@ -7,5 +7,35 @@
 
 	.globl thread_switch
 thread_switch:
-	/* YOUR CODE HERE */
+	/* Copy from kernel/swtch.S */
+	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 */

Using threads

实现 bucket 级别锁利用多线程加速

# 编译
make ph

# 执行
./ph $(nproc)

Show me the code

diff --git a/notxv6/ph.c b/notxv6/ph.c
index 09a72f3..c7b0050 100644
--- a/notxv6/ph.c
+++ b/notxv6/ph.c
@@ -17,6 +17,8 @@ struct entry *table[NBUCKET];
 int keys[NKEYS];
 int nthread = 1;
 
+pthread_mutex_t lock[NBUCKET]; // 定义锁
+
 double
 now()
 {
@@ -42,6 +44,7 @@ put(int key, int value)
 
   // is the key already present?
   struct entry *e = 0;
+   pthread_mutex_lock(&lock[i]); // 获取锁
   for (e = table[i]; e != 0; e = e->next) {
     if (e->key == key)
       break;
@@ -54,6 +57,7 @@ put(int key, int value)
     // the new is new.
     insert(key, value, &table[i], table[i]);
   }
+   pthread_mutex_unlock(&lock[i]); // 释放锁
 }
 
 static struct entry *
@@ -117,6 +121,11 @@ main(int argc, char *argv[])
     keys[i] = random();
   }
 
+  // 初始化锁
+  for (int i = 0; i < NBUCKET; i++) {
+    pthread_mutex_init(&lock[i], NULL);
+  }
+
   //
   // first the puts
   //

Barrier

posix 强相关，主打了解一个 posix 的 API， broadcast 这些函数日常码代码见到的不多。

# 编译
make barrier

# 执行
./barrier

Show me the code

diff --git a/notxv6/barrier.c b/notxv6/barrier.c
index bcad78f..a9768db 100644
--- a/notxv6/barrier.c
+++ b/notxv6/barrier.c
@@ -25,11 +25,20 @@ barrier_init(void)
 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) {
+    bstate.round++;
+    bstate.nthread = 0;
+    pthread_cond_broadcast(&bstate.barrier_cond);
+  }
+  else {
+    pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
+  }
+
+  pthread_mutex_unlock(&bstate.barrier_mutex);
 }
 
 static void *

测试结果

$ make qemu-gdb
uthread: OK (4.4s)
== Test answers-thread.txt ==
answers-thread.txt: OK
== Test ph_safe == make[1]: Entering directory '/root/xv6-labs-2023'
gcc -o ph -g -O2 -DSOL_THREAD -DLAB_THREAD notxv6/ph.c -pthread
make[1]: Leaving directory '/root/xv6-labs-2023'
ph_safe: OK (15.7s)
== Test ph_fast == make[1]: Entering directory '/root/xv6-labs-2023'
make[1]: 'ph' is up to date.
make[1]: Leaving directory '/root/xv6-labs-2023'
ph_fast: OK (36.4s)
== Test barrier == make[1]: Entering directory '/root/xv6-labs-2023'
gcc -o barrier -g -O2 -DSOL_THREAD -DLAB_THREAD notxv6/barrier.c -pthread
make[1]: Leaving directory '/root/xv6-labs-2023'
barrier: OK (2.8s)
== Test time ==
time: OK
Score: 60/60