Scarce computer memory and processor core resources create crucial challenges to the real-time execution of concurrent software. How should a multicore processor be efficiently programmed to process concurrent software with different execution speeds and resource requirements?

Andersson et al. present a quasi-polynomial complexity algorithm for scheduling concurrent tasks with dependent uninterruptible execution periods. They propose a model for setting up a test for tasks with competing dependent runtimes, on an exact number of processors. The model consists of the parameters and runtime actions of tasksets and a function for testing a system’s schedule. The parameters include the default progress and the specific corunner requirements of concurrent tasks. A fixed-priority preemptive partitioned scheduler is used to monitor the runtime activities of corunner tasks. The scheduler computes the appropriate segments for each processor. Segments with the highest priorities are randomly selected and executed on target processors at specific time intervals. A function takes the corunner-reliant tasks and processors as input to test whether a system can be scheduled. The model inspects certain irregularities to decide on a schedulable system. The response time of a job cannot be maximized once there are other simultaneously arriving jobs. The priority assignments of jobs to processors are used to modify the execution requirements and progress of concurrent tasks.

The authors define COMP-CORUNNER as “the problem of performing exact schedulability testing,” and then use an NP-complete 3-PARTITION problem to show that the complexity of COMP-CORUNNER is NP-hard. Consequently, they present a new quasi-polynomial time complexity algorithm for testing whether concurrent tasks on systems with finite processors are schedulable. The algorithm is effectively used to process indiscriminately created tasksets using different sizes of processors, tasks, segments per task, degrees of corunner intrusion, and workloads on a system. The execution times utilized to test the schedulability of alternative systems with varying processor and task sizes are within 1000 seconds.

The authors present reliable algorithms and illustrations for computing the lower and upper bounds on the execution times of corunner tasks, and for the theoretical analysis of a safe, schedulable concurrent taskset execution test. The presented test is inexact but sufficient for testing a schedulable system.