Transcript Week 9 Resource Management I

ADVANCED
OPERATING SYSTEMS
Lecture 7 (Week 9)
Resource Management – I
(Process Scheduling)
by:
Syed Imtiaz Ali
1
What is Process Scheduling?
• In a multiprogrammed enviornment, multiple
processes or threads competing for the CPU
at the same time.
• This situation occurs whenever two or more
of them are simultaneously in the ready
state.
• If only one CPU is available, a choice has to
be made which process to run next.
• Part of operating system that makes choice is
scheduler, and algorithm is scheduling
algorithm.
2
Introduction to Scheduling (1)
• Process scheduling does not matter much
on simple PCs
• When we turn to networked servers, the
situation changes appreciably.
• Here multiple processes often do compete
for the CPU, so scheduling matters.
– For example, when the CPU has to choose
between running a process that gathers the
daily statistics and one that serves user
requests, the users will be a lot happier if the
latter gets first crack at the CPU.
3
Introduction to Scheduling (2)
• The scheduler also has to worry about:
1. Picking the right process to run
2. Making efficient use of the CPU
• because process switching is expensive.
• During process switching following
activities occur:
– Switch from user mode to kernel mode
– State of the current process must be saved
– New process must be selected by running the
scheduling algorithm.
– New process must be started.
4
Process Behavior (1)
• Bursts of CPU usage alternate with periods of I/O wait
a) a CPU-bound process
b) an I/O bound process
5
Process Behavior (2)
• Nearly all processes alternate bursts of
computing with (disk) I/O requests
• Typically the CPU runs for a while without
stopping, then a system call is made to read
from a file or write to a file.
• When the system call completes, the CPU
computes again until it needs more data or
has to write more data, and so on.
• I/O in this sense is when a process enters
the blocked state waiting for an external
device to complete its work.
6
Process Behavior (3)
• Nearly all processes alternate bursts of
computing with (disk) I/O requests
• Typically the CPU runs for a while without
stopping, then a system call is made to read
from a file or write to a file.
• When the system call completes, the CPU
computes again until it needs more data or
has to write more data, and so on.
• I/O in this sense is when a process enters
the blocked state waiting for an external
device to complete its work.
7
When to take a Scheduling Decision? (1)
• There are a variety of situations in which
scheduling decision is needed.
• First, when a new process is created:
– a decision needs to be made whether to run the
parent process or the child process.
• Since both processes are in ready state, the
scheduler can legitimately choose to run either the
parent or the child next.
• Second, when a process exits:
– That process can no longer run (since it no
longer exists), so some other process must be
chosen from the set of ready processes.
» Continue
8
When to take a Scheduling Decision? (2)
• Third, when a process blocks on I/O:
– another process has to be selected to run.
– reason for blocking plays a role in the choice.
• For example, if A is an important process and it is
waiting for B to exit its critical region, letting B run
next will allow it to exit its critical region and thus
let A continue.
• Fourth, when an I/O interrupt occurs:
– It is up to the scheduler to decide to run the:
• newly ready process
• process that was running at the time of the interrupt
(if the interrupt occurs to exit from I/O)
• some third process.
9
Non-preemptive Scheduling
• This algorithm picks a process to run and then
just lets it run until:
– it blocks (either on I/O or waiting for another
process)
– it voluntarily releases the CPU.
• In effect, no scheduling decisions are made
during clock interrupts.
• After clock interrupt processing has been
completed, the process that was running
before the interrupt is resumed, unless a
higher-priority process was waiting for a nowsatisfied timeout.
10
Preemptive Scheduling
• Preemptive scheduling algorithm picks a
process and lets it run for a maximum of some
fixed time.
• If it is still running at the end of the time
interval, it is suspended and the scheduler
picks another process to run
• Doing preemptive scheduling requires, a clock
interrupt at the end of the time interval to give
control of the CPU back to the scheduler.
• If no clock is available, nonpreemptive
scheduling is the only option.
11
Categories of Scheduling (1)
• In different environments different scheduling
algorithms are needed.
– Different application areas have different
goals.
– What the scheduler should optimize for is
not the same in all systems.
• Three environments worth distinguishing are:
1. Batch.
2. Interactive.
3. Real time.
12
Categories of Scheduling (2)
Batch & Interactive Systems
• In batch systems, there are no users
impatiently waiting at their terminals for a
quick response to a short request.
– Nonpreemptive algorithms, or preemptive
algorithms with long time periods for each
process, are often acceptable.
– This approach reduces process switches and thus
improves performance.
• In interactive systems, preemption is essential
to keep one process from hogging the CPU
and denying service to the others.
13
Categories of Scheduling (3)
Real-Time Systems
• In systems with real-time constraints,
preemption is not needed
– Processes know that they may not run for long
periods of time and usually do their work and
block quickly.
• The difference with interactive systems is that
real-time systems run only programs that are
intended to further the application at hand.
– Interactive systems are general purpose and may
run arbitrary programs that are not cooperative or
even malicious.
14
Scheduling Algorithm Goals
15
Scheduling in Batch Systems (1)
First-Come First-Served(1)
• The simplest of all scheduling algorithms is
non-preemptive first-come first-served.
• There is a single queue of ready processes.
• When first job enters, it is started immediately
and allowed to run as long as it wants to.
– As other jobs come in, they are put onto the end
of the queue.
• When the running process blocks, the first
process on the queue is run next.
– Once blocked process is ready, like a newly
arrived job, it is put on the end of the queue.
16
Scheduling in Batch Systems (2)
First-Come First-Served(2)
• The strength of this algorithm is that it is:
– easy to understand
– easy to program
• With this algorithm, a single linked list keeps
track of all ready processes.
• Picking a process to run just requires
removing one from the front of the queue.
• Adding a new job or unblocked process just
requires attaching it to the end of the queue.
17
Scheduling in Batch Systems (3)
First-Come First-Served(3)
• A powerful disadvantage.
– Suppose that there is:
• many l/O-bound processes that use CPU for 1 msec but
each have to perform 1000 disk reads to complete.
• one compute-bound process that runs for 1 sec/time
– The compute-bound process runs for 1 sec, then it
reads a disk block.
• All the I/O processes now run and start disk reads.
– When the compute-bound process gets its disk
block, it runs for another 1 sec, followed by all the
I/O-bound processes in quick succession. >>Continue
18
Scheduling in Batch Systems (4)
First-Come First-Served(4)
• The net result is that each I/O-bound process
gets to read 1 block per second and will take
1001 sec to finish.
• With a scheduling algorithm that preempted
the compute-bound process every 10 msec,
the I/O-bound processes would finish in 11
sec instead of 1001 sec, and without slowing
down the compute-bound process very much.
19
Scheduling in Batch Systems (5)
Shortest Job First (1)
• Another non-preemptive batch algorithm that
assumes the run times are known in advance.
• When several equally important jobs are
sitting in the input queue waiting to be started,
the scheduler picks the shortest job first.
20
Scheduling in Batch Systems (6)
Shortest Job First (2)
• Look at Figure:
– Four jobs A, B, C, and D with run times of 8,4,4,
and 4 minutes, respectively.
• By running them in that order, the turnaround
time for:
– A is 8 minutes
– C is 16 minutes
– B is 12 minutes
– D is 20 minutes
An average of 14 minutes.
21
Scheduling in Batch Systems (7)
Shortest Job First (3)
• Now let us consider running these four jobs
using shortest job first, as shown in Fig. (b).
• The turnaround times are now 4, 8, 12, and 20
minutes for an average of 11 minutes.
• Shortest job first is only optimal when all the
jobs are available simultaneously.
22
Scheduling in Batch Systems (8)
Shortest Remaining Time Next
• With this algorithm:
– Scheduler always chooses the process whose
remaining run time is the shortest.
• The run time has to be known in advance.
• When a new job arrives, its total time is
compared to current process' remaining time.
– If new job needs less time to finish than current
process, it is suspended and new job started
• This scheme allows new short jobs to get
good service.
23
Scheduling in Interactive Systems (1)
Round-Robin Scheduling (1)
• One of the most widely used algorithms
• Each process is assigned a time interval,
called its quantum
– If the process is still running at the end of the
quantum, the CPU is preempted and given to
another process.
– If the process has blocked or finished before the
quantum has elapsed, the CPU switching is done
24
Scheduling in Interactive Systems (2)
Round-Robin Scheduling (2)
• Round robin is easy to implement.
– All the scheduler needs to do is maintain a list
– When the process uses up its quantum, it is put on
the end of the list
a) list of runnable processes
b) list of runnable processes after B uses up its quantum
25
Scheduling in Interactive Systems (3)
Round-Robin Scheduling (3)
• Issue with round robin is length of quantum
• Switching from one process to another
requires a certain amount of time
– Suppose that process switch takes 1 msec,
– Suppose that the quantum is set at 4 msec.
• After doing 4 msec of useful work, CPU will
have to spend 1 msec on process switching.
• 20% of the CPU time will be thrown away on
administrative overhead (this is too much)
26
Scheduling in Interactive Systems (4)
Round-Robin Scheduling (4)
• To improve the CPU efficiency:
– we could set the quantum to, say, 100 msec.
– Now the wasted time is only 1%.
• But consider what happens on a server system if
50 requests come in within a very short time
– They will be put on list of runnable processes.
– If the CPU is idle, the first one will start immediately,
the second one may not start until 100 msec later, and
so on.
• With short quantum they may have better service.
27
Scheduling in Interactive Systems (5)
Round-Robin Scheduling (5)
• The conclusion can be formulated as
follows:
– setting the quantum too short causes too
many process switches and lowers the
CPU efficiency
– setting it too long may cause poor
response to short interactive requests.
• A quantum around 20-50 msec is often
a reasonable compromise.
28
Scheduling in Interactive Systems (6)
Priority Scheduling (1)
• Round-robin scheduling thinks that all
processes are equally important.
• The need to take external factors into
account leads to priority scheduling.
• The basic idea is straightforward:
– each process is assigned a priority, and runnable
process with highest priority is allowed to run.
– E.g. sending electronic mail has lower priority
than a video film in real time.
29
Scheduling in Interactive Systems (7)
Priority Scheduling (2)
• To prevent high-priority processes from
running indefinitely:
– the scheduler decreases the priority of the currently
running process at each clock tick.
– Alternatively, each process may be assigned a
maximum time quantum that it is allowed to run.
• When this quantum is used up, the next highest
priority process is given a chance to run.
• Priorities can be assigned to processes
statically or dynamically.
30
Scheduling in Interactive Systems (8)
Priority Scheduling (3)
• It is often convenient to group processes into
priority classes and use priority scheduling
among the classes but round-robin
scheduling within each class.
• Figure shows a system with four priority
classes.
31
Scheduling in Interactive Systems (8)
Priority Scheduling (3)
• The scheduling algorithm is as follows:
– In presence of runnable processes in priority class
4, just run each one for one quantum, round-robin
fashion.
– If priority class 4 is empty, then run the class 3
processes round robin.
– If classes 4 and 3 are both empty, then run class 2
round robin, and so on.
• If priorities are not adjusted occasionally,
lower priority classes may all starve to death.
32
Scheduling in Real-Time Systems (1)
• A real-time system is one in which time
plays an essential role.
– For example, the computer in a compact disc
player gets the bits as they come off the drive
and must convert them into music within a very
tight time interval.
– If the calculation takes too long, the music will
sound peculiar.
• Other real-time systems are:
– patient monitoring in a hospital ICU
– the autopilot in an aircraft
– robot control in an automated factory.
33
Scheduling in Real-Time Systems (2)
Real-time systems ate generally categorized as:
1. Hard real time:
– there are absolute deadlines that must be met, or else
2. Soft real time:
– missing an occasional deadline is undesirable, but
nevertheless tolerable.
• In both, real-time behavior is achieved by
dividing program into a number of processes
– When an external event is detected, it is job of the
scheduler to schedule the processes in such a way
that all deadlines are met.
34
Scheduling in Real-Time Systems (3)
• The events that a real-time system may have to
respond to can be further categorized as:
1. Periodic (occurring at regular intervals)
2. Aperiodic (occurring unpredictably).
• If in a periodic real time systems
– Given
• m periodic events
• event i occurs within period Pi and requires Ci seconds
– Then the load can only be hand if
m
Ci
1

i 1 Pi
– A real-time system that meets this criterion is said
to be schedulable.
35
Scheduling in Real-Time Systems (4)
• As an example, consider soft real-time system:
– Periodic events, m = 3
– These periods have 100, 200, and 500 msec
– these events require 50, 30, and 100 msec of CPU
time per event, respectively,
• Is this system is schedulable?
– Yes! because 50/100 + 30/200 + 100/500 =
0.5 + 0.15 + 0.2 < 1.
• If a fourth event with a period of 1 sec is added,
system schedulable as long as this event does not
need more than 150 msec of CPU time per event.
36
Scheduling in Real-Time Systems (5)
• Real-time scheduling algorithms can be:
1. Static
•
It makes their scheduling decisions before the
system starts running.
2. Dynamic
• It makes their scheduling decisions at run time.
• Static scheduling only works when there is:
– information available in advance about the work to
be done and the deadlines that have to be met.
• Dynamic scheduling algorithms do not have
these restrictions.
37