Received 13 March 2016; accepted 24 April 2016; published 27 April 2016

ABSTRACT

This paper proposes a novel chronically evaluated highest instantaneous priority next processor scheduling algorithm. The currently existing algorithms like first come first serve, shortest job first, round-robin, shortest remaining time first, highest response ratio next and varying response ratio priority algorithm have some problems associated with them. Some of them can lead to endless waiting or starvation and some of them like round-robin has problem of too many context switches and high waiting time associated with them. In the proposed algorithm, we have taken care of all such problems. As the novel algorithm is capable of achieving as good results as shortest remaining time first algorithm and also it will never lead to starvation.

Keywords:

Chronically Evaluated Highest Instantaneous Priority Next, CEHIPN, Priority Scheduling, Preemptive Scheduling, Processor Scheduling, Starvation

1. Introduction

Scheduling algorithm improves processor’s efficiency by improving its utilization. The short-term scheduler uses various algorithms to do assignments for the processor [1] . First come, first serve (FCFS) [2] - [4] , Shortest job first (SJF) [2] - [5] , Shortest remaining time first (SRTF) [3] [4] , Round-robin (RR) [2] - [4] , Highest response ratio next (HRRN) [4] , Mid Average Round-Robin (MARR) [6] , Adaptive Round-Robin (Adaptive RR) [7] , Improved Round-Robin Approach using Dynamic Time Quantum (IRRADTQ) [8] and Varying Response Ratio Priority (VRRP) [9] , are some of the examples of scheduling algorithm used by the scheduler. A good scheduling approach fulfills some basic goals like increasing throughput, reducing overhead, avoiding starvation and execution according to priority. That is why researchers are working around the world to improve them in the terms of better waiting time and response time.

As performance of the algorithm may vary under various situations [5] , so the possible criteria for selection of a proper algorithm can be reduced context switch count, increased throughput, increased processor use, reduced waiting time, reduced response time and reduced turnaround time [10] .

On analyzing the existing algorithms we found that they have some withdrawing factors, such as long waiting time or starvation associated with them. To overcome these demerits, we have proposed a novel algorithm for processor scheduling. The novel algorithm considers the instantaneous waiting time and instantaneous remaining time for evaluating the priority. The proposed approach is preemptive and the priority for the processes will be calculated when any new process arrives or any process finishes.

2. Related Work

The First come first serve is one of the simplest processor scheduling algorithms [3] [4] , it takes processes in same sequence as they arrive, regardless of their burst time, later it follows the same sequence to assign processor to them. There is a major drawback associated as it is a non preemptive approach less time-consuming process waits for a less important one to finish first.

To overcome this problem the shortest job first algorithm was proposed in which the job with shorter burst time is executed first [3] [4] [11] . But in this approach if short processes keep coming in sequence, then any long process has to wait endlessly for its chance and may starve [12] . Further, there was a new algorithm proposed by the name Shortest remaining time first [3] [4] this was a preemptive approach in which job with shorter remaining time is executed first. Again problem was the same, if new jobs with shorter running time keep coming then an older job with larger remaining time has to wait endlessly creating a condition of starvation.

To overcome this starvation problem new Round-robin algorithm was introduced [3] [4] [11] . In this approach processor handles each process in recurring order and for a fixed time quantum. Hence each process gets the processor equally and no process ever starves. But because of these frequent switching this algorithm is associated with a large number of context switches and high average waiting time [4] [13] . To further reduce the average waiting time, many improvements over round-robin algorithm were proposed [14] - [16] . Like Proportional Share Scheduling Algorithm, which was proposed by Helmy and Dekdouk [16] , this algorithm inherits features from round-robin and is encouraging for shorter jobs, there is an SBRRR algorithm that is a blend of Shortest job first and Round-robin [18] , on the other hand the PBDRR algorithm holds the features from priority algorithm and Round-Robin [19] .

In adaptive Round-Robin [7] [20] , the processes in ready queue are first arranged in increasing order of their burst time. If number of contributing processes is even. Then time quantum is calculated as an average of their burst time. If the number of processes is odd, then burst time of the middle process is taken as the time quantum. Later in mid average Round-Robin algorithm [6] [20] first all processes are sorted in increasing order of their burst time in the ready queue. Next we find the middle process. Then average burst time for all process from mid process to the end process is calculated. This average value is then assigned as a time quantum for further calculations. Further, in 2013, Negi et al. proposed an enhanced Round-Robin algorithm using dynamic time quantum and improved average waiting time [8] . This approach uses a time margin to check whether the process in its second last round can be finished in the same round by extending the time quantum by a small margin. If it is possible then it will be finished in the same round by providing time extension for achieving better performance.

Next in the sequence is the highest response ratio next algorithm [4] . It is a non preemptive approach which considers the ratio of waiting time to burst time for calculating response ratio. This ratio is used to assign next process to the processor. Waiting time is considered for calculating the response ratio. Ensuring process with larger waiting time will get a higher response ratio and it will never starve.

In 2015, Singh et al. Proposed Varying Response Ratio Priority algorithm. It calculates the priority of each process based on their waiting time and remaining burst time [9] . The algorithm ensures there will be no endless waiting by including waiting time in calculating the priority.

The novel algorithm proposed in this paper inherits some features from both highest response ratio next as well as shortest remaining time first approaches. The proposed approach is a preemptive approach. It uses instantaneous remaining time and waiting time together to calculate instantaneous priority.

3. Proposed Approach

The proposed chronically evaluated highest instantaneous priority next algorithm is a preemptive approach. It takes the instantaneous remaining time and waiting time of the processes into consideration to calculate their instantaneous priority. Then the process with highest instantaneous priority is allocated to the processor. This also makes this approach a priority base scheduling algorithm.

The Algorithm

The flow chart included below explains the working of the proposed algorithm (see Figure 1). It can be observed in the flow chart below that each time any process finishes or any new process arrives the instantaneous priority for each participating process will be calculated and then the processor will allocated to the process which has the highest priority.

4. Functioning of the Algorithm

The proposed algorithm considers two factors instantaneous remaining time and waiting time to calculate the instantaneous priority. Every time either a process finishes or a new one arrives, the priority for every contributing process is calculated.

(1)

where,

= Instantaneous waiting time of the processes.

BT = Burst Time

= Instantaneous remaining time of processes.

Here, P represents the process number for “n” contributing processes and Rem.T is their respective remaining time. First the sum of remaining time from process 1 to n is calculated. Then the sum is divided by “n” to get mean value as Mean Rem.T. When waiting time of any process increases its priority will also increase. As no process has to wait endlessly. Hence,

α

Time will come when chronically increasing priority of that process will become considerably high to take over the processor from any other process with even smaller remaining time. This is called inversion of execution order.

The priority value will also increase with decreasing remaining time of any process, as shorter jobs should be executed first. Hence,

α

The exponent “n” in the denominator of the formula for calculating instantaneous priority is there to lowers the sharp growth of priority value for any process which has large waiting time. For the higher value of “n” the whole denominator term will become a huge value. Hence even for the process with large waiting time the priority will not increase sharply. This will make the priority value to increase slowly and the priority inversion will be delayed. Which will eventually enhance the performance by keeping the average waiting time for the process low. In the formula the constant 1 is added to the first ratio, so that when the waiting time of any process is zero the value of the first factor will become one. As initially when processes will arrive their waiting time

will be zero. Hence the factor will become one and the priority for the processes will be simply calculated on the basis of the ratio. That is the process with the smallest remaining time will get the highest priority. Also the factor is included in formula to scale the priorities.

By scaling we mean to arrange all the processes on same scale with respect to the mean remaining time value. This will help to measure the processes priority on the same scale for getting a proper response. So the second ratio arranges the processes in order to which the enhancement values obtained from the first ratio are multiplied to obtain the instantaneous priority.

Let there be “I” number of processes initially in ready queue as. Let P_k be the process with highest burst time of T_k and sum of burst time for all (i-1) processes except P_k is. Then for best performance of CEHIPN we will consider the below equation based on the first factor (See expression 2),

Or,

(2)

Now this expression 2 will be used to decide the value of exponent “n” in the formula.

During the run, cases may arise when processes may have same priority. In such cases process with shorter remaining time should be preferred, as it will make CEHIPN to behave like shortest remaining time first algorithm. If their remaining time is also same then any of the process can be chosen. Hence in this case of equality of process priority the below equality holds,

(3)

On rearranging the above expression, we will have,

(4)

4.1. CASE I: Process Priorities Are Equal and Also Rem.T_i = Rem.T_j

When remaining time of the processes is same, then in expression 4 mentioned above we have,

Let,

Now the expression 4 can be rewritten as,

(5)

Or,

Or,

(6)

Therefore, when remaining time is same for both the processes then their waiting time will also be same. Hence anyone of them can be considered for next execution.

4.2. CASE II: Process Priorities are Equal and Also Rem.T_i > Rem.T_j

In this case, when both processes are having different remaining time but same priority. We can recall expression 4,

Now,

As given that,

Hence,

(7)

Or,

(8)

Expression 8 shows that waiting time of Pi is also greater than that of Pj. But priority of both the processes is still same. In this case, the process with smaller remaining time value will be selected next, as waiting time is included in expression 1 to increase the priority to avoid starvation only.

Consider the average waiting time at current instance as AWT for 'm' number of contributing processes. Now if process Pi with larger remaining time is executed first instead of Pj. Then average waiting time at the end, when both processes will finish, will be AWT(i). where,

On the other hand if Pj is executed first. Then average waiting time at the end, when both processes will finish, will be AWT(j). where,

Since Rem.Ti is greater than Rem.Tj. Hence AWT(i) will also be greater than AWT(j). We also know that average waiting time should be kept to minimum for the best performance. Hence second approach of selecting Pj will give better result. Therefore, when priority is same and it comes to selection between two processes. Then process with shorter remaining time will be selected first.

5. Performance of the Algorithm

The performance of the algorithm can be analyzed by comparing the average waiting time, average response time and number of context switches of CEHIPN with other algorithms. We have considered the burst time of the processes in increasing, decreasing and random orders to generate four different cases. Then theoretical calculations are performed to obtain below data for analysis.

5.1. CASE I: Random Order of Burst Time

In Case I processes are arriving in random order of burst time and exponent “n” will take three different values 1, 2 and 3 respectively for three different calculations (see Table 1 and Table 2). It is possible with CEHIPN algorithm to achieve the same results as shortest remaining time first algorithm by varying the values of exponent “n” (see Figure 2 and Figure 3).

Calculations Involved in CEHIPN for n = 1:

Round #1: Time = 1 (P2 arrives)

Priority P1 = 0.67

Priority P2 = 2

P2 is selected.

Round #2: Time = 3 (P3 arrives)

Priority P1 = 0.68

Priority P2 = 5

Priority P3 = 1

P2 is selected.

Round #3: Time = 4 (P2 finished and P4 arrives)

Priority P1 = 0.89

Priority P3 = 1.44

Priority P4 = 1.5

P4 is selected.

Round #4: Time = 8 (P4 finished)

Priority P1 = 1.38

Priority P3 = 2.8

P3 is selected.

Round #5: Time = 10 (P5 arrives)

Priority P1 = 1.33

Priority P3 = 5.33

Priority P5 = 1

P3 is selected.

Round #6: Time = 13 (P3 finished)

Priority P1 = 1.94

Priority P5 = 1.88

P1 is selected. Here the priority of P1 got amplified, as it was waiting for a long time. It got selected over P5 which even has a smaller remaining time. Ensuring there will be no starvation.

5.2. CASE II: Random Order of Burst Time

Also in Case II the processes are arriving in random order of burst time and value of exponent “n” in three different calculations of CEHIPN is 1,2 and 3 respectively (see Table 3 and Table 4). On increasing the value of exponent “n”. The result of CEHIPN will improve and will become same as for Shortest remaining time first (see Figure 4 and Figure 5).

5.3. CASE III: Decreasing Order of Burst Time

In Case III the processes are arriving in decreasing order of burst time (see Table 5 and Table 6). The exponent “n” has two values 1 and 3 respectively for two different calculations (see Figure 6 and Figure 7).

5.4. CASE IV: Increasing Order of Burst Time

In this case we will get same values for all the algorithms. As the burst time is in increasing order. So the shorter job will always come first and will be executed first, resulting in same sequence as for the shortest remaining time first algorithm (see Table 7 and Table 8).

6. Results

In the present study there is comparison of the novel CEHIPN algorithm with First come first serve, Shortest job first, Shortest remaining time first, Round-robin, Highest response ratio next, Varying Response Ratio Priority, Mid Average Round-Robin and Adaptive Round-Robin in terms of number of context switches, average waiting time, and average response time. There are four different cases where the Burst time of the contributing processes is arranged in random, decreasing and increasing orders to get the following results.

In Figure 8 there is comparison of CEHIPN when processes are arriving in random order of their burst time for Case I (see Figure 8). The average waiting time and average response time of CEHIPN with n = 1 are far better than that of First come first serve, Shortest job first, Round-robin, Highest response ratio next, Varying Response Ratio Priority, Mid Average Round-Robin and Adaptive Round-Robin. For CEHIPN with n = 2 and 3, values are same to that of Shortest remaining time first. The context switches in all the three cases of CEHIPN are less than that of Varying Response Ratio Priority and are equal to that of Shortest remaining time first.

In Figure 9 there is comparison of CEHIPN when processes are arriving in random order of their burst time for Case II and n = 1, 2 and 3 respectively for three cases of CEHIPN (see Figure 9). The average waiting time and average response time of CEHIPN with n = 2 are better than that of CEHIPN with n = 1, First come first serve, Shortest job first, Round-robin, Highest response ratio next, Varying Response Ratio Priority, Mid Average Round-Robin and Adaptive Round-Robin. For CEHIPN with n = 3, values are same to that of Shortest remaining time first. The number of context switches for all three cases of CEHIPN is same as that of Shortest remaining time first and Varying Response Ratio Priority.

In Figure 10 there is comparison of CEHIPN when the burst time is in decreasing order (see Figure 10). The average waiting time of CEHIPN for n = 1 is better than that of First come first serve, Round-robin, Highest response ratio next, Varying Response Ratio Priority, Mid Average Round-Robin and Adaptive Round-Robin. When comparing the average response time the value of CEHIPN with n = 1 is better than First come first serve, Shortest job first, Round-robin, Highest response ratio next, Varying Response Ratio Priority, Mid Average Round-Robin and Adaptive Round-Robin. For CEHIPN with n = 3, values are same to that of Shortest remaining time first. The number of context switches in both the cases of CEHIPN is same as that of Shortest remaining time first and Varying Response Ratio Priority.

In case IV when processes are arranged in increasing order of their burst time, the average waiting time, average response time and the number of context switches for all the considered algorithms are same.

7. Conclusions

From the results of our study it is inferred that CEHIPN has much better results in terms of average waiting time, and average response time, when compared with First come first serve, Shortest job first, Round-robin, Highest response ratio next, Varying Response Ratio Priority, Mid Average Round-Robin and Adaptive Round-Robin. Also for higher values of exponent “n”, CEHIPN gives same results as Shortest remaining time first, until there

is no inversion of execution order. On the other hand, the number of context switches associated with CEHIPN is same as for Shortest remaining time first. Also the proposed CEHIPN algorithm will never lead to starvation.

In the present study it is concluded that novel CEHIPN algorithm is better than First come first serve, Shortest job first, Round-robin, Highest response ratio next, Varying Response Ratio Priority, Mid Average Round- Robin and Adaptive Round-Robin in terms of average waiting time and average response time. For higher values of exponent “n” CEHIPN gives result same as Shortest remaining time first, until there is no inversion of execution order and also it will never lead to starvation.

Cite this paper

Amit Pandey,Pawan Singh,Nirayo H. Gebreegziabher,Abdella Kemal, (2016) Chronically Evaluated Highest Instantaneous Priority Next: A Novel Algorithm for Processor Scheduling. Journal of Computer and Communications,04,146-159. doi: 10.4236/jcc.2016.44013

References