Scheduling: Introduction
Previous Chapter : How to switch blu processes >
-
context switch mechanism
current chapter : When to switch bl processes >
-
scheduling policies.
Early Enses 1940-1950s) : A queue of jobs (on punch cards , tapes
would arrive at the machine room.
-
computers ran one job at a time.
-the operator decided the job order.
-
CPU idle during 1/0
Even though the term CPU scheduling wasn't used yet the ,
act of choosing which job runs next is fundamentally the
same decision modern of schedulers make.
-
only now, it's automated faster, and more
complex
,
What are the factors to keep in mind, while developing a
scheduling
policy
.
Assumptions
an the workload (like, duration arrival time, etc.)
,
-
what metrics to optimize ? (maximize utilization) musiisize
response tinse etc.) .
what the about the processes ?
are
assumptions
.
1 Each job runs for the same amount of time.
.
2 All jobs arrive at the same time.
.
3 Once started ,
each job runs completion.
to its
.
4 All jobs only use the CPU (it- no 10)
5
. The run-time of each job is known
The above assumptions are unrealistic and we will get rid of each of
them are by one.
which are the metrics that we are interested in
optimizing ?
turnaround time
*
Average
*
Average response turse
the turnaround time ofjob is defined as the time at which the
a
job completes minus the time at which the job arrived in the system.
i .,
Eurnaround =
Tcompletion -
Taxiral
By Assumption 2 , we have Tarrival = o
=>> under these apumptions , Turnaround =
Tcompletion
eduling policies
1) First In , First out (FIFO
eg : this is a
typical serving policy in the
grocery stores-
Imaglise three jicbs say
,
A, B, andC arrive in the system
around the time. (1
same Tarrival 0), and each job
., =
runs for 10 seconds.
average turnaround time for
What would be the these
jobs in #IFO
A B C
Tcomp (A) = 10
m
-
Tcomp(B) = 20
80 100 120
Tcomp(c) = 30
turnaround time =
=>
average + 20 + 30 = 20
3 -
Rex assumption 1 and use the sameFito strategy-
-
i ., each job need not have the same running time .
3 jobs A, B, and c where A runs for 100 seconds while B and <
eg!-
runs for 10 each
C
! -
Tcomp(a) = 100
, Tcomp(B) = 110
,
Tcomp(a) = 120
average turnaround
bad !
=>
-
= 110 , which is pretty
-
the above problems is
generally referred to as convoy effect, where a
number of relatively short potential consumers of a resource get queued
behind a heavyweight resource consumer.
How to overcome this problems?
Grocery stores adapts the idea of "ten-items-orless"
to deal convey effect-
our next scheduling strategy is inspired by this idea-
(2) Shortest Job First (SJF)
Recall the previous example , 3 jobs A, B, and c where A runs for 100
seconds I
while Bandc runs for 10 each sir works as follows.
=
T
comp(B) = 10
Tromp(B) = 20
Tcomp (A) = 120
average turnaround
=
+ 20120 = 50
,
3
good improvement
which is a !
Now what if we need to relax Assumption
? 2
, -
u .,
every job need not start at the same time as
well !
let us
modify the previous example . This fire let A arrives at t = o
and needs to run for 100 seconds where as Band C arrive at t =
10 and
,
each need to run for 10 seconds. Then SJF waks as follows :
rad-
= 100
Turn around (B) = 110-10 = 100
0 = 10
=> average
turnaround =
5
310 = 103 3 seconds
.
;
which is also pretty bad !
So what to do now ? > -
Relax
-
Assumption 3
li ., jobs need not run to umpletion.
In particular using tiser interrupt and context
,
switching mechanisms ,
add preemption to SJF the new version
·
is called
13) PreemptiveShortest Job First (PSJF)
or shortest Tirise to Completion First (STCF).
i When a new enters the system :
job
- determine which of the remaining jobs Including the new job) has
the least time left , and schedules that one .
the above the scheduler A Band
now
&
in
example ,
can
stop when C
arrive.
arrival of B and .
C
At
=> Turnaround (A) = 120 -
0 =
120
i
C
Turnaround (B) = 20-10 = 10
Turnaround (C) = 30-10 = 20
=> average turnaround
10 50 seconds
=
# 10+20 = =
,
3
3
which is better than SJF .
A STCF is a great policy for turnaround time (under the assumptions)
necessary
A metric
response time
new :
-
- --
terminal and demand
-
In time
sharing systems ,
users would sit at a
interactive performance from the system as .
well
Note that STCF and related previous policies are not
for
particularly good time
response
-
Tresponse =
Tfinstrum -
Tarrival
Lie
,
time from when the job arrives in a system to the
first time it is scheduled)
three jobs arrive at the same time, the third lob
Even in STCF
, If
has to wait for the previous jobs to run in their
entirety before being
scheduled just once.
=> bad response time and .
interactivity
Question: How can we build a scheduler that is sensitive to response time ?
(4) Round Robin (RR) (also known as time
slicing scheduling
A Run a job for a twise slice and then switch to the next job in
the run
queue until the jobs are finished.
sometimes called .
A time slice is a
scheduling quantum
* It
repeatedly does so until the jobs are finished.
A the length of the time slice must be a multiple of the tier-interrupt
period .
Forexample suppose the jobs A B and c
, , ,
arrive at the same time in
the system and each of them wish to
,
run for 5 seconds.
what does an SJF scheduler do ?
A
response time (A)
m
=> = 0
response time (B) = 5
10
response time (C) =
seconds
average response te
H
=
=
5
In contract to above RR with a time slice ofI second would cycle
through jobs quickly. response time (A)
0 =
response time (B) = 1
T
response time (c) = 2
fire 1
, which
average response =
Es great !
What is the biggest challenge i RR ?
&
The length of the time slice is critical !
shorter time slice=> > better response time
but the cost of context switching will dominate overall performance
longer time slice = > amortize the cost of switching
but wase response time.
Deciding on the length of the time slice presents a trade-off to a system
In fact, RR with a reasonable time slice, is an excellent
designer .
scheduler if response time is our
only metric.
But , what about the metric turnaround time
Tarrival (A) Tarrival (B) Tarrival (C) 0
T
=
=
=
=> Turnaround (A) Tromp (A) 13
=
=
Turnaround (B) =
Tcmp (B) =
14
Turnaround (C) =
Tcomp(C) = 15
=> average turnaround =
14 , which is
pretty awful !
RR is fair, but performs poorly on metrics such as turnaround time.
to summarize
,
under the current assumptions (4 and 5)
Sick > optivities turnaround time but bad time
response
-
RR >
-
optisizes response time ,
but bad turnaround time.
Reling mption
4
ie ., jobs can also perform No-
IncorporatingIQ
eg: -Let A and B be two processes such that A andB need 50ms of
CPU tre each.
= A runs for 10ms and then issues an 10 request
-
No each takes 10 ms
and performs 10
-B
simply uses the CPU for zoms no
the scheduler runs A first then B after.
,
we intend to build Sick scheduler .
o
Disk
........
O 20 40 60 so 100 120140
A better approach is as follows :
treat each 10 ms sub-job of A as an independent job-
-
-thus , at the beginning the choice is blu 10ms A or a zoms B
.
STCF clearly choose 10 ms A
-
when A initiates to request, job A is blocked waiting I
for
- Thus scheduler schedules .
B completion
When the 10 completes ,
an interrupt is raised, the os moves A from
blocked to
ready and again make a choice.
A B A B A B AB A B
r
Disic
11 . 11 / 11
O 20 40 60 so 100 120140
