Class LotteryScheduler

  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
          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


public LotteryScheduler()
Allocate a new lottery scheduler.

Method Detail


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

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