DESIGN AND IMPLEMENTATION OF A MODIFIED MEDIAN ROUND ROBIN ALGORITHM (DIMMRRA)

Abstract

Central Processing Unit (CPU) scheduling involves a careful examination of pending processes to determine the most efficient way to service the requests. Several scheduling algorithms have been designed to arrange accesses to computer resources efficiently. Round robin scheduling algorithm (RRSA) is an attractive algorithm but suffers from the problem of time quantum determination. In the classical round robin algorithm, quantum time is fixed throughout the scheduling process. This static nature made it very difficult to optimize the algorithm. The only solution to this problem is to provide a quantum time that changes dynamically during execution. Major challenges of dynamic round robin schedulers reported in the literature are: they do not include Average Response Time as a criterion for comparison and they do not bother much on preempting processes with negligible completion time after executing for a given time quantum leading to an increase in the number of context switches. This research proposed an algorithm, the Modified Median Round Robin (MMRRA), with a dynamic time quantum aimed at reducing the overhead of the RRSA. The proposed algorithm was implemented and evaluated against the following five algorithms in the literature: Improved Round Robin (IRR), Improved Mean Round Robin with Shortest Job First (IMRRSJF), Dynamic Round Robin with Controlled Preemption (DRRCP), Half Life Variable Quantum Time RR (HLVQTRR) and CLASSICAL RR. Which in turns, proved to perform better in terms of AWT, ATAT and NCS. But, in terms of ART, HLVQTRR has the best result but still the result for MMRRA was not bad.

CHAPTER ONE

INTRODUCTION

1.1 BACKGROUND OF THE STUDY

Process scheduling algorithm has been an interesting field of study in Operating Systems. Scheduling is a key concept in computer multitasking, multiprocessing and real-time operating system designs. The operating system uses some sort of scheduling techniques to allocate resources to processes in the ready queue. Scheduling refers to the way processes are assigned to run on available Central Processing Unit (CPU). Certain CPU scheduling techniques or algorithms have been developed. The overall goal of these algorithms is to: maximize CPU utilization, reduce average waiting time and average turnaround time, reduce the number of context switching, increase throughput and try as much as possible to be fair to all processes. Processor Manager is in charge of allocating a single CPU to execute the jobs of those users.In a single user system, the processor is busy only when the user is executing a job but, at any other time it is idle. Processor Management in this environment is simple. However, when there are many users with many jobs on the system (this is known as a multiprogramming environment), the processor must be allocated to each job in a fair and efficient manner, which can be a complex task. The processor, also known as the CPU (Central Processing Unit), is the part of the machine that performs the calculations and executes the programs.

Multiprogramming requires that the processor be allocated to each job or to each process for a period of time and de-allocated at an appropriate moment. If the processor is de-allocated during a program‟s execution, it must be done in such a way that it can be restarted later as easily as possible, this is a delicate procedure. A single processor can be shared by several jobs or several processes, but if, and only if, the operating system has a scheduling policy, as well as a scheduling algorithm, to determine when to stop working on one job and proceed to another. Some examples of these scheduling algorithms are:

i First Come First Serve (FCFS): Attends to processes in their order of arrivals.

ii Shortest Job First (SJF): Attends to processes in an increasing order of their burst time.

iii Round Robin (RR): Gives an equal time slice (Quantum) to every process in the ready queue in a circular manner. If the Quantum time is greater or equal to the burst time of the process it will run to completion without being preempted. Otherwise, the process must be preempted after it must have exhausted its time Quantum and then return to the tail of the ready queue to take turn.

iv Priorities scheduling: Here, processes are attended to based on their priorities.

The preemptive nature of Round Robin scheduling can only suggest that it is designed to handle time sharing systems. As bad as context switching may be, it is highly needed in time sharing systems, although too much context switching is an overhead. Another issue is what should be the Quantum time? This is even more serious because smaller Quantum time will increase the number of context switching, and a larger value will automatically change the system to ordinary FCFS. Therefore, an optimal Quantum time is what we need. In the Classical RR the quantum time is static. This is why it is sometimes called Static RR. Here, the quantum time is gotten from the average of the processes‟ burst time in the ready queue and remain constant throughout the entire procedure. The static nature made it difficult for maximum improvement, and as such research on Dynamic RR is on. The idea of dynamic RR is to use more than one different quantum time for processes depending on their circumstances. Some of the proposed dynamic RR are: Improved Mean Round robin with shortest job first scheduling, Self-Adjustment time quantum in Round Robin algorithm depending on Burst time of the New Running Processes (SARR), An Improved Round Robin CPU Scheduling Algorithm (IRR), A new Round Robin Based Scheduling Algorithm for Operating System, Dynamic Quantum Using the Mean (An Algorithm), Half-life variable quantum time RR (HLVQTRR), Dynamic Round Robin with Control Preemption (DRRCP) etc. So far, from the various proposed Dynamic RR, it has been proven to be more efficient than the Classical RR when compared and evaluated on the basis of number of context switching, average waiting time and average turnaround time. The purpose of this research is to develop a new dynamic RR algorithm base on the ideas gotten from the different scheduling algorithms like IRR, IMRR, HLVQTRR, DRRCP etc. that will provide answers to some of the critical setbacks experienced in the classical RR and the various proposed dynamic RRs. Comparative analysis would be carried out on Six RR algorithms to enable this research work reach a meaningful conclusion.

1.2 PROBLEM STATEMENT

The greatest challenge in RR is Quantum time. That is, what should be the Quantum time? In the classical RR, Quantum time is fixed throughout the scheduling process. This static nature made it very difficult to optimize the algorithm. In order to reduce the number of context switching, average waiting time and average turnaround time, we must find a dynamic Quantum time. This will provide a Quantum time that change automatically according to a circumstance so as to improve the general performance of the system. Each of the proposed dynamic RR performs better when compared with static RR on the basis of number of context switching, average waiting time and average turnaround time. If that is the case, which among them should be implemented and why? In order to answer the above question, the Modified Median RR (MMRRA) was proposed. Another problem is that, most of these algorithms do not care to include ART as a criteria for comparison. And, they do not bother much on preempting processes with negligible left over. Mis-calculation of number of context switching (NCS) is another problem to most of these algorithms. The MMRRA would be compared against the classical RR, Improved Round Robin(IRR), Improved Mean Round Robin(IMRR), Half Life Variable Quantum Time RR(HLVQTRR) and Dynamic Round Robin with Controlled Preemption (DRRCP) using analytic and simulation techniques.

Department: Computer Science (M.Sc)

Format: MS Word

Chapters: 1 - 5, Preliminary Pages, Abstract, References

No. of Pages: 139

NB: The Complete Thesis is well written and ready to use.

Price: 20,000 NGN

In Stock

Buy Now

M.SC Thesis in Computer Science