http://www.akaedu.org/bbs/viewthread.php?tid=16231&extra=page%3D1Linux Kernel 2.6进程 调度的分析 4(1) interactive_credit --
奖励sleep_avg
interactive_credit是设置在task_struct里面用来标记进程的"交互程度"的，它在 进程创建时候被置为0，以后随着不同的情况而增加，减少。 增加 interactive_credit有两处增1的地方，都在函数recalc_task_prio()里面。 a. 进程所拥有的内存区域不为空(p->mm!=NULL)，即进程不是内核进程，如果不是从 TASK_UNINTERRUPTIBLE状态中被唤醒的（p->activated!=-1），且等待的时间（包 括在休眠中等待时间和在就绪队列中等待时间）超过了一定限度（sleep_time> INTERACTIVE_SLEEP(p)）；此时将interactive_credit增1； b. 进程的等待时间大于NS_MAX_SLEEP_AVG了，这种进程很可能是交互进程，所以 interactive_credit增1。 减少 interactive_credit只有一处地方减1，在函数schedule()里面。当进程将要被切换 出CPU的时候，要计算进程的运行时间run_time，并将进程的sleep_avg进行调整，如 果调整后的sleep_avg小于0（说明进程的运行时间大于等待时间），而且该进程的 interactive_credit在HIGH_CREDIT(p)和LOW_CREDIT(p)之间（说明该进程非交互进程）， 则将interactive_credit减1作为对进程的惩罚。 从上面的分析可以看出，无论interactive_credit如何增减，它都在-(CREDIT_LIMIT +1) ~ (CREDIT_LIMIT+1)范围内；而且当interactive_credit增大到CREDIT_LIMIT+ 1，即调度器认定该进程为交互进程以后，interactive_credit就不再变化。 调度器采用宏HIGH_CREDIT()来判断一个进程是否是交互进程，如果是，则该进程将 得到以下奖励： a. 当进程被剥夺CPU使用权时，如果发现该进程是交互进程，则将该进程的运行时间 减小，run_time /= (CURRENT_BONUS(prev) ? : 1)。即sleep_avg减去的运行时间比 实际的运行时间要小，从而增加进程的sleep_avg。 b. 交互式进程在就绪队列上等待的时间也将增加到sleep_avg里面，p->sleep_avg += sleep_time；从而增加进程的sleep_avg。 可见，对于交互进程都是奖励sleep_avg的，从而达到提高优先级的目的。对于交互 式进程，调度器并没有在时间片上进行奖励，而是在优先级上进行奖励，是因为交互 式进程通常是运行时间短、睡眠时间长，而且要求响应快，而奖励优先级可以给交互 进程更多的运行机会，因此，调度器对于交互进程的奖励办法是非常公平和科学的。 (2) 平均等待时间sleep_avg -- 奖励动态优先级 在"平均等待时间"一节已做详细介绍。对于交互进程来说，因为它睡眠的时间较长， 所以sleep_avg要大一些。另外，经常处于TASK_INTERRUPTIBLE状态，而且是被中断 唤醒的进程最有可能是交互进程，而这种进程的衡量因素也是sleep_avg。 总之，由于交互进程一般sleep_avg较大，所以调度器通过奖励动态优先级的方式来 使得进程获得更多执行的机会。 (3) TASK_INTERACTIVE() -- 奖励再次被插入active array 这个宏是根据进程的动态优先级和静态优先级来判断该进程的"交互程度"。在进程时 间片用完时，使用这个宏作为一个参考因素来决定是否将进程重新插入active array 。它的定义是： (p)->prio <= (p)->static_prio - DELTA(p) DELTA(p) = (SCALE(TASK_NICE(p), 40, MAX_BONUS) + INTERACTIVE_DELTA) SCALE(v1,v1_max,v2_max) = (v1) * (v2_max) / (v1_max) 可以看出这个宏是将进程的动态优先级和进程的静态优先级做比较，以判断nice值为 n（静态优先级）时，进程p需要多大的动态优先级才能具有"足够的交互性"。从宏的 定义可以看出当进程的nice值大于12时，进程是不可能被认为是具有足够的交互性（ 因为nice>12时，DELTA(p)>5，而由于sleep_avg给进程带来的动态优先级上的奖励最 大只有5，所以TASK_INTERACTIVE(p)永假）；当进程的nice值为-20时，进程的sleep_avg 必须非常小才可能使得TASK_INTERACTIVE(p)值为假。 从以上分析可以看出，这三种奖励办法一个比一个奖励力度大，奖励条件也一个比一 个苛刻。而且调度器将用户的意愿放在了第一位（因为nice值是可以通过系统调用改 变的），由于用户的意愿而给予的奖励（再次被插入active array）最大，而调度器 所给予的奖励占的比例并不大。 4. 调度器主函数schedule()（kernel/sched.c） schedule()是用来挑选出下一个应该执行的进程，并且完成进程切换的工作，是进程 调度的主要执行者，也是操作系统Kernel很重要的一个函数，它的性能将直接决定操 作系统的性能。 (1) 函数主要流程 两个重要数据：prev和next prev 当前进程，也就是即将被切换出CPU的进程 next 下一个进程，也就是即将被切换进CPU的进程 准备工作 a. 做原子操作方面的检查（主要是检查内核抢占和内核锁的深度是否一致）； b. 关闭内核抢占（通过函数preempt_disable()，详见"内核可抢占"一节），因为此 时将要对内核一系列重要数据进行操作，所以必须将内核抢占关闭； c. 将当前进程current赋值给prev，获取当前CPU的运行队列rq，释放prev的内核锁 （因为即将对prev做一系列操作），计算prev的运行时间（如果是交互进程则给予run_time 上的奖励，详见"interactive_credit"一节），给rq上自旋锁（防止其他进程访问rq ）； d. 进行内核的数据统计（如上下文切换次数等），如果prev处于可中断状态，而且 有信号等待处理，则将prev状态置为TASK_RUNNING，否则将prev从rq中删除。（这一 部分的代码主要是因为在进程在转入睡眠状态时，需要主动调用schedule()函数）； e. 如果rq中就绪进程个数为0，而且系统是SMP，则进行负载均衡的操作（详见"负载 均衡"一节），否则将next置为idle进程，赋值rq->expired_timestamp = 0（具体含 义参见"expired_timestamp"的介绍一节），然后直接进行进程切换。 寻找最高优先级进程 a. 如果rq的active array中进程个数为0，则将active array和expired array进行 切换。具体的过程由以下代码完成： array = rq->active; rq->active = rq->expired; rq->expired = array; rq->expired_timestamp = 0; rq->best_expired_prio = MAX_PRIO; b. 用函数sched_find_first_bit()找到优先级最高的进程队列的偏移量idx，那么queue [idx]->next即为所找的next，可以通过以下三行代码快速完成： idx = sched_find_first_bit(array->bitmap); queue = array->queue + idx; next = list_entry(queue->next, task_t, run_list); c. 如果next是从TASK_INTERRUPTIBLE状态中被唤醒的（actived>0），则将进程从就 绪队列中删除，将进程在就绪队列上的等待时间也加在等待时间里面重新计算进程的 prio（详见"平均等待时间"一节），再根据新的优先级将进程插入相应就绪队列。 进程切换 a. 如果prev!=next，则进行进程切换； b. 进行进程切换前的准备：将当前时间赋给next->timestamp，并且将rq->curr=next ；可见此时的rq->curr与current不再相同； c. 进程切换，包括内存、堆栈切换等。具体过程和Kernel 2.4大致相同，在这里不 再赘述； 完成进程切换后 完成进程切换过后，还需要进行释放prev的mm，给rq解锁，重新给current获得内核 锁（注意在此时current=next=rq->curr），使能内核抢占；最后检查TIF_NEED_RESCHED 位，如果已被置位，则重新开始进行调度，重复上述过程；否则调度结束。 (2) 函数执行时机 schedule()函数何时被调用，如何被调用也是一个非常重要的问题。 在Kernel 2.4里面，schedule()函数可以通过两种方式调用： 一种是主动调度，直接调用函数schedule()，如进程退出，或者进入睡眠状态等。 一种是强制性调度，置位当前进程task_struct里面的need_resched。当是从内核态 返回用户态的时候将检查这个位，如果发现已经被置位，会调用schedule()；有以下 三种情况可能会置位need_resched： a. 时钟中断服务程序中，发现进程已经用完自己的时间片，需要被切出CPU； b. 当唤醒一个睡眠进程时，发现该进程比当前占有CPU的进程更有运行资格； c. 一个进程通过系统调用改变调度政策、nice值等。 和主动调度相比，强制性调度有一定的调度延时。 Kernel2.6的调度时机包含了Kernel 2.4的调度时机（不同的就是need_resched变成 了一个bit）同时加入了一个重要的特性--内核可抢占，具体的分析见"内核可抢占" 一节。 5. 进程调度的生与死 这一部分分析了系统调度器开始工作的时机，以及一个进程从创建到灭亡过程中和进 程调度相关的信息和函数。 (1) 系统启动时进程调度的初始化 -- sched_init() 系统进程调度的初始化由sched_init()函数完成，它被init/main.c中函数start_kernel ()调用，该函数主要完成以下工作： a. 对于所有的CPU，完成runqueue的初始化工作； b. 对于SMP，要获取第一个进程的CPU号； c. 调用wake_up_forked_process()（参见下面"wake_up_forked_process"一节）来 唤醒当前进程； d. 初始化timer (2) 创建新进程时的调度信息改变 -- sched_fork(task_t *p) 当当前进程fork出一个新进程的时候，需要改变新进程的调度信息，该函数主要的调 用关系是：kenel/fork.c - do_fork()->copy_process->sched_fork()，函数主要完 成： |
