Download presentation
Presentation is loading. Please wait.
1
陈香兰 xlanchen@ustc.edu.cn 助教：陈博、李春华 Spring 2009
嵌入式操作系统 陈香兰 助教：陈博、李春华 Spring 2009
2
Embedded Operating Systems
进程调度 调度策略 调度算法 Embedded Operating Systems
3
Embedded Operating Systems
进程的分类 不同类型的进程有不同的调度需求 第一种分类： I/O-bound 频繁的进行I/O 通常会花费很多时间等待I/O操作的完成 CPU-bound 计算密集型 需要大量的CPU时间进行运算 Embedded Operating Systems
4
Embedded Operating Systems
第二种分类 交互式进程（interactive process） 需要经常与用户交互，因此要花很多时间等待用户输入操作 响应时间要快，平均延迟要低于50~150ms 典型的交互式程序：shell、文本编辑程序、图形应用程序等 Embedded Operating Systems
5
Embedded Operating Systems
批处理进程（batch process） 不必与用户交互，通常在后台运行 不必很快响应 典型的批处理程序：编译程序、科学计算 实时进程（real-time process） 有实时需求，不应被低优先级的进程阻塞 响应时间要短 典型的实时进程：视频/音频、机械控制等 Embedded Operating Systems
6
Embedded Operating Systems
Linux中的进程调度 Linux既支持普通的分时进程，也支持实时进程 Linux中的调度是多种调度策略和调度算法的混合。 什么是调度策略？ 是一组规则，它们决定什么时候以怎样的方式选择一个新进程运行 Linux的调度基于分时和优先级 随着版本的变化，分时技术在不断变化 Embedded Operating Systems
7
Embedded Operating Systems
Linux的进程根据优先级排队 根据特定的算法计算出进程的优先级，用一个值表示 这个值表示把进程如何适当的分配给CPU Linux中进程的优先级是动态的 调度程序会根据进程的行为周期性的调整进程的优先级 较长时间未分配到CPU的进程，通常↑ 已经在CPU上运行了较长时间的进程，通常↓ Embedded Operating Systems
8
Embedded Operating Systems
与调度相关的系统调用 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 Embedded Operating Systems
9
Embedded Operating Systems
采用常规分时时，时间片的选择 时间片的长短对系统性能非常关键，它既不能太长也不能太短 太短： 频繁的切换会造成系统开销过大 假如切换时间为1ms，时间片设置为1ms，那就没空执行进程了 Embedded Operating Systems
10
Embedded Operating Systems
太长 几乎每个进程都一次运行完 并发的概念基本消失 普通进程需要等待很长时间才能运行 时间片大小的选择总是一种折衷。Linux采取单凭经验的方法，即选择尽可能长的时间片，同时能保持良好的响应时间 Embedded Operating Systems
11
Embedded Operating Systems
调度算法 Linux 2.4的调度算法 需要遍历可运行队列，算法O(n) Epoch，基本时间片，动态优先级 Linux 的调度算法（2.6.23之前） 采用双队列（Active；expire ），按照优先级组队，O(1) Linux 的调度算法 非实时：CFS，vruntime，红黑树 实时：优先级队列 Linux进程可以指定该进程所采用的调度策略 调度算法根据进程的调度策略，采用不同的调度算法 Embedded Operating Systems
12
Linux 2.6.26中的 调度策略：Policy，调度类型
在task_struct中，使用数据项policy来表达该进程采用的调度策略 Embedded Operating Systems
13
Embedded Operating Systems
查看各个policy的使用情况 Embedded Operating Systems
14
Embedded Operating Systems
Embedded Operating Systems
15
Embedded Operating Systems
调度类型 阅读const struct sched_class，调度类 rt_sched_class fair_sched_class idle_sched_class fair_sched_class idle_sched_class rt_sched_class Embedded Operating Systems
16
Embedded Operating Systems
阅读2.6.26的schedule函数 调度函数的关键： 调度算法的关键 入列 CFS根据vruntime的值入列，其关键在于vruntime值的计算 RT根据优先级入列 Embedded Operating Systems
17
Embedded Operating Systems
Linux2.6.26中的优先级 优先数范围为0～139，其中0～99为实时优先数 普通任务和批处理任务的优先数在100～139之间 优先数越大，优先级越低。 Embedded Operating Systems
18
Embedded Operating Systems
Linux2.6.26中的nice值 Nice值用来调整进程的优先级 Nice值的范围在-20~19之间。 Embedded Operating Systems
19
Thanks！ The end.
20
Embedded Operating Systems
以下内容作为参考：2.4的调度算法 epoch linux调度算法把CPU时间划分为时期（epoch） 在一个单独的时期内，每个进程有一个指定的时间片 一个进程用完它的时间片时，就会被强占 只要进程的时间片没有用完，就可以被多次调度运行 当所有的进程用完它的时间片的时候，一个时期才结束，此时要重新计算所有进程的时间片，并重新开始一个新的时期 Embedded Operating Systems
21
Embedded Operating Systems
基本时间片（base time quantum） 每个进程有一个基本时间片 可以通过nice、setpriority系统调用调整进程的基本时间片 新进程总是继承父进程的基本时间片 时间片的计算公式： nice缺省为0（在-20到19之间选择） 通常，基本时间片的值 为6，由于时钟中断大约10ms左右， 因此基本时间片的长度大约60ms Embedded Operating Systems
22
Embedded Operating Systems
2.4调度程序使用的数据结构 进程描述符中： need_resched：是否需要调度 policy：调度策略 普通的分时进程 先入先出的实时进程 循环轮转的实时进程 当一个进程自动放弃运行时设置 Embedded Operating Systems
23
Embedded Operating Systems
rt_priority：实时进程的静态优先级，普通进程不用 counter：当前剩余时间片 新时期开始时根据上述计算公式计算 每次时钟中断发生，时间片都会-1，直到为0（则请求调度） 创建一个新的进程时，子进程会继承父进程的一半剩余时间片 nice：对时间片进行调节 Embedded Operating Systems
24
Embedded Operating Systems
schedule函数 schedule函数实现调度 目的：在运行队列中找到一个进程，把CPU分配给它 调用方法： 直接调用，如sleep_on 松散调用，根据need_resched标记 阅读schedule函数，了解如何区分实时和非实时进程 Embedded Operating Systems
25
Embedded Operating Systems
2.4调度算法的性能 不适合进程数量很大的情况 重新计算所有进程的动态优先级很耗时 对高负载系统来说，预定义的时间片太长 对于I/O密集型的程序不是很有利 对实时应用的支持是微弱的 Embedded Operating Systems
26
Embedded Operating Systems
2.6.17中的优先级队列 优先级队列的组织 双队列：active和expired Embedded Operating Systems
Similar presentations
