ABSTRACT
The priority based CPU scheduling algorithm (i.e. Shortest Job First (SJF) or Priority Scheduling (PS)) is a kind of scheduling algorithm that assigns the CPU to processes based on the priority of each process. The shortcoming of both of these algorithms is starvation (i.e. starvation of processes with longer burst times in the case of SJF and starvation of processes with lower priorities in the case of PS). This dissertation proposes a new algorithm that introduces the concept of EFFICIENCY FACTOR which uses three properties which are priority, burst time and arrival time to compute one factor which is used to schedule processes in the case of the proposed Priority algorithm instead of only one factor that priority is in the case of traditional Priority algorithm and two properties which are burst time and arrival time to compute one factor which is used to schedule processes in the case of proposed Shortest Job First algorithm instead only one factor that is burst time in the case of traditional Shortest Job First algorithm. This proposed algorithm was implemented and benchmarked against SJF, PS and the Optimum Service Time Concept for Round Robin Algorithm (OSTRR) by Saxena and Agarwal (2012) using three different statistical distributions (namely Normal, Uniform and Exponential Distributions) to generate the burst times of the processes, two different statistical distributions (namely Uniform and Exponential Distributions) to generate the priorities of the processes and also, uses Poisson Distribution to generate the arrival times of processes. It is observed that in the SJF category, the traditional SJF produced better Average Waiting Time (AWT), Average Turnaround Time (ATAT), Average Response Time (ART) and Waiting Time Variance Deviation (WTVD) compared with the proposed SJF. But they both produced the same Number of Context Switches (NCS). The proposed SJF produced better results compared with OSTRR with respect to AWT, ATAT, ART, NCS and WTVD. While in the PS category, the proposed Priority produced better AWT, ATAT, ART and WTVD compared to the traditional Priority
TABLE OF CONTENTS
TITLE PAGE………………………………………………………………………………………i
DECLARATION ……………………………………………………………………………………………………………. ii
CERTIFICATION …………………………………………………………………………………………………………. iii
DEDICATION ………………………………………………………………………………………………………………. iv
ACKNOWLEDGEMENT ……………………………………………………………………………………………….. v
ABSTRACT ………………………………………………………………………………………………………………….. vi
TABLE OF CONTENTS ………………………………………………………………………………………………. viii
LIST OF TABLES ………………………………………………………………………………………………………….. x
LIST OF FIGURES ……………………………………………………………………………………………………….. xi
LIST OF ABBREVIATIONS ………………………………………………………………………………………… xiii
CHAPTER ONE: INTRODUCTION ………………………………………………………………………………… 1
1.1 Background of the Study ……………………………………………………………………………………………… 1
1.2 Research Motivation and Goals ……………………………………………………………………………………. 2
1.3 Research Aim and Objectives ………………………………………………………………………………………. 2
1.4 Research Methodology ………………………………………………………………………………………………… 3
1.5 Contribution to knowledge …………………………………………………………………………………………… 5
CHAPTER TWO: LITERATURE REVIEW ……………………………………………………………………… 6
2.1 INTRODUCTION ………………………………………………………………………………………………………… 6
2.2 OPERATING SYSTEM ………………………………………………………………………………………………… 6
2.1.1 The Process State …………………………………………………………………………………………………. 7
2.1.2 CPU Scheduling Algorithms …………………………………………………………………………………….. 8
2.1.3 Performance Criteria ………………………………………………………………………………………….. 10
2.3 Waiting Time Variance ……………………………………………………………………………………………… 11
2.4 CPU Scheduling ………………………………………………………………………………………………………… 12
2.4.1 The importance of priority in CPU Scheduling ………………………………………………………… 13
2.5 Review of Priority Based CPU Scheduling Algorithms ………………………………………………… 13
2.6 Observations on the Review Literatures Showing the Knowledge Gap Addressed by the Dissertation …………………………………………………………………………………………………………………………… 18
2.7 Waiting Time Variance (WTV): …………………………………………………………………………………. 19
CHAPTER THREE: MATERIALS AND METHOD ………………………………………………………… 21
3.1 Introduction ………………………………………………………………………………………………………………. 21
3.2 Assumption ……………………………………………………………………………………………………………….. 21
ix
3.3 Efficiency Factor ……………………………………………………………………………………………………….. 21
3.4 The pseudo code of the Proposed Priority Based CPU Scheduling Algorithms ……………………. 23
3.5 Proposed Algorithm for Priority CPU Scheduling Algorithm………………………………………. 27
3.6 Proposed Algorithm for Shortest Job First CPU Scheduling Algorithm ………………………. 30
3.7 Time Complexity of the Proposed Priority Based CPU Scheduling Algorithm ……………………. 33
CHAPTER FOUR: RESULTS AND DISCUSSION …………………………………………………………. 35
4.1 Introduction ………………………………………………………………………………………………………………… 35
4.2 Illustrative Examples …………………………………………………………………………………………………… 35
4.2.1 Shortest Job First (SJF) ………………………………………………………………………………………….. 36
4.2.2 Priority Scheduling (PS) ………………………………………………………………………………………… 38
4.2.3 Proposed Shortest Job First ………………………………………………………………………………….. 39
4.2.4 Proposed Priority Scheduling ………………………………………………………………………………… 40
4.2.5 OSTRR ………………………………………………………………………………………………………………… 41
4.3 System Requirements …………………………………………………………………………………………………… 43
4.3.1 Experimental Setup…………………………………………………………………………………………….. 43
4.4 Results and Discussion ………………………………………………………………………………………………… 45
4.4.1 Results obtained using normal distribution to generate burst time ………………………………. 46
4.4.1.1 First category …………………………………………………………………………………………………… 47
4.4.1.2 Second category ……………………………………………………………………………………………….. 53
4.4.2 Results obtained using uniform distribution to generate burst time ……………………………… 58
4.4.2.1 First category …………………………………………………………………………………………………… 59
4.4.2.2 Second category ……………………………………………………………………………………………….. 65
4.4.3 Results obtained using exponential distribution to generate burst time ………………………… 70
4.4.3.1 First category …………………………………………………………………………………………………… 71
4.4.3.2 Second category ……………………………………………………………………………………………….. 77
CHAPTER FIVE: SUMMARY, CONCLUSION AND RECOMMENDATION ………………….. 85
5.1 Summary …………………………………………………………………………………………………………………… 85
5.2 Conclusion ………………………………………………………………………………………………………………… 85
5.3 Recommendation ……………………………………………………………………………………………………….. 88
REFERENCES …………………………………………………………………………………………………………….. 89
APPENDIX …………………………………………………………………………………………………………………………… 92
x
LIST OF TABLES
Table 3.1: Process Table ………………………………………………………………………………………………… 28
Table 3.2: Process Table for Priority CPU Scheduling Algorithm ……………………………………….. 30
Table 3.3: Process Table ………………………………………………………………………………………………… 31
Table 3.4: Process Table for Shortest Job First CPU Scheduling Algorithm …………………………. 33
Table 4.1: Process Table ………………………………………………………………………………………………… 35
Table 4.2: Comparative Table…………………………………………………………………………………………. 43
Table 4.3: Performance of Statistical Distributions in Generating Burst Times …………………….. 82
Table 4.4: Performance of Algorithms Based on Metrics Used in Comparing Them for First Category ………………………………………………………………………………………………………………………. 83
Table 4.5: Performance of Algorithms Based on Metrics Used in Comparing Them for Second Category ………………………………………………………………………………………………………………………. 84
xi
CHAPTER ONE
INTRODUCTION
This chapter discusses the introductory part of this dissertation which comprises the background of the study, research motivation and goals which stipulate the research questions for which the dissertation provides answers, the aims and objectives of the research work, the methodology that is followed in the research and the contribution which the dissertation makes to knowledge.
1.1 Background of the Study
The Central Processing Unit (CPU) is an important component of the computer system; hence it must be utilized efficiently. This can be achieved through what is called CPU scheduling (Oyetunji and Oluleye, 2009). CPU Scheduling refers to a set of policies and mechanisms to control the order of work to be performed by a computer system. The CPU scheduling is one of the most important tasks of the operating system (Mehdi et al, 2012). The need for a scheduling algorithm to achieve the efficiency of the CPU arises from the requirement for most modern systems to perform multitasking (execute more than one process at a time) and multiplexing (transmit multiple flows simultaneously). The basic idea is to keep the CPU busy as much as possible by executing a user process or job until it must wait for an event, and then switch to another process. In multiprogramming systems, when there is more than one runnable process (that is ready to run on the CPU), the operating system must decide which one to activate as shown in Figure 1.1. The decision is made by the part of the operating system called the scheduler, using a scheduling algorithm (Suri and Sumit, 2012).
2
Figure1.1: The Traditional Process State Diagram (Silberschatz,et al. 2006)
1.2 Research Motivation and Goals
Priority based CPU Scheduling Algorithms such as Shortest Job First Algorithm which assigns CPU to processes according to their burst times and Priority CPU Scheduling Algorithm which assigns CPU to processes according to their priorities suffer from the problem of starvation. They are not fair as they are biased to processes of high priorities (Saxena and Agarwal 2012). Consequently the goal of this work is to minimize starvation in the priority based CPU scheduling algorithms that is Shortest Job First and Priority scheduling algorithms thereby reducing the average waiting time, average turnaround time, average response time, number of context switches and waiting time variance deviation.
1.3 Research Aim and Objectives
The aim of this dissertation is to develop an algorithm that minimizes starvation in priority based CPU scheduling algorithms. This has been done by modifying the optimum priority in Saxena and Agarwal (2012) and applying it to the priority based CPU scheduling algorithms in order to
3
reduce average waiting time, average turnaround time, average response time and waiting time variance deviation. This is achieved with the following objectives:
1. Develop a new algorithm based on OSTRR by Saxena and Agarwal (2012)
2. Implement the algorithm using Java programming language
3. Assess the algorithm side-by-side traditional Shortest Job First algorithm, traditional Priority algorithm and OSTRR by Saxena and Agarwal (2012)
1.4 Research Methodology
The research was conducted in two stages as follows: In the first stage, the following steps were taken
i. Values were assigned for process number, burst time, arrival time and priority randomly.
ii. The values assigned in i were used to calculate EFFICIENCY FACTORS for the processes both in the SJF and Priority categories.
iii. The processes were scheduled based on their EFFICIENCY FACTORS values.
iv. Compared the results for the proposed algorithm against the traditional priority based CPU scheduling algorithms and OSTRR by Saxena and Agarwal (2012) by the use of Gantt charts
In the second stage,
i. Developed an algorithm to reduce starvation in priority based CPU scheduling algorithms
ii. The data to be used was generated randomly using three different experiments as follows:
a. In the first experiment, the arrival time is generated using Poisson Distribution (because it is a probability distribution of a discrete random variable that stands
4
for the number (count) of statistically independent events, occurring within a unit of time or space Letkowski (2012)); while the burst time is generated using Normal/Gaussian Distribution (because it is the most widely known and used of all distributions. And also, it approximates many natural phenomena so well, it has developed into a standard of reference for many probability problems (https://math.berkeley.edu/~scanlon/m16bs04/ln/16b2lec31.pdf)) and the priority is generated using Exponential Distribution (because it is used to model the behavior of units that have a constant failure rate
(http://reliawiki.org/index.php/The_Exponential_Distribution)).
b. In the second experiment, the arrival time is generated using Poisson Distribution, the burst time is generated using Uniform Distribution (because it defines equal probability over a given range for a continuous distribution. For this reason, it is important as a reference distribution. It is also used in the generation of random numbers. That is, almost all random number generators generate random numbers on the (0,1) interval. For other distributions, some transformation is applied to the uniform random numbers
(http://www.itl.nist.gov/div898/handbook/eda/section3/eda3662.htm)) and the priority is generated using Exponential Distribution
iii. In the third experiment, the arrival time is generated using Poisson Distribution, the burst time is generated using Exponential Distribution and the priority is generated using Uniform Distribution.
5
Iii Simulated the algorithm developed in step i against the traditional priority based CPU scheduling algorithms and Optimum Service Time for Round Robin Algorithm(OSTRR) by Saxena and Agarwal (2012) using Java programming language,
iv. The comparison is done based on average waiting time, average turnaround time, average response time, number of context switches and waiting time variance deviation for the three different experiments on the priority based CPU scheduling algorithms and OSTRR by Saxena and Agarwal (2012)
1.5 Contribution to knowledge
The dissertation contributed to knowledge by optimizing the traditional priority CPU scheduling algorithms thereby reducing starvation using Efficiency Factor which makes use of three metrics that is arrival time, waiting time and priority of processes to obtain one optimal value to schedule each process instead of using only one metric that is the priority of a process to schedule the process in the case of traditional Priority algorithm.
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»
