Simple Schedulers

Scheduling Information

Today we will talk about schedulers that use three kinds of additional information in order to choose what thread to run next:

What will happen next? Oracular schedulers can cannot be implemented but can be a good point of comparison.
What just happened? Typical schedulers—and many other operating system algorithms—use the past to predict the future.
What does the user want? Schedulers usually have ways to incorporate user input.

Choose a scheduling quantum. This is the maximum amount of time any thread will be able to run at one time.
Then:
1. Choose a thread a random from the ready pile.
2. Run the thread until it it blocks or the scheduling quantum expires.

What happens when a thread leaves the waiting state?

Choose a scheduling quantum. This is the maximum amount of time any thread will be able to run at one time.
Establish an ordered ready queue. For example, when a thread is created add it to the tail of the ready queue.
Then:
1. Choose the thread at the head of the ready queue.
2. Run the thread until it it blocks or the scheduling quantum expires.
3. If its scheduling quantum expires, place it at the tail of the ready queue.
What happens when a thread leaves the waiting state?
- Could put it at the head of the ready queue, or at the tail.

The random and round robin scheduling algorithms:
- require no information about a threads past, present, or future, and
- accept no user input.
These are rarely useful algorithms except as straw men to compare other approaches to.
Both penalize—or at least do not reward—threads that give up the CPU before their quantums expire.
As one exception, round robin scheduling is sometimes used once other scheduling decisions have been made and a set of threads are considered equivalent.
- As an example, you might rotate round-robin though a set of threads with the same priority.

Let’s say we can predict the future. What might we like to know about the thread we are about to execute?

Why would we use this algorithm?

More generally, why would we prefer threads that give up the CPU before their time quantum ends?

They are probably waiting for something else, which can be done in parallel with CPU use.

Normally we cannot predict the future

Instead, use the past to predict the future.

Choose a scheduling quantum. This is the maximum amount of time any thread will be able to run at one time.
Establish some number of queues; each represents a level.
Threads from the highest-level queues are chosen first.
Then:
1. Choose and run a thread from the highest-level non-empty queue.
2. If the thread blocks or yields, promote it to a higher level queue.
3. If the thread must be preempted at the end of a quantum, demote it to a lower level queue.