صفحه 1:
Uniprocessor Scheduling
Chapter 9
صفحه 2:
Aim of Scheduling
° Assign processes to be executed
by the processor(s)
° Response time
° Throughput
° Processor efficiency
صفحه 3:
Table 9.1 Types of Scheduling
صفحه 4:
سس
=e ee G جه
Co et
‘een
Figure 9.1 Scheduling and Process State Transitions
صفحه 5:
صفحه 6:
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
صفحه 7:
Medium-Term
Scheduling
° Part of the swapping function
° Based on the need to manage
the degree of
multiprogramming
صفحه 8:
Short-Term Scheduling
° Known as the dispatcher
° Executes most frequently
° Invoked when an event occurs
~ Clock interrupts
- 1/0 interrupts
~ Operating system calls
- Signals
صفحه 9:
Short-Tem Scheduling
Criteria
° 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
صفحه 10:
Short-Term Scheduling
Criteria
° Performance-related
~ Quantitative
~ Measurable such as response time
and throughput
صفحه 11:
Table9.2 Scheduling Criteria
‘User Oriented, Performance Related
‘Turnaround time This isthe interval of time berveen the submission of a process ands completion.
Jncludes actual execution tame pis tne spent wang for resources, including the processor. Tiss an
appcopriate measure foca batch jb,
‘Response time Foran interactive rocess this isthe tine fiom the submission of 2 request wil the
response begins to be received. Often a process can begin produc some omtpn othe user hile
Contiming to process the request Thus this is a beter measure than tamarcund time from the user's point
of ew. The scheduling disciptine should arene to achieve tow response time and to maximize the
numberof interactive users receiving acceptable response tine
Deadlines When process completion deadlines can be specified, the scheduling discipline should
ssbordinate other gals to that of maximising che percentage of deadlines met.
User Oriented, Other
‘Predictability given job should run in abou the same smount of tine and at about the same cost
regardless of the load on the system. A ide Viton in respoase time ot umaround tine ic dseacing 6
‘users. Ifmay signal a wide swingin system workloads o the need for syste rang to cure instabilities
11
صفحه 12:
‘System Oriented, Performance Related
Throughput The scheduling policy should atempt to maximize the muuber of processes completed
pert of time. This ie a mame of how mich work is being performed. This clearly depends on the
Sverage length of a process bus leo infuenced by the scheduling policy, which may affect wization
Processor uilization This isthe percentage of tie tht the processor is busy. For an expensive shared
system, this sa significant crteron. In single-user systems and in some other systems, such اه
systems, his criterion s less enportane than seme of the eters.
System Oriented, Other
Faimess Inthe absence of guidance fom the user or other system spied guidance, processes should
be treated the same, and uo process should sufler starvation
Enforcing priovties | When processes are assigned pririties the scheduling policy should favur
bigher-pority processes
Balancing resources The scheduling policy should keep the sesonrees ofthe system busy. Processes
(hat wl undertilize stressed resources shouldbe favored. This cterion ako involves medium: term and
long-eem schecoling
12
صفحه 13:
13
Release
Longer Timeout
ses
Realy Quewe Shorten
5 ‘healing
=
1
Menem
سب
ا ss wails
wer ولة
0ك
sag
Block 3
Blocked Que
ven | Ly Eva Wat
Oecuts TT
‘Queuing Diagram for Scheduling
Figure 9.3
صفحه 14:
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
14
صفحه 15:
15
Roo
Dispate
Preemption
Event Wait
‘Blocked Queue
Figure 9.4 Priority Queuing
anit —>|
Event
صفحه 16:
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
16
صفحه 17:
Process Scheduling
Example
‘Table 9.4 Process Scheduling Example
Process | Arrival Time | Service Time
0
عاعواه
2
4
5
8
۳
صفحه 18:
First-Come-First-Served
(FCFS)
First-Come-First
Served (FCFS)
moa
* Each process joins the Ready queue
* When the current process ceases to
execute, the oldest process in the
Ready queue is selected
صفحه 19:
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
صفحه 20:
Round-Robin
on a clock
ermined
Round Robin
اوه
* Uses preemption based
° An amount of time is de
that allows each process to use the
processor for that length of time
20
صفحه 21:
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
صفحه 22:
22
(a) Pine quantum grater an tye
Figure 9.6 Effect of Size of Preemption Time Quantum
صفحه 23:
23
امس
Ready Quene
Digpateh Release
Aoxitiory Quene
VOL Wait
TOT Quene
Wo Wat
102 سم 1
3
1
Woe Wait
Ton Que
Admit
vor
Occurs
دور
Occurs
Won
Occurs
Figure 9.7 Queuing Diagram for Virtual Round-Robin Scheduler
صفحه 24:
Shortest Process Next
0 5 0 15 20
Shortest Process
Next (SPN)
* Nonpreemptive policy
* Process with shortest expected
processing time is selected next
* Short process jumps ahead of longer
processes
24
صفحه 25:
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
صفحه 26:
26
Age of Observation
Figure 9.8 Exponential Smoothing Coefficients
Coefficient Value
صفحه 27:
27
ime
(a Increasing function
Time
(Decreasing funtion
Figure 9.9 Use of Exponential Averaging
صفحه 28:
Shortest Remaining
Tian
10 5
0
Shortest Remaining 1
A
B
‘Time (SRT) اک
3
3
* Preemptive version of shortest
process next policy
* Must estimate processing time
صفحه 29:
Highest Response Ratio
Next (HRRN)
10 15
Ratio Next (HRN)
* Choose next process with the
greatest ratio
time spent waiting + expected service time
xpected service time
صفحه 30:
30
Feedback
i
Feedback,
at
050
*» Penalize jobs that have been running
longer
* Don’t know remaining time process
needs to execute
صفحه 31:
ROO Release
Admit 3
ont oe
Figure 9.10 Feedback Scheduling
31
صفحه 32:
Starvation
No
Possble
Possible
Pose
32
1g Policies
Eifecton
Processes
Peaalzes short
processes
penalizes 10
‘bound Eroceses
Fair مس
Penalzes long
Perales Tone
processes
Good balance
May ver 0
ound processes
Overhead
hee
مسا
(Con be high
Con be igh
Can be ish
Cites
Response
Time
‘arte هلط
specially if
there i arge
process
Provides 200d
sesposce tine
Tor short
مر
Provides good
sesposs time
pr
proseses
Provides good
‘espouse ine
Provides goed
sesponse time
امس اد
یهن
Not
emphasized
May be tow i
quaatum isto0
cea
High
Bia
High
Nor
emphasized
‘Table 93 Characteristics of Various Schedul
Deciion
Mode
Nospeeenptive
Preemptive at
مهو هار
بر
Preemptive Gr
ail)
Nonoreemptive
Preemptive Ge
time quent)
Selection
Fusetion
smashed
Grete)
tie spe wating
time spear ia execution so for
total service time required bythe proces including ©
سمل
Robi
SPN
SRT
IRRN
Feedback
صفحه 33:
33
ia
8.60
256
1080
27
10.00
am
760
بر
720
159
800
برد
10.00
229
1060
263
550
150
عد ماع م 5
20
260
20
4
280
20
4
2.80
0
14
280
0
14
280
19
B
2.60
20
14
26
275
100
13
225,
16
2
3.00
11
1
350
117
15
13
227
1
2
18
3000
17
15
250
wale oa]
1.00
‘Table 95 A Comparison of Scheduling Poli
Pros
لمجم Time
Service Time (7)
Fash Time
Tummaound Time (7>)
Tle
Finish Time
Tummaound Time (7)
7
Finish Time
Turnaround Time (Z,)
Tile
Finish Time
‘Turnaond Time (T,)
aa
Finish Time
Turneround Time (7)
Il
Finish Tine
‘Turnevound Time (7)
aly
Fash Tine
Tunaeund Time (F)
Tike
Fash Tine
Torasound Time (7)
Tile
FCES
SRT
بحا
Fz
صفحه 34:
34
‘Two Priovity Categories
9. Priority 1 items are serviced before priority 2 items
3. Fits-in-fistout dispatching for items of equal priority
No item is interupted while being served.
‘No items leave the queve (ost ealls delayed)
‘Table 9.6 Formalas for Single-Server Queues wi
“Ascomptions: 1. Poisson arival rate
(@) General Formulas
© Preemptive-resume queuing discipline;
‘exponential service times
ale
1
%
( of,
Tat
۸ 2 اک
صفحه 35:
35
aaa و
0
pry
eaten 6)
Figure 9.11 Overall Normalized Response Time
)172 مسلا ع سود اسالسممواة
صفحه 36:
36
2 pir eas
Figure 9.12 Normalized Response Time for Shorter Processes
Narra espome tine)
صفحه 37:
ok
rin
To pir
tation)
‘gure 9.13 Normalized Response Time for Longer Processes
37
ومع سمي تعس
صفحه 38:
38
eee me ried
jure 9.14 Simulation Results for Normalized Turnaround Time
i
i
E
صفحه 39:
Figure 9.15 Simulation Results for Waiting Time
صفحه 40:
Fair-Share Scheduling
° 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
صفحه 41:
Grow ده
Figure9.16 Example of Fair Share Sched ulerSThree Processes, Two Groups
صفحه 42:
Traditional
UNIX Scheduling
° Multilevel feedback using round
robin within each of the priority
queues
° Ifa running process does not
block or complete within 1
second, it is preempted
° Priorities are recomputed once
per second
* Base priority divides all processes
into fixed bands of priority levels
42
صفحه 43:
Bands
° Decreasing order of priority
~ Swapper
~ Block I/O device control
~ File manipulation
~ Character I/O device control
~ User processes
صفحه 44:
44
عستي يعست مسر مودت تسوه
Figure 9.17. Example o Traditional UNIX Process Scheduling,