A job scheduler is a policy engine which allows users to control over when and how resources (CPU time, memory etc.) are allocated to jobs. It also provides mechanisms to help optimize the use of these resources.
In theory any job that need more than a single piece of allocated resource runs the risk of starvation, unless there is a way of reserving resources in advance. Another way to solve starvation is by using a preemptive job scheduler but if jobs can be preempted it is more difficult to predict when the job will finish. When an idle job becomes eligible to run, it is assigned a priority. This priority is used to sort the jobs before the scheduler selects a job to start. Many batch systems use queues to divide and classify the workload. Each queue is then assigned a priority and sometimes each job is assigned a second priority to sort themselves within the queue. This classifying scheme is often too coarse. To take into account all parameters that set a batch job policy, you may end up with more queues than jobs.
The Maui job scheduler has the ability to allocate resource in the future as well as in Maui, "queues" have lost their importance in classification and priority calculations. Instead a quality of service attribute can be used to classify the jobs. The quality of service is basically a method of setting the parameters of a job when it enters the scheduler. All jobs eligible to run remain in one common idle-queue and their priorities are compared with all others.
Jobs in Maui can be in one of three major states: running (a job that has been allocated its required resources and has started its computation is considered running until it finish), queued or idle (job that is eligible to run. The priority is calculated here and the jobs in this state are sorted according to calculated priority and non-queued (job that is not allowed to start. Jobs in this state do not gain any queue-time priority).
The Maui job scheduler is an open source job schedule and currently maintained and supported by Adaptive Computing. For more information, documents, and to download it, you can check http://www.clusterresources.com/products/maui-cluster-scheduler.php.