Linux内核2.6的进程调度

    Linux是多任务抢占操作系统，多任务就是指多个进程间通过分时切换来并发执行。非抢占的系统是对每个进程而言，除非时间片用完或主动放弃否则不会被剥夺CPU，主动放弃包括调用一些调度的系统调用（比如sched_yield）或者调用IO等阻塞操作。抢占式系统表示即使当前进程没有用完时间片，也没有主动放弃CPU，如果调度系统发现有更高动态优先级的进程，则强制剥夺当前进程的CPU，选择更高动态优先级的进程执行。
    调度系统什么时候查看是否有更高优先级的进程呢？有这些情况：①时钟中断处理程序（Linux2.6的系统时钟频率默认是1000HZ，即每1ms调用一次时钟中断处理程序，具体系统配置的时钟频率可以通过cat /boot/config-* | grep "^CONFIG_HZ="来获取）。如果是多核处理器，则每个CPU都会执行时钟中断处理程序（其他中断处理程序只会映射到某个CPU上执行）；②其他一些中断处理程序，会让某个CPU执行调度程序；③当前进程阻塞、睡眠等主动放弃处理器；④当前进程用完时间片；⑤创建了新进程；⑥执行一些调度相关的系统调用，比如改变进程的静态优先级等。
    内核2.6的进程调度策略一共有三种：SCHED_NORMAL，SCHED_FIFO和SCHED_RR。其中SCHED_NORMAL用于普通进程的调度，后两种用于实时进程的调度。
    Linux的进程有的属于IO消耗型进程，有的属于处理器消耗型进程。IO消耗型进程希望获得更多的处理器响应机会，每次响应不需要很长时间；处理器消耗型进程则相反。调度程序通常在系统响应速度和最大系统吞吐量之间寻求平衡。
    Linux进程的静态优先级。静态优先级分为两个范围：0~99是实时进程的静态优先级（值越大优先级越高），100~139是普通进程的静态优先级（通过nice值表示，-20~19，值越大优先级越低）。
    首先介绍普通进程的调度策略。Linux采用称为完全公平调度算法的调度策略（CFS），每个CPU都有个可运行队列，多个处理器的可运行队列会在调度时进行队列的平衡处理。对某个处理器而言，应该选取哪个进程投入执行是调度的核心问题，CFS根据当前可运行队列中普通进程的静态优先级给每个进程分配处理器使用比，确定周期时间T（T的选取和可运行进程个数相关，默认是20ms，这个时间T是用来控制进程切换频率的，如果太小会导致进程很快完成当前分配的处理比，而重新分配处理比，重新调度）。调度时计算虚拟运行时间，这个时间很关键，因为调度系统就是选择最小虚拟运行时间的进程投入执行。
    虚拟运行时间是指每个进程的实际运行时间标准化后的时间，这个时间是相对的，可以理解为实际时间处理处理器使用比。调度思想是这样的，每个进程已经分配好处理器使用比了，调度系统希望各个进程差不多同时用完这个使用比，而不是有的进程很早完成，有的进程很晚完成。那么各个进程的完成的程度就是调度的依据，总是选择完成比最小的进程投入运行。
    如果一个进程阻塞了，其他进程运行了一段时间，显然这个阻塞进程的完成比最小，那么当它醒过来的时候，会导致很长一段时间都只运行这个进程，所以在唤醒时会将完成比调整为当前可运行队列中完成比的最小值。新建的进程会根据优先级计算一个完成比，而不是简单的完成比赋为0。
    再介绍实时进程的调度。SCHED_FIFO策略很简单，就是选取最高静态优先级的实时进程投入运行，并且直到进程运行完成或被更高优先级的实时进程抢占。SCHED_RR是带时间片的SCHED_FIFO。内核不为实时进程计算动态优先级。