null - 程序员宅基地

优先级调度算法实现_Linux CFS调度器-程序员宅基地

一直没有写过关于Linux内核调度器的内容，这几天被问起，简单的讲了讲，收到一堆challenge，这次决定做一个通篇总结方便自己整理思路。
要说Linux2.4和2.6最大的差异就在于CFS调度器的引入。CFS是 Completely Fair Scheduler 的缩写。不过讲真话，个人并不完全认同“完全公平”调度是这个算法的本意，如何裁决资源抢占（preempt，字面上是优先权）才是这个调度器的本意。

对于时分多任务操作系统来说，可以理解为调度器维护着一个任务池，确定某一时刻CPU到底应该执行哪个任务。简单粗暴一点的调度器往往就是一个round robin，也就是分配相同的时间间隔，大家简单轮流使用CPU。很显然，这种调度才是最公平的，但政治正确的“完全公平”无法满足复杂场景下的调度，于是就有了本文中的CFS调度模型。

至于调度，本质上是CPU运行时间片(epoch)管理，CFS的模型主要的改进是在round robin采用的真实运行时间片的基础上实现了加权出了一个虚拟运行时间的概念vruntime。每个线程（这里理解为系统调度的最小单位，下同）都有一个vruntime值，而不同的权重即该线程的优先级，具体算法为：

这里的权重比是nice 0 的权重和线程权重的比值，nice 0即为系统默认的线程权限，该权重默认为1024。粗暴的理解为在默认条件下，vruntime就等于该线程的实际运行时间。具体来说可以在cgroup中的键值cpu.shares找到这个值，调整这个值可以改变vruntime的计算权重。而既然提到了cgroup，cgroup既然是嵌套的，这个值自然必须嵌套加权。

[root@localhost proc

得到了这个vruntime之后，系统将会根据每个线程的vruntime排序（实际上是基于红黑树算法，这里不展开），vruntime最小的线程则会最早获得调度。而一旦vruntime的次序发生变化，系统将尝试触发下一次调度。也就是说调度器尽可能的保证所有线程的vruntime都一致，而权重高的线程vruntime提升的慢，容易被优先调度；权重低，同样的时间上vruntime上升的快，反而容易被轮空。一个进程的vruntime可以通过/proc/<PID>/sched中的se.vruntime选项查看

[root@localhost 1352

这个时候，有个比较典型的例子就是当系统中存在大量vruntime相似的线程之后，类似多米诺效应，线程调度将会被过于频繁的触发，这明显不合理！于是就如何定义“vruntime触发调度”时，CFS引入了一个阈值，即如果前后两个线程vruntime保持在一个阈值之内，系统不会触发调度。而这个阈值大小就是最小的调度时间片。

此外，CFS本质上是CPU运行时间导向的调度，这就有了另一个规则：对于sleep/IO这类的操作，由于相对来说并不占用过多资源，vruntime并不会被马上结算，仍会保持最初的vruntime。跟到这里，你可能马上出现了一个头脑实验：一个线程A，初始值小但一直sleep，所以vruntime始终不增长；线程B，vruntime初始较大重始终排队等待，这种策略就变得不可理喻了。所以系统在该线程被重新唤醒之后会重新计算vruntime，vruntime将取当期线程的vruntime和当前系统内最小vruntime-阈值这两个值中的最大值。也就是说如果当前系统中有两个及以上线程，当sleep/IO线程被唤醒之后，无论如何该线程将无法获得第一优先调度，最好的情况也要等当前最小vruntime接受调度之后再次触发调度。

另外，在cgroup的目录下还有两个跟调度有关的设定：cpu.cfs_quota_us，cpu.cfs_period_us。这两个值确定的该线程得到调度后CPU时间的占空比。cpu.cfs_period_us是得到调度的周期，而cpu.cfs_quota_us是在这个调度周期内绝对CPU时常，单位都是微秒（us)。

总结一下，如果用上下文切换的方式评价调度器的差异性：

更多的线程分配到更少数量的CPU core上（不区分物理core和逻辑core），上下文切换的次数会增多。如果各个线程的优先级一致，足够多的线程分配最终的结果就是线程的切换频率等于vruntime阈值。
不同的优先级调度只在需要多线程切换时才有效，即便系统中只有一个优先级很低的线程，系统仍有可能达到full utilization（满负载）。
CPU share的方式采用了占空比来控制cpu的utilization，跟上下文切换次数无关。

--原文发布于2018/01/29

Linux CFS调度器 - 开源小站www.litrin.net

--update 2020/10/30 回答网友@quentin zhao的提问

请问对于sleep/IO这类的操作不会马上被调度有什么解决办法吗？只能改调度算法吗？

取决于不同的目的，目前对于调度延时的方法可以说是多种多样啦，简单介绍个几种吧：

调整线程优先级。本文其实探讨了很多cpu.share/cpu.cfs_quota_us之类的设置其实都是服务于这个方法的。简单、容易实现起效最快，但并不能从根本上解决问题。
资源隔离、资源池化技术。主要应用在服务器线上应用，即为重要的几个app或者说进程划分属于它自己独占的资源配额。通过逻辑上的资源隔离确保CPU上的任务不会因为CPU资源调度而被中断。甚至某些极端的还会做CPU中断处理绑定（cpu affinity + IRQ affinity）。缺点这样的方式是以整个系统的计算密度和容量为代价的，运营成本非常高。
轻量级线程（比如协程）、边缘触发、用户态迁移。这是一系列技术的软件实现，旨在将原先应该由kernel调度或者可能导致上下文切换的系统调用降低为用户态自由选择调度的方式。举几个例子的话就是DPDK/SPDK这种绕开kernel直接一个烟囱到用户态的玩法。这类实现都需要重新开发，而且本质上需要改变用户行为，属于“另起炉灶”的方法。
如果单纯只是需要低时延的环境，且调整优先级还不能满足的话。有个选项就是实时操作系统了。其实Linux内核可以实现实时操作系统，但大多数的发行版并不默认提供，需要启用的话必须重新编译内核。除此之外，不同的行业也有自己专属的实时操作系统，只是不被传统上的“IT行业”提及罢了。

本文链接：https://blog.csdn.net/weixin_39932611/article/details/110213972

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

解决安卓模拟器系统中已经是root用户，mount仍然报错：Permission denied_mount: permission denied (are you root?)-程序员宅基地

文章浏览阅读3.4k次。错误信息：root@android:/ # mount -o rw,remount,rw /systemroot@android:/ # mount -o rw,remount,rw /system mount: Permission denied原因分析：可能是系统在启动的时候/system目录已经被分成ro（read-only）权限。所以需要在启动的预先设置为rw权限。1. 找..._mount: permission denied (are you root?)

计算机丢失concrt140,小编教你解决concrt140 dll 【解决教程】的技巧_-程序员宅基地

文章浏览阅读4.5w次。近日有小伙伴发现电脑出现问题了，在突然遇到concrt140 dll时不知所措了，对于concrt140 dll带来的问题，其实很好解决concrt140 dll带来的问题，下面小编跟大家介绍concrt140 dll解决方法：丢失CONCRT140.dll，怎么办？答：分析及解决：网上下载这个DLL文件，将其放置到system32目录下面。重启系统，或者在CMD下面运行regsvr32*.dl..._concrt140.dll下载教程

微信小程序源码案例大全_微信小程序switch页面demo-程序员宅基地

文章浏览阅读4.3k次，点赞4次，收藏62次。微信小程序demo：足球，赛事分析小程序简易导航小程序demo：办公审批小程序Demo：电魔方小程序demo：借阅伴侣微信小程序demo：投票微信小程序demo：健康生活小程序demo：文章列表demo 微商城（含微信小程序）完整源码+配置指南微信小程序Demo：一个简单的工作系统微信小程序Demo：用于聚会的小程序微信小程序Demo：Growth 是一款..._微信小程序switch页面demo

SLAM学习笔记(Code2)----刚体运动、Eigen库_eigen.determinant-程序员宅基地

文章浏览阅读2.2k次。2.1除了#include<iostream>之外的头文件#include <Eigen/Core>//Core:核心#include <Eigen/Dense>//求矩阵的逆、特征值、行列式等#include <Eigen/Geometry>//Eigen的几何模块，可以利用矩阵完成如旋转、平移/***其他***/#include <ctime>//可用于计时，比较哪个程序更快#include <cmath>//包含a_eigen.determinant

图像梯度-sobel算子-程序员宅基地

文章浏览阅读1w次，点赞12次，收藏61次。（1）理论部分x 水平方向的梯度，其实也就是右边 - 左边，有的权重为1，有的为2 。若是计算出来的值很大说明是一个边界。y 竖直方向的梯度，其实也就是下面减上面，权重1，或2 。若是计算出来的值很大说明是一个边界。图像的梯度为：有时简化为：即：（2）程序部分函数：Sobelddepth 通常取 -1，但是会导致结果溢出，检测不出边缘，故使..._sobel算子

cuda10.1和cudnn7.6.5百度网盘下载链接（Linux版）_cudnn7.6网盘下载-程序员宅基地

文章浏览阅读3.6k次，点赞17次，收藏8次。cuda10.1和cudnn7.6.5百度网盘下载链接（Linux版）在官网下载不仅慢，，，主要是还总失败。。终于下载成功了，这里给出百度网盘下载链接，希望可以帮到别人百度网盘下载链接提取码: vyg5_cudnn7.6网盘下载

随便推点

《重构-改善既有代码》-程序员宅基地

文章浏览阅读1.2k次，点赞15次，收藏21次。1、如果你发现自己需要为程序添加一个特性，而代码结构使你无法很方便地达成目的，那就先重构哪个程序，使特性的添加比较容易的进行，然后再添加特性2、重构前，先检查自己是否有一套可靠的测试机制，这些测试必须有自我检验能力3、重构技术就是以微小的步伐修改程序，如果你犯下错误，很容易便可发现它4、任何一个傻瓜都能写出计算机可以理解的代码，唯有写出人类容易理解的代码，才是优秀的程序员5、重构（名词）：对软件内部结构的一种调整，目的是在不改变软件可观察行为的前提下，提高其可理解性，降低其修改成本。

NILM（非侵入式电力负荷监测）学习笔记 —— 准备工作（一）配置环境NILMTK Toolkit_nilmtk学习-程序员宅基地

文章浏览阅读1.9w次，点赞27次，收藏122次。安装Anaconda，Python，pycharm我另一篇文章里面有介绍https://blog.csdn.net/wwb1990/article/details/103883775安装NILMTK有了上面的环境，接下来进入正题。NILMTK官网：http://nilmtk.github.io/因为官方安装流程是基于linux的（官方安装流程），我这里提供windows..._nilmtk学习

k8s-pod 控制器-程序员宅基地

文章浏览阅读826次，点赞20次，收藏28次。如果实际 Pod 数量比指定的多那就结束掉多余的，如果实际数量比指定的少就新启动一些Pod，当 Pod 失败、被删除或者挂掉后，RC 都会去自动创建新的 Pod 来保证副本数量，所以即使只有一个 Pod，我们也应该使用 RC 来管理我们的 Pod。label 与 selector 配合，可以实现对象的“关联”，“Pod 控制器” 与 Pod 是相关联的 —— “Pod 控制器”依赖于 Pod，可以给 Pod 设置 label，然后给“控制器”设置对应的 selector，这就实现了对象的关联。

ico引入方法_arco的ico怎么导入-程序员宅基地

文章浏览阅读1.2k次。打开下面的网站后，挑选要使用的，https://icomoon.io/app/#/select/image下载后解压，先把fonts里面的文件复制到项目fonts文件夹中去，然后打开其中的style.css文件找到类似下面的代码@font-face {font-family: ‘icomoon’;src: url(’…/fonts/icomoon.eot?r069d6’);s..._arco的ico怎么导入

Microsoft Visual Studio 2010（VS2010）正式版 CDKEY_visual_studio_2010_professional key-程序员宅基地

文章浏览阅读1.9k次。Microsoft Visual Studio 2010（VS2010）正式版 CDKEY / SN：YCFHQ-9DWCY-DKV88-T2TMH-G7BHP企业版、旗舰版都适用推荐直接下载电驴资源的vs旗舰版然后安装，好用方便且省时！） MSDN VS2010 Ultimate 简体中文正式旗舰版破解版下载(附序列号) visual studio 2010正_visual_studio_2010_professional key