logo资料库

调度器章节笔记整理_修订版.pdf

发布时间：2022-06-07 发布人：admin 分类：说明书 资料大小：1.44M 资料格式：pdf 举报 版权申诉
第1页 / 共60页
第2页 / 共60页
第3页 / 共60页
第4页 / 共60页
第5页 / 共60页
第6页 / 共60页
第7页 / 共60页
第8页 / 共60页
资料共60页，剩余部分请下载后查看
    Kevin.Liu 2012/10/20 ~2012/10/27 内核版本：2.6.24 博客：http://janneo.blog.sohu.com Linux2.6.24 内核，调度器章节的笔记 本文只是为了方便今后复习整理的读书笔记，仅仅是将现有的知识用我自己 的语言（和图画）进行重新表述，没有什么所谓的原创，都是参考他人的或者参 考 linux 内核源码及文档。 主要参考《深入理解 Linux 内核架构》（Wolfgang Mauerer)一书。 另外还参考了： 对 switch_to 的理解 http://home.ustc.edu.cn/~hchunhui/linux_sched.html#sec9 和 郭 海林 同学的 ppt 主调度器执行的时机 http://www.linuxdiyf.com/linux/201107/648.html http://www.ibm.com/developerworks/linux/library/l-task-killable/ http://blog.csdn.net/ustc_dylan/article/details/4140245 http://book.51cto.com/art/201005/200918.htm 进程的状态切换 虚拟运行时间部分 组调度 题外话 此文对 linux 内核的理解或者表述很有可能出现多处谬误，希望您在读的时 候保持怀疑的态度。如果发现错误了希望您能帮我指出，免得此文误导更多人， 谢谢！ 注意：文中出现的名字“队列”仅仅是一个普通中文名词，表示具有先后 顺序的一串事物，不是指抽象数据结构中先进先出的结构体 queue. 本文章也是“吃百家饭”而成的，可以任意转载，不要求注明原作者，但是 你得保证我在更新了文章中的错误时，你也能够及时更新你转载的副本，否则错 误会蔓延下去。 目录 Linux2.6.24 内核，调度器章节的笔记 ................................................................................ 1 1. 调度器相关的功能结构概述....................................................................................... 2 1.1. 运行（Run Queue）队列 .............................................................................. 2 1.2. 核心调度器 ................................................................................................. 3
    1.1.1. 主调度器.............................................................................................. 3 1.1.2. 周期性调度器....................................................................................... 4 1.3. 调度器类..................................................................................................... 5 2. 就绪进程在队列中如何排序的 ................................................................................... 7 2.1. 实时进程..................................................................................................... 7 2.2. 普通进程..................................................................................................... 8 2.2.1. 模型建立.............................................................................................. 9 2.2.2. 抽象模型的总结 ................................................................................. 18 2.2.3. 真实模型概述..................................................................................... 18 2.2.4. 对应关系............................................................................................ 21 2.2.5. 真实模型详述..................................................................................... 22 3. 进程优先权 ............................................................................................................. 30 4. 核心调度器 ............................................................................................................. 35 4.1. 周期性调度器............................................................................................ 36 4.2. 主调度器................................................................................................... 42 4.2.1. 代码块 1 ............................................................................................ 43 4.2.2. 代码块 2 ............................................................................................ 43 4.2.3. 代码块 3 ............................................................................................ 44 4.2.4. 代码块 4 ............................................................................................ 45 4.2.5. 总结................................................................................................... 46 switch_to ............................................................................................ 47 4.2.6. 5. 进程的状态切换 ...................................................................................................... 54 1. 调度器相关的功能结构概述 在学习调度器前，先从整体上做一个了解，对整体构成有一个清晰的认识， 然后在深入细节，才不会像我一样在学习的过程中迷失在细节里。 1.1. 运行（Run Queue）队列 原理概述 linux 内核用结构体 rq（struct rq）将处于就绪（ready）状态的进程组织 在一起。 rq 结构体包含 cfs 和 rt 成员，分别表示两个就绪队列：cfs 就绪队列用于 组织就绪的普通进程(这个队列上的进程用完全公平调度器进行调度)；rt 就绪队 列用于用于组织就绪的实时进程(该队列上的进程用实时调度器调度)。 在多核系统中，每个 CPU 对应一个 rq 结构体。 Figure.就绪队列简要示意图
    细节 cfs 队列实际上是用红黑树组织的，rt 队列是用链表组织的。 在这里只需要知道如下性质就行了：红黑树是一种二叉搜索树，大小关系是： 左孩子<父节点<右边，即最左边的节点的值最小（如果对该内容感兴趣可以参考 数据结构和算法分析相关书籍）。 有几个 CPU 就会有几个 rq 结构体，所有的结构体保存在 一个数组中（即 runqueues)。 1.2. 核心调度器 原理概述 进程调度与两个调度函数有关：scheduler_tick()和 schedule()，这两者分 别被称作周期性调度器(或周期性调度函数)和主调度器(或主调度函数)。两者合 在一起被称作通用调度器（或者核心调度器）（这里一定要分清几个名词分别代 表什么意思，不要像我第一次读到书中这个部分时一样，搞定一头雾水，完全不 知所云） 1.1.1. 主调度器 在我们通常的概念中：调度器就负责将 CPU 使用权限从一个进程切换到另 一个进程。完成这个工作的这其实就是 Linux 内核中所谓的主调度器。 A1A2A3A4A5B1B2B3B4B5CPU0C1C2C3C4C5D1D2D3D4D5CPU1CFSRTRQCFSRTRQrunqueues:01
    上图中，三种不同颜色的长条分别表示 CPU 分配给进程 A、B、C 的一小段 执行时间，执行顺序是：A,B,C。竖直的虚线表示当前时间，也就是说；A 已经 在 CPU 上执行完 CPU 分配给它的时间，马上轮到 B 执行了。这时主调度器 shedule 就负责完成相关处理工作然后将 CPU 的使用权交给进程 B。 总之，主调度器的工作就是完成进程间的切换。 1.1.2. 周期性调度器 再来看看周期性调度器都干些什么吧。同样是刚才的那幅图，不过现在我们 关注的不是从进程 A 切换到进程 B 这个过程，而是把 A 在 CPU 上执行的过程放 大后观察细节。 在 A 享用它得到的 CPU 时间的过程中，系统会定时调用周期性调度器（即 定时执行周期性调度函数 scheduler_tick（）)。 CPUABCschedule()主调度器示意图CPUAscheduler_tick()周期性调度器示意图
    在此版本的内核中，这个周期为 10ms（这个 10ms 是这样得来的：内中定 义了一个宏变量：HZ=100，它表示每秒钟周期性调度器执行的次数，那么时间 间隔 t=1/HZ=1/100s=10ms。10ms 是个什么概念呢，我们粗略地计算一下：如 果周期性调度程序每次执行 100 条指令，每秒执行 100 次，那么一秒钟周期性 调度器在 CPU 上执行的指令就是 1 万条。如果主频为 1GHz 的处理器每秒钟执 行 10 亿条指令，就相当于，周期性调度器消耗的 CPU 只占 CPU 总处理能力的 1 万/10 亿=10 万分之一，微乎其微）。为了方便理解，上图将 A 获得的时间段分 成长度为 10ms 的小片（注意：只是为了方便讲解，假想成这样的，内核并没有 做这样的划分）。 周期性调度器每 10ms 执行一次，那它都干了些什么呢？它只是更新了一些 统计信息。例如：进程 A 的结构体的成员 sum_exec_runtime 记录了 A 在 CPU 上运行的总时间，周期性调度器会更新该时间为：sum_exec_runtime+=10ms （这种说法不准确，细节信息后续内容会讲到）。 我第一次在书中看到周期性调度器的时候，就没法儿理解，它又不负责进程 切换，怎么能称之为调度器呢，这未免也太误导读者了吧。要记住一点：它不负 责进程切换。 细节 周期性调度器是用中断实现的：系统定时产生一个中断，然后在中断过程中 执行 scheduler_tick()函数，执行完毕后将 CPU 使用权限还给 A（有可能不会 还给 A 了，细节后续在讨论），下一个时间点到了，系统会再次产生中断，然 后去执行 scheduler_tick()函数。（中断过程对进程 A 是透明的，所以 A 是一 个傻子，它以为自己连续享用了自己得到的 CPU 时间段，其实它中途被 scheduler_tick()中断过很多次)。 小结： 主调度器负责将 CPU 的使用权从一个进程切换到另一个进程。周期性调度 器只是定时更新调度相关的统计信息。 1.3. 调度器类 原理概述 内核中定义了很多用于处理不同类型进程（普通进程、实时进程、idle 进程） 的处理函数，例如：将普通进程放入就绪队列的函数：enqueue_task_fair(), 将实时进程放入就绪队列的函数 enqueue_task_rt()。 调度器需要用到这些函数，如果需要将睡眠的进程重新放入就绪队列，会调 用 enque_task_XXX()函数。那么，调用哪一个？答：先判断该进程是什么类型 的进程，如果是普通进程就调用 enqueue_task_fair()，如果是实时进程就调用 enqueue_task_rt()。(如下图)
    这固然可行，但是内核不是这样做的。Linux 内核把这些用于处理普通进程 的函数用结构体实例 fair_sched_class(该结构体的成员全是指向函数的指针) 组织起来,把用于处理实时进程的函数用结构体实例 rt_sched_class 组织起来, 把用于处理 idle 进程的函数用 idle_sched_class 组织起来。 然后将普通进程关联到 fair_sched_class(task_A->sched_class = fair_sched_class),实时进程关联到 rt_sched_class,idle 进程关联到 idle_sched_class，那么需要用到相关函数的时候就不需要判断进程是什么类型 的了，而是直接调用该进程关联的函数就行了（如： task_A->sched_class->enqueue_task(rq, p, wakeup, head);）。
    2. 就绪进程在队列中如何排序的 对 linux 内核调度器有了大概的了解，现在我们接着进入细节的学习。 首先看一看各个进程在就绪队列中究竟是怎样进行先后排序的（即，如何决 定进程被调度的先后顺序）。 2.1. 实时进程 原理概述 所有就绪的的实时进程都被组织在 rq 结构体中的 rt(struct rt_rq)就绪队 列上，它的排序非常简单。 相同优先等级的实时进程被组织在同一个双向链表中。在本版本的内核中， 实时进程的优先等级从[0~99]，共 100 个等级，因此就有 100 个这样的链表。 每个链表的表头记录在 rt.active.queue 中。 active 是 rt(struct rt_rq)的一个成员，是 struct rt_prio_array 类型的： kernel/sched.c struct rt_rq { struct rt_prio_array active; ... }; struct rt_prio_array 的定义如下: kernel/sched.c struct rt_prio_array { DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */ struct list_head queue[MAX_RT_PRIO]; }; 它包含两个成员，一个数组 queue，用来存放各个优先级的实时进程的链表 头。另一个是一个位图。位图中每一位对应一个实时进程的链表，如果优先级为 5 的链表上没有进程，那么为图中第 5 位就为 0，反之则为 1。如下图： 优先级递增
    调度器选择实时进程进程执行时，先在优先级高的链表上查找，如果没有再 依次找优先级低的。在同一个优先级中，进程被调度的先后顺序就是它在链表中 的先后顺序。 2.2. 普通进程 原理概述 所有就绪的普通进程被组织在 rq 结构体中的 cfs(struct cfs_rq)就绪队列 上。这里为了方便把它称作"队列"，它实际上是用红黑树进行组织的，红黑树是 一种二叉搜索树：左孩子的值小于父节点，右孩子的值大于父节点，即最小的会 出现在红黑树最左边。如下图所示： 红黑树的具体细节不做讨论，只需要记住排在最左边进程最先执行就行了。 接下来的讨论中我们不关心它如何使使用红黑树进行组织的，只是简单地把它看 做是一个具有先后顺序的队列就行了（再次提醒，这里的“队列”仅仅指具有先 后顺序的一串事物，不是指抽象数据结构中先进先出的结构体 queue）。 这个版本的 linux 内核中用于决定就绪进程在就绪队列中先后顺序的机理很 简单，也很巧妙。直接讲它怎么实现的，对于读者来说要听明白应该也是轻而易 举的；但是对于表述能力如此差的我来说，要讲明白则太过于勉强了，所以我就 从最简单的"模型"开始一步一步构建"真实模型"。 提示：这一部分内容对调度器的理解不是特别重要，在这里却占用了很多的篇幅， 如果不感兴趣最好是直接跳过，直接从进程优先权看起，或者先看完后面的内容， 再回头看这部分。 以下内容，为了讲解方便，可能运用了类似于时间片的讲述方法，可能会让 读者误以为该版本 linux 内核采用了时间片的管理方式。因此,需要特别声明一下， 早期的内核中有时间片的概念，但是该版本的内核已经没有时间片的概念了。 细节 79155176138
    分享到：
    赞 收藏

    相关推荐

    资料库

    操作系统

    共收录1433份资料，累计11个分类，关注成员有19位，主要包括：CentOS,MacOS,DOS,Solaris,Ubuntu,Unix,OS,桌面系统,其它,Windows Server,Linux

    热门标签

    CentOS MacOS DOS Solaris Ubuntu Unix OS 桌面系统 其它 Windows Server Linux

    最新资料