### Table of Content

Today we will practice problems on different types of **CPU Scheduling Algorithms**. We will see here how the CPU scheduler uses scheduling algorithms during the execution of the process. Let’s see.

## FCFS Example

Consider the above set of processes that arrive at time zero. The length of the **CPU Burst Time** is given in milliseconds. Now we calculate the average waiting time, average turnaround time, and throughput.

### Average Waiting Time

First of all, we have to calculate the waiting time of each process.

**Waiting Time = Starting Time – Arrival Time**

Waiting time of

P1 = 0

P2 = 5 – 0 = 5 ms

P3 = 29 – 0 = 29 ms

P4 = 45 – 0 = 45 ms

P5 = 55 – 0 = 55 ms

**Average Waiting Time = Waiting Time of all Processes / Total Number of Process**

Therefore, average waiting time = (0 + 5 + 29 + 45 + 55) / 5 = 25 ms

### Average Turnaround Time

First of all, we have to calculate the turnaround time of each process.

**Turnaround Time = Waiting time in the ready queue + executing time + waiting time in waiting-queue for I/O**

Turnaround time of

P1 = 0 + 5 + 0 = 5ms

P2 = 5 + 24 + 0 = 29ms

P3 = 29 + 16 + 0 = 45ms

P4 = 45 + 10 + 0 = 55ms

P5 = 55 + 3 + 0 = 58ms

**Average Turnaround Time = (Total Turnaround Time / Total Number of Process)**

Total Turnaround Time = (5 + 29 + 45 + 55 + 58)ms = 192ms

Therefore, Average Turnaround Time = (192 / 5)ms = 38.4ms

### Throughput

Here, we have a total of five processes. Process P1, P2, P3, P4, and P5 takes 5ms, 24ms, 16ms, 10ms, and 3ms to execute respectively.

Throughput = (5 + 24 +16 + 10 +3) / 5 = 11.6ms

It means one process executes every 11.6 ms.

## SJF(Shortest Job First) Scheduling

### Average Waiting Time

We will apply the same formula to find the average waiting time in this problem. Here arrival time is common to all processes(i.e., zero).

Waiting Time for

P1 = 3 – 0 = 3ms

P2 = 34 – 0 = 34ms

P3 = 18 – 0 = 18ms

P4 = 8 – 0 = 8ms

P5 = 0ms

Therefore, Average Waiting Time = (3 + 34 + 18 + 8 + 0) / 5 = 12.6ms

### Average Turnaround Time

According to the SJF Gantt chart and the turnaround time formulae,

Turnaround Time of

P1 = 3 + 5 = 8ms

P2 = 34 + 24 = 58ms

P3 = 18 + 16 = 34ms

P4 = 8 + 10 = 18ms

P5 = 0 + 3 = 3ms

Therefore, Average Turnaround Time = (8 + 58 + 34 + 18 + 3) / 5 = 24.2ms

### Throughput

Here, we have a total of five processes. Process P1, P2, P3, P4, and P5 takes 5ms, 24ms, 16ms, 10ms, and 3ms to execute respectively. Therefore, the Throughput will be the same as the above problem i.e., 11.6ms for each process.

## Round Robin Scheduling Example

Here is the round-robin scheduling example with the Gantt chart. Time Quantum is **5ms**.

### Average Waiting Time

To find the Average Waiting Time, we have to find out the waiting time of each process.

Waiting Time of

P1 = 0 + (15 – 5) + (24 – 20) = 14ms

P2 = 5 + (20 – 10) = 15ms

P3 = 10 + (21 – 15) = 16ms

Therefore, Average Waiting Time = (14 + 15 + 16) / 3 = 15ms

### Average Turnaround Time

The same concept for finding the Turnaround Time.

Turnaround Time of

P1 = 14 + 30 = 44ms

P2 = 15 + 6 = 21ms

P3 = 16 + 8 = 24ms

Therefore, Average Turnaround Time = (44 + 21 + 24) / 3 = 29.66ms

### Throughput

Throughput = (30 + 6 + 8) / 3 = 14.66ms

In 14.66ms, one process executes.

## Shortest Remaining Time First(SRTF)

### Average Waiting Time

First of all, we have to find the waiting time for each process.

Waiting Time of process

P1 = 0ms

P2 = (3 – 2) + (10 – 4) = 7ms

P3 = (4 – 4) = 0ms

P4 = (15 – 6) = 9ms

P5 = (8 – 8) = 0ms

Therefore, Average Waiting Time = (0 + 7 + 0 + 9 + 0) / 5 = 3.2ms

### Average Turnaround Time

First of all, we have to find the turnaround time of each process.

Turnaround Time of process

P1 = (0 + 3) = 3ms

P2 = (7 + 6) = 13ms

P3 = (0 + 4) = 4ms

P4 = (9 + 5) = 14ms

P5 = (0 + 2) = 2ms

Therefore, Average Turnaround Time = (3 + 13 + 4 + 14 + 2) / 5 = 7.2ms

### Throughput

Throughput = (3 + 6 + 4 + 5 + 2) / 5 = 4ms

Therefore, each process takes 4ms to execute.

## Priority Scheduling Example

### Average Waiting Time

First of all, we have to find out the waiting time of each process.

Waiting Time of process

P1 = 3ms

P2 = 13ms

P3 = 25ms

P4 = 0ms

P5 = 9ms

Therefore, Average Waiting Time = (3 + 13 + 25 + 0 + 9) / 5 = 10ms

### Average Turnaround Time

First, find the Turnaround Time of each process.

Turnaround Time of process

P1 = (3 + 6) = 9ms

P2 = (13 + 12) = 25ms

P3 = (25 + 1) = 26ms

P4 = (0 + 3) = 3ms

P5 = (9 + 4) = 13ms

Therefore, Average Turnaround Time = (9 + 25 + 26 + 3 + 13) / 5 = 15.2ms

### Throughput

Throughput = (6 + 12 + 1 + 3 + 4) / 5 = 5.2ms

Therefore, each process takes 5.2ms to execute.

## Leave a Reply