summaryrefslogtreecommitdiff
path: root/notxv6
diff options
context:
space:
mode:
authorMole Shang <[email protected]>2024-02-17 11:55:33 +0800
committerMole Shang <[email protected]>2024-02-17 12:22:07 +0800
commite8e0a7b4c97064eb5e9415726d7e38aaceccd3fd (patch)
treefb42ba5be7a8ae608b968266f62fd71fa889a89d /notxv6
parenta6af72924b115c1177d18d9b1eaba56623e4248b (diff)
parentd85aec2689c4250d0384904bdc11aa618c726bec (diff)
downloadxv6-labs-e8e0a7b4c97064eb5e9415726d7e38aaceccd3fd.tar.gz
xv6-labs-e8e0a7b4c97064eb5e9415726d7e38aaceccd3fd.tar.bz2
xv6-labs-e8e0a7b4c97064eb5e9415726d7e38aaceccd3fd.zip
Merge branch 'thread' into fs
Conflicts: .gitignore Makefile conf/lab.mk kernel/param.h
Diffstat (limited to 'notxv6')
-rw-r--r--notxv6/barrier.c86
-rw-r--r--notxv6/ph.c153
2 files changed, 239 insertions, 0 deletions
diff --git a/notxv6/barrier.c b/notxv6/barrier.c
new file mode 100644
index 0000000..b7737a6
--- /dev/null
+++ b/notxv6/barrier.c
@@ -0,0 +1,86 @@
+#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()
+{
+ // 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 *
+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..db8a630
--- /dev/null
+++ b/notxv6/ph.c
@@ -0,0 +1,153 @@
+#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;
+pthread_mutex_t lock[NBUCKET];
+
+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;
+ }
+ pthread_mutex_lock(&lock[i]);
+ if(e){
+ // update the existing key.
+ e->value = value;
+ } else {
+ // the new is new.
+ insert(key, value, &table[i], table[i]);
+ }
+ pthread_mutex_unlock(&lock[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);
+ 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();
+ }
+
+ //
+ // 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));
+}