nachos.threads
Class LotteryScheduler

java.lang.Object
  extended by nachos.threads.Scheduler
      extended by nachos.threads.PriorityScheduler
          extended by nachos.threads.LotteryScheduler

public class LotteryScheduler
extends PriorityScheduler

A scheduler that chooses threads using a lottery.

A lottery scheduler associates a number of tickets with each thread. When a thread needs to be dequeued, a random lottery is held, among all the tickets of all the threads waiting to be dequeued. The thread that holds the winning ticket is chosen.

Note that a lottery scheduler must be able to handle a lot of tickets (sometimes billions), so it is not acceptable to maintain state for every ticket.

A lottery scheduler must partially solve the priority inversion problem; in particular, tickets must be transferred through locks, and through joins. Unlike a priority scheduler, these tickets add (as opposed to just taking the maximum).


Nested Class Summary
 
Nested classes/interfaces inherited from class nachos.threads.PriorityScheduler
PriorityScheduler.PriorityQueue, PriorityScheduler.ThreadState
 
Field Summary
 
Fields inherited from class nachos.threads.PriorityScheduler
priorityDefault, priorityMaximum, priorityMinimum
 
Constructor Summary
LotteryScheduler()
          Allocate a new lottery scheduler.
 
Method Summary
 ThreadQueue newThreadQueue(boolean transferPriority)
          Allocate a new lottery thread queue.
 
Methods inherited from class nachos.threads.PriorityScheduler
decreasePriority, getEffectivePriority, getPriority, getThreadState, increasePriority, setPriority
 
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
 

Constructor Detail

LotteryScheduler

public LotteryScheduler()
Allocate a new lottery scheduler.

Method Detail

newThreadQueue

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

Overrides:
newThreadQueue in class PriorityScheduler
Parameters:
transferPriority - true if this queue should transfer tickets from waiting threads to the owning thread.
Returns:
a new lottery thread queue.