15.5 实时调度和多处理器调度慕课视频播放-操作系统-MOOC慕课视频教程-柠檬大学

下面我们来讨论实时和多处理机调度

实时调度呢是对时间有要求的调度算法

而多处理机调度呢

是指在有多个处理机的系统里

它的调度算法

那在这里我们只能对它

做一个简要的讨论

实时操作系统是指

它的正确性依赖于时间

和功能两方面的操作系统

也就说你操作系统实践

它不仅仅是要求功能

而且要求在指定的时间内

完成相应的功能

好实时系统呢

它的性能指标要求呢

就是时间约束的及时性

也就相当于

我必须在约定的时间内

完成约定的工作

速度和平均性能相对来说就不重要了

那在这里头呢

它最显著的特征是什么呢

它最显著特征是在于

要求时间约束的可预测性

也就说我必须知道在什么情况下

我的这些时间约束是能够达到的

那在说调度算法之前呢

我们首先来定义一下实时任务

任务是指我要做的一件事情

比如说计算读写文件

或者说信息传递

那对于时间的要求呢

就是它的属性

它有时间的参数在什么时间完成

然后它要占用哪些资源

这是任务的相关属性

那这个属性

我们可以用这样一个图示来表示

首先在一个时刻发出任务请求

好这时候呢我要来

由操作系统来做这件事情

然后呢还有一个呢就是

操作系统的执行时间

我要来处理这个任务的时候

它需要多长时间

然后再有一个就是截止时间

截止时间呢有准确的时刻

和从请求到截止中间这个长度

那分别是相对截止时间

和绝对截止时间

好这是一个实时任务它的要求

然后通常情况下我们在实时系统里呢

它是处理周期性这种类似的任务

这叫周期实时任务

那对于周期实时任务呢

我们可以这样来描述

除了我在这里头有一个请求时间

截止时间和它的长度之外

那还有一个就是它的规律性的重复

那么有了这个规律性的重复之后呢

这件事情我们就会定义这样几个参数

一个是周期它的这个间隔

第一次请求到第二次请求

然后它的执行时间

在这里呢要求是你最大的执行时间

因为中间有可能会快

如果你要想保证实时的话

你必须保证最坏的情况它能算出来

然后再有一个呢就是使用率

我这一块使用

占我整个CPU时间长度来讲

它能占多大比例

那最好是100%，

但实际上100% 很难保证它的实时性

那我多少能保证的

这是其中一个重要指标

好然后在这种情况下

我们对满足实时要求呢

又把它按照要求的强烈程度不同

分成硬实时和软实时

硬实时是指

错过这个时间截止实现

那么这时候呢它就会有灾难性

或者非常严重的后果

所以这时候对系统的要求是

必须验证在最坏的情况下

能够满足这个实现的要求

而软实时呢

是指我系统通常情况下

能够满足任务的实现

如果不满足的话

系统可以降级提供服务

那这时候呢要求系统

尽量保证满足系统任务的实现

但不是必须

好那么我们在实时的系统上

要求系统周期性完成一系列的

周期性的任务

好在这种情况下

我们来定义可调度性

也就相当于我的调度算法

在什么情况下

它是能够满足实现的要求

可调度表示一个实时系统

它能够满足任务的实现要求

那可调度系统呢

我们可以用这样一个图来表述

说我有三个周期性的任务

它们出现的频率

和执行时间是各不相同的

那现在的问题是

在这个系统里头

执行这样三类周期性的任务

它可调度吗

它可以满足这个实现的要求吗

好那如何来判断这个呢

我就需要确定一个任务的执行持续

如果说你能给出一个任务的执行持续

满足所有的任务对实现的要求

那么这时候呢

这个系统就是可调度的

那这样一来我在这里头

给了这个任务之后

我如何能知道

它能不能满足这个可调度性的要求呢

那这时候就是我们这里说的调度算法

那在这儿呢我们有两类

一类是静态一类是动态

静态是指我事先把执行顺序排出来

然后你就照这个调度就行了

我可以从理论上保证

我一定能够满足你的要求

另一种呢动态

动态呢我没有办法事先给出你来

那这时候执行的过程当中我来给

那这时候呢执行的过程当中

我也需要保证

我最后能不能达到它的要求

好那对这两个算法呢

我们做一个简要的介绍

一个呢是静态的调度算法

那叫做速率单调调度算法

它的做法是什么呢

它根据你这个任务的周期

来安排它的优先级

频率越高周期越短的

优先级越高

然后调度的时候呢是

周期越短的先执行

周期越长的后执行

那你说这个调度算法好像很简单

实际上它麻烦的地方在哪呢

麻烦的地方在于

我这个系统里到底

执行多少任务的时候它是可调度的

好那实际上呢我们在这里呢

你有相关的文献可以证明

你在一定的使用率的情况下

速率单调调度算法

是可以满足可调度性要求的

好相关的证明呢

大家可以下去之后看相关的文献

第二种呢是动态调度算法

那这里是最早截止时间优先

那它的思路呢也很简单

告诉你说我截止时间越早的

我优先级越高

那后面已经请求的这几个任务

到底哪一个的截止时间最早

那我先执行最早的

好然后呢执行

截止时间最早的任务

那这个算法就清楚了

好那这时候也有同样的问题

我在什么样的情况下

我有多少个周期性任务的时候

动态调度算法是可调度的

那这些问题呢我都只能是在这里提出

详细的内容

希望有兴趣的同学

下去之后阅读相关的文献

多处理机调度是指

在有多个处理器的系统当中

它的调度算法

那多处理器调度呢

它的特征有这样几条

首先第一个它是针对

多个处理机组成的系统

然后在这上头呢

一条系统总线上连了多个物理的CPU

每个CPU里可能有多个逻辑的核

然后在这里头

我们来做它的调度算法

那这个调度算法

可以在各个处理器之间呢

实现负载共享

好那么我们现在

用的最多的一类系统呢

是对称多处理机系统

在对称多处理机系统上的调度算法呢

通常有这样一些特点

一个是说每个处理机

有自己的调度程序

各自进行调度

然后它们之间

访问共享的资源的时候需要同步

实际上对于多处理机调度来说

同步是其中很大的一个问题

多处理机调度算法

其中很重要一个问题就是进程分配

我们把一个进程

到底放到哪个处理机上运行

那在这里呢分配的办法有两类

一类叫做静态进程分配

那么这时候呢

进程是从一开始执行

就把它分配到一个固定的CPU上运行

一直到它结束

在这儿中间呢它不会切换

好对于这种情况呢

每个处理机呢有自己的队列

也就相当于我在起头的时候有一个分配

然后就变成是一个单处理机的

系统上的调度算法了

好这时候呢相对来说它的开销比较小

因为每一个进程在调度的时候呢

只需要管自己一个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.5 实时调度和多处理器调度在线视频