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.