The design of effective algorithms for scheduling a system of coupled central processing units (CPUs) with intermittent tasks that share resources is not easy, despite the available simulation results of multiprocessor scheduling algorithms [1]. How should a multiprocessor allocation scheme (MAS) be designed to support irregular tasks contending for resources?

Andersson and Easwaran present a MAS for achieving the finite deadline execution of real-time tasks that share resources. The MAS uses the available physical processors to emulate three types of virtual processors with two speeds. Each virtual processor has access to a portion of an available physical processor and does not dissipate processing capability. The total number of virtual processors is twice the number of available physical processors plus the total collective resources that tasks require.

The authors outline an algorithm called global earliest deadline first (EDF) with virtual processor-based resource sharing (gEDF-vpr). The gEDF-vpr uses the status of each task to schedule its execution phases on the various sets of virtual processors. The status of each task is ready for execution without requesting a resource, while awaiting a shared resource, or due to incomplete execution subsequent to relinquishing a shared resource. The EDF algorithm uses nonpreemptive scheduling of processors to enforce mutually exclusive access to shared resources. The authors convincingly present a finite competitive ratio in favor of the nonpreemptive EDF algorithm for scheduling tasks, with inherent relative time limits on a single processor. Although the proposed MAS imposes restrictions on deadlines and access patterns to shared resources, the paradigm of gEDF-vpr offers intuitive practical ideas.