Efficient partitioning of sporadic real-time tasks with shared resources and spin locks
Efficient partitioning of sporadic real-time tasks with shared resources and spin locks
复制标题
DOI：
10.1109/sies.2013.6601470
复制
发表时间：
2013-06
期刊：
影响因子：
--
通讯作者：
Alexander Wieder;Björn B. Brandenburg
中科院分区：
文献类型：
--
作者：
Alexander Wieder;Björn B. Brandenburg
分区固定优先级调度由于其简单性和低运行时开销而被广泛应用于嵌入式多处理器实时系统中。然而，它从根本上需要一个静态的映射任务的处理器来确定。最优任务集划分是NP难的，当有限的资源（如I/O端口、协处理器、缓冲器等）必须在任务之间共享。分区算法的计算速度要快得多，但即使存在有效的映射，也可能找不到。在实践中，这种低效率可以通过过度配置处理器（即，通过使用比严格要求更多和更快的处理器），尽管以增加的空间、重量和功率（SWaP）要求为代价。这项工作使两个贡献的实时任务，共享自旋锁保护的资源的有效映射。首先，一个非线性规划（ILP）制定的问题，这虽然计算昂贵，是有效的意义上说，它会找到一个有效的分配，如果存在，从而最大限度地减少处理器的要求。这个ILP配方是第一个最佳的解决方案的映射问题中存在的自旋锁。其次，引入了一种新的资源感知分区启发式算法，虽然不是最优的，但在很容易扩展到大型问题实例的意义上是有效的。值得注意的是，所提出的启发式比以前的方法简单得多，无参数，并显示出在广泛的工作负载下表现良好。
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.