Linux-6调度优先级与时间片算法

1、linux调度过程中调度优先级与时间片算法对象设计与描述:动态优先级的计算主要 由effect_prio()函数完成，该函数实现相当简单， 从中可见非实时进程的优先级仅决定于静态优先级 (static_prio )和进程的sleep_avg值两个因素，而 实时进程的优先级实际上是在 setscheduler() 中设置的(详见"调度系统的实时性能 ; 以下仅考虑非实时进程)，且一经设定就不再改变。unsigned long sleep_avg进程的平均等待时间，单位是纳秒(nanosecond ),在 0 NS_MAX_SLEEP_AVG范围内。它的实质是进程等待时间和运行时间的差值

2、。当进程处于等待或者睡眠状态时，该值变大；当进程运行时，该值变小。上本次休眠时间sleep_time 就达到了如果不是从 TASK_UNINTERRUPTIBLE休眠中被唤醒的(p->activated!=-1 )sleep_avg是进程的"平均"等待时间，recalc_task_prio() 计算了等待时间， 如果不是从TASK_UNINTERRUPT旧LE眠中被唤醒的(p->activated!=-1 )系统引入了一个 interactive_credit的进程属性(见"改进后的task_struct"),用来表征该进程是否是交互式进程：

3、只要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

4、等待得越久，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% ,因此子进程最后的优先级会比父进程稍低(但子进程仍然会置于与父进程相同的就绪

5、队列上，位置在父进程之前-也就是"前言"所说”子进程先于父进程运行")。一个进程结束运行时，如果 它的交互程度比父进程低(sleep_avg较小)，那么核心将在 sched_exit()中对其父进程的 sleep_avg 进行调整，这表明sleep_avg可以表示交互度进程优先级无论什么进程静态优先级固定，实时进程动态优先级也固定利用进程平均等待时间来衡量进程的优先级，使得宏观上相同静态优先级的所有进程的等待时间和运行时间的比值趋向一致，反映了 Linux 要求各进程分时共享cpu的公平性。另一方面，sleep_avg还是进程交互式程度的衡量标准。effectiv

6、e_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 ) 、 interac

7、tive_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 )来完成的。该函

8、数也是使用线性映射的方法，将进程优先级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;如

9、果进程p是个实时进程，那么直接返回该实时进程的prio (实时进程的动态优先级prio不依赖于静态优先级static_prio ,两者是否相等?)I1I if (rt_task(p)| return p->prio;|I1计算红利bonus:I1| bonus = CURRENT_BONUS( p ) - MAX_BONUS / 2; |I1prio = max ( 100, min(根据如下公式计算该进程动态优先级prio:与static_prio , sleep_avg 有关static_prio - bonus + 5, 139)| prio = p->static_prio

10、 - bonus;| if (prio < MAX_RT_PRIO)| prio = MAX_RT_PRIO;| if (prio > MAX_PRIO-1)| prio = MAX_PRIO-1;|return prio;A:优先级优先级由两部分构成，一是静态优先级static_prio , 一是动态优先级prio。静态优先级在进程创建的时候就被赋值，并且不变(除非用系统调用改变进程的nice值)；而进程的动态优先级则是跟static_prio 和sleep_avg有关。对于实时进程的优先级在创建的时候就确 定了，而且一旦确定以后就不再改变，所以下面部分仅对于非实时进程而言。具体

11、的计算由函数 effecitve_prio() (kernel/sched.c )完成：sleep_avg函数将进程的 sleep_avg映射成范围是-MAX_BONUS/2 -MAX_BONUS/的变量bonus,而MAX_BONUS等于10 ,可见sleep_avg仅能影响的优先级范围在 -5 5之间。sleep_avg和bonus是一个线性关系。进程的 sleep_avg越大，bonus越大，从而进程的动 态优先级也就越高。B:计算优先级：recalc_task_prio()来计算进程的sleep_av计算进程的动态优先级一般调用两个函数，一个是effective_prio() , 一个

12、是 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. 进程用完时间片以后，被重

13、新插入到active array或者expired array的时候需要重新计算动态优先级，以便将进程插入到队列的相应位置。此时，使用函数 effective_prio() ;d.其他情况，如IDLE进程初始化等时候。(2)进程时间片A:时间片的计算：仅有普通进程要计算进程的时间片time_slice 是基于进程静态优先级的，静态优先级越高(值越小)，时间片就越大。计算时间片是同过函数task_timeslice() (kernel/sched.c )来完成的。该函数也是使用线性映射的方法，将进程优先级MAX_RT_PRIO, MAXFRIO-1(这个优先级区间静态优先级是普通进程的)映射到时

14、间片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.进程用完时间片以后，需要重新计算时间片，并将进程插入到相应的运行队

15、列。c.进程退出时，根据first_timeslice的值来决定是否将子进程的时间片返还给父进程。平均等待时间 sleep_avg平均等待时间sleep_avg决定了进程优先级，并且影响进程交互程度 A:进程创建当一个进程被创建的时候， 父进程的sleep_avg要乘以"PARENT_PENALTY/ 100",子进程 的 sleep_avg 要乘以"CHILD_PENALTY / 100" , PARENT_PENALTY=100 而 CHILD_PENALTY = 95,可见创建 以后子进程的sleep_avg要降低，而父进程则不变。B:进程被唤醒当

16、一个进程被唤醒以后，acitvate_task()将调用函数recalc_task_prio()来计算进程的sleep_avg,参数是进程的睡眠时间，从而进一步计算进程的动态优先级。计算sleep_avg有以下几种可能：a. MAX_SLEEP_AVG AVG_TIMESLICE当用户进程(p->mm 不是由 UNINTERRUPTIBLE醒(p->activated != -1 ),且睡眠 时间大于INTERACTIVE_SLEEP(p)贝U做此赋值；b. 不变当用户进程(p->mni)是由 UNINTERRUPTIBLE醒(p->activated = -1),且“

17、交互 程度”不高(！HIGH_CREDIT(p),如果原来的 sleep_avg 已经大于 INTERACTIVE_SLEEP(p) 则不变(对非自愿睡眠的进程进行惩罚)； 否则见下面一条；c. INTERACTIVE_SLEEP(p如果力口上此次的睡眠时间后大于INTERACTIVE_SLEEP(p)贝U sleep_avg 赋值为 INTERACTIVE_SLEEP(p)d. sleep_avg+sleep_time如果以上条件全都不满足，则直接将本次睡眠时间加到sleep_avg上。C:进程调度过程中在schedule()过程中，如果发现优先级最高的程序是刚刚从TASK_INTERRUP

18、T旧LE态被唤醒的进程，那么将调用recalc_task_prio() ,运算过程与(2)相同，所不同的就是调用时的参数sleep_time是进程在就绪队列的等待时间。如果进程不是被中断唤醒的(actived=1 ),那么 sleep_time 还将受到"(ON_RUNQUEUE_WEIGHT 128 /100) /128”的限制，因为该进程很可能不是交互式进程。D:进程被剥夺CPUt用权当进行进程切换的时候，被剥夺CPUf用权的进程的sleep_avg将会被减去进程的运行时间 run_time，从而保证调度器的公平性。进程运行的时间越长，sleep_avg就越小(底限是0),进程的

19、动态优先级也就越低，从而被调度器调度到的机会也就会越小。E:进程退出当一个进程退出时，如果该进程的sleep_avg比父进程要小(也就是运行时间长)，那么父进程将得到惩罚。具体惩罚的规则为：p->parent->sleep_avg = p->parent->sleep_avg / (EXIT_WEIGHT+1) * EXIT_WEIG HT+ p->sleep_avg / (EXIT_WEIGHT + 1);父进程的sleep_avg 将变为原来的1/( EXIT_WEIGHT+1)再加上子进程的 sleep_avg的 1/( EXIT_WEIGHT+1)可见子进

20、程运行的越多，父进程得到的惩罚也就越大。这样也是为 了保证调度器的公正性。2)优先级计算时机优先级的计算不再集中在调度器选择候选进程的时候进行了，只要进程状态发生改变，核心就有可能计算并设置进程的动态优先级：a)创建进程在wake_up_forked_process()中，子进程继承了父进程的动态优先级，并添加到父进程所 在的就绪队列中。如果父进程不在任何就绪队列中(例如它是IDLE进程)，那么就通过effect_prio() 函数计算出子进程的优先级，而后根据计算结果将子进程放置到相应的就绪队列中。b)唤醒休眠进程：TASK_KILLABLE休眠进程被唤醒时(activate_task() 调用r