diff options
| -rw-r--r-- | answers-thread.txt | 10 | ||||
| -rw-r--r-- | notxv6/barrier.c | 16 | ||||
| -rw-r--r-- | notxv6/ph.c | 9 | ||||
| -rw-r--r-- | user/uthread.c | 33 | ||||
| -rw-r--r-- | user/uthread_switch.S | 30 |
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 */ |