16.4 Stride调度算法慕课视频播放-操作系统-MOOC慕课视频教程-柠檬大学

好那我们看看

接下来我们要完成的练习就是

stride scheduling

这是一个我们在原理课

没有讲的一个算法

这个算法呢

来自于一篇比较有名的一个论文

大家有兴趣的话可以看看这篇论文

这边给出了一个相应的链接

当然我们也通过简单的图示

来给大家展示一下

这个算法它大致的一个含义是什么

假定我们现在有三个进程

P1 P2 P3

那么呢每个进程有两个属性

一个属性是什么呢它的步长

就是说它现在执行到了什么地方

你可以把这个理解为一个跑道

可以看出来

这个stride有三个

P1是100 P2是106

P3是102

也就意味着现在最落后的是谁是P1

那么跑的最快的是谁呢 P2

因为它这个106最大的一个值

这是一个参数

就是当前的它的位置

第二个呢

pass 要代表它一次要前进的步数

比如说P1它一次前进的步数是16

P2一次前进的步数是7

P3一次前进的步数是10

那我们这个调度的

算法的策略怎么来选择呢

我们要选择当前

步长最小的一个值的进程去执行它

然后呢它执行的长度是多少呢

是这个当前的步长加上它这个pass

所以说我们可以看到

在这种情况下我们要选择哪个呢

很明显这个P1

它这个当前的步长是最小的

所以我们选择它

然后呢它会去走一段距离

是stride加上pass

我们叫做步进值

一个是步长值

一个是步进值 OK

它到这个位置了

好我们接下来再看一看

当前谁的步长是最小的呢

P3现在是102

所以说我们接下来呢

我们的调度算法应该选择P3

然后它执行的步长是什么呢

10 102加上10等于112

到这个位置

好再接下来是P2

它走的步长会到113这个位置

好这三个进程都走了一轮之后呢

我们接下来再判断

第二轮的时候谁最小呢 P3最小

所以在这个时候应该选择P3去执行

这时候它已经变成122了

再接下来很明显P2执行

然后周而复始来完成这个

所有进程的一个选择让谁去执行

那可以看出来

这里面谁的步进值越小

那么它被调度的次数会越多

大家想想为什么

这给大家留一个思考

那这个算法呢它具有两个特点

它可以基于

进程的优先级来进行调度

那么这个优先级会和

我们的步进长度成一个反比

我们后面会讲到

第二个呢

它整个这个调度的选择是确定的

每一次选择不是

一个随机出现的一个值

而是一个确定的值

所以这个算法具有这两个优势

我们希望大家采取一定的数据结构

和一定的操作过程

来完成对这个算法的一个实现

这里面首先就要选择合适数据结构

为什么呢

因为我们基于数据结构

要完成相应的插入查找删除操作

而这个和我们

这个数据结构紧密联系

到底是取的list还是一个特殊的队列

比如优先队列等等

这些都影响到你后续的

这个算法的实现

那我们完成的步骤

第一步就是选择完数据结构之后呢

你就要去实现里面的

很重要的初始化函数init

从而可以完成对这个相应的队列

数组堆等的初始化

紧接着呢

会基于这种数据结构

来实现入队和出队这么两个函数

这里面再次提醒一下

这个入队出队是一个抽象的概念

它并不代表说

你处理的数据结构

一定要是一个queue

一个队列

第二个呢我们要实现什么呢

就是选择操作

就是到底选择哪一个来

作为接下来占用CPU执行的进程

这是pick_next要完成的工作

假定我们选择了之后呢

接下来还要干的一个事情

是proc_tick

proc_tick是要改变当前的

一个调度的一个参数

是否需要调度了

proc_tick在哪改呢

我们前面也讲到

是在中断的

关于时钟中断处理例程里面

会对这做一定的设置

如果认为当前进程用完了时间片

因为它每一个时钟中断

代表一个时间片的一小部分

当比如说一百个时钟中断

代表一个时间片的话

那么用完了时间片

那么就需要重新调度

这时候就要设置一个调度的一个

我们前面讲的

设置一个调度的变量

叫做need_resched

把它置为1之后呢

在接下来的某一个调度点

就会完成对schedule这个函数的调用

好这前面几个函数执行完之后

我们还要完成一个

入队和出队的一个实现

把这个实现了那我们就认为

我们就把这个关于这个调度算法

最关键的几个函数实现完毕

最后还需要干的一个事情就是

把它的这个调度类设置对

就是在sched_init这个函数里面呢

来设置一个default_sched_class

设置好之后就意味着

我们的schedule函数能够找到

你所设计的这个特定的一个调度类

针对你的这个Stride调度算法的调度类

来完成具体的调度过程

当你完成了上述的函数和相应的一个

关于这个算法的

调度类的一个设置之后呢

我们可以通过执行如下这个命令

make run-priority

来检查你是否正确的实现了这个

stride调度算法

那我们接下来呢

给大家做一些提示

使大家可以比较方便的

来完成这个实验

首先第一点就在于

你怎么选择一个合适的数据结构

那么这个数据结构呢

会有助于你完成针对

stride这个调度算法的

插入删除和选择这么几个操作

这里面可以用前面讲的list

双向链表来完成

也可以用一些更新的一些数据结构

priority queue

这代表是优先队列

那么优先队列呢

又可以用进一步的具体的叫做

斜堆（skew heap）这么一个数据结构

来完成相应的操作

就是哪三个操作呢

插入删除查找

如果采取双向链表

那么它的这个时间开销

是和我们进程个数呈一个线性关系

就O(n)这么一个关系

那它的执行开销比较大

如果我们采取一种新的数据结构

比如说基于斜堆的优先队列的话

那么它的这个执行开销

就是查找删除插入

会比基于双向链表这个开销呢

要优化很多

所以说我们这里可以

采取基于斜堆的优先队列

来完成这么一个数据结构一个组织

那这里面很重要就在于一个比较

因为它是一个堆结构

这个比较函数呢

大家可以看它怎么实现的

有了这个斜堆这么一个结构之后呢

我们就可以完成

关于这个数据结构的初始化

插入移除这么一个操作

那么通过比较呢

能够很快找着当前

最值得去执行的那个进程在哪

它正好是这个堆顶很容易找着

那么进一步我们会去修改

关于进程控制块的这么一个结构

增加一些相关的信息

比如说它有一个针对

斜堆的这么一个运行队列

那么我们会把我们这个

就绪进程呢挂到这个队列里面去

第二个呢这里面有一个stride

代表当前进程它这个步长值是多少

还有是一个优先级

这个优先级什么意思呢

就是说你优先级越高

证明你越有优先执行的权限

它和我们刚才说那个步进值pass

正好起一个反比

优先级越高它的pass值越低

而pass值越低呢

也意味着它有

更多的机会被调度去执行

另外还需要整个队列一个结构

我们还是一个run_queue

但是这里面专门有一个

特殊的叫lab6的run_queue

来完成对这个结构管理和记录

当然这个结构跟前面不太一样

在哪呢

我们前面一般是用list

list entry是一个双向链表

这里面是skew_heap

基于斜堆这么一个数据结构

好这里面还给大家一些提示就是

这个pass和priority

到底什么样一个关系

我们这里面来设置就是pass

等于一个BIG_VALUE / lab6_priority

这个lab6的priority

代表某一个进程它的优先级

这个值可以设置成不一样的

可以设置很大

也可以设置很小

那么BIG_VALUE就可以

设置一个相当大的值

就说有这些priority都不会大于这个BIG_VALUE

使得这个BIG_VALUE除以这个priority

会得到一个pass就是步进值

那步进值越小它前进的越慢

那我们调度时候呢

就会更多的选择这种进程去执行

这也是为什么这个pass和priority

正好是起反比的作用

第二个需要大家注意的是什么呢

这个步长

这个stride这个值呢

随着它不停地累加其实会溢出

你怎么保证这个溢出

不会影响到对这个值判断

比如到底选择哪一个

最小那个stride去执行

这个我们是需要有一些特殊的考虑

大家要想到这里面有一些约束条件

比如说STRIDE_MAX减去STRIDE_MIN

要小于PASS_MAX 这是一个约束条件

第二个呢我们还做一个特定设置

STRIDE和PASS是无符号整数

大家可以关注一下我们数据结构

可以看到都是unit32_t 32位无符号整型

那么有了这个之后呢

我们再做比较的时候

是用的有符号值来比较

那么这一种设计技巧呢

使得我们可以避免出现溢出之后

无法去做正确的判断

到底这个stride

谁大谁小这么一种情况

在这里面大家有必要去

深入理解一下这个stride

的比较是怎么来完成的

在它不停累加情况下

依然能正确的判断出

到底是谁的这个stride值最小

好那前面给大家做了简单介绍

希望大家能够基于这些介绍

能够理解关于这个调度算法的

一个支撑框架怎么来的

第二基于这个支撑框架知道

我们ucore操作系统

在什么时候可以完成

对调度算法一个函数的执行这是一个

第三个希望大家能够

参考Round Robin这个调度算法

来完成对这个stride调度算法的实现

操作系统课程列表：

第零讲在线教学环境准备

-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

16.4 Stride调度算法在线视频