15.3 先来先服务、短进程优先和最高响应比优先调度算法慕课视频播放-操作系统-MOOC慕课视频教程-柠檬大学

下面我们来介绍调度算法

那么在这里头呢

我们的调度算法呢分成了六种

大致可以分成这样几类

第一类呢关于就绪队列怎么排

然后第二类呢

是关于每一次执行时间

的长短的控制

然后再有后面两种

是关于多种算法

如何把它综合到一起

那首先是这几种算法的一个大致说明

首先是先来先服务算法

这个算法呢它是按着

到就绪队列里的先后顺序来排队的

那我们在找就绪进程的时候

也是按照这个先后顺序来的

跟我们前面讲的FIFO是很相似的

那在那个地方呢

是用来做置换算法的

第二个是说第一种算法它

按先来后到没有考虑到进程的特征

那在这儿第二类呢

就是短进程优先

这里头呢会有几种

稍微有一些小区别的变种

那它们是按照

作业执行时间的长短来进行排队的。

然后第三个是高响应比优先算法

在这个算法里头呢

它考虑的是进程在就绪队列里的等待时间

依据等待时间的长短呢

来考虑它排的这个队的情况

好下面呢是时间片轮转算法

那它是让各个进程

轮流占用一个基本的时间片

然后在这里头

排到就绪队列里头呢

仍然按照我们前面的

先来先服务算法来进行排队

在那基础上呢多了一个

执行时间的最大长度限制

你最长不能执行超过一个时间片

在这之前你可以由于等待

或者结束而让出CPU使用权

而多级反馈队列呢

是把我们的就绪队列排成多个子队列

不同的子队列里头呢

我可以有不同的算法

并且可以在多个队列之间

调整一个进程所排的队列

这样的话就形成了一种综合的算法

而最后的公平共享调度算法呢

它强调的是按照

进程占用的资源的情况来进行调度

保证我们每一个进程

占用的资源呢是相对公平的

好下面我们具体来说每一种算法

首先是先来先服务算法

那这种算法呢

它是按照进程进入就绪状态

的先后顺序来排队

那这是就绪队列里的排法

取的时候怎么办呢

我一个进程在进入等待或者结束

也就说进程主动让出CPU

然后我从就绪队列当中

选择下一个进程占用CPU

那在这种算法里头呢

它的特征是啥样子的

那我们在这儿呢

对它的周转时间做一个分析

假定我有三个进程

它们分别的执行时间是12 3 3

然后假定它们到达的顺序

是这样一个顺序

好那我们按照先来先服务算法的要求

那就是第一个执行完

执行第二个再执行第三个

第一个12 到了12

然后第二个是3 到了15

第三个是3 到了18

好这是我们来看它的周转时间

周转时间假定它们到达的时间

基本上是同一个时刻到达

好那这样它的周转时间

就变成是12 15 18

除以3得15

好这时候我们直观上就感觉到

由于第一个进程执行时间比较长

后面两个等的时间比较长

好这样的话周转时间变得长了

如果说我换一个顺序

假定到达顺序是这样子的

那两个短的在前头

那么这时候它的周转时间是什么样

那周转时间就变成了9

从这两个比较的角度来看呢

我们看到这个算法

它的周转跟你这个

队列到达的时间有很大的关系

如果说你运气不好

排到一个长的执行时间的进程的后面

那么你的等待时间呢那就很长

好这是呢我们这种算法它的特征

它的好处是简单

排队的依据很容易获得

排队过程当中呢也不需要什么变化

所以这种算法比较简单

它的麻烦呢是

平均等待时间波动非常大

也就说如果你一个进程

短的进程排在一个长的进程后面

那你的等待时间就长了

所以这时候呢你排的位置

对你这算法特征呢影响很大

再有一个呢是它资源的利用效率比较低

那你说我一个进程进入等待

另一个马上不就运行了嘛

这时候它怎么会CPU利用效率低呢

那我们看一种情况

说有一个CPU密集型的进程

那这时候它一直算

算的时候它就会

实际上I/O设备的操作

可以和CPU并行的

但是由于你CPU密集型进程呢正在运行

那这时候I/O设备呢就空闲了

那后面如果说你还有

很多要进行I/O的这样一些进程呢

也不会因为你当前CPU占用

然后I/O设备空闲

而让你可以先来执行I/O

好那这样一来

你的I/O设备它的利用效率就低了

好那我们这时候

要想对这种算法做改进

改进怎么办呢

我们排队的时候

刚才说没有考虑到进程的特征

那我们现在呢短进程优先算法

它考虑到进程的特征

考虑到进程什么特征呢

考虑到进程的执行时间

我在选择的时候呢

选择执行时间最短的进程

占用CPU进入运行状态

那这时候说我选择最短的

那这时候就按照预期的执行时间

因为执行时间

我是到执行的时候才会准确的知道

事先我没有办法知道得很准确

我只能是预期

那这个预期就会有一个麻烦

说我在这里头

这是我们的进程状态图

那我们在这里排的什么

实际上排的就是

把这个就绪队列按照这个来排了

好那在这里头呢

这个预期的时间呢

排完之后如果说我这里头

还有一个新的进程到达

并且它预计时间

比当前正在执行的还短怎么办

好那这地方呢就有一个变种

叫短剩余时间优先

好那也就是说相当于

我一个进程正在执行

它预期的执行时间很长

我又来了一个新的进程

它预期的执行时间

比当前正在已经执行了一半的这个进程

剩下那个时间还要短

那这时候我允许它抢先

那就是短剩余时间优先

好那这种算法有些什么样的特征呢

那我们看

它具有一个最优平均周转时间的特征

也就说你别的算法

你的平均周转时间都只能比它长

不会比它短

那我们看它如何得到这个特点的

在这儿呢我们假定有一个序列

是进程的执行时间的序列

好那如果说我按照

由短到长的这个顺序来排

它的执行顺序

那么这时候呢

它得到的周转时间是什么

这个地方ri实际上是

从0到执行完毕这个时间的长度

好我们说这个时间呢

是它的最短时间

那我调整一下顺序

是不是只会比它长吗

那实际上这是可以证明的

那我们看一下

假定我调整

这时候不管你做什么样的调整

都可以转换成一系列的基本调整

我只要保证每一次调整

它的时间你只会变长不会变短

那么你总的时间就不会比我这个还短

那每一个最基本的调整是什么呢

实际上我是把两个对掉

那在这儿呢我把3 4 5倒了一下

那在这里头呢

2 前面两个还是跟原来一样

现在不是执行3了而是执行4

那4呢我倒了一遍之后

这时候它的完成时间是什么

是从这个点减去它的长度

我给了这个表示

然后5呢实际上是从这个地方

5减去3 也就相当于它串到后面来

把它俩往前串了

然后这个P3执行结束呢

本来就是一个r5

为了后边我说起来方便

我把它表示成r3在这个时间

加上这两个的长度

这里C3 C4 C5

都是进程Pi的执行时间。

好有了这个之后

我们继续来算它的平均周转时间

这是把它全加在一起

然后我做一个等式变换

好这时候呢把最后变的这一段加到这儿

那我们看到

由于我们这一个

是按照由小到大排的

所以这里的C3一定是小于C4 C5

所以这个数肯定是一个非负的数

也就说是0或者是一个正数

那么这样一来的话

你这个下面这个周转时间

一定是比上面这个大的

好那从这个角度来讲呢

我们看到短作业优先呢

它可以有最优的平均周转时间

这是它的好的特征

但是它也会有麻烦

它的麻烦是什么呢

如果我一台机器里头

就绪进程不断地产生

不断地产生正在执行

因为你是按照由短到长来排的

那如果说我短的很多

那这么长的就会一直得不到CPU的资源

好那这时候呢就会导致饥饿

也就是说我有一个进程处于就绪状态

由于它声称它的运行时间比较长

好所有的短的作业呢进程呢

都在它前面加塞了

好那这时候它就得不到CPU资源了

好那同时呢

这时候还有一个问题

它需要预知你的执行时间

那我如何来估计CPU的进程

的下一个执行时间长短呢

那这和我们前面做

内存的置换算法的时候

的状态是一样的

我们希望知道未来的情况

但是要知道未来是很麻烦的

好那这时候我们用过去来预测

那实际上在这里头

我们的预测有这样几种办法

第一个我到底要执行多长时间

我去问用户用户你自己来说

这时候就可能有两种情况

一种是说用户

因为我想很快能运行

我告诉你我只需要执行一秒钟

实际上我执行了一分钟

那这时候怎么办呢

那说对于操作系统来讲

你声称你执行多长时间

那你就排到相应队列里头

好那就把你声称时间到了之后

你还没执行完

系统可以把你强行终止掉

那还有一种情况

用户干脆我不知道我会执行多长时间

因为它在某些情况下

它不知道数据处理

到底要什么样的复杂程度

好这种情况怎么办

这时候我们还是有另一种做法

就是用过去预测未来

那这就是执行时间的预估

那怎么来预估呢

就是利用历史信息来预测

预估未来的执行时间

那具体的做法呢是这样的

这是一个小事例

说我在这个程序里呢做一组循环

读数据数据处理那这就相当于I/O

然后进行CPU 执行

那在这个过程当中

我们给出这样一个公式

说我下一次执行时间的预测

在这里头呢

就是这一次的执行时间

你N次的执行时间

前面加上一个衰减系数

然后加上你上一次的预估值

把它俩加在一起

就是你下一次的预估值

就实际上把当前时间

和你上一次预估值做一个校正

好那这时候我得到一个新的预估值

那这一种呢相当于如果我把它展开之后

实际上就是把前面的

每一次的执行时间做衰减

当前最近的这一次呢

它的影响权重是最大的

后面呢以前的个次依次衰减

到一定时间长度之后就可以忽略不计了

这是在这里预测的做法

那这种预测的做法呢

带来的结果是说

这是我实际的执行的过程当中

的每一次占用CPU的时候

进入等待状态之前它的执行时间

好然后在这上头呢我作为一个预测

依据我刚才的公式就是这一条线

那么这一条线

和我们前面这条黄的线

它们俩之间可以有一个比较好的拟合

那这就是我这里用过去

预测未来的预测的结果

好那这是短作业优先算法

然后第三个算法呢是最高响应比优先

那在前面呢

我只是考虑到进程执行时间的因素

那有可能刚才说

短进程优先

会因为长进程等的时间而出现饥饿

那现在呢我为了避免这种情况出现

高响应比优先我是在这里

按照响应比R的值来排序

这个R怎么计算呢

W是你的等待时间

S是你预估的执行时间

那在这里头呢我这个等的时间越长

我R因为它在分子 R会越来越大

等的时间越长

它的优先级越高

那这样的话在一定程度上

就可以避免我们刚才说的

短进程优先里头的

长进程等待时间长的这种情况

而导致出现饥饿

好那么在这种算法里头呢

那它是基于短进程优先算法之上的改进

那在这里头呢它不允许强占

好那这时候呢它关注的是

进程的等待时间好

这时候呢它可以避免无限期的等待

因为你等的时间越长

你的优先级越高

最终你会变成最高优先级

所以你能得到CPU的使用权

好到这个地方呢我们就说清楚了

前面三种关于就绪队列排序的算法

它根据先后到达顺序

执行时间等待时间

这样几个指标来排序

操作系统课程列表：

第零讲在线教学环境准备

-0.1 Piazza讨论区

--piazza访问和使用

--html

-0.2 在线实验平台

-0.2在线实验平台

第一讲操作系统概述

-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.2 系统启动流程

-3.3 中断、异常和系统调用比较

--3.3 中断、异常和系统调用比较

-第三讲启动、中断、异常和系统调用--3.3 中断、异常和系统调用比较

-3.4 系统调用

--3.4 系统调用

-第三讲启动、中断、异常和系统调用--3.4 系统调用

-3.5 系统调用示例

--3.5 系统调用示例

-3.6 ucore+系统调用代码

--3.6 ucore+系统调用代码

第四讲实验一 bootloader启动ucore os

-4.1 启动顺序

-4.2 C函数调用的实现

-4.3 GCC内联汇编

-4.4 x86中断处理过程

-4.5 练习一

-4.6 练习二

-4.7 练习三

-4.8 练习四练习五

-4.9 练习六

第五讲物理内存管理: 连续内存分配

-5.1 计算机体系结构和内存层次

-5.2 地址空间和地址生成

-5.3 连续内存分配

-5.4 碎片整理

-5.5 伙伴系统

-第五讲物理内存管理: 连续内存分配--5.6 练习

第六讲物理内存管理: 非连续内存分配

-6.1 非连续内存分配的需求背景

-6.2 段式存储管理

-6.3 页式存储管理

-6.4 页表概述

-6.5 快表和多级页表

-6.6 反置页表

-6.7 段页式存储管理

-第六讲物理内存管理: 非连续内存分配--6.8 练习

第七讲实验二物理内存管理

-7.1 了解x86保护模式中的特权级

--7.1 了解x86保护模式中的特权级

-第七讲实验二物理内存管理--7.1 了解x86保护模式中的特权级

-7.2 了解特权级切换过程

--7.2 了解特权级切换过程

-第七讲实验二物理内存管理--7.2 了解特权级切换过程

-7.3 了解段/页表

--7.3 了解段/页表

-第七讲实验二物理内存管理--7.3 了解段/页表

-7.4 了解UCORE建立段/页表

--7.4 了解ucore建立段/页表

-第七讲实验二物理内存管理--7.4 了解UCORE建立段/页表

-7.5 演示lab2实验环节

--7.5 演示lab2实验环节

第八讲虚拟存储概念

-8.1 虚拟存储的需求背景

-8.2 覆盖和交换

-8.3 局部性原理

-8.4 虚拟存储概念

-8.5 虚拟页式存储

-8.6 缺页异常

第九讲页面置换算法

-9.1 页面置换算法的概念

--9.1 页面置换算法的概念

-9.2 最优算法、先进先出算法和最近最久未使用算法

--9.2 最优算法、先进先出算法和最近最久未使用算法

-第九讲页面置换算法--9.2 最优算法、先进先出算法和最近最久未使用算法

-9.3 时钟置换算法和最不常用算法

--9.3 时钟置换算法和最不常用算法

-第九讲页面置换算法--9.3 时钟置换算法和最不常用算法

-9.4 Belady现象和局部置换算法比较

--9.4 Belady现象和局部置换算法比较

-第九讲页面置换算法--9.4 Belady现象和局部置换算法比较

-9.5 工作集置换算法

--9.5 工作集置换算法

-第九讲页面置换算法--9.5 工作集置换算法

-9.6 缺页率置换算法

--9.6 缺页率置换算法

-第九讲页面置换算法--9.6 缺页率置换算法

-9.7 抖动和负载控制

--9.7 抖动和负载控制

第十讲实验三虚拟内存管理

-10.1 实验目标：虚存管理

--10.1 实验目标：虚存管理

-第十讲实验三虚拟内存管理--10.1 实验目标：虚存管理

-10.2 回顾历史和了解当下

-- 10.2 回顾历史和了解当下

-第十讲实验三虚拟内存管理--10.2 回顾历史和了解当下

-10.3 处理流程、关键数据结构和功能

--10.3 处理流程、关键数据结构和功能

-第十讲实验三虚拟内存管理--10.3 处理流程、关键数据结构和功能

-10.4 页访问异常

--10.4 页访问异常

-第十讲实验三虚拟内存管理--10.4 页访问异常

-10.5 页换入换出机制

--10.5 页换入换出机制

-第十讲实验三虚拟内存管理--10.5 页换入换出机制

第十一讲进程和线程

-11.1 进程的概念

--11.1 进程的概念

-第十一讲进程和线程--11.1 进程的概念

-11.2 进程控制块

--11.2 进程控制块

-第十一讲进程和线程--11.2 进程控制块

-11.3 进程状态

--11.3 进程状态

-第十一讲进程和线程--11.3 进程状态

-11.4 三状态进程模型

--11.4 三状态进程模型

-11.5 挂起进程模型

--11.5 挂起进程模型

-第十一讲进程和线程--11.5 挂起进程模型

-11.6 线程的概念

--11.6 线程的概念

-第十一讲进程和线程--11.6 线程的概念

-11.7 用户线程

--11.7 用户线程

-第十一讲进程和线程--11.7 用户线程

-11.8 内核线程

--11.8 内核线程

-第十一讲进程和线程--11.8 内核线程

第十二讲进程控制

-12.1 进程切换

--12.1 进程切换

-第十二讲进程控制--12.1 进程切换

-12.2 进程创建

--12.2 进程创建

-第十二讲进程控制--12.2 进程创建

-12.3 进程加载

--12.3 进程加载

-第十二讲进程控制--12.3 进程加载

-12.4 进程等待与退出

--12.4 进程等待与退出

-第十二讲进程控制--12.4 进程等待与退出

第十三讲实验四内核线程管理

-13.1 总体介绍

-13.2 关键数据结构

-13.3 执行流程

-13.4 实际操作

第十四讲实验五用户进程管理

-14.1 总体介绍

--14.1 总体介绍

-14.2 进程的内存布局

--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.5 进程复制

-14.6 内存管理的copy-on-write机制

--14.6 内存管理的copy-on-write机制

第十五讲处理机调度

-15.1 处理机调度概念

--15.1 处理机调度概念

-第十五讲处理机调度--15.1 处理机调度概念

-15.2 调度准则

--15.2 调度准则

-15.3 先来先服务、短进程优先和最高响应比优先调度算法

--15.3 先来先服务、短进程优先和最高响应比优先调度算法

-第十五讲处理机调度--15.3 先来先服务、短进程优先和最高响应比优先调度算法

-15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架

--15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架

-第十五讲处理机调度--15.4 时间片轮转、多级反馈队列、公平共享调度算法和uc

-15.5 实时调度和多处理器调度

--15.5 实时调度和多处理器调度

-第十五讲处理机调度--15.5 实时调度和多处理器调度

-15.6 优先级反置

--15.6 优先级反置

-第十五讲处理机调度--15.6 优先级反置

第十六讲实验六调度器

-16.1 总体介绍和调度过程

-16.2 调度算法支撑框架

-16.3 时间片轮转调度算法

-16.4 Stride调度算法

第十七讲同步互斥

-17.1 背景

--17.1 背景

-17.2 现实生活中的同步问题

--17.2 现实生活中的同步问题

-第十七讲同步互斥--17.2 现实生活中的同步问题

-17.3 临界区和禁用硬件中断同步方法

--17.3 临界区和禁用硬件中断同步方法

-第十七讲同步互斥--17.3 临界区和禁用硬件中断同步方法

-17.4 基于软件的同步方法

--17.4 基于软件的同步方法

-第十七讲同步互斥--17.4 基于软件的同步方法

-17.5 高级抽象的同步方法

--17.5 高级抽象的同步方法

-第十七讲同步互斥--17.5 高级抽象的同步方法

第十八讲信号量与管程

-18.1 信号量

--18.1 信号量

-第十八讲信号量与管程--18.1 信号量

-18.2 信号量使用

--18.2 信号量使用

-第十八讲信号量与管程--18.2 信号量使用

-18.3 管程

--18.3 管程

-第十八讲信号量与管程--18.3 管程

-18.4 哲学家就餐问题

--18.4 哲学家就餐问题

-18.5 读者-写者问题

--18.5 读者-写者问题

第十九讲实验七同步互斥

-19.1 总体介绍

--19.1 总体介绍

-19.2 底层支撑

--19.2 底层支撑

-第十九讲实验七同步互斥--19.2 底层支撑

-19.3 信号量设计实现

--19.3 信号量设计实现

-第十九讲实验七同步互斥--19.3 信号量设计实现

-19.4 管程和条件变量设计实现

--19.4 管程和条件变量设计实现

-第十九讲实验七同步互斥--19.4 管程和条件变量设计实现

-19.5 哲学家就餐问题

--19.5 哲学家就餐问题

第二十讲死锁和进程通信

-20.1 死锁概念

--20.1 死锁概念

-第二十讲死锁和进程通信--20.1 死锁概念

-20.2 死锁处理方法

--20.2 死锁处理方法

-第二十讲死锁和进程通信--20.2 死锁处理方法

-20.3 银行家算法

--20.3 银行家算法

-第二十讲死锁和进程通信--20.3 银行家算法

-20.4 死锁检测

--20.4 死锁检测

-第二十讲死锁和进程通信--20.4 死锁检测

-20.5 进程通信概念

--20.5 进程通信概念

-第二十讲死锁和进程通信--20.5 进程通信概念

-20.6 信号和管道

--20.6 信号和管道

-第二十讲死锁和进程通信--20.6 信号和管道

-20.7 消息队列和共享内存

--20.7 消息队列和共享内存

-第二十讲死锁和进程通信--20.7 消息队列和共享内存

第二十一讲文件系统

-21.1 文件系统和文件

--21.1 文件系统和文件

-第二十一讲文件系统--21.1 文件系统和文件

-21.2 文件描述符

--21.2 文件描述符

-第二十一讲文件系统--21.2 文件描述符

-21.3 目录、文件别名和文件系统种类

--21.3 目录、文件别名和文件系统种类

-第二十一讲文件系统--21.3 目录、文件别名和文件系统种类

-21.4 虚拟文件系统

--21.4 虚拟文件系统

-第二十一讲文件系统--21.4 虚拟文件系统

-21.5 文件缓存和打开文件

--21.5 文件缓存和打开文件

-第二十一讲文件系统--21.5 文件缓存和打开文件

-21.6 文件分配

--21.6 文件分配

-第二十一讲文件系统--21.6 文件分配

-21.7 空闲空间管理和冗余磁盘阵列RAID

--21.7 空闲空间管理和冗余磁盘阵列RAID

-第二十一讲文件系统--21.7 空闲空间管理和冗余磁盘阵列RAID

第二十二讲实验八文件系统

-22.1 总体介绍

--22.1 总体介绍

-第二十二讲实验八文件系统--22.1 总体介绍

-22.2 ucore 文件系统架构

--22.2 ucore 文件系统架构

-第二十二讲实验八文件系统--22.2 ucore 文件系统架构

-22.3 Simple File System分析

--22.3 Simple File System分析

-第二十二讲实验八文件系统--22.3 Simple File System分析

-22.4 Virtual File System分析

--22.4 Virtual File System分析

-第二十二讲实验八文件系统--22.4 Virtual File System分

-22.5 I/O设备接口分析

--22.5 I/O设备接口分析

-第二十二讲实验八文件系统--22.5 I/O设备接口分析

-22.6 执行流程分析

--22.6 执行流程分析

第二十三讲 I/O子系统

-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

--html

15.3 先来先服务、短进程优先和最高响应比优先调度算法在线视频