中国科学技术大学计算机系 陈香兰（0512－ ） Autumn 2009

Presentation on theme: "中国科学技术大学计算机系 陈香兰（0512－ ） Autumn 2009"— Presentation transcript:

1 中国科学技术大学计算机系 陈香兰（0512－87161312） xlanchen@ustc.edu.cn Autumn 2009
Linux操作系统分析 中国科学技术大学计算机系 陈香兰（0512－ ） Autumn 2009

2 主要内容 进程描述符 进程切换 进程的创建和删除 进程调度 2019/1/111/23/09 Linux操作系统分析

3 进程的分类 不同类型的进程有不同的调度需求 第一种分类： I/O-bound CPU-bound 频繁的进行I/O
计算密集型 需要大量的CPU时间进行运算 2019/1/111/23/09 Linux操作系统分析

4 第二种分类 交互式进程（interactive process） 需要经常与用户交互，因此要花很多时间等待用户输入操作
响应时间要快，平均延迟要低于50~150ms 典型的交互式程序：shell、文本编辑程序、图形应用程序等 2019/1/111/23/09 Linux操作系统分析

5 实时进程（real-time process）
批处理进程（batch process） 不必与用户交互，通常在后台运行 不必很快响应 典型的批处理程序：编译程序、科学计算 实时进程（real-time process） 有实时需求，不应被低优先级的进程阻塞 响应时间要短、要稳定 典型的实时进程：视频/音频、机械控制等 2019/1/111/23/09 Linux操作系统分析

6 Linux中的进程调度 Linux既支持普通的分时进程，也支持实时进程 Linux中的调度是多种调度策略和调度算法的混 合。
什么是调度策略？ 是一组规则，它们决定什么时候以怎样的方式选择一 个新进程运行 Linux的调度基于分时和优先级 随着版本的变化，分时技术在不断变化 2019/1/111/23/09 Linux操作系统分析

7 Linux的进程根据优先级排队 Linux中进程的优先级是动态的 根据特定的算法计算出进程的优先级，用一个值表示
这个值表示把进程如何适当的分配给CPU Linux中进程的优先级是动态的 调度程序会根据进程的行为周期性的调整进程的优先 级 较长时间未分配到CPU的进程，通常↑ 已经在CPU上运行了较长时间的进程，通常↓ 2019/1/111/23/09 Linux操作系统分析

8 与调度相关的系统调用 nice getpriority/setpriority
sched_getscheduler/sched_setscheduler sched_getparam/sched_setparam sched_yield sched_get_priority_min/sched_get_priority_max sched_rr_get_interval 2019/1/111/23/09 Linux操作系统分析

9 例如 2019/1/111/23/09 Linux操作系统分析

10 又如 2019/1/111/23/09 Linux操作系统分析

11 2019/1/111/23/09 Linux操作系统分析

12 2019/1/111/23/09 Linux操作系统分析

13 调度算法 Linux 2.4的调度算法 Linux 2.6.17的调度算法（2.6.23之前） Linux 2.6.26的调度算法
需要遍历可运行队列，算法O(n) Epoch，基本时间片，动态优先级 Linux 的调度算法（2.6.23之前） 采用双队列（Active；expire ），按照优先级组队，O(1) Linux 的调度算法 非实时：CFS，vruntime，红黑树 实时：优先级队列 Linux进程可以指定该进程所采用的调度策略 调度算法根据进程的调度策略，采用不同的调度算法 2019/1/111/23/09 Linux操作系统分析

14 关于CFS的vruntime 理想的调度，所有的任务都是公平的。等速度的 运行每个任务。
cfs就是通过追踪这个vruntime来进行任务调度的 。它总是选 vruntime最小的进程来运行。 2019/1/111/23/09 Linux操作系统分析

15 Linux 2.6.26中的 调度策略：Policy，调度类型
include/linux/sched.h 在task_struct中，使用数据项policy来表达该进程采用的调度策略 2019/1/111/23/09 Linux操作系统分析

16 查看linux-2.6.26中各个policy的使用情况
2019/1/111/23/09 Linux操作系统分析

17 kernel/sched.c 2019/1/111/23/09 Linux操作系统分析

18 调度类型 阅读const struct sched_class，调度类 rt_sched_class fair_sched_class
idle_sched_class kernel/sched_idletask.c kernel/sched_fair.c kernel/sched_rt.c fair_sched_class idle_sched_class rt_sched_class 2019/1/111/23/09 Linux操作系统分析

19 阅读2.6.26的schedule函数 调度函数的关键： 调度算法的关键 入列
CFS根据vruntime的值入列，其关键在于vruntime值的计算 RT根据优先级入列 kernel/sched.c，参见函数schedule() kernel/sched_fair.c，update_curr 2019/1/111/23/09 Linux操作系统分析

20 Linux 中每个CPU的就绪队列 2019/1/111/23/09 Linux操作系统分析

21 Linux-2.6.26中进程的调度实体 include/linux/sched.h:task_struct
2019/1/111/23/09 Linux操作系统分析

22 include/linux/sched.h
2019/1/111/23/09 Linux操作系统分析

23 2019/1/111/23/09 Linux操作系统分析

24 关于CFS的vruntime 理想的调度，所有的任务都是公平的。等速度 的运行每个任务。
cfs就是通过追踪这个vruntime来进行任务调度 的。它总是选 vruntime最小的进程来运行。 几个关键的vruntime更新之处 set_task_cpu：进程从原CPU上转移到新CPU上，需 根据两个cpu上就绪队列min_vruntime的值的差距进 行调整，使得进程的vruntime值能与新的调度队列中 的进程具有一定的可比性 kernel/sched.c 2019/1/111/23/09 Linux操作系统分析

25 在__update_curr中， 在yield_task_fair中， 等等 kernel/sched_fair.c
2019/1/111/23/09 Linux操作系统分析

26 了解linux-2.6.26中进程的滴答更新 调度类中的方法task_tick用来在任务运行时进行 滴答更新。
每个调度类都有自己的滴答更新方法： task_tick_rt、task_tick_fair和task_tick_idle（为空 ）。 2019/1/111/23/09 Linux操作系统分析

27 考虑task_tick_fair 2019/1/111/23/09 Linux操作系统分析

28 关键内部函数update_curr，参见源代码
2019/1/111/23/09 Linux操作系统分析

29 include/linux/sched.h
2019/1/111/23/09 Linux操作系统分析

30 考虑task_tick_rt 2019/1/111/23/09 Linux操作系统分析

31 Linux2.6.26中的优先级 优先数范围为0～139，其中0～99为实时优先数 普通任务和批处理任务的优先数在100～139之间
优先数越大，优先级越低。 2019/1/111/23/09 Linux操作系统分析

32 Linux2.6.26中的nice值 Nice值用来调整进程的优先级 Nice值的范围在-20~19之间。 2019/1/111/23/09

33 Linux 中的调度算法 2019/1/111/23/09 Linux操作系统分析

34 Linux-2.4.18的调度策略 Linux进程可以指定该进程所采用的调度策略 调度算法根据进程的调度策略，采用不同的调度 算法
普通的分时进程 先入先出的实时进程 循环轮转的实时进程 当一个进程自动放弃运行时设置 2019/1/111/23/09 Linux操作系统分析

35 Linux-2.4.18的调度主要基于分时技术 允许多个进程“并发”运行 CPU的时间被划分成“片”，给每个可运行进程分 配一片
在单处理器上，任何时刻只能运行一个进程，当 一个并发执行的进程时间片用完时（到期）还没 有终止，就可以进行进程调度 分时依赖于时钟中断，对进程透明 2019/1/111/23/09 Linux操作系统分析

36 采用常规分时时，时间片的选择 时间片的长短对系统性能非常关键，它既不能太 长也不能太短 太短： 频繁的切换会造成系统开销过大
假如切换时间为1ms，时间片设置为1ms，那就没空 执行进程了 2019/1/111/23/09 Linux操作系统分析

37 时间片大小的选择总是一种折衷。Linux采取单 凭经验的方法，即选择尽可能长的时间片，同时 能保持良好的响应时间
太长 几乎每个进程都一次运行完 并发的概念基本消失 普通进程需要等待很长时间才能运行 时间片大小的选择总是一种折衷。Linux采取单 凭经验的方法，即选择尽可能长的时间片，同时 能保持良好的响应时间 2019/1/111/23/09 Linux操作系统分析

38 Linux 进程的调度优先级 Linux在其调度程序中，根据特定的算法计算出 进程的调度优先级，用一个值goodness表示，进 程根据这个值竞争CPU 2019/1/111/23/09 Linux操作系统分析

39 Linux-2.4.18的调度算法（1） epoch linux调度算法把CPU时间划分为时期（epoch）
在一个单独的时期内，每个进程有一个指定的时间片 一个进程用完它的时间片时，就会被强占 只要进程的时间片没有用完，就可以被多次调度运行 当所有的进程用完它的时间片的时候，一个时期才结 束，此时要重新计算所有进程的时间片，并重新开始 一个新的时期 2019/1/111/23/09 Linux操作系统分析

40 Linux-2.4.18的调度算法（2） 基本时间片（base time quantum） 每个进程有一个基本时间片，通过nice计算
时间片/epoch到期时，新时间片的计算公式： 可以通过nice、setpriority系统调用调整进程的基本时 间片 nice缺省为0（在-20到19之间选择） 通常，基本时间片的值 为6，由于时钟中断大约10ms左右， 因此基本时间片的长度大约60ms 2019/1/111/23/09 Linux操作系统分析

41 Linux-2.4.18的调度算法（3） 当前剩余时间片 每个进程使用counter表示当前时期内的剩余时间 片
每当一个tick过去，就会从当前进程的counter上-1 在某个时期内创建的一个新进程，在该时期内的 剩余时间片将从父进程那里继承一半 2019/1/111/23/09 Linux操作系统分析

42 举例：进程0（INIT_TASK）的时间片：
HZ代表了1秒内的tick数 因此一个tick就是1/100秒 即10ms 可以计算出 DEF_COUNTER=10个tick 即100ms (实际上约105ms) MAX_COUNTER=20个tick 即200ms 2019/1/111/23/09 Linux操作系统分析

43 Linux-2.4.18中调度程序使用的数据结构 进程描述符中： need_resched：是否需要调度 policy：调度策略
rt_priority：实时进程的静态优先级（1~99），普通进 程不用（设为0） counter：当前剩余时间片 新时期开始时根据上述计算公式计算 每次时钟中断，时间片都会-1，直到为0（则请求调度） 创建一个新进程时，子进程会继承父进程的一半剩余时间片 nice：基本时间片参数，可以调节 2019/1/111/23/09 Linux操作系统分析

44 schedule函数 schedule函数实现调度 目的：在运行队列中找到一个进程，把CPU分配 给它 调用方法： 阅读schedule
直接调用，如sleep_on 松散调用，根据need_resched标记 阅读schedule 2019/1/111/23/09 Linux操作系统分析

45 调度的时机 调度时机来临时，内核或驱动将调用schedule() 在Linux中调度的时机主要有：
current的状态从running转换为其他状态时，如： 1）进程终止。exit()在最后调用schedule()。 2）进程因某种原因进入等待状态。 比较常见的就是进程调用nanosleep()或者wait系列的 系统调用。 此外，在设备驱动程序中，最常见的原因就是驱动引 发一次I/O操作后，为等待I/O操作的结束而进入等待 状态。多数情况下，驱动会直接调用schedule()。 2019/1/111/23/09 Linux操作系统分析

46 进程从中断、异常、系统调用状态（即内核态）返回 时。
当前进程的时间片用完时。 时间片是否用完，由时钟中断处理程序进行判断。 若到期，就将current的need_resched位置1。 返回用户态时，根据need_resched调用schedule() 进程从中断、异常、系统调用状态（即内核态）返回 时。 若在中断、异常、系统调用中，current的need_resched被置1 ，都会导致进程调度。 包括上述时钟中断。 2019/1/111/23/09 Linux操作系统分析

47 调度算法的性能 不适合进程数量很大的情况 对高负载系统来说，预定义的时间片太长 对于I/O密集型的程序不是很有利 对实时应用的支持是微弱的
重新计算所有进程的动态优先级很耗时 对高负载系统来说，预定义的时间片太长 对于I/O密集型的程序不是很有利 对实时应用的支持是微弱的 2019/1/111/23/09 Linux操作系统分析

48 作业： Linux为什么要引入pidhash表？
在传统的UNIX系统中，创建子进程时会复制父 进程的所有资源，代价比较高，现代UNIX系统 中引入了哪几项技术来解决这个问题？ Linux2.4.18中，名词解释： epoch 基本时间片 Linux2.6.26中，名词解释： CFS Linux2.6.17中，名词解释： 双队列 2019/1/111/23/09 Linux操作系统分析