diff options
| -rw-r--r-- | Makefile | 10 | ||||
| -rw-r--r-- | conf/lab.mk | 2 | ||||
| -rwxr-xr-x | grade-lab-thread | 70 | ||||
| -rw-r--r-- | notxv6/barrier.c | 78 | ||||
| -rw-r--r-- | notxv6/ph.c | 150 | ||||
| -rw-r--r-- | user/uthread.c | 161 | ||||
| -rw-r--r-- | user/uthread_switch.S | 11 |
7 files changed, 472 insertions, 10 deletions
@@ -46,11 +46,9 @@ OBJS_KCSAN += \ $K/kcsan.o endif -ifeq ($(LAB),$(filter $(LAB), lock)) OBJS += \ $K/stats.o\ $K/sprintf.o -endif OBJS += \ @@ -90,7 +88,7 @@ CFLAGS = -Wall -Werror -O -fno-omit-frame-pointer -ggdb -gdwarf-2 ifdef LAB LABUPPER = $(shell echo $(LAB) | tr a-z A-Z) -XCFLAGS += -DSOL_$(LABUPPER) -DLAB_$(LABUPPER) -DLAB_PGTBL -DLAB_NET +XCFLAGS += -DSOL_$(LABUPPER) -DLAB_$(LABUPPER) -DLAB_PGTBL -DLAB_NET -DLAB_LOCK endif CFLAGS += $(XCFLAGS) @@ -139,9 +137,7 @@ tags: $(OBJS) _init ULIB = $U/ulib.o $U/usys.o $U/printf.o $U/umalloc.o -ifeq ($(LAB),$(filter $(LAB), lock)) ULIB += $U/statistics.o -endif _%: %.o $(ULIB) $(LD) $(LDFLAGS) -T $U/user.ld -o $@ $^ @@ -197,10 +193,8 @@ UPROGS=\ -ifeq ($(LAB),$(filter $(LAB), lock)) UPROGS += \ $U/_stats -endif UPROGS += \ $U/_call\ @@ -236,11 +230,9 @@ endif UPROGS += \ $U/_pgtbltest -ifeq ($(LAB),lock) UPROGS += \ $U/_kalloctest\ $U/_bcachetest -endif ifeq ($(LAB),fs) UPROGS += \ diff --git a/conf/lab.mk b/conf/lab.mk index 1e7f18d..1e20dd0 100644 --- a/conf/lab.mk +++ b/conf/lab.mk @@ -1 +1 @@ -LAB=lock +LAB=thread diff --git a/grade-lab-thread b/grade-lab-thread new file mode 100755 index 0000000..18df65f --- /dev/null +++ b/grade-lab-thread @@ -0,0 +1,70 @@ +#!/usr/bin/env python3 + +import re +import subprocess +from gradelib import * + + +r = Runner(save("xv6.out")) + +@test(20, "uthread") +def test_uthread(): + r.run_qemu(shell_script([ + 'uthread' + ])) + expected = ['thread_a started', 'thread_b started', 'thread_c started'] + expected.extend(['thread_%s %d' % (tid, n) for n in range(100) for tid in ('c', 'a', 'b')]) + expected.extend(['thread_c: exit after 100', 'thread_a: exit after 100', 'thread_b: exit after 100']) + expected.append('thread_schedule: no runnable threads') + if not re.findall('\n'.join(expected), r.qemu.output, re.M): + raise AssertionError('Output does not match expected output') + +@test(5, "answers-thread.txt") +def test_answers(): + # just a simple sanity check, will be graded manually + check_answers("answers-thread.txt") + +# test the first ph task: add locks to eliminate the missing keys. +@test(10, "ph_safe") +def test_ph_safe(): + subprocess.run(['make', 'ph'], check=True) + result = subprocess.run(['./ph', '2'], stdout=subprocess.PIPE, check=True) + out = result.stdout.decode("utf-8") + matches = re.findall(r'^\d+: (\d+) keys missing$', out, re.MULTILINE) + assert_equal(len(matches), 2) + assert_equal(int(matches[0]), 0) + assert_equal(int(matches[1]), 0) + +# test the second ph task: locking that allows put() parallelism +@test(10, "ph_fast") +def test_ph_fast(): + subprocess.run(['make', 'ph'], check=True) + result = subprocess.run(['./ph', '2'], stdout=subprocess.PIPE, check=True) + out = result.stdout.decode("utf-8") + rate2 = re.findall(r' (\d+) puts.second$', out, re.MULTILINE) + assert_equal(len(rate2), 1) + result = subprocess.run(['./ph', '1'], stdout=subprocess.PIPE) + out = result.stdout.decode("utf-8") + rate1 = re.findall(r' (\d+) puts.second$', out, re.MULTILINE) + assert_equal(len(rate1), 1) + rate1 = float(rate1[0]) + rate2 = float(rate2[0]) + # demand that 2 threads yield at least 1.25x the + # throughput of a single thread. + if rate2 < 1.25 * rate1: + raise AssertionError('Parallel put() speedup is less than 1.25x') + +@test(14, "barrier") +def test_barrier(): + subprocess.run(['make', 'barrier']) + result = subprocess.run(['./barrier', '2'], stdout=subprocess.PIPE) + out = result.stdout.decode("utf-8") + if not re.match(r'^OK; passed$', out): + raise AssertionError('Barrier failed') + +@test(1, "time") +def test_time(): + check_time() + +run_tests() + diff --git a/notxv6/barrier.c b/notxv6/barrier.c new file mode 100644 index 0000000..12793e8 --- /dev/null +++ b/notxv6/barrier.c @@ -0,0 +1,78 @@ +#include <stdlib.h> +#include <unistd.h> +#include <stdio.h> +#include <assert.h> +#include <pthread.h> + +static int nthread = 1; +static int round = 0; + +struct barrier { + pthread_mutex_t barrier_mutex; + pthread_cond_t barrier_cond; + int nthread; // Number of threads that have reached this round of the barrier + int round; // Barrier round +} bstate; + +static void +barrier_init(void) +{ + assert(pthread_mutex_init(&bstate.barrier_mutex, NULL) == 0); + assert(pthread_cond_init(&bstate.barrier_cond, NULL) == 0); + bstate.nthread = 0; +} + +static void +barrier() +{ + // YOUR CODE HERE + // + // Block until all threads have called barrier() and + // then increment bstate.round. + // + +} + +static void * +thread(void *xa) +{ + long n = (long) xa; + long delay; + int i; + + for (i = 0; i < 20000; i++) { + int t = bstate.round; + assert (i == t); + barrier(); + usleep(random() % 100); + } + + return 0; +} + +int +main(int argc, char *argv[]) +{ + pthread_t *tha; + void *value; + long i; + double t1, t0; + + if (argc < 2) { + fprintf(stderr, "%s: %s nthread\n", argv[0], argv[0]); + exit(-1); + } + nthread = atoi(argv[1]); + tha = malloc(sizeof(pthread_t) * nthread); + srandom(0); + + barrier_init(); + + for(i = 0; i < nthread; i++) { + assert(pthread_create(&tha[i], NULL, thread, (void *) i) == 0); + } + for(i = 0; i < nthread; i++) { + assert(pthread_join(tha[i], &value) == 0); + } + printf("OK; passed\n"); +} diff --git a/notxv6/ph.c b/notxv6/ph.c new file mode 100644 index 0000000..82afe76 --- /dev/null +++ b/notxv6/ph.c @@ -0,0 +1,150 @@ +#include <stdlib.h> +#include <unistd.h> +#include <stdio.h> +#include <assert.h> +#include <pthread.h> +#include <sys/time.h> + +#define NBUCKET 5 +#define NKEYS 100000 + +struct entry { + int key; + int value; + struct entry *next; +}; +struct entry *table[NBUCKET]; +int keys[NKEYS]; +int nthread = 1; + + +double +now() +{ + struct timeval tv; + gettimeofday(&tv, 0); + return tv.tv_sec + tv.tv_usec / 1000000.0; +} + +static void +insert(int key, int value, struct entry **p, struct entry *n) +{ + struct entry *e = malloc(sizeof(struct entry)); + e->key = key; + e->value = value; + e->next = n; + *p = e; +} + +static +void put(int key, int value) +{ + int i = key % NBUCKET; + + // is the key already present? + struct entry *e = 0; + for (e = table[i]; e != 0; e = e->next) { + if (e->key == key) + break; + } + if(e){ + // update the existing key. + e->value = value; + } else { + // the new is new. + insert(key, value, &table[i], table[i]); + } + +} + +static struct entry* +get(int key) +{ + int i = key % NBUCKET; + + + struct entry *e = 0; + for (e = table[i]; e != 0; e = e->next) { + if (e->key == key) break; + } + + return e; +} + +static void * +put_thread(void *xa) +{ + int n = (int) (long) xa; // thread number + int b = NKEYS/nthread; + + for (int i = 0; i < b; i++) { + put(keys[b*n + i], n); + } + + return NULL; +} + +static void * +get_thread(void *xa) +{ + int n = (int) (long) xa; // thread number + int missing = 0; + + for (int i = 0; i < NKEYS; i++) { + struct entry *e = get(keys[i]); + if (e == 0) missing++; + } + printf("%d: %d keys missing\n", n, missing); + return NULL; +} + +int +main(int argc, char *argv[]) +{ + pthread_t *tha; + void *value; + double t1, t0; + + + if (argc < 2) { + fprintf(stderr, "Usage: %s nthreads\n", argv[0]); + exit(-1); + } + nthread = atoi(argv[1]); + tha = malloc(sizeof(pthread_t) * nthread); + srandom(0); + assert(NKEYS % nthread == 0); + for (int i = 0; i < NKEYS; i++) { + keys[i] = random(); + } + + // + // first the puts + // + t0 = now(); + for(int i = 0; i < nthread; i++) { + assert(pthread_create(&tha[i], NULL, put_thread, (void *) (long) i) == 0); + } + for(int i = 0; i < nthread; i++) { + assert(pthread_join(tha[i], &value) == 0); + } + t1 = now(); + + printf("%d puts, %.3f seconds, %.0f puts/second\n", + NKEYS, t1 - t0, NKEYS / (t1 - t0)); + + // + // now the gets + // + t0 = now(); + for(int i = 0; i < nthread; i++) { + assert(pthread_create(&tha[i], NULL, get_thread, (void *) (long) i) == 0); + } + for(int i = 0; i < nthread; i++) { + assert(pthread_join(tha[i], &value) == 0); + } + t1 = now(); + + printf("%d gets, %.3f seconds, %.0f gets/second\n", + NKEYS*nthread, t1 - t0, (NKEYS*nthread) / (t1 - t0)); +} diff --git a/user/uthread.c b/user/uthread.c new file mode 100644 index 0000000..18b773d --- /dev/null +++ b/user/uthread.c @@ -0,0 +1,161 @@ +#include "kernel/types.h" +#include "kernel/stat.h" +#include "user/user.h" + +/* Possible states of a thread: */ +#define FREE 0x0 +#define RUNNING 0x1 +#define RUNNABLE 0x2 + +#define STACK_SIZE 8192 +#define MAX_THREAD 4 + + +struct thread { + char stack[STACK_SIZE]; /* the thread's stack */ + int state; /* FREE, RUNNING, RUNNABLE */ +}; +struct thread all_thread[MAX_THREAD]; +struct thread *current_thread; +extern void thread_switch(uint64, uint64); + +void +thread_init(void) +{ + // main() is thread 0, which will make the first invocation to + // thread_schedule(). It needs a stack so that the first thread_switch() can + // save thread 0's state. + current_thread = &all_thread[0]; + current_thread->state = RUNNING; +} + +void +thread_schedule(void) +{ + struct thread *t, *next_thread; + + /* Find another runnable thread. */ + next_thread = 0; + t = current_thread + 1; + for(int i = 0; i < MAX_THREAD; i++){ + if(t >= all_thread + MAX_THREAD) + t = all_thread; + if(t->state == RUNNABLE) { + next_thread = t; + break; + } + t = t + 1; + } + + if (next_thread == 0) { + printf("thread_schedule: no runnable threads\n"); + exit(-1); + } + + if (current_thread != next_thread) { /* switch threads? */ + 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(??, ??); + */ + } else + next_thread = 0; +} + +void +thread_create(void (*func)()) +{ + struct thread *t; + + for (t = all_thread; t < all_thread + MAX_THREAD; t++) { + if (t->state == FREE) break; + } + t->state = RUNNABLE; + // YOUR CODE HERE +} + +void +thread_yield(void) +{ + current_thread->state = RUNNABLE; + thread_schedule(); +} + +volatile int a_started, b_started, c_started; +volatile int a_n, b_n, c_n; + +void +thread_a(void) +{ + int i; + printf("thread_a started\n"); + a_started = 1; + while(b_started == 0 || c_started == 0) + thread_yield(); + + for (i = 0; i < 100; i++) { + printf("thread_a %d\n", i); + a_n += 1; + thread_yield(); + } + printf("thread_a: exit after %d\n", a_n); + + current_thread->state = FREE; + thread_schedule(); +} + +void +thread_b(void) +{ + int i; + printf("thread_b started\n"); + b_started = 1; + while(a_started == 0 || c_started == 0) + thread_yield(); + + for (i = 0; i < 100; i++) { + printf("thread_b %d\n", i); + b_n += 1; + thread_yield(); + } + printf("thread_b: exit after %d\n", b_n); + + current_thread->state = FREE; + thread_schedule(); +} + +void +thread_c(void) +{ + int i; + printf("thread_c started\n"); + c_started = 1; + while(a_started == 0 || b_started == 0) + thread_yield(); + + for (i = 0; i < 100; i++) { + printf("thread_c %d\n", i); + c_n += 1; + thread_yield(); + } + printf("thread_c: exit after %d\n", c_n); + + current_thread->state = FREE; + thread_schedule(); +} + +int +main(int argc, char *argv[]) +{ + a_started = b_started = c_started = 0; + a_n = b_n = c_n = 0; + thread_init(); + thread_create(thread_a); + thread_create(thread_b); + thread_create(thread_c); + current_thread->state = FREE; + thread_schedule(); + exit(0); +} diff --git a/user/uthread_switch.S b/user/uthread_switch.S new file mode 100644 index 0000000..5defb12 --- /dev/null +++ b/user/uthread_switch.S @@ -0,0 +1,11 @@ + .text + + /* + * save the old thread's registers, + * restore the new thread's registers. + */ + + .globl thread_switch +thread_switch: + /* YOUR CODE HERE */ + ret /* return to ra */ |