Unlike most previous results for task systems with resources, it is assumed that there are a fixed number of processors in the system. This assumption is of both practical and theoretical interest. An upper bound is given for the worst case performance of critical path scheduling for these task systems. The proof of this bound is based on an involved weighting function argument. The bound itself depends on both the number of processors and the number of resources.
Task system scheduling with limited preemption is introduced.
Here, a preempted task may resume execution only on the processor where it originally executed. Two classes of limited preemptive schedules are introduced, corresponding to whether or not unforced idle time is allowed in the schedule. The main result is that, on two processors, these two classes are equivalent with respect to optimal schedule lengths. This result is used to establish a hierarchy of optimal schedule lengths. This paper introduces task systems with semaphore constraints, a generalization of the standard model that allows a broad class of task dependencies.