分类
操作系统

虚拟内存

传统存储管理方式的特征、缺点

  • 一次性作业必须一次性全部装入内存后才能开始运行。这会造成两个问题:
    • 作业很大时,不能全部装入内存,导致大作业无法运行(比如60G大小的GTA5无法在8G内存的电脑运行);
    • 当大量作业要求运行时,由于内存无法容纳所有作业,因此只有少量作业能运行,导致多道程序并发度下降
  • 驻留性:一旦作业被装入内存,就会一直驻留在内存中,直至作业运行结束。事实上,根据局部性原理,在一个时间段内,只需要访问作业的一小部分数据即可正常运行,这就导致了内存中会驻留大量的、暂时用不到的数据,浪费了宝贵的内存资源。

虚拟内存的定义和特征

基于局部性原理,在程序装入时可以将程序中很快会用到的部分装入内存,暂时用不到的部分留在外存,就可以让程序开始执行。

在程序执行过程中,当所访问的信息不在内存时,由操作系统负责将所需信息从外存调入内存,然后继续执行程序。

若内存空间不够,由操作系统负责将内存中暂时用不到的信息换出到外存

在操作系统管理下,在用户看来似乎由一个比实际内存大得多的内存,这就是虚拟内存

易混知识点

  • 虚拟内存的最大容量是由计算机的地址结构(CPU寻址范围)确定的
  • 虚拟内存的实际容量 = min(内存和外存容量之和, CPU寻址范围)

虚拟内存有以下三个主要特征:

  • 多次性:无需在作业运行时一次性全部装入内存,而是允许被分成多次调入内存
  • 对换性:在作业运行时无需一直常驻内存,而是允许在作业运行过程中,将作业换入、换出
  • 虚拟性:从逻辑上扩充了内存的容量,使用户看到的内存容量,远大于实际容量

如何实现虚拟内存技术

虚拟内存技术,允许一个作业分多次调入内存。如果采用连续分配方式,会不方便实现。因此,虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。

传统的非连续分配存储管理 虚拟内存的实现
基本分页存储管理 请求分页存储管理
基本分段存储管理 请求分段存储管理
基本段页式存储管理 请求段页式存储管理

主要区别:

  • 在程序执行过程中,当访问的信息不在内存时,由操作系统负责将所需信息从外存调入内存,然后继续执行程序
    • 操作系统要提供请求调页(或请求调段)功能
  • 若内存空间不够,由操作系统负责将内存中暂时用不到的信息换出到外存
    • 操作系统要提供页面置换(或段置换)的功能

请求分页管理方式

页表机制

与基本分页管理相比,请求分页管理中,为了实现”请求调页“,操作系统需要知道每个页面是否已经调入内存;如果还没调入,那么也需要知道该页面在外存中存放的位置。

当内存空间不够时,要实现”页面置换“,操作系统需要通过某些指标来决定到底置换出哪个页面;有的页面没有被修改过,就不用再浪费时间写回外存。有的页面被修改过,就需要将外存中的旧数据覆盖,因此,操作系统也需要记录各个页面是否被修改的信息。

请求分页存储管理的页表(请求页表)新增加了四个字段:

  • 内存块号(原本就有的)
  • 状态位:是否已调入内存
  • 访问字段:可记录最近被访问过几次,或记录上次访问的时间,供置换算法选择换出页面时参考。
  • 修改位:页面调入内存后是否被修改过
  • 外存地址:页面在外存中存放位置

缺页中断机制

缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的,因此属于内中断

一条指令在执行期间,可能产生多次缺页中断。(如 copy A to B,即将逻辑地址A中的数据复制到逻辑地址B,而A、B属于不同的页面,则有可能产生两次中断)

  • 在请求分页系统中,每当要访问的页面不在内存时,便产生一个缺页中断,然后由操作系统的缺页中断处理程序处理中断。此时缺页的进程阻塞,放入阻塞队列,调页完成后再将其唤醒,放回就绪队列。
  • 如果内存中有空闲块,则为进程分配一个空闲块,将所缺页面装入该块,并修改页表中相应的页表项
  • 如果内存中没有空闲块,则由页面置换算法选择一个页面淘汰,若该页面在内存期间被修改过,则要将其写回外存。未修改过的页面不用写回外存。

中断的分类

  • 内中断(内部异常)——信号来源:CPU内部
    • 陷阱、陷入(trap):有意为之的异常,如系统调用
    • 故障(fault):由错误条件引起的,可能被故障处理程序修复,如缺页中断
    • 终止(abort):不可恢复的知名错误造成的结果,终止处理程序不再将控制返回给引发终止的应用程序,如整数除0
  • 外中断——信号来源:CPU外部
    • I/O中断请求
    • 人工干预

地址变换机构

新增步骤

  • 新增步骤1:请求调页(查到页表项时进行判断,当该页面不在内存中时,需要请求调页)
  • 新增步骤2:页面置换(当没有空闲内存块,且需要调入页面时进行页面置换)
  • 新增步骤3:需要修改请求页表中新增的表项(移入移出内存、访问、修改)


页面置换算法

最佳置换算法(OPT)

最佳置换算法(OPT,Optimal):每次选择淘汰的页面将是以后永不使用,或者在最长时间内不再被访问的页面,这样可以保证最低的缺页率。

最佳置换算法可以保证最低的缺页率,但实际上,只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此,最佳置换算法是无法实现的

先进先出置换算法(FIFO)

先进先出置换算法(FIFO):每次选择淘汰的页面最早进入内存的页面

实现方法:把调入内存的页面根据调入的先后顺序排成一个队列,需要换出页面时选择对头页面即可。

队列的最大长度取决于系统为进程分配了多少个内存块

Belady异常:当为进程分配的物理块数增大时,缺页次数不减反增的异常现象。

只有FIFO算法会产生Belady异常。另外,FIFO算法虽然实现简单,但是该算法与进程实际运行时的规律不适应,因为先进入的页面也有可能最经常被访问。因此,算法性能差

最近最久未使用置换算法(LRU)

最近最久未使用置换算法(LRU, Least Recently Used):每次淘汰的页面最近最久未使用的页面

实现方法:赋予每个页面对应的页表项中,用访问字段记录该页面自上次被访问以来所经历的时间t,当需要淘汰一个页面时,选择现有页面中t值最大的,即最近最久未使用的页面。

该算法的实现需要专门的硬件支持,虽然算法性能好,但是实现困难,开销大

时钟置换算法(CLOCK)

时终置换算法是一种性能和开销较均衡的算法,又称CLOCK算法,或最近未用算法(NRU,Not Recently Used)

简单的CLOCK算法实现方法:为每个页面设置一个访问位,再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时,其访问位置为1。当需要淘汰一个页面时,只需检查页的访问位。如果是0,就选择该页换出;如果是1,则将它置为0,暂不换出,继续检查下一个页面,若第一轮扫描中所有页面都是1,则将这些页面的访问位依次置0后,再进行第二轮扫描(第二轮扫描中一定会有访问位为0的页面,因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描

改进型的时钟置换算法

简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上,如果被淘汰的页面没有被修改过,就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时,才需要写回外存

因此,除了考虑一个页面最近有没有被访问过外,操作系统还应考虑页面有没有被修改过。在其他条件都相同时,应优先淘汰没有被修改过的页面,避免I/O操作。这就是改进型的时钟置换算法的思想。

修改位=0,表示页面没有被修改过;修改位=1,表示页面被修改过。

为了方便描述,用(访问位,修改位)的形式表示各页面状态。如(1,1)表示一个页面最近被访问过,且被修改过。

算法规则:将所有可能被置换的页面拍成一个循环队列

  • 第一轮:从当前位置开始扫描到第一个(0,0)的帧用于替换。本轮扫描不修改任何标志位
  • 第二轮:若第一轮扫描失败,则重新扫描,查找第一个(0,1)的帧用于替换。本轮将所有扫描过的帧访问位设为0
  • 第三轮:若第二轮扫描失败,则重新扫描,查找第一个(0,0)的帧用于替换。本轮扫描不修改任何标志位
  • 第四轮:若第三轮扫描失败,则重新扫描,查找第一个(0,1)的帧用于替换

由于第二轮已将所有的帧的访问位设为0,因此经过第三轮、第四轮扫描一定会有一个帧被选中,因此改进型CLOCK置换算法选择淘汰一个页面最多会进行四轮扫描

淘汰的优先级:

  1. 最近没访问,且没修改过的页面
  2. 最近没访问,但修改过的页面
  3. 最近访问过,但没修改过的页面
  4. 最近访问过,且修改过的页面
算法规则 优缺点
OPT 优先淘汰最长时间内不会被访问过的页面 缺页率最小,性能最好;但无法实现
FIFO 优先淘汰最先进入内存的页面 实现简单;但性能很差,可能出现Belady异常
LRU 优先淘汰最近最久没访问过的页面 性能很好;但需要硬件支持,算法开销大
CLOCK(NRU) 循环扫描各页面,第一轮淘汰访问位=0的,并将扫描过的页面访问位置为1.若第一轮没选中,则进行第二轮扫描 实现简单,算法开销小;但未考虑页面是否被修改过
改进型CLOCK(改进型NRU) 若用(访问位,修改位)的形式表述,则:第一轮淘汰(0,0);第二轮淘汰(0,1),并将扫描过的页面访问位都置0;第三轮淘汰(0,0);第四轮淘汰(0,1) 算法开销较小,性能也不错

页面分配策略

页面分配、置换策略

  • 驻留集:指请求分页存储管理中给进程分配的物理块的集合。
    • 在采用了虚拟存储技术的系统中,驻留集大小一般小于进程的总大小。
    • 若驻留集太小,会导致缺页频繁,系统要花大量的时间来处理缺页,实际用于进程推进的时间很少;
    • 若驻留集太大,又会导致多道程序并发度下降,资源利用率低。所以应该选择一个合适的驻留集大小。
  • 固定分配:操作系统为每个进程分配一组固定数目的物理块,在进程运行期间不再改变。即,驻留集大小不变
  • 可变分配:先为每个进程分配一组固定数目的物理块,在进程运行期间,可根据情况做适当的增加或减少。即,驻留集大小可变
  • 局部置换:发生缺页时只能选进程自己的物理块进行置换。
  • 全局置换:可以将操作系统保留的空闲物理块分配给缺页进程,也可以将别的进程持有的物理块置换到外存,再分配给缺页进程。
局部置换 全局置换
固定分配
可变分配

全局置换意味着一个进程拥有的物理块数量必然会改变,因此不可能是固定分配

何时调入页面

  1. 预调页策略:根据空间局部性原理,一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没有被访问过,则又是低效的。因此可以预测不久之后可能访问到的页面,将它们预先调入内存,但目前预测成功率只有50%作业。故这种策略主要用于进程的首次调入,由程序员指出应该先调入哪些部分。
  2. 请求调页策略:进程在运行期间发现缺页时才将所缺页面调入内存。由这种策略调入的页面一定会被访问到,但由于每次只能调入一页,而每次调页都要磁盘I/O操作,因此I/O开销较大。

抖动(颠簸)现象

刚刚换出的页面马上又要换入内存,刚刚换入的页面马上又要换出到外存,这种频繁的页面调度行为称为抖动,或颠簸。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数(分配给进程的物理块不够

工作集

分类
操作系统

段页式管理

分页、分段管理方式中最大的优缺点

优点 缺点
分页管理 内存空间利用率高,不会产生外部碎片,只会有少量的页内碎片 不方便按照逻辑模块实现信息的共享和保护
分段管理 很方便按照逻辑模块实现信息的共享和保护 如果段长过大,为其分配很大的连续空间会很不方便。另外,段式管理会产生外部碎片

分段+分页的结合——段页式管理方式

将进程按逻辑模块分段,再将各段分页(如每个页面4KB)

再将内存空间分为大小相同的内存块/页框/物理块

将各页面分别装入各内存块中

段页式系统的逻辑地址结构由段号、页号、页内地址(页内偏移量)组成

段内地址分为页号和页内偏移量

段页式管理的地址结构是二维的

  • 段号的位数决定了每个进程做多可以分几个段
  • 页号位数决定了每个段最大由多少页
  • 页内偏移量决定了页面大小、内存块大小是多少

段表、页表

在段页式管理中,一个进程对应一个段表,这个段表中的每个段又对应一个页表,因此一个进程对应一个段表,但可能对应多个页表。

在段页式管理中,每个段表项由段号、页表长度、页表存放块(页表起始地址)组成。每个段表项长度相等,段号是隐含的

每个页面对应一个页表项,每个页表项由页号、页面存放的内存块号组成。每个页表项长度相等,页号是隐含的。


如何实现地址变换

  1. 由逻辑地址得到段号、页号、页内偏移量
  2. 段号与段表寄存器中的段长度比较,检查是否越界
  3. 由段表始址、段号找到对应段表项
  4. 根据段表中记录的页表长度,检查页号是否越界
  5. 由段表中的页表地址、页号得到查询页表,找到相应页表项
  6. 由页面存放的内存块号、页内偏移量得到最终的物理地址
  7. 访问目标单元

需要三次访存

  1. 查段表
  2. 查页表
  3. 访问目标单元

可引入快表机制,以段号和页号为关键字查询快表,即可直接找到最终的目标页面存放位置。引入快表后仅需一次访存。

分类
操作系统

基本分段存储管理方式

什么是分段(类似分页管理中的“分页”)

就如汇编中的段

进程的地址空间:按照程序自身的逻辑关系划分为若干个段,每个段都有一个段名(在低级语言(如汇编)中,程序员使用段来编程),每段从0开始编址

内存分配规则:以段为单位进行分配,每个段在内存中占连续的存储空间,但各段之间可以不相邻

  • 由于是按照逻辑功能模块划分,用户编程更方便,程序的可读性更高
  • 编译程序会将段名转换为段号
  • 段号的位数决定了每个进程最多可以分几个段
  • 段内地址位数决定了每个段的最大长度是多少

什么是段表(类似分页管理中的“页表”)

程序分多个段,各段离散地装入内存,为了保证程序能正常运行,就必须能从物理内存中找到各个逻辑段的存放位置。为此,需为每个进程建立一张段映射表,简称为“段表”。

  • 每个段对应一个段表项,其中记录了该段在内存中的起始位置(又称“基址”)和段的长度
  • 各个段表项的长度是相同的。(段号可以是隐藏的,不占存储空间

如何实现地址变换

分段和分页最大的差别:分段的段长是可变的,而分页的页长是固定的,因此,分段需要对逻辑地址中的段内地址进行检查,看是否超过了该段所在段表项中的段长;而分页就不需要检查。

  1. 由逻辑地址得到段号、段内地址
  2. 段号与段表寄存器中的段长度比较,检查是否越界
  3. 由段表始址、段号找到对应段表项
  4. 根据段表中记录的段长,检查段内地址是否越界
  5. 由段表中的”基址+段内地址“得到最终的物理地址
  6. 访问内存中的目标单元

分段、分页管理的对比

  • 信息的物理单位。分页的主要目的是为了实现离散分配,提高内存的利用率。分页仅仅是系统管理上的需要,完全是系统的行为,对用户是不可见的
  • 信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的,用户编程时需要显式地给出段名。
  • 页的大小是固定的且由系统决定。段的长度不固定,取决于用户编写的程序。
  • 分页的用户进程地址空间是一维的,程序员只需要给出一个记忆符即可表示一个地址。
  • 分段的用户进程地址空间是二维的,程序员在标识一个地址时,既要给出段名,又要给出段内地址。
  • 分段比分页更容易实现信息的共享和保护。不能被修改的代码称为纯代码可重入代码(不属于临界资源),这样的代码是可以共享的。可修改的代码时不能共享的(比如这个段中有很多变量,各进程并发地同时访问可能造成数据不一致)。
  • 访问一个逻辑地址需要几次访存?
  • 分页(单级页表,不考虑快表TLB): 第一次访存——查内存中的页表,第二次访存——访问目标内存单元
  • 分段:第一次访存——查内存中的段表,第二次访存——访问目标内存单元。
  • 与分页系统类似,分段系统中也可以引入快表机构,将近期访问过的段表项放到快表中,这样可以少一次访存,加快地址变换速度。
分类
操作系统

分页存储管理的基本概念

将内存分为一个个大小相等的分区(比如:每个分区4KB),每个分区就是一个”页框“,或称”页帧”、“内存块”、“物理块”。 每个页框有一个编号,即“页框号”(或者“内存块号”、“页帧号”、“物理块号”)页框号从0开始

将用户进程的地址空间页分为与页框大小相等的一个个区域,称为“”或“页面“。每个页面也有一个编号,即”页号”,页号也是从0开始

如何实现地址的转换

  1. 要计算出逻辑地址对应的页号
  2. 要知道该页号对应页面在内存中的起始地址
  3. 要算出逻辑地址在页面内的“偏移量”
  4. 物理地址 = 页面始址 + 页内偏移量

如何计算

  • 页号 = 逻辑地址 / 页面长度 (取除法的整数部分)
  • 页内偏移量 = 逻辑地址 \% 页面长度 (取余)
  • 页面在内存中的起始位置 = 内存块的块号 * 内存块的大小

页表

为了能知道进程的每个页面在内存种存放的位置,操作系统要为每个进程建立一张页表

  1. 一个进程对应一张页表
  2. 进程的每一页对应一个页表项
  3. 每个页表项由“页号”和“块号”组成
  4. 页表记录进程页面和实际存放的内存块之间的对应关系
  5. 在内存中,页表项的长度是相同的,页号是”隐含“的

内存块的起始地址 = 内存块的块号 * 内存块大小

易混概念

  • 页表长度:这个页表中总共有几个页表项,即总共有几个页
  • 页表项长度:每个页表项占多大存储空间
  • 页面大小:一个页面占多大的存储空间

基本地址变换机制

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。

通常会在系统中设置一个页表寄存器(PTR),存放页表在内存中的起始地址F页表长度M

进程未执行时,页表的始址 和 页表长度 放在进程控制块(PCB)中,当进程被调度时,操作系统内核会把它们放到页表寄存器中。

地址变换过程

  1. 根据逻辑地址算出页号、页内偏移量
  2. 页号的合法性检查(与页表长度对比)
  3. 若页号合法,再根据页表起始地址、页号找到对应页表项 (CPU第一次访问内存:查页表)
  4. 根据页表项中记录的内存块号、页内偏移量 得到最终的物理地址
  5. 访问物理内存对应的内存单元 (CPU第二次访问内存:访问目标内存单元)

具有快表的地址变换机构

什么是快表

快表,又称联想寄存器(TLB),是一种访问速度比内存快的多的高速缓冲存储器,用来存放当前访问的若干页表项,以加速地址变换的过程。与此对应,内存中的页表常称为慢表

有点类似于Cache,当CPU要将逻辑地址转换为物理地址中时,先会去TLB中找这个页号对应的内存块号,如果没找到的话再去内存中的页表找这个页号对应的内存块号,并且会将内存中页表的这个页表项复制到TLB中。

局部性原理

  • 时间局部性:如果执行了程序中的某条指令,那么不久后这条指令很可能再次执行;如果某个数据被访问过,不久后该数据很可能再次被访问。(因为程序中存在大量的循环)
  • 空间局部性:一旦程序访问了某个存储单元,在不久之后,其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的)

引入快表后,地址的变换过程

  1. CPU给出逻辑地址,由某个硬件算得页号、页内偏移量,将页号与快表TLB中的所有页号进行比较。
  2. 如果找到匹配的页号,说明要访问的页表项在快表中有副本,则直接从中取出该页对应的内存块号,再将内存块号与页内偏移量拼接形成物理地址,最后,访问该物理地址对应的内存单元。因此,若快表命中,则访问某个逻辑地址仅需要一次访存即可。
  3. 如果没有找到匹配的页号,则需要访问内存中的页表,找到页面存放的内存块号,再将内存块号与页内偏移量拼接形成物理地址,最后访问该物理地址对应的内存单元。因此,若快表未命中,则访问某个逻辑地址需要两次访存注意:在找到页表项后,需要将该页表项放入快表中,以便以后可能的再次访问。但如果快表已满,则需要按照一定的算法对旧的页表项进行替换)

两级页表

单极页表存在什么问题?如何解决

  • 问题一:页表必须连续存放,因此当页表很大时,需要占用很多个连续的页框

    当某个进程占用内存较大时候,将会使用到很多页,也就会在页表中有很多页表项,而查询页表的方法(页表项的位置 = 页表始址 + K*页表项大小)需要所有的页表项都连续存放。 这样将占用较大的一块连续内存存放页表,这将失去了内存中离散存放的优点。

  • 问题二:没有必要让整个页表常驻内存,因为进程在一段时间内可能只需要访问几个特定的页面

    根据局部性原理,很多时候,进程在一段时间内只需要访问某几个页面就可以正常运行了。因此没有必要让所有的整个页表都常驻内存

问题一的解决办法:

​ 创建页表的页表,即页目录表,又称顶级页表、外层页表,原来的页表称为二级页表,将二级页表中能够满足一个页面大小数量的页表项当作一个页面,并将此页面的页表项存放到页目录表中。

问题二的解决办法

​ 可以在需要访问页面时才把页面调入内存(虚拟存储技术)。可以在页表项中增加一个标志位,用于表示该页面是否已经调入内存。 若想访问的页面不在内存中,则产生缺页中断(内中断),然后将目标页面从外存中调入内存。

两级页表问题需要注意的几个细节

  1. 采用多级页表机制,则各级页表的大小不能超过一个页面。若两级页表不够,可以分更多级。

  2. 两级页表的访存次数分析(假如没有快表机构)

    第一次访存:访问内存中的页目录表

    第二次访存:访问内存中的二级页表

    第三次访存:访问目标内存单元

分类
操作系统

动态分区分配算法

动态分区分配算法:在动态分区分配方式中,当很多个空闲分区都能满足需求时,应该选择哪个分区进行分配

1. 首次适应算法(First Fit)

  • 算法思想:每次都从低地址开始查找,找到第一个能满足大小的空闲分区

  • 如何实现:空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。

    首次适应算法每次都要从头查找,每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分又更小的分区可以满足需求时,会更有可能用到低地址部分的小分区,也会更又可能把高地址部分的大分区保留下来(暗含了最佳适应算法的优点)。


2. 最佳适应算法(Best Fit)

  • 算法思想:由于动态分区分配是一种连续分配方式,为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间,可以尽可能多地留下大片的空闲区,即,优先使用更小的空闲区。
  • 如何实现:空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
  • 缺点:每次都选最小的分区进行分配,会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。

3. 最坏适应算法(Worst Fit)

又称最大适应算法(Largest Fit)

  • 算法思想:为了解决最佳适应算法的问题——即留下太多难以利用的小碎片,可以在每次分配时优先使用最大的连续空闲区,这样分配后剩余的空闲区就不会太小,更方便使用。
  • 如何实现:空闲分区按照容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区(也就是最大容量的空闲分区)。
  • 缺点:每次都选择最大的分区进行分配,虽然可以让分配后留下的空闲区更大,更可用,但是这种方式会导致较大的连续空闲区被迅速用完。如果之后又“大进程”到达,就没有内存分区可用了。

4. 临近适应算法(Next Fit)

  • 算法思想:首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区,而每次分配查找时,都要经过这些分区,因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索,就能解决上述问题。

  • 如何实现:空闲分区以地址递增的顺序排列(可拍成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空心啊分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。

    临近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用,也就导致了高地址部分的大分区更可能被使用,划分为小分区,最后导致无大分区可用(最大适应算法的缺点)。


综合来看,四种算法中,首次适应算法的效果反而最好

分类
web

通过使用JAVA发送邮件

最近因为JavaWeb的注册的作业,手机号比较麻烦,所以想着用邮箱来验证。但我去网上搜的一些教程很多都是有一些jar包不完整,导致出现各种问题。

开头先给出发邮件需要用到的jar包 activation.jarcommons-email-1.5.jarmail.jar 可自行下载。

在project下创建一个lib文件夹(如果是JavaWeb的话则需要在WEB-INF文件夹下创建lib文件夹),然后将这三个文件放入lib文件夹下,并将其

  1. 在项目下创建一个lib文件夹(如果是JavaWeb的话则需要在WEB-INF文件夹下创建lib文件夹)
    创建文件夹
    JavaWeb下:
    javaWeb

  1. 将这三个jar包复制粘贴到lib文件夹中

  1. 将这三个jar包 Add as Library (添加为依赖)

  1. 输入代码

    • 发送最基本的纯文字邮件
    
    import org.apache.commons.mail.EmailException;
    import org.apache.commons.mail.SimpleEmail;
    
    public class SendEmail {
       public static void send(String receiver, String content) throws EmailException {
               SimpleEmail email = new SimpleEmail();
               email.setHostName("smtp.exmail.qq.com");    // 设置邮件发送服务器
               email.setAuthentication("example@gamil", "password");    //设置邮箱账号密码
               email.addTo(receiver);    //设置收件人邮箱
               email.setFrom("example@gmail.com");    //设置发件人
               email.setSubject("Hello");    //邮件主题
               email.setMsg(content);
               email.send();
       }
    
    public static void main(String[] args) throws EmailException {
       String receiver = "example@qq.com";
       String content = "你好";
       send(receiver, content);
    }
    }

  1. 注意:
  • email.setAuthentication("example@gamil", "password"); //设置邮箱账号密码 这里面的密码通常为授权码,比如QQ邮箱就需要扫码获得授权码,而不是QQ密码。
  • 这个邮件功能需要将邮箱的smtp开启,并将发送服务器更改为对应邮箱服务商提供的地址。email.setHostName("smtp.exmail.qq.com"); // 设置邮件发送服务器
分类
操作系统

进程调度算法

一、进程调度算法的评价指标

  1. cpu利用率:

    利用率=cpu忙碌时间/总时间

  2. 系统吞吐量:

    系统吞吐量=总共完成了多少道作业/总共花费的时间

  3. 周转时间:

    1. 周转时间: 周转时间=作业完成时间-作业提交时间
    2. 平均周转时间: 平均周转时间=各作业周转时间之和/作业数量
    3. 带权周转时间: 带权周转时间=作业周转时间/作业实际运行的时间
    4. 平均带权周转时间: 平均带权周转时间=各作业带权周转时间之和/作业数量
  4. 等待时间:

    进程/作业 等待被服务的时间之和

    平均等待时间即各个 进程/作业 等待时间的平均值

  5. 响应时间:

    从用户提交请求到首次产生响应所用的时间


二、调度算法(早期批处理系统)

Tips:各种调度算法的学习思路

  • 算法思想
  • 算法规则
  • 这种调度算法是用于作业调度还是进程调度
  • 抢占式?非抢占式?
  • 优点核缺点
  • 是否会导致饥饿(某进程/作业长期得不到服务)

1. 先来先服务(FCFS)

image-20200325150609731

2. 短作业优先(SJF)

  1. 短作业/进程优先调度算法:每次调度时选择当前已到达运行时间最短的作业/进程。

  2. 最短剩余时间优先算法:每当有进程加入就绪队列改变时就需要调度,如果新到达的进程剩余时间比当前运行时间的进程剩余时间更短,则由新进程抢占处理机,当前运行进程重新回到就绪队列。另外,当一个进程完成时也需要调度

    image-20200325152858734

3. 高响应比优先

响应比: 响应比=(等待时间+要求服务时间)/要求服务时间

高响应比优先算法规则:在每次调度时先计算各个作业/进程的相应比,选择相应比最高的作业/进程为其服务

image-20200325154733465


知识回顾

image-20200325154848100


三、调度算法(交互式系统)

1. 时间片轮转调度算法(RR)——常用于分时操作系统

算法规则:按照各进程到达就绪队列的顺序,轮流让各个进程执行一个时间片(如100ms)。若进程未在一个时间片内执行完,则剥夺处理机,将进程重新放到就绪队列队尾重新排队。

如果时间片太大,使得每个进程都可以在一个时间片内就完成,则时间片轮转调度算法退化为先来先服务调度算法,并且会增大进程响应时间。因此时间片不能太大

如果时间片太小,进程调度、切换是有时间代价的(保存、恢复运行环境),因此如果时间片太小,会导致进程切换过于频繁,系统会花大量的时间来处理进程切换,从而导致实际用于进程执行的时间比例减小。

image-20200325163257508

2. 优先级调度算法

算法规则:每个作业/进程有各自的优先级,调度时选择优先级最高的作业/进程

抢占式的优先级调度算法:每次调度时选择当前已到达优先级最高的进程。当前进程主动放弃处理机时发生调度。另外,当就绪队列发生改变时也需要检查是否会发生抢占。

非抢占的优先级调度算法:每次调度时选择当前已到达优先级最高的进程。仅在当前进程主动放弃处理机时发生调度。

优先级调度算法的补充:

  • 就绪队列未必只有一个,可以按照不同优先级来组织。另外,也可以把优先级高的进程排在更靠近就绪队列队头的位置
  • 根据优先级是否可以动态改变,可将优先级分为静态优先级动态优先级两种。
  • 静态优先级:创建进程时确定,之后一直不变。
  • 动态优先级:创建进程时有一个初始值,之后会根据情况动态地调整优先级。
    • 系统进程优先级高于用户进程
    • 前台进程优先级高于后台进程
    • 如果某进程在就绪队列中等待了很长时间,则可以适当提高其优先级
    • 如果某进程占用处理机运行了很长时间,则可以适当降低其优先级
    • 如果一个进程频繁地进行I/O操作,则可适当提升其优先级
    • 操作系统更偏好于I/O型进程(或称I/O繁忙型进程)
    • I/O设备和CPU可以并行工作。如果优先让I/O繁忙型进程优先运行的话,则越有可能让I/O设备尽早地投入工作,则资源利用率、系统吞吐量都会得到提升。
    • 注:与I/O型进程相对的是计算型进程(或称CPU繁忙型进程)

image-20200325171035937

3. 多级反馈队列调度算法

算法规则:

  1. 设置多级就绪队列,各级队列优先级从高到低,时间片从小到大

  2. 新进程到达时先进入第1级队列,按FCFS原则排队等待被分配时间片,若用完时间片进程还未结束,则进程进入下一级队列队尾。如果此时已经是在最下级的队列,则重新放回该队列队尾。

  3. 只有第K级队列为空时,才会为K+1级队头分配时间片。

    抢占式的算法:在K级队列的进程运行过程中,若上级的队列(1~K-1级)中进入了一个新进程,则由于新进程处于优先级更高的队列中,因此新进程会抢占处理机,原来运行的进程放回K级队列队尾。

    image-20200325173853530


知识回顾

image-20200325174051062


分类
操作系统

信号量机制

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作,从而很方便的实现了进程互斥、进程同步


信号量

信号量其实就是一个变量(可以是一个整数整形信号量,也可以是更复杂的记录型变量记录型信号量),可以用一个信号量来表示系统中某种资源的数量,比如:系统中有三台打印机,就可以设置一个初值为3的信号量。


原语

原语是一种特殊的程序段,其执行只能一气呵成,不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”,因此如果能把进入区、退出区的操作都用“原语”实现,使这些操作能够“一气呵成”就能避免问题


一对原语

wait(S) 原语和 signal(S) 原语,可以把原语理解为函数,,括号里的信号量S理解为函数的参数。

通常将wait(S)原语简称为P操作,而将signal(S)原语简称为V操作。因此,在做题的时候经常把wait(S)、signal(S)两个操作分别写为P(S)、V(S)


信号量机制分为 整形信号量记录型信号量

整形信号量

用一个整数型的变量作为信号量,用来表示系统中某种资源的数量

与普通整数型变量的区别:

​ 对信号量的操作只有三种,即 初始化P操作V操作

“检查”和“上锁”一气呵成,避免了并发、异步导致的问题

存在的问题:不满足“让权等待”原则,会发生“忙等

Eg: 某计算机系统中有一台打印机…

int S = 1; //初始化整形信号量S,表示当前系统中可用的打印机资源数

//“检查”和“上锁”一气呵成,避免了并发、异步导致的问题
void wait(int S){   //wait 原语,相当于“进入区”
    //存在的问题:不满足“让权等待”原则,会发生“忙等”
    while(S >= 0);  //如果资源数不够,就一直循环等待
    S--;            //如果资源数够,则占用一个资源
}

void signal(int S){ //signal 原语,相当于“退出区”
    S++;            //使用完资源后,在退出区释放资源
}

进程P0:
……
wait(S);        //进入区,申请资源
使用打印机资源…   //临界区,访问资源
signal(S);      //退出区,释放资源

记录型信号量(操作系统中非常重要的知识点)

为了解决整形信号量存在”忙等“问题的缺陷,人们提出了”记录型信号量“,即用记录型数据结构表示的信号量。

/*记录型信号量的定义*/
typedef struct {
    int value;          //剩余资源数
    struct process *L;  //等待队列
} semaphore;

/*某进程需要使用资源时,通过 wait 原语申请*/
void wait(semaphore S){
    S.value--;
    //如果剩余资源数不够,
    //使用block原语使进程从运行态进入阻塞态,
    //并把其挂到信号量S的等待队列(即阻塞队列)中
    if (S.value < 0){
        block(S.L);
    }
}

void signal(semaphore S){
    S.value++;
    //释放资源后,若还有别的进程在等
    //待这种资源,则使用wakeup原语
    //唤醒该等待队列中的一个进程,该
    //进程从阻塞态变为就绪态
    if (S.value <= 0){
        wakeup(S.L);
    }
}

wait(S)、signal(S)也可记为P(S)、V(S),这对原语可以用于**实现系统资源的 “申请” 和 “释放” **。

S.value 的初值表示系统中某种资源的数目

对信号量S的一次P操作意味着进程请求一个单位的该类资源,因此需要执行S.value–,表示资源数减一,当S.value < 0 时表示该类资源已经分配完毕,因此进程应调用block原语进行自我阻塞(当前运行的进程从运行态→阻塞态),主动放弃处理机,并插入该类资源的等待队列 S.L 中。可见,该机制遵循了“让权等待”的原则,不会出现“忙等”的现象。

对信号量S的一次V操作意味着进程释放了一个单位的该类资源,因此需要执行 S.value++,表示资源数加一,若加一后仍是 S.value <= 0,表示依然有进程在等待该类资源,因此应调用 wakeup 原语唤醒等待队列中的第一个进程(被唤醒进程从阻塞态→就绪态)。


总结

整形信号量

用一个整数型变量作为信号量,数值表示某种资源数

整形信号量与普通整数型变量的区别:对信号量只能执行 初始化PV 三种操作

整形信号量存在的问题:不满足让权等待原则

记录型信号量——操作系统中极其重要的考点

S.value 表示某种资源数,S.L指向等待该资源的队列

P 操作中,一定是先 S.value–,之后可能需要指向 block 原语

V 操作中,一定是先 S.value++,之后可能需要指向wakeup原语

注意:要能够自己推断在什么条件下需要执行 block 或 wakeup

可以用记录型信号量实现系统资源的“申请”和”释放“

可以用记录型信号量实现进程互斥、进程同步

注:若题目中出现P(S)、V(S) 的操作,除非特别说明,否则默认S为记录型信号量。


分类
markdown

Markdown语法

由于WordPress自带的编辑器不太习惯,而且得频繁点击鼠标,还是用我比较熟悉的MarkDown来写博客吧。

  • 标题

    标题是每篇文章的开头都要使用的,所以我首先来介绍标题。
    在MarkDown中想要将一段文字定义为标题只需要在其前面加 # 就行了。
    MarkDown的标题和HTML的标题相似都有六个等级,一级标题最大,六级标题最小,定义几级标题只需要在其前面添加几个 # 再在 # 后面添加一个空格就行了。

    # 一级标题
    ## 二级标题
    ### 三级标题

  • 列表

    和HTML一样,列表也分为有序列表无序列表

无序列表通过在前面添加 *-+ 作为列表标记

* 无序列表
– 无序列表
+ 无序列表

有序列表则是在其前面添加数字后面再加一个半角的句号.

  1. 有序列表
  2. 有序列表
  3. 有序列表

  • 引用

    引用是通过在被引用内容前面添加一个大括号 > 再添加一个空格来实现的

    > 被引用内容

    要结束一段引用需要在其后面按两次回车键


  • 插入链接链接与图片

    插入链接与插入图片的语法很像,区别在于插入图片前面多了一个感叹号 !

    [链接名](链接url)
    ![图片名](图片url)

  • 字体效果

    在MarkDown中你可以通过键盘来达到各种改变字体的效果,而不需要点击鼠标(虽然Word也可以通过各种快捷键来实现\~~~ )

    1. 字体加粗
      字体加粗是我们经常用来强调某个概念的,可以通过在被加粗内容两边添加 ** 来实现

      **被加粗内容 被加粗内容**

    2. 斜体
      斜体可以通过在斜体内容两边各添加 * 来实现

      *斜体内容 斜体内容*

    3. 粗斜体
      粗细体即粗体和斜体叠加而成,可以通过在粗斜体内容两边添加 *** 来实现

      *粗斜体** 粗斜体***
      4.删除线
      想要对一段内容添加删除线,只需要在添加删除线内容的两侧输入 ~~
      \~\~删除线\~\~ 删除线
      5.下划线
      下划线则需要通过HTML语法的<u>标签来实现
      \下划线\ 下划线

  • 代码框

    如果是一行代码的话可以用反引号将其包裹起来

    \System.out.println()\ System.out.println()

而如果是一段代码的话则可以用 ` 将其包围起来

int main(){
    printf("Hello, MarkDown!");
}

  • 分割线

    分割线只需要用---或者***即可

  • 转义字符

    MarkDown也是通过\来进行转移的
    如果你想输入MarkDown语法中已经使用到的符合,比如*, -, +等等,就必须在其前面添加一个转移字符\


本文完,由于我自己也不是很熟悉可能中间有些地方写错了或者不够完整,等以后用到了在来修改、添加。 这篇文章是我开这个博客后写的第一篇,大概花了我一个半小时。

分类
感想

我要尽量多写文章啊

以前也陆陆续续搭建过博客,写过几次很水的文章。但由于自己的自制力不够,经常半途而废。今年年初的这次疫情导致我们都是在家上网课,而又没有课本,因此无法在课本上做笔记。现在想着尽量把学习中的知识点都整理发到这个博客上来,一方面为了巩固知识,二为了锻炼文笔(自从高中毕业后,写文章的功底不知道比以前低到哪里去了),三者就是为了搭建一个博客,以后也能在搜索引擎上搜到。