# Genetic Algorithm Optimal Approach For Scheduling Processes In Operating System

DOI : 10.17577/IJERTV2IS50396

Text Only Version

#### Genetic Algorithm Optimal Approach For Scheduling Processes In Operating System

Manu Sharma Shobhit University Meerut

Preeti Sindhwani Assistant Professor N.I.E.T.

Gr. Noida

Vijay Maheshwari Assistant Professor Shobhit University Meerut

ABSTRACT

To enhance the performance of CPU, Many scheduling approaches are used to get maximum throughput in terms of scheduling the processes, waiting in the ready queue in minimum waiting time. This paper presents the genetic algorithm approach to provide the optimal solution for scheduling the processes and compares the results with other traditional scheduling algorithms. CPU scheduling is an NP hard problem. Genetic algorithm provides the optimal solution to these NP hard problems. These algorithms handle a population of possible solutions and the selection of these solutions is based on the fitness function. Crossover & other operators are used to generate new population.

General Terms

Genetic Algorithm, NP hard, Crossover, Inversion

Keywords

Ordered Crossover

1. INTRODUCTION

CPU Utilization and Throughput can be maximized by effectively allocating processes to the processor. It requires an optimal solution for allocating these processes in an Operating System. Genetic Algorithm uses recombination operators, able to mix good characteristics from different solutions and it is considered helpful to find optimal solutions of the problem. Genetic Algorithm uses genetics as its model of problem solving. Genetic Algorithm handles a population of possible solutions. Each solution is represented through a chromosome. Select two parent chromosomes from a population according to their fitness (the better fitness the bigger the chance to get selected.) with a crossover probability crossover the parents to form new offspring. Each string undergoes with the inversion operator[1].

2. Genetic Algorithm

Steps involved in genetic algorithm used in this paper are:

[Start] Generate Random Population of n chromosomes (Suitable solutions)

[Fitness] Evaluate the Fitness F(x) of each chromosome x in the population.

[New Population] Create new Population by Repeating following steps until the new population is complete.

[Selection] Select to Parent chromosomes from a population according to their Fitness.

[Crossover] With a crossover probability crossover the parents to form a new offsprings.

[Replace] Place new offspring in the new population.

D S

D S

Populations (Chromosomes)

Populations (Chromosomes)

[Termination] If the End condition is satisfied, stop and return the best solution in the current population.

New generation ecoded

tring

offspring

Parents n

Parents n

Genetic Operations

Genetic Operations

Evaluation (Fitness Function)

Evaluation (Fitness Function)

parents

calculation

Reproduction

Selection

Selection

Mate

Fig 1: Genetic Algorithm Cycle

1. Comparison of Genetic Algorithm with other Traditional optimization techniques

• Genetic algorithms operate with coded versions of the problem parameters rather than parameter themselves i.e. GA works with the coding of the solution set not with the solution itself.

• Almost all conventional optimization techniques search from a single point but GAs always operate on a whole population of points (strings).GA uses population of solutions rather than a single solution. This plays a major role to the robustness of GAs. It improves the chance of reaching the global optimum.

• GA uses fitness functions for evaluation rather than derivatives. They can be applied to any kind of continuous or discrete optimization problem[3].

3. Assumption for CPU scheduling problem

Consider N processes with their static Burst time. These processes have been processed on CPU to process in such a way that their waiting time should be minimized. The initial population of individual solutions is randomly generated. Processes are waiting in the ready queue i.e. gene pool.

1. Fitness Evaluation

For calculating fitness the chromosome has to be first decoded and abject function has to be evaluated. The fitness not only indicates how good the solution is, but also corresponds to how close the chromosome is to the optimal one (Lesser the Burst time of process more fit it will be).

Fitness F(x) = (i =1, 2, 3…..N)

.Wi is the waiting time of processes.

2. Selection

In this paper the selection process used is based on Roulette Wheel Process. The expected value of an individual is the fitness divided by the actual fitness of the population. The wheel spins N times, where N is the number of individuals in the population[2]. On each spin, the individual under the wheel marker is selected to be in the gene pool of parents for next generation.

• Sum the total expected value of the individuals in the population. Let it be T.

• Repeat N times.

> Choose a random integer r between 0 and T.

> Loop through the individuals in the population, summing the expected value puts the sum over this limit is the one selected.

Let F(max) be the fitness of the currently available best string. If the next string has fitness of F(x) such that F(x)> F (max), then new string is selected otherwise it is selected with Boltzmann Probability:-

P=

Where, T = T0 (1-)^k and k = (1+100*g/G) g=current generation number; G=Max Value of g.

= [0,1] ; T0 =[5,100]

Final state is reached when computation approaches 0 value of T.

3. Crossover

 Parent1 : 4 2 1 | 3 6 5 Parent2 : 2 3 1 | 4 5 6 Offspring: 4 2 1 4 5 6
 Parent1 : 4 2 1 | 3 6 5 Parent2 : 2 3 1 | 4 5 6 Offspring: 4 2 1 4 5 6

Two mating chromosomes are cut once at corresponding points and the sections after the cut are exchanged. Crossover point is selected randomly along the length of the mated string and bits next to the cross points are exchanged[5].

In this paper Modified Ordered Crossover (MOX) is used.

1. Ordered Crossover (OX)

For given two parent chromosomes, two random crossover points are selected partitioning them into left, middle and right section from parent 1 and its middle section is determined by the genes in the middle section of parent 1 in the order in which the values appear in the parent 2. Similar process is applied to offspring 2.

Parent 1 : 4 2 | 1 3 | 6 5

Parent 2 : 2 3 | 1 4 | 5 6

 Offspring 1 : 4 2 | 3 1 | 6 5 Offspring 2 : 2 3 | 4 1 | 5 6 Modified OX

In modified OX two crossover points are the processes having the two longest burst time.

2. Inversion Operator

Two points are selected along the length of the chromosome, the chromosome is cut at those points and the end of the selection cut, gets reversed (switched or swapped). In this paper linear+ end inversion operator is used[4], which minimizes the property of linear inversion to disrupt the alleles present near the center of the string disproportionately to those of alleles present near the ends.

1 2 3 4 5 6 7 8 9 10

4 8 ^ 6 2 7 9 ^ 1 10 5 3

4 8 9 7 2 6 1 10 5 3

The gene is to be used in fitness function the same as before inversion and it remains same as after inversion operation also.

3. Replacement

After inversion new chromosome is generated and is added to the existing population. Fit chromosomes are again selected to produce another new offspring. This process continues until we not get the optimal solution[6]. New population always replaces the existing population to survive.

4. Termination

Multiple termination conditions are used in genetic algorithm. We will terminate the algorithm by equal fitness for the fittest selected chromosomes in respective iteration.

4. Pseudo code of GA

1. Begin /* MOX GA Algorithm*/

2. Generate random population of N chromosomes (possible solutions)

3. Evaluate Fitness F(x) of each chromosome x in the population using fitness function

Fitness F(x) = (i =1, 2,3…..N)

4. WHILE NOT terminate Do

BEGIN /* Produce New generation */

5. Select two best fitted parents from the existing population using Roulette Wheel selectio

6. Crossover the two individuals by apply Modified OX using OX_C( ) function.

7. linear +end inversion operator, Inversion( ) to generate offspring.

8. Compute the fitness of offspring and add the offspring into the new Population using Replace( ) function

END

9. IF Termination criteria is matched THEN end:= TRUE

end end end

5. Experimental Description:

Solutions are randomly generated to form an initial population. New generations are reproduced by crossover. Fittest solutions are chosen as parents to reproduce the offsprings for new generation. Fitness function is evaluated based on FCFS algorithm.

Suppose there are 4 jobs. The number of possible sequences are 4!. Total 10 sequences are selected out of 24 for 4 jobs. Consider the crossover point is 2. Suppose following two individuals are fit to generate next generation.

3 1 2 4 and 4 3 5 1

After cross over 3 1 5 1

This offspring is not valid because 4 is not there in new individual and job 1 appears twice such

individual is discarded .So to avoid this, we are using the modified OX . In the modified crossover we get proper order individual. let us assume two individual which are marked as fit and use for the next generation .

5 1 2 4 and 3 4 2 1

After modified OX 5 1 3 4

this individual is accepted because there is no repetition of any job.

6. Simulation Results:

Figure 1 shows the comparison graphs of various scheduling algorithms finding that GA based scheduling algorithm gives the same result as in SJF in some cases. Although SJF is optimal, it can not be implemented at the level of short term CPU scheduling[2]. There is no way to know the length of the next CPU burst. Hence GA based CPU scheduling algorithm can be implemented to find the near to optimal solution.

Table 1 shows the average waiting time of FCFS, SJF,RR and GA based scheduling algorithm for 4 processes with their burst times. Waiting time of processes has been minimized in SJF and GA based algorithms, so that the maximum CPU utilization can be achieved

Figure1. Comparison of various scheduling algorithms Table1: Result Analysis

 S.N. Burst time of processes (P1,P2,P3,P4) FCFS Round Robin SJF GA 1. 48,28,28,15 134 128 71 74 2. 21,25,31,42 167 99 77 77 3. 20,40,27,23 117 106 70 73 4. 29,10,30,22 99 91 61 61 5. 34,19,35,49 118 98 88 88 6. 8,8,36,48 82 74 52 52 7. 20,20,28,17 98 95 57 57 8. 49,40,49,46 168 157 135 135 9. 25,40,34,35 129 109 94 94 10. 45,6,45,32 126 123 83 83 Total Avg. Waiting Time 123.8 108 78.8 79.4
7. Conclusion & future scope:

Although SJF is optimal, it can not be implemented at the level of short term CPU scheduling. There is no way to know the length of the next CPU burst. Hence GA based CPU scheduling algorithm can be implemented to find the optimal

solution. Research can be extended so that GA can be implemented for dynamic process scheduling. The performance can also be increased by apply other GA based operators to this problem.

8. References

1. Genetic Algorithm approach to Operating System process scheduling Problem Dr.Rakesh Kumar, Reader Department of Computer Science and Application, Kurkshetra university, Haryana, India.

2. Genetic Algorithm approach to optimal CPU scheduling Problem Preeti Sindhwani, Assistant Professor , Noida Institute of Engg. & Technology, Gr. Noida, India

3. Introduction to genetic algorithm by S.N.Shivanandnam and S.N.Deepa.

4. L.M.Schmitt, Fundamental Study Theory of Genetic Algorithms , International Journal of Modelling and Simulation Theoretical Computer Science 259, 2001, 1 61.

5. L. Davis, "Applying Adaptive Algorithms to Epistactic Domains", in Proceedings of the Int. Joint Conf. on Artificial Intelligence (IJCAI'85), Los Angeles, CA, pp. 162-164.

6. Holland, J.H., 1975. Adaptations in natural and artificial systems, Ann Arbor: The University of Michigan Press.

Manu Sharma is pursuing her M.Tech. from Shobhit University,Meerut.She is also lecturer in Noida Institute Of Engineering & Technology, Gr. Noida. Her research interest includes Genetic algoritms & problem solving.

Preeti Sindhwani did her M.Tech. from N.C. College of Engineering, Israna(Panipat). She is gold medalist in M.Tech. She is also Assistant Professor in Noida Institute of Engineering & Technology,Gr. Noida. Her research interest includes approximation and optimization based algorithms.

Vijay Maheshwari did his M.Tech. from Shobhit University, Meerut. He is also an Assistant Professor in Shobhit University,Meerut. His research interest includes Genetic lgorithms & Neural Network Design.