A Performance Evaluation of Several Priority Policies for Parallel Processing Systems

Abstract

In this paper, analytical models for a multiprocessor executing a stream consisting of K classes of fork�join jobs are developed. Here, a fork�join job consists of a random number of tasks that can beexecuted independently ofeach other. Several priority policies are analyzed:(a) a strict nonpreemptive head of the line policy (b) a preemptive policy that allows preemptions at the job level, (c) a preemptive policy that allows preemptions at the task level, and (d) a policy in which the priority is a nondecreasing function of the number of tasks in the queue with preemptions at the job level. Using these models, the mean job response time for the different classes under the different policies is compared. These policies are compared to a system in which processors are partitioned so that classes are allocated only to certain processor groups. It is shown that, for the system considered, the task preemption policy has a uniformly better mean class response time and thus is preferable to a system with partitioned processors. © 1993, ACM. All rights reserved.