summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Makefile10
-rw-r--r--conf/lab.mk2
-rwxr-xr-xgrade-lab-thread70
-rw-r--r--notxv6/barrier.c78
-rw-r--r--notxv6/ph.c150
-rw-r--r--user/uthread.c161
-rw-r--r--user/uthread_switch.S11
7 files changed, 472 insertions, 10 deletions
diff --git a/Makefile b/Makefile
index a4e961a..fd6e82e 100644
--- a/Makefile
+++ b/Makefile
@@ -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 */