Operating Systems Lecture Notes
8 February 2012 • Scheduling
Outline
Scheduling mechanisms.
Scheduling strategy.
Eviction and selection strategies.
Implementation details.
Examples
The Story So Far
A system accepts processes and runs them until they're done.
The system and processes should behave in desirable ways.
Processes should move through the system as quickly as possible.
All parts of the system should be busy all the time.
Promises
The operating system magically multiplies system facilities.
Threads and the virtual CPU.
The operating system provides an imaginary environment for processes.
An isolated process running in its own system.
The operating system provides dials a process uses to manipulate its environment.
The Problem
How should the system and processes be managed to behave properly?
How should the operating system fulfill its promises?
How should the conflict between the previous two questions be resolved?
The
scheduler
plays a large part in answering these questions.
A Simple Solution
The simplest possible answer to these questions is to admit one process at a time.
The scheduler admits the next waiting process.
The process in the system executes until it's done.
Is this a solution? Is it a good solution?
Analysis
The simple solution
solves some problems (virtual machines),
doesn't solve some problems (system utilization), and
is unclear on some problems (abstract CPUs).
A more detailed analysis requires sharper criteria.
Scheduler Criteria
Schedulers can be judged by how they effect
overall system performance and
individual process performance.
Other, larger criteria (efficiency, convenience, protection).
Schedulers can also be judged on less (or non-) functional criteria.
How well a scheduler supports other OS abstractions.
Process Performance Measurements
Service time
is the amount of time needed to complete process execution.
Wait time
is the time between process entry and first process execution.
Turnaround time
is the time between first execution and last execution.
Response time
is the time between IO completion and execution in response.
Process Measures Example
The one-at-a-time scheduler does well on all process performance measurements.
Wait and response times are zero.
Service and turnaround times are equal.
That's just ducky. Or is it?
System Performance Measures
Throughput
is the number jobs per second.
High throughput is good.
Utilization
is the system-busy percentage.
High utilization is good.
An average of individual process measures.
High average responsiveness or low average turnaround.
System Measures Example
The one-at-a-time scheduler provides poor utilization and poor throughput.
Poor throughput is perhaps less obvious than poor utilization.
But it depends on the processes.
If processes use everything, then utilization is good.
If processes are minimal and simple, then throughput is good.
Conflicts Abound
System and process criteria often conflict.
The good of the many vs. the good of the few.
Criteria within a category also frequently conflict.
Simple vs omnivorous processes and system criteria.
Schedulers (and operating systems) usually represent these conflicts; they don't resolve them.
Trade-Offs
Schedulers (and operating systems) usually can't resolve conflict.
Resolution requires strong (or arbitrary) assumptions.
Instead, represent trade-offs as dials in the scheduler (and operating system).
More informed parties set the dials to trade-off as appropriate.
Performance tuning, for example.
Understanding Trade-offs
Lots of good knowledge is necessary for
representing trade-offs well, and
making good trade-offs.
Processes are central to both system and process trade-offs.
Understanding processes and their behavior becomes important.
Process States
Processes lead a simple life.
Blocked
: a process is unable run.
Running
: the process is in the CPU.
Ready
: the process can run, but isn't in the CPU.
Process Execution
From the state diagram, processes spend their lives running and not running.
Not running includes blocked and ready.
A process could be not running for many reasons.
But usually it's blocked waiting for a resource.
Process Behavior
Process behavior can be ordered along an activity continuum.
The continuum extremes are
Compute-bound
and
IO-bound
computations.
Simple Scheduling Redux
The simple process model shows how one-at-a-time scheduling fails systems:
Letting in more than one process at a time improves system throughput.
Without effecting (too much) system performance.
But Wow
What does a many-process scheduler have to do?
Figure out which processes to admit.
Figure out when to admit them.
And most importantly, figure out how to recover from the mistakes that will inevitably occur.
And figure out how to make fewer, less severe mistakes.
Scheduling Illustrated
Scheduling Levels
There are at least four levels of scheduling possible:
Admission (long-term, job) scheduling.
System (mid-term, process) scheduling.
Device (short-term) scheduling.
Thread scheduling.
There’s lots of other scheduling going on.
Disk-arm scheduling.
Simplifications
Ignore (mostly) admission and system scheduling.
Concentrate on the CPU device scheduler.
And on the thread scheduler, somewhat.
The device scheduler works with processes.
Thread = process, for the most part.
Scheduler Classification
Schedulers can be classified along two dimensions:
When they evict the running process: the
eviction algorithm
.
How they select the next running process:
selection algorithm
.
Each choice of an eviction and selection algorithm leads to a scheduler.
Eviction Algorithms
No eviction algorithm: the scheduler never evicts a running process.
Actual eviction algorithms fall into two categories:
Absolute: eviction is well defined, sorta.
Relative: eviction depends on other entities, usually processes.
No Eviction
Non-preemptive schedulers
don't evict (or preempt) processes.
Easy to implement.
Misbehaving processes are a problem.
The OS may provide tools for
cooperative scheduling
yield()
- Move from CPU to ready queue.
swap(id)
- Swap places with the identified process.
Absolute Eviction
Quantum schedulers
evict running processes at regular intervals.
Defining “regular” can be tricky.
The
quantum
gives the interval size in time.
Quantum size is an important dial in schedulers and OSs.
Premature eviction can also usually occur.
Via cooperative scheduling, or obvious eviction points.
Relative Eviction
Priority schedulers
evict processes to maintain a
priority invariant
.
Each process is assigned a comparable value called a
priority
.
Priority assignment is another important dial.
The
priority invariant
constrains running process relative to the waiting process.
For example, the running process priority is no less than any waiting process priority.
Hybrid Eviction
It's possible to combine various eviction algorithms into a new algorithm.
A quantum priority scheduler, for example.
Combine various versions of the same eviction algorithm.
Have short-, medium-, and long-quantum processes.
But now processes have to be assigned to versions.
Selection Algorithms
Once a process leaves the CPU, which process gets next crack?
Order the waiting processes into a queue.
The queue head is the next process.
Similar to eviction, queue ordering can be relative or absolute.
No selection (a set of waiting processes) is possible but...
Absolute Selection
Absolute scheduling imposes a strict (more or less) queue ordering on waiting processes.
New processes join at the tail, waiting processes leave at the head.
Queued processes may leave, when canceled, for example.
Relative Selection
Relative selection uses the (or perhaps a) priority to order waiting processes.
The queue becomes a priority queue.
Any process satisfying the priority invariant is selected next.
Hybrid Selection
When several processes satisfy the priority invariant, which one is selected?
Absolute and relative selection are frequently combined in the same algorithm.
Strictly queue same-priority processes.
Or could rely on a secondary priority.
A selection algorithm often contains several versions of the same selection algorithm.
Queues for high, medium, or low priority processes.
First Come First Serve Scheduling
Processes gain the CPU in the order they entered the system.
Treat the ready queue as a queue.
Usualy no eviction algorithm
FCFS Analysis
FCFS selection is easy to implement.
A strict queue and a simple selection algorithm.
Entry time is a weak property; other, more important properties are ignored.
Except for “queue fairness,” FCFS selection is unlikely to provide useful results.
Shortest Job Next Scheduling
Each process declares its expected compute time.
Order the ready queue by increasing compute time.
Select the head of the queue.
This is the process with the shortest estimated execution time.
SJN Analysis
SJN minimizes average wait time.
All the processes in front of you have the smallest possible execution times.
Large duration jobs may be starved.
Accurate job-duration estimates are hard to make.
Round Robin Scheduling
Strict queue-order selection, any eviction algorithm.
Evicted processes go to the end of the queue.
With voluntary eviction, this is equivalent to FCFS scheduling.
Single Scheduler Problems
What happens when selection produces several candidate processes?
Several processes with the same priority, or job time, or deadline.
One scheduler can’t meet all process expectations.
And those that try get complicated quickly.
An OS may support multiple process classes.
Foreground and background processes, for example.
Multi-Scheduler Systems
Using two or more schedulers can solve these problems.
At an increase in complexity and scheduling overhead.
Multiple schedulers often uses multiple ready queues.
On scheduler can move processes between queues.
Summary
Schedulers manage process flow through and within a system.
Schedulers comprise evection and selection algorithms.
Different choices of each lead to different schedulers.
There are many schedulers in a system, and the all (should) coordinate to provide good management.
This page last modified on 2012 February 8.