linux26调度优先级与时间片算法

linux 调度过程中调度优先级与时间片算法对象设计与描述： 动态优先级的计算主要 由 effect_prio() 函数完成， 该函数实现相当简单，从中可见 非实时进程的优先级 仅决定于静态优先级 （ static_prio）和进程的 sleep_avg 值两个因素 ，而实时进程的优先级实际上是在 setscheduler() 中设置的（详见“调度系统的实时性能 “，以下仅考虑非实时进程），且一经设定就不再改变。unsigned long sleep_avg进程的平均等待时间， 单位是纳秒（ nanosecond） ，在 0 NS_MAX_SLEEP_AVG 范围内。它的实质是进程等待时间和运行时间的差值。 当进程处于等待或者睡眠状态时，该值变大；当进程运行时，该值变小。上本次休眠时间 sleep_time 就达到了如果不是从 TASK_UNINTERRUPTIBLE 休眠中被唤醒的（ p-activated!=-1）sleep_avg 是进程的 “平均 “等待时间， recalc_task_prio() 计算了等待时间，如果不是从 TASK_UNINTERRUPTIBLE 休眠中被唤醒的（ p-activated!=-1）系统引入了一个 interactive_credit 的进程属性（见“改进后的 task_struct“），用来表征 该进程是否是交互式进程： 只要 interactive_credit 超过了 CREDIT_LIMIT 的阀值（HIGH_CREDIT()返回真）， 该进程就被认为是交互式进程。进程本次运行的时间 run_time交互式进程的 run_time 小于实际运行时间， sleep_avg 越大，则 run_time 减小得越多，因此被切换下来的进程最后计算所得的 sleep_avg 也就越大，动态优先级也随之变大。 交互式进程可以借此获得更多被执行的机会。run_time 可以用 系统当前时间与进程 timestamp（上一次被调度运行的时间） 的差值表示，但不能超过 NS_MAX_SLEEP_AVG用户进程 (p-mm!=NULL)等待得越久， sleep_avg 越大，进程越容易被调度到；而运行得越久， sleep_avg 越小，进程越不容易调度到。在 wake_up_forked_process() 中，父进程的 sleep_avg 要乘以 PARENT_PENALTY/100，而子进程的 sleep_avg 则乘以 CHILD_PENALTY/100。实际上 PARENT_PENALTY 为 100，CHILD_PENALTY 等于 95，也就是说父进程的 sleep_avg 不会变，而子进程从父进程处继承过来的 sleep_avg 会减小 5%，因此子进程最后的优先级会比父进程稍低（ 但子进程仍然会置于与父进程相同的就绪队列上，位置在父进程之前 -也就是 “前言 “所说 “子进程先于父进程运行“）。一个进程结束运行时，如果 它的交互程度比父进程低（ sleep_avg 较小） ，那么核心将在 sched_exit() 中对其父进程的 sleep_avg 进行调整 ，这表明 sleep_avg 可以表示交互度进程优先级 无论什么进程静态优先级固定，实时进程动态优先级也固定利用进程平均等待时间来衡量进程的优先级，使得宏观上相同静态优先级的所有进程的等待时间和运行时间的比值趋向一致，反映了 Linux 要求各进程分时共享 cpu 的公平性。另 一方面，sleep_avg 还是进程交互式程度的衡量标准。effective_prio()函数将进程的 sleep_avg 映射成范围是 -MAX_BONUS/2 MAX_BONUS/2 的变量bonus， 而 MAX_BONUS 是等于 ， 可见 sleep_avg 仅能影响的优先级范围在 -5 5 之间。具 体的映射是由以下规则完成的：那么进程的动态优先级就等于： （当然必须在 MAX_RT_PRIO 和MAX_PRIO-1 之间）。可见， sleep_avg 和 bonus 是一个线性关系。进程的 sleep_avg 越大，bonus 越大，从而进程的动态优先级也就越高。函数 recalc_task_prio ()先要根据进程被唤醒前的状态（即 actived）、 interactive_credit 等来计算进程的 sleep_avginteractive_credit 有两处增 1 的地方，都在函数 recalc_task_prio()里 面减少 interactive_credit 只有一处地方减 1，在函数 schedule()里面 。sleep_avg 给进程带来的动态优先级上的奖励最大只有 5时间片的计算： time_slice 完全只与 (p)-static_prio 有关进程的时间片 time_slice 是基于进程静态优先级的， 静态优先级越高（值越小），时间片就越大。 计算时间片是同过函数 task_timeslice()（kernel/sched.c）来完成的。该函数也是使用线性映射的方法，将进程优先级MAX_RT_PRIO, MAX_PRIO-1映射到时间片MIN_TIMESLICE, MAX_TIMESLICE范围内。通过优先级来计算时间片的等式为：timeslice = MIN_TIMESLICE + (MAX_TIMESLICE - MIN_TIMESLICE) *(MAX_PRIO-1- (p)-static_prio) / (MAX_USER_PRIO-1)effective_prio()函数返回进程 p 的动态优先级static int effective_prio(task_t *p)int bonus, prio;如果进程 p 是个实时进程，那么直接返回该实时进程的 prio(实时进程的动态优先级 prio 不依赖于静态优先级 static_prio， 两者是否相等?)|-| if (rt_task(p) | return p-prio; |-|计算红利 bonus:|-| bonus = CURRENT_BONUS(p) - MAX_BONUS / 2; | |-|根据如下公式计算该进程动态优先级 prio:与 static_prio， sleep_avg 有关prio = max ( 100, min(static_prio - bonus + 5, 139) )|-| prio = p-static_prio - bonus; | if (prio MAX_PRIO-1) | prio = MAX_PRIO-1; |-|return prio;A:优先级优先级由两部分构成， 一是静态优先级 static_prio，一是动态优先级 prio。 静态优先级在进程创建的时候就被赋值， 并且不变 （除非用系统调用改变进程的 nice 值） ；而进程的 动态优先级则是跟static_prio 和 sleep_avg 有关。 对于 实时进程的优先级 在创建的时候就确定了， 而且一旦确定以后就不再改变 ， 所以下面部分仅对于非实时进程而言。具体的计算由函数 effecitve_prio()（ kernel/sched.c）完成： sleep_avg函数将进程的 sleep_avg 映射成范围是-MAX_BONUS/2 - MAX_BONUS/2 的变量 bonus，而 MAX_BONUS是等于 10 ，可见 sleep_avg 仅能影响的优先级范围在-5 5 之间。sleep_avg 和 bonus 是一个线性关系。进程的 sleep_avg 越大，bonus 越大，从而进程的动态优先级也就越高。B:计算优先级： recalc_task_prio()来计算进程的 sleep_av计算进程的动态优先级一般调用两个函数，一个是 effective_prio()，一个是 recalc_task_prio()。函数 recalc_task_prio ()先要根据进程被唤醒前的状态（即 actived） 、interactive_credit 等来计算进程的 sleep_avg,在 最后调用 effective_prio()来计算函数的动态优先级 。总的来说，有以下几种情况需要计算进程的优先级：a. 创建新进程，使用函数 effective_prio()（因为此时进程尚未进行调度，没有 sleep_avg 和interactive_credit 可言） ；b. 唤醒等待进程时，使用函数 recalc_task_prio ()来计算进程动态优先级。c. 进程用完时间片以后，被重新插入到 active array 或者 expired array 的时候需要重新计算动态优先级，以便将进程插入到队列的相应位置。此时，使用函数 effective_prio()；d. 其他情况，如 IDLE 进程初始化等时候。(2) 进程时间片A:时间片的计算：仅有普通进程要计算进程的时间片 time_slice 是基于进程静态优先级的，静态优先级越高 （值越小），时间片就越大。计算时间片是同过函数 task_timeslice()（kernel/sched.c）来完成的。该函数也是使用线性映射的方法，将进程优先级MAX_ RT_PRIO, MAX_PRIO-1（这个优先级区间静态优先级是普通进程的 ）映射到时间片MIN_TIMESLICE, MAX_TIMESLICE范围内。通过优先级来计算时间片的等式为：timeslice = MIN_TIMESLICE + (MAX_TIMESLICE - MIN_TIMESLICE) *(MAX_PRIO-1- (p)-static_prio) / (MAX_USER_PRIO-1)B:计算时间片在 Linux 2.6 中时间片的计算是分散的，具体的计算既可以用 task_timeslice()，也可以用其他方法。a. 进程创建时，将父进程的时间片分一半给子进程， 同时父进程的时间片减半。b. 进程用完时间片以后 ， 需要重新计算时间片 ，并将进程插入到相应的运行队列。c. 进程退出时， 根据 first_timeslice 的值来决定是否将子进程的时间片返还给父进程。(3) 平均等待时间 sleep_avg平均等待时间 sleep_avg 决定了进程优先级， 并且影响进程交互程度A:进程创建当一个进程被创建的时候，父进程的 sleep_avg 要乘以“PARENT_PENALTY / 100“，子进程的sleep_avg 要乘以“CHILD_PENALTY / 100“，PARENT_PENALTY=100，而 CHILD_PENALTY = 95，可见创建 以后子进程的 sleep_avg 要降低，而父进程则不变。B:进程被唤醒当一个进程被唤醒以后，acitvate_task()将调用函数 recalc_task_prio()来计算进程的sleep_avg， 参数是进程的睡眠时间，从而进一步计算进程的动态优先级。计算 sleep_avg 有以下几种可能:a. MAX_SLEEP_AVG - AVG_TIMESLICE当用户进程（p-mm）不是由 UNINTERRUPTIBLE 状态唤醒（p-activated != -1） ，且睡眠时间大于INTERACTIVE_SLEEP(p)，则做此赋值；b. 不变当用户进程（p-mm）是由 UNINTERRUPTIBLE 状态唤醒（p-activated = -1） ，且“交互程度“不高（!HIGH_CREDIT(p)） ，如果原来的 sleep_avg 已经大于 INTERACTIVE_SLEEP(p)，则不变（对非自愿睡眠的进程进行惩罚） ； 否则见下面一条；c. INTERACTIVE_SLEEP(p)如果加上此次的睡眠时间后大于 INTERACTIVE_SLEEP(p)，则sleep_avg 赋值为 INTERACTIVE_SLEEP(p)；d. sleep_avg+sleep_time如果以上条件全都不满足，则直接将本次睡眠时间加到 sleep_avg 上。C:进程调度过程中在 schedule()过程中，如果发现优先级最高的程序是刚刚从 TASK_INTERRUPTIBLE 状态被唤醒的进程，那么将调用 recalc_task_prio()，运算过程与(2)相同，所不同的就是调用时的参数sleep_time 是进程在就绪队列的等待时间。如果进程不是被中断唤醒的（actived=1） ，那么sleep_time 还将受到“(ON_RUNQUEUE_WEIGHT * 128 / 100) / 128“的限制，因为该进程很可能不是交互式进程。D:进程被剥夺 CPU 使用权当进行进程切换的时候，被剥夺 CPU 使用权的进程的 sleep_avg 将会被减去进程的运行时间run_time，从而保证调度器的公平性。进程运行的时间越长，sleep_avg 就越小（底限是 0） ，进程的动态优先级也就越低，从而被调度器调度到的机会也就会越小。E:进程退出当一个进程退出时，如果该进程的 sleep_avg 比父进程要小（也就是运行时间长） ，那么父进程将得到惩罚。具体惩罚的规则为：p-parent-sleep_avg = p-parent-sleep_avg / (EXIT_WEIGHT+1) * EXIT_WEIGHT+ p-sleep_avg / (EXIT_WEIGHT + 1);父进程的 sleep_avg 将变为原来的 1/( EXIT_WEIGHT+1)，再加上子进程的 sleep_avg 的1/( EXIT_WEIGHT+1)，可见子进程运行的越多，父进程得到的惩罚也就越大。这样也是为了保证调度器的公正性。2) 优先级计算时机优先级的计算不再集中在调度器选择候选进程的时候进行了，只要进程状态发生改变，核心就有可能计算并设置进程的动态优先级：a) 创建进程 在 wake_up_forked_process()中，子进程继承了父进程的动态优先级，并添加到父进程所在的就绪队列中。如果父进程不在任何就绪队列中（例如它是 IDLE 进程）， 那么就通过 effect_prio() 函数计算出子进程的优先级，而后根据计算结果将子进程放置到相应的就绪队列中。b) 唤醒 休眠进程 ： TASK_