实时操作系统VxWorks的内核任务调度研究
> 实时操作系统VxWorks的内核任务调度研究
实时操作系统VxWorks的内核任务调度研究
&&&&& 1、引言
&&&本文引用地址：
&&&&&& VxWorks操作系统是WindRiver公司开发的一种高性能的嵌入式实时操作系统。它带有一个功能强大的集成开发系统环境Tornado。
&&&&&&& VxWorks具有软件生成代码小、实时性强及响应速度快等特点，特别适合于具有实时和多任务要求的系统。VxWorks自20世纪80年代问世以来，以其高性能、高可靠性、高实时性等特点成为实时操作系统中最具特色的系统。自1996年登陆中国，短短几年就已成为国防、工业自动化、网络通信、航空航天、医疗仪器、状态监控以及消费电子产品等嵌入式实时领域的首选操作系统。由于嵌入式实时操作系统在内核方面具有自身的特点，本文着重对实时内核中任务调度进行了详细分析。
&&&&&& 2、任务调度概述
&&&&& 2.1 调度的概念
&&&&&& 构成应用软件系统的程序集合中，独立的、相互作用的程序单元，在其执行时称之为任务。单个CPU 中，多任务机制制造了一个多个任务同时执行的假象。其实系统只是根据一个多任务调度算法，将内核插入到这些任务中执行。实时系统VxWorks的一个任务可有多种状态，但最基本的状态有以下四种：
&&&&& 1) 就绪态(Ready)：任务只等待系统分配CUP资源。
&&&&& 2) 挂起态(Pend)：任务需等待某些不可利用的资源而被阻塞。
&&&&& 3) 休眠态(Sleep)：如果系统不需要某一个任务工作，则这个任务处于休眠状态。
&&&&& 4) 延迟态(Delay)：任务被延迟时所处的状态。
&&&&&& 当系统函数对某一个任务进行操作时，任务从一种状态跃迁到另一种状态。处于任一状态的任务都可被删除。VxWorks的任务跃迁如图1所示。
&&&&&& &任务由系统内核调度运行一段固定长度的时间，称为时间片。调度是指为任务分配资源和时间，使系统满足特定的性能要求。调度算法的目的是在正常情况下，尽可能满足所有任务的时限：在峰值负载条件下，保证强实时任务满足时限。因为时限是区分实时系统和非实时系统的关键因素，因此调度算法是实时系统的基本问题。实时操作系统所具有的运行性能，如吞吐量的大小、周转时间的长短、相应的及时性和可预测性等在很大程度上都取决于实时调度。
&&&&& 2.2调度的类型
&&&&&& 虽然调度的主要目的都是为了分配处理机，但在不同的OS中所采用的调度方式是完全不同的。在执行调度时所采用的调度算法也可能不同。因此，常按照调度的层次把调度分成高级、中级和低级调度。
&&&&&& 高级调度又称长程调度或作业调度，用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。然而在实时系统中，为了能及时响应，用户通过键盘输入的数据都是直接送入内存，因而实时系统通常不需要作业调度。
&&&&&& 中级调度又称中程调度，引入它的主要目的是为了提高内存利用率和系统吞吐量。它使那些暂时不能运行的进程不再占用宝贵的内存空间，而将它们调到外存上去等待，此时的状态称为挂起状态。当这些进程重新具备运行条件，且内存又有空闲，由中级调度决定，将外存上的那些重新具备运行条件的就绪进程重新调入内存，并使它为就绪状态，挂在就绪队列上等待进程调度。
&&&&&& &低级调度又称进程调度。它决定就绪队列中的哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。进程调度是最基本的一种调度，各种OS中都必须配置这级调度。进程调度可采用下述两种方式。
&&&&& 1)非抢占方式。
&&&&&& 采用这种调度方式，一旦把处理机分配给某进程后，便让该进程一直执行，直到该进程完成或发生某事件而被阻塞，才再把处理机分配给其他进程，决不允许某进程抢占已经分配出去的处理机。显然它难于满足紧急任务的要求，实时系统中不宜采用这种调度方式。
&&&&& 2)抢占方式。
&&&&& 允许调度程序根据某种原则，去停止某个正在执行的进程，将已分配给该进程的处理机，重新分配给另一进程。抢占的原则有：
&&&&&& ① 时间片原则。各进程按时间片运行，当一个时间片用完后，便停止该进程的执行而重新进行调度。
&&&&&& ② 优先权原则。当一个进程到来时，如果其优先级比正在执行的进程的优先级高，便停止正在执行的进程，将处理机分配给优先级高的进程，使之执行。实时系统中一般采用基于优先级的抢占式调度和轮转调度的进程调度和中程调度相结合的调度策略。因此既可具有较大的灵活性，又能获得极小的调度延迟。
&&&& 3、任务调度分析
&&&&&& Wind内核缺省调度机制为基于优先级的抢占式调度。采用这种机制时，系统把处理机分配给优先级最高的进程，使之执行。一旦出现了另一个优先级更高的进程时，进程调度程序剥夺当前任务的执行，将处理机分配给高优先级任务。而在相同优先级的多个任务之间，采用时间片轮转调度机制。采用这种机制时，当一个任务到达时，它被排在轮转队列的后面，等待分配给自己的时间片的到来，如果在时间片内没有结束，则再等待属于自己的时间片的到来，直到任务完成。
&&&&& 3.1 优先级抢占式
&&&&&& 采用基于优先级的抢占式调度，系统中每个任务都有一个介于最高0到最低255之间的优先级。任一时刻，系统内核一旦发现一个优先级更高的任务转变为就绪态，内核就保存当前任务的上下文并把当前任务状态转换为阻塞态，同时切换到这个高优先级任务的上下文执行。如图2，低优先级的task1被中优先级的task2抢占，task2又被高优先级的task3抢占。
&&&&& 3.2 轮转调度算法
&&&&&&& 采用轮转调度算法，系统让处于就绪态的优先级相同的一组任务依次轮流执行预先确定长度的时间片。这是一种处理机平均分配的方法。如果不使用轮转调度算法，优先级相同的一组任务中第一个获得处理机的任务将不会被阻塞而独占处理机，如果没有阻塞或其他情况发生，它不会放弃处理机的使用权。如图3，相同优先级的task1、task2和task3平均分配预先确定的处理机时间片。
&&&&& 3.3 抢占调度与轮转调度混合方式
&&&&&& 有时，基于优先级的抢占式调度可与轮转调度相结合。当优先级相同的一组任务依次轮流平均分配处理机时，若有高优先级的任务转变为就绪态则可抢占该组任务。直到再一次符合执行条件时，该组任务才可再次共享处理机。如图4，相同优先级的task1、task2和task3轮流占有处理机时，高于该组优先级的task4抢占处理机，等task4执行结束，该组任务再次共享处理机。
&&&&&& 为了任务控制的灵活性，wind内核还提供了动态优先级机制，任务的优先级在运行期间可动态地变化。同时，为了防止优先级反转，还具有优先级继承机制，通过使用互斥信号量可以防止高优先级的任务被迫等待一段不确定时间，直到一个低优先级任务完成。
&&&& 4、结论
&&&&& 任务是代码运行的一个映像，从系统的角度来看，任务是竞争系统资源的最小运行单元。vxworks内核使任务能快速共享系统的绝大部分资源，同时有独立的上下文来控制个别线程的执行。内核调度是一个实时系统的核心，它的好坏直接影响整个系统的好坏，通过对这种内核调度分析，可以更深入的理解实时操作系统设计的独到之处。
分享给小伙伴们：
我来说两句……
最新技术贴
微信公众号二
微信公众号一2010年8月 硬件使用大版内专家分月排行榜第二
2010年7月 Windows专区大版内专家分月排行榜第三2009年1月 Windows专区大版内专家分月排行榜第三2008年12月 Windows专区大版内专家分月排行榜第三2006年8月 扩充话题大版内专家分月排行榜第三
2016年3月 其他开发语言大版内专家分月排行榜第二2014年10月 其他开发语言大版内专家分月排行榜第二2013年7月 Windows专区大版内专家分月排行榜第二2013年5月 其他开发语言大版内专家分月排行榜第二2013年4月 其他开发语言大版内专家分月排行榜第二2012年11月 其他开发语言大版内专家分月排行榜第二2012年6月 其他开发语言大版内专家分月排行榜第二2011年11月 其他开发语言大版内专家分月排行榜第二2011年9月 其他开发语言大版内专家分月排行榜第二2010年6月 其他开发语言大版内专家分月排行榜第二2007年4月 其他开发语言大版内专家分月排行榜第二2006年12月 其他开发语言大版内专家分月排行榜第二2006年11月 其他开发语言大版内专家分月排行榜第二2005年6月 其他开发语言大版内专家分月排行榜第二2003年5月 其他开发语言大版内专家分月排行榜第二2003年3月 其他开发语言大版内专家分月排行榜第二
2013年11月 其他开发语言大版内专家分月排行榜第三2013年8月 其他开发语言大版内专家分月排行榜第三2012年12月 其他开发语言大版内专家分月排行榜第三2012年9月 其他开发语言大版内专家分月排行榜第三2012年8月 其他开发语言大版内专家分月排行榜第三2012年5月 其他开发语言大版内专家分月排行榜第三2011年12月 其他开发语言大版内专家分月排行榜第三2010年12月 其他开发语言大版内专家分月排行榜第三2010年9月 其他开发语言大版内专家分月排行榜第三
2016年3月 其他开发语言大版内专家分月排行榜第二2014年10月 其他开发语言大版内专家分月排行榜第二2013年7月 Windows专区大版内专家分月排行榜第二2013年5月 其他开发语言大版内专家分月排行榜第二2013年4月 其他开发语言大版内专家分月排行榜第二2012年11月 其他开发语言大版内专家分月排行榜第二2012年6月 其他开发语言大版内专家分月排行榜第二2011年11月 其他开发语言大版内专家分月排行榜第二2011年9月 其他开发语言大版内专家分月排行榜第二2010年6月 其他开发语言大版内专家分月排行榜第二2007年4月 其他开发语言大版内专家分月排行榜第二2006年12月 其他开发语言大版内专家分月排行榜第二2006年11月 其他开发语言大版内专家分月排行榜第二2005年6月 其他开发语言大版内专家分月排行榜第二2003年5月 其他开发语言大版内专家分月排行榜第二2003年3月 其他开发语言大版内专家分月排行榜第二
2013年11月 其他开发语言大版内专家分月排行榜第三2013年8月 其他开发语言大版内专家分月排行榜第三2012年12月 其他开发语言大版内专家分月排行榜第三2012年9月 其他开发语言大版内专家分月排行榜第三2012年8月 其他开发语言大版内专家分月排行榜第三2012年5月 其他开发语言大版内专家分月排行榜第三2011年12月 其他开发语言大版内专家分月排行榜第三2010年12月 其他开发语言大版内专家分月排行榜第三2010年9月 其他开发语言大版内专家分月排行榜第三
2016年10月优秀大版主2016年8月优秀大版主
2016年9月 总版技术专家分月排行榜第二
2013年 总版技术专家分年内排行榜第三
2012年 总版技术专家分年内排行榜第七
本帖子已过去太久远了，不再提供回复功能。23:02 提问
基于优先级的时间片轮转调度算法
求一个基于优先级的时间片轮转调度算法。实在是不太会做了，没思路。要求java
（1）设系统中有n个进程，每个进程PCB格式如下：
进程名称：p1,..., pn；
进程状态：1-运行，2-就绪，3-等待，0-完成；
进程类型：0-系统进程，1-用户进程；
请求资源时刻；
需要的CPU时间；
已运行时间；
优先级：数字小的优先级高；
指向下一进程的指针。
（2）在调度程序运行之前，输入进程名称、所需CPU时间等。
（3）设计4个队列，完成队列，运行队列，就绪队列和等待队列。
（4）调度程序选择就绪队列首进程运行，采用时间片轮转法，输出调度过程。
按赞数排序
java的你自己改改
其他相关推荐君，已阅读到文档的结尾了呢~~
操作系统课程设计报告-基于时间片的高优先级调度模拟实现,优先级调度算法,描述优先级调度算法,优先级调度,进程调度 优先级,pintos 优先级调度,动态优先级调度算法,动态优先级调度,操作系统进程调度,操作系统调度,操作系统调度算法
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
操作系统课程设计报告-基于时间片的高优先级调度模拟实现
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口博客访问： 50191
博文数量： 6
博客积分： 0
博客等级： 民兵
技术积分： 463
注册时间：
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
分类： LINUX
操作系统的调度程序的两项任务：
1： 调度：
实现调度策略，决定就绪的进程、线程竞争cpu的次序的裁决原则。说白了就是进程和线程何时应该放弃cpu和选择那个就绪进程、线程来执行。
2： 分派：
原来实现调度机制如何时分复用cpu，处理好上下文交换的细节、完成进程、线程和cpu的绑定和放弃的具工作。
& linux 2.4 调度：
1：policy ：
进程的调度策略：
1）SCHED_FIFO : 实时进程使用的的先进先出策略，进程会一直占用cpu除非其自动放弃cpu。
2）SCHED_RR : 实时进程的轮转策略，当分配个u进程的时间片用完后，进程会插入到原来优先级的队列中。
3）SHED_OTHER：普通进程基于优先级的的时间片轮转调度。
2：priority：进程的静态优先级。
3：nice：进程用来控制优先级的因子。在-20～19间的整数。增加nice的值会使优先级降低。默认值为0。
4：rt_priority：实时进程的优先级。
5：counter：一个计时器，进程目前的剩余时间片。用来动态计算进程的动态优先级。系统将休眠次数多的进程的剩余时间叠会加起来。
6：schedule()的流程：
1）检查是否有软中断请求。有则先执行。
2）如果当前进程的调度策略为RR并且counter==0,将此进程移到运行进程队列的尾部。重新计算counter的值。
3）若当前进程的状态为 TASK_INTERRUPTIBLE 且有信号接收，则将进程状态设置为TASK_RUNNING，若当前进程的状态不是TASK_RUNNING,则将进程从可执行的队列中移出，将其进程描述符的need_resched置为0。
4) 选择出可运行队列中最大权值，保存在变量c中，与之对应的进程描述符保存在变量next中。
5）检查c是否为0,c==0,则队列中的所有进程的时间片都用完了。此时对队列中所有进程的时间片重新计算。重新执行第5步。
6）如果netx==当前进程，则结束调度进程。否则，进行进程切换。
过程：2.4的调度算法，将所有的就绪进程组织成一条可运行队列，不管是单核环境还是smp环境，cpu都只从这条可运行队列中循环遍历直到挑选到下一个要运行的进程。如果所有的进程的时间片都用完，就重新计算所有进程的时间片。
2.4调度的数据结构：
2.4调度的不足：
1）一个明显的缺点就是时间复杂度为O(n)，每次都要遍历队列，效率低！。虽然说O(n)的复杂度看起来不是很糟糕，而且系统能容纳进程数量也不一定会很大，但复杂度为O(n)还是很难忍受的。
2）由于在smp环境下多个cpu还是使用同一条运行队列，所以进程在多个cpu间切换会使cpu的缓存效率降低，降低系统的性能。
3）多个cpu共享一条运行队列，使得每个cpu在对队列操作的时候需要对运行队列进行加锁，这时如果其他空闲cpu要访问运行队列，则只能等待了。由2、3两点可以看出2.4的调度算法对smp环境的伸缩性不高！不能很好地支持smp环境。
4）不支持内核抢占，内核不能及时响应实时任务，无法满足实时系统的要求（即使linux不是一个硬实时，但同样无法满足软实时性的要求）。
5）进程的剩余时间是除了nice值外对动态优先级影响最大的因素，并且系统将休眠次数多的进程的剩余时间叠加起来，从而得出更大的动态优先级。这体现了系统更倾向优先执行I/O型进程。内核就是通过这种方式来提高交互进程的优先级，使其优先执行。但休眠多的进程就代表是交互型的进程吗？并不是的，这只能说明它是I/O型进程。I/O型进程需要进行I/O交互，如读写磁盘时进程会经常处于休眠的状态。如果把这种进程当成是交互进程，反而会影响其他真正的交互进程。
6）简单的负载平衡。那个cpu空闲就把就绪的进程调度到这个cpu上去执行。或者某个cpu的进程的优先级比某个进程低，就调度到那个cpu上去执行。这样简单的负载平衡缺点不言而喻。进程迁移比较频繁，而且出现2、3的情况。这样的负载平衡弊大于利！
&&&&linux 2.6
O(1)调度：
1：policy：调度策略跟2.4的一样。
2：rt_priority：实时进程的优先级。在0～99之间。MAX_RT_PRIO为100。不参与优先级的计算。
3：static_prio：非实时进程的静态优先级，由nice值转换而来，-20 &= nice &= 19。static_prio = MAX_RT_PRIO + nice + 20。所以 100 &= static_prio &= 139。
4：sleep_avg：进程平均等待时间。进程等待时间与执行时间的差。反映进程的交互性，又表示了进程需要运行的紧急程度。这个值越大，进程的优先级就越高。
5：prio：进程的动态优先级。主要影响进程的prio的因素是sleep_avg。其计算时机为：
1）进程在创建时继承父进程的prio。
2）进程由睡眠到被唤醒时进行优先级修正。
3）时钟中断中重新计算进程的优先级并且进程进入相应的队列。
4）负载平衡/修改nice/修改调度策略等都有可能修改prio的值。
6：time_slice：进程的时间片余额。进程的默认时间片与static_prio有关。
7：load_weight：平衡负载用的权重。
&& linux 2.6
O(1)调度的数据结构代码：
1：运行队列：部分代码如图：
2：优先级数组代码如图：
1）nr_active：数组内可运行的进程
2）DECLARE_BITMP(...)：优先级位图的宏。找出优先级最高的且有就绪进程的队列。
3）list_head queue：使用通用链表，优先级队列。
& linux 2.6
O(1)调度的数据结构（active or expired）：
每个cpu维护一个自己的运行队列，每个运行队列有分别维护自己的active队列与expried队列。当进程的时间片用完后就会被放入expired队列中。当active队列中所有进程的时间片都用完，进程执行完毕后，交换active队列和expried。这样expried队列就成为了active队列。这样做只需要指针的交换而已。当调度程序要找出下一个要运行的进程时，只需要根据上面提过的位图宏来找出优先级最高的且有就绪进程的队列。这样的数据组织下，2.6的调度程序的时间复杂度由原来2.4的O(n)提高到O(1)。而其对smp环境具有较好的伸缩性。
数据结构的组织如下：
& linux 2.6 O(1) 调度的进程优先级：
2.6调度有140个优先级级别，由0～139, 0～99 为实时优先级，而100～139为非实时优先级。上面的图有说。
1）动态优先级是在静态优先级的基础上结合进程的运行状态和进程的交互性来计算。所以真正参与调度的是进程的动态优先级。而进程的交互性是通过进程的睡眠时间来判断的（这点从根本上来说还是和2.4思想的一样）。所以动态优先级是通过静态优先级和进程睡眠时间来计算的。这里要注意的是，动态优先级是非实时进程插入优先级队列的依据。但实时进程是根据rt_prioirty来插入队列的，实时进程的实时优先级由进程被创建到进程结束都是不会改变的。但其执行的时间片是根据静态优先级来计算的。
2）进程优先级越高，它每次执行的时间片就越长。
3）使用TASK_INTERACTIVE()宏来判断进程是否为交互进程，该宏是基于nice来判断的，nice值越高，优先级越低，这样交互性越低。
4）如果一个进程的交互性比较强，那么其执行完自身的时间片后不会移到expired队列中，而是插到原来队列的尾部。这样交互性进程可以快速地响应用户，交互性会提高。如果被移到expired队列，那么在交换队列指针前，交互性进程可能就会发生严重的饥饿，从而使交互性严重下降
5）在创建新的进程时，子进程会与父进程平分进程的剩余时间片。即在 fork()------&do_fork() 后父子进程的时间片之和等于原来父进程的时间片大小。这样做的原因是为了防止父进程利用创建子进程来窃取时间片。如果子进程在退出时，从来没有被重新分配时间片，且还有时间片剩余，则其剩余的时间片会返还给父进程。这样父进程就不会因为创建子进程而受到时间片上的惩罚。
& 2.6 O(1)调度动态优先级的计算代码：
1）effective_prio(p)：
2）normal_prio：
3）__normal_prio：
& linux 2.6 O(1)调度的调度与抢占时机：
1：直接调度：当前进程因为阻塞而直接调用schedule()主动放弃cpu。
1）当前进程被放入相应的等待队列。
2）改变当前进程的进程状态。由TASK_RUNNING 改为TASK_UNINTERRUPTIBLE 或者 TASK_INTERRUPTIBLE。
3）选择新的进程运行。调用schedule() 来获得下一个需要运行的进程。
4）当资源可用时，把当前进程从等待队列中移除。
2：被动调度：当前进程因为时间片用完，或者被更高优先级的进程抢占，而被逼放弃cpu。这时当前进程不会立刻被调度出去，而是通过设置TIF_NEED_RESCHED位为1来告知kernel需要调度了。在适当的时机kernel会重新调度。
1）问题：为什么不能立刻调度？
进程在内核里运行时，可能要申请共享资源，如自旋锁，如果这个时候去抢占当前进程，使其立刻让出cpu，如果新进程也需要相同的共享资源的话，那么会导致死锁！所以这里进程只设置了标志位通知内核需要调度。
2）问题：什么时候才是合适的时机？
内核在即将返回用户空间时会检查TIF_NEED_RESCHED，如果设置了就调用schedule()，这样就会发生用户抢占。
a：从中断处理程序返回用户空间时。
b：从系统调用返回用户空间时。
& linux 2.6 O(1)调度的负载平衡：
& linux 2.6 O(1)调度的过渡：
1：SD调度器：
O(1)调度的复杂性主要来至于动态优先级的计算。调度器根据一些难以理解的经验公式和平均休眠时间来决定、修改进程的优先级。这是O(1)调度一个比较大的缺点（甚至可以说是致命的。）。SD调度的特点：
1）数据结构跟O(1)调度差不多，不过少了expired队列。
2）进程在用完其时间片后不会放到expired队列，而是放到下一个优先级队列中（这就是为什么没有expired队列的原因）。当下降到最低一级时，时间片用完，就回到初始优先级队列去，重新降级的过程！每一次降级就像我们下楼梯的过程，所以这被称为楼梯算法。
3）两种时间片：粗粒度、细粒度。粗粒度由多个细粒度组成，当一个粗粒度时间片被用完，进程就开始降级，一个细粒度用完就进行轮回。这样cpu消耗型的进程在每个优先级上停留的时间都是一样的。而I/O消耗型的进程会在优先级最高的队列上停留比较长的时间，而且不一定会滑落到很低的优先级队列上去。
4）不会饥饿，代码比O(1)调度简单，最重要的意义在于证明了完全公平的思想的可行性。
5）相对与O(1)调度的算法框架还是没有多大的变化，每一次调整优先级的过程都是一次进程的切换过程，细粒度的时间片通常比O(1)调度的时间片短很多。这样不可避免地带来了较大的额外开销，使吞吐量下降的问题。这是SD算法不被采用的主要原因！
2：RSDL调度器：
对SD算法的改进，其核心思想是“完全公平”，并且没有复杂的动态优先级的调整策略。引进“组时间配额” → tg 每个优先级队列上所有进程可以使用的总时间 ，”优先级时间配额“ → tp, tp不等于进程的时间片，而是小于进程时间片。当进程的tp用完后就降级。与SD算法相类似。当每个队列的tg用完后不管队列中是否有tp没有用完，该队列的所有进程都会被强制降级。
& linux 2.6 O(1)调度的不足：
1：复杂的难以理解的经验公式。
2：公平吗？
3：实时性？
& linux 杰出的调度算法 → cfs：
按照cfs的作者的说法：”cfs的 80% 的工作可以用一句话来概括：cfs在真实的硬件上模拟了完全理想的多任务处理器。“ 在完全理想的多任务处理器下，每个进程都能够同时获得cpu的执行时间，当系统中有两个进程时，cpu时间被分成两份，每个进程占50%。
1：虚拟运行时间。进程的 vt 与其实际的运行时间成正比，与其权重成反比。权重是由进程优先级来决定的，而优先级又参照nice值的大小。进程优先级权重越高，在实际运行时间相同时，进程的vt就越小。所有的非实时的可运行的进程用红黑树来组织起来，调度时选择的vt最小的那个进程。因为这里的红黑树左子树的键值比右边的小，所以每次调度时都选择树的最左下角的那个进程（实体）就可以了。
2：完全公平的思想。cfs不再跟踪进程的休眠时间、也不再区分交互式进程，其将所有的进程统一对待，在既定的时间内每个进程都获得了公平的cpu占用时间，这就是cfs里的公平所在！
3：cfs 引入了模块化、完全公平调度、组调度等一系列特性。虽说是完全公平调度，但进程之间本来就不公平的（有些内核线程用于处理紧急情况），所以这种完全公平是不能够实现的。cfs使用weight 权重来区分进程间不平等的地位，这也是cfs实现公平的依据。权重由优先级来决定，优先级越高，权重越大。但优先级与权重之间的关系并不是简单的线性关系。内核使用一些经验数值来进行转化。
如果有a、b、c 三个进程，权重分别是1、2、3,那么所有的进程的权重和为6, 按照cfs的公平原则来分配，那么a的重要性为1/6, b、c 为2/6, 3/6。这样如果a、b、c 运行一次的总时间为6个时间单位，a占1个，b占2个，c占3个。
& cfs调度器：
各个部分的数据结构关系图如下：
虚拟运行时间
&&&&在完全理想的多任务处理器下，每个进程都能同时获得cpu的时间。但实际上当一个进程占用cpu时，其他的进程必须等待，这样就产生了不公平。所以linux 的cfs调度引入了虚拟运行时间。虚拟运行时间主要由两个因素决定，一个是实际的运行时间，一个是其权重，它随自己的实际运行时间增加而增加，但又不等于实际运行时间。上面提过内核采用红黑树来对虚拟运行时间来排序，这样红黑树最左边的进程（调度实体）就是受到了最不公平待遇的进程，需要作为下一个被调度的进程。
进程的虚拟运行时间由calc_delta_fair()来计算。在每次时钟中断后都会进行更新。公式为：
&&&&if (se.load.weight != NICE_0_LOAD)
&&&&&&&&vruntime += delta * NICE_0_LOAD / se.load.
&&&&&&&&vruntime +=
delta是进程增加的实际的运行时间。 NICE_0_LOAD为nice 0进程的权重。虚拟运行时间与权重成反比，进程的权重越大虚拟运行时间就增加得越慢，位置就越左，越有可能被调度。
对cfs的理解最好就是看源代码了，下面贴出代码（网上有人整理得很好了）：
&&&&各个函数的调用关系图：
在tick中断处理函数中,会调用scheduler_tick()函数.该函数代码如下:
在tick中断处理函数中，会调用scheduler_tick()函数。该函数代码如下:
void scheduler_tick(void)
&&/*取得当前CPU*/
int cpu = smp_processor_id();
/*取得当前CPU对应的runqueue*/
&&&&struct rq *rq = cpu_rq(cpu);
/*当前运行的进程*/
&&&&struct task_struct *curr = rq-&curr;
&&&&sched_clock_tick();
&&&&spin_lock(&rq-&lock);
&&&&/*更新rq的当前时间戳.即使rq-&clock变为当前时间戳*/
&&&&update_rq_clock(rq);scheduler_tick()
&&&&/*更新rq的负载*/
&&&&update_cpu_load(rq);
&&&&/*调用调度模块的task_tick函数*/
&&&&curr-&sched_class-&task_tick(rq, curr, 0);
&&&&spin_unlock(&rq-&lock);
#ifdef CONFIG_SMP
&&&&rq-&idle_at_tick = idle_cpu(cpu);
&&&&trigger_load_balance(rq, cpu);
我们从上面的代码中可以看到,经过一部份共同处理之后,流程会转入调度模块的task_tick()函数.
对应CFS,它的sched_class结构如下:
static const struct sched_class fair_sched_class = {
&&&&.next = &idle_sched_class,
&&&&.enqueue_task = enqueue_task_fair,
&&&&.dequeue_task = dequeue_task_fair,
&&&&.yield_task = yield_task_fair,
&&&&.check_preempt_curr = check_preempt_wakeup,
&&&&.pick_next_task = pick_next_task_fair,
&&&&.put_prev_task = put_prev_task_fair,
#ifdef CONFIG_SMP
&&&&.select_task_rq = select_task_rq_fair,
&&&&.load_balance = load_balance_fair,
&&&&.move_one_task = move_one_task_fair,
&&&&.set_curr_task = set_curr_task_fair,
&&&&.task_tick = task_tick_fair,
&&&&.task_new = task_new_fair,
&&&&.prio_changed = prio_changed_fair,
&&&&.switched_to = switched_to_fair,
#ifdef CONFIG_FAIR_GROUP_SCHED
&&&&.moved_group = moved_group_fair,
即对应task_tick的处理函数为task_tick_fair().代码如下:
schedule()的执行过程
当进程需要被抢占或者是进程主运让出处理器,则会调用schedule()函数.为了减小篇幅,在这里就不分析schedule()函数代码.只列出在该函数中调用模块的主要函数.如下示:
Schedule()----&
sched_class-&put_prev_task(rq,prev)----&
sched_class-&pick_next_task()
对应到CFS中,put_prev_task()函数为put_prev_task_fair(),该操作就是将进程放回队列.
新进程的调度过程
在创建新进程的时候,在do_fork()中有如下过程:
long do_fork(unsigned long clone_flags,
&&&&&&&&&&unsigned long stack_start,
&&&&&&&&&&struct pt_regs *regs,
&&&&&&&&&&unsigned long stack_size,
&&&&&&&&&&int __user *parent_tidptr,
&&&&&&&&&&int __user *child_tidptr)
if (unlikely(clone_flags & CLONE_STOPPED)) {
&&&&&&&&&&&&/*
&&&&&&&&&&&&&* We'll start up with an immediate SIGSTOP.
&&&&&&&&&&&&&*/
&&&&&&&&&&&&sigaddset(&p-&pending.signal, SIGSTOP);
&&&&&&&&&&&&set_tsk_thread_flag(p, TIF_SIGPENDING);
&&&&&&&&&&&&__set_task_state(p, TASK_STOPPED);
&&&&&&&&} else {
&&&&&&&&&&&&wake_up_new_task(p, clone_flags);
即在末带CLONE_STOPPED标志创建进程时,就会对新进程调用wake_up_new_task().
&&& 加上附件，可以下载代码，其中有注释（摘自网上一篇很好的文章）。
阅读(13512) | 评论(6) | 转发(8) |
相关热门文章
给主人留下些什么吧！~~
专家点评：一篇不错的对于Linux调度原理的分析总结文章，思路清晰，配有许多图表，并将2.4和2.6的调度策略做了对比，是不错的参考资料。建议最好对代码稍做解析，并注意排版，代码都使用代码框，不用图片显示代码。（感谢您参与“原创博文评选”获奖结果即将公布）
：博主相当用心！向博主学习
这个世界需要交流。。感谢你的阅读！ |
：http://blog.csdn.net/kevin_hcy/article/details/6064525&好像一共有三篇的。。都可以找到，我把原博主的思路做成了yed文件，你需要可以找我拿。他的代码分析得不错！
博主相当用心！向博主学习 |
：http://blog.csdn.net/kevin_hcy/article/details/6064525&好像一共有三篇的。。都可以找到，我把原博主的思路做成了yed文件，你需要可以找我拿。他的代码分析得不错！
：博主，您好！可否提供您文章中提到的博文的链接
http://blog.csdn.net/kevin_hcy/article/details/6064525&好像一共有三篇的。。都可以找到，我把原博主的思路做成了yed文件，你需要可以找我拿。他的代码分析得不错！ |
请登录后评论。