pintos-os.org Git - pintos-anon/blob - src/tests/threads/alarm-wait.c

   1 /* Problem 1-1: Alarm Clock tests.
   2
   3    Creates N threads, each of which sleeps a different, fixed
   4    duration, M times.  Records the wake-up order and verifies
   5    that it is valid. */
   6
   7 #include <stdio.h>
   8 #include "tests/threads/tests.h"
   9 #include "threads/init.h"
  10 #include "threads/malloc.h"
  11 #include "threads/synch.h"
  12 #include "threads/thread.h"
  13 #include "devices/timer.h"
  14
  15 static void test_sleep (int thread_cnt, int iterations);
  16
  17 void
  18 test_alarm_single (void)
  19 {
  20   test_sleep (5, 1);
  21 }
  22
  23 void
  24 test_alarm_multiple (void)
  25 {
  26   test_sleep (5, 7);
  27 }
  28 \f
  29 /* Information about the test. */
  30 struct sleep_test
  31   {
  32     int64_t start;              /* Current time at start of test. */
  33     int iterations;             /* Number of iterations per thread. */
  34
  35     /* Output. */
  36     struct lock output_lock;    /* Lock protecting output buffer. */
  37     int *output_pos;            /* Current position in output buffer. */
  38   };
  39
  40 /* Information about an individual thread in the test. */
  41 struct sleep_thread
  42   {
  43     struct sleep_test *test;     /* Info shared between all threads. */
  44     int id;                     /* Sleeper ID. */
  45     int duration;               /* Number of ticks to sleep. */
  46     int iterations;             /* Iterations counted so far. */
  47   };
  48
  49 static void sleeper (void *);
  50
  51 /* Runs THREAD_CNT threads thread sleep ITERATIONS times each. */
  52 static void
  53 test_sleep (int thread_cnt, int iterations)
  54 {
  55   struct sleep_test test;
  56   struct sleep_thread *threads;
  57   int *output, *op;
  58   int product;
  59   int i;
  60
  61   /* This test does not work with the MLFQS. */
  62   ASSERT (!enable_mlfqs);
  63
  64   msg ("Creating %d threads to sleep %d times each.", thread_cnt, iterations);
  65   msg ("Thread 0 sleeps 10 ticks each time,");
  66   msg ("thread 1 sleeps 20 ticks each time, and so on.");
  67   msg ("If successful, product of iteration count and");
  68   msg ("sleep duration will appear in nondescending order.");
  69
  70   /* Allocate memory. */
  71   threads = malloc (sizeof *threads * thread_cnt);
  72   output = malloc (sizeof *output * iterations * thread_cnt * 2);
  73   if (threads == NULL || output == NULL)
  74     PANIC ("couldn't allocate memory for test");
  75
  76   /* Initialize test. */
  77   test.start = timer_ticks () + 100;
  78   test.iterations = iterations;
  79   lock_init (&test.output_lock);
  80   test.output_pos = output;
  81
  82   /* Start threads. */
  83   ASSERT (output != NULL);
  84   for (i = 0; i < thread_cnt; i++)
  85     {
  86       struct sleep_thread *t = threads + i;
  87       char name[16];
  88
  89       t->test = &test;
  90       t->id = i;
  91       t->duration = (i + 1) * 10;
  92       t->iterations = 0;
  93
  94       snprintf (name, sizeof name, "thread %d", i);
  95       thread_create (name, PRI_DEFAULT, sleeper, t);
  96     }
  97
  98   /* Wait long enough for all the threads to finish. */
  99   timer_sleep (100 + thread_cnt * iterations * 10 + 100);
 100
 101   /* Acquire the output lock in case some rogue thread is still
 102      running. */
 103   lock_acquire (&test.output_lock);
 104
 105   /* Print completion order. */
 106   product = 0;
 107   for (op = output; op < test.output_pos; op++)
 108     {
 109       struct sleep_thread *t;
 110       int new_prod;
 111
 112       ASSERT (*op >= 0 && *op < thread_cnt);
 113       t = threads + *op;
 114
 115       new_prod = ++t->iterations * t->duration;
 116
 117       msg ("thread %d: duration=%d, iteration=%d, product=%d",
 118            t->id, t->duration, t->iterations, new_prod);
 119
 120       if (new_prod >= product)
 121         product = new_prod;
 122       else
 123         fail ("thread %d woke up out of order (%d > %d)!",
 124               t->id, product, new_prod);
 125     }
 126
 127   /* Verify that we had the proper number of wakeups. */
 128   for (i = 0; i < thread_cnt; i++)
 129     if (threads[i].iterations != iterations)
 130       fail ("thread %d woke up %d times instead of %d",
 131             i, threads[i].iterations, iterations);
 132
 133   lock_release (&test.output_lock);
 134   free (output);
 135   free (threads);
 136 }
 137
 138 /* Sleeper thread. */
 139 static void
 140 sleeper (void *t_)
 141 {
 142   struct sleep_thread *t = t_;
 143   struct sleep_test *test = t->test;
 144   int i;
 145
 146   for (i = 1; i <= test->iterations; i++)
 147     {
 148       int64_t sleep_until = test->start + i * t->duration;
 149       timer_sleep (sleep_until - timer_ticks ());
 150
 151       lock_acquire (&test->output_lock);
 152       *test->output_pos++ = t->id;
 153       lock_release (&test->output_lock);
 154     }
 155 }