# How can be predict the burst time of future process in SJF Scheduling by dynamic method?

In this article, we will learn to **find out the burst time of the future process in SJF Scheduling**. We are going to learn **dynamic methods** and also understand **different factors to predict the burst time of processes**.

Submitted by Monika Jha, on October 26, 2019

**Prerequisites:** Static methods to predict burst time in SJF Scheduling

## Dynamic Method

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

- Simple Averaging
- 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**process then the CPU burst time for the next process

^{th}**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**process.^{th} - 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

**References:**

- Prediction of CPU Burst Time for a process in SJF
- Predicting Burst Time | SJF Scheduling
- SJF with prediction of Burst time.
- Shortest job next

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions