text: /* 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 <stdio.h>
  #include "tests/threads/tests.h"
  #include "threads/init.h"
  #include "threads/malloc.h"
  #include "threads/synch.h"
  #include "threads/thread.h"
  #include "devices/timer.h"
  
  static void test_sleep (int thread_cnt, int iterations);
  
  void
  test_alarm_single (void)
  {
    test_sleep (5, 1);
  }
  
  void
  test_alarm_multiple (void)
  {
    test_sleep (5, 7);
  }
  
  /* 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. */
  };
  
  /* Information about an individual thread in the test. */
  struct sleep_thread {
    struct sleep_test* test;     /* Info shared between all threads. */
    int id;                     /* Sleeper ID. */
    int duration;               /* Number of ticks to sleep. */
    int iterations;             /* Iterations counted so far. */
  };
  
  static void sleeper (void*);
  
  /* Runs THREAD_CNT threads thread sleep ITERATIONS times each. */
  static void
  test_sleep (int thread_cnt, int iterations)
  {
    struct sleep_test test;
    struct sleep_thread* threads;
    int* output, *op;
    int product;
    int i;
  
    /* This test does not work with the MLFQS. */
    ASSERT (!thread_mlfqs);
  
    msg ("Creating %d threads to sleep %d times each.", thread_cnt, iterations);
    msg ("Thread 0 sleeps 10 ticks each time,");
    msg ("thread 1 sleeps 20 ticks each time, and so on.");
    msg ("If successful, product of iteration count and");
    msg ("sleep duration will appear in nondescending order.");
  
    /* 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);
    test.output_pos = output;
  
    /* Start threads. */
    ASSERT (output != NULL);
    for (i = 0; i < thread_cnt; i++) {
      struct sleep_thread* t = threads + i;
      char name[16];
  
      t->test = &test;
      t->id = i;
      t->duration = (i + 1) * 10;
      t->iterations = 0;
  
      snprintf (name, sizeof name, "thread %d", i);
      thread_create (name, PRI_DEFAULT, sleeper, t);
    }
  
    /* Wait long enough for all the threads to finish. */
    timer_sleep (100 + thread_cnt * iterations * 10 + 100);
  
    /* 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;
  
      msg ("thread %d: duration=%d, iteration=%d, product=%d",
           t->id, t->duration, t->iterations, new_prod);
  
      if (new_prod >= product)
      { product = new_prod; }
      else
        fail ("thread %d woke up out of order (%d > %d)!",
              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)
        fail ("thread %d woke up %d times instead of %d",
              i, threads[i].iterations, iterations);
  
    lock_release (&test.output_lock);
    free (output);
    free (threads);
  }
  
  /* Sleeper thread. */
  static void
  sleeper (void* t_)
  {
    struct sleep_thread* t = t_;
    struct sleep_test* test = t->test;
    int i;
  
    for (i = 1; i <= test->iterations; i++) {
      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);
    }
  }
  