在任何多路复用资源的系统中,计算在哪里运行以及何时运行的调度问题都可能是最基本的问题。然而,就像计算机中许多其他重要问题一样(例如数据库中的查询优化),调度器的研究像钟摆一样,时而活跃,时而处于休眠状态,因为它被认为是一个“已解决”的问题。
调度一直是系统和网络中最基本的操作之一。它涉及将任务分配给CPU并在它们之间进行切换,这些决策对应用程序性能和系统效率都至关重要。长期以来,操作系统(OS)调度专注于公平性。
然而,近年来的两个发展导致了OS调度研究的复兴。首先,云计算的出现赋予了不同的,难以优化的指标。例如,微延迟和微秒(µs)尺度,这些指标在传统的调度器中没有被考虑。其次,摩尔定律的结束使得操作系统堆栈(包括调度)的专业化成为了继续提高性能的必要条件。
近年来有三篇论文或许实现了性能、可扩展性和策略选择相关的突破。第一篇论文挑战了低延迟(通常通过配置专用核心实现)和高利用率(需要核心重新分配)之间的假定权衡,通过在单微秒粒度上实现分配决策来解决这个问题。第二篇论文通过将策略的创建和操作进行分解,使得用户空间代理完全可以处理策略的创建和操作,而固定的内核机制则负责向代理通信事件和应用实施调度决策。第二篇论文根据微秒级灵活策略进行负载均衡和分配决策的能力,最终选择了根据应用程序选择策略的问题。
1. 微秒级核心重新分配
第一篇论文由Ousterhout等人回答了一个基本问题,即操作系统中核心分配可以多快进行以及这种重新分配是否有益于应用程序的性能。该论文介绍的系统名为Shenango,挑战了广泛存在的观念,即在微秒级别上跨应用程序分配核心是不可行的,因为存在高开销和潜在的缓存污染。
在这篇论文中,作者们详细阐述了Shenango系统的设计和实现,包括如何实现快速核心重新分配,以及如何避免因重新分配而导致的性能下降。此外,作者们还通过大量的实验验证了Shenango系统的有效性,快速核心重新分配确实是可能的,并展示了其在性能方面的显著优势。
在Shenango操作系统中,我们实现了微秒级别的核心重新分配,其关键在于使用了专用调度核心。该核心每5微秒可以做出一次CPU核心的分配决策,以确保系统的高效性。为了确定何时从应用程序中分配或回收核心,Shenango监视每个应用程序的线程运行队列和网络数据包队列的长度,并使用其导数作为拥塞信号。这种方法可以有效避免系统拥塞,保障了系统的稳定性和可靠性。同时,该算法完全在专用核心上运行,该核心还管理将传入的网络数据包引导到其相应的目标应用程序的CPU核心。这使得整个系统的运行更加高效,同时也提高了系统的可靠性和安全性。
作者们展示了这种方法的有效性,通过展示如何通过细粒度的CPU核心重新分配,来改善在同一系统上共存的延迟敏感和批处理应用程序的性能。通过基于瞬时输入的数据包速率分配CPU核心,Shenango操作系统在使用5微秒核心重新分配间隔与100微秒间隔相比,前者的延迟降低了,后者的吞吐量提高了6倍以上。随后的研究表明,Shenango的微秒级调度程序还可以帮助缓解其他系统资源(例如缓存和内存带宽)的干扰,并向网络提供细粒度反馈以防止过载。
2. 部署操作系统调度到Linux的框架
构建像Shenango这样高效的调度器是一个有趣的实验室练习,但是在生产环境中需要考虑更多的因素。比如,如何兼容现有的应用程序和操作系统(如Linux),如何满足不同的需求以及如何实现更高的可扩展性和可靠性等等。为了解决这些问题,一些Google的工程师构建了一个名为ghOSt的框架,该框架可以实现不同的调度策略,并将它们部署到Linux内核中,以方便用户更容易地使用。
ghOSt设计背后的关键理由是为了提高操作系统的灵活性。ghOSt从微内核中汲取灵感,将OS调度委托给用户空间代理,可以是全局的或每个CPU。这种方法的优点显而易见:用户空间代理可以根据不同的需求和场景制定不同的调度策略,而不仅仅是受限于内核代码的固有规则。因此,开发人员可以享受用户空间开发的灵活性,而不受内核代码的限制和长时间部署周期的困扰。
为了在用户空间代理和内核之间实现无缝的通信,ghOSt使用了共享内存来传递提示信息,使代理能够做出更明智的调度决策。这种方法不仅提高了操作系统的性能,而且还为应用程序提供了更广泛的功能和更高的效率。而最简化内核调度类,是ghOSt设计中最为重要的组成部分之一。内核调度类负责将代理传递的调度事件转换为内核可以理解的格式,并将处理结果返回给代理。
总的来说,ghOSt的设计使得操作系统变得更加灵活和高效,从而能够更好地满足不同用户的需求。它为开发人员提供了更多的自由度和创造空间,使得他们可以更好地实现自己的想法和创意。同时,ghOSt的设计也为用户提供了更好的体验和更快的响应速度,使得他们能够更加高效地完成工作。
ghOSt面临的最大挑战是内核组件与用户空间代理之间的通信延迟,可能需要达到5微秒。这可能会导致:
(1)竞争条件,例如,用户空间代理向已从线程的CPU掩码中删除的CPU来调度线程);
(2)低利用率,因为CPU保持空闲等待代理的调度决策。
ghOSt通过在共享内存上实现事务API来避免竞争条件,该API允许代理以原子方式提交调度决策。为了减轻第二个问题,作者们建议使用自定义的eBPF程序,在每个核心上本地运行并临时调度任务,直到收到代理的决策。当将其他操作系统功能卸载到用户空间(例如内存管理)时,相同的技术也适用。