Scheduling

Scheduling

scheduling: share CPU among processes

scheduling should:
– be fair

all processes must be similarly affected

no indefinite postponement
– “aging” as a possible solution

adjust priorities based on waiting time for resource

– max. possible no of processes per unit time

– reduce response time for interactive users

Scheduling Scheduling Criteria

– priorities should be used
I/O bound

– if critical resources exist: run processes using
CPU bound
those first so that the resources become available
quickly
interactive / batch
– not fail even under very heavy load
importance of quick response

e.g. accept no new processes to system
priority

e.g. lower quantum

real execution time

time to completion

Scheduling Priorities

preemptive x non-preemptive scheduling
static x dynamic priorities

preemptive
static priorities
– fixed during execution
– high cost of context switching
– easy to implement
– to be effective, there must be a sufficient amount – not efficient
of processes ready to run in memory

dynamic priorities
– change based on environment changes
– harder to implement + more CPU time
– enhances response times

1
Scheduling Example Scheduling Techniques

Process Time of Service
Deadline scheduling

Arrival Time – order processes based on their ending times
1 0 3
useless if process is not completed on time
2 2 6 – process must declare all resource requests
3 4 4 beforehend

may not be posible
4 6 5
– plan resource allocation based on ending times
5 8 2

new resources may become available

Scheduling Techniques Example: FIFO Scheduling

FIFO scheduling
– simplest technique
– order based on arrival times 5
0 10 15 20
– non-preemptive
– processes with short service times wait unnecessarily
because of processes requring long service times 1

ineffective for interactive processes

response times may be too long 2
– ineffective for I/O bound proceses

I/O ports may be available while the process waits for a CPU 3
bound process to complete
4
⇒ FIFO usually used together with other techniques
5

Scheduling Techniques Scheduling Techniques

– selection of quantum is critical

Round-Robin schedulling
has effect on performance of system
– FIFO-like – short x long
– assign CPU to processes for fixed time units in turn – fixed x variable
– same x different for each user
– preemptive

if too long quantum ⇒ becomes FİFO
– quantum = time slice

if too short quantum ⇒ too much time for context switches
– if not completed within quantum: move to end of queue
correct quantum sizes different for different types of systems
– effective for interactive processes
– has context switching

2
 Example: Round-Robin Scheduling Scheduling Techniques

shortest-job-first scheduling
5
0 10 15 20 – non-preemptive
– order based on shortest time to completion
– decreased average waiting times compared to FIFO
1 – better service for short jobs
2 – not suitable for interactive processes
– total running time must be known beforehand
3

user provides estimate
4
– if requires more than estimate, stop process and run later
5
if jobs repeat, may know running time

Example: Shortest-Job-First
Schedulling Scheduling Techniques

shortest time remaining

– preemptive version of previous technique
0 5 10 15 20
good performance for time-sharing systems
– run process with least time remaining to completion

consider new arrivals too
1
a running process may be preempted by a new, short process
2 – total running time must be known beforehand
3 – more time wasted
4
used / remaining time calculations
5
context switching

Example: shortest time remaining Scheduling Techniques

Multilevel queues
0 5 10 15 20
level 1
FIFO
CPU
1
level 2
FIFO
2
3 level 3
FIFO
4
5
level n
(round-robin)

3
Scheduling Techniques Scheduling Techniques

– processes at higher level queues finished before

– new process to end of level 1 those in lower levels can be run
– FIFO within levels – a running process may be preempted by a
– if not completed within quantum, go to end of process arriving to a higher level
lower level – in some systems stay in same queue for a few
– limited no of levels rounds
– in last level, round-robin instead of FIFO
e.g. at lower level queues
– short, new jobs completed in a short time
– in some systems, longer quantum at lower levels

Example: Multilevel Queues Scheduling in UNIX Systems

0 5 10 15 20

Assumption: Max 3 levels in system.

Scheduling in UNIX Systems Example:

Priority = CPU_usage + nice + base
Assume only 3 processes

base=60
CPU_usage = ∆T/2
no nice value

clock interrupts system 60 times per quantum

start with the order Process A, B and C

4
 Process A Process B Process C
Time Priority Cpu Count Priority Cpu Count Priority Cpu Count

0 60 0 60 0 60 0
1
2
|
60
1 75 30 60 0 60 0
1
2
|
60
2 67 15 75 30 60 0
1
2
|
60
3 63 7 67 15 75 30
8
9
|
67
4 76 33 63 7 67 15

Priority = (CPUusage/2) + 60