Transcript Ceng 334 - Operating Systems

Chapter 2.2 : Process Scheduling





Process concept 
Process scheduling
Interprocess communication
Deadlocks
Threads
1
Scheduling
 Select
process(es) to run on processor(s)
 Process state is changed from “ready” to
“running”
 The component of the OS which does the
scheduling is called the scheduler
2
Types of Scheduling



Scheduling is divided into various levels.
These levels are defined by the location of
the processes
A process can be
available to be executed by the processor
 partially or fully in main memory
 in secondary memory
 is not started yet

3
Types of Scheduling
 Long

Term Scheduling.
The decision to add to the pool of processes to be
executed.
 Medium

The decision to add to the process in main memory.
 Short

Term Scheduling.
The decision as to which process will gain the processor.
 I/O

Term Scheduling.
Scheduling.
The decision as to which process's I/O request shall be
handled by a device.
4
Scheduling Criteria





Fairness : each process should get a fair share
of the CPU
Efficiency: keep CPU 100% utilized
Response time : should be minimized for
interactive users
Turnaround : minimize batch turnaround
times
Throughput : maximize number of jobs
processed per hour
5
User-Oriented, Performance
Criteria
Criteria
Response Time
Turnaround Time
Deadlines
Aim
low response time,
maximum number of
interactive users
time between submission
and completion
maximise deadlines met
6
System-oriented, Performance
Criteria
Criteria
Aim
•Throughput
allow maximum number of jobs to complete
•Processor
maximise percentage of time processor is busy
utilisation
•Overhead
minimise time processor busy executing OS
7
System oriented, other criteria
Criteria
Aim
Fairness
treat processes the same avoid starvation
Enforcing Priorities
give preference to higher priority processes
Balancing Resources
keep the system resources busy
8
Important Factors
 I/O
boundedness of a process
 CPU boundedness of a process
 Is the process interactive or batch?
 Process priority
 Page fault frequency
 Preemption frequency
 Execution time received
 Execution time required to complete
9
Types of Scheduling
A scheduling algorithm is non-preemptive (run to
completion) if the CPU cannot be taken away by the
OS.
 A scheduling algorithm is preemptive if the CPU can be
taken away by the OS.
 Cooperative Scheduling is the scheduling algorithm used
by some operating systems (such as Windows versions
up to 95 in which processes relinquish the control of
CPU for some reason (I/O, waiting for some event etc.)

10
The Interrupting Clock
 The
OS sets the interrupting clock to
generate an interrupt at some specified future
time.
 This interrupt time is the process quantum.
 Provides reasonable response times and
prevents the system being held up by
processes in infinite loops.
11
Scheduling Algorithms
 FCFS
 Round
Robin
 Virtual Round Robin
 Priority
 Priority Classes
 Shortest Job First
 Shortest Remaining Time
 Highest Response Ratio Next
 Feedback Queues
12
FCFS (First Come First Serve)
 Implementation:
 As
each process becomes ready, it joins the
ready queue.
 When the current process finishes the oldest
process is selected next.
 Characteristics:
 Simple
to implement
 Nonpremptive
 Penalises short and I/O-bound processes
13
Round Robin (RR)
 Implementation:
 Processes
are dispatched FIFO. But are given a
fixed time on the CPU (quantum - time slice).
 Characteristics:
 Preemptive
 Effective
in time sharing environments
 Penalises I/O bound processes
14
Quantum Size
 Some
Options:
 Large
or small quantum
 Fixed or variable quantum
 Same for everyone or different
 If quantum is to large RR degenerates into
FCFS
 If quantum is to small context switching
becomes the primary job being executed
 A good guide is quantum should be slightly
larger than the time required for a typical
interaction
15
Virtual Round Robin (VRR)

A modification to the RR algorithm to remove
the bias towards CPU bound processes.
 Implementation:
 Two
“ready” queues, one called an AUX
queue for storing “completed” IO processes
 AUX queue has priority over READY queue
 IO processes only runs for remaining time
 Characteristics:
 Performance
studies indicate fairer than RR
16
Priority

Implementation:


Each process is assigned a priority and the
scheduler always selects the highest priority
process first
Characteristics:
High priority processes may run indefinitely, so
decrease the priority of these processes at regular
intervals
 Assign high priority to system processes with
known characteristics such as being I/O bound

17
Priority Classes
Priority Class 4
Highest
Priority Class 3
Priority Class 2
Priority Class 1
Lowest
18

Implementation:
Processes are grouped into priority classes
 Round Robin is used within a class
 When selecting process start with the highest
class. If the class is empty, use a lower class


Characteristics:

If priorities are not adjusted from time to time,
lower classes may starve to death
19
Shortest-Job-First (SJF)
 Sometimes
known as Shortest Process Next
(SPN)
 Implementation:
 The
process with the shortest expected
execution time is given priority on the
processor
20

Characteristics:
Nonpremptive
 Reduces average waiting time over FIFO
 Always
produces the minimum average
turnaround time
 Must know how long a process will run
 Possible user abuse
 Suitable for batch environments. Not useful in a
timesharing environment

21
Shortest Remaining Time (SRT)
 Preemptive
counterpart of SPN
 Implementation:
 Process
with the smallest estimated runtime to completion is run next
 A running process may be preempted by a
new process with a shorter estimate runtime
22

Characteristics:
 Still requires estimates of the future
 Higher overhead than SJF
 No additional interrupts are generated as in
RR
 Elapsed service times must be recorded
23
Highest Response Ratio Next
(HRRN)
 How
do you get around the problem of
Indefinite postponement?
 Implementation:
 Once
a job gets the CPU it runs it to completion
 The priority of a job is a function of the job's
service time and the time it has been waiting for
service
priority = (time waiting + service time) / service
time
24
 Characteristics:
 Nonpremptive
 Shorter
jobs still get preference over
longer jobs
 However aging ensures long jobs will
eventually gain the processor
 Estimation still involved
25
Feedback Queues
 Sometimes
called multi-level feedback queues
 Implementation:
There
is a network of ready queues
A new process enters at the top queue
Moves through the queue FIFO
26
 I/O
processes:
 If the job requires I/O before quantum
expiration it leaves the network and
comes back at the same level queue
 CPU bound processes:
 If the quantum expires first, the
process is placed on the next lower
queue
 This continues until it reaches the
bottom queue
27
 Dispatching:
A
process is only placed on the CPU if
all higher level queues are empty
 A running process is preempted by a
process arriving in a higher queue
 Processes from lower level queues
receive a larger quantum
 Modifications:
 In some systems processes can proceed
back up the network by becoming I/O
bound
28
A Scheduling Mechanism Should:
 Favour
short jobs
 Favour I/O bound jobs to get good I/O
device utilisation
 Determine the nature of a job and
schedule accordingly
29