|
Linux2.6版本中的进程调度作了不小的改变。
1、引入调度域概念
每一个CPU都有一个“基本”的调度域（struct sched_domain）。函数cpu_sched_domain(i)和宏this_sched_domain()用来表示可以使用的cpu域。域的层次结构均是通过->parent指针所指向的基础域而构建的。->parent指针要保证以NULL结束，而且应当为每个CPU分配域结构以便于CPU的增加。
在每一个调度域的范围内都拥有几个CPU（存于->span中）。调度域的范围意思是：“在各CPU之间达到负载的平衡”。一个域的范围必须不小于它的子域范围，而且CPU i的基础域范围至少为i。位于域层次结构最顶层的域的范围将覆盖系统中的所有CPU。
每一个调度域都必须有一个或多个CPU组（struct sched_group），用->groups指针链接成一个环形。而这些组的cpumask在域范围内都必须是相同的。任意的两个组的cpumask交集必须为空集（即不相同）。->groups指针所指向的组必须包含这个域所拥有的CPU。而当某些组被建立后，它们可能因为包含一些只读数据而被CPU所分享。
在组之间会发生调度域的平衡操作。这个时候，每一个组将被当成一个整体。组的负载将被定义为其每一个CPU的负载总和。所以当组与组的负载不平衡时，将发生调度域的平衡操作，在组与组之间进行平衡。
在kernel/sched.c中，rebalance_tick在每一个CPU上周期性的运行。这个函数在CPU的基础调度域内检查是否重新达到了平衡。如果是， 则将在那个域内运行load_balance。而rebalance_tick将接着检查父调度域（如果有的话），进而是父调度域的父调度域，如此下去。 “基础”域的“范围”将构成域层次结构的第一级。在SMT情况下，将跨度所有的物理CPU,而每个组将有一个虚拟CPU。 Linux 2.6内核为多程序提供了一种不同的途径，即NUMA（Non Uniform Memory Access）。这种方法中，内存和处理器是相互连接的，但对于每一个处理器，某些内存是“关闭”的，而某些内存则“更远”。这意味着当内存竞争出现时，“更近”的处理器对就近的内存有更高的使用权。2.6版内核提供了一套功能来定义内存和处理器之间的拓扑关系。调度程序可以利用这些信息来为任务分配本地内存。这样将减少内存竞争造成的瓶颈，提高吞吐量。 在SMP中，基础域的父域将跨度所有节点上的物理CPU。而每个组将有一个物理CPU。通过NUMA，SMP域的父域将跨度整个机器，而每个组将有每个节点的cpumask。或者，你可以采用多级NUMA或Opteron。 2、新的调度器算法O(1) a)ultra-scalable O(1) 调度器优点：
－即使在高负载的时候也能有比较好的交互性能
－在1－2个进程调度和唤醒上有更好的性能
－公平性：没有哪个进程拥有极多的CPU占有时间
－优先级：重要任务优先级高，反之亦然
－SMP效率：如果有任务，将不会有空闲的CPU
－SMP相关：进程将尽可能的在一个CPU上运行，进程不会在不同的CPU上频繁迁移 b)新调度算法带来的改变：
－完全的O(1)调度算法：取消了重算循环（recalculation loop）和优先级循环（goodness loop）
－真正的SMP：取消了runqueue_lock，而采用每个CPU均有独立的runqueues和locks－两个独立的CPU上的任务可以同时（并行的）被唤醒、调度 和上下文切换，不再需要任何的interlock。所有要调度的相关数据均能最大范围的划分进来。
－更好的SMP相关[映射]：旧的调度器有个特别的缺点，就是当有更高优先级或实时任务时，任务会在CPU间任意的迁移。而其原因就是时间片重 算循环（timeslice recalculation loop）首先需要计算当前正在运行的每个任务的时间片开销。时间片重算算法要求在所有的进程都用尽它们的时间片后，新时间片才会被重新计算。在一个多CPU系统中，当进程用完它们的时间片后不得不等待重算，以得到新的时间片。但是当这种情况发生时，有可能会造成一部分CPU空闲出来而不运行任何任务。只有当最后一个只有一个时间片的任务用完它的那个时间片后，重算循环才被激活，而其它的CPU才可以继续执行任务－在CPU空闲运转几个时钟间隔后。因此，CPU越多，效果越恶劣。
另外，还有一种情况会引起同样的效果：当有一个全局运行队列中的某任务“时间片剩余”，空闲的CPU将开始运行该任务，但该任务初始时并不 是运行于该CPU的（因为和该CPU相关[映射]的任务的时间片已经用完了），也就是指当空闲CPU开始执行那些时间片尚未用尽的、处于等待状态的进程时，会导致进程在处理器之间“迁移”。 新的调度器以单个CPU为单元来分配时间片，从而解决了这个问题，取消了全局同步和重算循环。
－批处理调度。
－平衡负载，降低那些超出CPU负载能力的进程的优先级，从而不会崩溃，也不会产生调度风暴
－O(1) RT 调度。
－在父进程之前，运行已创建的子进程 c)新调度器的运行机制
－每个CPU均有两个具有优先级的队列。一个“活动”队列，一个“过期”队列。活动队列中包含所有映射于该CPU并具有时间片的任务。而过期队列包含所有已经使用完时间片的任务（依然是一个有序队列）。活动队列和过期队列不能直接访问，而是通过每个CPU的运行队列结构中的两个指针来访问。调度程序不需每次都扫描所有的任务，而是在一个任务变成就绪状态时将其放到“活动”的队列中。当调度程序运行时，只选择活动队列中最有利的任务来执行。这样，调度可以在一个恒定的时间里完成。当任务执行时，它会得到一个时间片，或者在其转到另一线程之前得到一段时间的CPU使用权。当时间片用完后，任务会被转移到“过期”的队列中。在该队列中，任务会根据其优先级进行排序。 当活动队列中的任务均被运行完时，我们就交换两个指针，从而使得先前的过期队列成为活动队列，同样先前空闲的活动队列将转变为过期队列。因此，可以看得出来，“活动”队列中总是排好了顺序的任务队列，如此提高了速度。 －有一个64-bit位图的缓存用来存放队列索引。因此查找最高级的任务用两个x86 BSFL bit-search 指令就可以完成。 分离队列的方法使得我们能控制活动任务和过期任务的数量，而且当时间片使用完后，可以迅速的重算时间片。因为访问队列是通过运行队列中的两个指针，交换指针基本上是非常快的，所以交换两个队列将相当的快速。
没有相关教程
| 
注：本站部分文章源于互联网，版权归原作者所有！如有侵权，请原作者与本站联系，本站将立即删除！ 本站文章除特别注明外均可转载，但需注明出处！ [MinTao学以致用网] 
