多核资源共享协议汇总

09 Jun 2024

在多处理器系统中，可以同时从多个处理器（即全局资源）访问资源，而成熟的单处理器资源共享协议无法对其进行管理。为了限制访问全局资源的远程阻塞并防止死锁，已经提出了许多具有各种同步方法的多处理器资源共享协议。本节回顾了多处理器上的主要资源共享协议及其优点、缺点和局限性。

Multiprocessor Priority Ceiling Protocol(MPCP)

源自 PCP 的多处理器优先级上限协议 （MPCP） 是第一个针对具有固定优先级调度的全分区多处理器系统提出的资源共享协议

作为多处理器协议的先行者，MPCP 的初始方法是通过在所有应用处理器之间指定一个同步处理器，将多处理器资源共享模型转变为单处理器案例，其中任务可以使用本地资源执行或在应用进程处理器上独立运行，但必须在同步处理器上执行全局资源。请注意，不需要全局资源的任务也可以在同步处理器上执行。

在每次访问全局资源期间，该任务都被视为“迁移到”同步处理器。但是，在现实中，任务可以静态绑定到其指定的处理器，同时在同步处理器上创建用于执行每个全局资源的关键部分的线程（即代表其他任务执行的远程帮助进程）。使用全局资源执行时，任务的主机处理器是空闲的，以便本地优先级较低的任务可以开始执行（如果它不请求全局资源）。

使用这种方法，只能从一个处理器访问全局资源（即转换为本地资源），因此系统可以被视为多个独立的单处理器系统，其中每个处理器都采用IPCP。如果多个任务同时向一个全局资源发出请求，则假设每个任务具有唯一的优先级，则按基本优先级的递减顺序提供这些请求。此外，还引入了全局资源优先级提升机制，以防止因访问本地资源而造成的延迟，具体如下：

• 全局资源的基本优先级必须高于系统中所有任务的最高优先级（通常加 1）。
• 全局资源的上限优先级是系统中所有任务中最高优先级加上使用它的任务的最高优先级的总和。

这种优先级提升机制的直觉是为访问全局资源的任务提供最高的执行资格，以便可以限制远程阻止。如[88]所述，一个任务在访问全局资源时只能被阻止一次。

。。。

Multiprocessor Stack Resource Protocol(MSRP)

虽然 PCP 扩展为用于管理全局资源的 MPCP，但第 2.4.3 节中描述的众所周知的 SRP 也进行了修订以支持多处理器资源共享，即多处理器堆栈资源协议（MSRP）[47]. 然而，即使名称为MSRP，SRP也仅用于管理每个分区中对本地资源的访问，同时提出了一种简单有效的方法来控制对全局资源的请求。

与其暂停未满足的资源请求任务，不如暂停 MSRP 在争用全局资源时执行忙等待（即旋转），并且在等待和执行全局资源期间是非抢占式的。下面总结了该协议的定义：

• SRP 用于管理每个处理器上的本地资源。
• 每个全局资源都与一个 FIFO 等待队列相关联。
• 如果任务请求全局资源，则该任务将变为有效的非抢占式资源，并开始为该资源旋转。同时，它被放置在所请求资源的FIFO队列的末尾。
• 一旦任务成为FIFO队列的头部，就允许它获取资源。在使用全局资源执行期间，在释放资源之前，任务将保持非抢占式状态。
• 支持有限的嵌套资源访问，其中允许本地资源之间的访问以及从本地资源到同一处理器上的全局资源的访问。但是，由于死锁问题，不支持从本地资源到不同处理器上的全局资源的访问、从全局资源到本地资源的访问以及全局资源之间的访问。

Flexible Multiprocessor Locking Protocol

在[17]中开发的灵活多处理器锁定协议（FMLP）可以应用于全局或完全分区系统，并且是第一个多处理器资源共享协议，它提出了基于资源的不同特征管理资源的思想，具有多种同步方法

在 FMLP 中，根据关键部分的长度将资源分为长资源或短资源，其中采用基于悬架的锁来管理长资源，而自旋锁用于短资源。资源应被视为多头还是空头资源由用户决定。然而，每个短资源都应该有一个比任何长资源更短的关键部分。与 MPCP 和 MSRP 不同，FMLP 可以支持通过资源组和组锁在全局资源之间进行嵌套资源访问。下面总结了该协议的定义。

Preemptable Waiting Locking Protocol

如第 2.5.2 节和第 2.5.3 节所述，尽管非抢占式旋转锁保证了资源执行的强劲进展，每次资源访问都有有限的阻塞时间，但这种方法也对高优先级任务施加了相当多的阻塞时间，因此如果关键部分很长，系统的可调度性可能会受到破坏。

Parallel Priority Ceiling Protocol

并行优先级上限协议 （PPCP） 是 [41] 中提出的基于暂停的协议，适用于具有固定优先级的全局调度系统。

O(m) Locking Protocol

文献[20]中提出的O（m）锁定协议（OMLP）是一种基于挂起的协议，它保证每个任务在访问全局资源时最多可以产生M次的优先级倒置，其中M表示系统中的处理器数量。在 OMLP 中，资源由 m 排除锁（一种锁定结构，支持在给定时间最多 M 个任务的相互独占访问）进行管理，并由优先级和 FIFO 排序分开。 基本上，争用全局资源的任务根据这些任务的数量分为两个队列。如果这个数字小于 M，那幺所有竞争任务都可以直接放入全局 FIFO 队列中，根据到达顺序完成任务的地方。但是，如果存在更多的完成任务，则最近到达的任务将入到优先级排序队列中（假设 M 个竞争任务已插入到 FIFO 队列中），如果 FIFO 队列中的空格可用，这些任务可以稍后根据优先级顺序加入 FIFO 队列。

Spinning Processor Executes for Preempted Processor

非抢占式旋转锁（即非抢占式地等待和执行资源）的优点是，通过延迟高优先级任务的抢占，这是一种昂贵的操作[84]。 但是，这种方法可能会给高优先级任务带来大量的阻塞时间，因为它们必须等待当前资源访问完成，然后才能开始执行。另一方面，抢占式旋转方法有利于高优先级任务，因为它们可以直接抢占旋转的低优先级任务。但是，该方法（即第 2.5.4 节中的 PWLP）要求任务在被抢占时必须取消其当前请求，并在稍后恢复时重新请求资源，这延长了访问资源的等待时间。在此背景下，[100]中提出了一种替代的可抢占旋转方法，以最大程度地减少高优先级任务产生的到达阻塞，同时不干扰资源访问的进度，即抢占处理器的旋转处理器执行 （SPEPP）。

Multiprocessor BandWidth Inheritance protocol

多处理器带宽继承协议（M-BWI）是一种基于执行时服务器的资源共享协议，旨在实现基于保留调度的软实时多处理器系统[44]。该协议与本论文相关，因为它提出了一种完全抢占式的基于旋转的同步方法，该方法具有基于迁移的帮助机制，该机制可以处理任务预算耗尽或在持有共享资源时被抢占的情况。

Multiprocessor resource sharing Protocol

文献[27]中提出的多处理器资源共享协议（MrsP）旨在实现具有固定优先级的完全分区系统。MrsP 的基本功能类似于 MSRP 和 PWLP，采用自旋锁，资源按 FIFO 顺序提供。然而，MrsP 拥有一个重要的属性，即采用帮助机制来帮助资源持有任务在被抢占的同时保持进展。