Linux操作系统分析4.3_scheduling.ppt

Linux操作系统操作系统分析分析陈香兰陈香兰Fall 2010进进程程调调度度调度策略调度算法1/2/20232Linux操作系统分析操作系统分析进进程的分程的分类类不同类型的进程有不同的调度需求第一种分第一种分类类：I/O-bound频繁的进行I/O通常会花费很多时间等待I/O操作的完成CPU-bound计算密集型需要大量的CPU时间进行运算1/2/20233Linux操作系统分析操作系统分析第二种分类交互式进程（interactive process）需要经常与用户交互，因此要花很多时间等待用户输入操作响应时间要快，平均延迟要低于50150ms典型的交互式程序：shell、文本编辑程序、图形应用程序等1/2/20234Linux操作系统分析操作系统分析批处理进程（batch process）不必与用户交互，通常在后台运行不必很快响应典型的批处理程序：编译程序、科学计算实时进程（real-time process）有实时需求，不应被低优先级的进程阻塞响应时间要短典型的实时进程：视频/音频、机械控制等1/2/20235Linux操作系统分析操作系统分析Linux中的中的进进程程调调度度Linux既支持普通的分时进程，也支持实时进程Linux中的调度是多种调度策略和调度算法的混合。什么是调度策略？是一组规则，它们决定什么时候以怎样的方式选择一个新进程运行Linux的调度基于分时和优先级随着版本的变化，分时技术在不断变化1/2/20236Linux操作系统分析操作系统分析Linux的进程根据优先级排队根据特定的算法计算出进程的优先级，用一个值表示这个值表示把进程如何适当的分配给CPULinux中进程的优先级是动态的调度程序会根据进程的行为周期性的调整进程的优先级较长时间未分配到CPU的进程，通常已经在CPU上运行了较长时间的进程，通常1/2/20237Linux操作系统分析操作系统分析与与调调度相关的系度相关的系统调统调用用nicegetpriority/setprioritysched_getscheduler/sched_setschedulersched_getparam/sched_setparamsched_yieldsched_get_priority_min/sched_get_priority_maxsched_rr_get_interval1/2/20238Linux操作系统分析操作系统分析采用常采用常规规分分时时时时，时间时间片片的的选择选择时间片的长短对系统性能非常关键，它既不能太长也不能太短太短：频繁的切换会造成系统开销过大假如切换时间为1ms，时间片设置为1ms，那就没空执行进程了1/2/20239Linux操作系统分析操作系统分析太长几乎每个进程都一次运行完并发的概念基本消失普通进程需要等待很长时间才能运行时间片大小的选择总是一种折衷。Linux采取单凭经验的方法，即选择尽可能长的时间片，同时能保持良好的响应时间1/2/202310Linux操作系统分析操作系统分析调调度算法度算法Linux 2.4的调度算法需要遍历可运行队列，算法O(n)Epoch，基本时间片，动态优先级Linux 2.6.17的调度算法（2.6.23之前）采用双队列（Active；expire），按照优先级组队，O(1)Linux 2.6.26的调度算法非实时：CFS，vruntime，红黑树实时：优先级队列Linux进程可以指定该进程所采用的调度策略调度算法根据进程的调度策略，采用不同的调度算法1/2/202311Linux操作系统分析操作系统分析Linux 2.6.26中的中的调调度策略：度策略：Policy，调调度度类类型型include/linux/sched.h在在task_struct中，使用数据项中，使用数据项policy来表达该进程采用的调度策略来表达该进程采用的调度策略1/2/202312Linux操作系统分析操作系统分析查查看各个看各个policy的使用情况的使用情况1/2/202313Linux操作系统分析操作系统分析kernel/sched.c1/2/202314Linux操作系统分析操作系统分析调调度度类类型型阅读const struct sched_class，调度类rt_sched_classfair_sched_classidle_sched_classrt_sched_classfair_sched_classidle_sched_classkernel/sched_idletask.ckernel/sched_fair.ckernel/sched_rt.c1/2/202315Linux操作系统分析操作系统分析阅读阅读2.6.26的的schedule函数函数调度函数的关键：调度算法的关键入列入列CFS根据vruntime的值入列，其关键在于vruntime值的计算RT根据优先级入列kernel/sched.c，参见函数schedule()kernel/sched_fair.c，update_curr1/2/202316Linux操作系统分析操作系统分析Linux2.6.26中的中的优优先先级级优先数范围为优先数范围为0139，其中，其中099为实时优先数为实时优先数普通任务和批处理任务的优先数在普通任务和批处理任务的优先数在100139之间之间优先数越大，优先级越低优先数越大，优先级越低。1/2/202317Linux操作系统分析操作系统分析Linux2.6.26中的中的nice值值Nice值用来调整进程的优先级Nice值的范围在-2019之间。1/2/202318Linux操作系统分析操作系统分析ThanksThanks！The end.以下内容作以下内容作为为参考：参考：2.4的的调调度算法度算法epochlinux调度算法把CPU时间划分为时期（epoch）在一个单独的时期内，每个进程有一个指定的时间片一个进程用完它的时间片时，就会被强占只要进程的时间片没有用完，就可以被多次调度运行当所有的进程用完它的时间片的时候，一个时期才结束，此时要重新计算所有进程的时间片，并重新开始一个新的时期1/2/202320Linux操作系统分析操作系统分析基本时间片（base time quantum）每个进程有一个基本时间片可以通过nice、setpriority系统调用调整进程的基本时间片新进程总是继承父进程的基本时间片时间片的计算公式：nice缺省为0（在-20到19之间选择）通常，基本时间片的值 为6，由于时钟中断大约10ms左右，因此基本时间片的长度大约60ms1/2/202321Linux操作系统分析操作系统分析2.4调调度程序使用的数据度程序使用的数据结结构构进程描述符中：need_resched：是否需要调度policy：调度策略先入先出的实时进程循环轮转的实时进程普通的分时进程当一个进程自动放弃运行时设置1/2/202322Linux操作系统分析操作系统分析rt_priority：实时进程的静态优先级，普通进程不用counter：当前剩余时间片新时期开始时根据上述计算公式计算每次时钟中断发生，时间片都会-1，直到为0（则请求调度）创建一个新的进程时，子进程会继承父进程的一半剩余时间片nice：对时间片进行调节1/2/202323Linux操作系统分析操作系统分析schedule函数函数schedule函数实现调度目的：在运行队列中找到一个进程，把CPU分配给它调用方法：直接调用，如sleep_on松散调用，根据need_resched标记阅读schedule函数，了解如何区分实时和非实时进程1/2/202324Linux操作系统分析操作系统分析2.4调调度算法的性能度算法的性能不适合进程数量很大的情况重新计算所有进程的动态优先级很耗时对高负载系统来说，预定义的时间片太长对于I/O密集型的程序不是很有利对实时应用的支持是微弱的1/2/202325Linux操作系统分析操作系统分析2.6.17中的中的优优先先级队级队列列优先级队列的组织双队列：active和expired1/2/202326Linux操作系统分析操作系统分析