YouTube placeholder

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.

The Know Nothings

random
random 1
random 2
random 3
random 4
random 5
random 6
random 7
random 8
random 9
random 10
random 11
random 12
random 13
random 14
random 15
random 16
random 17
random 18
random 19
random 20
random 21
random 22

Random Scheduling

  • 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?
  • Just return it to the ready pile!

Round-Robin Scheduling

  • 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 Know Nothings

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

The Know-It-Alls

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

  • How long is it going to use the CPU!

  • Will it block or yield?

  • How long will it wait?

sjf 1
sjf 2
sjf 3
sjf 4
sjf 5
sjf 6
sjf 7
sjf 8
sjf 9
sjf 10
sjf 11

Shortest-Job First

Why would we use this algorithm?
  • Minimizes waiting time!

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.

The Know-It-Alls

waiting 1
waiting 2
waiting 3
waiting 4
waiting 5
waiting 6
waiting 7
waiting 8
waiting 9
waiting 10
waiting 11
waiting 12
waiting 13
waiting 14
waiting 15
waiting 16
waiting 17
waiting 18
waiting 18
waiting 19

Oracular Spectacular

Normally we cannot predict the future
  • Control flow is unpredictable.

  • Users are unpredictable.

Instead, use the past to predict the future.
  • What did the thread do recently? It will probably keep doing that.

Multi-Level Feedback Queues

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

mlfq 1
mlfq 2
mlfq 3
mlfq 4
mlfq 5
mlfq 6
mlfq 7
mlfq 8
mlfq 9
mlfq 10
mlfq 11
mlfq 12
mlfq 13
mlfq 14
mlfq 15
mlfq 16

Created 3/1/2017
Updated 9/18/2020
Commit 4eceaab // History // View
Built 2/28/2017 @ 19:00 EDT