Date of Award
5-1-2014
Degree Name
Master of Science
Department
Electrical and Computer Engineering
First Advisor
Kagaris, Dimitrios
Abstract
The Shortest Job First algorithm gives the optimal average turnaround time for a set of processes, but it suffers from starvation for long processes. Starvation occurs when a long process is denied processor resources because the resources are occupied by short processes, thus, causing the long process to potentially never finish its task. This thesis considers that the short processes are soft real time processes. It presents the designer with a choice to select an algorithm that provides close to optimal average turnaround time within the soft deadline for short processes as compared to the Shortest Job First algorithm which results in decreased average turnaround time for long processes. The proposed algorithm improves drawback, related to long job starvation, in Preemptive-Shortest Job First by providing protection to a process through prioritization. A priority is assigned to a process based on a percentage of its burst time to completion, by introducing the parameter Theta, or the time spent by the process in the waiting queue, by introducing the parameter Lambda. Theta protects a current running process from being preempted when its execution time reaches a percentage of its total computing time. Lambda gives priority to a process when it exceeds a certain amount of time in the waiting queue. Four variants of the proposed scheduling methodology, each using a different theta and lambda, have been developed. The performances of these variants are compared against Highest Response Ratio Next (HRRN), Railroad, Enhanced Shortest Job First (ESJF), and Alpha scheduling algorithms that have been previously proposed. Experimental results show that our proposed algorithm performs better in terms of reducing the average turnaround time of the long processes while maintaining the turnaround time on the short processes at low desired levels, as those required for soft real time tasks.
Access
This thesis is only available for download to the SIUC community. Current SIUC affiliates may also access this paper off campus by searching Dissertations & Theses @ Southern Illinois University Carbondale from ProQuest. Others should contact the interlibrary loan department of your local library or contact ProQuest's Dissertation Express service.