当前课程知识点：Linux 内核分析与应用 > 第3章 进程管理 > 3.3 Linux进程调度 > Video
大家好这一讲呢 我们来介绍一下进程的调度
那么这张图呢是进程调度的基本模型
我们说所谓调度实际上就是从就绪队列中选择一个进程投入CPU运行
那么从这张图看出来呢调度的主战场就是就绪队列
核心是调度算法 实质性的动作是进程的切换
对以时间片调度为主的调度时钟中断就是驱动力
确保每个进程在CPU上运行一定的时间
在调度的过程中呢
用户还可以通过系统调用nice来调整优先级
比如降低自己的优先级等等
当然也涉及进程状态的转换
新创建的进程 就加入到了就绪队列中
那么退出的进程呢就从队列中删除
从这张图我们还可以看出呢
所有CPU的所有进程都存放在了一个就绪队列中
那么我们从中选中一个进程进行调度的过程呢
实际上是从这个队列上的一种线性查找的过程
因此其算法复杂度为O(n)
详细调度过程和代码的分析呢
请参看教材3.4节的进程的调度
这是针对2.4版内核的代码分析
比较简单 看起来相对容易一些
本次课程主要讲解进程调度的演变过程
以指导大家阅读高版本的内核源代码
下面我们来看一下调度的主战场—就绪队列
那么在内核中如何来表示就绪队列
我们说 把就绪队列的进程 组成一个双向循环链表就叫做就绪队列
在task_struct结构里头定义的队列的结构
非常的简单 就是一个list_head
我们看这个图呢它的
队头就是init_task结构 也就是0号进程的PCB
那么这张图呢是关于
进程调度涉及的最主要的东西叫进程的优先级
我们说在进程的调度算法中呢 优先级是一个很重要的因素
我们可以从两个角度来看优先级
首先看用户态的空间
那么它有两种优先级
一中呢是普通优先级
从-20~19
数据越小呢优先级越高
我们可以通过修改这个值 改变普通进程获取CPU资源的比例
那第2种呢叫做调度优先级
从1~99
这是实时进程的优先级
当然呢普通进程也有调度优先级 但是被设定为0
从内核空间来看呢有动态优先级(prio)
静态优先级(static_prio) 归一化优先级(normal_prio)和实时优先级(rt_priorit )
这里特别介绍一下 归一化优先级
它是根据静态优先级
调度优先级和调度策略计算而得到的
那么动态优先级是什么呢是在运行过程中可以来动态的调整
那么在task_struct结构中呢
这些优先级如何来表示
我们看那么是下面列出的这样子
大家可以进入源代码呢查看相关的字段
那么这张图呢叫做O(1)调度的模型
前面我们介绍了O(n)调度器
那么这其中呢只有一个全局的就绪队列
这严重的影响了其扩展性
因此就引入了O(1)调度
在O(1) 调度器中呢
引入了每CPU一个就绪队列的概念
也就是说系统中所有的就绪进程呢
首先经过负载呢
挂入各个CPU就绪队列上
然后呢由主调度器和周期性的调度器呢
驱动该CPU上的调度行为
这张图是O(1)调度的优先级队列
那么我们就会发出疑问 为什么说它是O(1)调度呢
O(1)调度器的基本优化思路呢
就是把原来的就绪队列上的单链表呢
变成了多个链表
也就是说每一个优先级的进程呢
被挂入到不同的链表里边
那么优先级数组的结构是什么样子
我们这里给出了它的结构
O(1)由于支持140个优先级
因此呢队列成员中就有140个
分别表示各个优先级的链表头
那么不同优先级的进程呢
自然就挂到不同的链表中
其中bitmap字段表示什么意思呢
表示各个优先级进程的链表呢
是空还是非空
nr_active表示这个队列中呢
到底有多少个任务
那么在这些队列中呢
100~139是普通进程的优先级
那么其他的呢都是实时进程的优先级
因此呢在O(1)的调度器中呢
实时进程和普通进程就被区分来对待了
普通进程根本就不会影响实时进程的调度
从这张图中我们也看到
就绪队列中有两个优先级队列
它们分别用来管理
活跃队列active(也就是说时间片还有剩余的队列)
和expired(时间片耗尽)的进程
随着系统的运行呢
活跃队列中的任务呢一个个的耗尽其时间片
挂入到时间片耗尽的队列里头
当活跃队列的任务为空时候呢
两个队列互换开始新一轮的调度过程
虽然在O(1)的调度器中任务组织的形式发生了变化
但是其核心的思想仍然和O(n)调度是一致的
都是把CPU的资源分成一个个的时间片
分配给每一个就绪的进程
那么进程用完其额度后呢就被抢占
等待下一轮调度周期的到来
这里我们来介绍一下主调度器(也就是schedule函数)
它的主要功能就是从该CPU的就绪队列中呢
找到一个最合适的进程进行调度
其基本的思路就是从
活跃优先级队列中查找
首先呢在当前活跃队列的位图中
寻找第1个非空的进程链表
然后呢从在该链表中呢
找到的第1个节点呢
就是最适合下一个调度执行的进程
由于没有遍历整个链表的操作 因此 这个调度器的算法复杂度就是一个常量
从而解决了O(n)算法的复杂度的问题
但是呢O(1)调度器使用非常复杂的
算法来判断进程是不是交互式进程 以及进程的交互的次数
即使这样呢还依然会出现卡顿现象
那么怎么解决这个问题呢
能不能不要被用户的具体需求所捆绑
而又能够支持灵活多变的需求
在此呢我们想到了机制与策略分离的机制
那么这个模型呢就是
调度器里头的
调度模型 机制与策略分离
这种机制功能层面上来看呢
进程调度仍然分成两部分
第一个部分是通过负载均衡模块呢 将各个就绪状态的任务
根据负载情况呢
平均分配到各个CPU的就绪队列上去
分的功能 在各个CPU的主调度器(Main scheduler)
和周期性调度器(Tick scheduler)的驱动下呢
进行单个CPU上的调度
那么调度器处理的任务呢各个不同
有实时任务(RT task) 普通任务(normal task)
最后期限(Dead Line task)的任务
但是无论哪一种任务 它们有共同的逻辑
把这部分共同的逻辑抽象出来了
就成为核心调度器层(Core scheduler)
同时我们根据各种特定类型的调度器呢
可以定义自己的调度类(sched_class)
并以链表的形式加入到系统中
这样的机制与策略分离的设计可以方便用户
根据自己的场景定义特定的调度器
而不需要改动核心调度层的逻辑
下面我们简单的介绍一下
调度器类部分的成员作用
这个结构我们说它就是调度器类
下面我们对它的每个字段给予简单的介绍
其中第1个next指向下一个比自己低一级的优先级调度类
那么第2个字段指向入队的函数
第3个字段指向出队的函数
第4个字段呢
表示当前CPU上正在运行的进程呢
是不是可以被抢占
那么第5个呢就是核心的字段
也就是从就绪队列中选择一个最适合运行的进程
这是调度器比较核心的一个操作
例如呢我们依据什么来挑选最合适运行的进程呢
这是每一个调度器需要关注的问题
接下来 我们简述一下完全公平调度CFS
CFS调度器的目标是保证每一个进程的完全公平调度
那么CFS调度器与以往的调度器有什么不同之处呢
它的不同之处在于没有了时间片的概念
而是分配CPU使用时间的比例
理想的状态下呢 每个进程都能获得相同的时间片
而且能同时运行在CPU上
但实际上一个CPU同一时刻
运行的进程只能有一个
也就是说当一个进程占用CPU的时候呢
其他进程必须等待
CFS为了实现公平呢
必须惩罚当前正在运行的进程
以使那些正在等待的进程呢 下次再被调
这是完全公平调度算法中所使用的红黑树
那么在具体实现的时候
CFS通过每个进程的虚拟运行时间(vruntime)
衡量哪个进程最值得被调度
CFS中的就绪队列就是一棵
以虚拟时间为键值的红黑树
虚拟时间越小的进程呢
就越靠近红黑树的最左边
因此 调度器每次选择位于红黑树最左端的那个进程
该进程的虚拟时间是最小的
那么虚拟运行时间是通过什么来计算出来的呢
它是通过进程的实际运行时间
和进程的权重(weight)计算出来的
在CFS调度器中呢
将进程优先级这个概念呢
就给弱化了而是强调进程的权重
一个进程的权重越大说明这个进程越需要运行
因此它的虚拟运行时间就越小
这样的被调度的机会就越大
前面我们对
Linux调度器作了一个概要的介绍
那么下面呢我们给出一个总结
我们说进程调度是操作系统一个很重要的部件
那么它的主要功能是把系统中的任务呢
调度到各个CPU上去执行
以满足如下的性能的需求
对于分时的进程 调度器必须是公平的
而且是快速的进程响应时间
系统高的吞吐量 功耗还要小
当然呢对于不同的任务有不同的需求
因此呢我们需要对任务进行分类
一般呢分为两大类 普通进程和实施进程
对于实时进程来说毫无疑问
快速响应的需求是最重要的
而对于普通进程呢
我们一般要兼顾以上3点的需求
但是大家可能发现了 这些需求实际上是互相冲突的
那为了达到这些目标呢
调度器在设计的时候呢
必须综合考虑各种因素
更进一步详细的探讨 请大家阅读相关的参考书或源代码
关于参考资料的话 大家可以查看《深入理解Linux内核》第三版的第七章
在蜗窝科技网站(http://www.wowotech.net/)上关于进行调度呢有一系列的文章
非常详细介绍了调度的方方面面
本章结束后要求大家务必阅读
调度的源代码
可以看低版本的代码 比如说2.4版本的代码
从原理上入门 然后呢
按照兴趣或者需求 再看高版本的代码
-1.1 Linux操作系统概述
-1.2 Linux内核结构以及内核模块编程
--Video
-1.3 Linux内核源码中的双链表结构
--Video
-1.4 源码分析-内核中的哈希表
--Video
-1.5 动手实践-Linux内核模块的插入和删除
--Video
-第1章 概述--章节测验
-2.1 内存管理之内存寻址
--Video
-2.2 段机制
--Video
-2.3分页机制
--Video
-2.4 动手实践-把虚拟地址转换成物理地址
--Video
-第2章 内存寻址--章节测验
-3.1 进程概述
--Video
-3.2 Linux进程创建
--Video
-3.3 Linux进程调度
--Video
-3.4 动手实践-打印进程描述符task_struct中的字段
--Video
-3.5工程实践-基于内核模块的负载监控
--Video
-第3章 进程管理--章节测验
-4.1 Linux内存管理机制
--Video
-4.2 进程用户空间管理机制
--Video
-4.3 物理内存分配与回收机制（上）
--Video
-4.4 物理内存分配与回收机制（下）
--Video
-4.5 动手实践-Linux内存映射基础（上）
--Video
-4.6 动手实践-Linux内存映射实现（中）
--Video
-4.7 动手实践-Linux内存映射测试（下）
--Video
-4.8 初学者对内存管理的常见疑惑
-第4章 内存管理--章节测验
-5.1 中断机制概述
--Video
-5.2 中断处理机制
--Video
-5.3 中断下半部处理机制
--Video
-5.4 时钟中断机制
--Video
-5.5 动手实践-中断上半部的代码分析及应用
--Video
-5.6 动手实践-中断下半部的代码分析及应用
--Video
-第5章 中断--章节测验
-6.1 Linux中的各种API
--Video
-6.2 系统调用机制
--Video
-6.3 动手实践-添加系统调用（系统调用日志收集系统）
--Video
-第6章 系统调用--章节测验
-7.1 内核同步概述
--Video
-7.2 内核同步机制
--Video
-7.3 动手实践-内核多任务并发实例（上）
--Video
-7.4 动手实践-内核多任务并发实例（下）
--Video
-第7章 内核同步--章节测验
-8.1 虚拟文件系统的引入
--Video
-8.2 虚拟文件系统的主要数据结构
--Video
-8.3 文件系统中的各种缓存
--Video
-8.4 页高速缓存机制以及读写
--Video
-8.5 动手实践-编写一个文件系统（上）
--Video
-8.6 动手实践-编写一个文件系统（中）
--Video
-8.7 动手实践-编写一个文件系统（下）
--Video
-第8章 文件系统--章节测验
-9.1 设备驱动概述
--Video
-9.2 I/O空间管理
--Video
-9.3 设备驱动模型
--Video
-9.4 字符设备驱动程序简介
--Video
-9.5 块设备驱动程序简介
--Video
-9.6 动手实践-编写字符设备驱动程序
--Video
-9.7工程实践-编写块设备驱动的基础（上）
--Video
-9.8 工程实践-块设备驱动程序分析（中）
--Video
-9.9 工程实践-块设备驱动程序实现（下）
--Video
-第9章 设备驱动--章节测验
-致谢与说明
--Video
