Outline:

1. EDF (cont’d)
   • Recap
   • Proof of optimality
   • Guarantee test
2. Handling Non-Preemptivity
   • Scheduling via a search tree
   • Bratley’s Algorithm – bounding branches
   • Spring Algorithm – following a heuristic
3. Classifying scheduling algorithms, revisited

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

• Buttazzo section 3.4 (pp. 63-70)

Corrections in book (section 3.3 – EDF):

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