recalc_task_prio函数

函数recalc_task_prio更新进程p的平均睡眠时间和动态优先级，更重要的是，他还通过平均睡眠时间判断进程是否是交互进程。它接收进程描述符的指针p和由函数sched_clock()计算出当前时间戳now作为参数。

static int recalc_task_prio(struct task_struct *p, unsigned long long now)
{
    /* Caller must always ensure 'now >= p->timestamp' */
    unsigned long sleep_time = now - p->timestamp;

    if (batch_task(p) || sched_interactive == 0)
        sleep_time = 0;

    if (likely(sleep_time > 0)) {

        unsigned long ceiling = INTERACTIVE_SLEEP(p);

        if (p->mm && sleep_time > ceiling && p->sleep_avg < ceiling) {

            p->sleep_avg = ceiling;

            p->sleep_type = SLEEP_NONINTERACTIVE;
        } else {

            if (p->sleep_type == SLEEP_NONINTERACTIVE && p->mm) {
                if (p->sleep_avg >= ceiling)
                    sleep_time = 0;
                else if (p->sleep_avg + sleep_time >=
                     ceiling) {
                        p->sleep_avg = ceiling;
                        sleep_time = 0;
                }
            }

            p->sleep_avg += sleep_time;

        }
        if (p->sleep_avg > NS_MAX_SLEEP_AVG)
            p->sleep_avg = NS_MAX_SLEEP_AVG;
    }

    return effective_prio(p);
}


该函数执行下述操作：
1.  把now  -  p->timestamp的结果赋给局部变量sleep_time。这个好理解吧，p->timestamp字段包含导致进程进入睡眠状态的进程切换的时间戳，因此，sleep_time中存放的是从进程最后一次执行开始，进程消耗在睡眠状态的纳秒数（如果进程睡眠的时间更长，sleep_time就等于1s）。

2. 如果是批处理进程（batch_task(p)），或者不是交互式进程（sched_interactive == 0，因为有可能是内核线程），则sleep_time = 0，并直接到第7步。呵呵，牢记！非交互进程是不需要调整平均睡眠时间的。

3. 如果是用户进程（p->mm!=NULL），且睡眠时间超过了睡眠时间极限（ sleep_time > ceiling），并且其平均睡眠时间居然还小于睡眠时间极限（p->sleep_avg < ceiling)），则说明它休眠得太长了，肯定不是什么好鸟，至少不是交互进程。那么将它的平均休眠时间调整（降低到）ceiling，同时为了避免饥饿，将其类型改成非交互进程（p->sleep_type = SLEEP_NONINTERACTIVE）。随后跳到第6步。

这里补充一个概念：睡眠时间极限，就是ceiling，它是指其规定对应的静态优先级产生的最长交互式进程休眠时间。睡眠时间极限依赖于进程的静态优先级。简而言之，第4步的目的是保证已经在不可中断模式上（通常是等待磁盘I/O的操作）睡眠了很长时间的进程获得一个预先确定而且足够长的平均睡眠时间，以使这些进程即能尽快获得服务，又不会因睡眠时间太长而引起其它进程的饥饿。

4. 如果不同时满足第3步的三个条件，那么又会有两种情况，其本身就不是非交互进程（p->sleep_type = SLEEP_NONINTERACTIVE）并且又是用户进程的话，就把它的sleep_time给清零了。除此之外直接跳到第5步。

5. 平均睡眠时间累加：p->sleep_avg += sleep_time。注意，这里充分的体现了sleep_avg并不是计算平均时间，而是对sleep_time进行累加以领取奖赏（bonus）。

6. 最后检查进程平均睡眠时间是否超过最大值NS_MAX_SLEEP_AVG。检查p->sleep_avg是否超过1000个时钟节拍（以毫秒为单位），如果是，函数就把它减到1000个时钟节拍（以毫秒为单位，即1秒）。
#define NS_MAX_SLEEP_AVG    (JIFFIES_TO_NS(MAX_SLEEP_AVG))

7.    更新进程的动态优先权：p->prio = effective_prio(p);函数effective_prio( )已经在前面的“scheduler_tick( )函数 ”博文中讨论过。

上面是整个函数的流程，很多人（包括我）在第3步的时候会看晕，下面我就这个步骤再深入一些。

首先，补充一个知识点，判断进程的睡眠时间极限的宏——INTERACTIVE_SLEEP(p) ：

#define INTERACTIVE_SLEEP(p) (JIFFIES_TO_NS(MAX_SLEEP_AVG * (MAX_BONUS / 2 + DELTA((p)) + 1) / MAX_BONUS - 1))

该宏在函数中返回给内部变量ceiling。我们前面说过，为了避免进程产生饥饿，完全依靠进程过去的平均睡眠时间。这里就是代码的体现：

#define JIFFIES_TO_NS(TIME)    ((TIME) * (1000000000 / HZ))

上边的代码是做一个JIFFIES向处理器速度的转换，我们把它看成定值；MAX_BONUS定义很复杂，我们来考察考察：

#define MAX_BONUS  (MAX_USER_PRIO * PRIO_BONUS_RATIO / 100)
#define PRIO_BONUS_RATIO   25
#define MAX_USER_PRIO   (USER_PRIO(MAX_PRIO))
#define USER_PRIO(p)   ((p)-MAX_RT_PRIO)
#define MAX_USER_RT_PRIO    100
#define MAX_RT_PRIO        MAX_USER_RT_PRIO
#define MAX_PRIO        (MAX_RT_PRIO + 40)

MAX_BONUS = ((((MAX_RT_PRIO + 40)-MAX_RT_PRIO)) * 25)/100 = 10

好家伙，MAX_BONUS算了半天是个定值10，跟我们在“进程调度的数据结构和优先级 ”博文中bonus（奖赏）是从范围0~10的值相吻合。下面再来考察考察MAX_SLEEP_AVG：

#define MAX_SLEEP_AVG        (DEF_TIMESLICE * MAX_BONUS)
#define DEF_TIMESLICE        (100 * HZ / 1000)

MAX_SLEEP_AVG = 100 * HZ / 1000 * 10

哈哈，还是定值。也就是说ceiling内部变量其实就跟DELTA((p))成正比，所以我们考察DELTA宏：

#define DELTA(p) (SCALE(TASK_NICE(p) + 20, 40, MAX_BONUS) - 20 * MAX_BONUS / 40 + INTERACTIVE_DELTA)
#define SCALE(v1,v1_max,v2_max) (v1) * (v2_max) / (v1_max)
#define TASK_NICE(p)        PRIO_TO_NICE((p)->static_prio)

也就是说，DELTA((p))宏又与(p)->static_prio成正比。所以到头来，静态优先级越高，ceiling越小。

进程的 sleep_avg 值是决定进程动态优先级的关键，也是进程交互程度评价的关键，它的设计是 2.6 调度系统中最为复杂的一个环节，可以说，2.6 调度系统的性能改进，很大一部分应该归功于 sleep_avg 的设计。这里，我们将专门针对 sleep_avg 的变化和它对调度的影响进行分析，着重理解recalc_task_prio为什么会这样做。

内核中主要有四个地方会对 sleep_avg 进行修改：休眠进程被唤醒时（activate_task()调用 recalc_task_prio() 函数）、TASK_INTERRUPTIBLE 状态的进程被唤醒后第一次调度到（schedule()中调用 recalc_task_prio()）、进程从 CPU 上被剥夺下来（schedule()函数中）、进程创建和进程退出。recalc_task_prio() 主要是通过计算进程的等待时间（或者是在休眠中等待，或者是在就绪队列中等待）对优先级的影响来重置优先级。

最后一个环节，我们来讨论如何判断一个进程是否是交互进程。首先，交互进程必须是实时的 ，因为当接受用户的指令后，其必须立即被唤醒，所以其静态优先级必须很高 。其次，其睡眠时间会很长（sleep_avg值很大），因为用户的动作肯定是比不过机器的速度，所以要避免其久久位于运行队列中的expired中而产生饥饿。

判断一个进程是否是交互进程由宏TASK_INTERACTIVE(p)来实现 ：

#define TASK_INTERACTIVE(p) ((p)->prio <= (p)->static_prio - DELTA(p))
#define DELTA(p) (SCALE(TASK_NICE(p) + 20, 40, MAX_BONUS) - 20 * MAX_BONUS / 40 + INTERACTIVE_DELTA)
#define SCALE(v1,v1_max,v2_max) (v1) * (v2_max) / (v1_max)
#define TASK_NICE(p) PRIO_TO_NICE((p)->static_prio)
#define PRIO_TO_NICE(prio)    ((prio) - MAX_RT_PRIO - 20)
#define INTERACTIVE_DELTA      2

DELTA(p) = (p->static_prio - 100) / 4 -3，那么：

TASK_INTERACTIVE(p) = p->static_prio - (p->static_prio - 100) / 4 + 3

该宏主要基于进程的static_prio值来判定它是不是一个“交互性十足”的进程。static_prio值越小(优先级越高)，越能说明该进程交互性越高。那么，怎么从程序上来判断呢？如果一个进程的动态优先级变高了，即p->prio的值变小了，（回忆一下动态优先级计算公式p->prio = p->static_prio - bonus，即平均睡眠时间sleep_avg增大了，bonus也增大，那么p->prio就变小），小到一定程度，即小于等于p->static_prio - (p->static_prio - 100) / 4 + 3，就变成交互性进程。