Efficient partitioning of sporadic real-time tasks with shared resources and spin locks

Partitioned fixed-priority scheduling is widely used in embedded multiprocessor real-time systems due to its simplicity and low runtime overheads. However, it fundamentally requires a static mapping of tasks to processors to be determined. Optimal task set partitioning is known to be NP-hard, and the situation is further aggravated when limited resources (such as I/O ports, co-processors, buffers, etc.) must be shared among the tasks. Partitioning heuristics are much faster to compute, but may fail to find a valid mapping even if one exists. In practice, such inefficiencies can be addressed by over-provisioning processors (i.e., by using more and faster processors than strictly required), albeit at the expense of increased space, weight, and power (SWaP) requirements. This work makes two contributions towards the efficient mapping of real-time tasks that share resources protected by spin locks. First, an Integer Linear Programming (ILP) formulation of the problem is presented, which, while computationally expensive, is efficient in the sense that it will find a valid assignment if one exists, thereby minimizing processor requirements. This ILP formulation is the first optimal solution to the mapping problem in the presence of spin locks. Second, a new resource-aware partitioning heuristic is introduced, which, while not optimal, is efficient in the sense that it easily scales to large problem instances. Notably, the proposed heuristic is much simpler than prior approaches, parameter-free, and shown to perform well for a wide range of workloads.