From 3565288c68d89554939dd594717c7a196b6a9f81 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Thu, 14 Oct 2004 06:14:16 +0000 Subject: [PATCH] Add more tests. --- .../{alarm-simple.c => alarm-multiple.c} | 7 +- grading/threads/alarm-single.c | 118 ++++++++++++++++ grading/threads/mlfqs.c | 130 ++++++++++++++++++ grading/threads/priority-donate-multiple.c | 87 ++++++++++++ grading/threads/priority-donate-nest.c | 104 ++++++++++++++ grading/threads/priority-donate-one.c | 63 +++++++++ grading/threads/priority-fifo.c | 92 +++++++++++++ grading/threads/priority-preempt.c | 52 +++++++ 8 files changed, 650 insertions(+), 3 deletions(-) rename grading/threads/{alarm-simple.c => alarm-multiple.c} (97%) create mode 100644 grading/threads/alarm-single.c create mode 100644 grading/threads/mlfqs.c create mode 100644 grading/threads/priority-donate-multiple.c create mode 100644 grading/threads/priority-donate-nest.c create mode 100644 grading/threads/priority-donate-one.c create mode 100644 grading/threads/priority-fifo.c create mode 100644 grading/threads/priority-preempt.c diff --git a/grading/threads/alarm-simple.c b/grading/threads/alarm-multiple.c similarity index 97% rename from grading/threads/alarm-simple.c rename to grading/threads/alarm-multiple.c index 65f1ae8..ac42fb3 100644 --- a/grading/threads/alarm-simple.c +++ b/grading/threads/alarm-multiple.c @@ -12,15 +12,16 @@ #include "threads/thread.h" #include "devices/timer.h" -/* Number of iterations. */ -#define ITERATION_CNT 1 +#ifdef MLFQS +#error This test not applicable with MLFQS enabled. +#endif static void test_sleep (int iterations); void test (void) { - test_sleep (ITERATION_CNT); + test_sleep (7); } struct sleep_thread_data diff --git a/grading/threads/alarm-single.c b/grading/threads/alarm-single.c new file mode 100644 index 0000000..521acf6 --- /dev/null +++ b/grading/threads/alarm-single.c @@ -0,0 +1,118 @@ +/* Problem 1-1: Alarm Clock tests. + + Based on a test originally submitted for Stanford's CS 140 in + winter 1998 by Rob Baesman , Ben + Taskar , and Toli Kuznets + . */ + +#include "threads/test.h" +#include +#include "threads/malloc.h" +#include "threads/synch.h" +#include "threads/thread.h" +#include "devices/timer.h" + +#ifdef MLFQS +#error This test not applicable with MLFQS enabled. +#endif + +static void test_sleep (int iterations); + +void +test (void) +{ + test_sleep (1); +} + +struct sleep_thread_data + { + int64_t start; /* Start time. */ + int duration; /* Number of ticks to sleep. */ + int iterations; /* Number of iterations to run. */ + struct semaphore done; /* Completion semaphore. */ + tid_t tid; /* Thread ID. */ + + struct lock *lock; /* Lock on access to remaining members. */ + int *product; /* Largest product so far. */ + char **out; /* Output pointer. */ + }; + +static void sleeper (void *); + +static void +test_sleep (int iterations) +{ + struct sleep_thread_data threads[5]; + const int thread_cnt = sizeof threads / sizeof *threads; + char *output, *cp; + struct lock lock; + int64_t start; + int product; + int i; + + printf ("\n" + "Testing %d sleeps per thread.\n" + "If successful, product of iteration count and\n" + "sleep duration will appear in nondescending order.\n", + iterations); + + /* Start all the threads. */ + product = 0; + lock_init (&lock, "product"); + cp = output = malloc (128 * iterations * thread_cnt); + ASSERT (output != NULL); + start = timer_ticks (); + for (i = 0; i < thread_cnt; i++) + { + struct sleep_thread_data *t; + char name[16]; + + snprintf (name, sizeof name, "thread %d", i); + t = threads + i; + t->start = start; + t->duration = (i + 1) * 10; + t->iterations = iterations; + sema_init (&t->done, 0, name); + t->tid = thread_create (name, PRI_DEFAULT, sleeper, t); + + t->lock = &lock; + t->product = &product; + t->out = &cp; + } + + /* Wait for all the threads to finish. */ + for (i = 0; i < thread_cnt; i++) + sema_down (&threads[i].done); + + printf ("%s...done\n", output); +} + +static void +sleeper (void *t_) +{ + struct sleep_thread_data *t = t_; + int i; + + for (i = 1; i <= t->iterations; i++) + { + int old_product; + int new_product = i * t->duration; + + timer_sleep ((t->start + new_product) - timer_ticks ()); + + lock_acquire (t->lock); + old_product = *t->product; + *t->product = new_product; + *t->out += snprintf (*t->out, 128, + "%s: duration=%d, iteration=%d, product=%d\n", + thread_name (), t->duration, i, new_product); + if (old_product > new_product) + *t->out += snprintf (*t->out, 128, + "%s: Out of order sleep completion (%d > %d)!\n", + thread_name (), old_product, new_product); + lock_release (t->lock); + } + + /* Signal completion. */ + sema_up (&t->done); +} diff --git a/grading/threads/mlfqs.c b/grading/threads/mlfqs.c new file mode 100644 index 0000000..cbf6e81 --- /dev/null +++ b/grading/threads/mlfqs.c @@ -0,0 +1,130 @@ +/* Problem 1-4: Advanced Scheduler tests. + + This depends on a correctly working Alarm Clock (Problem 1-1). + + Run this test with and without the MLFQS enabled. The + threads' reported test should be better with MLFQS on than + with it off. You may have to tune the loop counts to get + reasonable numbers. + + Based on a test originally submitted for Stanford's CS 140 in + winter 1999 by by Matt Franklin + , Greg Hutchins + , Yu Ping Hu . + Modified by arens and yph. */ + +/* Uncomment to print progress messages. */ +#define SHOW_PROGRESS + +#include "threads/test.h" +#include +#include +#include "threads/synch.h" +#include "threads/thread.h" +#include "devices/timer.h" + +static thread_func io_thread; +static thread_func cpu_thread; +static thread_func io_cpu_thread; + +void +test (void) +{ + static thread_func *funcs[] = {io_thread, cpu_thread, io_cpu_thread}; + static const char *names[] = {"IO", "CPU", "IO & CPU"}; + struct semaphore done[3]; + int i; + + printf ("\n" + "Testing multilevel feedback queue scheduler.\n"); + + /* Start threads. */ + for (i = 0; i < 3; i++) + { + sema_init (&done[i], 0, names[i]); + thread_create (names[i], PRI_DEFAULT, funcs[i], &done[i]); + } + + /* Wait for threads to finish. */ + for (i = 0; i < 3; i++) + sema_down (&done[i]); + printf ("Multilevel feedback queue scheduler test done.\n"); +} + +static void +cpu_thread (void *sema_) +{ + struct semaphore *sema = sema_; + int64_t start = timer_ticks (); + struct lock lock; + int i; + + lock_init (&lock, "cpu"); + + for (i = 0; i < 5000; i++) + { + lock_acquire (&lock); +#ifdef SHOW_PROGRESS + printf ("CPU intensive: %d\n", thread_get_priority ()); +#endif + lock_release (&lock); + } + + printf ("CPU bound thread finished in %"PRId64" ticks.\n", + timer_elapsed (start)); + + sema_up (sema); +} + +static void +io_thread (void *sema_) +{ + struct semaphore *sema = sema_; + int64_t start = timer_ticks (); + int i; + + for (i = 0; i < 1000; i++) + { + timer_sleep (10); +#ifdef SHOW_PROGRESS + printf ("IO intensive: %d\n", thread_get_priority ()); +#endif + } + + printf ("IO bound thread finished in %"PRId64" ticks.\n", + timer_elapsed (start)); + + sema_up (sema); +} + +static void +io_cpu_thread (void *sema_) +{ + struct semaphore *sema = sema_; + struct lock lock; + int64_t start = timer_ticks (); + int i; + + lock_init (&lock, "io & cpu"); + + for (i = 0; i < 800; i++) + { + int j; + + timer_sleep (10); + + for (j = 0; j < 15; j++) + { + lock_acquire (&lock); +#ifdef SHOW_PROGRESS + printf ("Alternating IO/CPU: %d\n", thread_get_priority ()); +#endif + lock_release (&lock); + } + } + + printf ("Alternating IO/CPU thread finished in %"PRId64" ticks.\n", + timer_elapsed (start)); + + sema_up (sema); +} diff --git a/grading/threads/priority-donate-multiple.c b/grading/threads/priority-donate-multiple.c new file mode 100644 index 0000000..971caf2 --- /dev/null +++ b/grading/threads/priority-donate-multiple.c @@ -0,0 +1,87 @@ +/* Problem 1-3: Priority Scheduling tests. + + Based on a test originally submitted for Stanford's CS 140 in + winter 1999 by by Matt Franklin + , Greg Hutchins + , Yu Ping Hu . + Modified by arens. */ + +#ifdef MLFQS +#error This test not applicable with MLFQS enabled. +#endif + +#include "threads/test.h" +#include +#include "threads/synch.h" +#include "threads/thread.h" + +static void test_donate_multiple (void); + +void +test (void) +{ + /* Make sure our priority is the default. */ + ASSERT (thread_get_priority () == PRI_DEFAULT); + + test_donate_multiple (); +} + +static thread_func a_thread_func; +static thread_func b_thread_func; + +static void +test_donate_multiple (void) +{ + struct lock a, b; + + printf ("\n" + "Testing multiple priority donation.\n" + "If the statements printed below are all true, you pass.\n"); + + lock_init (&a, "a"); + lock_init (&b, "b"); + + lock_acquire (&a); + lock_acquire (&b); + + thread_create ("a", PRI_DEFAULT + 1, a_thread_func, &a); + printf (" 1. Main thread should have priority %d. Actual priority: %d.\n", + PRI_DEFAULT + 1, thread_get_priority ()); + + thread_create ("b", PRI_DEFAULT + 2, b_thread_func, &b); + printf (" 2. Main thread should have priority %d. Actual priority: %d.\n", + PRI_DEFAULT + 2, thread_get_priority ()); + + lock_release (&b); + printf (" 5. Thread b should have just finished.\n"); + printf (" 6. Main thread should have priority %d. Actual priority: %d.\n", + PRI_DEFAULT + 1, thread_get_priority ()); + + lock_release (&a); + printf (" 9. Thread a should have just finished.\n"); + printf ("10. Main thread should have priority %d. Actual priority: %d.\n", + PRI_DEFAULT, thread_get_priority ()); + printf ("Multiple priority priority donation test finished.\n"); +} + +static void +a_thread_func (void *lock_) +{ + struct lock *lock = lock_; + + lock_acquire (lock); + printf (" 7. Thread a acquired lock a.\n"); + lock_release (lock); + printf (" 8. Thread b finished.\n"); +} + +static void +b_thread_func (void *lock_) +{ + struct lock *lock = lock_; + + lock_acquire (lock); + printf (" 3. Thread b acquired lock b.\n"); + lock_release (lock); + printf (" 4. Thread b finished.\n"); +} diff --git a/grading/threads/priority-donate-nest.c b/grading/threads/priority-donate-nest.c new file mode 100644 index 0000000..d391233 --- /dev/null +++ b/grading/threads/priority-donate-nest.c @@ -0,0 +1,104 @@ +/* Problem 1-3: Priority Scheduling tests. + + Based on a test originally submitted for Stanford's CS 140 in + winter 1999 by by Matt Franklin + , Greg Hutchins + , Yu Ping Hu . + Modified by arens. */ + +#ifdef MLFQS +#error This test not applicable with MLFQS enabled. +#endif + +#include "threads/test.h" +#include +#include "threads/synch.h" +#include "threads/thread.h" + +static void test_donate_nest (void); + +void +test (void) +{ + /* Make sure our priority is the default. */ + ASSERT (thread_get_priority () == PRI_DEFAULT); + + test_donate_nest (); +} + +static thread_func medium_thread_func; +static thread_func high_thread_func; + +struct locks + { + struct lock *a; + struct lock *b; + }; + +static void +test_donate_nest (void) +{ + struct lock a, b; + struct locks locks; + + printf ("\n" + "Testing nested priority donation.\n" + "If the statements printed below are all true, you pass.\n"); + + lock_init (&a, "a"); + lock_init (&b, "b"); + + lock_acquire (&a); + + locks.a = &a; + locks.b = &b; + thread_create ("medium", PRI_DEFAULT + 1, medium_thread_func, &locks); + thread_yield (); + printf (" 1. Low thread should have priority %d. Actual priority: %d.\n", + PRI_DEFAULT + 1, thread_get_priority ()); + + thread_create ("high", PRI_DEFAULT + 2, high_thread_func, &b); + thread_yield (); + printf (" 2. Low thread should have priority %d. Actual priority: %d.\n", + PRI_DEFAULT + 2, thread_get_priority ()); + + lock_release (&a); + thread_yield (); + printf (" 9. Medium thread should just have finished.\n"); + printf ("10. Low thread should have priority %d. Actual priority: %d.\n", + PRI_DEFAULT, thread_get_priority ()); + printf ("Nested priority priority donation test finished.\n"); +} + +static void +medium_thread_func (void *locks_) +{ + struct locks *locks = locks_; + + lock_acquire (locks->b); + lock_acquire (locks->a); + + printf (" 3. Medium thread should have priority %d. Actual priority: %d\n", + PRI_DEFAULT + 2, thread_get_priority ()); + printf (" 4. Medium thread got the lock.\n"); + + lock_release (locks->a); + thread_yield (); + + lock_release (locks->b); + thread_yield (); + + printf (" 7. High thread should have just finished.\n"); + printf (" 8. Middle thread finished.\n"); +} + +static void +high_thread_func (void *lock_) +{ + struct lock *lock = lock_; + + lock_acquire (lock); + printf (" 5. High thread got the lock.\n"); + lock_release (lock); + printf (" 6. High thread finished.\n"); +} diff --git a/grading/threads/priority-donate-one.c b/grading/threads/priority-donate-one.c new file mode 100644 index 0000000..e6382bd --- /dev/null +++ b/grading/threads/priority-donate-one.c @@ -0,0 +1,63 @@ +/* Problem 1-3: Priority Scheduling tests. + + Based on a test originally submitted for Stanford's CS 140 in + winter 1999 by by Matt Franklin + , Greg Hutchins + , Yu Ping Hu . + Modified by arens. */ + +#ifdef MLFQS +#error This test not applicable with MLFQS enabled. +#endif + +#include "threads/test.h" +#include +#include "threads/synch.h" +#include "threads/thread.h" + +static void test_donate_return (void); + +void +test (void) +{ + /* Make sure our priority is the default. */ + ASSERT (thread_get_priority () == PRI_DEFAULT); + + test_donate_return (); +} + +static thread_func acquire_thread_func; + +static void +test_donate_return (void) +{ + struct lock lock; + + printf ("\n" + "Testing priority donation.\n" + "If the statements printed below are all true, you pass.\n"); + + lock_init (&lock, "donor"); + lock_acquire (&lock); + thread_create ("acquire1", PRI_DEFAULT + 1, acquire_thread_func, &lock); + printf ("This thread should have priority %d. Actual priority: %d.\n", + PRI_DEFAULT + 1, thread_get_priority ()); + thread_create ("acquire2", PRI_DEFAULT + 2, acquire_thread_func, &lock); + printf ("This thread should have priority %d. Actual priority: %d.\n", + PRI_DEFAULT + 2, thread_get_priority ()); + lock_release (&lock); + printf ("acquire2 and acquire1 must already have finished, in that order.\n" + "This should be the last line before finishing this test.\n" + "Priority donation test done.\n"); +} + +static void +acquire_thread_func (void *lock_) +{ + struct lock *lock = lock_; + + lock_acquire (lock); + printf ("%s: got the lock\n", thread_name ()); + lock_release (lock); + printf ("%s: done\n", thread_name ()); +} diff --git a/grading/threads/priority-fifo.c b/grading/threads/priority-fifo.c new file mode 100644 index 0000000..b49ff5d --- /dev/null +++ b/grading/threads/priority-fifo.c @@ -0,0 +1,92 @@ +/* Problem 1-3: Priority Scheduling tests. + + Based on a test originally submitted for Stanford's CS 140 in + winter 1999 by by Matt Franklin + , Greg Hutchins + , Yu Ping Hu . + Modified by arens. */ + +#ifdef MLFQS +#error This test not applicable with MLFQS enabled. +#endif + +#include "threads/test.h" +#include +#include "threads/malloc.h" +#include "threads/synch.h" +#include "threads/thread.h" + +static void test_fifo (void); + +void +test (void) +{ + /* Make sure our priority is the default. */ + ASSERT (thread_get_priority () == PRI_DEFAULT); + + test_fifo (); +} + +static thread_func simple_thread_func; + +struct simple_thread_data + { + struct lock *lock; /* Lock on output. */ + char **out; /* Output pointer. */ + }; + +static void +test_fifo (void) +{ + struct simple_thread_data data; + struct lock lock; + char *output, *cp; + int i; + + printf ("\n" + "Testing FIFO preemption.\n" + "10 threads will iterate 5 times in the same order each time.\n" + "If the order varies then there is a bug.\n"); + + output = cp = malloc (5 * 10 * 128); + ASSERT (output != NULL); + lock_init (&lock, "output"); + + data.lock = &lock; + data.out = &cp; + + thread_set_priority (PRI_DEFAULT + 2); + for (i = 0; i < 10; i++) + { + char name[16]; + snprintf (name, sizeof name, "%d", i); + thread_create (name, PRI_DEFAULT + 1, simple_thread_func, &data); + } + thread_set_priority (PRI_DEFAULT); + + lock_acquire (&lock); + *cp = '\0'; + printf ("%sFIFO preemption test done.\n", output); + lock_release (&lock); +} + +static void +simple_thread_func (void *data_) +{ + struct simple_thread_data *data = data_; + int i; + + for (i = 0; i < 5; i++) + { + lock_acquire (data->lock); + *data->out += snprintf (*data->out, 128, "Thread %s iteration %d\n", + thread_name (), i); + lock_release (data->lock); + thread_yield (); + } + + lock_acquire (data->lock); + *data->out += snprintf (*data->out, 128, + "Thread %s done!\n", thread_name ()); + lock_release (data->lock); +} diff --git a/grading/threads/priority-preempt.c b/grading/threads/priority-preempt.c new file mode 100644 index 0000000..1e2a268 --- /dev/null +++ b/grading/threads/priority-preempt.c @@ -0,0 +1,52 @@ +/* Problem 1-3: Priority Scheduling tests. + + Based on a test originally submitted for Stanford's CS 140 in + winter 1999 by by Matt Franklin + , Greg Hutchins + , Yu Ping Hu . + Modified by arens. */ + +#ifdef MLFQS +#error This test not applicable with MLFQS enabled. +#endif + +#include "threads/test.h" +#include +#include "threads/synch.h" +#include "threads/thread.h" + +static void test_preempt (void); + +void +test (void) +{ + /* Make sure our priority is the default. */ + ASSERT (thread_get_priority () == PRI_DEFAULT); + + test_preempt (); +} + +static thread_func simple_thread_func; + +static void +test_preempt (void) +{ + printf ("\n" + "Testing priority preemption.\n"); + thread_create ("high-priority", PRI_DEFAULT + 1, simple_thread_func, NULL); + printf ("The high-priority thread should have already completed.\n" + "Priority preemption test done.\n"); +} + +static void +simple_thread_func (void *aux UNUSED) +{ + int i; + + for (i = 0; i < 5; i++) + { + printf ("Thread %s iteration %d\n", thread_name (), i); + thread_yield (); + } + printf ("Thread %s done!\n", thread_name ()); +} -- 2.30.2