Transcript ITFN 2601 Introduction to Operating Systems

ITFN 2601
Introduction to Operating
Systems
Lecture 4
Scheduling
Agenda
Scheduling
Batch
Interactive
Real-Time
Threads
Scheduling: When
New Process is Created
Parent Process
Child Process
Process Exits
When a process blocks
I/O Interrupt occurs
Clock Interrupts
Non-preemptive
Preemptive
Objectives of a Good
Scheduling Policy
Fairness
Efficiency
Low response time (important for
interactive jobs)
Low turnaround time (important for
batch jobs)
High throughput
Scheduling
Throughput
The amount of useful work accomplished per unit time. This
depends, of course, on what constitutes “useful work.” One
common measure of throughput is jobs/minute (or second, or
hour, depending on the kind of job)
Utilization
For each device, the utilization of a device is the
fraction of time the device is busy. A good
scheduling algorithm keeps all the devices (CPUs,
disk drives, etc.) busy most of the time.
Scheduling
 Turnaround
The length of time between when the job arrives in the system
and when it finally finishes
 Response Time
The length of time between when a job arrives in the system
and when it starts to produce output. For interactive jobs,
response time might be more important than turnaround.
 Wait Time
The amount of time the job is ready (runnable but not running).
This is a better measure of scheduling quality than turnaround
since the scheduler has no control of the mount of time the
process spends computing or blocked waiting for I/O.
Preemption
Needs a clock interrupt (or equivalent)
Needed to guarantee fairness
Found in all modern general purpose
operating systems
Without preemption, the system
implements “run to completion (or
yield)”
Scheduling Algorithms
(Batch)
FIFO (First In First Out)
Fairest
Low throughput
High Turnaround
Shortest First
High Throughput
Low Turnaround
Unfair for Large Jobs
Scheduling Algorithms
(Batch, cont)
Shortest Remaining
High Turnaround on Long Jobs
Unfair for Large Jobs
Multi-Scheduling (CPU or Memory Limited)
HIGH Turnaround (disk swaps)
Throughput highly variable, probably low
Fairness highly variable
First-Come First-Served
The simplest possible scheduling
discipline is called First-come, firstserved (FCFS). The ready list is a simple
queue (first-in/first-out). The scheduler
simply runs the first job on the queue
until it blocks, then it runs the new first
job, and so on. When a job becomes
ready it is simply added to the end of the
queue.
FCFS
Main advantage of FCFS is that it is easy
to write and understand
No starvation
If one process gets into an infinite loop, it
will run forever and shut out all the
others
FCFS tends to excessively favor long
bursts. CPU-bound processes
Shortest Job First (SJF)
Whenever the CPU has to choose a burst
to run, it chooses the shortest one
Non-preemptive policy
Preemptive version of the SJN, called
shortest remaining time first
Starvation is possible
Scheduling Algorithms
(Interactive)
Round Robin
Fairest overall
Response time variable but finite
Priority Scheduling
Fair
“More Fair” for users with higher priorities
Response time inverse to priority
Round-Robin
Round-robin (RR). RR keeps all the
processes in a queue and runs the first
one, like FCFS. After a length of time q
(called quantum), if the current burst
hasn’t completed, it is moved to the tail of
the queue and the next process is started
Round Robin
An important preemptive policy
Essentially the preemptive version of FCFS
The key parameter is the quantum size q
When a process is put into the running state, a
timer is set to q
If the timer goes off and the process is still
running, the OS preempts the process.
The process is moved to the ready state
The next job in the queue is selected to run
Round Robin
Quantum can’t be too large
Quantum can’t be too small
What quantum should we choose
Tradeoff
Small q makes system more responsive
Large q makes system more efficient since
there’s less switching
Round Robin, Example
Priority Scheduling
Always run the highest priority process
Preemptive or non-preemptive
Priorities can be assigned externally to
processes based on their importance
Assigned (and changed) dynamically
Other Interactive Scheduling
Multiple Queues
Shortest Process Next
Guaranteed Scheduling
Lottery Scheduling
Fair-Share Scheduling
Scheduling Algorithms
(Interactive, cont)
Multi-Quantized
Response time proportionate to quanta
More bookkeeping
Shortest Process Next
Estimation of process length
Unfair for large jobs
Fast response for small jobs
Scheduling Algorithms
(Interactive, cont)
Guaranteed Scheduling
Lottery Scheduling
Alotted time proportional to Job
Size/Importance
Sharing
Fair by user, not necessarily fair by job
Responses become disproportionate
Scheduling Algorithms
(Real-Time)
Small Jobs
High Priority
Periodic/Aperiodic
Schedulable?
Iff the sum of the ratios CPU Time to Period
time is less than one
Sum(CPU/Period) <= 1
Static/Dynamic?
Scheduler Mechanism
Some processes are intrinsically more
important at some times than others
Time-dependent response
High-priority request
How can a process raise it’s scheduling
priority?
Thread Scheduling
User-level threads
Process has a Thread Scheduler
Same concept as Process Scheduler
Conflicts with Process Scheduling
Kernel Level Threads
Kernel has Thread and Process Scheduler
Two Quanta’s
Thread Quanta
Process Quanta
Summary
Scheduler responsible for many goals
Scheduling algorithms complex
Know your math!