pintos-os.org Git - pintos-anon/blob - src/tests/threads/priority-donate-chain.c

   1 /* The main thread set its priority to PRI_MIN and creates 7 threads
   2    (thread 1..7) with priorities PRI_MIN + 3, 6, 9, 12, ...
   3    The main thread initializes 8 locks: lock 0..7 and acquires lock 0.
   4
   5    When thread[i] starts, it first acquires lock[i] (unless i == 7.)
   6    Subsequently, thread[i] attempts to acquire lock[i-1], which is held by
   7    thread[i-1], except for lock[0], which is held by the main thread.
   8    Because the lock is held, thread[i] donates its priority to thread[i-1],
   9    which donates to thread[i-2], and so on until the main thread
  10    receives the donation.
  11
  12    After threads[1..7] have been created and are blocked on locks[0..7],
  13    the main thread releases lock[0], unblocking thread[1], and being
  14    preempted by it.
  15    Thread[1] then completes acquiring lock[0], then releases lock[0],
  16    then releases lock[1], unblocking thread[2], etc.
  17    Thread[7] finally acquires & releases lock[7] and exits, allowing
  18    thread[6], then thread[5] etc. to run and exit until finally the
  19    main thread exits.
  20
  21    In addition, interloper threads are created at priority levels
  22    p = PRI_MIN + 2, 5, 8, 11, ... which should not be run until the
  23    corresponding thread with priority p + 1 has finished.
  24
  25    Written by Godmar Back <gback@cs.vt.edu> */
  26
  27 #include <stdio.h>
  28 #include "tests/threads/tests.h"
  29 #include "threads/init.h"
  30 #include "threads/synch.h"
  31 #include "threads/thread.h"
  32
  33 #define NESTING_DEPTH 8
  34
  35 struct lock_pair
  36   {
  37     struct lock *second;
  38     struct lock *first;
  39   };
  40
  41 static thread_func donor_thread_func;
  42 static thread_func interloper_thread_func;
  43
  44 void
  45 test_priority_donate_chain (void)
  46 {
  47   int i;
  48   struct lock locks[NESTING_DEPTH - 1];
  49   struct lock_pair lock_pairs[NESTING_DEPTH];
  50
  51   /* This test does not work with the MLFQS. */
  52   ASSERT (!thread_mlfqs);
  53
  54   thread_set_priority (PRI_MIN);
  55
  56   for (i = 0; i < NESTING_DEPTH - 1; i++)
  57     lock_init (&locks[i]);
  58
  59   lock_acquire (&locks[0]);
  60   msg ("%s got lock.", thread_name ());
  61
  62   for (i = 1; i < NESTING_DEPTH; i++)
  63     {
  64       char name[16];
  65       int thread_priority;
  66
  67       snprintf (name, sizeof name, "thread %d", i);
  68       thread_priority = PRI_MIN + i * 3;
  69       lock_pairs[i].first = i < NESTING_DEPTH - 1 ? locks + i: NULL;
  70       lock_pairs[i].second = locks + i - 1;
  71
  72       thread_create (name, thread_priority, donor_thread_func, lock_pairs + i);
  73       msg ("%s should have priority %d.  Actual priority: %d.",
  74           thread_name (), thread_priority, thread_get_priority ());
  75
  76       snprintf (name, sizeof name, "interloper %d", i);
  77       thread_create (name, thread_priority - 1, interloper_thread_func, NULL);
  78     }
  79
  80   lock_release (&locks[0]);
  81   msg ("%s finishing with priority %d.", thread_name (),
  82                                          thread_get_priority ());
  83 }
  84
  85 static void
  86 donor_thread_func (void *locks_)
  87 {
  88   struct lock_pair *locks = locks_;
  89
  90   if (locks->first)
  91     lock_acquire (locks->first);
  92
  93   lock_acquire (locks->second);
  94   msg ("%s got lock", thread_name ());
  95
  96   lock_release (locks->second);
  97   msg ("%s should have priority %d. Actual priority: %d",
  98         thread_name (), (NESTING_DEPTH - 1) * 3,
  99         thread_get_priority ());
 100
 101   if (locks->first)
 102     lock_release (locks->first);
 103
 104   msg ("%s finishing with priority %d.", thread_name (),
 105                                          thread_get_priority ());
 106 }
 107
 108 static void
 109 interloper_thread_func (void *arg_ UNUSED)
 110 {
 111   msg ("%s finished.", thread_name ());
 112 }
 113
 114 // vim: sw=2