Development of an Optimized Priority Based CPU Scheduling Algorithm to Minimize Starvation 0f Processes Using an Efficiency Factor

Development of an Optimized Priority Based CPU Scheduling Algorithm to Minimize Starvation 0f Processes Using an Efficiency Factor.

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 is burst time in the case of the 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 scheduling algorithm. But they both produced the same NCS.

The proposed Priority algorithm produced better results which means the proposed priority algorithm produced lesser NCS and smaller value of WTVD when compared to OSTRR by Saxena and Agarwal (2012),

and OSTRR by Saxena and Agarwal (2012) produced minimal AWT and ATAT than the proposed Priority algorithm although the values are almost identical in all categories of the statistical distributions used.

Based on these results, the proposed Priority algorithm should be preferred over the traditional Priority algorithm.

This is because starvation has been minimized by reducing the average waiting time, average turnaround time, average response time and waiting for time variance deviation in the case of the 500 processes that were considered and the burst time of processes ranging between 1 and 100ms and a quantum time of 10ms used by OSTRR by Saxena and Agarwal (2012).

TABLE OF CONTENTS

TITLE PAGEi
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 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

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

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

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 the 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 …5.1

Summary ………………………… 85
5.2 Conclusion …………………. 85
5.3 Recommendation ………………………… 88
REFERENCES ………………………….. 89
APPENDIX …………………… 92

INTRODUCTION

This chapter discusses the introductory part of this dissertation which comprises the background of the study, research motivation and goals which the research questions for which the dissertation provides answers, the aims and objectives of the research work.

The methodology that is followed in the and the contribution which the dissertation makes to knowledge.

1.1 Background of the Study

The Central Processing (CPU) is an important of the computer ; 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).

REFERENCES

Abdullahi, I and Junaidu, S. B. (2013). Empirical Framework to Migrate Problems in Longer Job First Scheduling Algorithm (LJF+CBT). International Journal of Computer Applications, 75 (14), 9-14. ABDULLAHI, I. (2012).

ROCESS SCHEDULING IN LONGEST JOB FIRST (LJF) ALGORITHM: A Proposed framework for Starvation Problem. A.B.U Zaria: M.Sc Thesis. Abdulrazaq, A., Saleh, E. A., and Junaidu, B. S. (2014).

A New Improved Round Robin (NIRR) CPU Scheduling Algorithm. International Journal of Computer Applications, 90 (4), 27-33.

Behera, H. S., Rakesh, M., Sabyasachi, S., and Sourav, K. B. (2011). COMPARATIVE PERFORMANCE ANALYSIS OF MULTI-DYNAMIC TIME QUANTUM ROUND ROBIN (MDTQRR) ALGORITHM WITH ARRIVAL TIME. Indian Journal of Computer Science and Engineering (IJCSE) , 262-271.

Behera, H.S, Mohanty, R and Debashree, N. (2010). A New Proposed Dynamic Quantum with Re-Adjusted Round Robin Scheduling Algorithm and Its Performance Analysis. International Journal of Computer Applications (0975 – 8887), 5 (5), 10-15.