ECE391- Computer System Engineering
Lecture 17 Scheduling
University of Illinois at Urbana- Champaign
Fall 2021
Announcements
• MP3
– Checkpoint 2: 5:59PM on Tuesday 10/26
– CP2 Demo: 10/26 Tuesday, 6:30pm: all teams
• Exam 2
– 10/28/2021, 7-9 PM, ECEB 1002
– Conflicts by 10/22/2021
– Review Session in class 10/26/2021 – No Class 10/28/2021
Basic Philosophy
SCHEDULING
What is scheduling?
Role of Dispatcher vs. Scheduler
• Dispatching(LastTime)
– Low-level mechanism
– Responsibility: context switch
• Save previous process state in PCB
• Load next process state from PCB to registers
• Change scheduling state of process (running, ready, or
blocked)
• Migrate processes between different scheduling queues
• Switch from kernel to user mode
• Scheduler (Today)
– High-level policy
– Responsibility: Deciding which process to run
http://www.cs.columbia.edu/~junfeng/09sp-w4118/syllabus.html
What kinds of things must be scheduled?
Scheduling Philosophy
• Interactive
–examples: editors, GUIs
–driven by human interaction (e.g., keystrokes, mouse clicks)
–little or no work to do after each event –but important to respond quickly
Scheduling Philosophy
• Batch
–examples: compilation, simulation
–usually only time to completion matters –want a fair share of CPU computation
Scheduling Philosophy (cont.)
• Real-time
– examples: music, video, teleconferencing
– periodic deadlines (e.g., 30 frames per second of video)
– work often only useful if finished on time
• alternative taxonomy: I/O-bound vs. compute-
bound
• Goal of scheduling:
efficient, fair, and responsive (all at once!)
How do we evaluate scheduling methods?
Goal of Scheduling
• Efficient
• Fair
• Responsive
• (And a bag of chips[1])
[1] Adj. something or someone which possesses all desired qualities PLUS unimagined or unforseen bonuses.
Algorithms and Designs
SCHEDULING
6.4 Scheduling Basics
• Schedulers come in two basic flavors – Preemptive
– Non-preemptive
• Basic scheduler steps
1. Grab the attention of the processor.
2. Save the state of the currently running process.
3. Select a new process to run.
4. Dispatch the newly selected process to run on the processor.
https://www.cc.gatech.edu/~rama/CS2200-External/ppt-slides/Chapter06.pptx
6.6 Non-preemptive Scheduling Algorithms
• Non-preemptive means that once a process is running it will continue to do so until it relinquishes control of the CPU. This would be because it terminates, voluntarily yields the CPU to some other process (waits) or requests some service from the operating system.
https://www.cc.gatech.edu/~rama/CS2200-External/ppt-slides/Chapter06.pptx
6.7 Preemptive Scheduling Algorithms • Two simultaneously implications.
– Scheduler is able to assume control of the processor anytime unbeknownst to the currently running process.
– Scheduler is able to save the state of the currently running process for proper resumption from the point of preemption.
• Any of the Non-preemptive algorithms can be made Preemptive
https://www.cc.gatech.edu/~rama/CS2200-External/ppt-slides/Chapter06.pptx
First-Come, First-Served (FCFS)
• Simplest CPU scheduling algorithm
– First job that requests the CPU gets the CPU – Nonpreemptive
• Advantage: simple implementation with FIFO queue
• Disadvantage: waiting time depends on arrival order
– short jobs that arrive later have to wait long http://www.cs.columbia.edu/~junfeng/09sp-w4118/syllabus.html
Example of FCFS
Process Burst Time P1 24
P2 3
P3 3
• Suppose that the processes arrive in the order: P1 , P2 , P3
• The Gantt Chart for the schedule is:
P1
P2
P3
0 24 27 30
• WaitingtimeforP1 =0;P2 =24;P3=27
• Average waiting time: (0 + 24 + 27)/3 = 17
http://www.cs.columbia.edu/~junfeng/09sp-w4118/syllabus.html
Example of FCFS (Cont.) Suppose that the processes arrive in the order
P2 ,P3 ,P1 • The Gantt chart for the schedule is:
P2
P3
P1
036 30
• WaitingtimeforP1=6;P2 =0;P3=3
• Average waiting time: (6 + 0 + 3)/3 = 3
• Much better than previous case
• Convoy effect: short process stuck waiting for long process
– Alsocalledheadofthelineblocking
http://www.cs.columbia.edu/~junfeng/09sp-w4118/syllabus.html
Shortest Job First (SJF)
• Schedule the process with the shortest time
– FCFSifsametime
• Advantage: minimize average wait time
– provablyoptimal
– Movingshorterjobbeforelongerjobdecreaseswaitingtimeofshort job more than increases waiting time of long job
– Reducesaveragewaittime • Disadvantage
– Notpractical:difficulttopredictbursttime
• Possible: past predicts future
– Maystarvelongjobs http://www.cs.columbia.edu/~junfeng/09sp-w4118/syllabus.html
Shortest Remaining Time First (SRTF) • SRTF == SJF with preemption
– New process arrives w/ shorter CPU burst than the remaining for current process
– SJF without preemption: let current process run
– SRTF: preempt current process
– Reduces average wait time
http://www.cs.columbia.edu/~junfeng/09sp-w4118/syllabus.html
Example of Nonpreemptive SJF
Process Arrival Time Burst Time P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
• SJF
0 3 78 12 16
• Averagewaitingtime=(0+6+3+7)/4 =4 http://www.cs.columbia.edu/~junfeng/09sp-w4118/syllabus.html
P1
P3
P2
P4
Example of Preemptive SJF (SRTF)
Process Arrival Time Burst Time P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
• SJF (preemptive)
0
11 16
P1
P2
P3
P2
P4
P1
2457
• Averagewaitingtime=(9+1+0+2)/4=3 http://www.cs.columbia.edu/~junfeng/09sp-w4118/syllabus.html
Round-Robin (RR)
• Practical approach to support time-sharing
– Run process for a time slice, then move to back of FIFO queue
– Preempted if still running at end of time-slice
• Advantages
– Fair allocation of CPU across processes
– Low average waiting time when job lengths vary widely
http://www.cs.columbia.edu/~junfeng/09sp-w4118/syllabus.html
Example of RR with Time Slice = 20 Process Arrival Time Burst Time
P1 0 400 P2 20 60 P3 20 60
• The Gantt chart is:
P1
P2
P3
P1
P2
P3
P1
P2
P3
P1
0 20 40 60 80 100120 140160 180200
• Average waiting time:
• Compare to FCFS and SJF:
http://www.cs.columbia.edu/~junfeng/09sp-w4118/syllabus.html
Disadvantage of Round-Robin
• Pooraveragewaitingtimewhenjobshavesimilar lengths
– Imagine N jobs each requiring T time slices
– RR: all complete roughly around time N*T
– Average waiting time is even worse than FCFS!
• Performancedependsonlengthoftimeslice – Too high è degenerate to FCFS
– Too lowètoo many context switch, costly – How to set time-slice length?
http://www.cs.columbia.edu/~junfeng/09sp-w4118/syllabus.html
TANSTAAFL
Time slice and Context Switch Time
http://www.cs.columbia.edu/~junfeng/09sp-w4118/syllabus.html
Priorities
• A priority is associated with each process
– Runhighestpriorityreadyjob(somemaybeblocked) – Round-robinamongprocessesofequalpriority
– Canbepreemptiveornonpreemptive
• Representing priorities
– Typicallyaninteger
– Thelargerthehigherorthelower?
• Solaris: 0-59, 59 is the highest
• Linux: 0-139, 0 is the highest
• Question: what data structure to use for priority scheduling? One queue for all processes?
http://www.cs.columbia.edu/~junfeng/09sp-w4118/syllabus.html
Setting Priorities • Priority can be statically assigned
– Some processes always have higher priority than others
– Problem: starvation
• Priority can be dynamically changed by OS
– Aging: increase the priority of processes that wait in the ready queue for a long time
http://www.cs.columbia.edu/~junfeng/09sp-w4118/syllabus.html
Priority Inversion
• High priority process depends on low priority process (e.g. to release a lock)
– What if another process with in-between priority arrives?
• Solution: priority inheritance
– inherit priority of highest process waiting for a
resource
– Must be able to chain multiple inheritances
– Must ensure that priority reverts to original value
http://www.cs.columbia.edu/~junfeng/09sp-w4118/syllabus.html
Linux
SCHEDULING
General strategy
• break time into slices
• allow interactive jobs to preempt the current job based on interrupts
– typically, a job becomes runnable when an interrupt occurs (e.g., a key is pressed)
– Linux checks for rescheduling after each interrupt, system call, and exception
• Linux 2.4 does NOT preempt code running in kernel (code may yield)
• Linux 2.6 DOES preempt code running in kernel to support real-time
Time broken into epochs
• each task given a quantum of time (in ticks of 10 milliseconds)
• run until no runnable task has time left • then start a new epoch
General Scheduling Algorithm Used by Linux
• Real-time jobs
– always given priority over non-real-time jobs – prioritized amongst themselves
• Static and dynamic priorities used for non- real-time jobs
Interactive jobs handled with heuristics
• heuristic estimate job interactiveness
• an interactive job
– can continue to run after running out of time – takes turns with other interactive jobs
• philosophy is that they don’t usually use up quantum
• heuristic ensures that job can’t use lots of CPU and still be “interactive”
Task State (fields of task_struct) • Statefieldcanbeoneof
– TASK_RUNNING
• task is executing currently or waiting to execute • task is in a run queue on some processor
– TASK_INTERRUPTIBLE
• task is sleeping on a semaphore/condition/signal • task is in a wait queue
• can be made runnable by delivery of signal
– TASK_UNINTERRUPTIBLE
• task is busy with something that can’t be stopped
• e.g., a device that will stay in unrecoverable state without further task interaction
• cannot be made runnable by delivery of signal
Task State (fields of task_t) (cont.)
– TASK_STOPPED
• task is stopped
• task is not in a queue; must be woken by signal
– TASK_ZOMBIE
• task has terminated
• task state retained until parent collects exit status information • task is not in a queue
• The swapper process is always runnable (it’s an idle loop)
Scheduling Data Structures
lock
# runnable
# switches
timestamp
current task
idle task
active array
expired array
priority array #1
priority array #2
load bal. for SMPs
• Each processor has a run queue (struct runqueue in sched.c)
– each run queue has two priority arrays
– arrays are lists of tasks of each priority
– they are double-buffered to implement epochs
for interactive jobs
tasks
two pointers used to implement double-buffering for priority arrays
Priority Array Structure (struct prio_array in sched.c)
• 100 real-time priorities
• 40 regular priorities
• One list per priority and a bitmap to make finding non-empty list fast
140 doubly-linked lists of tasks (using task’s run_list field)
# active
bitmap of non-empty lists
…
Rescheduling and Yielding
• Task can change (called a context switch) when
– current task yields by calling schedule (sched_yield at user level)
– current task runs out of time
Rescheduling and Yielding
• Other places where a task may yield implicitly – semaphores
– wake_up_process – copy_to/from_user
Rescheduling and Yielding
• At every timer tick (interrupt, generated every 10 milliseconds)
– run a function (scheduler_tick) to reduce current task’s time
– executes with IF=0
– replace it with another task if appropriate
– interrupt is IRQ0
Linux Scheduler CPU is running the idle task scheduler_tick and task_running_tick
idle_cpu returns 1 if
update_cpu_clock tracks nanoseconds since last tick/context switch
(kernel/sched.c)
for all but idle task, call task_running_tick
Take care of task which already expired
Critical section begins
Handle real-time tasks
if a task’s time slice expires
dequeue and reschedule the task
breaks long time slices into pieces
Critical section ends
Comments on scheduler_tick function • idle_cpu returns 1 if CPU is running the idle
task
• update_cpu_clock tracks nanoseconds since last tick/context switch
• For all but idle task, call task_running_tick
Comments on task_running_tick function
• If the task has already expired
– make sure that it gets rescheduled on return from
interrupt
– by setting TIF_NEED_RESCHED
• The remainder is a critical section for the run queue
• Next handle real-time tasks
– real-time round-robin tasks take turns by placing themselves at the end of the list of their priority
– otherwise real-time tasks just keep rescheduling (until yield or preemption by higher priority)
Comments on task_running_tick function
• Ifatask’stimesliceexpires – take it out of the run queue
– mark it as needing to be removed from processor
– give it a new time slice
– if it’s an interactive job, and expired tasks are not being starved by interactive ones, put it back into run queue (at end)
– normal tasks go into expired queue
• Lastblock
– breaks long time slices into pieces
– round-robin between tasks at same priority
Linux Scheduler
(Part1)
schedule function (kernel/sched.c)
Sleep timestamp records time at which task leaves CPU
Critical section begins
if the task is trying to go to sleep check for receipt of signal
default case removes task from run queue no tasks are runnable
nothing is left in the active run queue
find the next task to run
– find first no-zero bit in the bitmask of the active set – take the first task at the list indicataed by that bit
Comments on schedule function
• Schedule() function called when processor needs to change to new task
– time has expired for current task, or
– task has voluntarily yielded (by calling this function)
• Sleep timestamp records time at which task leaves
CPU
• Remainder is run queue critical section
• If the task is trying to go to sleep – check for receipt of signal
– handles race condition with sleeping in wait queue
• Default case removes task from run queue
Comments on schedule function
(cont.) • If no tasks are runnable
– run the idle task
– reset forced expiration of interactive tasks
• Ifnothingisleftintheactiverunqueue
– the epoch is over
– swap the priority arrays
– and reset forced expiration of interactive tasks
• Find the next task to run
– find first bit selects the priority
– then take the first task at that priority (linked list)
Linux Scheduler (Part2) schedule function (kernel/sched.c)
clear need_resched flag for next time current task is scheduled
Switch if newly selected task is not the current one call architecture-dependent switch function
Critical section ends
Comments on schedule function (cont.)
• This portion of the code implements the actual switch
• First clears need_resched flag for next time current
task is scheduled
• Switch only occurs if newly selected task is not the current one
• Switch does two things
– does some accounting
– calls architecture-dependent switch function (context_switch)