Priority scheduling algorithms

Priority scheduling algorithms ,Priority scheduling algorithms ,Priority scheduling algorithms

1. Welcome
to Our
Presentation

2. Priority
Scheduling
Algorithms
2

3. Submitted by-
Name ID
Asikul Islam 143-15-
Kanchon Kumar 143-15-
Saiful Islam 143-15-
Sonot Kumar 143-15-
Sohel Al Mamun 143-15-
Tuhinur Rahman 143-15-
Muine al Yamine
Submitted to-
Dept. Of CSE

4. Overview 4
Basic Concepts
Scheduling Criteria
Scheduling Algorithms
Example of Priority Scheduling
Advantages & Disadvantages

5. Basic Concepts
Main objective of multiprogramming is to keep on
running processes all the time for maximum CPU
utilization.
Scheduling is fundamental function of OS.
The task of selecting the processes in memory that are
ready to execute, and allocating them to the CPU is
performed by the CPU Scheduler.
5

6. CPU Scheduler
CPU scheduling decisions may take place when
a process:
o1. Switches from running to waiting state
o2. Switches from running to ready state
o3. Switches from waiting to ready
o4. Terminates
Scheduling under 1 and 4 is non preemptive.
All other scheduling is preemptive.
6

7. CPU Scheduler
Nonpreemptive
Once a process is allocated the CPU, it does
not leave unless:
oit has to wait, e.g., for I/O request 
oit terminates  
Preemptive
oOS can force (preempt) a process from CPU at anytime
oE.g., to allocate CPU to another higher-priority process 
7
CONT…

8. Scheduling Criteria
CPU utilization: keep the CPU as busy as possible
◦Maximize
Throughput: No of processes that complete their
execution per time unit
◦Maximize
Turnaround time: amount of time to execute a
particular process (time from submission to
termination)
◦Minimize
8

9. Scheduling Criteria 9
CONT…
Waiting time: amount of time a process has been
waiting in the ready queue (sum of time waiting in
ready queue)
oMinimize
Response time – amount of time it takes from when
a request was submitted until the first response is
produced, not output  (for time-sharing
environment)
oMinimize

10. Scheduling Algorithms
First Come, First Served
Shortest Job First
Priority
Round Robin
10

11. A priority number (integer) is associated with each
process.
Lager the CPU burst lower the priority.
The CPU is allocated to the process with the highest
priority (smallest integer º highest priority)
Starvation (Infinity blocking): low priority processes
may never execute.
Aging: as time progresses increase the priority of the
process.
Priority
11
CONT…

12. Example of Priority Scheduling (Non-
Preemptive) 12
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
Gantt Chart
Average waiting time = (6 + 0 + 16 + 18 + 1)/5 = 8.2
Average Turn Around Time= (1+6+16+18+19)/5 = 12
P
2 P
1P
5
61
16
0
P
3
18
P
4
19

13. Example of Priority Scheduling
(Preemptive)
Process Arrival Time Burst Time Priority
P
1
0 5 2
P
2
4 8 1
P
3
6 2

4

p4
8 6 3
Average WT: ([(0-0)+(12-4)]+(4-4)+(19-6)+(13-8))/4
= (8+0+13+5)/4 = 6.5
Average TAT: ((5+8)+(8+0)+(2+13)+(6+5))/4
= (13+8+15+11)/4 = 47/4 = 11.75
P
1
P
4P
2
4 190 13
P
3
2112
P
1

14. Advantages of Priority
Easy to use
User friendly
Aging :- As time increases , increase in the priority
of a process .
Simplicity .
Suiteble for aplications with varying time and
resource requirement .

15. Disadvantages of Priority
If system eventually crashes , all low priority
processes get lost .
Indefinite blocking or Starvation .

16. Preemptive vs nonpreemptive
scheduling
CPU scheduling decisions may take place when a process:
1.switches from running to waiting state
e.g., I/O request
2.switches from running to ready state
e.g., when interrupt or timeout occurs
3.switches from waiting to ready
e.g., completion of I/O
4.Terminates
scheduling under 1 and 4 is nonpreemptive
once a process starts, it runs until it terminates or willingly gives up control
simple and efficient to implement – few context switches
examples: Windows 3.1, early Mac OS
all other scheduling is preemptive
process can be "forced" to give up the CPU (e.g., timeout, higher priority process)
more sophisticated and powerful
examples: Windows 95/98/NT/2K, Mac OS-X, UNIX

17. Preemptive vs Non-Preemptive Scheduling
Scheduling is non-preemptive if once the CPU has been allocated
to a process, the process can keep the CPU until it releases it,
either by terminating or switching to the waiting state.
Scheduling is preemptive if the CPU can be taken away from a
process during execution.

18. Priority scheduling
each process is assigned a numeric priority
CPU is allocated to the process with the highest priority
priorities can be external (set by user/admin) or internal
 (based on resources/history)
SJF is priority scheduling where priority is the predicted
 next CPU burst time
priority scheduling may be preemptive or nonpreemptive
priority scheduling is not fair
starvation is possible – low priority processes may never execute
can be made fair using aging – as time progresses, increase the
priority
Aging is a technique of gradually increasing the priority of
processes that wait in the system for a long time