关于linux的调度算法

版本的

Linux

内核使用了新的调度器算法，它是由

Ingo

Molnar开发的

O（1）调度器算法。它在高负载的情况下极其出色，并且对处理器调度有很好的扩展。

Linux2.4

版本的标准调度器中，使用时间片重算的算法。这种算法要求在所有的进程都用尽时间片以后，重新计算下一次运行的时间片。这样每次任务调度的花销不确定，可能因为计算比较复杂，产生较大调度延迟。特别是多处理器系统，可能由于调度的延迟，导致大部分处理器处于空闲

状态，影响系统性能。

新的调度器采用

O（1）的调度算法，通过优先级数组的数据结构来实现。优先级数组可以使每个优先级都有相应的任务队列，还有一个优先级位图，每个优先级对应位图中一位，通过位图可快速执行最高优先级任务。因优先级个数是固定的，所以查找的时间也固定，不受运行任务数的影响。

新的调度器为每个处理器维护

2

个优先级数组：有效数组和过期数组。有效数组内任务队列的进程都还有可以运行的时间片；过期数组内任务队列的进程都没有时间片可以执行。当一个进程的时间片用光时，就把它从有效数组移到过期数组，并且时间片也已经重新计算好了。当需要重新调度这些任务的时候，只要在有效数组和过期数组之间切换就好了。这种交换是O（1）算法的核心。

关于该算法的更多内容，google

一下！

* Convert user-nice values [ -20 ... 0 ... 19 ]

* to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],

* and back.

*/

#define NICE_TO_PRIO(nice) (MAX_RT_PRIO + (nice) + 20)

#define PRIO_TO_NICE(prio) ((prio) - MAX_RT_PRIO - 20)

#define TASK_NICE(p) PRIO_TO_NICE((p)->static_prio)

/*

* 'User priority' is the nice value converted to something we

* can work with better when scaling various scheduler parameters,

* it's a [ 0 ... 39 ] range.

*/

#define USER_PRIO(p) ((p)-MAX_RT_PRIO)  

#define TASK_USER_PRIO(p) USER_PRIO((p)->static_prio)

#define MAX_USER_PRIO (USER_PRIO(MAX_PRIO))

说明：MAX_RT_PRIO为100，MAX_PRIO为140，即可计算出MAX_USER_PRIO=40

#define DEF_TIMESLICE (100 * HZ / 1000)  //默认时间片是100ms

/*

* task_timeslice() scales user-nice values [ -20 ... 0 ... 19 ]

* to time slice values: [800ms ... 100ms ... 5ms]

*

* The higher a thread's priority, the bigger timeslices

* it gets during one round of execution. But even the lowest

* priority thread gets MIN_TIMESLICE worth of execution time.

*/

#define SCALE_PRIO(x, prio) \

max(x * (MAX_PRIO - prio) / (MAX_USER_PRIO/2), MIN_TIMESLICE)

static unsigned int task_timeslice(task_t *p)

{

    if (p->static_prio <NICE_TO_PRIO(0))

        return SCALE_PRIO(DEF_TIMESLICE*4, p->static_prio)

    else

        return SCALE_PRIO(DEF_TIMESLICE, p->static_prio)

}

说明：

    当进程的静态优先级<120时，时间片=400*(140-prio)/20

    当进程的静态优先级>=120时，时间片=100*(140-prio)/20

结论：进程的时间片与其静态优先级(static_prio)相关，在运行队列中的位置与其实时优先级相关(prio)。