ghOSt Fast & Flexible User-Space Delegation of Linux Scheduling
AOS课程选题。
背景
定制的调度策略可以提高许多关键指标，较重要的有延迟、吞吐量、实时性，能耗，缓存干扰，安全性等。但是一方面定制的调度策略本身不具备普适性，需要对具体情况进行分析，另一方面硬件的发展如多核，异构计算等，也对调度程序和调度模型提出了挑战。
以Linux操作系统举例分析，目前的调度算法和策略存在以下问题：
操作系统默认采取CFS（Complete Fair Schedule）算法进行线程的调度，内核中的调度模块允许用户通过设定线程的nice值来对调度策略提出建议，但是这存在着不足。首先，用户只能在一定程度上提供建议，调度模块并不保证完全按照用户的建议进行调度。另外，用户无法突破CFS调度算法的框架，无法采用一些复杂的动态调度算法，如监测关键请求发生。因此Linux操作系统目前还不能支持用户执行自定义的调度策略。
如果由用户重写内核调度模块的话，一方面用户需要掌握大量的汇编、C语言、内核知识，需要进行大量的开发工作，另一方面内核模块的bug会直接导致操作系统的崩溃，考虑在用户自定义策略需求旺盛的云端，一段时间的机器崩溃和修复往往是厂商或用户不可承受的巨大成本。
目前用户可以通过eBPF（Extended Berkeley Packet Filter）的方式在内核态中执行经过审查的安全代码，即可以用这种方式实现用户自定义的调度策略。但是eBPF的速度较慢，可执行指令数具有上限，可访问的内核数据有限，不符合调度线程的需求。
因此出现了对于可自定义调度策略调度框架的需求。ghOSt框架基于上述实现用户自定义调度策略的问题，在设计时便列出了以下目标：
调度策略应易于实现和测试，减轻用户的开发使用难度
调度框架应注重于性能和效率，实现微妙级别的调度并保持调度策略的效率
调度框架应支持现代的调度模型，支持细粒度的调度单位，适应现代的计算集群
调度框架应该支持多种调度策略并行互不干扰
调度框架应该提供策略部署、升级、回滚甚至崩溃的支持
贡献
在本文中我们提出了ghOSt，它是一个原生的系统调度线程卷国家，将执行策略委托给了用户态程序执行。ghOSt的目标是从根本上改变调度策略被设计，应用和部署的流程，与此同时ghOSt提供了便捷的使用和简易的部署支持，能实现微妙级别的调度，支持多种调度策略并行互不干扰。通过ghOSt，用户可以轻松地实现自定义的调度策略，并快捷安全地部署在任何场景，并且几乎不添加额外的开销。在本文中我们还提出了中心化的调度模型，相比于传统的CPU调度模型，中心化模型更加符合现实应用场景，ghOSt框架对二者都做出了支持。
原理
ghOSt由内核态和用户态两部分组成，内核态利用权限向用户态提供内核中的线程信息，而用户态则接受内核态的信息，执行用户编程的调度策略，将调度结果发还给内核态予以执行。由此ghOSt便支持了用户自定义调度策略的部署和执行，基本满足了框架的设计目标。
内核态向用户态通信
内核态负责向用户态提供必要的调度信息，将线程信息如task_struct发给用户态辅助调度策略执行。因此用户态可以使用任何语言实现，只需要接受给定的信息，生成相应格式的调度结果即可，这便减轻了用户的开发负担，不必深入汇编，内核等相对底层的实现。
内核态通过消息队列的方式向发送信息，其中包括了像线程创建，线程唤醒等信息，以支持用户态编写较为复杂的实时动态调度算法，以服务器场景为例，用户自定义调度策略可以监测关键请求的来临，通过针对分配资源的方式降低服务的尾延迟。
在用户态收到了内核信息后，执行用户编写的调度策略，得到调度结果后发送中断以切换到待执行的线程。ghOSt框架也为用户态提供了相应的syscall API来支持消息队列的操作，在多CPU模型中，可以通过这些接口实现CPU间线程的迁移和管理。
用户态向内核态通信
用户态对应着一个或多个的处理器，用户态中包含用户所编写的调度策略，在收到内核态发送的线程信息后执行用户调度策略，将生成的结果回发至内核态，并通过syscall引发中断，调度到待执行的线程。
在调度开始后，调度器作为一个线程就让渡了自身的执行权，这时用户态是处于等待执行的状态，如果此时内核态更新了线程的状态信息，例如一个被策略标记为关键的线程开始执行了，此时就应该改变调度策略。为了支持复杂的动态的调度策略，ghOSt框架借鉴了分布式系统的设计，在消息中加入了时间戳。内核态向用户态发送的信息具有自增的序列号，而用户态回复的调度结果也需要带有此信息号，只有内核态收到的事务序列号等同于发出的消息序列号时才会视为一次交互，否则会返回错误令用户态重新生成调度策略。这样就为调度策略的设计提供了较为灵活的动态性，可以根据情况灵活地调整。
实现
错误容忍技术
飞地（Enclave）是指一个隔离的线程运行环境，是由硬件支撑的隔离技术。ghOSt框架使用了飞地技术，每个用户端与他们所负责调度的程序运行在同一个飞地当中。由此，ghOSt框架就可以大幅降低用户开发，部署，测试的难度，即使用户编写了错误的调度算法也不会影响到其他飞地以及内核的正常运行，即使发生了崩溃也只是导致这一飞地中的线程组出现调度问题。另外，多个互不干扰的飞地可以让ghOSt框架支持多种调度策略并行，不同的线程组使用不同的调度策略。
从设计的角度说，ghOSt也为调度崩溃留有冗余机制，ghOSt的调度类实现为了系统调度的低优先级调度类，当ghOSt行为发生异常后将会自动转交给默认的调度器进行调度，实现了较强的错误容忍机制。ghOSt也实现了更新机制，当用户端的策略需要进行调整时，会拉起一个新的用户端，直至新的用户端完成交互后，旧的客户端将结束。
中心化模型
为了满足中心化模型下多处理器调度场景，ghOSt框架需要管理本地或远程的多计算集群，由一个全局的用户态调度多个计算集群或CPU执行任务，控制各计算群调度策略以及计算群间的任务调度。在这种场景下就要仔细地考虑每个计算群的执行状态，因此ghOSt借鉴了数据库的概念，采用了transaction(事务)的方式来确认用户态发给内核态的信息，用户态产生的调度结果通过事务发送给内核态，在事务提交后才视为一次有效的调度，如果远程计算集群无法立即回应调度，那么事务不会被确认提交，内核态调度程序发现这一情况可以进行处理，重新发送调度要求或者转交由其他处理器执行。考虑到调度框架的性能要求，事务模型采用共享内存的方式实现以加快速度。
在中心化模型中，ghOSt框架会维护一个全局的用户态程序，全局的用户态程序会接受多个调度请求，然后将涉及的中断打包发给处理器，以减少信息传递的代价，这里利用了处理器硬件支持的batch interrupt功能。在涉及到计算集群间的任务迁移时，全局的用户态程序会发送IPI（Inter Processer Interrupt），触发迁移目的地集群中断实现。
实验
ghOSt是一个用户自定义调度策略执行框架，因此本文的实验评估基于以下三个方面开展：
- ghOSt框架带来的额外开销有多大？
- ghOSt框架执行自定义策略调度效果如何？
- ghOSt框架是否具有实用性？
性能与效率
经过测试，ghOSt框架的调度开销是微秒级别，相比于内核原生的调度器并没有添加过于沉重的开销。在中心化模型下，较大的开销是在remote schedule上，对多个处理器进行调度并通过处理器间中断（IPI）的方式进行调度。
同时作者也比较了使用ghOSt执行调度策略和定制的调度器之间的差距，实验表明ghOSt几乎可以达到定制调度器的调度效果，但是当然在性能上有所不足，这也是灵活性与性能的取舍。
实际场景应用
作者选取了Google Snap 和 Google Search任务来模拟真实的云端使用场景，以说明ghOSt框架的可用性。这里以Google Search测试为例，使用ghOSt执行用户自定义的调度策略，可以看到整体的吞吐量相矫CFS没有明显变化，但是自定义策略在AB两个案例中可以显著的降低尾延迟。这说明了ghOSt框架在真实场景下是可用的，可以大幅度提升处理效率。这里的实验C作者分析是由于定制策略还有待改进，使得提升效果不明显。
总结
ghOSt框架实现对了用户自定义策略的支持，将调度任务又内核态委托给了用户态执行，简化了用户开发、测试、部署的流程，在几乎不增加调度性能开销的基础上实现了功能强大的调度框架支持，为多调度策略，中心化模型提供了良好的支持。
通过ghOSt框架的实验测试，在云端等场景下存在着巨量的通过改进调度策略而提升执行效率的空间，这也为调度方向后续的研究提供了参考。