Development of an optimized priority based cpu scheduling algorithm to minimize starvation of processes using an efficiency factor

Project Abstract

<p> </p><p>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</p><p>&nbsp;</p> <br><p></p>

Project Overview

<p> INTRODUCTION<br>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.<br>1.1 Background of the Study<br>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).<br>2<br>Figure1.1: The Traditional Process State Diagram (Silberschatz,et al. 2006)<br>1.2 Research Motivation and Goals<br>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.<br>1.3 Research Aim and Objectives<br>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<br>3<br>reduce average waiting time, average turnaround time, average response time and waiting time variance deviation. This is achieved with the following objectives:<br>1. Develop a new algorithm based on OSTRR by Saxena and Agarwal (2012)<br>2. Implement the algorithm using Java programming language<br>3. Assess the algorithm side-by-side traditional Shortest Job First algorithm, traditional Priority algorithm and OSTRR by Saxena and Agarwal (2012)<br>1.4 Research Methodology<br>The research was conducted in two stages as follows: In the first stage, the following steps were taken<br>i. Values were assigned for process number, burst time, arrival time and priority randomly.<br>ii. The values assigned in i were used to calculate EFFICIENCY FACTORS for the processes both in the SJF and Priority categories.<br>iii. The processes were scheduled based on their EFFICIENCY FACTORS values.<br>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<br>In the second stage,<br>i. Developed an algorithm to reduce starvation in priority based CPU scheduling algorithms<br>ii. The data to be used was generated randomly using three different experiments as follows:<br>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<br>4<br>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 (<a target="_blank" rel="nofollow" href="https://math.berkeley.edu/~scanlon/m16bs04/ln/16b2lec31.pdf)">https://math.berkeley.edu/~scanlon/m16bs04/ln/16b2lec31.pdf)</a>) and the priority is generated using Exponential Distribution (because it is used to model the behavior of units that have a constant failure rate<br>(<a target="_blank" rel="nofollow" href="http://reliawiki.org/index.php/The_Exponential_Distribution))">http://reliawiki.org/index.php/The_Exponential_Distribution))</a>.<br>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<br>(<a target="_blank" rel="nofollow" href="http://www.itl.nist.gov/div898/handbook/eda/section3/eda3662.htm)">http://www.itl.nist.gov/div898/handbook/eda/section3/eda3662.htm)</a>) and the priority is generated using Exponential Distribution<br>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.<br>5<br>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,<br>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)<br>1.5 Contribution to knowledge<br>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. <br></p>