Transcript Scheduling Algorithms

Scheduling Algorithms



A computer system has limited resources that must be
shared among the processes competing for those
resources.
The operating system must insure that resources are
assigned to processes in fair and reasonable way.
This is the problem of scheduling.

Scheduling occurs at many levels, and are handled by
various OS components called schedulers.

Most scheduling is performed on the behalf of processes.

As processes move from state to state they are under
the influence of scheduling.
Process scheduling involves deciding which process to select,
when multiple processes are waiting for service.
In general, Scheduling can occur at 3 different levels:
Long-term (job scheduling): determining which jobs to admit into the
system as processes
Short-term (CPU scheduling): determining which process will be given
control of the CPU next. Performed by two modules: the scheduler and
the dispatcher.
Medium term (storage scheduling): determining which of the
processes will be active, occupying memory, and which processes will
become inactive and have their memory swapped to disk.
Begin
execution
termination
I/O bound
termination
CPU bound
It’s important to maintain a good process mix.
termination
Wait in the “job pool” for initial entry into the system
Long Term
Scheduler (job scheduler)
moves
process into the active set
Active
(Running)
S
H
O
R
T
Active
(Ready, Blocked)
T
E
R
M
S
C
H
E
D
U
L
I
N
G
Long Term
Process terminates
M
E
D
I
U
M
Inactive
(suspended
)
T
E
R
M
S
C
H
E
D
U
L
I
N
G
Scheduler (job scheduler)
and exits the system
INITIAL
New process is ready to run
Time quantum expires
READY
Process swapped
back into memory
CPU assigned
RUNNING
Terminate
when
complete
Event occurs or
resource available
Waiting for
event or
resource
SUSPENDED
READY
Event occurs or
resource available
BLOCKED
Waiting for long term
event
TERMINAL
Abort due to error
SUSPENDED
BLOCKED
Time Limits – that affect scheduling

Processor time quantum (time slice)

Storage time quantum

Job time limit
BATCH
INTERACTIVE
REAL-TIME
Job admission based on
characteristics and
resource needs.
Sessions and processes
normally accepted
unless capacity reached.
Processes either permanent or
accepted at once
MEDIUM-TERM
Usually none. Jobs remain in
storage until done.
Processes swapped on rotating
basis when necessary,
using storage time
quantum.
Processes never swapped or
suspended.
SHORT-TERM
Processes scheduled by
priority. They usually
continue until they wait
voluntarily, request
service or are
terminated.
Processes scheduled on a
rotating basis. They
continue until service is
requested or processor
time quantum expires.
Optional preemption
Scheduling based on strict
priority with immediate
preemption. Optional
time sharing among
equal priority processes.
LONG-TERM
Scheduling Objectives

Strategies used for scheduling decisions vary widely at each level.






Throughput: If the CPU and resources are busy being used then work is being
accomplished. The goal is to perform as much work as possible in a given time
period. This is a measure of the number of processed completed per time unit.
Turnaround: Goal is to complete jobs as soon as possible. This is the interval
from the time of submission to the time of completion. It is the sum of all of the
time periods spent waiting (in the ready queue, in resource queues, waiting to
enter memory) and time executing.
Response: Goal (particularly for interactive processes) is to process individual
requests as quickly as possible.
Fairness: Goal is to treat each process (or job) in a way that corresponds “fairly”
with its characteristics. Essentially process should be given an opportunity to
execute.
Consistency: Goal is to treat processes with the same characteristics predictably.
Resource Use: Goal is to keep each category of resource used as fully as
possible.
Measuring scheduling objectives

We can evaluate how successfully a scheduling algorithm meets its goals by
observing the queues waiting for service or resources. Some of the specific
properties we consider are:



Waiting time: A CPU scheduling algorithm only affects how long a process
spends waiting in the ready queue. (not how long it will execute, or how long it
must wait for resources).
Queue Length: this measures the size of the queues of waiting processes. We
want to minimize queue length to conserve storage.
Response Ration: This is a measure of waiting time balanced against the
service time required for each request: R=W/(W+S) Where “W” is the waiting
time, and “S” is the service time. A consistent response ration means that better
service is being given to shorter processes, which is usually considered fair.

Priorities




Preemption



Priority is used to represent the relative importance of
a process in the system.
Priorities aid the schedulers in making quick decisions
Dynamic vs. Static priorities
In a non-preemptive scheduling strategy, a process is
assigned the processor until it voluntarily gives it up.
In a preemptive strategy, a high-priority may be given
the processor immediately even though a lower or
equal priority process is currently running.
Overhead

This is a performance penalty associated with context
switching.
CPU Scheduling of Batch Processes




Submitted with a good estimate of their
resource needs, via job control statements
Upper limits the OS is expected to enforce
Generally expected that the OS will give
preferential treatment to processes with
lower resource needs.
Resource estimates may also include the
specification of an initial priority for a job
For batch processes
scheduling occurs at 2 levels:
Long-term and short term
Job Scheduling (long term)


Job scheduling involves deciding which job (job
step) to admit into the system as a process. A
job is a program which has been submitted to
the system, but which has not been loaded into
memory.
Initial resource estimates play an important role
of scheduling at the job level. A job can not be
loaded until sufficient resources are available
A “Job”
1) typically consists of multiple steps
2) Job control statements provide information about the resource
needs of each step. Including program to execute, maximum memory
requirements, and cpu time limits, and user information
3) Waiting jobs are stored in one or more job queues, ordered by
priority or class, which is determined by their announced resource
needs.
4) System processes called initiators, examine the job queues and
selects jobs when the system is ready for more work.
5) Jobs are admitted only when sufficient resources are available to
begin the first “step”. Also each additional step is admitted only when
resources are available.
6) Once a step has been admitted, it holds all of its resources until it is
complete. A timer is set to ensure that it does not exceed its planned
processor time.
Short term scheduling


When the processor (CPU) is available, a
process from the ready queue(s) is
selected according to some type of
algorithm.
The process is then given control of the
CPU and continues running until:





The process terminates
The process voluntarily suspends itself
(sleep)
The process requests an I/O transfer or
other service for which it must wait
The process is stopped because it has
exceeded its processor time quantum
(maximum CPU time for the entire job, or
step!)
IF preemption is allowed: a higher priority
process becomes ready. (preemption is
usually not used in a batch environment.)
Batch CPU Scheduling Algorithms
examples of scheduling algorithms used later in this presentation were taken from
“Operating System Concepts”, by Silberschatz, Galvin, Gagne
Please note: On the following slides, all
estimates of average waiting time of a
process is based on the following
assumptions:


Processes complete their computations in a
single burst of CPU activity with no I/O
No time is added to perform context switches
P2
P3
P1
Next to dispatch
F
tail
I
Jobs would be executed in the order received. P1 would be executed
followed by P3, followed by P2. The wait time of any particular
process is entirely dependent upon the processes in front of it, and is
often quite long. Lets assume the length of the CPU-burst time (in
milliseconds) for each of process above is:
F
O
head
Process
Burst time
P1
P3
P2
24
3
3
Then the wait time for P1 is 0 milliseconds, 24
milliseconds for P3 and 27 milliseconds for P2. The
average wait time is (0+24+27)/3 or 17
milliseconds. However if they arrived in the order
P2, P3, then P1, the average wait time would be (0
+ 3 + 6)/3 or 3 milliseconds
There is an underlying assumption that all
processes complete their activity in a single CPU
burst.
Static priority scheduling:
Multiple Ready queues
Priority 3
Priority 1
P2
P3
P1
Processes are executed in a FIFO order based on priority. In this
example the order P2, P1, P3. If another priority 3 process would
enter the system it would be executed before any remaining jobs in
the priority 1 queue.. In static priority methods the priority of a
process does NOT change.
P1
P2
P3
=====wait===------execute------ done
==---execute----- done
=============wait======---execute----- done
Shortest Job Next





Priority is based on the total expected
running time of the process
Expected running time may be adjusted if
the process waits or is suspended after a
CPU burst
Gives favorable treatment to SHORT jobs
Shortest average waiting time: waiting is
concentrated in a few long processes
Can lead to starvation!
If we have the following set of processes, with arrive in the following order,
and with the length of expected CPU usage in milliseconds:
Process
Expected
Cpu Time
needed
Wait time
P1
P2
P3
P4
100
24
10
35
69
10
0
34
The average waiting
time would be:
(0+10+34+69)/4
= 28 milliseconds
If these jobs had been executed in a FIFO order their wait time would be:
p2 -100, p3 – 124, p4 – 134 with an average of (0+100+124+134)/4 or
89 milliseconds!!!!!
Dynamic Priority Scheduling


Priority of a process can be increased
while it waits
Aging is the technique used to adjust
process priority



A fixed increment is added to the priority of
each waiting process
Processes which have waited a long time will
develop higher and higher priorities
Ensures that all waiting processes will be
served in a reasonable time
Preemptive scheduling



Higher priority processes get immediate
service.
A process that is preempted is returned to
the ready queue, and possibly it’s priority
is adjusted.
Well known example is: Shortest
Remaining Time Next!
Assume that the following 4 processes arrive at the listed arrival times, and with the CPU burst time
of:
Process
Arrival time
CPU Burst time
P1
0
8
P2
1
4
P3
2
9
P4
3
5
All times are in milliseconds
P1 arrives at time 0, and begins processing since it is the only process in the ready queue. At time 1,
P2 arrives its CPU burst time is 4 which is less that the remaining time for P1 which is 7. P1 is
preempted, and P2 begins execution. At time 2, P3 arrives, it’s CPU burst time is 9 which is greater
than the remaining time for P2, which is 3, so P2 continues. At time 3, P4 arrives with a CPU burst time
of 5. This is larger than the remaining time for P2 (which is 2) so P2 is allowed to complete.
Next, we compare the remaining CPU burst time for P1, P3, and P4. P1 has a remaining time of 7, P3
has a time of 9, and P4 has a time of 5. If no other processes arrive in the system, P4 is selected next
for execution, followed by P1, and then finally P3. The average wait time for these 4 processes is:
P1
0
P2
1
P4
5
P1
10
((10-1) + (1-1)+(17-2)+(5-3))/4 = 26/4 = 6.5
The number subtracted represents the arrival time of the process
P3
17
Scheduling Interactive Processes





Expected to perform computations in response
to requests made by the user.
Requests require short bursts of service
Interactive session may be one process which
executes a succession of programs
Or Each new request can create a new process
Typically nothing is known about their resource
needs.
Levels of scheduling


Few long-term scheduling decisions, as
long as resources permit, processes are
immediately admitted into the system
Medium-term scheduling:





Maintains a set of “active” processes.
Makes use of a storage time quantum (PCB)
Counter is reduced by the running and waiting
time the process consumes
When expired the process is swapped to disk
Ranges from a few seconds to a few minutes

Medium cont.

Inactive processes are selected for
readmission based on:
Its assigned priority
 Time in the inactive group
 Storage requirements.


Short-Term scheduling:

May select jobs based on priority or their
order of entry in the “ready” queue.

Short term cont….


Preemption may be allowed
Makes use of a Processor Time quantum
Maximum amount of time a process can control
the CPU without being interrupted.
 If the time quantum expires before the process
voluntarily gives up the CPU it is interrupted, and
another process given control of the CPU
 Typical values range from 100 milliseconds to
several seconds.
 Using a time quantum to share the processor is
called time slicing

Round Robin




Scheduling method designed especially for
interactive processes.
Ready processes are maintained in a
simple FIFO queue, all processes have the
same priority.
Each process is assigned a time quantum
When the processor becomes available it
is assigned to the process at the front of
the queue.
Ready queue
P2
P3
tail
P1
head
Place on end of queue
P1
--------===========--------=============
P2
=====--------===========--------======
P3
==========--------===========---------
------ represents run and ====== represents wait
Run

Average wait time can become quite long!
If the 3 processes above all arrived at time 0, and with expected CPU burst
times of:
Process
CPU burst time
P1
24
P2
3
P3
3
If we use a time quantum of 4 milliseconds, the P1 gets the first 4 milliseconds,
and is preempted. P2 does not need the full time and terminates. P3 also
does not need the full time. Finally, P1 gets another turn for an additional
time quantum.
No process receives more than one time quantum without being
interrupted. Even if P1 is the only process in the queue, it will be
interrupted and placed back on the queue, when its time quantum is
exhausted. If there are n processes then each process must wait a
maximum of (n-1)*q
Priority methods




We can also apply the “round robin” method to a
set of processes with assigned priorities!
Ready queue is maintained in priority order (or
separate queues for each priority)
Sometimes a process which exceeds its time
quantum is assigned a lower priority
Different priority processes have different time
quanta
Ready queue
P9
P4
P1
P6
P2
Priority 5
Time 12
Priority 10
Time 8
Priority 10
Time 8
Priority 15
Time 4
Priority 15
Time 4
Tail
Head
RUN
Feedback queues




This algorithm gives more favorable service to
I/O bound algorithms
Multi-level queue scheduling algorithm, based on
priority
Priority of processes that use up successive time
quanta is gradually reduced
Each time a process is stopped for exceeding it’s
time quanta, it is moved to a lower priority!
Queue 0,
quantum=8
Queue 1, quantum
= 10
P5
P3
P12
P4
P6
P2
Queue 2, quantum
= 12
Feedback Queues
P7
P1
Selfish Scheduling Algorithm
Entrance Priority
Waiting Queue
4
7
12
6
1
3
Scheduling Priority
Move process to active
queue
12
12
12
1
3
3
Active Queue
Dispatch processes using some standard algorithm
Scheduling Real-time Processes



There is no long-term scheduling. Most
processes are permanent. Dynamically created
processes are admitted immediately.
There is no storage scheduling. All processes
remain active and resident in main memory at
all times
Strict priority based scheduling is used. Usually
high –priority processes can preempt those of
lower priorities. However, processes can lock
themselves to block preemption. (typically
preemption occurs only when a system call is
complete or an I/O block occurs)



Real-time processes are trusted. They may
control each other, and they may influence the
overall scheduling algorithm. They may be
allowed to change the priority of other
processes, if that process must complete before
the real-time process can run. (perhaps the
lower priority process is modifying data needed
by the real-time process) This ability is known as
priority inversion.
The maximum resource needs of real-time
processes are usually known.
Optional timesharing is supported within priority
groups. (time slicing) This may be enabled or
disabled by any process



Processes may be scheduled to run
periodically at specific intervals, or to be
started in response to certain events.
Processes may be required to complete an
activity by a specific deadline.
Processes may create micro processes or
threads and schedule these privately
within their allotted time.