ECS150 FQ20
March 27, 2020
Scheduling
Lecture Notes 7
• Processor Scheduling Policy – Policy that determines which thread runs first
• Task – A user request, often called a job
• Response time (or delay) – The user-perceived time to do some task
• Predictability – Low variance in response time to do some task
• Throughput – The rate at which tasks are completed
• Scheduling overhead – The time to switch from one task to another
• Fairness – Equality in the number and timeliness of resources given to each task
• Starvation – The lack of progress for one task, due to resources given to a higher priority task
Uniprocessor Scheduling
• Workload – A set of tasks for some system to perform
• Compute-Bound Task – Only use processor
• I/O-Bound Task – Spends most time waiting for I/O
• Work-Conserving Policy – Never leave the processor idle if there is work to do
• Preemption – Ability to stop running task at any time and give processor to another task
• Scheduling Algorithms
• First-Come, First-Served (FCFS) – Handled with FIFO, first process starts first and executes to completion (causes Convoy Effect, many small get blocked behind)
• Shortest Job First (SJF) – The shortest expect CPU burst runs next (Exponential Average used to predict: tn+1=atn+(1-a)tn)
• Shortest Remaining Time First – Preemptive SJF
• Priority Scheduling
• Indefinite Blocking (Starvation) – Low priority tasks can be starved if high priority doesn’t block
• Aging – Gradual increase in priority the longer a process waits
• Round Robin (RR) – Like FCFS with preemption
• Processor Sharing – Share the processor each gets a time quantum
• Time Quantum (Time Slice) – A period of time a task gets the processor, typically 10
– 100ms
• Max-Min Fairness – Iteratively maximizes the minimum allocation given to a
particular process until all resources are assigned
• Multilevel Queue Scheduling – Multiple queues are used for scheduling
• Foreground (Interactive) – Want low response time
• Background (Batch) – Might want higher throughput or other metric
• Multilevel Feedback-Queue Scheduling – Allows tasks to move between queues
This content is protected and may not be shared, uploaded, or distributed. Lecture Notes 7
1 of 3
ECS150 FQ20 March 27, 2020
Multiprocessor Scheduling
• Scheduling Sequential Applications on Multiprocessors
• MFQ Lock Contention – Lock for Multilevel Feedback-Queue could be bottleneck in
system
• Cache Coherence Overhead – Lock will be held longer due to MFQ data structure being
cached in different core
• Limited Cache Reuse – Migrating threads has potential performance degradation due to
caching
• Affinity Scheduling – Once thread is scheduled on processor it stays on processor
• Scheduling Parallel Applications
• Oblivious Scheduling – OS operates without knowledge of the intent of the parallel
application
• Bulk Synchronous Delay – Threads are synchronized before computing next stage,
computation is limited by slowest thread
• Producer-Consumer Delay – One thread in the producer-consumer chain becomes
bottleneck
• Critical Path Delay – Critical Path is the minimum sequence of steps for application
to compute result, delay is in this path
• Preemption of lock holder – The holder of a lock is preempted requiring all others to
wait
• Gang Scheduling – All tasks of a process are scheduled together
• Processor Pinning – Explicitly specifying processor affinity for a thread
• Space Sharing – Processes get own share of processors
• Scheduler Activation – Application is aware of number of processors allocated to it
(notified through upcalls)
• Multiprocessor Scheduling Policy – How many processors should be assigned to a
process
Energy Aware Scheduling
• Processor Design – Different architectures have different energy cost for execution
• Processor Usage – Disabling cores can save power if not needed
• I/O Device Power – Disabling of unused/inactive I/O can save power
• Below the threshold of Human Perception – Optimize for energy use where human cannot
perceive difference
• Above the threshold of Human Perception – Optimize for response time if the user will
notice
• Long-running or background tasks – Balance energy use and responsiveness depending on
the available battery resources
Real-Time Scheduling
• Real-Time Constraint – Computation must be completed by a real deadline
This content is protected and may not be shared, uploaded, or distributed. Lecture Notes 7
2 of 3
ECS150 FQ20 March 27, 2020
• Over-provisioning – Provide more resources than needed
• Earliest Deadline First – Work on earliest deadline task first
• Priority Donation – Give higher priority to tasks
• Priority Inversion – A higher priority task is blocked by a medium priority task
Queueing Theory
• Deterministic Modeling – Analysis of predetermined workload • Analytic Evaluation
• Queuing Models
• Queueing Delay W – Wait time for a task to be scheduled
• Queued Tasks Q – Number of tasks that are queued
• Service Time S – Time to complete a task
• Response Time R – R = W + S
• Network Analysis – Use of queuing theory from network to analyze performance on
arrival/wait times etc.
• Arrival Rate λ – Average rate at which new tasks arrive
• Service Rate μ – The number of tasks the server can complete per unit of time
• Utilization U – is the fraction of time the server is busy if (λ < μ) then λ/μ, if (λ ≥ μ) then
1
• Throughput X – The number of tasks processed by the system per unit time X = Uμ , or
X is λ if (U < 1) and μ if (U = 1)
• Tasks in system N – The average number of tasks in the system is N = Q + U
• Little’s Law – Equation for stable system N = XR
Overload management
• Reduce the amount of work to be done – Reject some work to reduce load
This content is protected and may not be shared, uploaded, or distributed. Lecture Notes 7
3 of 3