Transcript Computer Network and Infrastructure

Uniprocessor Scheduling
Dr. E.C. Kulasekere
IT206 Operating Systems
Aim of Scheduling




Response time: The time it takes a system to react to a given
input.
Throughput: A measure of processor work. The number of
processes that are completed per unit time.
Processor efficiency: Or also known as the CPU utilization.
Other indices
 Turn around time: how long it took to complete processing a
process.
 Waiting time: The time spent in the waiting queue.
July 18, 2015
IESL-IT Part II - 2004
2
IT206 Operating Systems
Types of Scheduling
July 18, 2015
IESL-IT Part II - 2004
3
IT206 Operating Systems
July 18, 2015
IESL-IT Part II - 2004
4
IT206 Operating Systems
July 18, 2015
IESL-IT Part II - 2004
5
IT206 Operating Systems
Long-Term Scheduling





Determines which programs are admitted to the system for
processing
Controls the degree of multiprogramming
More processes, smaller percentage of time each process is
executed. This is the decision that the LT-scheduler will make.
In some sense this also limits the degree of multi programming.
The process mix is maintained by this scheduler.
July 18, 2015
IESL-IT Part II - 2004
6
IT206 Operating Systems
Medium-Term Scheduling



Part of the swapping function
Based on the need to manage the degree of multiprogramming
This process occurs based on the availability of system
resources. Less memory means the MT-scheduler is invoked
many times.
July 18, 2015
IESL-IT Part II - 2004
7
IT206 Operating Systems
Short-Term Scheduling



Known as the dispatcher
Executes most frequently
Invoked when an event occurs
 Clock interrupts
 I/O interrupts
 Operating system calls
 Signals
July 18, 2015
IESL-IT Part II - 2004
8
IT206 Operating Systems
Short-Tem Scheduling Criteria



The short term algorithms can be evaluated in two distinct
groups
 User oriented: where the criteria is looked at in from the
users point of view
 System oriented: where the criteria is based on the utilization
of the system resources.
User-oriented
 Response Time
 Elapsed time between the submission of a request until
there is output.
System-oriented
 Effective and efficient utilization of the processor
July 18, 2015
IESL-IT Part II - 2004
9
IT206 Operating Systems
Short-Term Scheduling Criteria …




Performance-related
 Quantitative
 Measurable such as response time and throughput
Not performance related
 Qualitative
 Predictability
Table 9.2
Note that all criteria in table 9.2 are inter dependent. For
example providing good response time may mean frequent task
switching, this increases the over head to the system thus
reducing the throughput of the system.
July 18, 2015
IESL-IT Part II - 2004
10
IT206 Operating Systems
Priorities



Scheduler will always choose a process of higher priority over
one of lower priority
Have multiple ready queues to represent each level of priority
Lower-priority may suffer starvation
 allow a process to change its priority based on its age or
execution history
July 18, 2015
IESL-IT Part II - 2004
11
IT206 Operating Systems
July 18, 2015
IESL-IT Part II - 2004
12
IT206 Operating Systems
July 18, 2015
IESL-IT Part II - 2004
13
IT206 Operating Systems
Decision Mode



Nonpreemptive
 Once a process is in the running state, it will continue until it
terminates or blocks itself for I/O
Preemptive
 Currently running process may be interrupted and moved to
the Ready state by the operating system
 Allows for better service since any one process cannot
monopolize the processor for very long
Table 9.3 gives the scheduling algorithms
July 18, 2015
IESL-IT Part II - 2004
14
IT206 Operating Systems
Process Scheduling Example
July 18, 2015
IESL-IT Part II - 2004
15
IT206 Operating Systems
First-Come-First-Served
(FCFS)
0
5
10
15
20
1
2
3
4
5


Each process joins the Ready queue
When the current process ceases to execute, the oldest process in the Ready
queue is selected
July 18, 2015
IESL-IT Part II - 2004
16
IT206 Operating Systems
First-Come-First-Served
(FCFS)


A short process may have to wait a very long time before it can
execute
Favors CPU-bound processes
 I/O processes have to wait until CPU-bound process
completes
 Note that the I/O bound processes have relatively short CPU
cycles.
 The total effect of this is called the convoy effect.
July 18, 2015
IESL-IT Part II - 2004
17
IT206 Operating Systems
Round-Robin
0
5
10
15
20
1
2
3
4
5


Uses preemption based on a clock
An amount of time is determined that allows each process to use the
processor for that length of time
July 18, 2015
IESL-IT Part II - 2004
18
IT206 Operating Systems
Round-Robin



Clock interrupt is generated at periodic intervals
When an interrupt occurs, the currently running process is
placed in the read queue
 Next ready job is selected
Known as time slicing
July 18, 2015
IESL-IT Part II - 2004
19
IT206 Operating Systems
Shortest Process Next
0
5
10
15
20
1
2
3
4
5



Nonpreemptive policy
Process with shortest expected processing time is selected next
Short process jumps ahead of longer processes
July 18, 2015
IESL-IT Part II - 2004
20
IT206 Operating Systems
Shortest Process Next



Predictability of longer processes is reduced
If estimated time for process not correct, the operating system
may abort it
Possibility of starvation for longer processes
July 18, 2015
IESL-IT Part II - 2004
21
IT206 Operating Systems
Shortest Remaining Time
0
5
10
15
20
1
2
3
4
5


Preemptive version of shortest process next policy
Must estimate processing time. Less overhead than RR but
since elapsed service time needs to be recorded this generates
a little bit of overhead.
July 18, 2015
IESL-IT Part II - 2004
22
IT206 Operating Systems
Highest Response Ratio Next (HRRN)
0
5
10
15
20
1
2
3
4

5
Choose next process with the lowest ratio
time spent waiting + expected service time
expected service time
July 18, 2015
IESL-IT Part II - 2004
23
IT206 Operating Systems
Feedback
0
5
10
15
20
1
2
3
4
5



If service time cannot be estimated, SPN, SRT, HRRN cannot be
used. Then to establish preference for shorter jobs we can use
feedback.
Penalize jobs that have been running longer
Newer shorter processes will be favored over longer older jobs.
July 18, 2015
IESL-IT Part II - 2004
24
IT206 Operating Systems
July 18, 2015
IESL-IT Part II - 2004
25
IT206 Operating Systems
Fair-Share Scheduling


In a multiuser system, the processes can be caregorized on user
based statistics. Now the criteria is not how one process
performs but how a class of processes associated with one user
application performs.
 User’s application runs as a collection of processes
(threads)
 User is concerned about the performance of the application
 Need to make scheduling decisions based on process sets
Eg. If a larger number of employees log onto a system from
department, we would like to see their performance degraded
rather than degrading of all user performance.
July 18, 2015
IESL-IT Part II - 2004
26
IT206 Operating Systems
July 18, 2015
IESL-IT Part II - 2004
27
IT206 Operating Systems
Traditional
UNIX Scheduling






The traditional Unix scheduling is primarily targeted at the time
sharing interactive environement we are so used too.
The scheduling algorithm is designed to provide a good
response time for interactive users while ensuring low priority
background jobs do not starve (?)
Multilevel feedback using round robin within each of the priority
queues. Users 1s preemption.
Priorities are recomputed once per second
Base priority divides all processes into fixed bands of priority
levels
Adjustment factor used to keep process in its assigned band
July 18, 2015
IESL-IT Part II - 2004
28
IT206 Operating Systems
Bands


Decreasing order of priority
 Swapper
 Block I/O device control
 File manipulation
 Character I/O device control
 User processes
Such a hierarchy allows for efficient use of I/O devices.
July 18, 2015
IESL-IT Part II - 2004
29
IT206 Operating Systems
July 18, 2015
IESL-IT Part II - 2004
30