一种在具有自旋锁的 FP-FPS 多处理器系统上分配任务的通用方法
许多复杂的实时系统，如自动驾驶汽车和 5G 无线基站，都包含大量共享资源，必须以互斥的方式访问。这会导致严重的资源竞争，尤其是在处理器之间共享资源时。为了减少资源竞争，研究者们开发了各种资源感知任务分配方法来本地化共享资源。遗憾的是，这些现有方法要么是针对特定的调度和分析方法量身定制的，要么会引入运行时开销，从而破坏其适用性。 本文提出了一种主流实时系统的任务分配方法：FP-FPS (fully-partitioned fixed-priority scheduling) 多处理器系统，具有管理共享资源的自旋锁。 该方法不依赖时间边界作为指导，而是利用模型来近似任务之间的资源竞争程度。该模型与优先级分配算法、资源共享协议和可调度性测试分离。因此，该任务分配方法可以在不详细了解底层系统的情况下应用，这在系统的初始设计阶段特别有用。在设计的后期阶段，有关系统的更多详细信息将提高近似精度并进一步提高性能。 实验结果表明，所提方法在系统可调度性方面平均优于现有方法 13.6% (最高 24.2%)，计算成本低得多 (平均 57 倍)，运行时开销可以忽略不计。
随着实时系统中实现越来越复杂的功能，例如自动驾驶汽车和 5G 电信基站，系统中的任务通常需要对必须以相互排斥的方式访问的同一对象进行操作，包括代码段、存储块、I/O 端口等。 AUTOSAR 标准 [1] 规定的自旋锁被广泛用于保护共享资源上的计算免受竞争条件的影响，并应用资源共享协议来管理对共享资源的访问 [2]。 但是，在强制实施旋转锁的情况下，系统中的任务可能会由于共享资源的竞争而引起资源争用。特别是，当任务从不同的处理器请求相同的资源时，它们会在其主机处理器上忙碌等待 (旋转)，直到请求的资源被授予。这会导致这些处理器中所有任务的高度阻塞，并可能严重破坏系统的可调度性 [3]。
为了缓解处理器之间的资源争用，在完全分区 (FP) 多处理器系统下，资源感知任务分配受到了广泛关注，该系统通过本地化共享资源来减少争用。对于各种调度方法和资源共享协议，有许多资源感知任务分配方法，例如固定优先级调度 (FPS) 和多处理器堆栈资源协议 (MSRP) [4]。这些方法通常可以分为两种主要方法，它们执行关键部分 (i) 在任务的主机处理器上或 (ii) 在专用处理器上。 第一种方法旨在将具有相同共享资源的任务分配给一个处理器以减少争用。然而，对于具有密集资源共享的复杂系统，这种方法中的方法要么变得无效 [5]，要么由于使用优化或基于搜索的技术 [6]，[7] 而带来高昂的计算成本。 第二种方法通过指定一组专用于资源访问的处理器来避免上述问题。然而，这种方法会带来额外的迁移开销，并且对于频繁的资源访问不太有利[8]。 此外，如第二节所述，大多数现有解决方案要么是针对固定调度方法和资源共享协议[9]量身定制的，要么需要特定的调度性分析来进行搜索[6]。 这些局限性带来了适用性问题，甚至带来了悲观，使它们在实际系统中的应用更具挑战性。
本文介绍了一种具有自旋锁的 FP-FPS (fully-partitioned fixed-priority scheduling, 完全分区固定优先级调度) 系统的通用任务分配方法，其中共享资源由任务从其主机处理器访问。与依赖于特定分析的基于搜索或优化的方法不同，建议的分配利用资源争用模型 （resource contention model, RCM） 来近似任务之间的资源争用程度。 基于本指南，我们按照始终将资源争用最高的任务分配给同一处理器的原则来分配任务，以减少资源竞争，从而减少任务的阻塞。 在给定不同级别的系统知识的情况下，构建了 RCM 的两种实现。 第一种实现基于应用进程任务的资源使用情况生成近似值，而不了解底层系统。 随着系统细节的深入，第二种实现方式考虑了自旋锁的主要特性，提高了近似精度，进一步提高了所提分配方法的有效性。
所提方法的优点是多方面的：(i) 它可以在没有底层系统详细信息的情况下产生分配解决方案；(ii) 它可以普遍应用于所有具有自旋锁的 FP-FPS 系统，而不需要选择优先级分配、资源共享协议和可调度性测试；(iii) 它可以通过避免复杂的基于搜索或优化的方法来提供有效和高效的解决方案。 所提出的方法在初始设计阶段作为试点解决方案特别有用。此外，在后期设计阶段，通过获得有关底层系统的更详细信息，增强性能，它仍具有竞争力。该评估验证了所提方法的可行性，并证明作为一种启发式方法，它比最先进的基于搜索的方法平均高出 13.6%（最高可达 24.2%），并显着降低了平均 57 倍的计算成本。
对资源感知任务分配的研究形成了大量的工作，涵盖了广泛的调度算法、资源共享协议、调度性测试等 [5] – [7]，[9] – [14]。本节重点介绍 FP-FPS 的现有资源感知分配方法，并讨论它们的局限性。
大多数现有方法在任务的主机处理器上执行关键部分 [5] – [7]、[10]、[11]。 根据这种方法，Lakshmanan 等 [5] 提出了一种同步感知分区算法 (SPA)，该算法将所有直接或可传递共享相同资源的任务捆绑在一起，并使用 Best Fit Decresing 启发式方法将任务包分配给处理器。 SPA 是通用的，仅利用资源使用情况的信息。但是，由于其任务捆绑和分配技术，它受到以下限制。
限制一：SPA [5] 可能导致无法放入任何处理器的繁重捆绑包，其中分配任务时不考虑共享资源，因此无法减少争用 [6]、[9]。
为了实现更高的效率，现有工作的一部分使用优化技术[6]，[15]来解决分配问题。在文献[6]中，提出了一个基于整数线性规划（ILP）的资源感知任务分配的优化问题。然而，ILP的可扩展性较低，在大规模设计空间探索等场景中是不利的[8]。在同一项工作中，开发了一种名为Greedy Slacker（GS）的基于搜索的方法，使用Audesly的最优优先级分配（OPA）和可调度性测试[16]来找到任务的分配和优先级顺序。然而，基于搜索的技术（例如，采用OPA的GS）只能应用于自旋锁的原始分析[17]，尽管有更准确的分析，例如[3]，[8]中的整体分析，但该分析具有高度的悲观性。这导致了以下限制。
限制二：文献 [6] 中基于搜索的方法要求使用原始的可调度性分析，该分析缺乏通用性，并引入了悲观性，从而破坏了其性能 [17]。
Hsiu 等 [11] 提出了一种方法，该方法将资源分配给处理器，并在每次请求共享资源时将任务迁移到指定的处理器，而不是将任务映射到处理器。这样可以本地化共享资源，并可以减少处理器之间的资源争用。据报道，该方法 [11] 减少了调度系统所需的处理器数量。遵循相同的方法，在 [9] 和 [12] 中构建了一种面向资源的分区 (resource-oriented partitioning, ROP) 方法，以使用基于搜索的方法和专门的可调度性测试来找到可行数量的专用处理器，用于共享资源和任务分配。提供了两个版本的 ROP，分别应用优先级上限协议和非抢占协议来管理专用处理器上的资源访问。在 [12] 中已经表明，ROP 优于一组现有方法，包括 [6] 中的 GS。但是，ROP 下的任务每次访问共享资源 (即迁入和迁回专用处理器) 时都可能产生额外的迁移开销。这可能会带来不平凡的运行时开销，并导致以下限制 [8]，[18]。
限制三：在密集的资源访问中，ROP [9] 会导致频繁的任务迁移，从而产生不小的开销，从而破坏方法的性能 [8]。
此外，大多数现有方法都是针对特定的调度方法和资源共享协议 [7]，[10] 量身定制的，或者由于基于搜索的技术需要对每个分配决策 [6]，[12] 的任务的最坏情况响应时间进行迭代计算，因此需要很高的计算成本。这些局限性使它们难以应用于实际工业系统，在早期设计阶段可能无法获得底层系统的全部细节，并且可能需要进行大规模的设计空间探索。为了解决这个问题，我们提出了一种资源感知分配方法，该方法可以提供有效和高效的解决方案，而无需详细了解底层系统。
我们专注于包含一组相同处理器的系统 Λ 以及根据 FP-FPS 计划安排的一系列零星任务Γ。Λ 中的第 x 个处理器表示为 λx. 任务 τi (Γ 中的第 i 个任务) 定义为 τi = {Ci, Ti, Di, Pi, Ai}，其中 Ci 是不访问共享资源的纯最坏执行时间，Ti 是周期，Di 是受约束的截止时间，Di ≤ Ti, Pi 是优先级，Ai 是分配。每个任务都有唯一的优先级，Pi 值越高表示优先级越高。函数 Γ (λx) 返回分配给 λx 的所有任务的集合。为简单起见，我们使用 u 来表示给定任务或任务组的利用率，例如分别使用 Uτi 和 UΓ (λx)。函数 |·| 表示给定集合的大小，例如，|Λ| 给出系统中的处理器数。
该系统还包含一组受旋转锁保护的共享资源 R。对于资源 rk (R 中的第 k 个资源)，ck 表示 rk 上最坏情况的计算时间，N k i 给出了一个版本中 τi 向 rk 发出的请求数。函数 F (·) 表示给定任务请求的资源。在多个处理器中的任务之间共享的资源称为全局资源，而在处理器中访问的资源称为本地资源。 此外，还假设了一种基于自旋的资源共享协议来管理共享资源，该协议涵盖了广泛的选择 [3]。但是，没有假设指定系统的协议和关联的可调度性分析。我们假设一个任务在任何时候都只能保存一个资源。但是，可以使用组锁来轻松支持嵌套资源访问，如 [8] 中所述。
本节介绍应用了旋转锁的 FP-FPS 的通用资源感知任务分配方法，其中任务直接在其主机处理器上访问共享资源。与现有方法不同，所提方法利用资源争用模型（RCM），该模型可以近似任务之间的资源争用程度，称为争用因子（CF）。使用近似 CF 作为指导，该方法按照以下基本原则生成分配决策：始终 （i） 将具有最高 CF 近似值的任务分组，以及 （ii） 将具有最高近似 CF 的任务组分配给一个处理器。
由于 RCM 的目的不是计算最坏情况下响应或阻塞时间的安全边界，因此它可以在不详细了解底层系统的情况下以足够的精度生成快速 CF 近似值。这为所提出的分配方法的通用性提供了关键，该方法普遍适用于所有FP-FPS系统。在本节中，我们将重点介绍假设存在 RCM 的建议分配方法。在第五节中，提出了RCM的两种实现，以证明CF近似值可以通过对底层系统的不同知识水平有效地获得。
对于一组给定的任务，建议的分配方法形成一组任务组 G，其中每个组包含具有高度资源争用的任务。符号 Ga 表示索引为 a 的任务组。此外，对所有任务组应用利用率边界 U 以限制一个组允许的最大利用率，即 U ≥ UGa 、∀Ga ∈ G。 在这项工作中，U 被设置为每个处理器中系统的平均利用率，即 U = UΓ/|Λ|。构造 G 后，然后执行分配，根据该组与该处理器上的现有任务之间的 CF 近似值将任务组分配给该处理器。 如前所述，所提出的方法中的组形成和分配决策都是基于 RCM 提供的 CF 近似值做出的。为了指导分配决策，RCM 需要为任何两个给定任务组生成 CF 近似值，表示为 ∆（Ga， Gb）。∆（Ga， Gb） 值越高，表示任务组之间的资源争用程度越高。对于不共享任何资源的 Ga 和 Gb，RCM 将通知分配器 ∆（Ga， Gb） = 0。此外，具有单个任务 τi 的输入被视为具有一个任务的组，即 {τi}。第五节详细介绍了符合上述要求的∆（Ga，Gb）的计算方法。
所提出的任务分组技术遵循的原则是始终将具有最高 CF 近似值的两个组合并为 U。这样一来，只有资源争用程度高的任务才会合并到一个组中，即使它们与系统中的其他任务共享某些资源也是如此。 此外，U 的使用有效地避免了无法安装到任何处理器中的重基团的产生。这突出了与 SPA 的主要区别，由于第 II 节中讨论的限制 1, SPA 往往会形成大型任务包。