ABSTRACT
Scheduling is the technique of deciding which process is given control of a computer resource at
a particular time. Processes are numerous while resources- such as the central processing unit
(CPU), bandwidth and memory among others – are scarce. It therefore becomes necessary for
scheduling to be done. Since there is no optimal scheduling algorithm, an algorithm becomes
suitable based on the scheduling criteria that the operating system is designed to uphold. This
thesis focuses on the development and evaluation of the performance of a CPU scheduling
algorithm that achieves service timeliness by minimizing the penalty ratio variance. The
algorithm inherits properties from the round robin scheduling algorithm. The model was tested
and evaluated for performance alongside the Round Robin algorithm and some modifications of
it, and was found to perform better than these other algorithms on penalty ratio variance
minimization. This therefore implies that the turnaround time of a process can be determined
before time; and can be evaluated to be a multiple of its penalty ratio.
TABLE OF CONTENTS
Declaration…………………………………………………………………………………………………………………….. i
Certification …………………………………………………………………………………………………………………. ii
Dedication …………………………………………………………………………………………………………………… iii
Acknowledgement ……………………………………………………………………………………………………….. iv
Abstract …………………………………………………………………………………………………………………………v
Table of Contents ………………………………………………………………………………………………………… vi
List of Tables …………………………………………………………………………………………………………….. viii
List of Figures ………………………………………………………………………………………………………………. ix
List of Abbreviations ……………………………………………………………………………………………………..x
1.0 GENERAL INTRODUCTION …………………………………………………………………………………..1
1.1 Background ………………………………………………………………………………………………………………1
1.2 Research Questions …………………………………………………………………………………………………..3
1.3 Motivation of the Study ……………………………………………………………………………………………..3
1.4 Aim of the Study………………………………………………………………………………………………………..3
1.5 Objectives of the Study ………………………………………………………………………………………………3
1.6 Methodology …………………………………………………………………………………………………………….4
1.7 Scope…………………………………………………………………………………………………………………………4
1.8 Significant Contributions ………………………………………………………………………………………….4
1.9 Organization of the Thesis …………………………………………………………………………………………4
2.0 LITERATURE REVIEW …………………………………………………………………………………………6
2.1 Introduction to Operating Systems …………………………………………………………………………….6
2.2 Processes …………………………………………………………………………………………………………………..7
2.3 Scheduling ………………………………………………………………………………………………………………10
2.3.1 Long-term or admission scheduler…………………………………………………………………………….12
2.3.2 Mid-term or memory scheduler ………………………………………………………………………………..12
2.3.3 Short-term or CPU scheduler ……………………………………………………………………………………14
2.3.4 Performance criteria for scheduling algorithms (Scheduling criteria) …………………………….14
2.4 Scheduling Algorithms in Operating Systems ……………………………………………………………16
2.4.1 First come first served (FCFS) ………………………………………………………………………………….16
2.4.2 Shortest job first (SJF) …………………………………………………………………………………………….17
2.4.3 Round robin (RR) ………………………………………………………………………………………………….19
2.4.4 Priority scheduling ………………………………………………………………………………………………….20
2.4.5 Highest response ratio next (HRRN) ……………………………………………………………………….. 21
2.5 Related Work ……………………………………………………………………………………………………….. 22
3.0 MINIMIZED PENALTY RATIO VARIANCE FRAMEWORK …………………………….. 26
3.1 Introduction …………………………………………………………………………………………………………… 26
3.2 Approach of the Model ………………………………………………………………………………………….. 27
3.3 The Minimized Penalty Ratio Variance Algorithm (MPRV) ……………………………………. 28
3.3.1 The proposed model ………………………………………………………………………………………………. 29
3.3.2 MPRV algorithm …………………………………………………………………………………………………… 30
2.3.3 Flowchart of the proposed model ……………………………………………………………………………. 32
4.0 IMPLEMENTATION AND TEST OF THE MINIMIZED PENALTY RATIO
VARIANCE ALGORITHM ……………………………………………………………………………………….. 33
4.1 Introduction ………………………………………………………………………………………………………….. 33
4.2 Case Assumption ……………………………………………………………………………………………………. 33
4.3 System Requirements ………………………………………………………………………………………………33
4.3.1 Notepad++ …………………………………………………………………………………………………………….33
4.3.2 PHP Language ……………………………………………………………………………………………………….34
4.3.3 Simulation system specifications ………………………………………………………………………………34
4.4 Simulation Framework ………………………………………………………………………………………….. 34
4.5 Experiment Case Alongside Round Robin Algorithms …………………………………………….. 36
4.5.1 Classical round robin …………………………………………………………………………………………….. 37
4.5.2 Dynamic quantum re-adjusted round robin (DQRRR) …………………………………………………39
4.5.3 Improved round robin (IRR) ………………………………………………………………………………….. 41
4.5.4 New improved round robin (NIRR) …………………………………………………………………………. 43
4.5.5 Minimized penalty ratio variance algorithm …………………………………………………………….. 45
4.6 Results, Discussion And Conclusion ……………………………………………………………………….. 48
5.0 SUMMARY, CONCLUSION AND FUTURE WORK …………………………………………….. 54
5.1 Introduction …………………………………………………………………………………………………………….54
5.2 Summary ………………………………………………………………………………………………………………. 54
5.3 Conclusion …………………………………………………………………………………………………………….. 55
5.4 Future Work ………………………………………………………………………………………………………….. 55
References ………………………………………………………………………………………………………………….. 56
Appendix: PHP Source Codes for the MPRV Algorithm ………………………………………………
CHAPTER ONE
GENERAL INTRODUCTION
1.1 BACKGROUND
One of the main functions of the operating system is scheduling (Babu et al., 2012). By
switching the CPU among processes, the operating system can make the computer more
productive (Silberschatz et al, 2005). Hence, it has become an interesting and important field of
research in operating systems.
By way of definition, CPU scheduling can be defined as the art of determining which process to
run when there are multiple runnable processes, (Chaudhary et al.,2012). It also refers to the way
processes are assigned to run on the available CPU (Curtis et al., 2012).CPU scheduling
therefore involves selecting from the processes in memory that are ready to execute, and
allocating the CPU to one of them. A process is a program in execution.
CPU scheduling is not planning since there is no optimal solution; rather it is about balancing
goals and making difficult tradeoffs. A new scheduling algorithm either places emphasis on a
different goal or provides a simpler way to achieve the same goals as its predecessors. The only
bad scheduling policy is one that trades something for nothing or de-emphasizes one goal
without an improvement in another (Meehean, 2011). There exist various CPU scheduling
algorithms, each one with its advantages and disadvantages (Lenka and Ranjan, 2012). In order
to measure and compare the efficiency of a scheduling algorithm some criteria were suggested
(Das et al., 2012). Which criteria are used for comparison can make a substantial difference in
which algorithm is judged to be the best.
This research focuses on minimizing the variance of penalty ratio of the processes. The penalty
ratio of a process is the elapsed time from running the process divided by the sum of the CPU
and I/O demands of the job. It is also called the response ratio and is a factor of the turnaround
time (Sharma et al., 2012). Another area of concentration in this research will be with making
sure that every process makes progress, thereby preventing starvation. Starvation is a condition
in which process are made to wait indefinitely for allocation to required resources.
Expected values for turnaround time and waiting time which may or may not be met up with
after the processes have been executed will be generated and worked with. However, in the long
run, the variance of the penalty ratio values will be minimized. Comparison of results will be
done with the following round robin scheduling algorithms: classical Round Robin (RR),
Dynamic Quantum Re-adjusted Round Robin (DQRRR), Improved Round Robin (IRR) and
New Improved Round Robin (NIRR) algorithms. This is so because the proposed algorithm is a
modification of the round robin algorithm.
The results to be compared will be popular CPU scheduling criteria, namely: average waiting
time, average turnaround time and context switching. However, two other scheduling uncommon
scheduling criteria will also be introduced and used as a basis of comparison. These are: average
penalty ratio and penalty ratio variance.
1.2 RESEARCH QUESTIONS
a. How much does the proposed algorithm gain on the minimized penalty ratio variance?
b. What are the trade-offs of the proposed algorithm?
1.3 MOTIVATION OF THE STUDY
Processes that are run using the round robin algorithm have high turnaround time (Abdullahi,
2012), which implies a high variance in penalty ratio values. However, if this variance is
reduced, the quality of service experienced by the user can be maximized (Ye et al, 2005).
1.4 AIM OF THE STUDY
The aim of the research is to design and implement an algorithm that minimizes the variance of
the penalty ratio of the processes in the computer system.
1.5 OBJECTIVES OF THE STUDY
The objectives of the research are to:
a. Modify the round robin scheduling algorithm such that it minimizes the variance of the
penalty ratio.
b. Implement the Minimized Penalty Ratio Variance algorithm.
c. Evaluate other modifications to the round robin algorithm, namely RR, IRR, NIRR,
DQRRR.
1.6 METHODOLOGY
The approaches that will be applied in achieving our aim and objectives in this research are to:
a. Make extensive study of scheduling algorithms.
b. Develop the proposed algorithm.
c. Implement the proposed algorithm using the PHP programming language.
d. Evaluate the proposed algorithm by comparing it with already existing CPU scheduling
algorithms.
e. Summarize and recommend future research.
1.7 SCOPE
The work is limited to the round robin CPU scheduling algorithm. The proposed algorithm is a
modification of the classical round robin algorithm.
1.8 SIGNIFICANT CONTRIBUTIONS
The research hopes to make a meaningful contribution in the problem of high turnaround times
generated by the Round Robin algorithm. In minimizing the penalty ratio variance, the Round
Robin algorithm uses the penalty ratio of each process to determine their turnaround time,
thereby achieving service timeliness.
1.9 ORGANIZATION OF THESIS
In chapter two, existing literature and researches conducted in the field of process scheduling are
discussed.
In chapter three, the methodologies adopted to design the proposed framework for the Minimized
Penalty Ratio Variance Algorithm are discussed.
In chapter four, the implementation and testing of the proposed algorithm is presented.
In chapter five, the summary of the work and proposed areas for future work are presented.
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»
