/* Problem 1-1: Alarm Clock tests.
- Based on a test originally submitted for Stanford's CS 140 in
- winter 1998 by Rob Baesman <rbaesman@cs.stanford.edu>, Ben
- Taskar <btaskar@cs.stanford.edu>, and Toli Kuznets
- <tolik@cs.stanford.edu>. */
+ Creates N threads, each of which sleeps a different, fixed
+ duration, M times. Records the wake-up order and verifies
+ that it is valid. */
#include "threads/test.h"
#include <stdio.h>
#error This test not applicable with MLFQS enabled.
#endif
-static void test_sleep (int iterations);
+static void test_sleep (int thread_cnt, int iterations);
void
test (void)
{
- test_sleep (7);
+ test_sleep (5, 7);
}
+\f
+/* Information about the test. */
+struct sleep_test
+ {
+ int64_t start; /* Current time at start of test. */
+ int iterations; /* Number of iterations per thread. */
+
+ /* Output. */
+ struct lock output_lock; /* Lock protecting output buffer. */
+ int *output_pos; /* Current position in output buffer. */
+ };
-struct sleep_thread_data
+/* Information about an individual thread in the test. */
+struct sleep_thread
{
- int64_t start; /* Start time. */
+ struct sleep_test *test; /* Info shared between all threads. */
+ int id; /* Sleeper ID. */
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. */
+ int iterations; /* Iterations counted so far. */
};
static void sleeper (void *);
+/* Runs THREAD_CNT threads thread sleep ITERATIONS times each. */
static void
-test_sleep (int iterations)
+test_sleep (int thread_cnt, 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;
+ struct sleep_test test;
+ struct sleep_thread *threads;
+ int *output, *op;
int product;
int i;
printf ("\n"
- "Testing %d sleeps per thread.\n"
+ "Creating %d threads to sleep %d times each.\n"
+ "Thread 0 sleeps 10 ticks each time,\n"
+ "thread 1 sleeps 20 ticks each time, and so on.\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);
+ "sleep duration will appear in nondescending order.\n\n"
+ "Running test... ",
+ thread_cnt, iterations);
+
+ /* Allocate memory. */
+ threads = malloc (sizeof *threads * thread_cnt);
+ output = malloc (sizeof *output * iterations * thread_cnt * 2);
+ if (threads == NULL || output == NULL)
+ PANIC ("couldn't allocate memory for test");
+
+ /* Initialize test. */
+ test.start = timer_ticks () + 100;
+ test.iterations = iterations;
+ lock_init (&test.output_lock, "output");
+ test.output_pos = output;
+
+ /* Start threads. */
ASSERT (output != NULL);
- start = timer_ticks ();
for (i = 0; i < thread_cnt; i++)
{
- struct sleep_thread_data *t;
+ struct sleep_thread *t = threads + i;
char name[16];
- snprintf (name, sizeof name, "thread %d", i);
- t = threads + i;
- t->start = start;
+ t->test = &test;
+ t->id = i;
t->duration = (i + 1) * 10;
- t->iterations = iterations;
- sema_init (&t->done, 0, name);
- t->tid = thread_create (name, PRI_DEFAULT, sleeper, t);
+ t->iterations = 0;
- t->lock = &lock;
- t->product = &product;
- t->out = &cp;
+ snprintf (name, sizeof name, "thread %d", i);
+ thread_create (name, PRI_DEFAULT, sleeper, t);
}
- /* Wait for all the threads to finish. */
- for (i = 0; i < thread_cnt; i++)
- sema_down (&threads[i].done);
+ /* Wait long enough for all the threads to finish. */
+ timer_sleep (100 + thread_cnt * iterations * 10 + 100);
+ printf ("done\n\n");
+
+ /* Acquire the output lock in case some rogue thread is still
+ running. */
+ lock_acquire (&test.output_lock);
+
+ /* Print completion order. */
+ product = 0;
+ for (op = output; op < test.output_pos; op++)
+ {
+ struct sleep_thread *t;
+ int new_prod;
+
+ ASSERT (*op >= 0 && *op < thread_cnt);
+ t = threads + *op;
+
+ new_prod = ++t->iterations * t->duration;
+
+ printf ("thread %d: duration=%d, iteration=%d, product=%d\n",
+ t->id, t->duration, t->iterations, new_prod);
+
+ if (new_prod >= product)
+ product = new_prod;
+ else
+ printf ("FAIL: thread %d woke up out of order (%d > %d)!\n",
+ t->id, product, new_prod);
+ }
+
+ /* Verify that we had the proper number of wakeups. */
+ for (i = 0; i < thread_cnt; i++)
+ if (threads[i].iterations != iterations)
+ printf ("FAIL: thread %d woke up %d times instead of %d\n",
+ i, threads[i].iterations, iterations);
- printf ("%s...done\n", output);
+ printf ("Test complete.\n");
+
+ lock_release (&test.output_lock);
+ free (output);
+ free (threads);
}
+/* Sleeper thread. */
static void
sleeper (void *t_)
{
- struct sleep_thread_data *t = t_;
+ struct sleep_thread *t = t_;
+ struct sleep_test *test = t->test;
int i;
- for (i = 1; i <= t->iterations; i++)
+ for (i = 1; i <= test->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);
+ int64_t sleep_until = test->start + i * t->duration;
+ timer_sleep (sleep_until - timer_ticks ());
+
+ lock_acquire (&test->output_lock);
+ *test->output_pos++ = t->id;
+ lock_release (&test->output_lock);
}
-
- /* Signal completion. */
- sema_up (&t->done);
}