Invert the priority scheme, so that PRI_MIN is now the lowest priority
authorBen Pfaff <blp@cs.stanford.edu>
Mon, 10 Apr 2006 00:28:22 +0000 (00:28 +0000)
committerBen Pfaff <blp@cs.stanford.edu>
Mon, 10 Apr 2006 00:28:22 +0000 (00:28 +0000)
and PRI_MAX is now the highest priority.  This should reduce student
confusion (and at the same time subtly frustrate attempts to resubmit
work from previous quarters).

20 files changed:
doc/44bsd.texi
doc/threads.texi
doc/tour.texi
src/tests/threads/alarm-priority.c
src/tests/threads/alarm-priority.ck
src/tests/threads/priority-change.c
src/tests/threads/priority-condvar.c
src/tests/threads/priority-condvar.ck
src/tests/threads/priority-donate-multiple.c
src/tests/threads/priority-donate-multiple.ck
src/tests/threads/priority-donate-nest.c
src/tests/threads/priority-donate-nest.ck
src/tests/threads/priority-donate-one.c
src/tests/threads/priority-donate-one.ck
src/tests/threads/priority-fifo.c
src/tests/threads/priority-preempt.c
src/tests/threads/priority-sema.c
src/tests/threads/priority-sema.ck
src/threads/thread.c
src/threads/thread.h

index 208dcd47cfccc100854419f58878eb33ffe42d41..e44232662334d4c4db3941802a99b6280a41cba5 100644 (file)
@@ -104,13 +104,13 @@ highest priority, yields.
 
 Our scheduler has 64 priorities and thus 64 ready queues, numbered 0
 (@code{PRI_MIN}) through 63 (@code{PRI_MAX}).  Lower numbers correspond
-to @emph{higher} priorities, so that priority 0 is the highest priority
-and priority 63 is the lowest.  Thread priority is calculated initially
+to lower priorities, so that priority 0 is the lowest priority
+and priority 63 is the highest.  Thread priority is calculated initially
 at thread initialization.  It is also recalculated once every fourth
 clock tick, for every thread.  In either case, it is determined by
 the formula
 
-@center @t{@var{priority} = (@var{recent_cpu} / 4) + (@var{nice} * 2)},
+@center @t{@var{priority} = @code{PRI_MAX} - (@var{recent_cpu} / 4) - (@var{nice} * 2)},
 
 @noindent where @var{recent_cpu} is an estimate of the CPU time the
 thread has used recently (see below) and @var{nice} is the thread's
@@ -243,9 +243,10 @@ scheduler.  It is not a complete description of scheduler requirements.
 Every thread has a @var{nice} value between -20 and 20 directly under
 its control.  Each thread also has a priority, between 0
 (@code{PRI_MIN}) through 63 (@code{PRI_MAX}), which is recalculated
-using the following formula whenever the value of either term changes:
+using the following formula whenever the value of either variable term
+changes:
 
-@center @t{@var{priority} = (@var{recent_cpu} / 4) + (@var{nice} * 2)}.
+@center @t{@var{priority} = @code{PRI_MAX} - (@var{recent_cpu} / 4) - (@var{nice} * 2)}.
 
 @var{recent_cpu} measures the amount of CPU time a thread has received
 ``recently.''  On each timer tick, the running thread's @var{recent_cpu}
index d1ff66640cd05f9d428375bf6bf0bd91958357ea..d83b52f4525770b2a89d7768713426e1ad1821b0 100644 (file)
@@ -442,8 +442,8 @@ priority such that it no longer has the highest priority must cause it
 to immediately yield the CPU.
 
 Thread priorities range from @code{PRI_MIN} (0) to @code{PRI_MAX} (63).
-Lower numbers correspond to @emph{higher} priorities, so that priority 0
-is the highest priority and priority 63 is the lowest.
+Lower numbers correspond to lower priorities, so that priority 0
+is the lowest priority and priority 63 is the highest.
 The initial thread priority is passed as an argument to
 @func{thread_create}.  If there's no reason to choose another
 priority, use @code{PRI_DEFAULT} (31).  The @code{PRI_} macros are
@@ -685,8 +685,8 @@ If multiple threads have the same highest priority,
 
 Priority donation only changes the priority of the donee
 thread.  The donor thread's priority is unchanged.  
-Priority donation is not additive: if thread @var{A} (with priority 3) donates
-to thread @var{B} (with priority 5), then @var{B}'s new priority is 3, not 8.
+Priority donation is not additive: if thread @var{A} (with priority 5) donates
+to thread @var{B} (with priority 3), then @var{B}'s new priority is 5, not 8.
 
 @item Can a thread's priority change while it is on the ready queue?
 
index c1371cfde5760df3df4129a4f5eec6b0c4d3e66e..2e15b38ff525b1b15c8e2246a64d8eaa98f27850 100644 (file)
@@ -327,8 +327,8 @@ the page.  @xref{Interrupt Handling}, for more information.
 
 @deftypecv {Member} {@struct{thread}} {int} priority
 A thread priority, ranging from @code{PRI_MIN} (0) to @code{PRI_MAX}
-(63).  Lower numbers correspond to @emph{higher} priorities, so that
-priority 0 is the highest priority and priority 63 is the lowest.
+(63).  Lower numbers correspond to lower priorities, so that
+priority 0 is the lowest priority and priority 63 is the highest.
 Pintos as provided ignores thread priorities, but you will implement
 priority scheduling in project 1 (@pxref{Priority Scheduling}).
 @end deftypecv
index 51ca6a92f1146c248cfc538f7fac44871919598c..4839ecdfc81491d36c656ea4ef98761cf5206616 100644 (file)
@@ -26,13 +26,13 @@ test_alarm_priority (void)
   
   for (i = 0; i < 10; i++) 
     {
-      int priority = (i + 5) % 10 + PRI_DEFAULT + 1;
+      int priority = PRI_DEFAULT - (i + 5) % 10 - 1;
       char name[16];
       snprintf (name, sizeof name, "priority %d", priority);
       thread_create (name, priority, alarm_priority_thread, NULL);
     }
 
-  thread_set_priority (PRI_MAX);
+  thread_set_priority (PRI_MIN);
 
   for (i = 0; i < 10; i++)
     sema_down (&wait_sema);
index 6fa6128f73bbda61e27398fd888851484525c0dc..c62b024944b0e16d63921b836a4f04ab3b071ef7 100644 (file)
@@ -4,15 +4,15 @@ use warnings;
 use tests::tests;
 check_expected ([<<'EOF']);
 (alarm-priority) begin
-(alarm-priority) Thread priority 32 woke up.
-(alarm-priority) Thread priority 33 woke up.
-(alarm-priority) Thread priority 34 woke up.
-(alarm-priority) Thread priority 35 woke up.
-(alarm-priority) Thread priority 36 woke up.
-(alarm-priority) Thread priority 37 woke up.
-(alarm-priority) Thread priority 38 woke up.
-(alarm-priority) Thread priority 39 woke up.
-(alarm-priority) Thread priority 40 woke up.
-(alarm-priority) Thread priority 41 woke up.
+(alarm-priority) Thread priority 30 woke up.
+(alarm-priority) Thread priority 29 woke up.
+(alarm-priority) Thread priority 28 woke up.
+(alarm-priority) Thread priority 27 woke up.
+(alarm-priority) Thread priority 26 woke up.
+(alarm-priority) Thread priority 25 woke up.
+(alarm-priority) Thread priority 24 woke up.
+(alarm-priority) Thread priority 23 woke up.
+(alarm-priority) Thread priority 22 woke up.
+(alarm-priority) Thread priority 21 woke up.
 (alarm-priority) end
 EOF
index 735920ffe49fa309b5088aa9290bf4ed4aee2b6c..bb462d462d85fe02c1a4ca22a132883ec881c0b4 100644 (file)
@@ -16,9 +16,9 @@ test_priority_change (void)
   ASSERT (!enable_mlfqs);
 
   msg ("Creating a high-priority thread 2.");
-  thread_create ("thread 2", PRI_DEFAULT - 1, changing_thread, NULL);
+  thread_create ("thread 2", PRI_DEFAULT + 1, changing_thread, NULL);
   msg ("Thread 2 should have just lowered its priority.");
-  thread_set_priority (PRI_DEFAULT + 2);
+  thread_set_priority (PRI_DEFAULT - 2);
   msg ("Thread 2 should have just exited.");
 }
 
@@ -26,6 +26,6 @@ static void
 changing_thread (void *aux UNUSED) 
 {
   msg ("Thread 2 now lowering priority.");
-  thread_set_priority (PRI_DEFAULT + 1);
+  thread_set_priority (PRI_DEFAULT - 1);
   msg ("Thread 2 exiting.");
 }
index 51008abdb71d9e61f34a8757c477fe59d7d1981a..3e31081da6a9b673c2d0a933189e46cb0205e990 100644 (file)
@@ -24,10 +24,10 @@ test_priority_condvar (void)
   lock_init (&lock);
   cond_init (&condition);
 
-  thread_set_priority (PRI_MAX);
+  thread_set_priority (PRI_MIN);
   for (i = 0; i < 10; i++) 
     {
-      int priority = (i + 7) % 10 + PRI_DEFAULT + 1;
+      int priority = PRI_DEFAULT - (i + 7) % 10 - 1;
       char name[16];
       snprintf (name, sizeof name, "priority %d", priority);
       thread_create (name, priority, priority_condvar_thread, NULL);
index d1d9038e957fbafa3db15b269a8ae4b8a8995bc2..580a019f50e5e9274ac3dc3689c7c441b6079a78 100644 (file)
@@ -4,35 +4,35 @@ use warnings;
 use tests::tests;
 check_expected ([<<'EOF']);
 (priority-condvar) begin
-(priority-condvar) Thread priority 39 starting.
-(priority-condvar) Thread priority 40 starting.
-(priority-condvar) Thread priority 41 starting.
-(priority-condvar) Thread priority 32 starting.
-(priority-condvar) Thread priority 33 starting.
-(priority-condvar) Thread priority 34 starting.
-(priority-condvar) Thread priority 35 starting.
-(priority-condvar) Thread priority 36 starting.
-(priority-condvar) Thread priority 37 starting.
-(priority-condvar) Thread priority 38 starting.
+(priority-condvar) Thread priority 23 starting.
+(priority-condvar) Thread priority 22 starting.
+(priority-condvar) Thread priority 21 starting.
+(priority-condvar) Thread priority 30 starting.
+(priority-condvar) Thread priority 29 starting.
+(priority-condvar) Thread priority 28 starting.
+(priority-condvar) Thread priority 27 starting.
+(priority-condvar) Thread priority 26 starting.
+(priority-condvar) Thread priority 25 starting.
+(priority-condvar) Thread priority 24 starting.
 (priority-condvar) Signaling...
-(priority-condvar) Thread priority 32 woke up.
+(priority-condvar) Thread priority 30 woke up.
 (priority-condvar) Signaling...
-(priority-condvar) Thread priority 33 woke up.
+(priority-condvar) Thread priority 29 woke up.
 (priority-condvar) Signaling...
-(priority-condvar) Thread priority 34 woke up.
+(priority-condvar) Thread priority 28 woke up.
 (priority-condvar) Signaling...
-(priority-condvar) Thread priority 35 woke up.
+(priority-condvar) Thread priority 27 woke up.
 (priority-condvar) Signaling...
-(priority-condvar) Thread priority 36 woke up.
+(priority-condvar) Thread priority 26 woke up.
 (priority-condvar) Signaling...
-(priority-condvar) Thread priority 37 woke up.
+(priority-condvar) Thread priority 25 woke up.
 (priority-condvar) Signaling...
-(priority-condvar) Thread priority 38 woke up.
+(priority-condvar) Thread priority 24 woke up.
 (priority-condvar) Signaling...
-(priority-condvar) Thread priority 39 woke up.
+(priority-condvar) Thread priority 23 woke up.
 (priority-condvar) Signaling...
-(priority-condvar) Thread priority 40 woke up.
+(priority-condvar) Thread priority 22 woke up.
 (priority-condvar) Signaling...
-(priority-condvar) Thread priority 41 woke up.
+(priority-condvar) Thread priority 21 woke up.
 (priority-condvar) end
 EOF
index 69056914306bdede6f7c53047adfdb33d3ce706f..e1bccbdb4b567baef5c1767173ff9271aeda74c9 100644 (file)
@@ -35,18 +35,18 @@ test_priority_donate_multiple (void)
   lock_acquire (&a);
   lock_acquire (&b);
 
-  thread_create ("a", PRI_DEFAULT - 1, a_thread_func, &a);
+  thread_create ("a", PRI_DEFAULT + 1, a_thread_func, &a);
   msg ("Main thread should have priority %d.  Actual priority: %d.",
-       PRI_DEFAULT - 1, thread_get_priority ());
+       PRI_DEFAULT + 1, thread_get_priority ());
 
-  thread_create ("b", PRI_DEFAULT - 2, b_thread_func, &b);
+  thread_create ("b", PRI_DEFAULT + 2, b_thread_func, &b);
   msg ("Main thread should have priority %d.  Actual priority: %d.",
-       PRI_DEFAULT - 2, thread_get_priority ());
+       PRI_DEFAULT + 2, thread_get_priority ());
 
   lock_release (&b);
   msg ("Thread b should have just finished.");
   msg ("Main thread should have priority %d.  Actual priority: %d.",
-       PRI_DEFAULT - 1, thread_get_priority ());
+       PRI_DEFAULT + 1, thread_get_priority ());
 
   lock_release (&a);
   msg ("Thread a should have just finished.");
index 9118722cbbd82ecd73b5d718278e76ec32535c20..d84a0ee5144ae67e11e8efc180eb2b9ee190e617 100644 (file)
@@ -4,12 +4,12 @@ use warnings;
 use tests::tests;
 check_expected ([<<'EOF']);
 (priority-donate-multiple) begin
-(priority-donate-multiple) Main thread should have priority 30.  Actual priority: 30.
-(priority-donate-multiple) Main thread should have priority 29.  Actual priority: 29.
+(priority-donate-multiple) Main thread should have priority 32.  Actual priority: 32.
+(priority-donate-multiple) Main thread should have priority 33.  Actual priority: 33.
 (priority-donate-multiple) Thread b acquired lock b.
 (priority-donate-multiple) Thread b finished.
 (priority-donate-multiple) Thread b should have just finished.
-(priority-donate-multiple) Main thread should have priority 30.  Actual priority: 30.
+(priority-donate-multiple) Main thread should have priority 32.  Actual priority: 32.
 (priority-donate-multiple) Thread a acquired lock a.
 (priority-donate-multiple) Thread a finished.
 (priority-donate-multiple) Thread a should have just finished.
index 1f245847698c3bc8254fe7d3726b9ff8530970a5..71cf8a9186db979a14ae224ccd809cf2f21754bf 100644 (file)
@@ -43,15 +43,15 @@ test_priority_donate_nest (void)
 
   locks.a = &a;
   locks.b = &b;
-  thread_create ("medium", PRI_DEFAULT - 1, medium_thread_func, &locks);
+  thread_create ("medium", PRI_DEFAULT + 1, medium_thread_func, &locks);
   thread_yield ();
   msg ("Low thread should have priority %d.  Actual priority: %d.",
-       PRI_DEFAULT - 1, thread_get_priority ());
+       PRI_DEFAULT + 1, thread_get_priority ());
 
-  thread_create ("high", PRI_DEFAULT - 2, high_thread_func, &b);
+  thread_create ("high", PRI_DEFAULT + 2, high_thread_func, &b);
   thread_yield ();
   msg ("Low thread should have priority %d.  Actual priority: %d.",
-       PRI_DEFAULT - 2, thread_get_priority ());
+       PRI_DEFAULT + 2, thread_get_priority ());
 
   lock_release (&a);
   thread_yield ();
@@ -69,7 +69,7 @@ medium_thread_func (void *locks_)
   lock_acquire (locks->a);
 
   msg ("Medium thread should have priority %d.  Actual priority: %d.",
-       PRI_DEFAULT - 2, thread_get_priority ());
+       PRI_DEFAULT + 2, thread_get_priority ());
   msg ("Medium thread got the lock.");
 
   lock_release (locks->a);
index 597d99dfda052461c34f7ce9cd24b42897f57865..6ec1b4aca3a6d4a415ac156c6ae9ace619039de4 100644 (file)
@@ -4,9 +4,9 @@ use warnings;
 use tests::tests;
 check_expected ([<<'EOF']);
 (priority-donate-nest) begin
-(priority-donate-nest) Low thread should have priority 30.  Actual priority: 30.
-(priority-donate-nest) Low thread should have priority 29.  Actual priority: 29.
-(priority-donate-nest) Medium thread should have priority 29.  Actual priority: 29.
+(priority-donate-nest) Low thread should have priority 32.  Actual priority: 32.
+(priority-donate-nest) Low thread should have priority 33.  Actual priority: 33.
+(priority-donate-nest) Medium thread should have priority 33.  Actual priority: 33.
 (priority-donate-nest) Medium thread got the lock.
 (priority-donate-nest) High thread got the lock.
 (priority-donate-nest) High thread finished.
index 603a7fe45a9b3469133f21aef75041d596a2981a..2a67b52e0960f99bbfba53ba757f8c2967b17cb4 100644 (file)
@@ -31,12 +31,12 @@ test_priority_donate_one (void)
 
   lock_init (&lock);
   lock_acquire (&lock);
-  thread_create ("acquire1", PRI_DEFAULT - 1, acquire1_thread_func, &lock);
+  thread_create ("acquire1", PRI_DEFAULT + 1, acquire1_thread_func, &lock);
   msg ("This thread should have priority %d.  Actual priority: %d.",
-       PRI_DEFAULT - 1, thread_get_priority ());
-  thread_create ("acquire2", PRI_DEFAULT - 2, acquire2_thread_func, &lock);
+       PRI_DEFAULT + 1, thread_get_priority ());
+  thread_create ("acquire2", PRI_DEFAULT + 2, acquire2_thread_func, &lock);
   msg ("This thread should have priority %d.  Actual priority: %d.",
-       PRI_DEFAULT - 2, thread_get_priority ());
+       PRI_DEFAULT + 2, thread_get_priority ());
   lock_release (&lock);
   msg ("acquire2, acquire1 must already have finished, in that order.");
   msg ("This should be the last line before finishing this test.");
index ff019a23ee05f7ce38ac5da4056676384c335cab..c09ecfd8830103931d3915fa6e28b3a802ef1028 100644 (file)
@@ -4,8 +4,8 @@ use warnings;
 use tests::tests;
 check_expected ([<<'EOF']);
 (priority-donate-one) begin
-(priority-donate-one) This thread should have priority 30.  Actual priority: 30.
-(priority-donate-one) This thread should have priority 29.  Actual priority: 29.
+(priority-donate-one) This thread should have priority 32.  Actual priority: 32.
+(priority-donate-one) This thread should have priority 33.  Actual priority: 33.
 (priority-donate-one) acquire2: got the lock
 (priority-donate-one) acquire2: done
 (priority-donate-one) acquire1: got the lock
index e71b7e5e00d07b14b982a5788df149b2be5ed69d..2f891962ad4e0a796bdc1851da970c27c93af7dd 100644 (file)
@@ -50,7 +50,7 @@ test_priority_fifo (void)
   ASSERT (output != NULL);
   lock_init (&lock);
 
-  thread_set_priority (PRI_DEFAULT - 2);
+  thread_set_priority (PRI_DEFAULT + 2);
   for (i = 0; i < THREAD_CNT; i++) 
     {
       char name[16];
@@ -60,7 +60,7 @@ test_priority_fifo (void)
       d->iterations = 0;
       d->lock = &lock;
       d->op = &op;
-      thread_create (name, PRI_DEFAULT - 1, simple_thread_func, d);
+      thread_create (name, PRI_DEFAULT + 1, simple_thread_func, d);
     }
 
   thread_set_priority (PRI_DEFAULT);
index 452c6807c25c524d2d1d4de02b29b622baaac4b9..70f8acbee8ee67bd14349f73106a10dfbb031565 100644 (file)
@@ -23,7 +23,7 @@ test_priority_preempt (void)
   /* Make sure our priority is the default. */
   ASSERT (thread_get_priority () == PRI_DEFAULT);
 
-  thread_create ("high-priority", PRI_DEFAULT - 1, simple_thread_func, NULL);
+  thread_create ("high-priority", PRI_DEFAULT + 1, simple_thread_func, NULL);
   msg ("The high-priority thread should have already completed.");
 }
 
index 8ca17a0aa9c3991f0b7b14b38e4b9f60051067e7..d7eb9cc076cfbaf26f9a174ff1503dcdb24d6d1a 100644 (file)
@@ -21,10 +21,10 @@ test_priority_sema (void)
   ASSERT (!enable_mlfqs);
 
   sema_init (&sema, 0);
-  thread_set_priority (PRI_MAX);
+  thread_set_priority (PRI_MIN);
   for (i = 0; i < 10; i++) 
     {
-      int priority = (i + 3) % 10 + PRI_DEFAULT + 1;
+      int priority = PRI_DEFAULT - (i + 3) % 10 - 1;
       char name[16];
       snprintf (name, sizeof name, "priority %d", priority);
       thread_create (name, priority, priority_sema_thread, NULL);
index eee1de6c81645fdfc26292fe2eb0147691c827cc..f2b9cde9203c779a3468d268a16bcea72379f4c8 100644 (file)
@@ -4,25 +4,25 @@ use warnings;
 use tests::tests;
 check_expected ([<<'EOF']);
 (priority-sema) begin
-(priority-sema) Thread priority 32 woke up.
+(priority-sema) Thread priority 30 woke up.
 (priority-sema) Back in main thread.
-(priority-sema) Thread priority 33 woke up.
+(priority-sema) Thread priority 29 woke up.
 (priority-sema) Back in main thread.
-(priority-sema) Thread priority 34 woke up.
+(priority-sema) Thread priority 28 woke up.
 (priority-sema) Back in main thread.
-(priority-sema) Thread priority 35 woke up.
+(priority-sema) Thread priority 27 woke up.
 (priority-sema) Back in main thread.
-(priority-sema) Thread priority 36 woke up.
+(priority-sema) Thread priority 26 woke up.
 (priority-sema) Back in main thread.
-(priority-sema) Thread priority 37 woke up.
+(priority-sema) Thread priority 25 woke up.
 (priority-sema) Back in main thread.
-(priority-sema) Thread priority 38 woke up.
+(priority-sema) Thread priority 24 woke up.
 (priority-sema) Back in main thread.
-(priority-sema) Thread priority 39 woke up.
+(priority-sema) Thread priority 23 woke up.
 (priority-sema) Back in main thread.
-(priority-sema) Thread priority 40 woke up.
+(priority-sema) Thread priority 22 woke up.
 (priority-sema) Back in main thread.
-(priority-sema) Thread priority 41 woke up.
+(priority-sema) Thread priority 21 woke up.
 (priority-sema) Back in main thread.
 (priority-sema) end
 EOF
index 16b8c8b692e8664b81bab789eb3eeb946e38f3b7..ca8a8b07e3fa54769d2068e482a2cb019c2ef563 100644 (file)
@@ -92,7 +92,7 @@ thread_init (void)
 void
 thread_start (void) 
 {
-  thread_create ("idle", PRI_MAX, idle, NULL);
+  thread_create ("idle", PRI_MIN, idle, NULL);
   intr_enable ();
 }
 
index 2043d8dc86e251bbd8c0492aaabc8266e935c3b9..fbef34b4673720b2f62bf3a80d1e08eadb441aa3 100644 (file)
@@ -20,9 +20,9 @@ typedef int tid_t;
 #define TID_ERROR ((tid_t) -1)          /* Error value for tid_t. */
 
 /* Thread priorities. */
-#define PRI_MIN 0                       /* Highest priority. */
+#define PRI_MIN 0                       /* Lowest priority. */
 #define PRI_DEFAULT 31                  /* Default priority. */
-#define PRI_MAX 63                      /* Lowest priority. */
+#define PRI_MAX 63                      /* Highest priority. */
 
 /* A kernel thread or user process.