ghOSt: Fast & Flexible User-Space Delegation of Linux Scheduling

发表于 | 分类于 | | 本文总阅读量 次
字数统计: 4.1k | 阅读时长 ≈ 15

kernel scheduling mechanism和policy definition分开，将Linux的调度策略部分delegate到用户态，实现user-defined的linux调度策略。

tailoring policies for specific workload能够大幅提高某些指标。 然而，因为调度算法实现在内核中，对新的调度算法的designing、implementing和deploying挑战性太大。

在之前的工作中，存在以下几种问题：

  1. 需要大量应用的修改
  2. 需要dedicated资源
  3. 需要application-specific的内核修改

ghOSt的目标是to fundamentally change how scheduling policies are designed, implemented and deployed. ghOSt provide the agility of userspace development and ease of deployment, while still enabling us-sacle scheduling. ghOSt将kernel scheduling mechanism和policy definition分开了。

Background and Design Goals

Scheduling in Linux

Linux主要通过scheduling classes来支持对多种调度机制的实现。

Implementing schedulers is hard

  1. 通常使用low-level的语言实现
    1. 导致用常用库
    2. 不能用pupular debug工具
  2. depend on并且interact with复杂的同步机制
  3. 长期维护困难

Deploying schedulers is even harder

kernel rollouts需要进行大量的工作。

User-level threading is not enough

虽然有一些用户态的线程调度，但是这些用户态的线程调度是inherently unpredictable的。 主要是因为native thread不受用户态调度算法的控制。 极端情况下，一个holding user-level lock的线程可能被内核de-schedule，造成死锁。 现在的解决方法要么隔离核，这将导致负载低的时候浪费资源。 要么听由native thread scheduler安排。

Custom scheduling via BPF is insufficient

  1. BPF的表达能力有限，访问内核数据结构的能力也有限
  2. 更重要的是，BPF程序是同步的，会block CPU，要求马上决定。而异步方案能够晚点响应，可以考虑的事情更多。

Design Goals

  • Policies should be easy to implement and test
  • Scheduling expressiveness and efficiency
  • Enabling scheduling decisions beyond the per-CPU model：不仅需要增加per-CPU的调度，还需要增加集中式的调度，以及其他中间方案
  • Supporting multiple concurrent policies
  • Non-disruptive updates and fault isolation：调度策略应该与主机内核解耦，并且ghOSt必须允许新策略的部署、更新、回滚，甚至崩溃，而不会产生机器重启的成本。

Design

ghOSt overview

ghOSt在用户态实现agents，主要负责make scheduling decisions，并instruct内核how to schedule native threads on CPUs。 ghOSt在内核态实现一个scheduling class，类似于常用的CFS class。

Partitioning the machine

ghOSt支持以CPU为粒度进行隔离，隔离抽象为enclave。 这么做是有意义的，特别是在一台机器上运行不同的工作负载时。 通过机器的拓扑结构来设置这些飞地的粒度通常是有用的，比如每NUMA-socket或每AMD-CCX。 飞地也有助于隔离故障，将agent崩溃的损害限制在它所属的飞地内。

ghOSt userspace agents

每个由ghOSt管理的CPU都有一个local agent，如图2所示。 在per-CPU的情况下，每个agent负责自己CPU的线程调度决策。 在集中式的情况下，一个全局agent负责调度飞地中的所有CPU。所有其他的local agent是不活跃的。 每个agent在Linux pthread中实现，所有agent belongs to the same userspace process。

Kernel-to-Agent Communication

Exposing thread state to the agents

为了让agent对其权限范围内的线程做出调度决定，内核必须将线程状态暴露给agent。

  • 一种方法是将现有的内核数据结构内存映射到用户空间，如task_structs。然而，这些数据结构的可用性和格式在不同的内核和内核版本之间是不同的。
  • 另一种方法是通过sysfs文件暴露线程状态，以/proc/pid/...的方式。然而，文件系统的API对于快速路径操作来说效率很低，因此很难支持us规模的策略：open/read/fseek，最初是为块设备设计的，太慢而且复杂（例如，需要错误处理和数据解析）。

受分布式系统的启发，ghOSt使用消息作为一种有效而简单的解决方案。

ghOSt messages

Table 1列了定义的message类型。

Message queues

消息是通过消息队列传递给agent的。 ghOSt下每个线程都会被assigned一个队列，所有关于该线程状态变化的消息都传递到该队列。 在per-CPU的例子中，每个线程都被分配到一个与它要运行的CPU相对应的队列中（图2，左）。（注：从图上看来，一个线程或者CPU对应最多一个队列，但一个队列可以对应多个线程或者CPU） 在集中式的例子中，所有线程都被分配到全局队列（图2，右）。 CPU事件的消息，如TIMER_TICK，被路由到与CPU相关的agent线程的队列中。

虽然有很多方法来实现队列，但ghOSt选择在共享内存中使用自定义队列，以有效地处理agent唤醒。

以前的队列机制对ghOSt来说是不够的，因为它们只存在于特定的内核版本。 例如，BPF系统通过BPF环形缓冲区将BPF事件传递给用户空间，最近版本的Linux也通过io_urings将异步I/O消息传递给用户空间。 这些都是快速的无锁环形缓冲器，可以同步消费者/生产者的访问。 然而，较早的Linux内核和其他操作系统并不支持它们。

Thread-to-queue association

在ghOSt的飞地初始化之后，在飞地中有一个单一的默认队列。 agent可以使用CREATE/DESTROY_QUEUE()的API来创建/销毁队列。 添加到ghOSt的线程被默认指定为向默认队列发布消息。 agent可以通过ASSOCIATE_QUEUE()改变这一分配。

Queue-to-agent association

一个队列可以被配置为在消息产生到队列时唤醒一个或多个agent。 agent可以通过CONFIG_QUEUE_WAKEUP()配置唤醒行为。

在per-CPU的例子中，每个队列正好与一个CPU相关，并被配置为唤醒相应的agent。 在集中式的例子中，队列由全局agent持续轮询，所以唤醒是多余的，因此没有配置。

agent的唤醒使用标准的内核机制来唤醒一个阻塞的线程。 这涉及到识别要唤醒的agent线程，将其标记为可运行，可选择向目标CPU发送一个中断以触发reschedule，并执行上下文切换到agent线程。

Moving threads between queues/CPUs

在per-CPU的例子中，为了实现CPU之间的负载均衡和work-stealing，agent可以通过ASSOCIATE_QUEUE()改变消息从线程到队列的路由。 正确协调跨队列的消息路由到agent取决于agent的实现（在用户空间）。

如果一个线程的association从一个队列改变到另一个队列，而原来的队列中还有待处理的消息，那么关联操作就会失败。 在这种情况下，agent必须在ASSOCIATE_QUEUE()之前处理完原始队列中的消息。

Synchronizing agents with the kernel

agent在通过消息观察到的系统状态上进行操作。 然而，当agent正在做出调度决定时，新的消息可能会进入队列，从而改变该决定。 这个挑战对于per-CPU的例子和集中式调度的例子略有不同。

无论怎样，ghOSt用agent/线程序列号来解决这个挑战： - 每个agent都有一个序列号，Aseq，每当有消息被发布到与该agent相关的队列中时，该序列号就会递增。第3.2节中解释了在per-CPU的场景下中对Aseq的使用。 - 每个线程T都有一个序列号，Tseq，每当该线程发布一个新的状态变化消息，MT，这个序列号就会增加。当一个agent pop自己的队列时，它同时收到一个消息和其相关的序列号：（MT，Tseq）。第3.3节中解释了如何使用Tseq进行集中调度。

Exposing sequence numbers via shared memory

ghOSt允许agent通过映射到agent的地址空间的status words，有效地轮询关于线程和CPU状态的辅助信息。 文中为了简洁起见，只讨论了使用status words来暴露上述的Aseq和Tseq给agent的这种用法。 当内核更新一个线程或agent的序列号时，它也更新相应的status words。 然后，agent就可以从shared mapping中的status words里读取序列号。

Agent-to-Kernel Communication

Sending scheduling decisions via transactions

agent通过向内核提交transaction发送调度决定。 受transactional memory和数据库系统的启发，ghOSt通过共享内存设计并实现了自己的transaction API。 agent通过TXN_CREATE()帮助函数在共享内存中open a new transaction。 agent写下要调度的线程的TID和要调度的线程的CPU的ID。 当transaction被填写完整后，agent通过TXNS_COMMIT()系统调用将其提交给内核，这就启动了提交程序并触发了内核启动上下文切换。

Group commits 批处理系统调用分摊开销。

Sequence numbers and transactions 在per-CPU的例子中，提交事务的agent将其CPU让给它正在调度的目标线程。 当agent运行时，发布到队列的消息不会导致唤醒，因为agent已经在运行。 然而，队列中的新消息可能来自于更高优先级的线程，如果agent意识到这一点，将会影响调度决策。 agent只有在下一次唤醒时才有机会检查该消息，这就太晚了。 ghOSt通过序列号来解决per-CPU情况下的这个问题。

一个agent通过检查agent线程的status words来轮询其Aseq，利用Aseq在有新消息发布到与该agent相关的队列时被递增的特性实现检查。 操作的顺序是：

  1. 读取Aseq；
  2. 从队列中读取消息；
  3. 做出调度决定；
  4. 将Aseq和transaction一起发送到TXNS_COMMIT()

如果与transaction一起发送的Aseq比内核观察到的当前Aseq要早（即，有新消息被发布到agent的队列中），transaction将被视为"stale"，并将触发ESTALE错误失败。 然后，agent排空其队列以检索较新的消息并重复这一过程。

Accelerating scheduling with BPF

ghOSt提供的用户级灵活性并不是免费的：消息传递和分组调度最多产生5us（见§4.1的表3）； 在集中式调度模型中，一个线程可能会等待整个集中式调度循环，直到一个调度决定以它的名义被提交（§4.4的30us）。

ghOSt允许通过一个，由agent attach到内核的pick_next_task()函数的，自定义BPF程序来recover lost CPU time。 当一个CPU闲置，而agent还没有发出transaction时，BPF程序会发出自己的transaction，挑选一个线程在该CPU上运行。 BPF程序通过一个shared-memory window into the agent's address space与agent通信。 而agent如何使用BPF infrastructure在CPU上调度线程的具体细节是调度策略的一部分。 ghOSt BPF程序本质上是agent本身的扩展，因此BPF字节码通过libbpf被嵌入到agent binary中。

The Centralized Scheduler

这一节主要讲实现集中式调度的一些细节。

One global agent with a single queue

对于集中式来说，是a single global agent polling a single message queue and making scheduling decisions for all CPUs managed under ghOSt。 如果一个指定的CPU已经运行了一个ghOSt线程，该transaction将抢占之前的线程，而运行新的线程。

Avoiding preemption of the global agent

全局agent必须持续运行，因为任何抢占将直接导致调度延迟。 为了防止全局agent被更高优先级的内核调度类引发的抢占，ghOSt给所有agent分配了一个高的内核优先级，类似于实时调度。 换句话说，机器中的其他线程，无论是ghOSt还是非ghOSt，都不能抢占agent线程。 然而，这种优先权的分配将破坏系统的稳定，除非小心处理。例如，大多数系统都有每个CPU的守护工作线程，它们必须在其指定的CPU上运行。

ghOSt通过以下方式维持系统的稳定性： 所有不活动的agent都会立即退出，腾出它们的CPU。 每当一个非ghOSt线程需要在全局agent的CPU上运行时，全局agent就会执行 "热移交 "到另一个CPU上的非活动agent。 例如，如果内核CFS调度器试图在全局agent正在运行的CPU上运行时，全局agent将首先找到一个空闲的CPU，然后唤醒该CPU上不活跃的agent作为新全局agent。 一旦新的CPU运行全局agent，旧的全局agent就会yield，允许CFS线程运行在原来的CPU上。

Sequence numbers and centralized scheduling

在某些时候，全局agent可能对一个线程的状态有不一致的看法。 例如，一个线程T可能发布一个THREAD_WAKEUP消息。 全局agent收到这个消息并决定将T安排在CPU 1。 同时，系统中的某个实体调用了sched_setaffinity()，导致了THREAD_AFFINITY消息，禁止T在CPU 1上运行。 我们需要一种机制来确保安排T在CPU 1上的transaction将失效。

原则上，我们可以使用agent序列号，就像上面为per-CPU的例子所描述的那样。 然而，全局agent必须支持成千上万的线程，这些线程不断向全局队列发布消息，使得排空队列很费时间。 与per-CPU例子中的本地agent不同，全局agent没有放弃自己的CPU。 The global agent must only verify that it is up-to-date with respect to the thread T being scheduled right now.

ghOSt用线程序列号来解决这个问题。 每条排队的消息MT都打上线程序列号Tseq的tag，如（MT，Tseq）。 当agent提交线程T的transaction时，它将transaction与它所知道的T的最新序列号Tseq一起发送。 当内核收到事务时，它验证Tseq对于transaction中的线程来说是最新的。否则，该事务将以ESTALE错误失败。

Fault Isolation and Dynamic Upgrades

Interaction with other kernel scheduling classes

ghOSt的设计目标之一是使现有系统能够轻松采用。 因此，即使ghOSt策略有问题，我们仍然希望ghOSt管理的线程能够与系统中的其他线程良好地互动。 我们希望避免ghOSt线程对其他线程造成非预期的后果，如饥饿、优先级倒置、死锁等。

我们通过给ghOSt的内核调度器类分配一个比默认的调度器类--通常是CFS--在内核的调度类层次结构中更低的优先级来实现这一目标。 其结果是，系统中的大多数线程将抢占ghOSt线程。 ghOSt线程的抢占会导致THREAD_PREEMPT消息的产生，触发相关agent（运行在不同的高优先级调度类中）做出调度决定。 agent进一步决定如何处理抢占的问题。

Dynamic upgrades and rollbacks

ghOSt通过以下方式实现动态升级：(a)更换agent，同时保持enclave infrastructure的完整，或(b)摧毁enclave，从头开始。

Replacing agents and destroying enclaves

用户空间的代码可以查询并判断一个agent是否连接到一个enclave。 为了升级一个agent，我们同时运行旧的和新的agent；新的agent暂停运行，直到旧的agent崩溃或退出，不再连接。 新agent从内核中提取飞地中所有线程的状态并恢复调度。

如果这个过程失败了，内核或用户空间的代码都可以摧毁飞地。摧毁enclave会杀死该enclave中的所有agent，使系统中的其他enclave保持完整，并自动将被摧毁的enclave中的所有线程移回CFS。 此时，这些线程仍在正常运行，但由CFS而不是ghOSt调度。

ghOSt watchdog

ghOSt或任何其他内核调度器中的调度错误会对整个系统产生影响。 例如，一个ghOSt线程可能在持有内核mutex的时候被抢占，如果它太久没有被调度，它可能会拖慢其他线程，包括那些在CFS或其他ghOSt enclave的线程。 同样地，如果GC和I/O poller等关键线程没有被调度，机器也会陷入停滞。

作为一种安全机制，ghOSt会自动销毁有行为不良的agent的enclave。 例如，当内核检测到一个agent没有在用户可配置的毫秒数内安排一个可运行的线程时，它将销毁一个飞地。

Evaluation

主要从以下几个方面进行实验

  • micro-benchmark（LoC、message delivery overhead、local scheduling、remote scheduling和global agent scalability）
  • Comparison to custom centralized schedulers
  • google snap/google search上的表现
  • 缓解L1TF/MDS攻击