Understanding Operating System Scheduling Principles

 
Operating System Principles:
Scheduling
CS 
111
Operating 
Systems
Harry Xu
 
 
Outline
 
What is scheduling?
What are our scheduling goals?
What resources should we schedule?
Example scheduling algorithms and their
implications
 
What Is Scheduling?
 
An operating system often has choices about
what to do next
In particular:
For a resource that can serve one client at a time
When there are multiple potential clients
Who gets to use the resource next?
And for how long?
Making those decisions is scheduling
 
OS Scheduling Examples
 
What job to run next on an idle core?
How long should we let it run?
In what order to handle a set of block requests
for a disk drive?
If multiple messages are to be sent over the
network, in what order should they be sent?
We’ll primarily consider scheduling processes
 
How Do We Decide
How To Schedule?
 
Generally, we choose goals we wish to achieve
And design a scheduling algorithm that is
likely to achieve those goals
Different scheduling algorithms try to optimize
different quantities
So changing our scheduling algorithm can
drastically change system behavior
 
The Process Queue
 
The OS typically keeps a queue of processes
that are ready to run
Ordered by whichever one should run next
Which depends on the scheduling algorithm used
When time comes to schedule a new process,
grab the first one on the process queue
Processes that are not ready to run either:
Aren’t in that queue
Or are at the end
 
Potential Scheduling Goals
 
Maximize throughput
Get as much work done as possible
Minimize average waiting time
Try to avoid delaying too many for too long
Ensure some degree of fairness
E.g., minimize worst case waiting time
Meet explicit priority goals
Scheduled items tagged with a relative priority
Real time scheduling
Scheduled items tagged with a deadline to be met
 
Different Kinds of Systems,
Different Scheduling Goals
 
Time sharing
Fast response time to interactive programs
Each user gets an equal share of the CPU
Batch
Maximize total system throughput
Delays of individual processes are unimportant
Real-time
Critical operations must happen on time
Non-critical operations may not happen at all
 
Preemptive Vs.
Non-Preemptive Scheduling
 
When we schedule a piece of work, we could
let it use the resource until it finishes
Or we could interrupt it part way through
Allowing other pieces of work to run instead
If scheduled work always runs to completion,
the scheduler is non-preemptive
If the scheduler temporarily halts running work
to run something else, it’s preemptive
 
Pros and Cons of
Non-Preemptive Scheduling
 
+
Low scheduling overhead
+
Tends to produce high throughput
+
Conceptually very simple
Poor response time for processes
Bugs can cause machine to freeze up
If process contains infinite loop, e.g.
Not good fairness (by most definitions)
May make real time and priority scheduling difficult
 
Pros and Cons of Pre-emptive
Scheduling
 
+
Can give good response time
+
Can produce very fair usage
+
Good for real-time and priority scheduling
More complex
Requires ability to cleanly halt process and
save its state
May not get good throughput
Possibly higher overhead
 
Scheduling: Policy and Mechanism
 
The scheduler will move jobs into and out of a
processor (
dispatching
)
Requiring various mechanics to do so
Part of the scheduling mechanism
How dispatching is done should not depend on
the policy used to decide who to dispatch
Desirable to separate the choice of who runs
(policy) from the dispatching mechanism
Also desirable that OS process queue structure not
be policy-dependent
Scheduling the CPU
ready queue
dispatcher
context
switcher
CPU
 
yield (or preemption)
resource
manager
 
resource request
 
resource granted
 
new
process
 
Scheduling and Performance
 
How you schedule important system activities
has a major effect on performance
Performance has different aspects
You may not be able to optimize for all of them
Scheduling performance has very different
characteristic under light vs. heavy load
Important to understand the performance
basics regarding scheduling
 
General Comments on Performance
 
Performance goals should be quantitative and
measurable
If we want “goodness” we must be able to quantify it
You cannot optimize what you do not measure
Metrics ... the way & units in which we measure
Choose a characteristic to be measured
 
It must correlate well with goodness/badness of service
Find a unit to quantify that characteristic
 
It must a unit that can actually be measured
Define a process for measuring the characteristic
That’s enough for now
But actually measuring performance is complex
How Should We Quantify
Scheduler Performance?
 
Candidate metric: throughput 
(processes/second)
But different processes need different run times
Process completion time not controlled by scheduler
Candidate metric: delay 
(milliseconds)
But specifically what delays should we measure?
Time to finish a job (turnaround time)?
Time to get some response?
Some delays are not the scheduler's fault
 
Time to complete a service request
 
Time to wait for a busy resource
 
Other Scheduling Metrics
 
Mean time to completion (seconds)
For a particular job mix (benchmark)
Throughput (operations per second)
For a particular activity or job mix (benchmark)
Mean response time (milliseconds)
Time spent on the ready queue
Overall “goodness”
Requires a customer specific weighting function
Often stated in 
Service Level Agreements (SLAs)
 
An Example – Measuring CPU
Scheduling
 
Process execution can be divided into phases
Time spent running
 
The process controls how long it needs to run
Time spent waiting for resources or completions
 
Resource managers control how long these take
Time spent waiting to be run
 
This time is controlled by the scheduler
Proposed metric:
Time that “ready” processes spend waiting for the
CPU
Typical Throughput vs. Load Curve
throughput 
offered load
 
ideal
 
typical
 
Maximum possible capacity
 
Why Don’t We Achieve Ideal
Throughput?
 
Scheduling is not free
It takes time to dispatch a process (overhead)
More dispatches mean more overhead (lost time)
Less time (per second) is available to run processes
How to minimize the performance gap
Reduce the overhead per dispatch
Minimize the number of dispatches (per second)
 
This phenomenon is seen in many areas
besides process scheduling
Typical Response Time
vs. Load Curve
D
elay 
(response time)
 
ideal
 
typical
offered load
 
Why Does Response Time
Explode?
 
Real systems have finite limits
Such as queue size
When limits exceeded, requests are typically dropped
Which is an infinite response time, for them
There may be automatic retries (e.g., TCP), but they could
be dropped, too
If load arrives a lot faster than it is serviced, lots of
stuff gets dropped
Unless you’re careful, overheads explode during
periods of heavy load
 
Graceful Degradation
 
When is a system “overloaded”?
When it is no longer able to meet its service goals
What can we do when overloaded?
Continue service, but with degraded performance
Maintain performance by rejecting work
Resume normal service when load drops to normal
What should we 
not
 do when overloaded?
Allow throughput to drop to zero (i.e., stop doing
work)
Allow response time to grow without limit
 
Non-Preemptive Scheduling
 
Scheduled process runs until it yields CPU
Works well for simple systems
Small numbers of processes
With natural producer consumer relationships
Good for maximizing throughput
Depends on each process to voluntarily yield
A piggy process can starve others
A buggy process can lock up the entire system
 
Non-Preemptive Scheduling
Algorithms
 
First come first served
Shortest job next
We won’t cover this in detail
Real time schedulers
 
First Come First Served
 
The simplest of all scheduling algorithms
Run first process on ready queue
 Until it completes or yields
Then run next process on queue
Until it completes or yields
Highly variable delays
Depends on process implementations
All processes will eventually be served
First Come First Served Example
 
Note: Average is worse than total/5 because four other processes had
to wait for the slow-poke who ran first.
 
Total
 
1275
 
595
 
When Would First Come First
Served Work Well?
 
FCFS scheduling is very simple
It may deliver very poor response time
Thus it makes the most sense:
1.
 When response time is not important (e.g., batch)
2.
 In embedded (e.g., telephone or set-top box)
systems
Where computations are brief
And/or exist in natural producer/consumer relationships
 
Real Time Schedulers
 
For certain systems, some things 
must
 happen
at particular times
E.g., industrial control systems
If you don’t rivet the widget before the conveyer
belt moves, you have a worthless widget
These systems must schedule on the basis of
real-time deadlines
Can be either 
hard 
or 
soft
 
Hard Real Time Schedulers
 
The system absolutely must meet its deadlines
By definition, system fails if a deadline is not
met
E.g., controlling a nuclear power plant . . .
How can we ensure no missed deadlines?
Typically by very, very careful analysis
Make sure no possible schedule causes a deadline
to be missed
By working it out ahead of time
Then scheduler rigorously follows deadlines
 
Ensuring Hard Deadlines
 
Must have deep understanding of the code used in
each job
You know 
exactly
 how long it will take
Vital to avoid non-deterministic timings
Even if the non-deterministic mechanism usually speeds
things up
You’re screwed if it 
ever
 slows them down
Typically means you do things like turn off interrupts
And scheduler is non-preemptive
Typically you set up a pre-defined schedule
No run time decisions
 
Soft Real Time Schedulers
 
Highly desirable to meet your deadlines
But some (or any) of them can occasionally be
missed
Goal of scheduler is to avoid missing deadlines
With the understanding that you miss a few
May have different classes of deadlines
Some “harder” than others
Need not require quite as much analysis
 
What If You Don’t Meet a
Deadline?
 
Depends on the particular type of system
Might just drop the job whose deadline you
missed
Might allow system to fall behind
Might drop some other job in the future
At any rate, it will be well defined in each
particular system
 
What Algorithms Do You
Use For Soft Real Time?
 
Most common is Earliest Deadline First
Each job has a deadline associated with it
Based on a common clock
Keep the job queue sorted by those deadlines
Whenever one job completes, pick the first one
off the queue
Prune the queue to remove missed deadlines
Goal: Minimize 
total lateness
 
Example of a Soft Real Time
Scheduler
 
A video playing device
Frames arrive
From disk or network or wherever
Ideally, each frame should be rendered “on
time”
To achieve highest user-perceived quality
If you can’t render a frame on time, might be
better to skip it entirely
Rather than fall further behind
 
Preemptive Scheduling
 
Again in the context of CPU scheduling
A thread or process is chosen to run
It runs until either it yields
Or the OS decides to interrupt it
At which point some other process/thread runs
Typically, the interrupted process/thread is
restarted later
 
Implications of Forcing Preemption
 
A process can be forced to yield at any time
If a more important process becomes ready
Perhaps as a result of an I/O completion interrupt
If running process’s importance is lowered
Perhaps as a result of having run for too long
Interrupted process might not be in a “clean” state
Which could complicate saving and restoring its state
Enables enforced “fair share” scheduling
Introduces extra context switches
Not required by the dynamics of processes
Creates potential resource sharing problems
 
Implementing Preemption
 
Need a way to get control away from process
E.g., process makes a sys call, or clock interrupt
Consult scheduler before returning to process
Has any ready process had its priority raised?
Has any process been awakened?
Has current process had its priority lowered?
Scheduler finds highest priority ready process
If current process, return as usual
If not, yield on behalf of current process and
switch to higher priority process
 
Clock Interrupts
 
Modern processors contain a clock
A peripheral device
With limited powers
Can generate an interrupt at a fixed time
interval
Which temporarily halts any running process
Good way to ensure that runaway process
doesn’t keep control forever
Key technology for preemptive scheduling
 
Round Robin Scheduling
Algorithm
 
Goal - fair share scheduling
All processes offered equal shares of CPU
All processes experience similar queue delays
All processes are assigned a nominal time slice
Usually the same sized slice for all
Each process is scheduled in turn
Runs until it blocks, or its time slice expires
Then put at the end of the process queue
Then the next process is run
Eventually, each process reaches front of queue
 
Properties of Round Robin
Scheduling
 
All processes get relatively quick chance to do
some computation
At the cost of not finishing any process as quickly
A big win for interactive processes
Far more context switches
Which can be expensive
 
Round Robin and I/O Interrupts
 
Processes get halted by round robin scheduling
if their time slice expires
If they block for I/O (or anything else) on their
own, the scheduler doesn’t halt them
Thus, some percentage of the time in round
robin acts no differently than FIFO
When I/O occurs in a process and it blocks
Round Robin Example
Assume a 50 msec time slice
Dispatch Order:  0, 1, 2, 3, 4, 0, 1, 2,  . . .
Process
Length
1st
2nd
3d
4th
5th
6th
7th
8th
Finish
Switches
0
350
0
250
475
650
800
950
1050
1100
7
1
125
50
300
525
550
3
2
475
100
350
550
700
850
1000
1100
1150
1275
10
1200
1250
3
250
150
400
600
750
900
900
5
4
75
200
450
475
2
4
1
3
0
1275
27
2
 
Average waiting time:
 
100 msec
 
First process completed:
 
475 msec
 
Comparing Round Robin to FIFO
 
Context switches:  27 vs. 5 for FIFO
Clearly more expensive
First job completed:  475 msec vs. 350 for
FIFO
Can take longer to complete first process
Average waiting time:  100 msec vs. 595 for
FIFO
For first opportunity to compute
Clearly more responsive
 
Choosing a Time Slice
 
Performance of a preemptive scheduler
depends heavily on how long the time slice is
Long time slices avoid too many context
switches
Which waste cycles
So better throughput and utilization
Short time slices provide better response time
to processes
How to balance?
 
Costs of a Context Switch
 
Entering the OS
Taking interrupt, saving registers, calling scheduler
Cycles to choose who to run
The scheduler/dispatcher does work to choose
Moving OS context to the new process
Switch stack, non-resident process description
Switching process address spaces
Map-out old process, map-in new process
Losing instruction and data caches
Greatly slowing down the next hundred instructions
 
Multi-Level Feedback Queue
(MLFQ) Scheduling
 
One time slice length may not fit all processes
Create multiple ready queues
Short time (foreground) tasks that finish quickly
 
Short but frequent time slices, optimize response time
Long time (background) tasks that run longer
 
Longer but infrequent time slices, minimize overhead
Different queues may get different shares of the
CPU
Finds balance between good response time and
good turnaround time
 
How Do I Know What Queue To
Put New Process Into?
 
If it’s in the wrong queue, its scheduling
discipline causes it problems
Start all processes in short time queue
Move to longer queue if too many time-slice ends
Move back to shorter queue if too few time slice
ends
Processes dynamically find the right queue
If you also have real time tasks, you know
where they belong
Start them in real time queue and don’t move them
 
 
Multiple Queue Scheduling
 
ts
max
 = ∞
real time queue
ts
max
 = 500us
short time queue
ts
max
 = 2ms
medium time queue
ts
max
 = 5ms
long time queue
share
scheduler
 
20%
 
50%
 
25%
 
05%
 
What Benefits Do We
Expect From MLFQ?
 
Acceptable response time for interactive jobs
Or other jobs with regular external inputs
It won’t be too long before they’re scheduled
But they won’t waste CPU running for a long time
Efficient but fair CPU use for non-interactive jobs
They run for a long time slice without interruption
Predictable real time response
Based on known percentage of CPU
Dynamic and automatic adjustment of scheduling
based on actual behavior of jobs
 
Priority Scheduling Algorithm
 
Sometimes processes aren’t all equally
important
We might want to preferentially run the more
important processes first
How would our scheduling algorithm work
then?
Assign each job a priority number
Run according to priority number
 
Priority and Preemption
 
If non-preemptive, priority scheduling is just
about ordering processes
Much like shortest job first, but ordered by
priority instead
But what if scheduling is preemptive?
In that case, when new process is created, it
might preempt running process
If its priority is higher
Priority Scheduling Example
Process
Length
0
350
1
125
2
475
Priority
10
30
40
0
200
 
Process 3’s priority is lower than
running process
 
Process 4’s priority is higher than
running process
300
 
Process 4 completes
4
375
 
So we go back to process 2
550
 
Time
 
Problems With Priority Scheduling
 
Possible 
starvation
Can a low priority process 
ever
 run?
If not, is that really the effect we wanted?
May make more sense to adjust priorities
Processes that have run for a long time have
priority temporarily lowered
Processes that have not been able to run have
priority temporarily raised
 
Hard Priorities Vs. Soft Priorities
 
What does a priority mean?
That the higher priority has absolute
precedence over the lower?
Hard priorities
That’s what the example showed
That the higher priority should get a larger
share of the resource than the lower?
Soft priorities
 
Priority Scheduling in Linux
 
Each process in Linux has a priority
Called a 
nice 
value
A soft priority describing share of CPU that a
process should get
Commands can be run to change process
priorities
Anyone can request lower priority for his
processes
Only privileged user can request higher
 
Priority Scheduling in Windows
 
32 different priority levels
Half for regular tasks, half for soft real time
Real time scheduling requires special privileges
Using a multi-queue approach
Users can choose from 5 of these priority
levels
Kernel adjusts priorities based on process
behavior
Goal of improving responsiveness
Slide Note
Embed
Share

Operating system scheduling involves making decisions on resource allocation among multiple clients, determining who gets to use the resource next and for how long. Different scheduling algorithms aim to achieve specific goals, such as maximizing throughput, minimizing waiting time, ensuring fairness, and meeting priority objectives. The process queue maintains a list of processes ready to run, ordered based on the scheduling algorithm in use.


Uploaded on Sep 12, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Operating System Principles: Scheduling CS 111 Operating Systems Harry Xu Lecture 4 Page 1 CS 111 Winter 2020

  2. Outline What is scheduling? What are our scheduling goals? What resources should we schedule? Example scheduling algorithms and their implications Lecture 4 Page 2 CS 111 Winter 2020

  3. What Is Scheduling? An operating system often has choices about what to do next In particular: For a resource that can serve one client at a time When there are multiple potential clients Who gets to use the resource next? And for how long? Making those decisions is scheduling Lecture 4 Page 3 CS 111 Winter 2020

  4. OS Scheduling Examples What job to run next on an idle core? How long should we let it run? In what order to handle a set of block requests for a disk drive? If multiple messages are to be sent over the network, in what order should they be sent? We ll primarily consider scheduling processes Lecture 4 Page 4 CS 111 Winter 2020

  5. How Do We Decide How To Schedule? Generally, we choose goals we wish to achieve And design a scheduling algorithm that is likely to achieve those goals Different scheduling algorithms try to optimize different quantities So changing our scheduling algorithm can drastically change system behavior Lecture 4 Page 5 CS 111 Winter 2020

  6. The Process Queue The OS typically keeps a queue of processes that are ready to run Ordered by whichever one should run next Which depends on the scheduling algorithm used When time comes to schedule a new process, grab the first one on the process queue Processes that are not ready to run either: Aren t in that queue Or are at the end Lecture 4 Page 6 CS 111 Winter 2020

  7. Potential Scheduling Goals Maximize throughput Get as much work done as possible Minimize average waiting time Try to avoid delaying too many for too long Ensure some degree of fairness E.g., minimize worst case waiting time Meet explicit priority goals Scheduled items tagged with a relative priority Real time scheduling Scheduled items tagged with a deadline to be met Lecture 4 Page 7 CS 111 Winter 2020

  8. Different Kinds of Systems, Different Scheduling Goals Time sharing Fast response time to interactive programs Each user gets an equal share of the CPU Batch Maximize total system throughput Delays of individual processes are unimportant Real-time Critical operations must happen on time Non-critical operations may not happen at all Lecture 4 Page 8 CS 111 Winter 2020

  9. Preemptive Vs. Non-Preemptive Scheduling When we schedule a piece of work, we could let it use the resource until it finishes Or we could interrupt it part way through Allowing other pieces of work to run instead If scheduled work always runs to completion, the scheduler is non-preemptive If the scheduler temporarily halts running work to run something else, it s preemptive Lecture 4 Page 9 CS 111 Winter 2020

  10. Pros and Cons of Non-Preemptive Scheduling +Low scheduling overhead +Tends to produce high throughput +Conceptually very simple Poor response time for processes Bugs can cause machine to freeze up If process contains infinite loop, e.g. Not good fairness (by most definitions) May make real time and priority scheduling difficult Lecture 4 Page 10 CS 111 Winter 2020

  11. Pros and Cons of Pre-emptive Scheduling +Can give good response time +Can produce very fair usage +Good for real-time and priority scheduling More complex Requires ability to cleanly halt process and save its state May not get good throughput Possibly higher overhead Lecture 4 Page 11 CS 111 Winter 2020

  12. Scheduling: Policy and Mechanism The scheduler will move jobs into and out of a processor (dispatching) Requiring various mechanics to do so Part of the scheduling mechanism How dispatching is done should not depend on the policy used to decide who to dispatch Desirable to separate the choice of who runs (policy) from the dispatching mechanism Also desirable that OS process queue structure not be policy-dependent Lecture 4 Page 12 CS 111 Winter 2020

  13. Scheduling the CPU yield (or preemption) context switcher ready queue CPU dispatcher resource manager resource granted resource request new process Lecture 4 Page 13 CS 111 Winter 2020

  14. Scheduling and Performance How you schedule important system activities has a major effect on performance Performance has different aspects You may not be able to optimize for all of them Scheduling performance has very different characteristic under light vs. heavy load Important to understand the performance basics regarding scheduling Lecture 4 Page 14 CS 111 Winter 2020

  15. General Comments on Performance Performance goals should be quantitative and measurable If we want goodness we must be able to quantify it You cannot optimize what you do not measure Metrics ... the way & units in which we measure Choose a characteristic to be measured It must correlate well with goodness/badness of service Find a unit to quantify that characteristic It must a unit that can actually be measured Define a process for measuring the characteristic That s enough for now But actually measuring performance is complex Lecture 4 Page 15 CS 111 Winter 2020

  16. How Should We Quantify Scheduler Performance? Candidate metric: throughput (processes/second) But different processes need different run times Process completion time not controlled by scheduler Candidate metric: delay (milliseconds) But specifically what delays should we measure? Time to finish a job (turnaround time)? Time to get some response? Some delays are not the scheduler's fault Time to complete a service request Time to wait for a busy resource Lecture 4 Page 16 CS 111 Winter 2020

  17. Other Scheduling Metrics Mean time to completion (seconds) For a particular job mix (benchmark) Throughput (operations per second) For a particular activity or job mix (benchmark) Mean response time (milliseconds) Time spent on the ready queue Overall goodness Requires a customer specific weighting function Often stated in Service Level Agreements (SLAs) Lecture 4 Page 17 CS 111 Winter 2020

  18. An Example Measuring CPU Scheduling Process execution can be divided into phases Time spent running The process controls how long it needs to run Time spent waiting for resources or completions Resource managers control how long these take Time spent waiting to be run This time is controlled by the scheduler Proposed metric: Time that ready processes spend waiting for the CPU Lecture 4 Page 18 CS 111 Winter 2020

  19. Typical Throughput vs. Load Curve Maximum possible capacity ideal throughput typical offered load Lecture 4 Page 19 CS 111 Winter 2020

  20. Why Dont We Achieve Ideal Throughput? Scheduling is not free It takes time to dispatch a process (overhead) More dispatches mean more overhead (lost time) Less time (per second) is available to run processes How to minimize the performance gap Reduce the overhead per dispatch Minimize the number of dispatches (per second) This phenomenon is seen in many areas besides process scheduling Lecture 4 Page 20 CS 111 Winter 2020

  21. Typical Response Time vs. Load Curve typical Delay (response time) ideal offered load Lecture 4 Page 21 CS 111 Winter 2020

  22. Why Does Response Time Explode? Real systems have finite limits Such as queue size When limits exceeded, requests are typically dropped Which is an infinite response time, for them There may be automatic retries (e.g., TCP), but they could be dropped, too If load arrives a lot faster than it is serviced, lots of stuff gets dropped Unless you re careful, overheads explode during periods of heavy load Lecture 4 Page 22 CS 111 Winter 2020

  23. Graceful Degradation When is a system overloaded ? When it is no longer able to meet its service goals What can we do when overloaded? Continue service, but with degraded performance Maintain performance by rejecting work Resume normal service when load drops to normal What should we not do when overloaded? Allow throughput to drop to zero (i.e., stop doing work) Allow response time to grow without limit Lecture 4 Page 23 CS 111 Winter 2020

  24. Non-Preemptive Scheduling Scheduled process runs until it yields CPU Works well for simple systems Small numbers of processes With natural producer consumer relationships Good for maximizing throughput Depends on each process to voluntarily yield A piggy process can starve others A buggy process can lock up the entire system Lecture 4 Page 24 CS 111 Winter 2020

  25. Non-Preemptive Scheduling Algorithms First come first served Shortest job next We won t cover this in detail Real time schedulers Lecture 4 Page 25 CS 111 Winter 2020

  26. First Come First Served The simplest of all scheduling algorithms Run first process on ready queue Until it completes or yields Then run next process on queue Until it completes or yields Highly variable delays Depends on process implementations All processes will eventually be served Lecture 4 Page 26 CS 111 Winter 2020

  27. First Come First Served Example Dispatch Order 0, 1, 2, 3, 4 Process 0 1 2 3 4 Total Duration 350 125 475 250 75 1275 Start Time 0 350 475 950 1200 End Time 350 475 950 1200 1275 Average wait 595 595 Note: Average is worse than total/5 because four other processes had to wait for the slow-poke who ran first. Lecture 4 Page 27 CS 111 Winter 2020

  28. When Would First Come First Served Work Well? FCFS scheduling is very simple It may deliver very poor response time Thus it makes the most sense: 1. When response time is not important (e.g., batch) 2. In embedded (e.g., telephone or set-top box) systems Where computations are brief And/or exist in natural producer/consumer relationships Lecture 4 Page 28 CS 111 Winter 2020

  29. Real Time Schedulers For certain systems, some things must happen at particular times E.g., industrial control systems If you don t rivet the widget before the conveyer belt moves, you have a worthless widget These systems must schedule on the basis of real-time deadlines Can be either hard or soft Lecture 4 Page 29 CS 111 Winter 2020

  30. Hard Real Time Schedulers The system absolutely must meet its deadlines By definition, system fails if a deadline is not met E.g., controlling a nuclear power plant . . . How can we ensure no missed deadlines? Typically by very, very careful analysis Make sure no possible schedule causes a deadline to be missed By working it out ahead of time Then scheduler rigorously follows deadlines Lecture 4 Page 30 CS 111 Winter 2020

  31. Ensuring Hard Deadlines Must have deep understanding of the code used in each job You know exactly how long it will take Vital to avoid non-deterministic timings Even if the non-deterministic mechanism usually speeds things up You re screwed if it ever slows them down Typically means you do things like turn off interrupts And scheduler is non-preemptive Typically you set up a pre-defined schedule No run time decisions Lecture 4 Page 31 CS 111 Winter 2020

  32. Soft Real Time Schedulers Highly desirable to meet your deadlines But some (or any) of them can occasionally be missed Goal of scheduler is to avoid missing deadlines With the understanding that you miss a few May have different classes of deadlines Some harder than others Need not require quite as much analysis Lecture 4 Page 32 CS 111 Winter 2020

  33. What If You Dont Meet a Deadline? Depends on the particular type of system Might just drop the job whose deadline you missed Might allow system to fall behind Might drop some other job in the future At any rate, it will be well defined in each particular system Lecture 4 Page 33 CS 111 Winter 2020

  34. What Algorithms Do You Use For Soft Real Time? Most common is Earliest Deadline First Each job has a deadline associated with it Based on a common clock Keep the job queue sorted by those deadlines Whenever one job completes, pick the first one off the queue Prune the queue to remove missed deadlines Goal: Minimize total lateness Lecture 4 Page 34 CS 111 Winter 2020

  35. Example of a Soft Real Time Scheduler A video playing device Frames arrive From disk or network or wherever Ideally, each frame should be rendered on time To achieve highest user-perceived quality If you can t render a frame on time, might be better to skip it entirely Rather than fall further behind Lecture 4 Page 35 CS 111 Winter 2020

  36. Preemptive Scheduling Again in the context of CPU scheduling A thread or process is chosen to run It runs until either it yields Or the OS decides to interrupt it At which point some other process/thread runs Typically, the interrupted process/thread is restarted later Lecture 4 Page 36 CS 111 Winter 2020

  37. Implications of Forcing Preemption A process can be forced to yield at any time If a more important process becomes ready Perhaps as a result of an I/O completion interrupt If running process s importance is lowered Perhaps as a result of having run for too long Interrupted process might not be in a clean state Which could complicate saving and restoring its state Enables enforced fair share scheduling Introduces extra context switches Not required by the dynamics of processes Creates potential resource sharing problems Lecture 4 Page 37 CS 111 Winter 2020

  38. Implementing Preemption Need a way to get control away from process E.g., process makes a sys call, or clock interrupt Consult scheduler before returning to process Has any ready process had its priority raised? Has any process been awakened? Has current process had its priority lowered? Scheduler finds highest priority ready process If current process, return as usual If not, yield on behalf of current process and switch to higher priority process Lecture 4 Page 38 CS 111 Winter 2020

  39. Clock Interrupts Modern processors contain a clock A peripheral device With limited powers Can generate an interrupt at a fixed time interval Which temporarily halts any running process Good way to ensure that runaway process doesn t keep control forever Key technology for preemptive scheduling Lecture 4 Page 39 CS 111 Winter 2020

  40. Round Robin Scheduling Algorithm Goal - fair share scheduling All processes offered equal shares of CPU All processes experience similar queue delays All processes are assigned a nominal time slice Usually the same sized slice for all Each process is scheduled in turn Runs until it blocks, or its time slice expires Then put at the end of the process queue Then the next process is run Eventually, each process reaches front of queue Lecture 4 Page 40 CS 111 Winter 2020

  41. Properties of Round Robin Scheduling All processes get relatively quick chance to do some computation At the cost of not finishing any process as quickly A big win for interactive processes Far more context switches Which can be expensive Lecture 4 Page 41 CS 111 Winter 2020

  42. Round Robin and I/O Interrupts Processes get halted by round robin scheduling if their time slice expires If they block for I/O (or anything else) on their own, the scheduler doesn t halt them Thus, some percentage of the time in round robin acts no differently than FIFO When I/O occurs in a process and it blocks Lecture 4 Page 42 CS 111 Winter 2020

  43. Round Robin Example Assume a 50 msec time slice Length Process 1st Finish 2nd 3d 4th 5th 6th 7th 8th Switches 0 0 350 7 1100 0 250 475 650 800 950 1050 1 1 125 3 550 50 300 525 2 2 475 10 1275 1150 1200 1250 350 550 700 850 1000 1100 100 3 3 250 5 900 400 600 750 900 150 4 4 75 2 475 1275 200 450 27 Average waiting time: 100 msec First process completed: 475 msec Lecture 4 Page 43 CS 111 Winter 2020

  44. Comparing Round Robin to FIFO Context switches: 27 vs. 5 for FIFO Clearly more expensive First job completed: 475 msec vs. 350 for FIFO Can take longer to complete first process Average waiting time: 100 msec vs. 595 for FIFO For first opportunity to compute Clearly more responsive Lecture 4 Page 44 CS 111 Winter 2020

  45. Choosing a Time Slice Performance of a preemptive scheduler depends heavily on how long the time slice is Long time slices avoid too many context switches Which waste cycles So better throughput and utilization Short time slices provide better response time to processes How to balance? Lecture 4 Page 45 CS 111 Winter 2020

  46. Costs of a Context Switch Entering the OS Taking interrupt, saving registers, calling scheduler Cycles to choose who to run The scheduler/dispatcher does work to choose Moving OS context to the new process Switch stack, non-resident process description Switching process address spaces Map-out old process, map-in new process Losing instruction and data caches Greatly slowing down the next hundred instructions Lecture 4 Page 46 CS 111 Winter 2020

  47. Multi-Level Feedback Queue (MLFQ) Scheduling One time slice length may not fit all processes Create multiple ready queues Short time (foreground) tasks that finish quickly Short but frequent time slices, optimize response time Long time (background) tasks that run longer Longer but infrequent time slices, minimize overhead Different queues may get different shares of the CPU Finds balance between good response time and good turnaround time Lecture 4 Page 47 CS 111 Winter 2020

  48. How Do I Know What Queue To Put New Process Into? If it s in the wrong queue, its scheduling discipline causes it problems Start all processes in short time queue Move to longer queue if too many time-slice ends Move back to shorter queue if too few time slice ends Processes dynamically find the right queue If you also have real time tasks, you know where they belong Start them in real time queue and don t move them Lecture 4 Page 48 CS 111 Winter 2020

  49. Multiple Queue Scheduling 20% real time queue tsmax= 50% short time queue tsmax = 500us share scheduler 25% medium time queue tsmax = 2ms 05% long time queue tsmax = 5ms Lecture 4 Page 49 CS 111 Winter 2020

  50. What Benefits Do We Expect From MLFQ? Acceptable response time for interactive jobs Or other jobs with regular external inputs It won t be too long before they re scheduled But they won t waste CPU running for a long time Efficient but fair CPU use for non-interactive jobs They run for a long time slice without interruption Predictable real time response Based on known percentage of CPU Dynamic and automatic adjustment of scheduling based on actual behavior of jobs Lecture 4 Page 50 CS 111 Winter 2020

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#