分类： LINUX
2010-08-19 19:02:37
调度程序是内核的组成部分，它负责选择下一个要运行的进程。进程调度程序可看作在可运行态进程之间分配有限的处理器时间资源的内核子系统。
多任务操作系统就是能够同时并发的交互执行多个进程的操作系统。多任务系统可以划分为两类：抢占式和非抢占式。Linux提供了抢占式的多任务模式。在此 模式下，由调度程序来决定什么时候停止一个进程的运行以便其他进程能够得到执行机会。这个强制的挂起动作叫做抢占。进程在被抢占之前能够运行的时间是预先 设置好的，而且有一个专门的名字，叫进程的时间片。时间片实际上就是分配给每个可运行进程的处理器时间段。
4.1 策略
4.1.1 进程优先级
进程可以分为I/O消耗型和处理器消耗型。调度算法中最基本的一类就是基于优先级的调度。这是一种根据进程的价值和其对处理器时间的需求来对进程分级的想 法。在Linux系统中，优先级高的进程使用的时间片也较长。调度程序总是选择时间片未用尽而且优先级高的进程运行。用户和系统都可以通过设置进程的优先 级来影响系统的调度。
Linux内核提供了两组独立的优先级范围。第一种是nice值，范围 -20~19，默认是0。值越大，优先级越低，时间片越短。第二个范围是实时优先级，其值可配置，变化范围：0~99。
4.2 可执行队列（运行队列）
当内核要寻找一个新的进程在CPU上运行时，必须只考虑处于可运行状态的进程，（即在TASK_RUNNING状态的进程），因为扫描整个进程链表是相当低效的，所以引入了处于可运行状态的进程的双向循环链表，也叫运行队列（runqueue）。
运行队列容纳了系统中所有可以运行的进程，它是一个双向循环队列，该队列通过task_struct结构中的两个指针run_list（Pointers to the next and previous elements in the runqueue list to which the process belongs）链表来维持。队列的标志有两个：一个是“空进程”idle_task、一个是队列的长度。
有两个特殊的进程永远在运行队列中待着：当前进程和空进程。前面我们讨论过，当前进程就是由cureent指针所指向的进程，也就是当前运行着的进程，但是请注意，current指针在调度过程中（调度程序执行时）是没有意义的；空进程是个比较特殊的进程，只有系统中没有进程可运行时它才会被执行，Linux将它看作运行队列的头，当调度程序遍历运行队列，是从idle_task开始、至idle_task结束的，在调度程序运行过程中，允许队列中加入新出现的可运行进程，新出现的可运行进程插入到队尾，这样的好处是不会影响到调度程序所要遍历的队列成员，可见，idle_task是运行队列很重要的标志。
另一个重要标志是队列长度，也就是系统中处于可运行状态（TASK_RUNNING）的进程数目，用全局整型变量nr_running表示，在/kernel/fork.c中定义如下：
int nr_running=1；
若 nr_running为0，就表示队列中只有空进程。在这里要说明一下：若nr_running为0，则系统中的当前进程和空进程就是同一个进程。但是Linux会充分利用CPU而尽量避免出现这种情况。
由于可执行队列是调度程序的核心数据结构体，所以有一组宏定义用于获取与“给定处理器或进程”相关的可执行队列。cpu_rq（processor）宏用于返回给定处理器可执行队列的指针。this_rq()宏用来返回当前处理器的可执行队列。宏task_rq(task)返回给定任务所在的队列指针。
在 对可执行队列进行操作以前，应该先锁住它。因为每个可执行队列唯一的对应一个处理器。在其拥有者读取或者改写队列成员的时候，可执行队列包含的锁用来防止 队列被其它代码改动。锁住运行队列最常见的情况发生在你想锁住的运行队列上恰巧有一个特定的任务在运行。此时需要用到task_rq_lock()和 task_rq_unlock()函数：
struct runqueue *rq;
unsigned long flags;
rq = task_rq_lock(task,&flags);
对任务队列的操作
task_rq_unlock(rq, &flags);
一个疑问，解锁后，之前的任务还继续运行吗？
睡眠和唤醒
休 眠（被阻塞）的进程处于一个特殊的不可执行状态。 进程休眠有种原因，但肯定都是为了等待一些事件。事件可能是一段时间，从文件I/O读取更多的数据，或者是某个硬件事件。一个进程还有可能在尝试获取一个 已被占用的内核信号量时被迫进入休眠。休眠的一个常见原因是文件I/O——如进程对一个文件执行了read()操作，而这需要从磁盘里读取。还有，进程在 获取键盘输入的时候也需要等待。无论哪种情况，内核的操作都相同：进程把它自己标记成休眠状态，把自己从可执行队列移出，放入等待队列，然后调用 schedule()选择和执行一个其他进程。唤醒的过程刚好相反；进程被设置为可执行状态，然后再从等待队列中移到可执行队列。 等待队列：休眠通过等待队列来处理，等待队列是由等待某些事件发生的进程组成的简单链表。
4.3 抢占和上下文切换
上下文切换，也就是从一个可执行进程切换到另一个可执行进程，由定义在kernel/sched.c中的context_switch()函数处理。每当一个新的进程被选出来准备投入运行的时候，schedule()就会调用该函数。它完成两项基本工作：
（1）调用定义在
（2）调用定义在
4.3.1 用户抢占
内 核即将返回用户空间的时候，如果need_resched标志被设置，会导致schedule()被调用，此时就会发生用户抢占。内核无论是从中断处理程 序还是在系统调用后返回，都会检查need_resched标志。如果它被设置了，那么内核会选择一个其他进程投入运行。从中断处理程序或系统调用返回的代码都是和体系结构相关的，在entry.S(此文件不仅包含内核入口部分的程序，内核退出部分的代码也在其中)文件中通过汇编语言来实现。
4.3.2 内核抢占
只 要当前进程没有持有锁，内核就可以进行抢占。锁是非抢占区的标志。所以，如果没有持有锁，那么正在执行的代码就是可重新导入的，也就是可抢占的。 为了支持内核抢占，每个进程的thread_info引入了preempt_count计数器。初始值为0，每当使用锁的时候就加1，释放锁的时候就减 1。当=0时，内核就可以被抢占。从中断返回内核空间的时候，内核会检查need_resched和preempt_count的值。如果前者被设置，且 后者为0，则说明有一个更为重要的任务需要执行并且可以安全的抢占，此时，调度程序就会被调用。
4.4 与调度相关的系统调用
