Class 11: Smarter Scheduling

Posted: Thu 27 February 2014

Problem Set 3 is due by 11:59pm on Wednesday, 5 March (note this is a two-day extension from the original due date). You should have definitely at least finished Problem 5 by today.

Exam 2 has been postponed until after Spring Break (schedule to be announced later). If you follow a hard real-time scheduling policy, though, you can elect to do the exam according to the original schedule. If you want to do this, let me know by Friday (28 Feb).


Videos

Readings

The OSTEP book covers scheduling in these sections:

These provide a lot more detail on several of the scheduling policies we discuss in class, as well as several policies we didn't cover in class. You are not expected to know details of other scheduling policies beyond what we discuss in class and what you explore in PS3, but you should find these sections well worth reading.

The Shortest Job First and Shortest Time-to-Completion First policies described in Section 7 are similar to the SRPT policy you are implementing for PS3 Problem 5 (you should consider which one of these is closer to what you should do for PS3).

Scheduling Recap

When is planned scheduling used?

What is a hard real-time system?

Scheduling Strategies

First Come, First Served (FIFO): processes run to completion, in the order they are started.

Round-Robin: each process gets to run for a given time slice (or until it finishes or is blocked).

What are the advantages and disadvantages of Round-Robin scheduling compred to First Come, First Served?

Exploring Processes and Priorities

What does the priority of a process mean?

Try this: ps -w -e -o pri,pid,pcpu,vsz,cputime,command | sort -n -r --key=5 | sort --stable -n --key=1

Preemptive Priority Scheduling

  • Always run the highest priority process that is ready to run
  • Round-robin schedule among equally high, ready to run, highest-priority processes

What are the advantages and disadvantages of preemptive priority scheduling?

What really happened on Mars? Glen Reeve's account

Is priority inheritance a good solution?

Lottery Scheduling

Carl Waldspurger's PhD dissertation: Lottery and Stride Scheduling: Flexible Proportional-Share Resource Management (If you are considering going to grad school and want a good model of what a PhD involves, this is the best example I know of a dissertation worth reading.)

Stride Scheduling

What are the advantages of stride scheduling over lottery scheduling?

comments powered by Disqus