ABSTRACT

Longest Job First (LJF), the opposite of Shortest Job First, has been an unpopular process

scheduling algorithm. The idea of combinational burst time was used to avoid the starvation

problem associated with the LJF algorithm and to make it compete with other scheduling

algorithms with respect to some performance metrics. Although the combinational burst time

proposal led to improved performance, the work suffers from the limitations that the average

waiting time and the average turnaround time were slightlyhigher, and the number of context

switches was a little higher also. The research reported in this dissertation addressed these

shortcomings by proposing a new scheduling algorithm that enhanced the combinational

burst time model by using median as a statistics of central tendency and assigning the

processors to the CPU in interleave order. The proposed algorithm was implemented and

compared with First Come First Serve (FCFS), Longest Job First (LJF), Longest Job First

with combinational model (LJF+CBT) and Shortest Job First (SJF) scheduling algorithms

using varying number of processes and burst times. Results from the experiments showed

that the enhanced LJF+CBT outperformed the existing LJF+CBT producing 26.69% better

average waiting time (AWT), 21.77% better average turnaround time (ATAT) and 14.29%

better number of context switches (CS). In Longest Job First (LJF) scheduling this algorithm

drastically reduced the average waiting time by 46.5%, average turnaround time by 39.39%

and number of context switching between processes by 33.33% for all the number of

processes used. Sequel to these results, a better solution to starvation problem in Longest Job

First scheduling algorithm was proffered.

xv

CHAPTER ONE INTRODUCTION

This chapter discusses the introductory part of this thesis which includes the background of the

study, problem statement, the research aim and objectives, the methodology that was used in

solving the problems stated and finally the summary of the thesis contribution to knowledge.

1.1      Background of the Study

CPU scheduling is the basis of multiprogrammed operating systems. By switching the CPU among

processes, the operating system can make the computer more productive (Silberschatz et al., 2005).

The objective of multiprogramming is to have some process running at all times, to maximize CPU

utilization, so whenever the CPU becomes idle the operating system must select one of the

processes in the ready queue to be executed, the short-term scheduler (or CPU scheduler) carries

out the selection process. The scheduler selects a process from the processes in memory that are

ready to be executed and allocates the CPU to that process (Silberschatz et al., 2005).

Nearly all processes alternate bursts of computing with (disk) I/O requests, as shown in Fig. 1.1