进程调度

进程调度程序可看作在可运行态进程之间分配有限的处理器时间资源的内核子系统。

在一组处于可运行状态的进程中选择一个来执行，是调度程序所需要完成的基本工作。

多任务系统可以划分为两类：非抢占式多任务和抢占式多任务模式。

linux是抢占式多任务模式，在这个模式下，由调度程序来决定什么时候停止一个进程的运行以便其他进程能够得到执行，这个强制挂起动作就叫做抢占。进程在被抢占之前能够运行的时间是被分配好的，而且有一个专门名字，叫进程的时间片。

4.1 策略

非抢占式多任务模式下，除非进程自己停止，否则会一直执行。

4.1.1 I/O消耗型和处理器消耗型的进程

进程可以被分为I/O消耗型和处理器消耗型。前者是指进程的大部分时间用来提交I/O请求或是等待I/O请求。这样的进程经常处于可运行状态，通常都是运行短短的一会。因为他在等待更多的I/O请求时候总会阻塞（这里指的是所有的I/O操作，像键盘活动等都包括）。

4.1.2 进程优先级

优先级高的进程先运行，优先级低的进程后运行，优先级高的进程时间片较长。

linux采用动态优先级的调用方式，一开始先设置基本的优先级，然后他允许调度程序根据需要来加减优先级。如果一个进程在I/O等待上耗费的时间多于其运行时间，那么该进程明显属于I/O消耗型进程。他会被动态的提高，如果一个进程的全部时间片一下就被耗尽，那么该进程属于处理器消耗型进程，他的优先级会被动态的降低。

linux内核提供了两种独立的优先级范围。一种是nice值，范围-20－－19，默认值为0。nice值也用来决定分配给进程的时间片的长短。

4.1.3 时间片

调度策略必须规定一个默认的时间片，这个时间片为20ms。

进程并不是一定非要一次就用完它所有的时间片。他可以分几次运行，这样他可以保证它们尽可能长时间的处于可运行状态。当等到其他所有的进程都耗尽了它们的时间片。在那个时候，所有进程的时间片会被重新计算。

4.1.4 进程抢占

linux系统是抢占式的，当一个进程进入TASK_RUNNING状态，内核会检查它的优先级是否高于当前正在执行的进程。如果这样，调度程序会被唤醒，抢占当前正在运行的进程并运行新的进程。当一个进程时间片为0时，它会被抢占，调度程序会被唤醒选择一个新的进程。

4.2 linux调度算法

linux的调度程序定义于kernel/sched.c中。

4.2.1 可执行队列

调度程序中最基本的数据结构是运行队列（runqueue）。可执行队列定义于kernel/sched.c中，可执行队列是给定处理器上的可执行进程的链表。

为什么是kernel/sched.c而不是kernel/sched.h，因为把调度程序的代码抽象出来而只给内核的其余部分提供某些接口是一种理想的做法。把运行队列的代码放在头文件中会使调度程序以外的代码也访问运行队列的代码，这不是一种理想的做法。

由于可执行队列是调度程序的核心数据结构体，所以有一组宏定义用于获取与给定处理器或进程相关的可执行队列。cpu_rq(processor)宏用于返回给定处理器可执行队列的指针。this_rq()宏用来返回当前处理器的可执行队列。宏task_rq(task)返回给定任务所在的队列指针。

在对可执行队列进行操作以前，应该先锁住它，因为每个可执行队列唯一地对应一个处理器，所以很少出现一个处理器需要锁在其他处理器的可执行队列的情况。在其拥有者读取或改写队列成员的时候，可执行队列包含的锁用来防止队列被其他代码改动，锁住运行队列的最常见情况发生在你想锁住的运行队列上恰巧有一个特定的任务在运行。此时需要用到task_rq_lock()和task_rq_unlock()函数。

this_rq_lock()来锁住当前的可执行队列，用rq_unlock(struct runqueue *rq)释放给定队列的锁。

为了避免死锁，要锁住多个运行队列的代码必须总是按照同样的顺序获取这些锁。

嵌套的锁必须以相同的顺序操作，自旋锁用于防止多个任务同时对可执行队列进行操作。

例：最开始，一个任务来到门前，拿起钥匙开了门，走进去把门锁上。如果这个时候第二个任务来了，没有钥匙，只能在门口等着，直到第一个任务走出来交出钥匙，这个等待过程叫做自旋。因为实际上任务是在不停地执行一个循环操作来查询钥匙是否被交出来。

如果一号任务先锁住队列甲，然后锁队列乙，而二号任务想先锁住队列乙，然后锁住队列甲，如果在一号任务锁住队列甲同时，二号任务锁住了队列乙，就是说，钥匙都被对方拿着，就形成了死锁。如果两个任务用相同的顺序操作锁，这种局面就不会产生。

4.2.3 重新计算时间片

linux为每个处理器维护两个优先级数组：活动数组，过期数组。活动数组内的可执行队列上的进程都还有时间片剩余；而过期数组内的可执行队列上的进程都耗尽了时间片。当一个进程的时间片耗尽时，它会被移至过期数组，但在此之前，时间片已经给它重新计算好了。

4.2.4 schedule()

选定下一个进程并切换到它去执行是通过schedule()函数实现的。当内核代码想要休眠时，会直接调用该函数，如果哪个进程被抢占，那么该函数也会被唤起执行。schedule()函数独立于每个处理器运行。因此，每个CPU都要对下一次该运行哪个进程做出自己的判断。

4.2.5 计算优先级和时间片

如果一个进程的大部分时间都在休眠，那么它就是I/O消耗型的，如果一个进程执行的时间比休眠的时间长，那它就是处理器消耗型的。当一个任务的时间片用完之后，就要根据任务的静态优先级重新计算时间片。task_timeslice()函数为给定任务返回一个新的时间片。时间片的计算只需要把优先级按比例缩放。

4.2.6 睡眠和唤醒

休眠（被阻塞）的进程处于一个特殊的不可执行状态。进程把自己标记成休眠状态，把自己从可执行队列移出，放入等待队列，然后调用schedule()选择和执行一个其他进程。唤醒的过程刚好相反：进程被设置为可执行状态，然后再从等待队列中移到可执行队列。

4.2.7 负载平衡程序

如果可执行队列间出现负载不均衡的情况时，比如一个处理器的队列上有五个进程，而另外一个处理器上只有一个进程，该怎么处理呢？负载平衡程序会拿当前处理器的可执行队列和系统中的其他可执行队列做比较，如果它发现了不均衡就会把相对繁忙的队列中的进程抽到当前的可执行队列中来。负载平衡由kernel/sched.c中的函数load_balance()来实现。

4.3 抢占和上下文切换

从一个可执行的进程切换到另一个可执行的进程，由定义在kernel/sched.c中的context_switch()函数负责处理。