ABSTRACT
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 access to computer resources efficiently.
Round 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 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 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 many 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 , 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 MeanRound Robin with Shortest Job First (IMRRSJF), Dynamic Round Robin with ControlledPreemption (DRRCP), Half-Life Variable Quantum Time RR (HLVQTRR) and CLASSICAL. Which in turn, 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
Acknowledgment…………………………………………………………………………………………………………. 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 THEORETICAL 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
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 TECHNIQUES…… 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
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 Criticism 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
INTRODUCTION
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 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 the available central Processing Unit (CPU).
Certain CPU scheduling techniques or algorithms have been developed. The overall goal of these algorithms is to: maximize , 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.
REFERENCES
Abur, M. Muhammed, A. Danjuma, S. and Abdullahi, S.(2011). A Critical Simulation of CPUScheduling Algorithm Using Exponential Distribution. ( IJCSI) International Journalof Computer Science Issues, Vol. 8, Issue 6, No 2, ISSN (Online): 1694-0814.pp 201-206
Agha A.E.A and Jassbi S.J (2013).A New Method to Improve Round Robin SchedulingAlgorithm with Quantum Time Based on Harmonic-Arithmetic Mean.moderneducation and computer science PRESS DOI:10,5815/ijitcs. pp. 56-62
Banerjee, P., Banerjee, P. and DhalS.S. (2012a) Comparative Performance Analysis of AverageMax Round Robin Scheduling Algorithm using Dynamic Quantum time with RoundRobin Scheduling Algorithm using static Quantum time, International Journal ofInnovative Technology and Exploring Engineering (IJITEE). Volume-1. pp. 56-62.
Banerjee, P., Banerjee, P. and DhalS.S. (2012b). Performance Evaluation of a New ProposedAverage Mid Max Round Robin Scheduling Algorithm with Round Robin SchedulingAlgorithm, International Journal of Advanced Research in Computer Science andSoftware Engineering, Volume 2, ISSN:2277 128X. pp.143-151.
Banks J. S., Carson J.S., Nelson B. L., Nicol D.M., (2005).Discrete-Event System SimulationFourth Edition.
Behera H.S., Mohanty R. and Nayak D. (2010).A New Proposed Dynamic Quantum WithRe-Adjusted Round Robin Scheduling Algorithm and its Performance Analysis.
StudentsandScholarship Team.
Be the first to comment