Home » Operating System

Prediction of CPU Burst Time for a Process in SJF by Dynamic Method

In this tutorial, we will learn how to predict of CPU burst time for a process in SJF scheduling by dynamic method? By Monika Jha Last updated : May 08, 2023

Prediction of CPU Burst Time for a Process in SJF by Dynamic Method

We can dynamically predict the burst time of future process by following two techniques,

1. Simple Averaging
2. Exponential averaging or Aging

1. Simple Averaging

In the simple averaging method, the average burst time is taken of all the processes that have executed till now.

There is a total of n processes P(1), P(2), ... , P(n) and burst time of each process P(i) as t(i),

where i = 1,2,3, ..., n.

The predicted burst time for process P(n+1) is T(n+1) given by the following,

T(n+1) = (1/n) ∑ t(i)

Example

There are processes P1, P2, P3, and P4. The burst time of these processes is 6, 3, 4, 7.

Then the average burst time of the newly arrived process is calculated as:

Average burst time 
    = (P1 + P2 + P3 + P4)/4
    = (6+3+4+7)/4
    = 20/4
    = 5 units

2. Exponential averaging or Aging

Let, t(n) be the actual burst time of n^th process. T(n) be the predicted burst time for n^th process then the CPU burst time for the next process T(n+1) given by the following,

T(n+1) = α. t(n) + (1-α) . T(n)

Where, α is the smoothening factor, where 0<= α <=1

Smoothening factor (α)

It controls and manages the relative weight of the recent and past history of processes in our prediction,

• If α = 0, Τ(n+1) = Τ(n), it represents there is no change in the value of initial predicted burst time.
• If α = 1, Τ(n+1) = t(n), it represents predicted burst-time of the new process will always change according to actual burst-time of the n^th process.
• If α = 1/2, it represents the current and past history of equally-weighted processes.

Example

In this example, if the predicted burst time for the first process is 20 units and the actual burst time of the first four processes is 6, 10, 4 and 7 units respectively. Given α = 0.5. Then we will calculate the predicted burst time using the exponential averaging technique for the fifth process.

So given that, predicted burst time for first process = 20 units.

And actual burst time of the first four processes are as follows = 6, 10, 4, 7.

And the smoothening factor (α) = 0.5.

We can calculate the predicted Burst Time for the second Process by,

= α * Actual burst time of first process + (1-α) * Predicted burst time for first process
= 0.5 * 6 + 0.5 * 20
= 3 + 10
= 13 units

We can calculate predicted Burst Time for third Process by,

= α * Actual burst time of second process + (1-α) * Predicted burst time for second process
= 0.5 * 10 + 0.5 * 13
= 5 + 6.5
= 11.5 units

We can calculate predicted burst time for fourth process by,

= α * Actual burst time of third process + (1-α) * Predicted burst time for third process
= 0.5 * 4 + 0.5 * 11.5
= 2 + 5.75
= 7.75 units

We can calculate predicted Burst Time for fifth Process by,

= α * Actual burst time of fourth process + (1-α) * Predicted burst time for fourth process
= 0.5 * 7 + 0.5 * 7.75
= 3.5 + 3.875
= 7.375 units

---