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.
TABLE OF CONTENTS
Declaration ……………………………………………………………………………………………………………………. iii
Certification ………………………………………………………………………………………………………………….. iv
Dedication ……………………………………………………………………………………………………………………… v
Acknowledgement …………………………………………………………………………………………………………. vi
Abstract ……………………………………………………………………………………………………………………….. vii
Table of Contents …………………………………………………………………………………………………………. viii
List of Figures ……………………………………………………………………………………………………………….. xi
List of Tables ………………………………………………………………………………………………………………. xiii
List of Abbreviations ……………………………………………………………………………………………………….. i
CHAPTER ONE: INTRODUCTION …………………………………………………………………………….. 1
1.1 BACKGROUND OF THE STUDY …………………………………………………………………….. 1
1.2 PROBLEM STATEMENT …………………………………………………………………………………. 4
1.3 JUSTIFICATION OF THE STUDY ……………………………………………………………………. 5
1.4 AIM AND OBJECTIVES …………………………………………………………………………………… 5
1.5 SCOPE …………………………………………………………………………………………………………….. 6
1.6 METHODOLOGY …………………………………………………………………………………………….. 6
CHAPTER TWO: LITERATURE REVIEW …………………………………………………………………… 8
2.1 THEORITICAL FRAME WORK ……………………………………………………………………….. 8
2.2 MULTIPROGRAMMING ………………………………………………………………………………… 11
2.3 SCHEDULING ……………………………………………………………………………………………….. 12
2.3.1 Job Scheduling Versus Process Scheduling …………………………………………………… 12
2.4 PROCESS SCHEDULER …………………………………………………………………………………. 13
2.5 JOB AND PROCESS STATUS …………………………………………………………………………. 15
ix
2.6 PROCESS CONTROL BLOCKS ………………………………………………………………………. 18
2.6.1 Process Identification …………………………………………………………………………………. 18
2.6.2 Process Status……………………………………………………………………………………………. 19
2.6.3 Process State …………………………………………………………………………………………….. 19
2.6.4 Accounting ……………………………………………………………………………………………….. 20
2.7 PCBs AND QUEUING …………………………………………………………………………………….. 21
2.8 PROCESS SCHEDULING POLICIES ………………………………………………………………. 22
2.9 PROCESS SCHEDULING ALGORITHMS ……………………………………………………….. 25
2.9.1 First-Come First Served ……………………………………………………………………………… 25
2.9.2 Shortest Job Next ………………………………………………………………………………………. 27
2.9.3 Priority Scheduling ……………………………………………………………………………………. 29
2.9.4 Shortest Remaining Time …………………………………………………………………………… 30
2.9.5 Round Robin …………………………………………………………………………………………….. 33
2.10 STATIC RR VERSUS DYNAMIC RR SCHEDULING TECHNIQUE ………………. 37
2.11 CONTEXT SWITCHING ……………………………………………………………………………… 38
2.12 REVIEW OF VARIOUS DYNAMIC RR CPU SCHEDULING TECHNIQUE …… 39
CHAPTER THREE: DESIGN OF A MODIFIED MEDIAN ROUND ROBIN ALGORITHM 46
3.1 INTRODUCTION ……………………………………………………………………………………………. 46
3.2 MMRRA ALGORITHM…………………………………………………………………………………… 48
3.3 MMRRA FLOW CHART …………………………………………………………………………………. 49
3.4 EVALUATION: CLASSICALRR, IRR, IMRR, HLVQTRR, DRRCP & MMRRA .. 50
3.4.1 Generated data from the proposed algorithm …………………………………………………. 50
3.4.2 Generated data from DRRCP………………………………………………………………………. 62
3.4.3 Generated dada from IMRRSJF…………………………………………………………………… 71
x
CHAPTER FOUR: EVALUATION OF THE DESIGNED MMRRA ………………………………. 80
4.1 INTRODUCTION ……………………………………………………………………………………………. 80
4.2 DESCRIPTION OF THE SIMULATION …………………………………………………………… 80
4.3 PSEUDOCODE FOR THE SIMULATION ………………………………………………………… 82
4.4 EVALUATION CRITERIA ……………………………………………………………………………… 82
4.5 ALGORITHM EVALUATION …………………………………………………………………………. 84
4.6 DISTRIBUTION FUNCTION USED ………………………………………………………………… 85
4.7 ALGORITHM FOR THE EXPONENTIAL DISTRIBUTION …………………………….. 86
4.8 THE BEST WAY OF CHOOSING PERCENTAGE (for a method) ………………………. 86
4.9 PRESENTATION OF RESULTS. ……………………………………………………………………… 89
4.10 DISCUSSION OF RESULTS. ……………………………………………………………………….. 93
CHAPTER FIVE: SUMMARY, CONCLUSION AND RECOMMENDATION ……………….. 97
5.1 SUMMARY ……………………………………………………………………………………………………. 97
5.1.1 Advantage of MMRRA over IMRRSJF ……………………………………………………….. 98
5.1.2 Advantage of MMRRA over HLVQTRR……………………………………………………… 99
5.1.3 Advantage of MMRRA over DRRCP ………………………………………………………… 100
5.1.4 Advantage of MMRRA over IRR ………………………………………………………………. 101
5.1.5 Some Major Challenges of DYNAMIC RR Algorithms. ………………………………. 101
5.1.6 Critisism With Respect To Context Switching On Most Of the proposed Round Robin Algorithms reviewed …………………………………………………………………………………… 103
5.2 CONCLUSION ……………………………………………………………………………………………… 104
5.3 RECOMMENDATION ………………………………………………………………………………….. 105
REFERENCES …………………………………………………………………………………………………………… 106
Appendix : Source code ………………………………………………………………………………………………. 111
xi
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.
2
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
3
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.
4
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.
5
1.3 JUSTIFICATION OF THE STUDY
So far, a lot of research papers having excellent ideas on dynamic RR algorithms have been published eg IRR, HLVQTRR etc. But most of these papers only considered average waiting time, average turnaround time and number of context switching as the criteria for comparison and evaluation. They did not bother to include other criteria like multiprogramming, response time and so on. Since dynamic RR has proven to provide better results, a new dynamic RR CPU scheduling algorithm should be developed that will provide better solutions to both the classical RR and most of the proposed dynamic RR algorithms that were reviewed. The evaluation would be done analytically and also through the use of simulation on the following criteria: average waiting time; average turnaround time; number of context switching; response time; and priority on shorter jobs. Random variable will be generated using exponential distribution function to perform the analysis. In general, the concept of CPU scheduling would be thoroughly presented to serve as a learning resource material.
1.4 AIM AND OBJECTIVES
The aim of this work is to propose a better solution to the classical and most of the dynamic RR CPU scheduling algorithm. The basic objectives are:
1. Develop a new Dynamic RR algorithm. “Modified Median Round Robin Algorithm”
(MMRRA)
6
2. Implement a system that will help in minimizing the overall waiting time, turnaround time, number of context switching and response time of processes.
3. Compare the proposed algorithm against five selected dynamic RR CPU scheduling algorithm.
1.5 SCOPE
This research work would focus on the scheduling algorithm for Round Robin technique. Thereby, developing a framework that will make fair consideration to shorter jobs on the queue. Many research papers with excellent ideas on RR scheduling have been published. But most of these papers focused on only average waiting time, average turnaround time and number of context switching as the criteria for comparison and evaluation. A new dynamic RR CPU scheduling algorithm would be proposed so as to provide better solutions to both the classical RR and most of the proposed dynamic RR algorithms that were reviewed. The evaluation shall be done analytically and also through the use of simulation on the following criteria: average waiting time; average turnaround time; number of context switching; average response time and priority on shorter jobs.
1.6 METHODOLOGY
The approaches and series of steps to be taken in actualizing our research objectives are as follows: i Random variables are generated using Exponential distribution ii Visual basic programming language 6.0 is used in writing the program.
iii MMRRA was evaluated analytically and through simulation against the classical RR,
7
IRR, IMRR, DRRCP and HLVQTRR. iv The result of each run of the simulator is also represented graphically using column graph. v The results of the evaluation are plotted using Microsoft excel 2007. Three data set have been used for the analysis. i The first set has been generated by the proposed algorithm ii The second set are the data set used in DRRCP. iii The third set are the data set used in IMRRSJF. Reason for using the data set in DRRCP and IMRRSJF is because MMRRA borrowed some few ideas but not exactly of these two (2) algorithms. Therefore, there is need to use their own data set for analysis.
8
Do you need help? Talk to us right now: (+234) 08060082010, 08107932631 (Call/WhatsApp). Email: [email protected].
IF YOU CAN'T FIND YOUR TOPIC, CLICK HERE TO HIRE A WRITER»
