进程调度
1.策略
进程可以被划分为I/O消耗型和处理器消耗型。前者指进程的大部分时间用来提交I/O请求或是等待I/O请求，常处于可运行状态。后者把时间大多用在执行代码上，除非被抢占，否则一直不停地运行，调度器不应该经常让它们运行。
调度算法中最基本的一类就是基于优先级的调度。这是一种根据进程的价值和其对处理器时间的需求来对进程分级的想法。优先级高的进程先运行，低的后运行，相同优先级的进程按轮转方式进行调度。
Linux根据以上思想实现了一种基于动态优先级的调度方法。一开始，该方法先设置基本的优先级，然而它允许调度程度根据需要来加、减优先级。例如，如果一个进程在I/O等待上耗费的时间多于其运行时间，那么该进程明显属于I/O消耗型，它的优先级会被动态提高。相反，处理器消耗型进程的优先级会被动态降低。
Linux内核提供两组独立的优先级范围。第一种是nice值，范围从-20到+19，默认值是0。nice值越大优先级越低。第二种是实时优先级，其值可配置，范围从0到99，任何实时进程的优先级都高于普通的进程。
时间片是一个数值，它表明进程在被抢占前所能持续运行的时间，I/O消耗型不需要长的时间片，而处理器消耗型的进程则希望越长越好。注意，进程并不是一定非要一次就用完它所有的时间片，例如一个拥有100毫秒时间片的进程，可以通过重复调度，分5次每次20毫秒用完这些时间片。
Linux是抢占式的。当一个进程进入TASK_RUNNING状态，内核会检查它的优先级是否高于当前正在执行的进程。如果是这样，调度程序会被唤醒，抢占当前正在运行的进程并运行新的可运行进程。此外，当一个进程的时间片变为0时，它会被抢占，调度程序被唤醒以选择一个新的进程。
2.Linux调度算法
调度程序中最基本的数据结构是运行队列（runqueue）。可执行队列定义在kernel/sched.c中。可执行队列是给定处理器上的可执行进程的链表，每个处理器一个。每个可投入运行的进程都唯一的归属一个可执行队列。此外，可执行队列中还包含每个处理器的调度信息。
每个运行队列都有两个优先级数组，一个活跃的和一个过期的。优先级数组是一种能够提供O（1）级算法复杂度的数据结构。优先级数组使可运行处理器的每一种优先级都包含一个相应的队列，而这些队列包含对应优先级上的可执行进程链表。优先级数组还拥有一个优先级位图，当需要查找当前系统内拥有最高优先级的可执行进程时，它可以帮助提高效率。
活跃数组内的可执行队列上的进程都还有时间片剩余，而过期数组内的都耗尽了时间片。当一个进程的时间片耗尽时，它会被移至过期数组，但在此之前，时间片已经给它重新计算好。重新计算时间片变得非常简单，只要在活跃和过期数组之间来回切换，这是O（1）级调度程序的核心。
选定下一个进程并切换到它去执行是通过schedule()函数实现的。当内核代码想要休眠时，会直接调用该函数，另外，如果有哪个进程将被抢占，那么该函数也会被唤起执行。schedule()函数独立于每个处理器运行。