学习和研究中前行,并在分享中提升自己

欢迎订阅阿里内推邮件



linux 下cfs 调度器研究

阅读次数: 365| 时间:2018年2月14日 21:53 | 标签:linux-task

前言

对于一个操作系统来说,任务调度系统是其核心之一。一方面要保证各种类型的任务的及时运行避免被“饿死”,另外一方面又要尽量减少调度算法复杂度。今天我们主要介绍linux cfs task 调度器的一些核心思想

系统中task类型

在介绍cfs 调度器之前,我们先来看一下在linux系统中存在的三种task 任务类型

  • 批量执行任务(batch):这类任务不在意执行的latency和时效性,只关注在给定的时间内尽可能完成多的任务
  • 交互性任务:比如文档编译操作等,这类任务比较关注在睡眠之后是否能及时被唤醒并被调度执行
  • 实时任务:这类任务就比较关注latency和时效性,比如视频编解码等。

通常一个的好的调度器,必须能够同时handle住这种三种类型task的需求。

怎么去衡量一个调度的器的好坏

  • cpu使用率:cpu使用饱和度(越大越好)
  • 吞吐量:单位时间内完成的任务数量(越大越好)
  • task在 ready queue里面等待调度时间(越小越好)
  • task 从开始到完成的时间(越小越好)
  • 调度latency:task 被唤醒到真正被调度的时间 (越小越好)
  • 能满足不同任务的需求

cfs 介绍和核心思想

cfs是全称Completely Fair Scheduler,完全公平的调度器。之所以称为公平,是因为他可以确保在一个调度周期(sched_latency_ns),让每个进程在这个周期内至少有机会运行一次,换一种说法就是每个进程等待CPU的时间最长不超过这个调度周期;然后根据进程的数量,大家平分这个调度周期内的CPU使用权,由于进程的优先级即nice值不同,分割调度周期的时候要加权;每个进程的累计运行时间保存在自己的vruntime字段里,哪个进程的vruntime最小就获得本轮运行的权利。

1.cfs 对进程的管理 在cfs中是通过red-black树来管理的,树中的结点是以剩余vruntime来进行排序的,左边的结点task剩余的vruntime要比右边的多,因此调度器总会选择左树最左端的那个进程来运行。由于使用的是红黑树,所以该算法的时间复杂度为O(log(n)),其中n为系统中task总数量

2.新进程vruntime的初始化 当一个新的进程被fork出来之后,那么这个进程的vruntime应该是多少呢?如果是0的话,那就会导致这个task常时间的占着cpu,那么其他老的进程就会面临着得不到cpu而饿死的风险,就谈不上公平了。为了解决这个问题,每cpu的cfs_rq都维护了一个minimum的vruntime,当新进程fork出来之后 vruntime就是所在cpu的cfs_rq的最小vruntime.

3.睡眠进程的vruntime的处理 试想一下如果你用vim打开源码文件,在思考良久之后准备写下一行代码时,可能发现居然等了很久vim才反应过来。没错这就是一个典型的睡眠到唤醒的场景,那么cfs为了在这种场景下能尽快反应,cfs会对刚唤醒的进程进行vruntime补偿,同时会检查是否可以抢占当前正在运行的进程。由于其vruntime被补偿,所以很大概率唤醒的进程会抢占当前正在运行的进程。

上面描述的是一种正面的场景,也是我们希望发生的。但是有一种类似的场景却会影响性能,场景是这样的。A,B两个进程跑在同一个cpu上,A进程需要进行业务计算,B进程是一个无关紧要的监控程序,每隔2分钟会查看一下服务器相关指标,然后睡眠。虽然B进程运行的时间不长,但是唤醒/睡眠的非常频繁。而每次唤醒都会打断A进程,导致A进程大量contex switch,近而影响整体性能。

后续

今天,先介绍到这里,下一篇准备介绍一下怎么使用perf debug scheduler并进行性能优化。