【第六章 | 虚拟存储器】《操作系统 慕课版》课后答案 + 复习

文章目录

【第六章】虚拟存储器

| 本章概念

1.虚拟存储器概述

• 前面基础存储器的缺点 - 有一个共同特点：作业全部装入内存后方能运行- 常规存储器管理方式的特征：一次性：作业被一次性全部装入内存；驻留性：作业一直驻留在内存- 一次性和驻留性使许多在程序运行中不用或暂不用的程序（数据）占据了 大量的内存空间，使得一些需要运行的作业无法装入运行。
• 如何解决【大作业装不下、少量作业得以运行】的问题？解决办法：扩充内存、逻辑上扩充内存容量（虚拟存储器）
• 虚拟存储器的定义 - 应用程序在运行之前，没有必要全部装入内存，仅须将 那些当前要运行的部分页面或段先装入内存便可运行- 具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。- 其运行速度接近于内存速度，而成本接近于外存
• 虚拟存储器的特征 - 多次性：作业中的程序和数据允许被分成多次调入内存允许- 对换性：作业运行时无须常驻内存- 虚拟性：从逻辑上扩充了内存容量，使用户看到的内存容量远大于实 际内存容量
• 虚拟存储器的实现方法 - 请求分页系统- 请求分段系统- 段页式虚拟存储器

2.请求分页存储管理方式基本概念

• 最小物理块数的确定：保证进程正常运行所需的最小物理块数。取决于指令的格式、功能和寻址方式。 - 平均分配算法；- 按比例分配算法； 各进程页面总和 S = ΣSi 每个进程所能分到的物理块数 bi ＝ Si / S * m- 考虑优先权的分配算法；
• 页面调入策略： - 何时调入页面？预调页策略、请求调页策略- 从何处调入页面？- 如何调入页面？查找所需页在磁盘上的位置、查找一内存空闲块、将所需页读入新空闲块然后更新页表、重启用户进程
• 缺页率的计算： - S：访问页面成功次数- F：访问页面失败次数- A ： 总访问次数 = S+F- 缺页率 = F/A
• 缺页中断处理时间： - β：被置换的页面被修改的概率- ta：被置换页面被 修改的缺页中断处理时间- tb：被置换页面没有被修改的缺页中断时间- 缺页中断处理的时间 = β * ta + （1-β）*tb

3.页面置换算法的相关概念

• 页面置换：找到内存中没有使用的一些页，换出
• 性能的关键点 ：找出一个导致最小缺页数的算法
• 同一个页可能会被装入内存多次（可能造成“抖动”）
• 页面置换完善了逻辑内存和物理内存的划分——在一个较小的物理 内存基础之上可以提供一个大的虚拟内存
• 常见的页面置换算法：最佳置换算法 OPT 、先进先出置换算法 FIFO 、最近最久未使用算法 LRU 、最少使用算法 LFU、Clock置换算法、页面缓冲算法
• 目的：尽可能小的缺页率

4.请求分段存储管理方式基本概念

• 在分页基础上建立的请求分页式虚拟存储器系统，是以页面为单位进行换出 / 换入的。而在分段基础上所建立的请求分段式虚拟存储器系统，则是以分段为单位进行换入 / 换出的
• 请求分段中的硬件支持 - 请求段表机制- 缺段中断机构：在指令执行期间产生和处理中断信号。一条指令在执行期间，可能产 生多次缺段中断。由于段不是定长的，因此中断处理比缺页中断复杂- 地址变换机构：若段不在内存中，则必须先将 所缺的段调入内存，并修改段表，然后利用段表进行地址变换。
• 分段保护： - 越界检查：比较段号与段表长度；段内地址与段表长度- 存取控制检查：以段为基本单位进行- 环保护机构

| 本章算法

1.分页存储管理的有关计算公式

最小物理块的数量计算公式

按比例分配算法； 各进程页面总和 S = ΣSi 每个进程所能分到的物理块数 bi ＝ Si / S * m

缺页率的计算

• S：访问页面成功次数
• F：访问页面失败次数
• A ： 总访问次数 = S+F
• 缺页率 = F/A

缺页中断处理时间的计算

• β：被置换的页面被修改的概率
• ta：被置换页面被 修改的缺页中断处理时间
• tb：被置换页面没有被修改的缺页中断时间
• 缺页中断处理的时间 = β * ta + （1-β）*tb

2.请求分页系统访问内存的有效时间EAT

λ：为查找快表所需要的时间

t：为访问一次内存所需要的时间

访问页在内存，且其对应页表项在快表中 EAT= λ + t

访问页在内存，但其对应页表项不在快表中 EAT= λ + t + λ + t = 2(λ + t)

t：为访问一次内存所需要的时间

φ：缺页中断处理时间

f：缺页率

访问页不在内存中：需进行缺页中断处理，有效时间可分为查找快表的时间、查找页表的时间、 处理缺页的时间、更新快表的时间和访问实际物理地址的时间

EAT = t + f ×(φ + t) + (1- f) × t

区别于【第五章：存储器管理】的【引入快表后的有效访问时间】计算公式

这个是请求调页系统，第五章那个是分页存储系统

3.已知逻辑地址、页大小、页表；求物理地址

①把逻辑地址转为二进制（如101(8) → 001 000 001）

②根据页大小计算出页的地址结构（如一页32B，2^5=32 因此低5位为页内地址，其余页为页号）

③由①的二进制，结合②的地址结构，可以得出【页号、页内地址】（如001 000 001，低5位为页内地址，则该二进制表示第2页，页内第1位）

④查表，若查得到则OK；若查不到则表示该逻辑地址不能转换

4.页面置换算法

最佳页面置换算法 OPT

• 被置换的页将是之后最长时间不被使用的页。是一种理想算法，永远不可能实现

先进先出置换算法 FIFO

• 总是淘汰最先进入内存的页面

最近最久未使用算法 LRU

• 选择最近最久未使用的页面予以淘汰
• 硬件支持：被访问的页面对应寄存器的Rn-1位置为1，定时右移
• 具有最小数值的寄存器所对应的页面为淘汰页

最少使用算法 LFU（了解）

• 选择在最近时期使用最少的页面作为淘汰页。（如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰；当存在两个或者更多个键具有相同的使用频次时，应该淘汰最久未使用的数据。（即此时为 LRU）
• 为内存中的每个页面设置 一个移位寄存器，用来记 录该页面的被访问频率

Clock置换算法（了解）

• LRU的近似算法，又称最近未用(NRU)或二次机会页面置换算法
• 每个页都与一个访问位相关联，初始值位0，当页被访问时置访问位为1，置换时选择访问位为0的页 ；若为1，重新置为0页面缓冲算法（了解）
• 设置两个链表：- ①空闲页面链表：保存空闲物理块- ②修改页面链表：保存已修改且需要被换出的页面，等被换出的页面数目达到一定值时，再一起换出外存

5.请求分段存储管理方式 地址变换

作业最多可拥有的段数 = 2 ^ 虚拟地址中【段号】的位数

作业最多可拥有的长度字节 = 2 ^ 虚拟地址中【段内相对地址】的位数

已知段号和段内地址，如何进行地址变换？

① 找到段号对应的段长 L 和主存起始地址 S

② 若段表中段号所对应的段长 ＜ 所给的段内地址 则说明产生了越界中断，无法转换

​ 若段表中段号对应的段长 ≥ 所给的段内地址， 则逻辑地址对应的主存地址为【主存起始地址 + 段内地址】

| 课后简答题

1．常规存储器管理方式具有哪两大特征?它们对系统性能有何影响?

一次性：进程必须全部装入内存。一次性对内存空间的浪费非落大

驻留性：在程序运行过程中，进程全部驻留在内存中。驻留性使内存中暂时不用的程序或数据无法被释放。

2.什么是虚拟存储器?如何实现页式虚拟存储器?

虚拟存储器是具有请求调入功能和置换功能,能从逻辑上对内存容量进行扩充的一种存储系统

为实现虚拟存储器，首先需要扩充页表，增加状态位以指出所需页是否在内存中,

另外，还要使用两种关键技术。

①请求调页技术该项技术是指及时将进程所要访问的不在内存中的页调人内存。

②置换页技术该项技术

3.“整体对换从逻辑上也扩充了内存，因此也实现了虚拟存储器的功能”这种说法是否正确，请说明理由。

这种说法是错误的。

整体对换将内存中暂时不用的某个程序及其数据换出至外存，腾出足够的内存空间以装入在外存中具备运行条件的进程所对应的程序和数据。

虚拟存储器是指仅把作业的一部分装入内存便可运行作业的存储器系统，亦指具有请求调人功能和置换功能、能从逻辑上对内存容量进行扩充的存储器系统，它的实现必须建立在离散分配的基础上。虽然整体对换和虚拟存储器均能从逻辑上扩充内存空间，但整体对换不具备离散性。实际上，在具有整体对换功能的系统中，进程的大小仍将受到实际内存容量的限制。

4．在请求分页系统中，为什么说一条指令执行期间可能产生多次缺页中断?

在请求调页时，只要作业的部分页在内存中，该作业就能执行;

而在执行过程中发现所要访问的指令或数据不在内存中时、系统会产生缺页中断，将所需的页面调入内存。

在请求调页系统中，—条指令（如copy A to B)可能跨了两个页，而其中要访问的操作数可能与指令不在同一个页上,且操作数本身也可能跨了两个页。当要执行这类指令而相应的页又都不在内存中时，就将产生多次缺页中断。

5．试比较缺页中断与一般的中断，它们之间有何明显区别?

缺页中断与一般中断的区别主要有:

①一般中断只需要保护现场然后即可直接跳到须及时处理的地方;

②缺页中断除了需要保护现场外，还需要判断内存中是否有足够的空间来存储所需的页或段，然后再把所需的页或段调进来使用。

6.试说明在请求分页系统中页面的调入过程。

每当程序所要访问的页面未在内存时（存在位为“0”）.便向CPU发出缺页中断，中断处理程序保存CPU现场信息，分析中断原因后，转人缺页中断处理程序。该程序通过查找页表得到该页在外存的物理地址，如果此时内存能谷纳新贝，则后功伍，将历欧贝面调人内存，然后修改页表。如果内存已满，则须按照某种置换算法进行页面置换;如果换出页面被修改过（修改位为“1”)，则必须将它写回磁盘，再把缺页调入内存，将页表中调入页的存在位改为“1”，并将此页表项写入快表中。利用修改后的页表，形成要访问数据的物理地址，再去访问内存数据。整个页面调人过程对用户是透明的。

7.（考研真题）简述在具有快表的请求分页系统中，将逻辑地址转换为物理地址的完整过程。

在具有快表的请求分页系统中、将逻辑地址转换为物理地址的完整过程为

①检索快表，试图从中找出所要访问的页

②如果找到，那么修改页表项中的访问位,供置换算法选择淘汰页时参考，将写指令的修改位置1，然启利用页表项中给出的物理块号和页内地址形成物理地址，地址转换结束:

③如果没找到，那么应到内存中查找贝表，再根据查找到的贝表项中的状态位来判断该页是否已调。若该页已调入内存、则将该页的页表项写入快表。
当快表已满时，先调出按某种算法所确定的页的页表项，再写人该页的页表项。若该页未调入内存，则产生缺页中断，请求OS从外存中将该页调人内存，再转到步骤②进行地址转换。

8．何谓固定分配局部置换和可变分配全局置换的内存分配策略?
(1）固定分配局部置换:固定分配是指，为每个进程分配一组固定数目的物理块，在进程运行期间不再改变;局部置换是指，如果进程在运行中发现缺页，则只能从分配给该进程的n个页面中选出1页换出,然后再调人1页。
(2)可变分配全局置换;可变分配是指，先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的改变;全局置换是指，如果进程在运行中发现缺页，则将Os所保留的空闲物理块或者所有进程的全部物理块选择1块换出然后再将缺页调入。

10.为了实现请求分段存储管理，应在系统中增加配置哪些硬件机构?

为了实现请求分段存储管理，应在系统中配置多种硬件机构以支持快速完成请求分段功能。

所需的硬件支持有段表机制、缺段中断机构以及地址转换机构。