Linux操作系统分析13_scheduling.ppt

Linux内核源代码导读内核源代码导读 中国科学技术大学计算机系中国科学技术大学计算机系陈香兰（陈香兰（05513606864）Spring 2009进程调度进程调度v调度策略v调度算法12/22/20222Linux内核源代码导读内核源代码导读进程的分类进程的分类v不同类型的进程有不同的调度需求v第一种分类：第一种分类：I/O-boundl频繁的进行I/Ol通常会花费很多时间等待I/O操作的完成CPU-boundl计算密集型l需要大量的CPU时间进行运算12/22/20223Linux内核源代码导读内核源代码导读v第二种分类交互式进程（interactive process）l需要经常与用户交互，因此要花很多时间等待用户输入操作l响应时间要快，平均延迟要低于50150msl典型的交互式程序：shell、文本编辑程序、图形应用程序等12/22/20224Linux内核源代码导读内核源代码导读批处理进程（batch process）l不必与用户交互，通常在后台运行l不必很快响应l典型的批处理程序：编译程序、科学计算实时进程（real-time process）l有实时需求，不应被低优先级的进程阻塞l响应时间要短l典型的实时进程：视频/音频、机械控制等12/22/20225Linux内核源代码导读内核源代码导读Linux中的进程调度中的进程调度vLinux既支持普通的分时进程，也支持实时进程vLinux中的调度是多种调度策略和调度算法的混合。v什么是调度策略？是一组规则，它们决定什么时候以怎样的方式选择一个新进程运行vLinux的调度基于分时和优先级随着版本的变化，分时技术在不断变化优先级越来越复杂12/22/20226Linux内核源代码导读内核源代码导读vLinux的进程根据优先级排队根据特定的算法计算出进程的优先级，用一个值表示这个值表示把进程如何适当的分配给CPUvLinux中进程的优先级是动态的调度程序会根据进程的行为周期性的调整进程的优先级l较长时间未分配到CPU的进程，通常l已经在CPU上运行了较长时间的进程，通常12/22/20227Linux内核源代码导读内核源代码导读与调度相关的系统调用与调度相关的系统调用vnicevgetpriority/setpriorityvsched_getscheduler/sched_setschedulervsched_getparam/sched_setparamvsched_yieldvsched_get_priority_min/sched_get_priority_maxvsched_rr_get_interval12/22/20228Linux内核源代码导读内核源代码导读调度算法调度算法vLinux 2.4的调度算法需要遍历可运行队列，算法O(n)Epoch，基本时间片，动态优先级vLinux 2.6.17的调度算法（2.6.23之前）采用双队列（Active；expire），按照优先级组队，O(1)vLinux 2.6.26的调度算法非实时：CFS，vruntime，红黑树实时：优先级队列vLinux进程可以指定该进程所采用的调度策略v调度算法根据进程的调度策略，采用不同的调度算法12/22/20229Linux内核源代码导读内核源代码导读Linux 2.6.26中的中的调度策略：调度策略：Policy，调度类型，调度类型在在task_struct中，使用数据项中，使用数据项policy来表达该进程采用的调度策略来表达该进程采用的调度策略12/22/202210Linux内核源代码导读内核源代码导读查看各个查看各个policy的使用情况的使用情况12/22/202211Linux内核源代码导读内核源代码导读12/22/202212Linux内核源代码导读内核源代码导读调度类型调度类型v阅读const struct sched_class，调度类rt_sched_classfair_sched_classidle_sched_classrt_sched_classfair_sched_classidle_sched_class关于调度的描述，关于调度的描述，参见参见sched_coding.txt和和sched-design-CFS.txt12/22/202213Linux内核源代码导读内核源代码导读调度类接口举例调度类接口举例v找到主要与运行队列有关的enqueue_task、dequeue_taskvIdle相关：idle_sched_classno enqueue/yield_task for idle tasksdequeue_task_idlevFair相关enqueue_task_fairdequeue_task_fairvRt相关enqueue_task_rtdequeue_task_rt12/22/202214Linux内核源代码导读内核源代码导读接口关系接口关系12/22/202215Linux内核源代码导读内核源代码导读12/22/202216Linux内核源代码导读内核源代码导读Idle类特殊类特殊12/22/202217Linux内核源代码导读内核源代码导读Fair类类进而查看进而查看1）enqueue_entity2）_enqueue_entity（红黑树）（红黑树）3）sched_entity结构结构4）struct rq5）struct cfs_rqCompletely Fair Scheduler 完全公平调度完全公平调度12/22/202218Linux内核源代码导读内核源代码导读Rt类类进而查看：进而查看：1）enqueue_rt_entity2）_enqueue_rt_entity每个每个cpu有一个队列有一个队列3）sched_rt_entity4）struct rq5）struct rt_rq6）struct rt_prio_array优先级队列优先级队列12/22/202219Linux内核源代码导读内核源代码导读v激活一个任务activate_task相对的：相对的：deactivate_task12/22/202220Linux内核源代码导读内核源代码导读TASK_RUNNING状态的进程组织状态的进程组织v每个每个cpu有一个运行队列有一个运行队列v非实时任务和实时任务各有一个子队列12/22/202221Linux内核源代码导读内核源代码导读运行队列数据结构运行队列数据结构12/22/202222Linux内核源代码导读内核源代码导读vstruct cfs_rq红黑树红黑树12/22/202223Linux内核源代码导读内核源代码导读vstruct rt_rq基于优先级的运行队列基于优先级的运行队列12/22/202224Linux内核源代码导读内核源代码导读调度实体调度实体v公平调度实体：sched_entity3部分，其中调度统计和组公平调度的不看12/22/202225Linux内核源代码导读内核源代码导读v实时调度实体sched_rt_entity其中组实时调度信息不看12/22/202226Linux内核源代码导读内核源代码导读阅读阅读2.6.26的的schedule函数函数v调度函数的关键：v 调度算法的关键入列lCFS根据vruntime的值入列，其关键在于vruntime值的计算lRT根据优先级入列12/22/202227Linux内核源代码导读内核源代码导读CFS算法算法v就绪队列的组织：红黑树v进程在红黑树中的键值的调整v阅读入列操作enqueue_entity12/22/202228Linux内核源代码导读内核源代码导读Linux2.6.26中的优先级范围中的优先级范围优先数范围为优先数范围为0139，其中，其中099为实时优先数为实时优先数普通任务和批处理任务的优先数在普通任务和批处理任务的优先数在100139之间之间优先数越大，优先级越低。优先数越大，优先级越低。12/22/202229Linux内核源代码导读内核源代码导读Linux2.6.26中的中的nice值值vNice值用来调整进程的优先级vNice值的范围在-2019之间。12/22/202230Linux内核源代码导读内核源代码导读Linux2.6.26中的中的USER_PRIO12/22/202231Linux内核源代码导读内核源代码导读CFS进程的优先级进程的优先级vprio：当前有效优先级vstatic_prio：根据nice设置vnormal_prio：常规优先级vInit_task12/22/202232Linux内核源代码导读内核源代码导读v在fork时，根据sched_forkv在wake_up_new_task时，v在rt_mutex_setprio时，设置任务的当前优先级12/22/202233Linux内核源代码导读内核源代码导读v在set_user_nice时，v在_setscheduler中，v在init_idle中12/22/202234Linux内核源代码导读内核源代码导读12/22/202235Linux内核源代码导读内核源代码导读schedule_tickv被时钟中断按照滴答时间单位在关中断状态下调用v在fork中，随着父进程时间片的变化，也会被调用v调度时钟的稳定性由配置参数CONFIG_HAVE_UNSTABLE_SCHED_CLOCK来确定v假定是稳定的12/22/202236Linux内核源代码导读内核源代码导读scheduler_ticksched_clock_tick（空函数）（空函数）update_rq_clock获得就绪队列的当前获得就绪队列的当前时钟值。时钟值。参见源代码参见源代码update_cpu_load统计统计CPU负载信息负载信息当前任务所在当前任务所在调度类型的调度类型的task_tick方法方法例如例如task_tick_fairentity_tickupdate_curr12/22/202237Linux内核源代码导读内核源代码导读ThanksThanks！The end.以下内容作为参考：以下内容作为参考：2.4的调度算法的调度算法vepochlinux调度算法把CPU时间划分为时期（epoch）在一个单独的时期内，每个进程有一个指定的时间片l一个进程用完它的时间片时，就会被强占l只要进程的时间片没有用完，就可以被多次调度运行当所有的进程用完它的时间片的时候，一个时期才结束，此时要重新计算所有进程的时间片，并重新开始一个新的时期12/22/202239Linux内核源代码导读内核源代码导读v基本时间片（base time quantum）每个进程有一个基本时间片可以通过nice、setpriority系统调用调整进程的基本时间片新进程总是继承父进程的基本时间片时间片的计算公式：nice缺省为0（在-20到19之间选择）通常，基本时间片的值 为6，由于时钟中断大约10ms左右，因此基本时间片的长度大约60ms12/22/202240Linux内核源代码导读内核源代码导读2.4调度程序使用的数据结构调度程序使用的数据结构v进程描述符中：need_resched：是否需要调度policy：调度策略先入先出的实时进程循环轮转的实时进程普通的分时进程当一个进程自动放弃运行时设置12/22/202241Linux内核源代码导读内核源代码导读rt_priority：实时进程的静态优先级，普通进程不用counter：当前剩余时间片l新时期开始时根据上述计算公式计算l每次时钟中断发生，时间片都会-1，直到为0（则请求调度）l创建一个新的进程时，子进程会继承父进程的一半剩余时间片vnice：对时间片进行调节12/22/202242Linux内核源代码导读内核源代码导读schedule函数函数vschedule函数实现调度v目的：在运行队列中找到一个进程，把CPU分配给它v调用方法：直接调用，如sleep_on松散调用，根据need_resched标记阅读schedule函数，了解如何区分实时和非实时进程12/22/202243Linux内核源代码导读内核源代码导读2.4调度算法的性能调度算法的性能v不适合进程数量很大的情况重新计算所有进程的动态优先级很耗时v对高负载系统来说，预定义的时间片太长v对于I/O密集型的程序不是很有利v对实时应用的支持是微弱的12/22/202244Linux内核源代码导读内核源代码导读2.6.17中的优先级队列中的优先级队列v优先级队列的组织双队列：active和expired12/22/202245Linux内核源代码导读内核源代码导读