Linux内核2_6_24的CFS调度器分析
第27卷第2期2010年2月计算机应用与软件
ComputerApplicationsandSoftwareVol.27No.2Feb.2010
Linux内核2.6.24的CFS调度器分析
杜慧江王云光
(上海医疗器械高等专科学校医用电子仪器系
上海200093)
摘
Linux内核2.6.24采用了新的调度器CFS(CompletelyFairScheduler),以公平的原则对待所有任务。其性能和对交互进
程的响应速度都超过之前版本内核的O(1)调度器,并且算法与实现也更简单。先简单对比了O(1)和CFS,然后结合源代码对CFS
要
的算法和实现作了分析。关键词
Linux
内核
调度器
CFS
ANALYSISOFCOMPLETELYFAIRSCHEDULERINLINUXKERNEL2.6.24
DuHuijiang
WangYunguang
(DepartmentofMedicalElectronicsApparatus,ShanghaiMedicalInstrumentationCollege,Shanghai200093,China)
AbstractLinuxkernel2.6.24hasadoptedanewCompletelyFairScheduler,theprincipleofitisthefairtreatmentonalltasks.Itsper-
formanceandrespondingspeedoninteractivetasksareallsuperiortopreviousschedulerO(1),anditsalgorithmandimplementationaresim-plertoo.InthispaperwedrawasimplecomparisonbetweenCFSandO(1),andthenbrieflyanalysethealgorithmandimplementationofCFSaccordingtoitssourcecode.Keywords
Linux
Kernel
Scheduler
CFS
为提高交互式任务的响应速度,每次时钟中断中,当前任务
的时间片被减1,当时间片为0时,调度器判断其类型,如果是交互式任务,则重置其时间片并重新插入active数组;否则将其从active数组中移到expired数组,这样交互式任务就总能优先获得CPU。但是这些任务不能一直留在active数组中,当交互任务已经占用CPU的时间超过一个固定值后,也会被移到ex-pired数组中。若active数组为空,则交换active数组和expired数组,开始新的一轮调度。
O(1)调度器算法的不足之处在于会在很多情况下失效,导致交互式任务反应缓慢。
Linux2.6.22内核使用的是O(1)调度器,它支持SMP并且
用来选择合适的能保证无论系统的负载和处理器的数目如何,任务并且给它分配处理器所花费的时间是固定的。
O(1)调度器的任务调度主要包括两部分工作:
(1)动态计算任务优先级普通任务的优先级是动态计算
min(staticpriority-bonus+的,由公式dynamicpriority=max(100,
5,139))[2]得出。其中bonus取决于任务的平均睡眠时间。普通其bonus就越大,从而得到更高的优任务的平均睡眠时间越长,先级。静态优先级越高,任务所能分配到的时间片也越长。实时
而且总是比普通任务的优先级高。任务的优先级不会动态修改,
(2)选出下一个获得CPU的任务普通任务的调度选择
算法基于任务的优先级,当前拥有最高优先级的任务被调度器选中。调度器为每个CPU维护了两个任务队列数组:active数组和expired数组。数组中的元素保存着某一优先级的任务队列指针。当需要选择下一个任务时,不用遍历所有任务队列,而是直接从active数组中选择当前最高优先级队列中的第一个任务。这种算法的复杂度为O(1)。
0引言
Linux的稳定内核版本从2.6.24开始,使用了新的调度程序CFS,能够更加公平高效地调度所有任务(包括进程和线程),平衡交互任务和普通任务。本文首先将2.6.22内核的O(1)调度器与CFS进行比较,然后根据源代码对CFS的实现进行分析。
1O(1)调度器
2
CFS调度器
CFS调度器由IngoMolnar提出,采用了完全公平的思想对
“公平”不等于同等对待所有任务,而是指相待所有任务。但是
对长程的、统计上的公平。在每个小的时间区间很可能看起来
并不公平,原因可能是需要对以往的不公平作出补偿、系统的负载变化等。
CFS还增加了一个调度器模块管理器,各种不同的调度算法可以作为一个模块注册到该管理器中。不同的任务可以选择使用不同的调度器模块,例如实时任务可以选择实时任务调度CFS实现了两个调度算法,CFS算模块。Linux2.6.24内核中,
法模块和实时调度模块。对应实时任务,将使用实时调度模块;对应普通任务则使用CFS算法。
CFS的算法和实现都更简单,现有的测试表明其性能也比
收稿日期:2008-09-09。杜慧江,讲师,主研领域:软件与算法。
3.CFS算法 在Linux2.6.23内核中发布了一种新的调度算法——CFS算法,CFS是“CompletelyFair 2.4与Linux2.6调度算法简介 2.4内核调度算法 Linux 2.4内核采用的...
Linux 2.4 内核的 O(n) 算法和早期 Linux 2.6 内核的 O(1)算法都是以往调度算法中的经典算法, 但是存在着一些缺点。 Linux 2.6.23 内核发布的 CFS ...
Linux 内核之 CFS 调度和组调度 作者:harvey wang 邮箱:harvey.perfect@gmail.com 新浪博客地址:http://blog.sina.com.cn/harveyperfect ,有关于减肥和学习英语...
linux 内核分析之调度算法 linux 调度算法在 2.6.32 中采用调度类实现模块式...linux 上主要有两大类调度算法,CFS(完全公平调度算法)和实时调度算法。宏 SCHED...
linux内核调度_IT/计算机_专业资料。linux内核调度内核调度 2.6.23 内核中包含了一个重要的变化,用 CFS 替代了以前的调度器。CFS 被合并到 mainline 之前,关于...
cfs调度算法_IT/计算机_专业资料。linux内核cfs调度算法分析CFS?调度器 ???wxc200 大家好哈, 兄弟最近...
42页 1财富值 Linux内核2_6_24的CFS调度... 3页 1财富值搜...本文分别介绍了嵌入式技术和Linux 技术并对嵌入式Linux 的关键技术进行了分析和...
组调度是当前操作系统内核调度算法的发展方向之一,在 linux 最新内核中, 在完全公平调度算法 CFS 的基础之上,实现了基于分组的进程调度。该文以 Kernel2.6.27 ...
? 调度实体– 内核中共有两种调度实体,分别是CFS调度实体(struct sched_entity)和实时调度实体(struct sched_rt_entity)。– 它们在include/linux/sched.h文件中...
热门文档