Outline:

1. Recap so far
   
2. Classifying scheduling algorithms
   
3. Allowing arbitrary arrivals: EDF
   
   • Problem statement
   • Algorithm
   • Proof of optimality
   • Guarantee test
4. Notes on assignments

Reading assignment (to be completed by the next class):

• Buttazzo section 2.3.1 (pp. 35-39)
• Buttazzo section 3.3 (pp. 58-64)

Corrections in book:

• p. 59, paragraph after Theorem 3.2:
  • With a list, it is O(n) per task; with a heap, it is only O(log n) per task.
• p. 63, equations:
  • There should be a preceding both summations.
• p. 63, after (3.2), and p. 64, Fig. 3.7:
  • The initial value of should be , not 0.