1. Multi-Level Feedback Queue
-
Try to minimize response time and turnaround time
Priority based on observed behavior (history)
Round-robin for equal priorities
2. Long-Running Jobs
3. I/O vs. CPU-intensive Workloads
4. Priority Boost
-
Avoid starvation
5. Gaming Tolerance
6. Non-Uniform Time Slices
7. Summary
-
MLFQ Rules:
- If Priority(A) > Priority(B), A runs (B doesn't).
- If Priority(A) = Priority(B), A & B run in round-robin fashion using the time slice (quantum length) of the given queue.
- When a job enters the system, it is placed at the highest priority (the topmost queue).
- Once a job uses up its time allotment at a given level (regardless of how many times it has given up the CPU), its priority is reduced (i.e., it moves down one queue).
- After some time period S, move all the jobs in the system to the topmost queue.
Other Scheduling Policies: (skip)
-
Chapter 9: fair-share, lottery scheduling (random), stride scheduling (deterministic)
Chapter 10: multiprocessor scheduling
8. Exercises
-
Exercises from the book using mlfq.py:
1. Run a few randomly-generated problems with just two jobs and two queues; compute the MLFQ execution trace for each. Make your life easier by limiting the length of each job and turning off I/Os.
2. How would you run the scheduler to reproduce each of the examples in the chapter?
3. How would you configure the scheduler parameters to behave just like a round-robin scheduler?