From af42b7cc9c85b36ae0fa5da75e4dab80ac236059 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Fri, 17 Sep 2004 06:53:04 +0000 Subject: [PATCH] Add threads tests. --- src/tests/threads/p1-1.c | 121 ++++++++++++++++++++++++++++++++++ src/tests/threads/p1-2.c | 105 ++++++++++++++++++++++++++++++ src/tests/threads/p1-3.c | 108 +++++++++++++++++++++++++++++++ src/tests/threads/p1-4.c | 136 +++++++++++++++++++++++++++++++++++++++ 4 files changed, 470 insertions(+) create mode 100644 src/tests/threads/p1-1.c create mode 100644 src/tests/threads/p1-2.c create mode 100644 src/tests/threads/p1-3.c create mode 100644 src/tests/threads/p1-4.c diff --git a/src/tests/threads/p1-1.c b/src/tests/threads/p1-1.c new file mode 100644 index 0000000..cd1b8b9 --- /dev/null +++ b/src/tests/threads/p1-1.c @@ -0,0 +1,121 @@ +/* Problem 1-1: Alarm Clock tests. + + These tests will work with Pintos "out of the box" because an + implementation of timer_sleep() that "busy-waits" is + included. You need to replace that implementation with one + that doesn't busy-wait. + + Based on a test originally submitted for Stanford's CS 140 in + winter 1998 by Rob Baesman , Ben + Taskar , and Toli Kuznets + . */ + +/* If you've implemented thread_join(), you can uncomment this. */ +/*#define THREAD_JOIN_IMPLEMENTED*/ + +#include "threads/test.h" +#include +#include "threads/synch.h" +#include "threads/thread.h" +#include "devices/timer.h" + +static void test_sleep (int iterations); + +void +test (void) +{ + test_sleep (1); + test_sleep (7); +} + +struct sleep_thread_data + { + int64_t start; /* Start time. */ + int duration; /* Number of ticks to sleep. */ + int iterations; /* Number of iterations to run. */ + int *product; /* Largest product so far. */ + struct lock *lock; /* Lock on access to `product'. */ + struct semaphore done; /* Completion semaphore. */ + tid_t tid; /* Thread ID. */ + }; + +static void sleeper (void *); + +static void +test_sleep (int iterations) +{ + struct sleep_thread_data threads[5]; + const int thread_cnt = sizeof threads / sizeof *threads; + 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"); + 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; + t->product = &product; + t->lock = &lock; + sema_init (&t->done, 0, name); + t->tid = thread_create (name, PRI_DEFAULT, sleeper, t); + } + + /* Wait for all the threads to finish. */ + for (i = 0; i < thread_cnt; i++) + { +#ifdef THREAD_JOIN_IMPLEMENTED + thread_join (threads[i].tid); +#else + sema_down (&threads[i].done); +#endif + } + + printf ("...done\n"); +} + +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; + lock_release (t->lock); + + printf ("%s: duration=%d, iteration=%d, product=%d\n", + thread_name (), t->duration, i, new_product); + + if (old_product > new_product) + printf ("%s: Out of order sleep completion (%d > %d)!\n", + thread_name (), old_product, new_product); + } + + /* Signal completion. */ + sema_up (&t->done); +} diff --git a/src/tests/threads/p1-2.c b/src/tests/threads/p1-2.c new file mode 100644 index 0000000..fb39bb1 --- /dev/null +++ b/src/tests/threads/p1-2.c @@ -0,0 +1,105 @@ +/* Problem 1-2: Join tests. + + Based on a test originally submitted for Stanford's CS 140 in + winter 1998 by Rob Baesman , Ben + Taskar , and Toli Kuznets + . Later modified by shiangc, yph, and + arens. */ +#include "threads/test.h" +#include +#include "threads/interrupt.h" +#include "threads/thread.h" + +static void simple_test (void); +static void quick_test (void); +static void multiple_test (void); + +void +test (void) +{ + simple_test (); + quick_test (); + multiple_test (); +} + +static thread_func simple_thread_func; +static thread_func quick_thread_func; + +static void +simple_test (void) +{ + tid_t tid0; + + printf ("\n" + "Testing simple join.\n" + "Thread 0 should finish before thread 1 starts.\n"); + tid0 = thread_create ("0", PRI_DEFAULT, simple_thread_func, "0"); + thread_yield (); + thread_join (tid0); + simple_thread_func ("1"); + printf ("Simple join test done.\n"); +} + +static void +quick_test (void) +{ + tid_t tid2; + + printf ("\n" + "Testing quick join.\n" + "Thread 2 should finish before thread 3 starts.\n"); + + tid2 = thread_create ("2", PRI_DEFAULT, quick_thread_func, "2"); + thread_yield (); + thread_join (tid2); + simple_thread_func ("3"); + printf ("Quick join test done.\n"); +} + +static void +multiple_test (void) +{ + tid_t tid4, tid5; + + printf ("\n" + "Testing multiple join.\n" + "Threads 4 and 5 should finish before thread 6 starts.\n"); + + tid4 = thread_create ("4", PRI_DEFAULT, simple_thread_func, "4"); + tid5 = thread_create ("5", PRI_DEFAULT, simple_thread_func, "5"); + thread_yield (); + thread_join (tid4); + thread_join (tid5); + simple_thread_func ("6"); + printf ("Multiple join test done.\n"); +} + +void +simple_thread_func (void *name_) +{ + const char *name = name_; + int i; + + for (i = 0; i < 5; i++) + { + printf ("Thread %s iteration %d\n", name, i); + thread_yield (); + } + printf ("Thread %s done!\n", name); +} + +void +quick_thread_func (void *name_) +{ + const char *name = name_; + int i; + + intr_disable (); + + for (i = 0; i < 5; i++) + { + printf ("Thread %s iteration %d\n", name, i); + thread_yield (); + } + printf ("Thread %s done!\n", name); +} diff --git a/src/tests/threads/p1-3.c b/src/tests/threads/p1-3.c new file mode 100644 index 0000000..32c91e6 --- /dev/null +++ b/src/tests/threads/p1-3.c @@ -0,0 +1,108 @@ +/* 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. */ + +#include "threads/test.h" +#include +#include "threads/thread.h" + +static void test_preempt (void); +static void test_fifo (void); +static void test_donate_return (void); + +void +test (void) +{ + /* Make sure our prority is the default. */ + ASSERT (thread_get_priority () == PRI_DEFAULT); + + test_preempt (); + test_fifo (); + test_donate_return (); +} + +static thread_func simple_thread_func; +static thread_func acquire_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 +test_fifo (void) +{ + int i; + + printf ("\n" + "Testing FIFO preemption.\n" + "5 threads will iterate 10 times in the same order each time.\n" + "If the order varies then there is a bug.\n"); + + thread_set_priority (PRI_DEFAULT + 2); + for (i = 0; i < 5; i++) + { + char name[16]; + snprintf (name, sizeof name, "%d", i); + thread_create (name, PRI_DEFAULT + 1, simple_thread_func, NULL); + } + thread_set_priority (PRI_DEFAULT); + + printf ("FIFO preemption test done.\n"); +} + +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 (); + printf ("acquire1 and acquire2 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 +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 ()); +} + +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/src/tests/threads/p1-4.c b/src/tests/threads/p1-4.c new file mode 100644 index 0000000..7c97e37 --- /dev/null +++ b/src/tests/threads/p1-4.c @@ -0,0 +1,136 @@ +/* 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. + + 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. */ + +/* If you've implemented thread_join(), you can uncomment this. */ +/*#define THREAD_JOIN_IMPLEMENTED*/ + +/* Uncomment to print progress messages. */ +/*#define SHOW_PROGRESS*/ + +#include "threads/test.h" +#include +#include "threads/synch.h" +#include "threads/thread.h" + +static thread_func io_thread; +static thread_func cpu_thread; +static thread_func io_cpu_thread; + +void +test (void) +{ + static const thread_func *funcs[] = {io_thread, cpu_thread, io_cpu_thread}; + static const char *names[] = {"IO", "CPU", "IO & CPU"}; + struct semaphore done[3]; + tid_t tids[3]; + + printf ("\n" + "Testing multilevel feedback queue scheduler.\n"); + + /* Start threads. */ + for (i = 0; i < 3; i++) + { + sema_init (&done[i], 0); + tids[i] = thread_create (names[i], PRI_DEFAULT, funcs[i], &done[i]); + } + + /* Wait for threads to finish. */ + for (i = 0; i < 3; i++) + { +#ifdef THREAD_JOIN_IMPLEMENTED + thread_join (tids[i]); +#else + sema_down (&done[i]); +#endif + } + 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 %"PRI64d" 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 %"PRI64d" 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 %"PRI64d" ticks.\n", + timer_elapsed (start)); + + sema_up (sema); +} -- 2.30.2