nachos.threads
Class LotteryScheduler
java.lang.Object
nachos.threads.Scheduler
nachos.threads.PriorityScheduler
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).
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
LotteryScheduler
public LotteryScheduler()
- Allocate a new lottery scheduler.
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.