nachos.threads
Class PriorityScheduler

java.lang.Object
  extended by nachos.threads.Scheduler
      extended by nachos.threads.PriorityScheduler
Direct Known Subclasses:
LotteryScheduler

public class PriorityScheduler
extends Scheduler

A scheduler that chooses threads based on their priorities.

A priority scheduler associates a priority with each thread. The next thread to be dequeued is always a thread with priority no less than any other waiting thread's priority. Like a round-robin scheduler, the thread that is dequeued is, among all the threads of the same (highest) priority, the thread that has been waiting longest.

Essentially, a priority scheduler gives access in a round-robin fassion to all the highest-priority threads, and ignores all other threads. This has the potential to starve a thread if there's always a thread waiting with higher priority.

A priority scheduler must partially solve the priority inversion problem; in particular, priority must be donated through locks, and through joins.


Nested Class Summary
protected  class PriorityScheduler.PriorityQueue
          A ThreadQueue that sorts threads by priority.
protected  class PriorityScheduler.ThreadState
          The scheduling state of a thread.
 
Field Summary
static int priorityDefault
          The default priority for a new thread.
static int priorityMaximum
          The maximum priority that a thread can have.
static int priorityMinimum
          The minimum priority that a thread can have.
 
Constructor Summary
PriorityScheduler()
          Allocate a new priority scheduler.
 
Method Summary
 boolean decreasePriority()
          If possible, lower the priority of the current thread user in some scheduler-dependent way, preferably by the same amount as would a call to increasePriority().
 int getEffectivePriority(KThread thread)
          Get the effective priority of the specified thread.
 int getPriority(KThread thread)
          Get the priority of the specified thread.
protected  PriorityScheduler.ThreadState getThreadState(KThread thread)
          Return the scheduling state of the specified thread.
 boolean increasePriority()
          If possible, raise the priority of the current thread in some scheduler-dependent way.
 ThreadQueue newThreadQueue(boolean transferPriority)
          Allocate a new priority thread queue.
 void setPriority(KThread thread, int priority)
          Set the priority of the specified thread.
 
Methods inherited from class nachos.threads.Scheduler
getEffectivePriority, getPriority, setPriority
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

priorityDefault

public static final int priorityDefault
The default priority for a new thread. Do not change this value.

See Also:
Constant Field Values

priorityMinimum

public static final int priorityMinimum
The minimum priority that a thread can have. Do not change this value.

See Also:
Constant Field Values

priorityMaximum

public static final int priorityMaximum
The maximum priority that a thread can have. Do not change this value.

See Also:
Constant Field Values
Constructor Detail

PriorityScheduler

public PriorityScheduler()
Allocate a new priority scheduler.

Method Detail

newThreadQueue

public ThreadQueue newThreadQueue(boolean transferPriority)
Allocate a new priority thread queue.

Specified by:
newThreadQueue in class Scheduler
Parameters:
transferPriority - true if this queue should transfer priority from waiting threads to the owning thread.
Returns:
a new priority thread queue.

getPriority

public int getPriority(KThread thread)
Description copied from class: Scheduler
Get the priority of the specified thread. Must be called with interrupts disabled.

Overrides:
getPriority in class Scheduler
Parameters:
thread - the thread to get the priority of.
Returns:
the thread's priority.

getEffectivePriority

public int getEffectivePriority(KThread thread)
Description copied from class: Scheduler
Get the effective priority of the specified thread. Must be called with interrupts disabled.

The effective priority of a thread is the priority of a thread after taking into account priority donations.

For a priority scheduler, this is the maximum of the thread's priority and the priorities of all other threads waiting for the thread through a lock or a join.

For a lottery scheduler, this is the sum of the thread's tickets and the tickets of all other threads waiting for the thread through a lock or a join.

Overrides:
getEffectivePriority in class Scheduler
Parameters:
thread - the thread to get the effective priority of.
Returns:
the thread's effective priority.

setPriority

public void setPriority(KThread thread,
                        int priority)
Description copied from class: Scheduler
Set the priority of the specified thread. Must be called with interrupts disabled.

Overrides:
setPriority in class Scheduler
Parameters:
thread - the thread to set the priority of.
priority - the new priority.

increasePriority

public boolean increasePriority()
Description copied from class: Scheduler
If possible, raise the priority of the current thread in some scheduler-dependent way.

Overrides:
increasePriority in class Scheduler
Returns:
true if the scheduler was able to increase the current thread's priority.

decreasePriority

public boolean decreasePriority()
Description copied from class: Scheduler
If possible, lower the priority of the current thread user in some scheduler-dependent way, preferably by the same amount as would a call to increasePriority().

Overrides:
decreasePriority in class Scheduler
Returns:
true if the scheduler was able to decrease the current thread's priority.

getThreadState

protected PriorityScheduler.ThreadState getThreadState(KThread thread)
Return the scheduling state of the specified thread.

Parameters:
thread - the thread whose scheduling state to return.
Returns:
the scheduling state of the specified thread.