The size of real-life scheduling problems is too large to be solved by single processor
computer systems. Therefore, multiprocessor scheduling has become necessary to solve
these problems. Multiprocessing is the coordinated processing of programs by more
than one processor. These scheduling problems are known to be NP-hard even in the
very restricted situations (Ullman, 1975; Hou, 1994). Approximation algorithms have
been developed in response to the challenge of solving these problems to optimality.
However, in order to be useful in practical situations, these solutions have to be
supported by theoretical analysis showing how good the solutions are.
In this study, we propose an algorithm based on the concept of gang scheduling to
solve a multiprocessor scheduling problem. Gang scheduling is a scheduling approach
in which multiple threads of a given job are scheduled simultaneously on different
processors. Start time and finishing time of each thread will be the same. However,
though the jobs are split into multiple threads of shorter length, it is unavoidable that
certain processors may remain idle due to this requirement. Our proposed algorithm will
try to reduce these idle times by bringing some jobs to the front of the queue to fill the
gaps occurring in idle processors. This approach is known as backfilling (Feitelson et
al., 2004).
Gang scheduling and backfilling techniques have been used by several researchers
in solving multiprocessor scheduling problems. Zhang et al. (2000) have analyzed the behavior of well-known queuing policies such as First-Come-First-Served (FCFS), when
backfilling is used. Ward et al. (2002) have discussed the difference between two basic
approaches of backfilling: conservative backfilling and aggressive backfilling.
Conservative backfilling allows a lower priority job to run only if it will not delay any
of the higher priority waiting jobs, while the aggressive backfilling allows a lower
priority job to run if it will not delay the highest priority job. Siyambalapitiya and
Sandirigama (2011) have proposed an improvement to FCFS approach using gang
scheduling.
In this paper, we propose an improved algorithm for multiprocessor scheduling
which incorporates the idea of backfilling into gang scheduling. It is a further
improvement to decreasing-ascend algorithm proposed earlier (Siyambalapitiya and
Sandirigama, 2010). The idea is to reduce the idle times of the processors by bringing
some jobs in the queue to the front, which is known as backfilling. We shall also try
to give an idea of the quality of solution obtained by comparing it with a lower bound
for an optimal solution.
The remainder of this paper is organized as follows: in section 2, we explain the
methodology of developing the proposed algorithm. The proposed decreasing backfillgang
algorithm is presented in section 3. Results and discussion are presented in
section 4 and the conclusion is given in section 5.
|
