Arachne：核心感知线程管理

本文包含在第13届USENIX操作系统设计和实现研讨会(OSDI’18)的会议记录中。

主要分为三个模块：

1. Arachne的设计与评估

2. Arachne应用于memcache的优点

3. Arachne应用于RAMcloud的优点

（理解第一部分就较容易理解第二、三部分）

温馨提示：

注意：我们使用术语核心core来表示可以支持独立计算线程的任何硬件机制。在具有超线程的处理器中，我们将每个超线程视为单独的逻辑核心，即使其中一些共享单个物理核心。

摘要

Arachne是一个新的用户级线程实现，它为具有极短生命周期(仅几微秒)的应用程序提供低延迟和高吞吐量。Arachne是核心感知的：每个应用程序根据其负载确定它需要多少核心；它总是确切地知道它已经分配了哪些核心，并且它控制它的线程在这些核心上的位置。中央核心仲裁器在应用程序之间分配核心。将Arachne添加到分布式缓存memcached，将符合SLO（服务级别目标）的吞吐量提高了37%，将尾延迟减少了10倍以上，并允许分布式缓存与后台应用程序共存，而几乎没有性能影响。将Arachne添加到RAMCloud存储系统后，其写操作吞吐量提高了2.5倍以上。Arachne线程库经过优化，可将缓存未命中降至最低；它可以在320 ns内在不同的核心上启动新的用户线程(具有负载平衡)。Arachne完全在Linux上的用户级别实现；不需要修改内核。

1. 简介

网络和存储技术的进步使数据中心服务能够以极低的延迟运行[5]。因此，近年来开发了各种低延迟服务，包括FaRM[11]、Memcached[23]、MICA[20]、RAMCloud[30]和Redis[34]。它们为同一数据中心内的客户端提供低至5µs的端到端响应时间，以及低至1-2µs的内部请求服务时间。这些系统采用各种新技术来实现低延迟，包括轮询而不是中断、内核旁路和运行至完成[6，31]。

论文的引出： 1.背景及问题的引出，2.该问题的现有解决办法及缺陷见第8节

然而，很难构建同时提供低延迟和高吞吐量的服务。实现低延迟的技术，例如为峰值吞吐量保留内核或使用轮询而不是中断，会浪费资源。多级服务(其中为一个请求提供服务可能需要对其他服务器的嵌套请求(例如复制))为资源利用不足创造了额外的机会，特别是如果它们使用轮询来减少延迟。服务内的后台活动，如垃圾收集，要么需要额外的保留(因此未充分利用)资源，要么冒着干扰前台请求服务的风险。理想情况下，应该可以将面向吞吐量的服务(例如MapReduce分布式计算系统[10]或视频处理[22])与低延迟服务共同定位，以便当低延迟服务不需要时，资源完全被面向吞吐量的服务占用。然而，在实践中很少尝试这样做，因为它会影响延迟敏感型服务的性能。

很难将低延迟和高吞吐量结合起来的原因之一是，应用程序必须使用虚拟资源(线程)管理它们的并行性；它们不能告诉操作系统它们需要多少物理资源(核心)，并且它们不知道已经为它们的使用分配了哪些核心。因此，应用程序无法调整其内部并行度以匹配可供其使用的资源，并且它们无法使用特定于应用程序的知识来优化资源的使用。这可能导致核心的利用率不足和过度使用，从而导致资源利用率低和/或性能不佳。应用程序的唯一方法是将线程固定到核心；这会导致应用程序内的核心利用率不足，并且不会阻止将其他应用程序调度到相同的核心上。

Arachne是一个线程管理系统，通过为应用程序提供对它们正在使用的物理资源的可见性来解决这些问题。我们称这种方法为核心感知线程管理。在Arachne中，应用程序线程完全在用户级别进行管理；它们对操作系统不可见。应用程序通过核心而不是线程与系统协商。核心分配给单独的应用程序专用，并在很长的时间间隔(几十毫秒)内保持分配给应用程序。每个应用程序总是确切地知道它分配了哪些核心，并决定如何在核心上调度应用程序线程。核心仲裁器决定将多少核心分配给每个应用程序，并响应于改变的应用程序需求来调整分配。

主要贡献

用户级线程管理系统在过去已经实现了很多次[39，14，4]，并且Arachne的基本功能是在1990年代早期以调度程序激活的形式为原型[2]。Arachne在以下方面是新颖的：

【·Arachne包含用于估计应用程序运行时所需核心数量的机制。——1.核心评估

Arachne的主要内容即设计内容

·Arachne允许每个应用程序定义一个核心策略，该策略在运行时确定应用程序需要多少个核心，以及如何将线程放置在可用核心上。——2.核心策略

·Arachne运行时旨在将缓存未命中降至最低。它使用一种新颖的调度信息表示法，没有就绪队列，这为线程创建、调度和同步提供了低延迟和可伸缩的机制。——3.最小化缓存未命中

·Arachne提供了比调度器激活更简单的公式，基于每个核心使用一个内核线程。——Arachne runtime

·Arachne完全在内核之外运行，不需要修改内核；核心仲裁器是使用Linux cpuset机制在用户级别实现的。Arachne应用程序可以与不使用Arachne的传统应用程序共存。——5.性能隔离

我们已经用C++实现了Arachne runtime和核心仲裁器，并使用合成基准测试程序以及分布式缓存和RAMCloud存储系统对它们进行了评估。Arachne可以在大约320 ns内在不同的核心上启动一个新线程(具有负载平衡)，应用程序可以在20-30µs内从核心仲裁器获得额外的核心。当Arachne被添加到分布式缓存时，它将尾延迟降低了10倍以上，并允许在低延迟下提高37%的吞吐量。Arachne还改进了性能隔离；后台视频处理应用程序可以与分布式缓存共存，而对分布式缓存的延迟几乎没有影响。当Arachne添加到RAMCloud存储系统时，它将写入吞吐量提高了2.5倍以上。

2. 线程问题

Arachne的动机是在创建处理大量非常小的请求的服务时遇到的挑战。这些服务可以针对低延迟或高吞吐量进行优化，但使用由操作系统实现的传统线程很难同时实现这两种功能。

例如，以memcached[23]为例，它是一种广泛使用的内存键值存储。memcached在大约10µs内处理请求。内核线程太昂贵，无法为每个传入请求创建一个新的线程，所以memcached使用固定大小的工作线程池。通过一个单独的调度线程以循环方式将新连接静态分配给工作线程。

当memcached启动时，工作线程的数量是固定的，这会导致几个效率低下的问题。如果memcached可用的核心数量小于工作线程的数量，则操作系统将在单个核心上多路传输工作线程，从而导致发送到取消调度的工作线程的请求出现长时间延迟。为了获得最佳性能，必须为每个工作线程保留一个核心。如果后台任务在低负载期间在机器上运行，它们很可能会干扰memcached工作线程，因为有大量不同的工作线程。此外，在低负载期间，每个工作线程将被轻载，增加其核心将进入具有高延迟唤醒的省电状态的风险。如果memcached可以在低负载期间缩减，以便更密集地使用较少数量的内核线程(和核心)，那么它的性能会更好。

此外，memcached对工作线程的静态连接分配可能会导致倾斜工作负载下的负载不平衡，一些工作线程过载，其他工作线程空闲。这会影响延迟和吞吐量。

RAMCloud存储系统提供了另一个示例[30]。RAMCloud是一个内存中的键值存储，可以在大约2µs内处理小的读请求。像memcached一样，它基于内核线程。一个调度线程处理所有网络通信，并使用内核旁路在NIC中轮询传入的数据包。当请求到达时，调度线程将其分派给一组工作线程中的一个执行；这种方法避免了倾斜工作负载的问题。活动工作线程的数量因负载而异。工作线程的最大数量是在启动时确定的，这会产生与memcached类似的问题。

RAMCloud实现了嵌套请求，导致了资源利用率较低，因为无法使用微秒级的空闲时间。当工作线程收到写请求时，它会将新值的副本发送到备份服务器，并在响应原始请求之前等待这些复制请求返回。所有复制请求都在7-8µs内完成，因此工作线程忙等待它们。如果工作线程要休眠，则需要几微秒才能再次唤醒它；此外，上下文切换开销太高，无法在如此短的时间内完成许多有用的工作。结果，工作线程的核心浪费了70-80%的时间来处理写请求；对于小型写操作，服务器的写吞吐量仅为约150 Kops/秒，而对于小型读操作，则约为1 Mops/秒。

Arachne的目标是提供一个线程管理系统，允许将低延迟和高吞吐量更好地结合在一起。例如，每个应用程序都应该将其工作负载与可用核心相匹配，仅根据需要获取尽可能多的核心，并动态调整其内部并行度，以反映分配给它的核心数量。此外，Arachne应该提供一个用户级线程的实现，该实现对于非常短的线程足够有效，并且允许在短暂的阻塞期间（例如用于嵌套请求的阻塞）完成有用的工作。

尽管一些现有的应用程序将从Arachne中受益，但我们预计Arachne将主要用于线程生存期仅为几微秒的新粒度应用程序。由于当前线程基础设施的低效，现在很难或不可能构建这些应用程序。

3. Arachne综述

图1：Arachne架构。核心仲裁器使用应用程序中每个内核线程的一个套接字加一页共享内存与每个应用程序通信。

图1显示了Arachne的整体架构。三个组件一起工作来实现Arachne线程。核心仲裁器由一个独立运行的用户进程加上一个链接到每个应用程序的小库组成。Arachne runtime和核心策略是链接到应用程序中的库。不同的应用程序可以使用不同的核心策略。应用程序还可以用自己的线程库替换Arachne runtime和核心策略，同时仍然使用核心仲裁器。

核心仲裁器是一个用户级进程，它管理核心并将它们分配给应用程序。它从每个应用程序收集有关它需要多少核心的信息，并使用简单的优先级机制在竞争应用程序之间划分可用核心。当应用程序需求改变时，核心仲裁器调整核心分配。第4节详细描述了核心仲裁器。

Arachne runtime创建几个内核线程并使用它们来实现用户线程，这些用户线程由Arachne应用程序使用。Arachne用户线程抽象包含类似于基于内核线程的线程包的工具，包括线程创建和删除、锁和条件变量。然而，用户线程上的所有操作都是完全在用户级别执行的，无需进行内核调用，因此它们比内核线程上的操作快一个数量级。第5节更详细地描述了Arachne runtime的实现。

Arachne runtime与核心策略一起工作，核心策略确定应用程序如何使用核心。核心策略使用Arachne runtime收集的性能信息计算应用程序的核心需求。它还确定哪些用户线程在哪些核心上运行。每个应用程序选择其核心策略。核心策略将在第6节中讨论。

Arachne使用内核线程作为核心的代理。runtime创建的每个内核线程都在单独的核心上执行，并且它在运行时具有对该内核的独占访问权限。当仲裁器将核心分配给应用程序时，它会在该内核上解锁该应用程序的内核线程之一；当从应用程序中移除该核心时，在该核心上运行的内核线程会阻塞。Arachne runtime在每个内核线程中运行一个简单的分派器，它在关联的核心上多路复用几个用户线程。

Arachne对用户线程使用协作多线程模型：runtime不会抢占已经开始执行的用户线程。如果用户线程需要长时间执行而不阻塞，则它必须偶尔调用让步方法，该方法允许其他线程在调用线程继续之前运行。我们期望大多数线程要么阻塞要么快速完成，因此应该很少需要调用让步方法。

线程的用户级实现的一个潜在问题是用户线程可能导致底层内核线程阻塞。例如，如果用户线程调用阻塞一个内核调用或引发页面错误，则可能发生这种情况。这会防止在内核调用或页面错误完成之前内核线程运行其他用户线程。以前的用户级线程的实现试图以各种方式解决这种低效问题，通常涉及复杂的内核修改。

Arachne不会采取任何特殊步骤来处理阻塞的内核调用或页面错误。大多数现代操作系统支持异步I/O，因此可以在不阻塞内核线程的情况下实现I/O。考虑到内存成本低和内存尺寸大，如今分页几乎没有成本效益。现代服务器很少发生页面错误，除了初始加载，例如当应用程序启动或文件映射到虚拟内存时。因此，为了简单起见，Arachne不会尝试利用内核线程因页面错误或内核调用而被阻塞的时间。

4. 核心仲裁器——管理核心并将它们分配给应用程序

本节描述核心仲裁器如何要求对(大多数)系统的核心的控制并在应用程序之间分配它们。核心仲裁器有三个有趣的特性。首先，它使用现有的Linux机制完全在用户级别实现核心管理；它不需要任何内核更改。其次，它与不使用Arachne的现有应用程序共存。第三，在优先级机制和从应用程序抢占核心的方式上，它对核心管理采取了合作的方法。

核心仲裁器作为具有root权限的用户进程运行，并使用Linux cpuset机制来管理核心。cpuset是一个或多个核和一个或多个内存库的集合。在任何给定时间，每个内核线程都恰好分配给一个cpuset，Linux调度器确保该内核线程只在该cpuset中的核心上执行。默认情况下，所有线程都在包含所有核心和所有内存库的cpuset中运行。核心仲裁器使用cpuset将特定的核心分配给特定的应用程序。

核心仲裁器将核心分为两组：托管核心和非托管核心。托管核心由核心仲裁器分配；只有Arachne创建的内核线程在这些核心上运行。非托管核心继续由Linux调度。它们由不使用Arachne的进程使用，也由核心仲裁器本身使用。此外，如果Arachne应用程序在Arachne外部创建新的内核线程(例如，使用std：：thread)，则这些线程将在非托管核心上运行。

当核心仲裁器启动时，它为非托管核心创建一个cpuset(非托管cpuset)，并将系统的所有核心放入该集中。然后，它将每个现有内核线程(包括其自身)分配给非托管cpuset；由这些线程派生的任何新线程也将在此cpuset上运行。核心仲裁器还创建一个对应于每个核心的托管cpuset，它包含该单个内核，但最初没有分配给它的线程。为了将一个核心分配给一个Arachne应用程序，仲裁器从非托管cpuset中删除该核心，并将Arachne内核线程分配给该核心的托管cpuset。当任何Arachne应用程序不再需要某个核心时，核心仲裁器将该核心重新添加到非托管cpuset。

该方案允许Arachne应用程序与其线程由Linux内核管理的传统应用程序共存。Arachne应用程序接收对核心的优先访问，除了核心仲裁器为非托管cpuset保留至少一个核心。Arachne runtime使用仲裁器的库包中的三种方法与核心仲裁器通信：

·setRequestedCores：每当其核心需求发生变化时，由runtime调用；指示应用程序在不同优先级级别所需的核心总数(详细信息见下文)。runtime—所需的核心总数–>核心仲裁器

·blockUntilCoreAvailable：由内核线程调用以向核心仲裁器标识自身，并将内核线程置于休眠状态，直到为其分配了核心。在内核线程唤醒时，此方法返回分配的核心的标识符。内核线程—>核心仲裁器

·mustReleaseCore：由runtime定期调用；返回值为true意味着调用的内核线程应该调用lockUntilCoreAvailable以将其核心返回给仲裁器。runtime—-如果true返回(即释放)内核线程对应的核心–à核心仲裁器

通常，Arachne runtime处理与核心仲裁器的所有通信，因此这些方法对应用程序是不可见的。但是，应用程序可以通过直接调用仲裁器库包来实现自己的线程和核心管理

上述方法使用Unix域套接字和共享内存页面的集合与核心仲裁器通信(见图1)。仲裁器库为每个内核线程打开一个套接字。此套接字用于向核心仲裁器发送请求，并且还用于在内核线程没有分配核心时将其置于休眠状态。核心仲裁器使用共享内存页将信息传递到仲裁器库；它由核心仲裁器写入，并且对仲裁器库是只读的。（仲裁器库包—–套接字发送核心请求—à核心仲裁器，核心仲裁器—–共享内存页———-à仲裁器库）

当Arachne runtime启动时，它调用setRequestedCores来指定应用程序的初始条件；setRequestedCores通过套接字将信息发送到核心仲裁器。然后runtime为机器上的每个核心创建一个内核线程；所有这些内核线程都调用blockUntilCoreAvailable。block UntilCoreAvailable通过属于该内核线程的套接字向核心仲裁器发送请求，然后尝试从套接字读取响应。这有两个效果：首先，它通知核心仲裁器内核线程可供其管理(请求包括线程的Linux标识符)；其次，套接字读取将内核线程置于睡眠状态。

此时，核心仲裁器知道应用程序的核心需求及其所有内核线程，并且内核线程都被阻塞。当核心仲裁器决定为应用程序分配核心时，它选择应用程序的阻塞内核线程之一在该核心上运行。它将该内核线程分配给与分配的核心相对应的cpuset，然后通过线程的套接字发回响应消息。这会导致线程唤醒，Linux将在给定的核心上调度线程；blockUntilCoreAvailable方法返回，并将核心标识符作为其返回值。然后内核线程调用Arachne调度程序来运行用户线程。

如果核心仲裁器希望从应用程序中收回核心，则它要求应用程序释放核心。核心仲裁器不会单方面抢占核心，因为核心的内核线程可能处于不方便的状态(例如，它可能已经获得了重要的自旋锁)；突然停止它可能会对应用程序产生重大的性能后果。因此，核心仲裁器在共享内存页面中设置一个变量，指示应该释放哪个(哪些)内核。然后等待应用程序响应。

每个内核线程负责定期通过调用mustReleaseCore来测试共享内存中的信息。Arachne runtime在其调度器中执行此操作。如果mustReleaseCore返回true，那么内核线程将按照第5.4节中所述进行清理，并调用blockUntilCoreAvailable。这会通知核心仲裁器并将内核线程置于休眠状态。在这一点上，核心仲裁器可以将核心重新分配给不同的应用程序。

核心仲裁器和应用程序之间的通信机制故意是不对称的：从应用程序到核心仲裁器的请求使用套接字，而从核心仲裁器到应用程序的请求使用共享存储器。套接字很方便，因为它们允许核心仲裁器在等待请求时休眠；它们还允许应用程序内核线程在等待分配核心时休眠。套接字通信相对昂贵(每个方向几微秒)，但它只在应用程序核心需求发生变化时发生，我们预计这不会很频繁。共享内存页很方便，因为它允许Arachne runtime有效地测试来自核心仲裁器的传入请求；这些测试经常进行(每次通过用户线程调度器传递)，因此重要的是它们速度快并且不涉及内核调用。

应用程序可以将释放核心延迟很短的时间，以便达到方便的停止点，例如在没有锁定的情况下。Arachne runtime不会释放核心，直到在该核心上调用调度器，当用户线程阻塞、让步或退出时会发生这种情况。

如果应用程序未能在超时期间(当前为10ms)内释放核心，则核心仲裁器将强制回收该核心。它通过将核心的内核线程重新分配给非托管cpuset来实现这一点。内核线程将能够继续执行，但由于非托管cpuset中其他线程的干扰，它可能会遇到性能下降。

核心仲裁器使用简单的优先级机制为应用程序分配核心。Arachne应用程序可以请求不同优先级的核心(当前实现支持八个)。核心仲裁器从最高优先级到最低优先级分配核心，因此低优先级应用程序可能不会接收核心。如果在特定级别没有足够的核心用于所有请求，则核心仲裁器在请求应用程序之间平均分配核心。每当应用程序请求改变时，核心仲裁器重复此计算。只要可能，仲裁器就将特定硬件核心的所有超线程分配给相同的应用程序。核心仲裁器还试图将应用程序的所有核心保持在同一套接字上。

此核心分配策略假设应用程序(及其用户)将合作选择优先级：行为不当的应用程序可能会通过请求处于最高优先级的所有核心而使其他应用程序处于饥饿状态。通过要求应用程序在首次连接时向核心仲裁器进行身份验证，并允许系统管理员为每个应用程序或用户设置限制，可以防止反社会行为。我们将这种机制留待将来的工作。

5. The Arachne Runtime ——创建内核线程并使用它们来实现用户线程

本节讨论Arachne runtime如何实现用户线程。runtime的最重要目标是为现代多核心硬件提供快速且可伸缩的用户线程实现。我们希望Arachne支持粒度计算，粒度计算由大量生命周期极短的线程组成。例如，低延迟服务器可能会为每个传入请求创建一个新线程，并且该请求可能只需一两微秒即可处理；服务器可能每秒处理数百万个这样的请求。

5.1 缓存最优化设计

Arachne runtime的性能由缓存未命中主导。大多数线程操作(如创建线程、获取锁或唤醒阻塞的线程)都相对简单，但它们涉及核心之间的通信。跨核通信需要缓存未命中。例如，要将值从一个核心传输到另一个核心，必须在源核心上写入该值，并在目标核心上读取该值。这需要大约三次高速缓存未命中时间：写操作可能会导致第一次读取数据的高速缓存未命中；然后写操作将使目标高速缓存中的数据副本无效，这需要大约与高速缓存未命中相同的时间；最后，读操作将导致高速缓存未命中以获取数据的新值。高速缓存未命中可能需要50-200个周期，因此即使一个操作仅需要单个高速缓存未命中，该未命中的成本也可能比该操作的所有其他计算都要高。在我们的服务器上，缓存未命中没有在同一套接字中将值从一个核心传输到另一个核心，只要在同一核心上的用户线程之间进行上下文切换，就需要7-8倍的时间。套接字之间的传输甚至更昂贵。因此，我们在实现用户线程时最重要的目标是将缓存未命中降至最低。

可以通过在高速缓存未命中同时执行其他操作来降低高速缓存未命中的有效成本。例如，如果在彼此的几个指令内发生几个高速缓存未命中，则它们都可以以单个未命中的成本来完成(现代处理器具有乱序的执行引擎，其可以在等待高速缓存未命中的同时继续执行指令，并且每个核心具有多个存储器通道)。因此，额外的高速缓存未命中基本上是空闲的。然而，现代处理器具有大约100条指令的无序执行限制，因此代码必须设计为将可能的缓存未命中集中在彼此附近。

类似地，如果孤立地进行数十纳秒的计算发生在缓存未命中附近，则它实际上可能具有零边际成本；它只会在处理缓存未命中时填充时间。第5.3节将展示Arachne调度器如何使用这种技术来隐藏看似昂贵的代码的成本。

5.2 创建线程

许多用户级线程包(如GO[14]中的那个)在与父线程相同的核心上创建新线程；它们使用工作窃取来平衡核心之间的负载。这避免了线程创建时的缓存未命中。然而，工作窃取是一个代价高昂的操作(它需要缓存未命中)，这对于寿命较短的线程尤其明显。工作窃取还会在线程被窃取到未加载的核心之前引入一个时间延迟，这会影响服务延迟。对于Arachne，我们决定在线程创建时执行负载平衡；我们的目标是尽快在未加载的核心上获得一个新线程。通过基于缓存未命中优化此机制，我们能够实现线程创建时间与在父核心上创建子线程的系统竞争。

在线程创建期间可能会发生缓存未命中，原因如下：

·负载平衡：Arachne必须以跨可用核心平衡负载的方式为新线程选择核心；在获取描述当前负载的共享状态时，可能会发生缓存未命中。

·状态转移：线程的顶级方法的地址和参数必须从父核心转移到子核心。

·调度：父线程必须向子线程的核心表明子线程是可运行的。

·线程上下文：线程的上下文由其调用堆栈加上Arachne runtime使用的元数据组成，例如调度状态和线程未运行时保存的执行状态。根据此信息的管理方式，可能会导致额外的缓存未命中。

一个用户线程分配一个线程上下文，且线程上下文和用户线程一样专属于一个特定核心，但核心可包含多个线程上下文

下面我们将描述Arachne如何在四次缓存未命中时间内创建新的用户线程。

为了最小化线程上下文的缓存未命中，Arachne将每个线程上下文绑定到单个内核(该上下文仅由单个内核线程使用)。每个用户线程在创建时都被分配给一个线程上下文，并且线程仅在上下文的关联核心上执行。大多数线程的整个生命周期都在一个核心上。线程仅作为显式迁移的一部分移动到不同的核心。这仅在极少数情况下发生，例如当核心仲裁器回收核心时。线程上下文在线程完成后仍然绑定到其核心，并且Arachne在创建新线程时重用最近使用的上下文。如果线程的生存期较短，则可能已经缓存了新线程的上下文。

一个核心包含一个64位maskAndCount值

要创建新的用户线程，Arachne runtime必须为线程选择一个核心，并分配与该核心关联的线程上下文之一。这些操作中的每一个都可能导致缓存未命中，因为它们操作共享状态。为了将缓存未命中降至最低，Arachne使用相同的共享状态同时执行两个操作。状态由每个活动核心的64位maskAndCount值组成。该值的56位是指示哪个核心的线程上下文当前正在使用的位掩码，而其余的8位是掩码中1的数量的计数。

在创建新线程时，Arachne使用“两个选择的力量”方法进行负载平衡[26]。它随机选择两个核心，读取它们的maskAndCount值，并选择具有最少活动线程上下文的核心。这可能会导致每个maskAndCount的缓存未命中，但它们将被并发处理，因此总延迟是单个未命中的延迟。然后，Arachne扫描所选核心的掩码位以找到可用的线程上下文，并使用原子比较和交换操作来更新所选核心的maskAndCount。如果比较和交换由于并发更新而失败，Arachne会重新读取所选核心的maskAndCount，并重复分配线程上下文的过程。这种创建机制是可伸缩的：使用大量的核心，可以在不同的核心上同时创建多个线程。

一旦分配了线程上下文，Arachne就会将线程的顶级方法的地址和参数复制到上下文中，并通过在上下文中设置一个字大小的变量以指示线程是可运行的来调度线程的执行。为了最大限度地减少缓存未命中，Arachne使用单个缓存行来保存所有这些信息。这将在具有64字节缓存行的计算机上将参数列表限制为6个单一字参数；较大的参数列表必须通过引用传递，这将导致额外的缓存未命中。

通过这种机制，可以在四次缓存未命中时间内在不同的内核上调用新线程。读取maskAndCount需要一个缓存未命中，传输包含方法地址和参数以及调度标志的行需要三个缓存未命中时间，如第5.1节所述。

maskAndCount变量将Arachne限制为每个内核在给定时间内56个线程。因此，依赖于大量阻塞线程的编程模型可能不适合与Arachne一起使用。

5.3 线程调度

线程调度的传统方法使用一个或多个就绪队列来标识可运行的线程(通常每个核心一个队列，以减少争用)，加上每个线程的调度状态变量，该变量指示该线程是可运行的还是阻塞的。从高速缓存未命中的角度来看，这种表示是有问题的。在就绪队列中添加或删除条目需要对多个变量进行更新。即使队列是无锁的，当队列在多个核心之间共享时，这可能会导致多个缓存未命中。此外，我们希望共享是常见的：当线程被唤醒时，必须将线程添加到其核心的就绪队列中，但唤醒通常来自不同核心上的线程。

此外，调度状态变量受竞赛的影响。例如，如果一个线程在条件变量上阻塞，但另一个线程在阻塞线程进入睡眠之前通知该条件变量，则对调度状态变量的争用可能会导致唤醒丢失。这种竞争通常通过控制对状态变量的访问的锁来消除。但是，锁定会导致额外的缓存未命中，因为它是跨核共享的。

为了最大限度地减少缓存未命中，Arachne不使用就绪队列。Arachne 调度器不检查就绪队列，而是重复扫描与当前核心关联的所有活动用户线程上下文，直到找到一个可运行的线程。这种方法被证明是相对有效的，原因有两个。首先，我们期望在给定的时间内只有几个线程上下文被一个核心占用(对于间歇性任务，不需要保持阻塞的线程；可以为每个任务创建一个新线程)。其次，扫描活动线程上下文的成本很大程度上被唤醒的线程的调度状态变量上不可避免的缓存未命中所隐藏。此变量通常由不同的核心修改以唤醒线程，这意味着调度程序必须采取缓存未命中来观察新值。在调度器的缓存中使变量的前一个值无效到可以获取新值之间需要100个或更多的周期；在此期间可以扫描大量的线程上下文。第7.4节评估了这种方法的成本。

Arachne还使用了一种新的无锁机制来调度状态。线程的调度状态用线程上下文中的64位wakeupTime**变量**表示。如果线程的wakeupTime小于或等于处理器的细粒度循环计数器，则调度器认为该线程是可运行的。在将控制转移到线程之前，调度器将其wakeupTime设置为可能的最大值。当线程阻塞时，wakeupTime不需要修改：较大的值将阻止线程再次运行。要唤醒线程，wakeupTime设置为0。这种方法消除了前面描述的争用条件，因为当线程阻塞时wakeupTime不会被修改；因此，访问变量不需要同步。

wakeupTime变量还支持基于计时器的唤醒。如果线程希望休眠给定的时间段，或者如果它希望向某些其他阻塞操作(如条件等待)添加超时，它可以在阻塞之前将wakeupTime设置为所需的唤醒时间。Arachne调度器中的单个测试既可以检测正常解锁，也可以检测基于计时器的解锁。

Arachne使用两种方法将wakeupTime机制导出到应用程序：

·block(Time)将阻塞当前用户线程。time参数是可选的；如果指定了它，wakeupTime将设置为此值(使用比较和交换来检测并发唤醒)。

·signal(Thread)将给定用户线程的wakeupTime设置为0。——即唤醒用户线程

这些方法使得构造更高级别的同步和调度运算符变得容易。例如，在协作多线程中使用的让步方法允许其他用户线程运行，它只是调用block(0)。

5.4 添加和释放核心

当核心仲裁器将新的核心分配给应用程序时，它会唤醒在blockUntilCoreAvailable中阻塞的一个内核线程。内核线程通知新核心的核心策略，如下面第6节所述，然后它进入Arachne调度程序循环。——添加核心

当核心仲裁器决定从应用程序中回收核心时，在核心上运行的Arachne调度器中mustReleaseCore将返回true。内核线程修改其maskAndCount以防止在其上放置任何新线程，然后通知回收的核心策略。如果该核心上存在任何用户线程，Arachne runtime会将它们迁移到其他核心。为了迁移线程，Arachne选择一个新的核心(目标核心)，并使用与线程创建相同的机制在该核心上保留未占用的线程上下文。然后，Arachne将正被迁移的线程的上下文与未占用的上下文交换，使得线程的上下文被重新绑定到目的核心，并且来自目的核心的未使用的上下文被重新绑定到源核心。一旦所有线程都迁移走了，通过调用blockUntilCoreAvailable回收核心上的内核线程。这会通知核心仲裁器该核心不再使用，并将内核线程置于休眠状态。——释放核心

6. 核心策略

我们Arachne的目标之一是让应用程序精确控制其核心的使用。例如，在RAMCloud中，中央调度线程通常是性能瓶颈。因此，调度线程独占使用核心是有意义的。此外，同一物理核心上的另一个超线程应该是空闲的(如果同时使用两个超线程，则它们各自的运行速度比只使用一个超线程时慢约30%)。在其他应用程序中，可能希望将特定线程托管在相同核心或套接字的超线程上，或者强制所有低优先级后台线程在单个核心上执行，以便最大化可用于前台请求处理的资源。

Arachne runtime不实现核心使用的策略。这些在单独的核心策略模块中提供。每个应用程序在启动时选择特定的核心策略。编写高性能核心策略可能具有挑战性，特别是对于处理NUMA问题和超线程的策略。我们希望可以开发一小部分可重用的策略来满足大多数应用程序的需求，这样应用程序开发人员就很少需要实现自定义的核心策略。

为了管理核心使用情况，核心策略必须知道哪些核心已分配给应用程序。每当应用程序获得或失去核心时，Arachne runtime都通过调用核心策略中的方法来提供此信息。当应用程序创建新的用户线程时，它会为该线程指定一个整数线程类。核心策略使用线程类来管理用户线程；每个线程类对应于特定的服务级别，例如“前台线程”或“后台线程”。每个核心策略定义自己的一组有效线程类。Arachne runtime将线程类与线程一起存储，但不知道如何使用它们。核心策略使用线程类来管理新线程的放置。创建新线程时，Arachne调用核心策略中的方法getCores，并将其传递给线程类。getCores方法使用线程类来选择线程可接受的一个或多个核心。Arachne runtime使用第5节中描述的“两个选择的能力”机制将新线程放置在其中一个核心上。如果核心策略希望将新线程放置在特定核心上，getCores可以返回包含单个条目的列表。当线程必须作为释放核心的一部分进行迁移时，Arachne还会调用getCores为线程找到新的宿主。Arachne的一个不同寻常的特性是，每个应用程序都负责确定它需要多少核心；我们称之为核心估计，它由核心策略处理。Arachne runtime测量每个核心的两个统计信息，它使核心策略可以使用这些统计信息，以便在核心评估中使用。第一个统计数据是利用率，这是每个Arachne内核线程执行用户线程所花费的时间的平均比例。第二个统计数据是负载因子，它是对该核心上可运行用户线程的平均数量的估计。这两个都是通过Arachne调度循环中的几个简单操作来计算的。

6.1 默认核心策略

Arachne目前包含一个核心策略；我们在第7节中对所有性能度量使用了默认策略。默认策略支持两个线程类：Exclusive和Normal。每个独占线程在为该特定线程保留的单独核心上运行；当独占线程被阻塞时，其核心处于空闲状态。独占线程对于长时间运行的轮询调度线程很有用。普通线程共享于与用于独占线程的核心不相交的核心池；可以有多个普通线程同时分配给一个核心。

6.2 核心评估

默认的核心策略为每个独占线程请求一个核心，另外为普通线程请求额外的核心。估计正常线程所需的核心需要在核心利用率和快速响应时间之间进行权衡。如果我们试图在100%的时间内保持核心忙碌，负载的波动将产生挂起线程的积压，从而导致新线程的延迟。另一方面，我们可以优化快速响应时间，但这会导致核心利用率低。工作负载越突发，必须浪费的资源就越多，以便获得快速响应。

默认策略使用不同的向上扩展和向下扩展机制。按向上扩展的决定基于负载因子：当运行正常线程的所有核心的平均负载因子达到阈值时，核心策略会将其请求的核心数量增加1。我们选择这种方法是因为负载因子是响应时间的相当直观的代理；这使得用户在需要时更容易指定非默认值。此外，性能测量表明，负载因子优于向上扩展的利用率：单个负载因子阈值适用于各种工作负载，而按向上扩展的最佳利用率取决于工作负载的突发性和总体容量。

另一方面，向下扩展基于利用率。负载因子很难用于向下扩展，因为感兴趣的度量不是当前的负载因子，而是少了一个内核就会出现的负载因子；这很难估计。相反，默认核心策略记录每次增加其请求的核心数量时的总利用率(运行正常线程的所有核心的利用率之和)。当利用率返回到略低于此时的水平时，runtime将其请求的核心数量减少1(“稍微减少”的功能提供滞后以防止振荡)。为每个不同数量的请求核心记录单独的向下扩展利用率。

总体而言，有三个参数控制核心估计机制：用于向上扩展的负载因子，用于核心估计的统计数据平均的间隔，以及用于向下扩展的滞后因子。默认核心策略当前使用的负载因子阈值为1.5，平均间隔为50毫秒，滞后系数为9%的利用率。

7. 评估

我们在Linux上用C++实现了Arachne；源代码可以在GitHub[33]上找到。核心仲裁器包含4500行代码，runtime包含3400行，默认核心策略包含270行。

我们对Arachne的评估解决了以下问题：

·Arachne线程基元的效率如何？Arachne与其他线程系统相比如何？

·Arachne的核心感知线程方法是否为低延迟应用程序带来了显著的好处？

·Arachne的内部机制，如线程调度的无队列方法，以及核心估计和核心分配的机制，对性能有何贡献？

表1描述了用于基准测试的机器的配置。

表1：用于基准测试的硬件配置。所有节点都运行Linux 4.4.0。C状态已启用，Meltdown缓解已禁用。启用了超线程(每个内核2个超线程)。未将计算机配置为执行数据包引导(如RSS或XPS)。

7.1 调度基元

表2：调度基元的平均成本。创建、通知和信令是端到端测量的，从一个线程中的启动到目标线程醒来并开始在另一个内核上执行。Arachne在与父线程不同的内核上创建所有线程。

Go总是在父核心上创建Go例程。uThread使用循环方法将线程分配给核心；当它选择父核心时，平均成本下降到250 ns。在“单向产出”中，控制权从让步线程传递到同一内核上的另一个可运行线程。在“空产率”中，没有其他可运行的线程，因此控制权立即返回到让步线程。“线程退出周转”测量从一个线程的最后一个指令到下一个线程的第一个指令在内核上运行的时间。N/A表示线程系统不公开测量的基元。“Arachne RQ”意味着Arachne被修改为使用就绪队列，而不是第5.3节中描述的无队列调度机制。“No HT”意味着每个线程使用一个超线程在单独的内核上运行；每个内核的另一个超线程是不活动的。“HT”表示每个内核的另一个超线程处于活动状态，运行Arachne 调度器。

表2将Arachne中基本线程操作的成本与C++ std：：thread、Go和uThread[4]进行了比较。std：：Thread基于内核线程；Go在语言运行时在用户级别实现线程；uThread使用内核线程来复用用户线程，如Arachne。uThread是GitHub上评价很高的C++用户线程库，并声称具有高性能。度量使用微基准，因此它们代表最佳情况下的性能。

Arachne的线程操作比任何其他系统都快得多，除了uThread的产量更快之外。 Arachne的缓存优化设计执行线程创建的速度是GO的两倍，即使Arachne将新线程放置在与父核心不同的核心上，而GO在父核心上创建新线程。

为了评估Arachne的无队列方法，我们对Arachne进行了修改，使其在每个核心上使用无需等待的多生产者单消费者队列[7]来识别可运行的线程，而不是扫描所有上下文。我们从GitHub上的几个候选者中选择了这个实现，因为它的速度和简单性。表2显示，无队列方法比使用就绪队列的方法快28-40%(在Arachne的就绪队列变体中，我们为线程创建计数了三个额外的缓存未命中)。

图2：线程创建吞吐量作为可用内核的函数。在(a)中，单个线程尽可能快地创建新线程；每个子线程消耗1µs的执行时间，然后退出。在(b)中，为每个内核创建3个初始线程；每个线程创建一个子线程，然后退出。

我们设计了Arachne的线程创建机制，不仅是为了最小化延迟，而且是为了提供高吞吐量。我们运行了两个实验来测量线程创建吞吐量。在第一个实验中(图2(a))，单个“调度”线程尽可能快地创建新线程(例如，如果单个线程轮询网络接口以获取传入请求，则可能会发生这种情况)。一个Arachne线程每秒可以产生500多万个新线程，这是GO速率的2.5倍，至少是std：：Thread或uThread速率的10倍。这个实验演示了在线程创建时执行负载平衡的好处。Go的工作窃取方法会产生显著的额外开销，特别是在线程生命周期较短的情况下，并且父工作队列可能会成为瓶颈。在较低的核心计数下，GO表现出比Arachne更高的吞吐量，因为除了其他可用核心之外，它还在创建者的核心上运行线程，而Arachne仅使用创建者的核心进行调度。

第二个实验使用分布式方法测量线程创建吞吐量，其中许多现有线程中的每个线程都创建一个子线程，然后退出(图2(b))。在本实验中，Arachne和GO的吞吐量都随着可用核心数量的增加而扩展。uThread和std：：thread都没有可扩展的吞吐量；uThread的吞吐量比Arachne或Go低10倍，而std：：thread的吞吐量比Arachne或Go低100倍。Go的线程创建方法在这个实验中工作得很好；每个核心都在本地创建和执行线程，并且不需要窃取工作，因为负载自然地平衡了自己。结果，GO的吞吐量是Arachne的1.5-2.5倍。Arachne的性能反映了表2中线程创建和退出周转的成本，以及并发线程创建之间的偶尔冲突。

图2还包括Arachne的就绪队列变体的测量。Arachne的无队列方法为两个实验提供了比就绪队列变体更高的吞吐量。

7.2 Arachne用于分布式缓存的好处

我们修改了分布式缓存[23]版本1.5.6以使用Arachne；源代码可以在GitHub[19]上找到。在修改后的版本(“memcached-A”)中，工作线程池被单个调度线程替换，它等待所有连接上的传入请求。当请求到达时，调度线程创建一个新的Arachne线程，该线程的生存期仅足以处理连接上的所有可用请求。memcached-A使用默认的核心策略；调度线程是“独占”的，工作线程是“正常”线程。

memcached-A在原始分布式缓存上提供了两个好处。首先，它减少了内核线程之间(没有多路复用)和应用程序之间(核心专用于应用程序)之间的性能干扰。其次，memcached-A提供了更细粒度的负载平衡(在单个请求而不是连接的级别)。

表3：memcached实验的配置。Program是用于生成工作负载的基准程序(我们的Memtier版本是在原始版本的基础上修改的)。Key和Value给出数据集中键和值的大小(ETC重新创建Facebook ETC工作负载[3]，它模拟memcached的实际使用)。Items是数据集中对象的总数。PUTs是所有PUTs请求的分数(其他请求是GETs)。Clients是客户端的总数(20+1意味着20个客户端生成了密集的工作负载，另外1个客户端使用较轻的工作负载测量了延迟)。Threades是每个客户端的线程数。Conns是每个客户端的连接总数。Pipeline是在减少工作负载之前每个连接允许的最大未完成请求数。IR Dist是请求间时间分布。除非另有说明，memcached配置了16个工作线程，memcached-A自动在2到15个核心之间扩展。

图3：在实际基准下，Memcached和memcached-A获得的吞吐量作为平均值和第99个百分位数的请求延迟的函数。每次测量在5秒热身后运行30秒。Y轴使用对数刻度。

我们使用分布式缓存执行了三个实验；表3总结了它们的配置。第一个实验真实的测量延迟作为真实条件下负载的函数；它使用Mutilate基准[17，27]来重新创建Facebook ETC工作负载[3]。图3(a)显示了结果。分布式缓存的最大吞吐量比memcached-A高20%。这是因为memcached-A使用更少的2个核心 (一个核心为非托管线程保留，另一个为调度器保留)；此外，memcached-A为每个请求生成一个线程会产生开销。然而，memcached-A的延迟明显低于memcached。因此，如果应用程序有服务级别的需求，memcached-A提供更高的可用吞吐量。例如，如果应用程序要求平均延迟小于100µs，则memcached-A支持的吞吐量比memcached高37.5%(1.1 mops/sec与800 kops/sec)。在第99个百分位数时，memcached-A的延迟范围比memcached低3-40倍。我们发现Linux经常在核心之间迁移memcached线程：在高负载下，每个线程每秒迁移大约10次；在低负载下，线程大约每三次请求迁移一次。迁移增加了开销并增加了多路复用的可能性。

我们Arachne的目标之一是自动适应应用程序负载和可用核心的数量，因此管理员不需要指定配置选项或保留核心。图3(b)显示了memcached在分配给它的核心少于它所需的核心时的行为。对于memcached，16个工作线程仅在8个核心上多路复用；memcached-A被限制为最多8个核心。正如预期的那样，两个系统的最大吞吐量都下降了。Arachne继续高效运行：延迟大约与图3(a)中相同。相比之下，memcached在平均和尾部延迟方面都经历了显著增加，这可能是由于额外的多路复用；由于平均延迟限制为100µs，memcached只能处理300 Kops/sec，而memcached-A处理了780 Kops/sec。

图4：Colocation实验中的memcached性能。请求速率从10kops/sec逐渐增加到1mops/sec，然后下降回10kops/sec。在一些实验中，X264视频编码器[25]使用来自Xiph.org[21]的原始视频文件(Sintel-1280.y4m)并行运行。当memcached-A与X264一起运行时，内核仲裁器为memcached-A分配了它所请求的内核数量；X264不由Arachne管理，因此Linux将其调度在memcached-A未使用的内核上。当memcached使用X264运行时，Linux调度程序确定每个应用程序接收到多少内核。默认情况下，X264为自身设置了一个“非常好”的值10；我们没有在这些实验中更改这一行为。(a)显示分配给memcached-A的内核数量；(b)显示memcached和memcached-A的第99个百分位数的尾部延迟；(c)显示平均延迟，加上请求速率；(d)显示视频解码器单独运行或与memcached或memcached-A一起运行时的吞吐量(在结尾平均4秒)。

第二个实验，Colocation，动态地改变负载以评估Arachne的核心估计器。它还测量了memcached和memcached-A与计算密集型应用程序(X264视频编码器[25])协同定位时的性能。结果如图4所示。图4(a)显示，memcached-A在低负载(调度和一个工作线程)时仅使用2个核心，并且随着负载的增加逐渐增加以使用所有可用核心。memcached-A在负载增加时保持接近恒定的平均和尾部延迟，这表明核心估计器选择了更改其核心请求的好点。memcached的延迟高于memcached-A，并且它随负载变化更大；即使在没有后台应用程序的情况下运行时，memcached的99%延迟也比memcached-A高10倍。memcached-A的结尾延迟实际上在高负载时比低负载时要好，因为有更多的核心可用于吸收突发请求。

当后台视频应用程序与memcached共存时，memcached的延迟翻倍，平均和第99个百分位数都是如此，即使后台应用程序以较低的优先级运行。相比之下，memcached-A几乎完全不受视频应用程序的影响。这表明Arachne的核心感知方法改进了应用程序之间的性能隔离。图4(a)显示了memcached-A在与视频应用程序协同定位时更快地提升了其核心使用率。这表明视频应用程序存在一些性能干扰，但核心估计器检测到了这一点，并更积极地分配核心以进行补偿。

图4(d)显示了视频应用程序的吞吐量。在高负载下，它与memcached-A协同定位时的吞吐量不到与memcached协同定位时的一半。这是因为memcached-A将视频应用程序限制在单个非托管核心中。使用memcached，Linux允许视频应用程序消耗更多的资源，这降低了memcached的性能。

图5：具有核心仲裁器(“memcached-A”，与图4相同)和没有核心仲裁器(“NoArbiter”)的协同定位实验中的平均和尾部延迟。

图5显示专用核心是Arachne性能的基础。对于这个图，我们使用一个没有专用核心的memcached-A变体运行了Colocation实验：不是使用核心仲裁器，而是Arachne通过阻塞和解除信号量上的内核线程进行扩展，并且Linux内核调度了未阻塞的线程。如图5所示，无论使用还是不使用后台应用程序，这都会导致延迟显著增加。其他测量表明，当Linux取消调度内核线程时，但Arachne继续将新用户线程分配给该内核线程，会出现延迟峰值；在高负载突发期间，大量用户线程可能会在取消调度的内核线程上搁置许多毫秒。如果没有核心仲裁器提供的专用核心，memcached-A的性能明显低于未修改的memcached。

图4和图5使用了后台视频应用程序的默认配置，其中它将执行优先级降低到“NICE”级别10。我们还在视频应用程序以正常优先级运行的情况下运行了实验；memcached的平均和尾部延迟增加了约2倍，而memcached-A的延迟几乎完全不受影响。由于空间限制，我们省略了细节。

memcached的最后一个实验是skew，如图6所示。当客户端连接之间的负载不均衡时，这个实验将评估memcached的性能。由于静态缓存了工作线程之间的客户端连接，因此可能会出现热点，其中一些工作线程过载，而另一些工作线程处于空闲状态；这可能会导致整体吞吐量较差。相反，memcached-A对每个请求执行负载平衡，因此性能不受跨客户端连接的负载分布的影响。

图6：当目标负载为1.5mops/sec时，工作负载倾斜对memcached性能的影响。最初，负载平均分布在512个连接上(每个memcached工作处理512/16=32个连接)；随着时间的推移，总负载中越来越多的部分通过增加热门工作连接上的请求速率和降低所有其他连接上的请求速率而被定向到一个特定的“热”工作线程。底部的图表显示了memcached中的总体吞吐量以及过载工作线程的吞吐量。

7.3 Arachne用于RAMCloud的好处

图7：当许多客户端执行100字节对象的连续背靠背写入RPC时，单个RAMCloud服务器的吞吐量是以每秒完成的写入数来衡量的。

图8：RAMCloud和RAMCloud-A在修改的YCSB基准[9]上使用100字节对象的比较。两者都使用12台存储服务器运行。Y轴表示30台独立客户端计算机的聚合吞吐量，每台计算机运行8个线程。

我们还修改了RAMCloud[30]以使用Arachne。在修改的版本(“RAMCloud-A”)中，消除了长时间运行的工作线程池，并且调度线程为每个请求创建了一个新的工作线程。忙于等待嵌套RPCs的线程在轮询循环的每次迭代后都会让步。这允许在等待时间内处理其他请求，这样就不会浪费核心。图7显示RAMCloud-A的写入吞吐量是RAMCloud的2.5倍。在YCSB基准测试9上，对于写操作频繁的YCSB-A工作负载，RAMCloud-A提供的吞吐量比RAMCloud高54%。在只读操作的YCSB-C工作负载上，由于Arachne的线程调用和线程退出的开销，RAMCloud-A的吞吐量比RAMCloud低15%。这些实验表明，Arachne使得在阻塞期间短至几微秒安排其他工作变得切实可行。

7.4 Arachne内部机制

本节评估对Arachne的性能至关重要的几种内部机制。如第5.3节所述，Arachne放弃使用就绪队列作为其缓存优化设计的一部分；相反，调度器扫描wakeupTime变量以查找占用的线程上下文，直到找到可运行的线程。因此，当核心充满线程时，它的调度器必须遍历越来越多的上下文。为了评估扫描这些标志的成本，我们测量了发送信号通知特定阻塞线程的成本，同时改变目标核心上其他阻塞线程的数量；图9显示了结果。即使在所有56个线程上下文都被占用的最坏情况下，唤醒线程的平均成本也增加了不到100 ns，这相当于大约一个高速缓存一致性未命中。这意味着避免扫描所有活动上下文的替代实现必须在不引入任何新的缓存未命中的情况下这样做；否则其性能将比Arachne差。图9中Arachne的最差情况性能仍然好于表2中Arachne的就绪队列变体。

图9：随着目标核心上线程数量的增加，发出阻塞线程信号的成本。延迟是从紧接在一个内核上发信号之前直到目标线程在另一个核心上恢复执行为止测量的。

图10：从核心请求到核心获取的延迟的累积分布(a)当核心仲裁器具有可用的空闲核心时，以及(b)当它必须从竞争应用程序收回核心时。

图11显示了需要抢占另一个进程的核心的核心请求的每个步骤的时间。大约80%的时间花费在套接字通信上。

图11：对核心仲裁器的核心请求的时间线。有两个应用程序。这两个应用程序都以单个专用内核开始，而顶级应用程序也以等待放置在内核上的线程开始。顶层应用程序具有比底层应用程序更高的优先级，因此当顶层应用程序请求额外的核心时，底层应用程序被要求释放其核心。

图10和图11显示了Arachne的核心分配机制的性能。图10显示了分配时间的分布，从线程调用setRequestedCores到内核线程在新分配的核心上唤醒为止。在第一种场景下，有一个空闲的核心可供核心仲裁器使用，成本仅仅是将内核线程移动到该空闲核心并解除阻塞的成本。在第二个场景中，必须从较低优先级的应用程序中回收核心，因此成本包括发信号通知另一个进程并等待它释放核心。图10显示，Arachne可以在大约30µs内重新分配核心，即使必须从其他应用程序回收核心也是如此。这使得Arachne能够以毫秒的粒度适应负载的变化。

8. 相关工作

在过去的几十年中，已经开发了许多用户级线程包。我们已经将Arachne与Go[14]和uThread[4]进行了比较。Boost光缆[1]、Folly[13]和Seastar[37]实现用户级线程，但不跨多核多路复用用户线程。Capriccio[39]通过将系统调用替换为异步系统调用解决了阻塞系统调用的问题，但它不能扩展到多个核心。Cilk[8]是用于在内核线程上调度任务的编译器和runtime，但不处理阻塞，并且不是核心感知的。Carbon[16]提出使用硬件队列来调度数百个指令粒度的任务，但它需要对硬件进行更改，并且仅限于并行的fork-join模型。在撰写本文时，Wikipedia[40]列出了21个C++线程库。其中，10个仅提供内核线程，3个提供基于编译器的自动并行化，3个是没有发布任何性能数字的商业软件包，5个似乎已失效。上面列出的系统都不支持线程创建时的负载平衡，计算核心需求和符合核心分配的能力，或者实现特定于应用程序的核心策略的机制。

调度器激活[2]类似于Arachne，因为它们将处理器分配给应用程序以高效地实现用户级线程。调度器激活工作的一个主要焦点是在阻塞内核调用期间允许处理器抢占；这导致了大量的内核修改。Arachne专注于其他问题，例如最小化缓存未命中、估计核心需求以及启用特定于应用程序的核心策略。

Akaros[35]和Parlib[15]遵循调度器激活的传统。Akaros是一个为应用程序分配专用核心并使所有阻塞系统调用异步的操作系统；Parlib是用于在专用核心上构建用户调度程序的框架。Akaros提供了类似于Arachne核心仲裁器的功能，但它似乎还没有达到能够支持有意义的性能度量的成熟程度。

核心仲裁器控制用户空间中的进程调度策略，同时将机制留给内核，类似于Hydra中的策略模块[18]。

在多核心机器上管理多线程应用程序的传统方法是组调度[12，29]。在组调度中，每个应用程序单方面确定其线程需求；然后操作系统尝试在不同的核心上同时调度应用程序的所有线程。Tucker和Gupta指出，当系统过载时，组调度导致低效率的多路复用[38]。他们认为，更有效的方法是划分核心，以便每个应用程序都可以独占使用几个核心；然后，应用程序可以调整其并行度以匹配可用的核心。Arachne实现了这种方法。

基于事件的应用程序(如Redis[34]和nginx[28])代表了用户线程的替代方案，以实现高吞吐量和低延迟。Behren等人[39]认为基于事件的方法是一种特定于应用程序的优化形式，这种优化是由于缺乏有效的线程runtime；Arachne提供了高效的线程作为事件的更方便的替代方案。

最近的几个系统，如IX[6]和Zygos[32]，已经将线程调度器与高性能网络堆栈相结合。这些系统与Arachne的目标相同，即将低延迟与高效的资源使用相结合，但它们通过将线程机制耦合到网络堆栈，采用了比Arachne更特殊的方法。Arachne是一种通用机制；它可以与高性能网络堆栈一起使用，例如在RAMCloud中，但也可以在其他情况下使用。

9. 未来工作

我们相信，Arachne的核心感知调度方法在其他领域将是有益的。例如，虚拟机可以使用多级核心感知方法，其中应用程序使用Arachne与其它客户操作系统就核心进行协商，而客户操作系统使用类似的方法与虚拟机管理程序进行协商。这将提供比目前的方法更灵活、更有效的核心管理方式，因为虚拟机管理程序将知道每个虚拟机需要多少核心。

对于数据中心规模的应用程序，核心感知调度在集群调度器中也是有益的。集群调度器可以从每个集群机器上的核心仲裁器收集关于核心需求的信息，并使用该信息在机器之间放置应用程序和移动服务。这将允许基于实际的核心需求而不是静态声明的最大需求做出决策。Arachne的性能隔离将允许集群调度程序更积极地运行后台应用程序，而无需担心影响前台应用程序的响应时间。

Arachne有几个方面我们还没有完全探索。我们只有初步的实现核心策略的经验，而我们当前的核心策略并没有解决与NUMA机器相关的问题，例如如何在跨多个套接字的应用程序中分配核心。我们希望能够创建各种可重用的核心策略，以便应用程序开发人员可以实现高线程性能，而不必为每个应用程序编写自定义策略。此外，我们在核心估计参数方面的经验是有限的。我们根据基准应用程序的一些实验选择了当前值。当前参数为我们的基准测试提供了延迟和利用率之间的良好权衡，但我们不知道这些参数是否为所有应用程序的最佳值。

10. 总结

操作系统中最基本的原则之一是虚拟化，在虚拟化中，系统使用一组物理资源来实现更大和更多样化的虚拟实体集。然而，只有在虚拟对象的使用和可用的物理资源之间取得平衡时，虚拟化才能起作用。例如，如果虚拟内存的使用超过可用物理内存，系统将在页面抖动下崩溃。

Arachne提供了一种机制来平衡虚拟线程的使用与物理核心的可用性。每个应用程序动态计算其核心需求，并将其传送到中央核心仲裁器，然后中央核心仲裁器在竞争应用程序之间分配核心。核心仲裁器将核心专用于应用程序，并告诉每个应用程序它已经接收到哪个核心。然后，应用程序可以使用该信息来管理其线程。Arachne还在用户级别提供了特别快速的线程实现，这使得即使对于非常短的生存期任务也可以使用线程。总体而言，Arachne的核心感知线程管理方法支持结合低延迟和高吞吐量的粒度应用程序。