《嵌入式Linux内核开发教程之深入分析Linux内核源码-进程调度.ppt》由会员分享，可在线阅读，更多相关《嵌入式Linux内核开发教程之深入分析Linux内核源码-进程调度.ppt（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、嵌入式嵌入式LinuxLinux内核开内核开发发教程之深教程之深入分析入分析LinuxLinux内核源内核源码码进进程程调调度度(2)(2)Linux的调度程序Schedule()根本原理1时间片轮转调度算法2优先权调度算法3多级反响队列调度4实时调度3.2 Linux进程调度时机三个函数是如何协调工作的3.3 进程调度的依据3.4 进程可运行程度的衡量根本原理调度的实质就是资源的分配。系统通过不同的调度算法Scheduling Algorithm来实现这种资源的分配。通常来说，选择什么样的调度算法取决于的资源分配的策略Scheduling Policy，在这里只说明与Linux调度相关的几种
2、算法及这些算法的原理。一个好的调度算法应当考虑以下几个方面：1公平：保证每个进程得到合理的CPU时间。2高效：使CPU保持忙碌状态，即总是有进程在CPU上运行嵌入式嵌入式LinuxLinux内核开内核开发发教程之教程之LinuxLinux的的调调度程序度程序Schedule()Schedule()3响应时间：使交互用户的响应时间尽可能短。4周转时间：使批处理用户等待输出的时间尽可能短。5吞吐量：使单位时间内处理的进程数量尽可能多。很显然，这5个目标不可能同时到达，所以，不同的操作系统会在这几个方面中作出相应的取舍，从而确定自己的调度算法，例如UNIX采用动态优先数调度、BSD采用多级反响队列调
3、度、Windows采用抢先多任务调度等等。嵌入式嵌入式LinuxLinux内核开内核开发发教程教程下面来了解一下主要的调度算法及其根本原理：1时间片轮转调度算法时间片Time Slice就是分配给进程运行的一段时间。在通常的轮转法中，系统将所有的可运行即就绪进程按先来先效劳的原那么，排成一个队列，每次调度时把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，系统发出信号，通知调度程序，调度程序便据此信号来停止该进程的执行，并将它送到运行队列的末尾，等待下一次执行；然后，把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证运行队列中的所有进程，在一个给定
4、的时间内，均能获得一时间片的处理机执行时间。嵌入式嵌入式LinuxLinux内核开内核开发发教程之教程之1 1时时间间片片轮转调轮转调度算法度算法为了照顾到紧迫型进程在进入系统后便能获得优先处理，引入了最高优先权调度算法。当将该算法用于进程调度时，系统将把处理机分配给运行队列中优先权最高的进程，这时，又可进一步把该算法分成两种方式：(1)非抢占式优先权算法又称不可剥夺调度：Nonpreemptive Scheduling在这种方式下，系统一旦将处理机CPU分配给运行队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可将处理机分配给另一个优先权高
5、的进程。这种调度算法主要用于批处理系统中，也可用于某些对实时性要求不严的实时系统中。嵌入式嵌入式LinuxLinux内核开内核开发发教程之教程之2 2优优先先权调权调度算法度算法(2)抢占式优先权调度算法又称可剥夺调度：Preemptive Scheduling该算法的本质就是系统中当前运行的进程永远是可运行进程中优先权最高的那个。在采用这种调度算法时，每当出现一新的可运行进程，就将它和当前运行进程进行优先权比较，如果高于当前进程，将触发进程调度。这种方式的优先权调度算法，能更好的满足紧迫进程的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。Linux也采用这
6、种调度算法。嵌入式嵌入式LinuxLinux内核开内核开发发教程教程这是时下最时髦的一种调度算法。其本质是：综合了时间片轮转调度和抢占式优先权调度的优点，即：优先权高的进程先运行给定的时间片，相同优先权的进程轮流运行给定的时间片。嵌入式嵌入式LinuxLinux内核开内核开发发教程之教程之3 3多多级级反响反响队队列列调调度度最后我们来看一下实时系统中的调度。什么叫实时系统，就是系统对外部事件有求必应、尽快响应。在实时系统中，广泛采用抢占调度方式，特别是对于那些要求严格的实时系统。因为这种调度方式既具有较大的灵活性，又能获得很小的调度延迟；但是这种调度方式也比较复杂。嵌入式嵌入式LinuxLi
7、nux内核开内核开发发教程之教程之4 4实实时调时调度度Linux的调度程序是一个叫Schedule的函数，这个函数被调用的频率很高，由它来决定是否要进行进程的切换，如果要切换的话，切换到哪个进程等等。我们先来看在什么情况下要执行调度程序，我们把这种情况叫做调度时机。Linux调度时机主要有：1、进程状态转换的时刻：进程终止、进程睡眠；2、当前进程的时间片用完时current-counter=0；3、设备驱动程序主动调用schedule；嵌入式嵌入式LinuxLinux内核开内核开发发教程之教程之3.2 3.2 LinuxLinux进进程程调调度度时时机机4、进程从中断、异常及系统调用返回到用
8、户态时；时机1，进程要调用sleep或exit等函数进行状态转换，这些函数会主动调用调度程序进行进程调度；时机2，由于进程的时间片是由时钟中断来更新的，因此，这种情况和时机4是一样的。时机3，当设备驱动程序执行长而重复的任务时，直接调用调度程序。在每次反复循环中，驱动程序都检查need_resched的值，如果必要，那么调用调度程序schedule()主动放弃CPU。嵌入式嵌入式LinuxLinux内核开内核开发发教程教程时机4，如前所述，不管是从中断、异常还是系统调用返回，最终都调用ret_from_sys_call，由这个函数进行调度标志的检测，如果必要，那么调用调度程序。那么，为什么从系
9、统调用返回时要调用调度程序呢？这当然是从效率考虑。从系统调用返回意味着要离开内核态而返回到用户态，而状态的转换要花费一定的时间，因此，在返回到用户态前，系统把在内核态该处理的事全部做完。每个时钟中断timer interrupt发生时，由三个函数协同工作，共同完成进程的选择和切换，它们是：schedule、do_timer及ret_form_sys_call。我们先来解释一下这三个函数：嵌入式嵌入式LinuxLinux内核开内核开发发教程教程schedule：进程调度函数，由它来完成进程的选择调度；do_timer：暂且称之为时钟函数，该函数在时钟中断效劳程序中被调用，被调用的频率就是时钟中断
10、的频率即每秒钟100次简称100赫兹或100Hz；ret_from_sys_call：系统调用返回函数。当一个系统调用或中断完成时，该函数被调用，用于处理一些收尾工作，例如信号处理、核心任务等等。嵌入式嵌入式LinuxLinux内核开内核开发发教程教程前面我们看到，时钟中断是一个中断效劳程序，它的主要组成局部就是时钟函数do_timer，由这个函数完成系统时间的更新、进程时间片的更新等工作，更新后的进程时间片counter作为调度的主要依据。在时钟中断返回时，要调用函数ret_from_sys_call，前面我们已经讨论过这个函数，在这个函数中有如下几行：cmpl$0，_need_resche
11、djne reschedulerestore_all:RESTORE_ALL嵌入式嵌入式LinuxLinux内核开内核开发教程教程之之个函个函数是如何数是如何协调工作工作的的reschedule:call SYMBOL_NAME(schedule)jmp ret_from_sys_call这几行的意思很明显：检测 need_resched 标志，如果此标志为非0，那么就转到reschedule处调用调度程序schedule进行进程的选择。调度程序schedule会根据具体的标准在运行队列中选择下一个应该运行的进程。当从调度程序返回时，如果发现又有调度标志被设置，那么又调用调度程序，直到调度标志
12、为0，这时，从调度程序返回时由RESTORE_ALL恢复被选定进程的环境，返回到被选定进程的用户空间，使之得到运行。嵌入式嵌入式LinuxLinux内核开内核开发发教程教程Linux 调度程序和其他的UNIX调度程序不同，尤其是在“nice level优先级的处理上，与优先权调度priority高的进程最先运行不同，Linux用的是时间片轮转调度Round Robing，但同时又保证了高优先级的进程运行的既快、时间又长both sooner and longer。而标准的UNIX调度程序都用到了多级进程队列。大多数的实现都用到了二级优先队列：一个标准队列和一个实时“real time队列。一般
13、情况下，如果实时队列中的进程未被阻塞，它们都要在标准队列中的进程之前被执行，并且，每个队列中，“nice level高的进程先被执行。嵌入式嵌入式LinuxLinux内核开内核开发发教程教程调度程序运行时，要在所有处于可运行状态的进程之中选择最值得运行的进程投入运行。选择进程的依据是什么呢？在每个进程的task_struct结构中有这么五项：need_resched、nice、counter、policy 及rt_priorityneed_resched:在调度时机到来时，检测这个域的值，如果为1，那么调用schedule()。counter:进程处于运行状态时所剩余的时钟滴答数，每次时钟中断
14、到来时，这个值就减1。当这个域的值变得越来越小，直至为0时，就把need_resched 域置1，因此，也把这个域叫做进程的“动态优先级。嵌入式嵌入式LinuxLinux内核开内核开发发教程之教程之3.3 3.3 进进程程调调度的依据度的依据nice:进程的“静态优先级，这个域决定counter 的初值。只有通过nice()，sched_setparam()系统调用才能改变进程的静态优先级。rt_priority:实时进程的优先级policy:从整体上区分实时进程和普通进程，因为实时进程和普通进程的调度是不同的，它们两者之间，实时进程应该先于普通进程而运行，可以通过系统调用sched_sets
15、cheduler()来改变调度的策略。对于同一类型的不同进程，采用不同的标准来选择进程。对于普通进程，选择进程的主要依据为counter和nice。对于实时进程，Linux采用了两种调度策略，即FIFO先来先效劳调度和RR时间片轮转调度。因为实时进程具有一定程度的紧迫性，所以衡量一个实时进程是否应该运行，Linux采用了一个比较固定的标准。实时进程的counter只是用来表示该进程的剩余滴答数，并不作为衡量它是否值得运行的标准，这和普通进程是有区别的。嵌入式嵌入式LinuxLinux内核开内核开发发教程教程函数goodness就是用来衡量一个处于可运行状态的进程值得运行的程度。该函数综合使用了
16、上面我们提到的五项，给每个处于可运行状态的进程赋予一个权值weight，调度程序以这个权值作为选择进程的唯一依据。函数主体如下：static inline int goodness(struct task_struct*p,int this_cpu,struct mm_struct*this_mm)int weight;*权值，作为衡量进程是否运行的唯一依据*weight=-1;if(p-policy&SCHED_YIELD)嵌入式嵌入式LinuxLinux内核开内核开发发教程之教程之3.4 3.4 进进程可运行程度的衡量程可运行程度的衡量goto out;/*如果该进程愿意“礼让yield，
17、那么让其权值为1*switch(p-policy)/*实时进程*/case SCHED_FIFO:case SCHED_RR:weight=1000+p-rt_priority;/*普通进程*/case SCHED_OTHER:weight=p-counter;if(!weight)嵌入式嵌入式LinuxLinux内核开内核开发发教程教程goto out/*做细微的调整*/if(p-mm=this_mm|!p-mm)weight=weight+1;weight+=20-p-nice;/*在剩余counter一样的情况下，短进程优先*/out:return weight;/*返回权值*/嵌入式嵌
18、入式LinuxLinux内核开内核开发发教程教程其中，在中对调度策略定义如下：#define SCHED_OTHER 0#define SCHED_FIFO 1#define SCHED_RR 2#define SCHED_YIELD 0 x10这个函数比较很简单。首先，根据policy区分实时进程和普通进程。实时进程的权值取决于其实时优先级，其至少是1000，与conter和nice无关。普通进程的权值需特别说明两点：嵌入式嵌入式LinuxLinux内核开内核开发发教程教程为什么进行细微的调整？如果p-mm为空，那么意味着该进程无用户空间例如内核线程，那么无需切换到用户空间。如果p-mm=this_mm，那么说明该进程的用户空间就是当前进程的用户空间，该进程完全有可能再次得到运行。对于以上两种情况，都给其权值加1，算是对它们小小的奖励。进程的优先级nice是从早期Unix沿用下来的负向优先级，其数值标志“谦让的程度，其值越大，就表示其越“谦让，也就是优先级越低，其取值范围为2019，因此，20-p-nice的取值范围就是040。可以看出，普通进程的权值不仅考虑了其剩余的时间片，还考虑了其优先级，优先级越高，其权值越大。根据进程调度的依据，调度程序就可以控制系统中的所有处于可运行状态的进程并在它们之间进行选择。嵌入式嵌入式LinuxLinux内核开内核开发发教程教程