本文记录了 Lab: Multithreading 的实验过程

Lab: Multithreading

git fetch
git checkout thread
make clean

Uthread: switching between threads (moderate)

为用户级线程设计一个上下文切换的机制

实验思路

1. 借鉴内核线程的上下文切换机制，在 struct thread 添加一个同样的 struct context
2. user/uthread_switch.S 中的代码和 kernel/swtch.S 中的一样
3. 在 thread_create 中将函数指针和栈顶指针保存在 context 的 ra 和 sp 中，注意栈是从高地址向低地址增长
4. 在 thread_schedule 中调用 thread_switch 切换线程

---

Using threads (moderate)

思路

创建一个 pthread_mutex_t lock[NBUCKET] ，实现分段锁的功能。

---

Barrier(moderate)

思路

在 barrier() 中，首先加锁，然后进入 barrier() 的线程数 bstate.nthread 加 1。此时如果线程数等于 nthread，那么 bstate.round 加 1，重置 bstate.nthread 为 0，最后唤醒所有线程去往下一轮；否则等待其他线程进入 barrier()。

测试

make grade

Diff

diff --git a/answers-thread.txt b/answers-thread.txt
new file mode 100644
index 0000000..7c27e29
--- /dev/null
+++ b/answers-thread.txt
@@ -0,0 +1,4 @@
+When 2 threads execute insert() concurrent, then maybe they result in missing key. But when 1 thread, insert() serialize, missing key won't happen.
+Thread1 -> insert();
+Thread2 -> insett();
+Note: lock between e->next = n;*p = e; can't resolve missing key. Because every thread will update table[i].
\ No newline at end of file
diff --git a/notxv6/barrier.c b/notxv6/barrier.c
index 12793e8..5a8ab07 100644
--- a/notxv6/barrier.c
+++ b/notxv6/barrier.c
@@ -30,7 +30,16 @@ barrier()
   // 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 *
@@ -40,9 +49,9 @@ thread(void *xa)
   long delay;
   int i;
 
   for (i = 0; i < 20000; i++) {
     int t = bstate.round;
     assert (i == t);
     barrier();
     usleep(random() % 100);
   }
diff --git a/notxv6/ph.c b/notxv6/ph.c
index 6df1500..24145d5 100644
--- a/notxv6/ph.c
+++ b/notxv6/ph.c
@@ -16,6 +16,7 @@ struct entry {
 struct entry *table[NBUCKET];
 int keys[NKEYS];
 int nthread = 1;
+pthread_mutex_t lock[NBUCKET];
 
 double
 now()
@@ -46,6 +47,7 @@ void put(int key, int value)
     if (e->key == key)
       break;
   }
+  pthread_mutex_lock(&lock[i]);
   if(e){
     // update the existing key.
     e->value = value;
@@ -53,6 +55,7 @@ void put(int key, int value)
     // the new is new.
     insert(key, value, &table[i], table[i]);
   }
+  pthread_mutex_unlock(&lock[i]);
 }
 
 static struct entry*
@@ -62,10 +65,11 @@ get(int key)
 
 
   struct entry *e = 0;
+  pthread_mutex_lock(&lock[i]);
   for (e = table[i]; e != 0; e = e->next) {
     if (e->key == key) break;
   }
-
+  pthread_mutex_unlock(&lock[i]);
   return e;
 }
 
@@ -111,6 +115,8 @@ main(int argc, char *argv[])
   tha = malloc(sizeof(pthread_t) * nthread);
   srandom(0);
   assert(NKEYS % nthread == 0);
+  for(int i = 0; i < NBUCKET; i++)
+    pthread_mutex_init(&lock[i], NULL);
   for (int i = 0; i < NKEYS; i++) {
     keys[i] = random();
   }
diff --git a/time.txt b/time.txt
new file mode 100644
index 0000000..f599e28
--- /dev/null
+++ b/time.txt
@@ -0,0 +1 @@
+5
diff --git a/user/uthread.c b/user/uthread.c
index 8e46826..2cdd801 100644
--- a/user/uthread.c
+++ b/user/uthread.c
@@ -10,11 +10,29 @@
 #define STACK_SIZE  8192
 #define MAX_THREAD  4
 
+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 context;       /* thread_switch() run thread */
 };
 struct thread all_thread[MAX_THREAD];
 struct thread *current_thread;
@@ -63,6 +81,7 @@ thread_schedule(void)
      * Invoke thread_switch to switch from t to next_thread:
      * thread_switch(??, ??);
      */
+    thread_switch((uint64)&t->context, (uint64)&next_thread->context);
   } else
     next_thread = 0;
 }
@@ -77,6 +96,8 @@ thread_create(void (*func)())
   }
   t->state = RUNNABLE;
   // YOUR CODE HERE
+  t->context.ra = (uint64)func; // return address of function
+  t->context.sp = (uint64)&t->stack[STACK_SIZE - 1]; // the stack pointer
 }
 
 void 
diff --git a/user/uthread_switch.S b/user/uthread_switch.S
index 5defb12..02206a6 100644
--- a/user/uthread_switch.S
+++ b/user/uthread_switch.S
@@ -8,4 +8,34 @@
 	.globl thread_switch
 thread_switch:
 	/* YOUR CODE HERE */
+    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 */