Prediction of CPU Burst Time for a process in SJF

The SJF algorithm is one of the best scheduling algorithms since it provides the maximum throughput and minimal waiting time but the problem with the algorithm is, the CPU burst time can't be known in advance.

We can approximate the CPU burst time for a process. There are various techniques which can be used to assume the CPU Burst time for a process. Our Assumption needs to be accurate in order to utilize the algorithm optimally.

There are the following techniques used for the assumption of CPU burst time for a process.

1. Static Techniques

Process Size

We can predict the Burst Time of the process from its size. If we have two processes T_OLD and T_New and the actual burst time of the old process is known as 20 secs and the size of the process is 20 KB. We know that the size of P_NEW is 21 KB. Then the probability of P_New having the similar burst time as 20 secs is maximum.

If,     P_OLD → 20 KB 
P_New → 21 KB 
BT(P_OLD) → 20 Secs
Then, 
BT(P_New) → 20 secs

Hence, in this technique, we actually predict the burst time of a new process according to the burst time of an old process of similar size as of new process.

Process Type

We can also predict the burst time of the process according to its type. A Process can be of various types defined as follows.

• OS Process

A Process can be an Operating system process like schedulers, compilers, program managers and many more system processes. Their burst time is generally lower for example, 3 to 5 units of time.

• User Process

The Processes initiated by the users are called user processes. There can be three types of processes as follows.

• Interactive Process

The Interactive processes are the one which interact with the user time to time or Execution of which totally depends upon the User inputs for example various games are such processes. There burst time needs to be lower since they don't need CPU for a large amount of time, they mainly depend upon the user's interactivity with the process hence they are mainly IO bound processes.

• Foreground process

Foreground processes are the processes which are used by the user to perform their needs such as MS office, Editors, utility software etc. These types of processes have a bit higher burst time since they are a perfect mix of CPU and IO bound processes.

• Background process

Background processes supports the execution of other processes. They work in hidden mode. For example, key logger is the process which records the keys pressed by the user and activities of the user on the system. They are mainly CPU bound processes and needs CPU for a higher amount of time.

2. Dynamic Techniques

Simple Averaging

In simple averaging, there are given list of n processes P(i).......P(n). Let T(i) denotes the burst time of the process P(i). Let τ(n) denotes the predicted burst time of Pth process. Then according to the simple averaging, the predicted burst time of process n+1 will be calculated as,

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

Where, 0<=i<=n and ∑ T(i) is the summation of actual burst time of all the processes available till now.

Exponential Averaging or Aging

Let, Tn be the actual burst time of nth process.τ(n) be the predicted burst time for nth process then the CPU burst time for the next process (n+1) will be calculated as,

τ(n+1) = α. Tn + (1-α) . τ(n)

Where, α is the smoothing. Its value lies between 0 and 1.