This is the archived Fall 2013 version of the course.
For the most recent version, see

Class 11: Smarter Scheduling

(Sorry, my laptop malfunctioned today, so there are no scribbles on the slides which may not fully make sense without them.)

Action Items

For your PS2 demo, your team should be ready with your shell running on one of your laptops at the appointed demo time. If there is another team scheduled after you and you wasted time by not having things ready to go at your appointed start time, we will cut your demo short so the next team does not need to wait. If your demo is scheduled with Dave, you should come to my office, Rice 507. Thursday and Friday morning demos with Weilin will be held in Rice 514. Friday afternoon demos with Purnam will be in Rice 204.

Start making contributions to the Norvig Numbers. You should claim the number you want to work on by posting in the forum, but your contribution should be a link to a github repository containing your code and a README file that explains why the number is important and how your code estimates it. Everyone should have made some meaningful contribution to this by the end of Thanksgiving break, but if you use a sensible scheduling algorithm you will do it sooner!

The midterm exam will be posted on Thursday, 10 October and due on Monday, 14 October. It will be open resources (except for other humans) and untimed. You should not be surprised if questions from the notes appear on the midterm. It is fine (and encouraged!) to discuss those questions in the course forum before the midterm is posted (but not during the midterm).

Revised Course Schedule

PS3 (zhtta) will be due by 8:59pm on Monday, 28 October (not 10 October as originally scheduled).

There is no PS4. After PS3, you will work on an open ended project due the last day of class (5 December). Note: if you already have a great idea for a project that will be more worthwhile for you than PS3, you can make a case for doing that instead of PS3 also.

Peter Norvig's Numbers Every Programmer Should Know

Original essay: Teach Yourself Programming in Ten Years (from 2001)

So it may be that 10,000 hours, not 10 years, is the magic number. (Henri Cartier-Bresson (1908-2004) said "Your first 10,000 photographs are your worst," but he shot more than one an hour.) Samuel Johnson (1709-1784) thought it took even longer: "Excellence in any department can be attained only by the labor of a lifetime; it is not to be purchased at a lesser price." And Chaucer (1340-1400) complained "the lyf so short, the craft so long to lerne." Hippocrates (c. 400BC) is known for the excerpt "ars longa, vita brevis", which is part of the longer quotation "Ars longa, vita brevis, occasio praeceps, experimentum periculosum, iudicium difficile", which in English renders as "Life is short, [the] craft long, opportunity fleeting, experiment treacherous, judgment difficult." Although in Latin, ars can mean either art or craft, in the original Greek the word "techne" can only mean "skill", not "art".

Approximate timing for various operations on a typical PC:

Operation Time
execute typical instruction 1/1,000,000,000 sec = 1 ns
fetch from L1 cache memory 0.5 ns
branch misprediction 5 ns
fetch from L2 cache memory 7 ns
Mutex lock/unlock 25 ns
fetch from main memory 100 ns
send 2K bytes over 1Gbps network 20,000 ns
read 1MB sequentially from memory 250,000 ns
fetch from new disk location (seek) 8,000,000 ns
read 1MB sequentially from disk 20,000,000 ns
send packet US to Europe and back 150 ms = 150,000,000 ns

To make a continually updated and useful list:

  • Define and justify a number that you think it is important for programmers to know.
  • Write a program that can estimate that number (e.g., Wil's Kernel Timer Interval program)

You may work alone, or in teams as large as you want (so long as the value of what you do scales with at least the square root of the team size). To avoid duplication and encourage sharing, post in the Piazza forum thread the number you want to work on.

Premptive 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.)

Number one will be your dissertation. Almost everyone hates their dissertation by the time they're done with it. The process inherently tends to produce an unpleasant result, like a cake made out of whole wheat flour and baked for twelve hours. Few dissertations are read with pleasure, especially by their authors. But thousands before you have suffered through writing a dissertation. And aside from that, grad school is close to paradise. Many people remember it as the happiest time of their lives. And nearly all the rest, including me, remember it as a period that would have been, if they hadn't had to write a dissertation.

Paul Graham, Undergraduation.

Stride Scheduling

What are the advantages of stride scheduling over lottery scheduling?

Linux Scheduler

What were the problems with the Linux O(N) scheduler?

What were the problems with the Linux O(1) scheduler?

Inside the Linux 2.6 Completely Fair Scheduler: Providing fair access to CPUs since 2.6.23
CFS Scheduler Design and Announcement