Scheduling of parallel jobs is usually viewed in terms of a 2D chart with time along one axis and the number of processors along the other axis. Each job can be thought of as a rectangle whose height is the user estimated run time and width is the number of processors required. Parallel job scheduling strategies has been widely studied in the past
The simplest way to schedule jobs is to use the First-Come-First-Served (FCFS) policy. This approach suffers from low system utilization.
Backfilling was proposed to improve system utilization and has been implemented in several production schedulers.Backfilling works by identifying “holes” in the 2D chart and moving forward smaller jobs that fit those holes. There are two common variations to backfilling - conservative and aggressive (EASY.In conservative backfill,every job is given a reservation when it enters the system. A smaller job is moved forward in the queue as long as it does not delay any previously queued job. In aggressive backfilling, only the job at the head of the queue has a reservation. A small job is allowed to leap forward as long as it does not delay the job at the head of the queue. Under FCFS, the priority of a job is its wait time. Other priority policies like Shortest job First (SF), eXpansion Factor(XF) can be used. Under SF, the priority of a job is inversely proportional to its user estimated run time. Under the XFactor
priority scheme, the priority of a job is its XFactor which is defined as follows:
XFactor = (Wait time + Estimated Run time) / Estimated Run time
Some of the common metrics used to evaluate the performance of scheduling schemes are the average turnaround time and the average bounded slowdown. We use these metrics for our studies. The bounded slowdown of a job is defined as follows:
Bounded Slowdown = (Wait time + Max(Run time, 10))/ Max(Run time, 10)
The threshold of 10 seconds is used to limit the influence
of very short jobs on the metric.