lab thread: finish

5 files changed, 85 insertions, 13 deletions

diff --git a/answers-thread.txt b/answers-thread.txt
new file mode 100644
index 0000000..80dde35
--- /dev/null
+++ b/answers-thread.txt
@@ -0,0 +1,10 @@
+1. Why are there missing keys with 2 threads, but not with 1 thread?
+    With 1 thread, the put and insert are always interleaved.
+    No changes to hash table happen at the same time.
+    But with 2 threads, there will be race to access the hash table,
+    and this leads to the missing keys.
+
+2. Identify a sequence of events with 2 threads that can lead to a key being missing.
+    Suppose thread No. 1 is running the insert and so does thread No. 2.
+    They shall both insert a entry. But because they enter the insert function with the same hash table,
+    they could only insert one key at most, which causes a key being missing.
diff --git a/notxv6/barrier.c b/notxv6/barrier.c
index 12793e8..b7737a6 100644
--- a/notxv6/barrier.c
+++ b/notxv6/barrier.c
@@ -25,12 +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) {
+    pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
+  } else {
+    pthread_cond_broadcast(&bstate.barrier_cond);
+    // All threads have reached barrier.
+    // reset and increase round
+    bstate.nthread = 0;
+    bstate.round++;
+  }
+  pthread_mutex_unlock(&bstate.barrier_mutex);
 }
 
 static void *
diff --git a/notxv6/ph.c b/notxv6/ph.c
index 82afe76..db8a630 100644
--- a/notxv6/ph.c
+++ b/notxv6/ph.c
@@ -16,7 +16,7 @@ struct entry {
 struct entry *table[NBUCKET];
 int keys[NKEYS];
 int nthread = 1;
-
+pthread_mutex_t lock[NBUCKET];
 
 double
 now()
@@ -47,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;
@@ -54,7 +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*
@@ -67,7 +68,6 @@ get(int key)
   for (e = table[i]; e != 0; e = e->next) {
     if (e->key == key) break;
   }
-
   return e;
 }
 
@@ -113,6 +113,9 @@ main(int argc, char *argv[])
   nthread = atoi(argv[1]);
   tha = malloc(sizeof(pthread_t) * nthread);
   srandom(0);
+  for (int i = 0; i < NBUCKET; i++) {
+    pthread_mutex_init(&lock[i], NULL);
+  }
   assert(NKEYS % nthread == 0);
   for (int i = 0; i < NKEYS; i++) {
     keys[i] = random();
diff --git a/user/uthread.c b/user/uthread.c
index 18b773d..7641d77 100644
--- a/user/uthread.c
+++ b/user/uthread.c
@@ -11,9 +11,30 @@
 #define MAX_THREAD  4
 
 
+// Saved registers for kernel context switches.
+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;       /* saved registers to switch thru threads */
 };
 struct thread all_thread[MAX_THREAD];
 struct thread *current_thread;
@@ -56,10 +77,8 @@ 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(??, ??);
-     */
+     // Invoke thread_switch to switch from t to next_thread:
+    thread_switch((uint64)&t->context, (uint64)&next_thread->context);
   } else
     next_thread = 0;
 }
@@ -73,7 +92,11 @@ thread_create(void (*func)())
     if (t->state == FREE) break;
   }
   t->state = RUNNABLE;
-  // YOUR CODE HERE
+  // Set up new context to start executing at func
+  memset(&t->context, 0, sizeof(struct context));
+  t->context.ra = (uint64)func;
+  // stack grows downward, set sp at the highest stack address in out thread
+  t->context.sp = (uint64)t->stack + STACK_SIZE;
 }
 
 void 
diff --git a/user/uthread_switch.S b/user/uthread_switch.S
index 5defb12..19cc400 100644
--- a/user/uthread_switch.S
+++ b/user/uthread_switch.S
@@ -7,5 +7,33 @@
 
 	.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 */