Linux进程调度的常用数据结构和函数

Linux2.4内核进程调度的缺陷：

Linux2.4 内核的进程调度采用时间片轮转和优先级相结合的调度策略，但存在以下几个致命缺陷:

1>调度算法时间复杂度是 O(n)。2.4 内核每次调度都要进行一次循环,耗时与当前就绪进程数有关,因此达不到实时性的要求；时间片重算时必须给 task_struct 结构和就绪进程队列上锁.

2>不提供抢占式调度,会导致大量的竞争,使就绪队列成为一个明显的瓶颈;

3>在 SMP 系统中,只有一个就绪队列,这将导致大部分的 CPU 处于空闲状态,从而影响 SMP 的效率;

Linux2.6 内核进程调度分析

进程的调度时机与引起进程调度的原因和进程调度的方式有关。在 2.6 中,除核心应用主动调用调度器之外, 核心还在应用不完全感知的情况下在以下三种时机中启动调度器工作:

1>从中断或系统调用返回到用户态;

2>某个进程允许被抢占 CPU;

3>主动进入休眠状态;

调度策略：

在 Linux2.6 中,仍有三种调度策略: SCHED_OTHER、SCHED_FIFO 和 SCHED_RR。

SCHED_ORHER:普通进程，基于优先级进行调度。

SCHED_FIFO：实时进程，实现一种简单的先进先出的调度算法。

SCHED_RR：实时进程，基于时间片的SCHED_FIFO,实时轮流调度算法。

前者是普通进程调度策略,后两者都是实时进程调度策略。

SCHED_FIFO 与 SCHED_RR 的区别是:

当进程的调度策略为前者时,当前实时进程将一直占用 CPU 直至自动退出,除非有更紧迫的、优先级更高的实时进程需要运行时,它才会被抢占 CPU;当进程的调度策略为后者时,它与其它实时进程以实时轮流算法去共同使用 CPU，用完时间片放到运行队列尾部。

注：实时进程的优先级高于普通进程，后面介绍。

O(1)调度器是以进程的动态优先级 prio为调度依据的,它总是选择目前就绪队列中优先级最高的进程作为候选进程 next。由于实时进程的优先级总是比普通进程的优先级高,故能保证实时进程总是比普通进程先被调度。

Linux2.6 中,优先级 prio 的计算不再集中在调度器选择 next 进程时,而是分散在进程

状态改变的任何时候,这些时机有:

1>进程被创建时;

2>休眠进程被唤醒时;

3>从TASK_INTERRUPTIBLE 状态中被唤醒的进程被调度时;

4>因时间片耗尽或时间片过长而分段被剥夺 CPU 时;

在这些情况下,内核都会调用 effective_prio()重新计算进程的动态优先级 prio并根据计算结果调整它在就绪队列中的位置。