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