linux的内核调度.docx

调度公平调度(fair-share scheduling)的进程调度算法：一、公平分享的调度策略?? Linux 的调度算法是相对独立的一个模块，而且较容易理解。因此很多系统高手都爱对调度算法做改进。但是可以说调度器是一个非常神秘，难以捉摸的精灵。可能通过改变一个关键参数你就可以大大提高系统的效率。?? 对于一般进程，CPU的使用时间都是系统平均分配给每一个进程的，因此这种公平分享都是从进程的角度出发的。Bach在1986 年提出了公平分享调度策略（Fair_Share scheduling）来解决这个问题。和Linux 三种内建策略比，公平分享调度策略是一种更抽象的调度策略。它认为CPU应该根据拥有进程的组（对Linux 来说是用户）来分配时间，它实现了从用户角度考虑的公平原则。? 由内核的结构来看，实现这个算法有很多种方式。我们可以在与调度相关的程序里做小小的改动来实现，如改动一些数据结构并改写schedule()函数。当然也可以做得很复杂，比如重写schedule()来实现所需要的结果。但是有一点我们是要必须牢记的，那就是大部分的Linux 核心都是以短小高效为最高目标。所以，改进的算法必须尽量向这个目标靠拢。二、新调度策略的实现：分析1、这里所说的‘组’的概念，在Linux 中是一个用户。我们所关心的是Linux 的用户，而不是UNIX 系统下的用户组或是别的什么概念。因此在公平共享调度策略中，一个进程能够分配到的时间与登录的系统用户数以及拥有该进程用户开辟进程数的多少有关。2、超级用户的进程是独立于公平分享算法的，因此它拥有的进程得到的调度时间应该和现在的进程调度算法分配时间相当。3、对于实时进程，调度算法仍旧给予比普通进程更高的优先权。不过也不用担心会花太多的时间去实现，只要在现在调度算法的基础上稍做改进就可以简单实现。4、新的调度算法对系统的吞吐量不能有太多的影响。比如说，如果定义的时间片少于2 个“滴答”，那么新实现的调度器效率将变得很差。因为过于频繁的进程切换将耗费大部分的系统时间，而真正用于程序计算的时间则排在第二位了。此条说明时间片的划分不能太小。5、我们所实现的算法并不需要绝对的公平，严格的平均是需要用效率为代价来换取的。如果算法过于精确，那就需要复杂的数据结构和耗时的计算过程，所以我们可以在以速度为第一原则的基础上实现“模糊”的公平分享。6、我们首先需要的是不断地思考和设计，只有将所有的问题都考虑清楚以后才可以开始动手。调度器是操作系统的核心，它将被频繁调用，因此其作用和影响也将是巨大的。我们要花费最小的代价实现算法，并且这种改动对系统核心的影响要降到最小。Linux的进程调度机制：概述：在多进程的操作系统中，进程调度是一个全局性的、关键性的问题。可以说，关于进程调度的研究是整个操作系统理论的核心，它对系统的总体设计、系统的实现、功能设置以及各方面的性能都有着决定性的影响。1.?? 150ms：当系统中有大量进程共存时，根据测定，当每个用户可以接受的相应速度延迟超过１５０ms时，使用者就会明显地感觉到了。2.?? 在设计一个进程调度机制时要考虑的具体问题主要有：o调度的时机：什么情况下、什么时候进行调度；o调度的政策：根据什么准则挑选下一个进入运行的进程；o调度的方式：是“可剥夺”还是“不可剥夺”。当正在运行的进程并不自愿暂时放弃对ＣＰＵ的使用权时，是否可以强制性地暂时剥夺其使用权，停止其运行而给其他进程一个机会。如果是可剥夺的，那么是否在任何条件下都可剥夺，有没有例外？3.?? linux内核的调度机制：１）调度的时机：　　*首先，自愿的调度(主动调度)随时都可以进行：在内核里面，一个进程可以通过schedule()启动一次调度。也就是由当前进程自愿调用schedule()暂时放弃运行的情景。　　*除此之外，调度还可以非自愿的，即强制地发生在每次从系统调用返回的前夕，以及每次从中断或者异常处理返回到用户空间的前夕。　　上述红字说明：只有在用户空间（当ＣＰＵ在用户空间运行时）发生的中断或者异常才会引起调度。ret_from_exception:??? movl SYMBOL_NAME(bh_mask),%eax??? andl SYMBOL_NAME(bh_active),%eax??? jnehandle_bottom_half??? ALIGNret_from_intr:??? GET_CURRENT(%ebx)??? movl EFLAGS(%esp),%eax??? ??? # mix EFLAGS and CS??? movb CS(%esp),%al??? testl $(VM_MASK | 3),%eax??? # return to VM86 mode or non-superviso