Today’s Topics

u CPU scheduling basics

COS 318: Operating Systems u CPU scheduling algorithms

CPU Scheduling

Jaswinder Pal Singh and a Fabulous Course Staff

Computer Science Department
Princeton University

(http://www.cs.princeton.edu/courses/cos318/)

CPU Scheduler Preemptive and Non-Preemptive Scheduling

u Selects from among the processes/threads that are

ready to execute (in ready state), and allocates the CPU
Terminate Exited
to one of them (puts in running state). (call scheduler)
u CPU scheduling can be non-preemptive or pre-emptive
Scheduler
u Non-preemptive scheduling decisions may take place dispatch Running
when a process changes state: Block for resource
(call scheduler)
1. switches from running to waiting state Yield, Interrupt
2. switches from running to ready state (call scheduler)
3. switches from waiting to ready Ready
Blocked
4. terminates
u All other scheduling is preemptive Create Resource free,
l E.g. may be driven by an interrupt I/O completion interrupt
(move to ready queue)
4

1
Scheduling Criteria Some Problem Cases in Scheduling
u Assumptions made here u Scheduler completely blind about job types
l One process per user and one thread per process l Little overlap between CPU and I/O
l Processes are independent
u Optimization involves favoring jobs of type “A” over “B”
u Scheduling Goals l Lots of A’s? B’s starve
l Minmize response time (interactive) or turnaround time (batch) u Interactive process gets trapped behind others
• Time from submission of job/operation to its completion l Response time bad for no good reason.
• Job/operation could be keystroke in editor or running a big science simulation
u Priorities: A depends on B and A’s priority > B’s
l Maximize throughput (operations/jobs per second)
• Minimize overhead (e.g. context switching) l B never runs, so A doesn’t continue
• Use system resources efficiently (CPU, memory, disk, etc)
l Fairness and proportionality
• Share CPU in some equitable way, or that meets users’ expectations
• Everyone makes some progress; no one starves

Scheduling Algorithms First-Come-First-Serve (FCFS) Policy

u Schedule tasks in the order they arrive
l Run them until completion or they block or they yield
u Simplified view of scheduling:
u Example 1
l Save process state (to PCB)
l P1 = 24 sec, P2 = 3 sec, and P3 = 3 sec, submitted ‘same’ time in that order
l Pick which process to run next l Avg. response time = (24+27+30)/3 = 27. Avg. wait time (0+24+27)/3 = 17
l Dispatch process
P1 P2 P3
u Example 2
l Same jobs but come in different order: P2, P3 and P1
l Average response time = (3 + 6 + 30) / 3 = 13 sec, avg wait time: 3 sec

P2 P3 P1

u FIFO pro: Simple. Con: Short jobs get stuck behind long ones

2
Shortest Job First (SJF) Scheduling Example of non-preemptive SJF
u Whenever scheduling decision is to be made, schedule Process Arrival Time Burst Time
process with shortest remaining time to completion P1 0.0 7
l Non-preemptive case: straightforward (if time can be estimated) P2 2.0 4
l Preemptive case: if new process arrives with smaller remaining P3 4.0 1
time, preempt running process and schedule new one P4 5.0 4
u Simple example
l P1 = 6sec, P2 = 8sec, P3 = 7sec, P4 = 3sec uSJF (non-preemptive)
l All arrive at the same time
P1 P3 P2 P4
P4 P1 P3 P2
0 3 7 8 12 16
u Can you do better than SRTCF in terms of average
response time? uAverage waiting time = (0 + 6 + 3 + 7)/4 = 4
u Issues with this approach?

Example of preemptive SJF Round Robin

Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
Current
uSJF (preemptive) process

u Similar to FCFS, but with a time slice for timer interrupt

P1 P2 P3 P2 P4 P1
l Time-interrupted process is moved to end of queue

11 16
u FCFS for preemptive scheduling
0 2 4 5 7
u Real systems also have I/O interrupts in the mix
uAverage waiting time = (9 + 1 + 0 +2)/4 = 3
u How do you choose time slice?

3
FCFS vs. Round Robin Resource Utilization Example
u Example u A, B, and C run forever (in this order)
l 10 jobs and each takes 100 seconds l A and B each uses 100% CPU forever
u FCFS (non-preemptive scheduling) l C is a CPU plus I/O job (1ms CPU + 10ms disk I/O)
l job 1: 100s, job2: 200s, ... , job10: 1000s u Time slice 100ms
u Round Robin (preemptive scheduling) l A (100ms CPU), B (100ms CPU), C (1ms CPU + 10ms I/O),
l time slice 1sec and no overhead …
l job1: 991s, job2: 992s, ... , job10: 1000s
u Comparisons u Time slice 1ms
l Round robin is much worse (avg turnaround time) for jobs l A (1ms CPU), B (1ms CPU), C (1ms CPU), A (1ms CPU), B
about the same length (1ms CPU), C(10ms I/O) || A, B, …, A, B
l Both are fair, but RR is bad in the case where FIFO is optimal
l But, e.g. for streaming video, RR is good, since everyone u What do we learn from this example?
makes progress and gets a share “all the time”

Virtual Round Robin Priority Scheduling

u I/O bound processes go Timeout u Not all processes are equal, so rank them
to auxiliary queue u The method
(instead of ready Dispatch l Assign each process a priority
queue) to get CPU l Run the process with highest priority in the ready queue first
scheduled Admit
l Adjust priority dynamically (I/O wait raises the priority, reduce
u Aux queue is FIFO Aux queue priority as process runs)
u Aux queue has I/O wait u Why adjusting priorities dynamically
I/O completion

preference over ready l T1 at priority 4, T2 at priority 1 and T2 holds lock L

queue I/O wait l Scenario
• T1 tries to acquire L, fails, blocks.
• T3 enters system at priority 3.
I/O wait • T2 never gets to run, and T1 is never unblocked

16 17

4
Multi-level Feedback Queues (MFQ) Lottery Scheduling
u Motivations
l SJF does well with average response time, but is unfair (long
Priority Time slices jobs can be starved)
4 1 l Need a way to give everybody some chance of running
3 2
u Lottery method
2 4
l Give each job a number of tickets
1 8
l Randomly pick a winning ticket
l To approximate SJF, give short jobs more tickets
u Round-robin queues, each with different priority
l To avoid starvation, give each job at least one ticket
u Higher priority queues have shorter time slices
l Cooperative processes can exchange tickets
u Jobs start at highest priority queue
u If timeout expires, drop one level
u If timeout doesn’t expire, stay or pushup one level
u What does this method do?

Multiprocessor and Cluster Multiprocessor/Cluster Scheduling

u Design issue
l Process/thread to processor assignment
CPU CPU u Gang scheduling (co-scheduling)
L1 $ … L1 $ … l Threads of the same process will run together
L2 $ L2 $ l Processes of the same application run together
u Dedicated processor assignment
Memory Network l Threads will be running on specific processors to completion
l Is this a good idea?

Multiprocessor architecture Cluster or multicomputer

u Cache coherence u Distributed memory

u Single OS u An OS in each box

20 21

5
Real-Time Scheduling Rate Monotonic Scheduling (Liu & Layland 73)

u Two types of real-time u Assumptions

l Hard deadline l Each periodic process must complete within its period
• Must meet, otherwise can cause fatal error l No process is dependent on any other process
l Soft Deadline l A process needs same amount of CPU time on each burst
• Meet most of the time, but not mandatory l Non-periodic processes have no deadlines
l Process preemption occurs instantaneously (no overhead)
u Admission control
l Take a real-time process only if the system can guarantee the u Main ideas of RMS
“real-time” behavior of all processes. l Assign each process a fixed priority = frequency of occurrence
l Assume periodic processes. The jobs are schedulable, if the l Run the process with highest priority
following holds: u Example
∑ CTi ≤1 l P1 runs every 30ms gets priority 33 (33 times/sec)
i
l P2 runs every 50ms gets priority 20 (20 times/sec)

where Ci = computation time, and Ti = period

22 23

Earliest Deadline Scheduling BSD 4.3 Scheduling with Multi-Queue

u Assumptions u “1 sec” preemption
l When a process needs CPU time, it announces its deadline l Preempt if a process doesn’t block or complete within 1 sec
l No need to be periodic process
u Priority is recomputed every second
l CPU time needed may vary
l Pi = base + (CPUi-1) / 2 + nice, where CPUi = (Ui + CPUi-1) / 2
u Main idea of EDS l Base is the base priority of the process
l Sort ready processes by their deadlines l Ui is process utilization in interval i
l Run the first process on the list (earliest deadline first)
u Priorities
l When a new process is ready, it preempts the current one if its
deadline is closer l Swapper
l Block I/O device control
u Example
l File operations
l P1 needs to finish by 30sec, P2 by 40sec and P3 by 50sec
l P1 goes first l Character I/O device control
l More in MOS 7.4.4 l User processes

24 25

6
Linux Scheduling Windows Scheduling
u Time-sharing scheduling u Classes and priorities
l Each process has a priority and # of credits l Real time: 16 static priorities
l Process with the most credits will run next l Variable: 16 variable priorities, start at a base priority
• If a process has used up its quantum, lower its priority
l I/O event increases credits
• If a process waits for an I/O event, raise its priority
l A timer interrupt causes a process to lose a credit, until zero
credits reached at which time process is interrupted
u Priority-driven scheduler
l For real-time class, do round robin within each priority
l If no process has credits, then the kernel issues credits to all
processes: credits = credits/2 + priority l For variable class, do multiple queue
u Multiprocessor scheduling
l For N processors, run N-1 highest priority threads on N-1
u Real-time scheduling processors and run remaining threads on a single processor
l Soft real-time (really just higher priority threads: FIFO or RR) l A thread will wait for processors in its affinity set, if there are
l Kernel cannot be preempted by user code other threads available (for variable priorities)

26 27

Summary
u Best algorithms may depend on your primary goals
l FIFO simple, optimal avg response time for tasks of equal size,
but can be poor avg reponse time if tasks vary a lot in size
l SJF gives the minimal average response time, but can be not
great in variance of response times
l RR has very poor avg response time for equal size tasks, but is
close to SJF for variable size tasks
l Small time slice is important for improving I/O utilization
l If tasks have mix of processing and I/O, do well under SJF but
can do poorly under RR
l Priority and its variations are used in most systems
l Lottery scheduling is flexible
l Multi-queue can achieve a good balance
l Admission control is important in real-time scheduling
28