Linux内核学习013——进程调度(二)

Linux的进程调度

早期版本(1~2.4)的Linux内核中，调度程序十分简陋，其设计易于理解但是非常原始。采用所有任务的方式完成调度，其复杂度为O(n)。这一方法不能在多进程或者多处理器环境下使用，在Linux2.5中引入了O(1)调度器。O(1)调度器在数以十计的多处理器环境下表现出非常好的性能，但是该调度算法对于响应时间比较敏感的程序有些不足。因此，O(1)调度程序可以提高大服务器的工作负载，但是在需要很多交互程序的桌面系统上则表现较差。在Linux2.6.23中，开发人员引入了完全公平调度算法(Completely Fair Scheduler, CFS)。

策略

调度准则：

• CPU利用率：需要尽可能提高CPU利用率。
• 吞吐量：单位时间内完成的进程数量
• 周转时间：从进程提交到进程完成的时间。包括等待进入内存、在就绪队列中等待、在CPU上执行和I/O执行的时间
• 等待时间：进程在就绪队列中等待的时间之和
• 响应时间：从提交请求到产生第一响应的时间

调度器的策略决定何时进程才能运行，并且还用负责优化使用处理器的时间。

进程可以被分为两大类：I/O密集型和CPU密集型。前者指进程的大部分时间都是用来提交I/O请求或是等待I/O请求。后者值进程的大部分时间用于执行代码，它们没有太多的I/O需求。对于这类进程，调度策略需要降低它们的调度频率，延长其执行时间。注：也有进程兼具两种类型的特性。

调度策略需要在两个矛盾的目标中寻找平衡：进程响应迅速(即响应时间短)和最大系统利用率(高吞吐量)。

时间片

时间片是一个数值，表示进程在被抢占前所能持续运行的时间。时间片过长会影响系统对交互的响应，太短则会增大进程切换带来的开销。Linux的CFS调度器没有直接分配时间片给进程，而是分配使用比例。这样进程获得的处理器时间和系统负载相关，且会受到nice值的影响。Linux采用了抢占式调度，即高优先级的进程可以抢占当前进程的运行。对于CFS调度器，抢占时机取决于新的可运行程序消耗的处理器使用比。

调度算法

FCFS

最简单的CPU调度算法是先到先服务调度算法(first-com, first-served)。这一算法可以通过FIFO队列来实现，较为简单。但是，采用FCFS的平均等待时间一般较长。

转法调度

轮转法调度是专门为分时系统设计的，类似于FCFS，但是增加了抢占以切换进程。定义一个固定大小的时间片(比如10~100ms)，将就绪队列中的每个进程轮流执行一个时间片。

优先级调度

优先级调度根据进程的优先级进行调度，高优先级的进程先运行，低优先级的进程后运行，相同优先级的进程按轮转方式进行调度。

Linux采用了两种不同的优先级范围。一种是nice值，范围为-20~+19，默认为0(越大的优先级代表越低的优先级)。具体而言，nice值代表时间片的比例。可通过ps -el查看进程李彪，NI列即为进程对应的nice值。另一种是实时优先级，其值可配置。默认范围为[0, 99]。越高的实时优先级数值代表进程的优先级越高，且任何实时进程的优先级都高于普通进程。