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