Linux 2.4 进程调度分析 内容提要：
● 前言：技术的背景、特点和应用价值
● 就绪进程选择算法
● 相关数据结构
● 调度器及其他核心应用的调度相关部分：具体实现时函数的调用关系，并对各函数的基本功能进行说明
● Linux 2.4调度系统的一些问题：从操作系统原理的角度对所选择技术的优缺点及可能存在的改进方法进行分析
一. 前言
1. 技术背景： 调度系统对于操作系统的整体性能有着非常重要的影响，嵌入式系统、桌面系统和高端服务器对于调度器的要求是很不一样的。
2. 特点：核心不可抢占、 调度算法简单有效。
3. 应用价值：在开源操作系统中，Linux的发展最为显著，到目前为止，它在低端服务器市场已经占据了相当大的份额。从最新的Linux 2.6系统来看，Linux的发展方向主要有两个：嵌入式系统和高端计算领域。
二． 相关数据结构
在Linux中，进程用task_struct表示，所有进程被组织到以init_task为表头的双向链表中（见[include/linux/sched.h]SET_LINKS()宏），该链表是全系统唯一的。所有CPU被组织到以schedule_data（对界后）为元素的数组之中。进程与所运行的CPU之间可以相互访问（详见下）。
所有处于运行态的进程（TASK_RUNNING）被组织到以runqueue_head为表头的双向链表之中，调度器总是从中寻找最适合调度的进程。runqueue_head也是全系统唯一的。
下面分别介绍这些与调度器工作相关的数据结构。
1． init_tss
TSS，Task State Segment，80x86平台特有的进程运行环境，尽管Linux并不使用TSS，但将TSS所需要描述的信息保存在以cpu号为索引的tss_struct数组init_tss中，进程切换时，其中的值将获得更新。
2． task_struct
在Linux中，线程、进程使用的是相同的核心数据结构，可以说，在2.4的内核里只有进程，其中包含轻量进程。一个进程在核心中使用一个task_struct结构来表示，包含了大量描述该进程的信息，其中与调度器相关的信息主要包括以下几个：
i. state
Linux的进程状态主要分为三类：可运行的（TASK_RUNNING，相当于运行态和就绪态）；被挂起的（TASK_INTERRUPTIBLE、TASK_UNINTERRUPTIBLE和TASK_STOPPED）；不可运行的（TASK_ZOMBIE），调度器主要处理的是可运行和被挂起两种状态下的进程，其中TASK_STOPPED又专门用于SIGSTP等IPC信号的响应，而TASK_ZOMBIE指的是已退出而暂时没有被父进程收回资源的"僵尸"进程。
ii. need_resched
布尔值，在调度器中用于表示该进程需要申请调度（详见"调度器工作流程"）。
iii. policy
在Linux 2.4中，进程的调度策略可以有三种选择：SCHED_FIFO（先进先出式调度，除非有更高优先级进程申请运行，否则该进程将保持运行至退出才让出CPU）、SCHED_RR（轮转式调度，该进程被调度下来后将被置于运行队列的末尾，以保证其他实时进程有机会运行）、SCHED_OTHER（常规的分时调度策略）。另外，policy中还包含了一个SCHED_YIELD位，置位时表示主动放弃CPU。
iv. rt_priority
用于表征实时进程的优先级，从1-99取值，非实时进程该项应该为0。这一属性将用于调度时的权值计算（详见"就绪进程选择算法"）。
v. counter
该属性记录的是当前时间片内该进程还允许运行的时间（以CPU时钟tick值为单位，每个进程的counter初值与nice值有关，nice越小则counter越大，即优先级越高的进程所允许获得的CPU时间也相对越多），并参与"就绪进程选择算法"。在Linux 2.4中，每个（非SCHED_FIFO实时）进程都不允许运行大于某一时间片的时间，一旦超时，调度器将强制选择另一进程运行（详见"调度器工作流程"）
vi. nice
用户可支配的进程优先级，将参与"就绪进程选择算法"，同时该值也决定了该进程的时间片长度（详见下）。
vii. cpus_allowed
以位向量的形式表示可用于该进程运行的CPU（见"调度器工作流程"）。
viii. cpus_runnable
以位向量的形式表示当前运行该进程的CPU（相应位为1）。如果不在任何CPU上运行，则为全1。这一属性和cpus_allowed属性结合，可以迅速判断该进程是否能调度到某一CPU上运行（位"与"）。
ix. processor
本进程当前（或最近）所在CPU编号。
x. thread
用于保存进程执行环境（各个寄存器的值以及IO操作许可权映射表），内容与TSS相近。因为TSS以CPU id为索引，而Linux无法预测被替换下来的进程下一次将在哪个CPU上运行，所以这些信息不能保存在TSS中。
