操作系统教程ch2-2.7Linux.ppt

2.7Linux调度算法

2.7.1Linuxv2.4调度算法2.7.2Linuxv2.6调度算法2.4.1Linuxv2.4调度算法(1)

1进程调度策略1)policy：SCHED_OTHER普通类任务SCHED_FIFO先进先出实时类任务SCHED_RR轮转法实时类任务2)priority进程静态优先级3)nice进程可控优先级因子4)rt_priority实时进程静态优先级5)counter进程目前时间片配额，也称进程动态优先级Linuxv2.4调度算法(2)

2动态优先级的产生和变化当counter递减到0时，运行进程被迫出让CPU；当可运行队列中所有进程的counter值变为0后，表明一轮调度已经结束。等待态进程的动态优先级通常会逐渐增加，当所有可运行进程的counter都为0时，系统重新计算所有进程的counter，计算公式为：p-counter=(p-counter1)+NICE_TO_TICKS(P-nice)对于就绪态进程来说，因其counter都为0，计算结果就是nice转换过来的时钟滴答数；对于等待态进程就不一样，它们的counter都不为0，计算结束后，等待态进程的动态优先级会大于nice值。3Linuxv2.4进程调度机制进程调度依据和时机进程调度任务进程切换Linuxv2.4进程切换时机

(1)进程被动放弃CPU，当前进程时间片用完或当一个进程被唤醒，且其优先级高于当前进程的优先级时，通过TIF_NEED_RESCHED位置1，来告诉内核在适当的时刻需要重新调度。(2)进程主动放弃CPU，由于进程执行系统调用，状态发生变化，直接调用schedule()进入调度，这类系统调用有：yield()、pause()、sleep()、wait()和exit()。(3)进程执行等待系统调用，如read()或write()等，此时进程进入等待队列，系统调用schedule()进入调度，该函数的执行结果往往是当前进程放弃处理器。Linuxv2.4进程调度任务(1)(1)处理软中断服务请求，如果有则先执行这些请求。(2)处理当前进程：1)如果当前进程的调度策略为SCHED_RR且counter=0，则保持运行状态(TASK_RUNNING)，并把它移入可运行队列尾部，适当时刻counter被重新赋值。2)如果当前进程是可中断(TASK_INTERRUPTIBLE)的，且信号已经到达，则把它的状态修改为TASK_RUNNING，移入可运行队列尾部。3)把当前既非运行状态、又非可中断状态的进程从可运行队列中移出，这些进程暂无资格被调度，并把当前进程描述符的TIF_NEED_RESCHED标志清为0。Linuxv2.4进程调度任务(2)(3)选择进程运行·执行goodness()函数，最终最大的权值weight保存在变量c中，表示进程值得运行的程度；用变量next指向调度后要运行的进程；weight=counter+20-nice;c=weight;·如果c是0，表明所有可运行进程的时间片耗尽，应重新计算进程的时间片，对counter重新赋值，再次转向执行goodness()函数。·如果next就是当前进程，则结束调度工作，让当前进程返回运行；否则，进行进程切换，CPU改由next进程占有。Linuxv2.4进程调度任务(3)goodness()函数的参数是待查进程的描述符，返回值c反映待查进程值得运行的程度，C的取值范围如下：c=-1000，不必选择待查进程，当可运行队列里仅有一个进程时，c为该值。c=0，待查进程时间片用完，在其他进程的时间片耗尽之前不会选择它。0c1000，待查进程的时间片还未用完，剩余时间片可看作动态优先级。c1000，待查进程是实时进程，应该优先运行。如果该进程为实时进程，它的权值为1000+rt_priority，这是普通进程无法达到的权值，能保证实时进程总比普通进程优先运行。对于普通进程，它的权值为counter+20-nice，如果它又是内核线程，由于无须切换到用户空间，则将权值加1作为奖励。Linuxv2.4进程切换

上下文切换是从一个可运行进程切换到另一个可运行进程，由context_switch（）函数处理这项工作，每当一个新的进程被选出来准备投入运行时，schedule（）就会调用该函数。