CS 332 s20 — Uniprocessor Scheduling

Please watch the video lecture: It contains sections on

1. Introduction (0:04)
2. Overview (1:14)
3. Definitions (2:22)
4. Performance Metrics (7:29)
5. Policy: First In First Out (FIFO) (10:01)
6. Policy: Shortest Job First (SJF) (11:18)
7. FIFO vs SJF (12:55)
8. Is SJF Optimal? (13:49)
9. Is FIFO ever optimal? (19:31)
10. Policy: (Pre-emptive) Round Robin (23:08)
11. Round Robin on Equal-Length Tasks (25:25)
12. Round Robin on Mix of I/O and Compute Tasks (26:48)
13. Max-Min Fairness (28:12)
14. Multi-Level Feedback Queue (MFQ) (32:09)
15. Multiple Round Robin Queues (34:07)
16. MFQ With Four Levels (35:29)
17. Summary (38:00)
18. Reading: The Multi-Level Feedback Queue (40:07)
19. Annoucements (40:42)

The Panopto viewer has table of contents entries for each slide (https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=d151ff0c-5cc5-4c88-9d3a-abba011abfeb). You can access the lecture slides here.

Read OSTEP chapter 8, (p. 85–94) on the multi-level feedback queues. It develops this classic scheduling technique in more detail.

1. Provide your classmates with peer review feedback by Friday.
2. Quiz due tonight at 9pm.
3. Work through the homework questions in OSTEP chapter 8 to play with a simulated MFQ scheduler. Download the code here: http://pages.cs.wisc.edu/~remzi/OSTEP/Homework/HW-MLFQ.tgz