-/* Problem 1-3: Priority Scheduling tests.
+/* Problem 1-3: 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
<startled@leland.stanford.edu>, Greg Hutchins
<gmh@leland.stanford.edu>, Yu Ping Hu <yph@cs.stanford.edu>.
- Modified by arens. */
+ Modified by arens and yph. */
-#ifdef MLFQS
-#error This test not applicable with MLFQS enabled.
-#endif
+/* Uncomment to print progress messages. */
+/*#define SHOW_PROGRESS*/
#include "threads/test.h"
#include <stdio.h>
+#include <inttypes.h>
#include "threads/synch.h"
#include "threads/thread.h"
+#include "devices/timer.h"
-static void test_preempt (void);
-static void test_fifo (void);
-static void test_donate_return (void);
+static thread_func io_thread;
+static thread_func cpu_thread;
+static thread_func io_cpu_thread;
void
test (void)
{
- /* Make sure our priority is the default. */
- ASSERT (thread_get_priority () == PRI_DEFAULT);
+ 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]);
+ }
- test_preempt ();
- test_fifo ();
- test_donate_return ();
+ /* Wait for threads to finish. */
+ for (i = 0; i < 3; i++)
+ sema_down (&done[i]);
+ printf ("Multilevel feedback queue scheduler test done.\n");
}
-\f
-static thread_func simple_thread_func;
-static thread_func acquire_thread_func;
static void
-test_preempt (void)
+cpu_thread (void *sema_)
{
- 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");
+ 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
-test_fifo (void)
+io_thread (void *sema_)
{
+ struct semaphore *sema = sema_;
+ int64_t start = timer_ticks ();
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 < 10; i++)
+ for (i = 0; i < 1000; i++)
{
- char name[16];
- snprintf (name, sizeof name, "%d", i);
- thread_create (name, PRI_DEFAULT + 1, simple_thread_func, NULL);
+ timer_sleep (10);
+#ifdef SHOW_PROGRESS
+ printf ("IO intensive: %d\n", thread_get_priority ());
+#endif
}
- thread_set_priority (PRI_DEFAULT);
- printf ("FIFO preemption test done.\n");
+ printf ("IO bound thread finished in %"PRId64" ticks.\n",
+ timer_elapsed (start));
+
+ sema_up (sema);
}
static void
-test_donate_return (void)
+io_cpu_thread (void *sema_)
{
+ struct semaphore *sema = sema_;
struct lock lock;
+ int64_t start = timer_ticks ();
+ int i;
- 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");
-}
+ lock_init (&lock, "io & cpu");
-static void
-simple_thread_func (void *aux UNUSED)
-{
- int i;
-
- for (i = 0; i < 5; i++)
+ for (i = 0; i < 800; i++)
{
- printf ("Thread %s iteration %d\n", thread_name (), i);
- thread_yield ();
+ 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 ("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 ());
+ printf ("Alternating IO/CPU thread finished in %"PRId64" ticks.\n",
+ timer_elapsed (start));
+
+ sema_up (sema);
}