Scribd
Upload
2 views14 pages

Module 3 -Practice Problems

The document outlines various CPU scheduling algorithms and their calculations, including FCFS, SRT, RR, preemptive priority, and non-preemptive priority scheduling. It provides detailed steps for drawing Gantt charts and calculating average waiting and turnaround times for different sets of processes. The results of these calculations are presented in tabular format for clarity.

Uploaded by

samarthgoudabpatil
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views14 pages

Module 3 -Practice Problems

The document outlines various CPU scheduling algorithms and their calculations, including FCFS, SRT, RR, preemptive priority, and non-preemptive priority scheduling. It provides detailed steps for drawing Gantt charts and calculating average waiting and turnaround times for different sets of processes. The results of these calculations are presented in tabular format for clarity.

Uploaded by

samarthgoudabpatil
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

PROBLEMS BASED ON VARIOUS PROCESSES SCHEDULING ALGORITHM

Solution steps:
1. Draw Gantt chart for the given problem.
2. From Gantt chart find the completion time of each process
3. Determine the Turnaround time using the formula:
Turnaround time = Completion time – Arrival time
4. Determine the waiting time using the formula:
Waiting time = Turnaround time – Burst time
5. Determine the Response time using the formula:
Response time = First time process scheduled – Arrival time

1. Consider the following set of processes with CPU burst time (in ms)
Process Arrival time Burst Time
P0 0 6
P1 1 3

P2 2 1

P3 3 4

Compute the waiting time and average turnaround time for the above process using
FCFS, SRT and RR (time quantum = 2ms) scheduling algorithm.
Solution:
i.) The Gantt chart for the FCFS schedule is as follows:

Process Arrival time Burst Time Completion Turnaround Waiting


Time time time
P0 0 6 6 6 0
P1 1 3 9 8 5

P2 2 1 10 8 7

P3 3 4 14 11 7
Average Turnaround time = Sum of turnaround time/ no. of processes
= 33/4 = 8.25ms
Average waiting time = Sum waiting time/ no. of processes
= 19/4 = 4.75ms
ii.) The Gantt chart for the SRT schedule is as follows:

Process Arrival time Burst Time Completion Turnaround Waiting


Time time time
P0 0 6 14 14 8
P1 1 3 5 4 1

P2 2 1 3 1 0

P3 3 4 9 6 2

Average Turnaround time = Sum of turnaround time/ no. of processes


= 25/4 = 6.25ms
Average waiting time = Sum waiting time/ no. of processes
= 11/4 = 2.75ms
iii.) The Gantt chart for the RR (TQ = 2ms) schedule is as follows:

Process Arrival time Burst Time Completion Turnaround Waiting


Time time time
P0 0 6 12 12 6
P1 1 3 10 9 6

P2 2 1 5 3 2

P3 3 4 14 11 7

Average Turnaround time = Sum of turnaround time/ no. of processes


= 35/4 = 8.75ms
Average waiting time = Sum waiting time/ no. of processes
= 21/4 = 5.25ms
1. Consider the following set of processes given in the table
Process Arrival time Burst Time Priority
P1 0 10 4
P2 3 5 2

P3 3 6 6

P4 5 4 3

Consider the large number as highest priority. Calculate the average waiting time and
turnaround time and draw Gantt chart for preemptive priority scheduling and preemptive
SJF scheduling.
Solution:
i.) The Gantt chart for the preemptive priority schedule is as follows: (Priority high= larger
number)

Process Arrival Burst Priority Completion Turnaround Waiting


time Time Time time time
P1 0 10 4 16 16 6
P2 3 5 2 25 22 17

P3 3 6 6 9 6 0

P4 5 4 3 20 15 11

Average Turnaround time = Sum of turnaround time/ no. of processes


= 59/4 = 14.75ms
Average waiting time = Sum waiting time/ no. of processes
= 34/4 = 8.5ms
ii.) The Gantt chart for the preemptive SJF schedule is as follows:

Process Arrival Burst Time Completion Turnaround Waiting


time Time time time
P1 0 10 25 25 15
P2 3 5 8 5 0

P3 3 6 18 15 9

P4 5 4 12 7 3

Average Turnaround time = Sum of turnaround time/ no. of processes


= 52/4 = 13ms
Average waiting time = Sum waiting time/ no. of processes
= 27/4 = 6.75ms

3. For the following example calculate average waiting time and average turnaround time
using FCFS, preemptive SJF and RR ( 1 time unit) CPU scheduling algorithms
Process Arrival time Burst Time
P1 0 8
P2 1 4

P3 2 9

P4 3 5

Solution:
i.) The Gantt chart for the FCFS schedule is as follows:

Process Arrival Burst Time Completion Turnaround Waiting


time Time time time
P1 0 8 8 8 0
P2 1 4 12 11 7

P3 2 9 21 19 10

P4 3 5 26 23 18

Average Turnaround time = Sum of turnaround time/ no. of processes


= 61/4 = 15.25ms
Average waiting time = Sum waiting time/ no. of processes
= 35/4 = 8.75ms
ii.) The Gantt chart for the preemptive SJF schedule is as follows:

Process Arrival Burst Time Completion Turnaround Waiting


time Time time time
P1 0 8 17 17 9
P2 1 4 5 4 0

P3 2 9 26 24 15

P4 3 5 10 7 2

Average Turnaround time = Sum of turnaround time/ no. of processes


= 52/4 = 13ms
Average waiting time = Sum waiting time/ no. of processes
= 26/4 = 6.5ms

iii.) The Gantt chart for the RR(1 unit time) schedule is as follows

Process Arrival Burst Time Completion Turnaround Waiting


time Time time time
P1 0 8 23 23 15
P2 1 4 13 12 8

P3 2 9 26 24 15

P4 3 5 20 17 12

Average Turnaround time = Sum of turnaround time/ no. of processes


= 76/4 = 19ms
Average waiting time = Sum waiting time/ no. of processes
= 50/4 = 12.5ms
3. Given below is the snapshot of processes. Draw Gantt charts using preemptive
and non preemptive priority scheduling algorithm. (A smaller number has a
higher priority) Also, calculate the average waiting time and turnaround time for
both.
4.
Process Arrival time Burst Time Priority
P1 0 6 4
P2 3 5 2

P3 3 3 6

P4 5 5 3

i.) The Gantt chart for the preemptive Priority schedule is as follows

Process Arrival Burst Time Priority Completion Turnaround Waiting


time Time time time
P1 0 6 4 16 16 10
P2 3 5 2 8 5 0

P3 3 3 6 19 16 13

P4 5 5 3 13 8 3

Average Turnaround time = Sum of turnaround time/ no. of processes


= 45/4 = 11.25ms
Average waiting time = Sum waiting time/ no. of processes
= 26/4 = 6.5ms
ii.) The Gantt chart for the Non-preemptive Priority schedule is as follows

Process Arrival Burst Priority Completion Turnaround Waiting


time Time Time time time
P1 0 6 4 6 6 0
P2 3 5 2 11 8 3

P3 3 3 6 19 16 13

P4 5 5 3 16 11 6

Average Turnaround time = Sum of turnaround time/ no. of processes


= 41/4 = 10.25ms
Average waiting time = Sum waiting time/ no. of processes
= 22/4 = 5.5ms

5. Consider the following set of processes


Process Arrival time Burst Time Priority
P1 0 10 2
P2 2 5 1

P3 3 2 0

P4 5 20 3

Draw Gantt charts and calculate average waiting time, average turnaround time using
following CPU scheduling algorithm
i. Preemptive shortest job
ii. Non preemptive priority (0 = high priority)
i.)The Gantt chart for the preemptive shortest job schedule is as follows:

Process Arrival Burst Time Completion Turnaround Waiting


time Time time time
P1 0 10 17 17 7
P2 2 5 9 7 2

P3 3 2 5 2 0

P4 5 20 37 32 12

Average Turnaround time = Sum of turnaround time/ no. of processes


= 58/4 = 14.5ms
Average waiting time = Sum waiting time/ no. of processes
= 21/4 = 5.25ms
ii.)The Gantt chart for the Non-preemptive priority (0 = high priority) schedule is as follows:
Process Arrival Burst Time Priority Completion Turnaround Waiting
time Time time time
P1 0 10 2 10 10 0
P2 2 5 1 17 15 10

P3 3 2 0 12 9 7

P4 5 20 3 37 32 12

Average Turnaround time = Sum of turnaround time/ no. of processes


= 66/4 = 16.5ms
Average waiting time = Sum waiting time/ no. of processes
= 29/4 = 7.25ms

6. Consider the following set of processes


Process Arrival time Burst Time
P1 0 6
P2 2 3

P3 4 3

P4 5 5

Draw Gantt charts and calculate average waiting time, average turnaround time using
following CPU scheduling algorithm
i. FCFS
ii. SRTF
iii. RR (quantum = 1msec)
i.) The Gantt chart for the FCFS schedule is as follows:
Process Arrival Burst Time Completion Turnaround Waiting
time Time time time
P1 0 6 6 6 0
P2 2 3 9 7 4

P3 4 3 12 8 5

P4 5 5 17 12 7

Average Turnaround time = Sum of turnaround time/ no. of processes


= 33/4 = 8.25ms
Average waiting time = Sum waiting time/ no. of processes
= 16/4 = 4ms

ii.) The Gantt chart for the SRTF schedule is as follows:

Process Arrival Burst Time Completion Turnaround Waiting


time Time time time
P1 0 6 12 12 6
P2 2 3 5 3 0

P3 4 3 8 4 1

P4 5 5 17 12 7

Average Turnaround time = Sum of turnaround time/ no. of processes


= 31/4 = 7.75ms
Average waiting time = Sum waiting time/ no. of processes
= 14/4 = 3.5ms

iii.)The Gantt chart for the RR(time quantum = 1ms) schedule is as follows:
Process Arrival Burst Time Completion Turnaround Waiting
time Time time time
P1 0 6 14 14 8
P2 2 3 9 7 4

P3 4 3 13 9 6

P4 5 5 17 12 7

Average Turnaround time = Sum of turnaround time/ no. of processes


= 42/4 = 10.5ms
Average waiting time = Sum waiting time/ no. of processes
= 25/4 = 6.25ms

7. Consider the following set of processes


Process Burst time Priority
P1 10 3
P2 1 1

P3 2 3

P4 1 4

P5 5 2

The processes are assumed to have arrived in the order P1, P2, P3, P4, P5 all at time 0. Draw
Gantt charts and calculate average waiting time, average turnaround time using following
CPU scheduling algorithm
i. FCFS
ii. SJF
iii. RR (quantum = 1msec)
i) The Gantt chart for the FCFS schedule is as follows:
By considering arrival time = 0 for all processes.
Process Burst Time Completion Turnaround Waiting
Time time time
P1 10 10 10 0
P2 1 11 11 10

P3 2 13 13 11

P4 1 14 14 13

P5 5 19 19 14

Average Turnaround time = Sum of turnaround time/ no. of processes


= 67/5 = 13.4ms
Average waiting time = Sum waiting time/ no. of processes = 48/5 = 9.6ms

ii.) The Gantt chart for the SJF schedule is as follows:

Process Arrival Burst Time Completion Turnaround Waiting


time Time time time
P1 0 10 19 19 9
P2 0 1 1 1 0

P3 0 2 4 4 2

P4 0 1 2 2 1

P5 0 5 9 9 4

Average Turnaround time = Sum of turnaround time/ no. of processes


= 35/5 = 7ms
Average waiting time = Sum waiting time/ no. of processes
= 16/5 = 3.2ms
The Gantt chart for the RR(time quantum = 1ms) schedule is as follows:
Process Arrival Burst Time Completion Turnaround Waiting
time Time time time
P1 0 10 19 19 9
P2 0 1 2 2 1

P3 0 2 7 7 5

P4 0 1 4 4 3

P5 0 5 14 14 9

Average Turnaround time = Sum of turnaround time/ no. of processes


= 46/5 = 9.2ms
Average waiting time = Sum waiting time/ no. of processes
= 27/5 = 5.4ms

8. Consider the following set of processes


Process Arrival time Burst time Priority
P1 0 10 3
P2 0 1 1

P3 3 2 3

P4 5 1 4

P5 10 5 2

Draw Gantt charts and calculate average waiting time, average turnaround time using
preemptive priority scheduling algorithm. Assume highest priority = 1 and lowest priority =
4
The Gantt chart for the preemptive priority schedule is as follows:

Process Arrival Burst Time Priority Completion Turnaround Waiting


time Time time time
P1 0 10 3 11 11 1
P2 0 1 1 1 1 0
P3 3 2 3 18 15 13

P4 5 1 4 19 14 13

P5 10 5 2 16 6 1

Average Turnaround time = Sum of turnaround time/ no. of processes = 47/5 = 9.4ms
Average waiting time = Sum waiting time/ no. of processes = 28/5 = 5.6ms

9. Consider the following set of processes


Process Arrival time Burst time
P0 0 6
P1 1 3

P2 2 1

P3 3 4

Draw Gantt charts and calculate average waiting time, average turnaround time using
SRTF and non preemptive SJF
i). The Gantt chart for the SRTF schedule is as follows:

Process Arrival Burst Time Completion Turnaround Waiting


time Time time time
P0 0 6 14 14 8
P1 1 3 5 4 1

P2 2 1 3 1 0

P3 3 4 9 6 2

Average Turnaround time = Sum of turnaround time/ no. of processes = 25/4 = 6.25ms
Average waiting time = Sum waiting time/ no. of processes = 11/4 = 2.75ms

ii). The Gantt chart for the non preemptive SJF schedule is as follows:
Process Arrival Burst Time Completion Turnaround Waiting
time Time time time
P0 0 6 6 6 0
P1 1 3 10 9 6

P2 2 1 7 5 4

P3 3 4 14 11 7

Average Turnaround time = Sum of turnaround time/ no. of processes = 31/4 = 7.75ms
Average waiting time = Sum waiting time/ no. of processes = 17/4 = 4.25ms

You might also like