下载文档原格式
Minix3和linux3调度机制比较摘要minix3和linux是两个非常不同的系统，本文将对两个系统的调度机制进行比较。
minix3采用的是多级的进程队列进行调度。
为了防止系统出现挂起的情况，采用动态优先级的方法。
随后，文章将介绍minix3的调度算法中的一些具体实现；由于linux2.6中实现了多种的调度算法，本文选择了最常用的CFS（完全公平算法）来做介绍。
最后，文章对两类算法的应用做了对比和总结。
关键字：minix3,linux，进程调度，CFS1.Minix3的调度算法1.1基本思想一个多级的排队系统。
有16个排队队列，但实际上可以编译定义更多或更少的队列。
系统刚运行的时候一般不会使用这么多的队列，而仅使用其中几个。
进程的优先级基本上由其所在队列的优先级所决定。
选择进程运行的时候，调度器将从最高优先级队列中的进程开始选，如果有，则选取队首进程运行；若没有，则到下一个次优先级的队列中去选进程去执行。
1.2 CPU时间分配和防止系统挂起（hang）进程调度中既要给与高优先级进程更多的机会去运行，但同时也要防止系统老是被一个高优先级的进程所占用，出现低优先级进程的“进程饥饿”，最后甚至造成系统挂起的问题。
Minix3采用以下的方法。
首先，队列内采取时间片轮转的方法。
每个进程都有一个时间片，每次时间片用完，调度器都要进行进程调度。
优先级高的进程一般有较大的时间片。
对于某个优先级队列中的进程而言，一个进程运行完它的时间片后就会被放到原先优先级队列的尾部并分配一个新的时间片，使得队列中的进程能轮转地公平的得到运行的机会。
其次，对于队列间，采取如下动态优先级的策略。
但如果队列中只有一个进程，那这个进程在时间片运行完后，仍会立即继续下一个时间片地运行。
为了防止这种情况，但一个进程连续两个时间片地运行完后，将被放在一个较低的运行队列中。
而当进程没有妨碍其他进程的运行（即其时间片用完后，调度器调度了其他的进程运行）时，它的优先级又会不断提高直到到它能回到的（所允许的）最大优先级。
文章编号：1006-1576（2005）02-0089-02Linux 2.6内核分析栾建海，李众立，黄晓芳（西南科技大学计算机学院，四川绵阳 621002）摘要：Linux操作系统内核由进程和内存管理、文件系统、网络接口、进程间通信模块构成。
内核程序使用进程标识号（PID）标识过程。
内存管理程序采用页式管理机制，通过页面、中间目录及页面表三个层次实现从线形地址到物理地址的映射。
其网络接口模块分为：网络设备接口、网络接口核心、网络协议族及网络接口socket层。
关键词：Linux；操作系统；内核分析；网络接口中图分类号：TP316.89 文献标识码：AAnalyze on Linux 2.6 KernelLUAN Jian-hai, LI Zhong-li, HUANG Xiao-fang(College of Computer, Southwest University of Science & Technology, Mianyang 621002, China) Abstract: The kernel of Linux operating system is composed of course, memory management, file system, process communication model etc. The process is marked with PID numbers in kernel program. The page management system was applied in memory management program, and the mapping from line address to physics address was realized through three layers of page layout, middle list and page layout table. Interface modules of network are divided into interface of network device, the kernel of network interface, and the family of network protocol and socket layer of network interface. Finally, Linux 2.6 kernel was analyzed.Keywords: Linux; Operating system; Kernel analyze; Network interface1 引言Linux是运行于多种平台、源代码公开、免费、遵守POSIX标准、与UNIX兼容的操作系统。
linux内核分析之调度算法linux调度算法在2.6.32中采用调度类实现模块式的调度方式。
这样，能够很好的加入新的调度算法。
linux调度器是以模块方式提供的，这样做的目的是允许不同类型的进程可以有针对性地选择调度算法。
这种模块化结构被称为调度器类，他允许多种不同哦可动态添加的调度算法并存，调度属于自己范畴的进程。
每个调度器都有一个优先级，调度代码会按照优先级遍历调度类，拥有一个可执行进程的最高优先级的调度器类胜出，去选择下面要执行的那个程序。
linux上主要有两大类调度算法，CFS(完全公平调度算法）和实时调度算法。
宏SCHED_NOMAL主要用于CFS调度，而SCHED_FIFO和SCHED_RR主要用于实时调度。
如下面的宏定义：1. /*2. * Scheduling policies3. */4. /*支援Real-Time Task的排程,包括有SCHED_FIFO與SCHED_RR.5. */6.7. /*(也稱為SCHED_OTHER): 主要用以排程8. 一般目的的Task.*/9. #define SCHED_NORMAL 010. #define SCHED_FIFO 111. /*task預設的 Time Slice長度為100 msecs*/12. #define SCHED_RR 213. /*主要用以讓Task可以延長執行的時間14. (Time Slice),減少被中斷發生Task Context-Switch15. 的次數.藉此可以提高 Cache的利用率16. (每次Context-Switch都會導致Cache-Flush). 比17. 較適合用在固定週期執行的Batch Jobs任18. 務主機上,而不適合用在需要使用者互19. 動的產品 (會由於Task切換的延遲,而20. 感覺到系統效能不佳或是反應太慢).*/21. #define SCHED_BATCH 322. /* SCHED_ISO: reserved but not implemented yet */23. /*為系統中的Idle Task排程.*/24. #define SCHED_IDLE 51. /*每个处理器都会配置一个rq*/2. s truct rq {3. /* runqueue lock: */4. spinlock_t lock;5.6. /*7. * nr_running and cpu_load should be in the same cacheline because8. * remote CPUs use both these fields when doing load calculation.9. */10. /*用以记录目前处理器rq中执行task的数量*/11. unsigned long nr_running;12. #define CPU_LOAD_IDX_MAX 513. /*用以表示处理器的负载，在每个处理器的rq中14. 都会有对应到该处理器的cpu_load参数配置，在每次15. 处理器触发scheduler tick时，都会呼叫函数16. update_cpu_load_active,进行cpu_load的更新。
本文从Linux 2.4 调度系统的缺陷入手，详细分析了Linux 2.6 调度系统的原理和实现细节，并对与调度系统相关的负载平衡、NUMA 结构以及实时性能进行了分析和评价。
文末，作者从调度系统的发展和实现出发，对Linux 的发展特点和方向提出了自己的看法。
1．前言Linux 的市场非常广阔，从桌面工作站到低端服务器，它都是任何商用操作系统的有力竞争对手。
目前，Linux 正全力进军嵌入式系统和高端服务器系统领域，但它的技术缺陷限制了它的竞争力：缺乏对实时任务的支持，多处理机可扩展性差。
在2.4 内核中，造成这两个弱项的关键原因之一就是调度器设计上的缺陷。
2.6 调度系统从设计之初就把开发重点放在更好满足实时性和多处理机并行性上，并且基本实现了它的设计目标。
主要设计者，传奇式人物Ingo Molnar 将新调度系统的特性概括为如下几点：∙继承和发扬2.4 版调度器的特点：o交互式作业优先o轻载条件下调度/唤醒的高性能o公平共享o基于优先级调度o高CPU 使用率o SMP 高效亲和o实时调度和cpu 绑定等调度手段∙在此基础之上的新特性：o O(1)调度算法，调度器开销恒定（与当前系统负载无关），实时性能更好o高可扩展性，锁粒度大幅度减小o新设计的SMP 亲和方法o优化计算密集型的批处理作业的调度o重载条件下调度器工作更平滑o子进程先于父进程运行等其他改进在2.5.x 的试验版本中，新的调度器的开发一直受到广泛关注，实测证明它的确使系统性能得到很大改善。
本文就从新设计的数据结构开始，围绕 2.6 对于2.4 所作的改进，对2.6 调度系统的原理和实现细节进行分析。
2.6 调度器设计相当复杂，文中还存在很多需要继续研究的地方，特别是各个调度参数的设定，随着核心版本的升级，可能还会继续修正。
2．新的数据结构runqueue我们知道，在 2.4 内核中，就绪进程队列是一个全局数据结构，调度器对它的所有操作都会因全局自旋锁而导致系统各个处理机之间的等待，使得就绪队列成为一个明显的瓶颈。
2.4 的就绪队列是一个简单的以runqueue_head 为头的双向链表，在2.6 中，就绪队列定义为一个复杂得多的数据结构struct runqueue，并且，尤为关键的是，每一个CPU 都将维护一个自己的就绪队列，--这将大大减小竞争。
O(1)算法中很多关键技术都与runqueue 有关，所以，我们对调度器的分析就先从runqueue 结构开始。
1) prio_array_t *active, *expired, arrays[2]runqueue 中最关键的数据结构。
每个CPU 的就绪队列按时间片是否用完分为两部分，分别通过active 指针和expired 指针访问，active 指向时间片没用完、当前可被调度的就绪进程，expired 指向时间片已用完的就绪进程。
每一类就绪进程都用一个struct prio_array 的结构表示：图1：active、expired 数组示例图中的task 并不是task_struct 结构指针，而是task_struct::run_list，这是一个小技巧，详见下文run_list 的解释。
在2.4 版的内核里，查找最佳候选就绪进程的过程是在调度器schedule() 中进行的，每一次调度都要进行一次（在for 循环中调用goodness()），这种查找过程与当前就绪进程的个数相关，因此，查找所耗费的时间是O(n) 级的，n 是当前就绪进程个数。
正因为如此，调度动作的执行时间就和当前系统负载相关，无法给定一个上限，这与实时性的要求相违背。
在新的O(1) 调度中，这一查找过程分解为n 步，每一步所耗费的时间都是O(1) 量级的。
prio_array 中包含一个就绪队列数组，数组的索引是进程的优先级（共140 级，详见下"static_prio" 属性的说明），相同优先级的进程放置在相应数组元素的链表queue 中。
调度时直接给出就绪队列active 中具有最高优先级的链表中的第一项作为候选进程（参见"调度器"），而优先级的计算过程则分布到各个进程的执行过程中进行（见"优化了的优先级计算方法"）。
为了加速寻找存在就绪进程的链表，2.6 核心又建立了一个位映射数组来对应每一个优先级链表，如果该优先级链表非空，则对应位为1，否则为0。
核心还要求每个体系结构都构造一个sched_find_first_bit() 函数来执行这一搜索操作，快速定位第一个非空的就绪进程链表。
采用这种将集中计算过程分散进行的算法，保证了调度器运行的时间上限，同时在内存中保留更加丰富的信息的做法也加速了候选进程的定位过程。
这一变化简单而又高效，是 2.6 内核中的亮点之一。
arrays 二元数组是两类就绪队列的容器，active 和expired 分别指向其中一个。
active 中的进程一旦用完了自己的时间片，就被转移到expired 中，并设置好新的初始时间片；而当active 为空时，则表示当前所有进程的时间片都消耗完了，此时，active 和expired 进行一次对调，重新开始下一轮的时间片递减过程（参见"调度器"）。
回忆一下2.4 调度系统，进程时间片的计算是比较耗时的，在早期内核版本中，一旦时间片耗尽，就在时钟中断中重新计算时间片，后来为了提高效率，减小时钟中断的处理时间，2.4 调度系统在所有就绪进程的时间片都耗完以后在调度器中一次性重算。
这又是一个O(n) 量级的过程。
为了保证O(1) 的调度器执行时间，2.6 的时间片计算在各个进程耗尽时间片时单独进行，而通过以上所述简单的对调来完成时间片的轮转（参见"调度器"）。
这又是2.6 调度系统的一个亮点。
2) spinlock_t lockrunqueue 的自旋锁，当需要对runqueue 进行操作时，仍然应该锁定，但这个锁定操作只影响一个CPU 上的就绪队列，因此，竞争发生的概率要小多了。
3) task_t *curr本CPU 正在运行的进程。
4) tast_t *idle指向本CPU 的idle 进程，相当于 2.4 中init_tasks[this_cpu()] 的作用。
5) int best_expired_prio记录expired 就绪进程组中的最高优先级（数值最小）。
该变量在进程进入expired 队列的时候保存（schedule_tick()），用途见"expired_timestamp"的解释）。
6) unsigned long expired_timestamp当新一轮的时间片递减开始后，这一变量记录着最早发生的进程耗完时间片事件的时间（jiffies 的绝对值，在schedule_tick() 中赋），它用来表征expired 中就绪进程的最长等待时间。
它的使用体现在EXPIRED_STARVING(rq) 宏上。
上面已经提到，每个CPU 上维护了两个就绪队列，active 和expired。
一般情况下，时间片结束的进程应该从active 队列转移到expired 队列中（schedule_tick()），但如果该进程是交互式进程，调度器就会让其保持在active 队列上以提高它的响应速度。
这种措施不应该让其他就绪进程等待过长时间，也就是说，如果expired 队列中的进程已经等待了足够长时间了，即使是交互式进程也应该转移到expired 队列上来，排空active。
这个阀值就体现在EXPIRED_STARVING(rq) 上：在expired_timestamp 和STARVATION_LIMIT 都不等于0 的前提下，如果以下两个条件都满足，则EXPIRED_STARVING() 返回真：∙（当前绝对时间- expired_timestamp）>= （STARVATION_LIMIT * 队列中所有就绪进程总数+ 1），也就是说expired 队列中至少有一个进程已经等待了足够长的时间；∙正在运行的进程的静态优先级比expired 队列中最高优先级要低（best_expired_prio，数值要大），此时当然应该尽快排空active 切换到expired 上来。
7) struct mm_struct *prev_mm保存进程切换后被调度下来的进程（称之为prev）的active_mm 结构指针。
因为在2.6 中prev 的active_mm 是在进程切换完成之后释放的（mmdrop()），而此时prev 的active_mm 项可能为NULL，所以有必要在runqueue 中预先保留。
8) unsigned long nr_running本CPU 上的就绪进程数，该数值是active 和expired 两个队列中进程数的总和，是说明本CPU 负载情况的重要参数（详见"调度器相关的负载平衡"）。
9) unsigned long nr_switches记录了本CPU 上自调度器运行以来发生的进程切换的次数。
10) unsigned long nr_uninterruptible记录本CPU 尚处于TASK_UNINTERRUPTIBLE 状态的进程数，和负载信息有关。
11) atomic_t nr_iowait记录本CPU 因等待IO 而处于休眠状态的进程数。
12) unsigned long timestamp_last_tick本就绪队列最近一次发生调度事件的时间，在负载平衡的时候会用到（见"调度器相关的负载平衡"）。
13) int prev_cpu_load[NR_CPUS]记录进行负载平衡时各个CPU 上的负载状态（此时就绪队列中的nr_running 值），以便分析负载情况（见"调度器相关的负载平衡"）。
14) atomic_t *node_nr_running; int prev_node_load[MAX_NUMNODES]这两个属性仅在NUMA 体系结构下有效，记录各个NUMA 节点上的就绪进程数和上一次负载平衡操作时的负载情况（见"NUMA 结构下的调度"）。
15) task_t *migration_thread指向本CPU 的迁移进程。
每个CPU 都有一个核心线程用于执行进程迁移操作（见"调度器相关的负载平衡"）。
16) struct list_head migration_queue需要进行迁移的进程列表（见"调度器相关的负载平衡"）。
