当前课程知识点：操作系统 > 第十六讲 实验六 调度器 > 16.1 总体介绍和调度过程 > 16.1 总体介绍和调度过程
各位同学好
那么我们这次课呢
是讲解lab6
lab6是关于处理器调度
那这一节呢
主要有一个总体介绍
调度的过程的一个分析
以及我们说
为了支持不同的调度算法
我们要设计的一个支撑框架
就是调度算法的一个支撑框架
然后呢 给大家介绍一下
在实验中已经提供的
Round Robin的调度算法
希望同学能够实现什么呢
是一个Stride调度算法
这个算法呢 在原理课里面没有讲
我们希望通过同学的分析 理解
能够在lab6中完成
首先我们来看一下总体介绍
那总体介绍 主要介绍一下
我们这个实验的目标 练习
和一个大致的流程概述
可以看到 在我们完成了lab5之后
我们说 我们可以创建前面的
内核线程和用户进程
当我们的操作系统中
存在多个进程的时候
比如说有多个进程的时候
那就需要知道
有些进程它会占用cpu执行
有些进程可能会等待cpu执行
这里面有一个生命周期的管理
那我们这里面重点研究的
是什么时候 基于什么原则
来选择哪一个进程去执行
这是我们说调度要考虑的问题
这是我们lab6中
重点需要去理解
和掌握的一个知识
好 那我们的目标可以看看
细分一下 第一个是
理解操作系统的调度管理机制
第二个是熟悉ucore
这个调度器的设计框架
第三个是理解Round Robin调度算法
第四个 我们要去根据你对Stride
调度算法的理解来完成它
到底怎么去实现它这个调度算法
这是我们的目标
为此你需要去对ucore的
lab6里面的源码进行一个分析
包括调度器的框架
Round Robin调度算法
以及Stride调度算法
那其实我们可以看看
对于应用程序而言
比如hello这个应用程序
看起来它这里面
和操作系统的调度没有任何关系
但其实呢
操作系统在管理这个进程的
从创建到最后它消失
这个过程呢 其实我们操作系统
有多次的调度的机会
去选择让这个进程执行
或者是不让它执行
这其实是在后面
我们操作系统的底层
来完成了整个调度的过程
而所有的过程
对我们应用程序的执行来说
是透明的 看不见的
好 那我们再把大致的流程
给大家介绍一下
首先我们回顾一下
这个调度 其实并不是说
在lab6才出现
在早期的lab5
其实已经出现了调度
我们可以回顾一下 看看怎么回事
lab5中它完成了
对用户进程的管理
那在这个管理过程中呢
涉及到对整个进程
生命周期的管理
我们这边其实已经存在了
对一般进程它也有个调度
只是这个调度很简单 是FIFO
我们说先进先出这么一个调度算法
这里面呢 一个进程当创建完之后
它处于就绪态
然后一旦被我们的ucore选择
去让它在CPU上执行的时候
它就从头执行 直到结束
中间不会被打断
只有结束之后
我们的ucore才会去查找
下一个处于就绪态的进程
让它去执行
那么这个查找下一个进程
是由谁完成的呢
是我们的idle
idle实际上是一个内核线程
我们在里面其实大家再注意一下
我们在讲lab4 lab5的时候
虽然说它是一个是内核线程
一个是用户进程
但是它们的调度 它们的管理
这一块其实是大同小异
基本上是一样的 有一些区别
大家再回顾一下 有哪些区别
那么这个idle这个内核线程呢
它会不断的遍历这个进程池
直到找到第一个
runnable状态的进程
所谓runnable 就是就绪状态
然后找到这个之后呢
就会完成一个进程切换
把自身给挂起
然后去执行找到的进程 去执行它
那么这就是一个最简单的
基于FIFO这种调度策略的调度算法
我们前面讲到了lab4和lab5
其实都和进程管理相关
大家来回顾一下lab4和lab5
它们完成的内核的
线程和用户的进程
它们在管理上面
到底有哪些事情要做
那这种方式我们来给一个评价
这种方式怎么样呢
其实这种方式呢
它体现不出
进程和进程之间的一些特点
比如说我们说进程有优先级
这个进程运行时间太长了
其实它应该在更短的时间就应该结束
让给其他的进程去占用CPU
去完成它各自的工作
如果是基于FIFO这种方式
虽然我们的调度实现很简单
但是呢 它的效率不高
这个在原理课上已经讲过
不同的调度算法
它们有不同的评价指标
我们基于这个评价指标
来衡量这个算法它的好坏
那么我们就是为此
重新设计了lab6这个调度框架
这个lab6里面它主要完成两块
一块是关于调度的初始化过程
一块是具体的调度过程
那么在初始化过程中
首先我们需要去实现一个调度算法
那基于一个调度类来实现的
我们这里面用了C语言
来实现一个函数指针的一个列表
这个函数指针的列表呢
接口是统一的
但是具体的调度的
这个算法的实现是不一样的
那我们说在ucore的设计里面
设计了一种机制
可以用C语言来实现
一种类的表示方式
通过这种方式呢
我们具体完成一个调度算法的实现
然后绑定到ucore里
缺省的调度类里面去
从而可以使得我们的ucore
可以去调用你的这个调度算法
在哪调用呢
为此我们需要
进一步去设置相应的调度点
所谓调度点 或者叫抢占点
就是说当产生一些特殊的事件之后
我们需要去触发
我们的ucore操作系统
去完成一个调度
把这个设置好之后
就完成了整个调度的初始化过程
那接下来我们看一下
当产生了一些事件之后
我们就会在ucore里面
得到这些事件的一些信息
然后就到特定的调度点
去开始做两个事情
一个事情是要调整一些调度的参数
因为我们的调度算法
是基于这些参数来具体的去选择
最后应该选择哪一个进程去执行
还有就是要调用相应的调度算法
这是他们要干的两个事情
当调用调度算法的时候呢
调度算法会做两个事情
第一个是要选择新的进程
第二个完成进程切换
这里面呢 分两种情况
首先是如果有新的一个
优先级更高的进程
那么我们要选择这个进程 选出来
那基于里面的算法
我们可以有不同的选择策略
假定你选出了一个新的进程之后
我们就要进行进程切换
这是一种情况
有新的进程去运行
另一种情况呢
有可能说你这个调度的过程当中
发觉没有就绪进程了
在这种情况下
我们就会切到idle线程去运行
这时候idle线程干什么事呢
它只干一件事情
就是不停的去查询
是否有就绪的进程
如果有 它就做切换
如果没有 它就在不停的查询
做一个循环
这就是说idle线程
在这里面起到新的作用
接下来我们介绍一下调度过程
那么这个调度过程呢
比前面讲的那个总体介绍的过程
稍微要具体一点
那么使得我们可以更清楚的认识到
我们原理课堂讲的那些调度算法
怎么能够在ucore操作系统里面
能够具体的得以执行
首先我们看一下
就是怎么能够产生调度
这里面就涉及到触发的一个过程
第一点我们前面讲到有一些触发点
由于有一些事件的产生
使得这些触发点能够被调用
那么触发点呢
就是最终能激活
调度算法的一个执行
这是第一步
那么一旦调度算法得以执行之后呢
那么它干的第一个事是什么事呢
第一个事就是要把当前的这个进程
放入到就绪队列里面去
这是第一步
第二步呢 从就绪队列里
选取一个 它认为最合适的
一个进程去占用CPU执行
pick up一个process
第三步呢
就是把这个选择的进程呢
从就绪队列里面取出来
因为我们需要把它去做
完成一个接下来的切换
使得当前的进程和我们选出来这个
新的进程能够完成一个switch
一旦完成switch之后呢
我们就可以让这个进程去执行了
所以说这就是
让进程执行的这么一个图示
在这里面我们可以看到
所有处于就绪态的进程
也就是说Runnable的进程
它会在一个队列里面
我们会有专门的数据结构叫run_queue
来管理这个处于就绪态的进程
也就意味着我们这个算法呢
它会从就绪队列里面
选取一个它认为合适的进程去执行
当然还存在另外一种情况
什么情况呢
这个进程呢 它会睡眠或者等待
因为当某一个进程
它需要的资源得不到满足之后
它就会去等待和睡眠
这里面就存在一个所谓的等待队列
或者睡眠队列
来放置这些特殊的进程
那么这两类呢
就形成了我们整个这个
进程的管理的一个过程
那么我们这个lab6呢
它的调度算法这一块
主要设计的是处于就绪态的进程
和正在运行的当前进程
它们之间的一个相互切换的过程
我们的调度算法主要涉及这两块
但是呢 进程
它有其它状态
比如说刚才说得不到资源
它会处于等待或者睡眠的一个状态
以及当进程执行完毕之后
它会退出整个生命周期
那么这两个态呢
其实也和调度是有关系的
但是不太涉及到调度算法
所以说我们重点关注的是
怎么能够从就绪队列里面
选取一个新的进程去占用CPU执行
后续呢 在这一块
会做进一步的展开讲解
-0.1 Piazza讨论区
--html
-0.2 在线实验平台
--实验平台使用帮助
--平台使用帮助
-0.2在线实验平台
--Raw HTML
-1.1 课程概述
--视频
-第一讲 操作系统概述--练习
-1.2 教学安排
--视频
-1.3 什么是操作系统
--Video
-1.4 为什么学习操作系统，如何学习操作系统
--Video
-1.5 操作系统实例
--视频
-1.6 操作系统的演变
--视频
-1.7 操作系统结构
--视频
-2.1 前言和国内外现状
-2.2 OS实验目标
-2.3 8个OS实验概述
-2.4 实验环境搭建
-2.5 x86-32硬件介绍
-2.6 ucore部分编程技巧
-2.7 演示实验操作过程
--Q6
--Q7
--Q10
-3.1 BIOS
--3.1 BIOS
-3.2 系统启动流程
-3.3 中断、异常和系统调用比较
-第三讲 启动、中断、异常和系统调用--3.3 中断、异常和系统调用比较
-3.4 系统调用
--3.4 系统调用
-第三讲 启动、中断、异常和系统调用--3.4 系统调用
-3.5 系统调用示例
-3.6 ucore+系统调用代码
-4.1 启动顺序
--4.1 启动顺序
-4.2 C函数调用的实现
-4.3 GCC内联汇编
-4.4 x86中断处理过程
-4.5 练习一
--4.5 练习一
-4.6 练习二
--4.6 练习二
-4.7 练习三
--4.7 练习三
-4.8 练习四 练习五
-4.9 练习六
--4.9 练习六
-5.1 计算机体系结构和内存层次
-5.2 地址空间和地址生成
-5.3 连续内存分配
-5.4 碎片整理
--5.4 碎片整理
-5.5 伙伴系统
--5.5 伙伴系统
-第五讲 物理内存管理: 连续内存分配--5.6 练习
-6.1 非连续内存分配的需求背景
-6.2 段式存储管理
-- 6.2 段式存储管理
-6.3 页式存储管理
-6.4 页表概述
--6.4 页表概述
-6.5 快表和多级页表
-6.6 反置页表
--6.6 反置页表
-6.7 段页式存储管理
-第六讲 物理内存管理: 非连续内存分配--6.8 练习
-7.1 了解x86保护模式中的特权级
-第七讲 实验二 物理内存管理--7.1 了解x86保护模式中的特权级
-7.2 了解特权级切换过程
-第七讲 实验二 物理内存管理--7.2 了解特权级切换过程
-7.3 了解段/页表
-第七讲 实验二 物理内存管理--7.3 了解段/页表
-7.4 了解UCORE建立段/页表
-第七讲 实验二 物理内存管理--7.4 了解UCORE建立段/页表
-7.5 演示lab2实验环节
-8.1 虚拟存储的需求背景
-8.2 覆盖和交换
-8.3 局部性原理
-8.4 虚拟存储概念
-8.5 虚拟页式存储
-8.6 缺页异常
--8.6 缺页异常
-9.1 页面置换算法的概念
-9.2 最优算法、先进先出算法和最近最久未使用算法
-第九讲 页面置换算法--9.2 最优算法、先进先出算法和最近最久未使用算法
-9.3 时钟置换算法和最不常用算法
-第九讲 页面置换算法--9.3 时钟置换算法和最不常用算法
-9.4 Belady现象和局部置换算法比较
-第九讲 页面置换算法--9.4 Belady现象和局部置换算法比较
-9.5 工作集置换算法
-第九讲 页面置换算法--9.5 工作集置换算法
-9.6 缺页率置换算法
-第九讲 页面置换算法--9.6 缺页率置换算法
-9.7 抖动和负载控制
-10.1 实验目标：虚存管理
-第十讲 实验三 虚拟内存管理--10.1 实验目标：虚存管理
-10.2 回顾历史和了解当下
-第十讲 实验三 虚拟内存管理--10.2 回顾历史和了解当下
-10.3 处理流程、关键数据结构和功能
-第十讲 实验三 虚拟内存管理--10.3 处理流程、关键数据结构和功能
-10.4 页访问异常
-第十讲 实验三 虚拟内存管理--10.4 页访问异常
-10.5 页换入换出机制
-第十讲 实验三 虚拟内存管理--10.5 页换入换出机制
-11.1 进程的概念
-第十一讲 进程和线程--11.1 进程的概念
-11.2 进程控制块
-第十一讲 进程和线程--11.2 进程控制块
-11.3 进程状态
-第十一讲 进程和线程--11.3 进程状态
-11.4 三状态进程模型
-11.5 挂起进程模型
-第十一讲 进程和线程--11.5 挂起进程模型
-11.6 线程的概念
-第十一讲 进程和线程--11.6 线程的概念
-11.7 用户线程
-第十一讲 进程和线程--11.7 用户线程
-11.8 内核线程
-第十一讲 进程和线程--11.8 内核线程
-12.1 进程切换
-第十二讲 进程控制--12.1 进程切换
-12.2 进程创建
-第十二讲 进程控制--12.2 进程创建
-12.3 进程加载
-第十二讲 进程控制--12.3 进程加载
-12.4 进程等待与退出
-第十二讲 进程控制--12.4 进程等待与退出
-13.1 总体介绍
-13.2 关键数据结构
-13.3 执行流程
-13.4 实际操作
-14.1 总体介绍
-14.2 进程的内存布局
-14.3 执行ELF格式的二进制代码-do_execve的实现
--14.3 执行ELF格式的二进制代码-do_execve的实现
-14.4 执行ELF格式的二进制代码-load_icode的实现
--14.4 执行ELF格式的二进制代码-load_icode的实现
-14.5 进程复制
-14.6 内存管理的copy-on-write机制
-15.1 处理机调度概念
-第十五讲 处理机调度--15.1 处理机调度概念
-15.2 调度准则
-15.3 先来先服务、短进程优先和最高响应比优先调度算法
--15.3 先来先服务、短进程优先和最高响应比优先调度算法
-第十五讲 处理机调度--15.3 先来先服务、短进程优先和最高响应比优先调度算法
-15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架
--15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架
-第十五讲 处理机调度--15.4 时间片轮转、多级反馈队列、公平共享调度算法和uc
-15.5 实时调度和多处理器调度
-第十五讲 处理机调度--15.5 实时调度和多处理器调度
-15.6 优先级反置
-第十五讲 处理机调度--15.6 优先级反置
-16.1 总体介绍和调度过程
-16.2 调度算法支撑框架
-16.3 时间片轮转调度算法
-16.4 Stride调度算法
-17.1 背景
--17.1 背景
-17.2 现实生活中的同步问题
-第十七讲 同步互斥--17.2 现实生活中的同步问题
-17.3 临界区和禁用硬件中断同步方法
-第十七讲 同步互斥--17.3 临界区和禁用硬件中断同步方法
-17.4 基于软件的同步方法
-第十七讲 同步互斥--17.4 基于软件的同步方法
-17.5 高级抽象的同步方法
-第十七讲 同步互斥--17.5 高级抽象的同步方法
-18.1 信号量
--18.1 信号量
-第十八讲 信号量与管程--18.1 信号量
-18.2 信号量使用
-第十八讲 信号量与管程--18.2 信号量使用
-18.3 管程
--18.3 管程
-第十八讲 信号量与管程--18.3 管程
-18.4 哲学家就餐问题
-18.5 读者-写者问题
-19.1 总体介绍
-19.2 底层支撑
-第十九讲 实验七 同步互斥--19.2 底层支撑
-19.3 信号量设计实现
-第十九讲 实验七 同步互斥--19.3 信号量设计实现
-19.4 管程和条件变量设计实现
-第十九讲 实验七 同步互斥--19.4 管程和条件变量设计实现
-19.5 哲学家就餐问题
-20.1 死锁概念
-第二十讲 死锁和进程通信--20.1 死锁概念
-20.2 死锁处理方法
-第二十讲 死锁和进程通信--20.2 死锁处理方法
-20.3 银行家算法
-第二十讲 死锁和进程通信--20.3 银行家算法
-20.4 死锁检测
-第二十讲 死锁和进程通信--20.4 死锁检测
-20.5 进程通信概念
-第二十讲 死锁和进程通信--20.5 进程通信概念
-20.6 信号和管道
-第二十讲 死锁和进程通信--20.6 信号和管道
-20.7 消息队列和共享内存
-第二十讲 死锁和进程通信--20.7 消息队列和共享内存
-21.1 文件系统和文件
-第二十一讲 文件系统--21.1 文件系统和文件
-21.2 文件描述符
-第二十一讲 文件系统--21.2 文件描述符
-21.3 目录、文件别名和文件系统种类
-第二十一讲 文件系统--21.3 目录、文件别名和文件系统种类
-21.4 虚拟文件系统
-第二十一讲 文件系统--21.4 虚拟文件系统
-21.5 文件缓存和打开文件
-第二十一讲 文件系统--21.5 文件缓存和打开文件
-21.6 文件分配
-第二十一讲 文件系统--21.6 文件分配
-21.7 空闲空间管理和冗余磁盘阵列RAID
-第二十一讲 文件系统--21.7 空闲空间管理和冗余磁盘阵列RAID
-22.1 总体介绍
-第二十二讲 实验八 文件系统--22.1 总体介绍
-22.2 ucore 文件系统架构
-第二十二讲 实验八 文件系统--22.2 ucore 文件系统架构
-22.3 Simple File System分析
-第二十二讲 实验八 文件系统--22.3 Simple File System分析
-22.4 Virtual File System分析
-第二十二讲 实验八 文件系统--22.4 Virtual File System分
-22.5 I/O设备接口分析
-第二十二讲 实验八 文件系统--22.5 I/O设备接口分析
-22.6 执行流程分析
-23.1 I/O特点
--视频
-第二十三讲 I/O子系统--23.1 I/O特点
-23.2 I/O结构
--816C80A0F5E3B8809C33DC5901307461
-第二十三讲 I/O子系统--23.2 I/O结构
-23.3 I/O数据传输
--C58221E14388B9DB9C33DC5901307461
-第二十三讲 I/O子系统--23.3 I/O数据传输
-23.4 磁盘调度
--567A3F1FCBFB3F4C9C33DC5901307461
-第二十三讲 I/O子系统--23.4 磁盘调度
-23.5 磁盘缓存
--C327536B80D25CE79C33DC5901307461
-第二十三讲 I/O子系统--23.5 磁盘缓存
-html
--html
