Transcript Process Control Management

Operating Systems
AICT004-3-2
Process Control Management
Prepared by: Dhason
Topic & Structure of the lesson
Process Control Management
• Non-preemptive algorithms
• Calculations using non-preemptive scheduling algorithms
Operating Systems
Slide 2 of 18
Learning Outcomes
Process Control Management
• At the end of this lecture YOU should be able to:
- list non-preemptive scheduling algorithms
- perform calculations using non-preemptive
algorithms
Operating Systems
Slide 3 of 18
Key Terms you must be able to use
Process Control Management
If you have mastered this topic, you should be able to use
the following terms correctly in your assignments and
exams:
• first come first serve / first in first out
• shortest job first
• priority
Operating Systems
Slide 4 of 18
First Come First Serve ( FIFO / FCFS)
Process Control Management
• the simplest CPU scheduling non-preemptive algorithm
• a process that requests for the CPU first is allocated
the CPU
• the implementation of the FIFO policy is easily
managed with a FIFO queue
• the average waiting time for FIFO is quite long
• once the CPU has been allocated for the process, the
process keeps the CPU until termination or by
requesting for I/O
Operating Systems
Slide 5 of 18
First Come First Serve ( FIFO / FCFS)
Process Control Management
Step1:- Draw a Gantt Chart to represent timings for all processes
P1
0
P2 P3 P4
P5
10 11 13 14
Step2:- Calculate waiting time and average value
TW(P1) = 0
Process
TW(P2) = 10
TW(P3) = 11
P1
Tw(P4) = 13
P2
Tw(P5) = 14
P3
TW(average)=( 0+10+11+13+14)/5
P4
= 9.6 Milliseconds
P5
Operating Systems
19
Burst Time
(Milliseconds)
10
1
2
1
5
Slide 6 of 18
First Come First Serve ( FIFO / FCFS)
Process Control Management
Step-3: Calculate turn-around time and average value
TT(P1) = ( 0 + 10) = 10
P2 P3 P4
P5
10 11 13 14
TT = Tw+TB
TT(P2) = ( 10 + 1) = 11
Process
Burst Time
(Milliseconds)
P1
10
P2
1
P3
2
P4
1
P5
5
P1
0
TT(P3) = ( 11 + 2) = 13
TT(P4) = (13 + 1) = 14
TT(P5) = (14 + 5) = 19
Average turn around time is
(10+11+13+14+19)/5 = (67/5)
19
=13.4 Milliseconds
Operating Systems
Slide 7 of 18
Shortest Job First (SJF)
Process Control Management
• scheduling is done by examining the length of the next CPU
burst of a process
• if the CPU is free, the next process with the smallest CPU
burst time is assigned
• if two processes have the same CPU burst time, FIFO is
used to break the tie
• the difficulty with SJF is to determine the length of the next
process
• the advantage of this algorithm is that it is optimal; providing
minimum average waiting time
Operating Systems
Slide 8 of 18
Shortest Job First (SJF)
Process Control Management
Step1:- Draw a Gantt Chart to represent timings for all
processes
P2P4 P3
0 1 2
P5
4
P1
9
19
Step2:- Calculate waiting times and average
value
TW(P1) = 9
TW(P2) = 0
TW(P3) = 2
Tw(P4) = 1
Tw(P5) = 4
TW(average) = ( 9+0+2+1+4)/5
= 3.2 Milliseconds
Operating Systems
Process
Burst Time
(Milliseconds)
P1
10
P2
1
P3
2
P4
1
P5
5
Slide 9 of 18
Shortest Job First (SJF)
Process Control Management
Step-3: Calculate turn-around time and average value
TT = Tw+TB
P2P4 P3
0 1 2
P5
4
P1
9
TT(P1)=( 9 + 10)= 19
TT(P2)=( 0 + 1) = 1
TT(P3)=( 2 + 2) = 4
TT(P4)=(1 + 1) = 2
TT(P5)=(4 + 5) = 9
Average turn around time is
(19+1+4+2+9)/5 = (35/5)=7 Milliseconds
Operating Systems
19
Process
Burst Time
(Milliseconds)
P1
10
P2
1
P3
2
P4
1
P5
5
Slide 10 of 18
Priority
Process Control Management
• priority is associated with each process
• the CPU is allocated to a process with the highest priority
• equal priority processes are scheduled using FIFO
• priority can be high or low; however 0 can mean high priority
• can be preemptive or non-preemptive
• a problem with priority algorithm is starvation
• aging is a technique used to gradually increase the priority
of a process
Operating Systems
Slide 11 of 18
Priority
Process Control Management
Step1:- Draw a Gantt Chart to represent timings for all processes
P4
P1
P3
0 1
11
P5
13
P2
18 19
Step2:- Calculate waiting time and average
value
TW(P1) = 1
TW(P2) = 18
TW(P3) = 11
Tw(P4) = 0
Tw(P5) = 13
TW(average)=(1+18+11+0+13)/5
= 8.6 Milliseconds
Operating Systems
Process
Burst Time
(Milliseconds)
Priority
P1
10
3
P2
1
1
P3
2
3
P4
1
4
P5
5
2
Slide 12 of 18
Priority
Process Control Management
Step-3: Calculate turn-around times and average value
P1
P4
0 1
TT(P1)=(1+ 10)=11
P3
11
TT = Tw+TB
TT(P2)=(18+1)=19
TT(P3)=(11+2)=13
TT(P4)=(0+1) = 1
TT(P5)=(13+5)=18
Average turn around time is
(11+19+13+1+18)/5 = (62/5)
P5
13
P2
18 19
Process
Burst Time
(Milliseconds)
Priority
P1
10
3
P2
1
1
P3
2
3
P4
1
4
P5
5
2
=12.4 Milliseconds
Operating Systems
Slide 13 of 18
Quick Review Questions
Process Control Management
• Name three preemptive CPU scheduling algorithms
• Which of the three is the easiest to implement?
Operating Systems
Slide 14 of 18
Follow Up Assignment
Process Control Management
• FIFO on its own is a scheduling algorithm, however
FIFO is also used in other algorithms, name the
algorithms.
•
Operating Systems
Which non-preemptive algorithm is optimal and why?
Slide 15 of 18
Summary of Main Teaching Points
Process Control Management
• Non-preemptive CPU scheduling algorithms are
FIFO, SJF and priority.
• SJF algorithms have a shorter average waiting time
compared to FIFO and priority.
• Using priority scheduling may result in some processes
experiencing starvation; aging a method to overcome this
problem.
Operating Systems
Slide 16 of 18
Question and Answer Session
Process Control Management
Q&A
Operating Systems
Slide 17 of 18