Linux2.6内核调度器介绍

Linux2.6的调度器新的特性改善调度器的性能有提供完全的O(1)调度算法，也就是说，不管系统中进程数量的多少，调度器中所有的算法都必须在常数时间内完成。应该对SMP有良好的可伸缩性，理想情况下，每个处理器应该有独立的可执行进程队列和锁机制。应该提高SMP的处理器亲和性，但是同时也应该有在负载不平衡的时候在处理器间迁移进程的能力。
新的调度器都实现了这些目标，具体方法是。基于每个CPU来分布时间片，并且取消了全局同步和重算循环。每个进程有两个数组，活动就绪进程队列数组和不活跃就绪进程队列数组。每个数组中有140个就绪进程队列，每个队列对应于140个优先级的某一个。由一个位图来指示哪些队列是空的，哪些不是空的，每个队列都是先进先出的(FIFO)。这样，在挑选进程的时候，只要通过find_first_bit找到第一个不为空的队列，并取队首的进程就可以了。如果一个进程消耗完了它的“时间片”，就进入不活跃就绪进程数组的相应队列的队尾。当所有的进程都“耗尽”了它的“时间片”后，交换活跃与不活跃就绪进程队列数组的指针就可以了，不需要任何其他的开销。这样，不管队列中有多少个就绪进程，挑选就绪程的速度是一定的，所以称为0(1)算法。
这个算法有很多的优点，每个处理器都有独立的就绪进程队列，各个处理器可以并行地运行Scheduler程序来挑选进程运行，不同处理器上的进程可以完全并行地休眠、唤醒和上下文切换。进程只映射到一个处理器的就绪进程队列中，不会被其他的处理器选中，因而也就不会在不同的处理器之间跳跃。当然，处理器有时确实需要在处理器之间迁移进程，例如负载不平衡的时候，每个处理器每200ms检查一次其他的处理器是不是处在负载不平衡的状况下，就绪进程队列为空的处理器会每lms检查一次。但是这种情况并不是频繁的发生，所以处理器的亲和性基本能得到保证。
新的调度算法在以下几个方面有待改进。首先，尽管处理器的速度在很快的发展，但是存储体系的速度发展却是相对比较缓慢，对存储器的操作时间往往形成瓶颈。其次，仍是进程迁移问题，因为在处理器间迁移不同进程的代价是不尽相同的，所以在迁移进程的时候，应该适当考虑进程的特点。最后，当系统检测到需要迁移进程以平衡负载的时候，当系统的负载不平衡且很轻微的时候，是不一定需要平衡负载的。

更多相关文章

随机推荐