各位同学好
那么我们这次课呢
是讲解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执行
后续呢 在这一块
会做进一步的展开讲解