Linux阅码场

文章数:529 被阅读:836730

账号入驻

虚拟化场景用什么调度器更合适? 看看来自Amazon的Coscheduling

2019-10-09
    阅读数:

BFS和MuqSS两个调度器的介绍之后,本文再介绍一种有意思的调度器,即Coscheduling。

一直以来任何技术让人觉得都是 简单为美。 不管是设计上还是实现上。比如操作系统的任务调度算法,从FIFO到CFS以及多级反馈队列,都是能一两句话说清楚并让人理解的,同时其代码实现也是及其精炼的。

最近出来的一个新的调度算法有点不同。它也是可以用一两句话说清楚的,但是在实现上却看上去很复杂。

这就是Coscheduling。

先看介绍:https://lwn.net/Articles/764482/本文不会对上文做翻译,只是谈谈自己的理解。

接下来再看看patch:https://lwn.net/ml/linux-kernel/20180907214047.26914-1-jschoenh@amazon.de/

我的天,60个patch...

但实际上,这并不意味着这个算法真的是如此复杂,而是在既有的Schedule框架下实现它有点困难。

Linux Coscheduling调度器的思想还是很简单的。


Coscheduling的本质在于 “一组CPU排他式选择一组task” 。要点如下:

  • 一组CPU 一组CPU按照现代服务器CPU缓存层次化布局来分组,类似Linux调度域那般的CPU分组方式。

  • 一组task 一组进程按照业务逻辑相关性来分组,比如同一个进程的不同线程,同一个用户的不同进程。

  • 排他式 排他式的意思是,同一组的CPU同时只能运行同一个task组内的task或者idle。

下面是一个示意图:

我们来看看Coscheduling调度器解决了哪些问题,其应用场景是什么。来自patch介绍中的说明:

Coscheduling倾向于将一个调度组的CPU资源作为一个整体调度执行一组task。

这是 并行操作系统调度 的正确思路,和传统的Linux调度器核心是孑然不同的。传统的Linux调度器,O(1)调度器也好,CFS也罢,其核心还是在于 一个CPU选择一个task ,然后显式的在多个CPU之间做rebalance。虽然Linux内核实现了组调度,但却没有实现组CPU。

换句话说, 现代Linux,现代Windows等现代操作系统内核对待多CPU平台的态度相当于对待多个单CPU平台的叠加。

Coscheduling的不同在于,调度行为基于组来进行,形成task和CPU之间的排他式多对多映射而不是一对一映射。全局最优解在调度过程中产生,而不是靠显式机制来产生。这一点和BFS,MuqSS等不谋而合,此外,RIP路由协议,Spanning Tree协议等也是这个思路。

Coscheduling的这种策略对于需要并行化执行的多线程程序非常有意义,比如并行计算,虚拟化这些,最大限度地提高了资源的利用率,减少了切换带来的颠簸。

如果我们把时间和空间看作是效果等同的两个维度,其实我们会发现在内存和cache的关系这个空间维度上,早就实现了类似的进化,从直接映射,到全相联映射,再到组相联映射,从最初的一个内存位置映射到一个缓存位置,到最终的一组内存位置映射到一组缓存位置,实现了缓存的高效利用。

另一方面,在现代操作系统领域,时间和空间并不是正交的。缓存的布局和调度算法总是相互影响。


我们再来看看Coscheduling是否有必要,也就是说,现有的技术能不能通过组合达到相同的效果。

cpuset应该是都能想到的。

把一组task排他式地设置到一个cpuset。可是这真的和Coscheduling一样吗?

并不是。因为cpuset在空间上是排他的,时间上却不是分时的。比如一个task组tg1,包含P1,P2两个task,被设置进了cpuset1,如果想要cpuset1排他选择tg1,那么cpuset1便不能加入任何其它的task。这显然与Coscheduling不一致。

Coscheduling将排他调度全部交给了调度器,一个CPU组中可以有很多task组,由Coscheduling调度器决定当前哪个task组占有该CPU组。

这意味着Coscheduling真的是一个全新的调度算法。


采用不同思路的Coscheduling解释了为什么其实现这么复杂,因为既有的Schedule框架并不适合Coscheduling。

由于patch过于庞大且复杂,Coscheduling在可预见的将来合入主线的可能性非常小。我们也只能通过自己打patch的方式来学习以及使用它。但确实由于patch过于庞大,且目前根本就没有benchmark,所以更加合理的做法就是,依照Coscheduling的思路自己实现一个类似的,采用Con Kolivas直接改schedule实现的方式。


浙江温州皮鞋湿,下雨进水不会胖。

(完)

      Linux阅码场原创精华文章汇总

Linux阅码场精选在线视频课程汇总

更多精彩,尽在"Linux阅码场",扫描下方二维码关注



你的随手转发或点个在看是对我们最大的支持!

About Us 关于我们 客户服务 联系方式 器件索引 网站地图 最新更新 手机版

站点相关: TI培训

北京市海淀区知春路23号集成电路设计园量子银座1305 电话:(010)82350740 邮编:100191

电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2018 EEWORLD.com.cn, Inc. All rights reserved