KEMBAR78
Unit 2 - Scheduling Algorithms | PDF | Scheduling (Computing) | Computer Architecture
Scribd
Upload
6 views14 pages

Unit 2 - Scheduling Algorithms

The document outlines various CPU scheduling algorithms including First Come First Serve (FCFS), Shortest Job First (SJF), Round Robin (RR), and Priority Scheduling, detailing their characteristics and calculations for turnaround and waiting times. It provides examples with processes, burst times, and arrival times, demonstrating the average turnaround and waiting times for each algorithm. Additionally, it mentions multilevel queue scheduling and multilevel feedback queue scheduling as further methods for managing process execution.

Uploaded by

margaret.savitha
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
6 views14 pages

Unit 2 - Scheduling Algorithms

The document outlines various CPU scheduling algorithms including First Come First Serve (FCFS), Shortest Job First (SJF), Round Robin (RR), and Priority Scheduling, detailing their characteristics and calculations for turnaround and waiting times. It provides examples with processes, burst times, and arrival times, demonstrating the average turnaround and waiting times for each algorithm. Additionally, it mentions multilevel queue scheduling and multilevel feedback queue scheduling as further methods for managing process execution.

Uploaded by

margaret.savitha
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
You are on page 1/ 14

ALGORITHMS

CPU SCHEDULING
1. FIRST COME FIRST SERVE (FCFS) (nonpreemptive)
2. SHORTEST JOB FIRST or Shortest Job Next (SJN) (nonpreemptive)
SHORTEST REMAINING TIME FIRST (SRTF) (preemptive)
3. ROUND ROBIN (preemptive)
4. PRIORITY SCHEDULING (non-preemptive)
PRIORITY SCHEDULING (preemptive )
5. MULTILEVEL QUEUE SCHEDULING
6. MULTILEVEL FEEDBACK QUEUE SCHEDULING

Arrival Time = Completion Time - Turn Around Time


Burst Time = Completion Time - Waiting Time
Turn Around time = Completion time - arrival time
Waiting Time = Turnaround time - burst time
1. FIRST COME FIRST SERVE (FCFS)

Arrival
Process Burst Time
Time
p1 0 5
p2 0 3
p3 0 8

Average turnaround time = 9.67


Average waiting time = 4.33
Process Burst Time (BT) Arrival Time (AT)
P1 5 ms 2 ms
P2 3 ms 0 ms
P3 4 ms 4 ms

Turnaround
Completion Waiting Time
Process Time
Time (CT) (WT = TAT - BT)
(TAT = CT - AT)
P2 3 ms 3 ms 0 ms
P1 8 ms 6 ms 1 ms
P3 12 ms 8 ms 4 ms

Average Turnaround time = 5.67


Average waiting time = 1.67
Turn
Arrival Brust Completion Waiting
Convey Effect (FCFS) Process ID
Time Time Time
Around
Time
Time
P1 1 1 42 41 40
P2 1 3 45 44 41
P3 0 42 46 46 4

Average waiting Time of processes = 85/3.

Turn
Arrival Brust Completion Waiting
Process ID Around
Time Time Time Time
Time
P1 0 2 4 2 0
P2 0 1 3 3 2
P3 1 42 45 44 2

Average Waiting Time = 4/3


2. SHORTEST JOB FIRST or Shortest Job Next (SJN)

The Shortest Job First (SJF) Scheduling algorithm selects the process with the smallest
burst time for execution.
Turn Around time = Completion time - arrival time
Process Burst Time Arrival Time Waiting Time = Turnaround time - burst time
P1 6 ms 0 ms
P2 8 ms 2 ms
P3 3 ms 4 ms

Arrival Waiting Average Turn around time =


Burst Time Completion Turn Around
Process Time Time (6 + 15 + 5)/3 = 8.6 ms
(BT) Time (CT) Time (TAT)
(AT) (WT)
Average waiting time =
P1 0 6 6 6-0 = 6 6-6 = 0 ( 2 + 0 + 7 )/3 = 9/3 = 3 ms
P2 2 8 17 17-2 = 15 15-8 = 7
P3 4 3 9 9-4 = 5 5-3 = 2
Shortest Remaining Time First (Preemptive SJF) Scheduling Algorithm

Process Burst Time Arrival Time


P1 6 ms 0 ms
P2 8 ms 0 ms
P3 5 ms 0 ms

Arrival Time Burst Time Completion Turn Around Waiting Time


Process
(AT) (BT) Time (CT) Time (TAT) (WT)
P1 0 6 11 11-0 = 11 11-6 = 5
P2 0 8 19 19-0 = 19 19-8 = 11
P3 0 5 5 5-0 = 5 5-5 = 0

Average Turn around time = (11 + 19 + 5)/3 = 11.6 ms


Average waiting time = (5 + 0 + 11 )/3 = 16/3 = 5.33 ms
Process Burst Time Arrival Time
P1 6 ms 0 ms
P2 3 ms 1 ms
P3 7 ms 2 ms

Burst
Arrival Completion Turn Around Waiting Time
Process Time
Time (AT) Time (CT) Time (TAT) (WT)
(BT)
P1 0 6 9 9-0 = 9 9-6 = 3
P2 1 3 4 4-1 = 3 3-3 = 0
P3 2 7 16 16-2 = 14 14-7 = 7

Average Turn around time = (9 + 14 + 3)/3 = 8.6 ms


Average waiting time = (3 + 0 + 7 )/3 = 10/3 = 3.33 ms
3. ROUND ROBIN (RR) SCHEDULING

Used by operating systems to manage the execution time of multiple processes that are competing
for CPU attention. It is called "round robin" because the system rotates through all the processes,
allocating each of them a fixed time slice or "quantum”.
Time Quantum = 2 ms
Process Burst Time Arrival Time
P1 4 ms 0 ms
P2 5 ms 0 ms
P3 3 ms 0 ms

Processes AT BT CT TAT WT Average Turn around time =


P1 0 4 8 8-0 = 8 8-4 = 4 (8 + 12 + 11)/3 = 31/3 = 10.33
ms
P2 0 5 12 12-0 = 12 12-5 = 7 Average waiting time =
P3 0 3 11 11-0 = 11 11-3 = 8 (4 + 7 + 8)/3 = 19/3 = 6.33 ms
Process Burst Time (BT) Arrival Time (AT) Time Quantum = 2
P1 5 ms 0 ms
P2 2 ms 4 ms
P3 4 ms 5 ms

Completion Time Turnaround Time Waiting Time


Process
(CT) (TAT = CT - AT) (WT = TAT - BT)
P1 7 ms 7 ms 2 ms
P2 6 ms 2 ms 0 ms
P3 11 ms 6 ms 2 ms

Average Turn around time =7+2+6/3​=15/3=5ms


Average waiting time = 2+0+2/3=1.33ms
4. PRIORITY SCHEDULING (NON-PREEMPTIVE)

Process Arrival Time Burst Time Priority


P1 0 4 2
P2 1 2 1
P3 2 6 3

Turnaround Waiting
Arrival Burst Completion
Process Time Time
Time Time Time
(CT - AT) (TAT - BT)
P1 0 4 4 4 0
P2 1 2 6 5 3
P3 2 6 12 10 4

Average Turnaround Time = 6.33


Average Waiting Time = 2.33
Note: Higher number represents a higher priority.
Priority Scheduling (Preemptive )

Process Arrival Time Burst Time Priority


P1 0 7 2
P2 0 4 1
P3 0 6 3

Turnaround Waiting
Arrival Burst Completion
Process Time Time
Time Time Time
(CT - AT) (TAT - BT)
P1 0 7 13 13 6
P2 0 4 17 17 13
P3 0 6 6 6 0

Average Turnaround Time = 12


Average Waiting Time = 6.33
Priority Scheduling (Preemptive )

Process Arrival Time Burst Time Priority


P1 0 6 2
P2 1 4 3
P3 2 5 1

Turnarou Waiting
Arrival Burst Completion
Process nd Time Time
Time Time Time
(CT - AT) (TAT - BT)
P1 0 6 10 10 4
P2 1 4 5 4 0
P3 2 5 15 13 8

Average Turnaround Time = 9


Average Waiting Time = 4
5. MULTILEVEL QUEUE SCHEDULING
6. MULTILEVEL FEEDBACK QUEUE SCHEDULING

You might also like