Midterm

• Date: October 10th, 2019
• What does it cover?
• Everything up to (including) CPU Scheduling
• Assignment 1
• What types of questions?
• Very similar to the quizzes
• More reading code
• Review: October 8, 2019

1

Introduction to CPU Scheduling Part 2

2

• Each job (process/thread) runs the same amount of time.
• All jobs arrive at the same time.
• Once started, each job runs to completion (no interruption in the middle).
• All jobs only use the CPU (no I/O).
• The run time of each job is known.

The worst assumption:

• Most likely never happen in real life
• Yet, without it, SJF/STCF becomes invalid

​

3

The Question

​

​

How do we schedule jobs without knowing their run time duration so that we can minimize turnaround time and also minimize response time for interactive jobs?

4

Multilevel Feedback Queue (MLFQ)

• Fernando José Corbató (1926 - )
• Ph.D. in Physics (Cal Tech),
• Professor of MIT
• One of the developers of Multics (Predecessor of UNIX)
• First use of password to secure file access on computers
• Recipient of the Turing Award in 1990 (the Nobel prize of computing)

5

Multilevel Feedback Queue (MLFQ)

​

• Learn from the past to predict the future.
• Common in Operating Systems design. Other examples include hardware branch predictors and caching algorithms.
• Works when jobs have phases of behavior and are predictable.
• Assumption: Two categories of jobs
• Long-running CPU-bound jobs
• Interactive I/O-bound jobs

​

6

Multilevel Feedback Queue (MLFQ)

​

• Consists of a number of distinct queues, each assigned a different priority level.
• Each queue has multiple ready-to-run jobs with the same priority.
• At any given time, the scheduler choose to run the jobs in the queue with the highest priority
• If multiple jobs are chosen, run them in Round-Robin

​

7

Multilevel Feedback Queue (MLFQ)

​

​

• Consists of a number of distinct queues, each assigned a different priority level.
• Each queue has multiple ready-to-run jobs with the same priority.
• At any given time, the scheduler choose to run the jobs in the queue with the highest priority
• If multiple jobs are chosen, run them in Round-Robin

​

8

?

Multilevel Feedback Queue (MLFQ)

​

Rule 1: If Priority(A) > Priority(B), A runs (B doesn’t)

Rule 2: If Priority(A) = Priority(B), RR(A, B)

​

Does it work well?

9

Multilevel Feedback Queue (MLFQ)

​

Rule 1: If Priority(A) > Priority(B), A runs (B doesn’t)

Rule 2: If Priority(A) = Priority(B), RR(A, B)

With only these two rules, A and B will keep alternating via RR, and C and D will never get to run.

What other rule(s) do we need to add?

We need to understand how job priority changes over time.

10

Attempt 1: How to Change Priority

Rule 3: When a job enter the system, it is placed at the highest priority (the top most queue).

Rule 4a: If a job uses up an entire time slice while running, its priority is reduced (it moves down one queue).

Rule 4b: If a job gives up the CPU (voluntarily) before the time slice is up, it stays at the same priority level.

11

Example 1: A Single Long-Running Job

• System maintains three queues, in the order of priority from high to low: Q2, Q1, and Q0.
• Time-slice of 10 ms

12

Example 2: Along Came A Short Job

• Job A (Dark): long-running CPU intensive
• Job B (Gray): short-running interactive

​

Major goal of MLFQ: At first, since the scheduler does not know about the job, it first assumes that is might be a short job (higher priority). If it is not a short job, it will gradually be moved down the queues.

13

Example 3: What about I/O?

• The interactive job (gray) only needs the CPU for 1 ms before performing an I/O. MLFQ keeps B at the highest priority before B keep releasing the CPU.

​

• What are potentially problems?

14

Problem 1: Starvation

• If new interactive jobs keep arriving, long-running job will stay at the bottom queue and never get any work done.

15

Problem 2: Gaming the System

• What if some industrious programmers intentionally write a long running program that relinquishes the CPU just before the time-slice is up (Job B).

16

Problem 3:

• What if a program changes behavior:
• Starting out as a long running job
• Turn into an interactive job

17

Attempt 2: Priority Boost

Rule 5: After some time period S, move all the jobs in the system to the topmost queue

18

Problem: Starvation

Rule 5 help guaranteeing that processes will not be staved. It also helps with CPU-bound jobs that become interactive

19

What should S be set to?

• Voodoo constants (John Ousterhout)
• S requires some form of magic to set them correctly.
• Too high: Long running jobs will starve
• Too low: Interactive jobs will not get a proper share of the CPU.

20

Attempt 3: Better Accounting

Rewrite of Rule 4 to address the issue of gaming the system

Rule 4: Once a job uses up its time allotment at a given level (regardless of how many time it has given up the CPU), its priority is reduced.

21

Summary

Rule 1: If Priority(A) > Priority(B), A runs (B doesn’t)

Rule 2: If Priority(A) = Priority(B), RR(A, B)

Rule 3: When a job enter the system, it is placed at the highest priority (the top most queue).

Rule 4: Once a job uses up its time allotment at a given level (regardless of how many time it has given up the CPU), its priority is reduced.

Rule 5: After some time period S, move all the jobs in the system to the topmost queue

​

MLFQ observes the execution of a job and gradually learns what type of job it is, and prioritize it accordingly.

• Excellent performance for interactive I/O bound jobs: good response time
• Fair for long-running CPU-bound jobs: good turnaround time without starvation.

Used by many systems, including FreeBSD, MacOS X, Solaris, Linux 2.6, and Windows NT

22

Exercise

Follow the Setup External Access slides to enable browser-based access to the VM.

Update the Operating-Systems git repository in the CSC VM

$ cd ~/Operating-Systems

$ git pull

$ cd schedule

$ ls

​

23

Exercise 1

• Use more to read the README-scheduler file
• Run ./scheduler.py to answer the following questions:
• Compute the response time and turnaround time when running three jobs of length 200 with the SJF and FIFO schedulers.
• Now do the same but with jobs of different lengths: 100, 200, and 300.
• Now do the same, but also with the RR scheduler and a time-slice of 1.
• For what types of workloads does SJF deliver the same turnaround times as FIFO?
• For what types of workloads and quantum lengths does SJF deliver the same response times as RR?
• What happens to response time with SJF as job lengths increase? Can you use the simulator to demonstrate the trend?
• 7. What happens to response time with RR as quantum lengths increase? Can you write an equation that gives the worst-case response time, given N jobs?

24

Exercise 2

• Use more to read the README-mlfq file
• Run ./mlfq.py to answer the following questions:
• 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.
• How would you run the scheduler to reproduce each of the examples in the chapter?
• How would you configure the scheduler parameters to behave just like a round-robin scheduler?
• Craft a workload with two jobs and scheduler parameters so that one job takes advantage of the older Rules 4a and 4b (turned on with the -S flag) to game the scheduler and obtain 99% of the CPU over a particular time interval.�

25