大工21春《操作系统概论》复习资料十二
《操作系统概论》辅导资料十二主题：第4章存储管理（第5—6节）学习时间： 2020年6月15日--6月21日“不忘初心、牢记使命”主题理论学习：
忠诚是共产党人必须具备的优秀品格。“忠诚印寸心，浩然充两间”的坚毅，“砍头不要紧，只要主义真”的无畏，腹中满是草根而宁死不屈的气节，食指钉入竹签而永不叛党的坚贞，无数先烈用鲜血诠释了对党的忠诚。对党忠诚必须是纯粹的、无条件的，是政治标准、更是实践标准，鲜明体现在坚决贯彻答案决策部署上。
摘选自《在第十九届中央纪律检查委员会第二次全体会议上的讲话》内容：
这周我们将学习课件第4章中的第5—6节，下面整理出的理念框架供同学们学习。
本篇的基本要求：
1. 了解段页式存储管理
2. 掌握虚拟存储管理
重点掌握内容：
1. 虚拟存储技术，页面置换算法4.5 段页式存储管理
一、段页式存储管理的基本思想
在为程序分配内存空间时，首先运用分段存储管理的思想，根据程序自身的逻辑结构，把程序的逻辑地址空间划分为若干个段，每个段有各自的段号；
再运用分页存储管理的思想，将每个分段按照一定的大小划分为不同的页，每个页通过页号进行标识。内存空间亦划分成与页面大小相等的物理块，并对所有物理块从0开始依次编号。
在为程序分配内存空间时，允许以页为单位一次性将一个进程的所有的页面装入内存中若干不相邻接的物理块中。二、段页式存储管理中的地址转换
/
地址变换机构要完成对内存空间中某个存储单元的访问至少要3次访问内存。
第一次:
访问内存是根据段号，通过段表寄存器中的段表始址在内存中找到段表，从段表的表项中找到对应页表的始址；
第二次:
访问内存是根据页表始址和段内页号到内存中访问页表，从页表中找到与页号对应的物理块号，并将该物理块号与页内地址一起形成指令或数据的物理地址；
第三次:
访问内存才是根据得到的物理地址访问相应的存储单元。三．段页式存储管理算法/四、段页式存储管理的优缺点
㈠、优点
（1）虚拟存储器的功能；
（2）无紧缩问题，无页外的碎片存在；
（3）便于处理变化的数据结构，段可动态增长；
（4）便于共享；
（5）便于控制存取访问。
㈡、缺点：增加了硬件成本；增加了软件复杂性和管理开销；存在页内碎片。4.6虚拟存储管理
一、虚拟存储系统的基本概念
1．“实存”管理技术：作业运行时，整个作业的逻辑地址空间必须全部装入主存。
当作业大于主存可用空间时，无法运行。
2．“虚拟存储”管理技术
（1）虚拟存储器：实际上并不存在的存储器。
（2）逻辑地址空间：一个程序被编译连接后产生的目标程序的地址的集合。
（3）物理地址(实存地址)空间：CPU能直接访问的主存的地址空间。
（4）逻辑地址空间与物理地址空间的关系----概念上不同，且又有联系。
前者----程序的指令和数据放置的逻辑上的空间；
后者----程序在执行时实际存放其指令和数据的物理空间。
3．虚拟地址与实地址
进程要执行程序，这也就是说进程要访问的是程序的指令和数据的逻辑地址。而进程必须在处理器上运行，它通过处理器才能访问指令和数据，这样指令和数据必须存放在处理器能直接访问的主存中，也就是说处理所实际访问的是存放指令和数据的主存地址。
（1）虚拟地址：一个运行进程所访问的地址。
（2）虚拟地址空间----一个运行进程可访问的虚地址的集合。
（3）实地址：处理器可直接访问的主存地址。
（4）实地址空间----计算机的主存。
/
4．进程的虚拟地址空间包含的信息：正文(程序可执行代码)、数据(包括已初始化数据、未初始化数据、修改过的数据)、堆栈、共享主存区、共享库。
5．虚拟存储管理技术的好处
（1）只把进程当前所用部分放在主存，减少进程启动和滚进滚出的开销；
（2）主存中可同时容纳大量进程，提高系统多道程度和并行性。
6．虚拟存储管理技术的代价
（1）地址转换表等主存的开销；
（2）地址转换增加了每条指令的执行时间。
（3）页面调度消耗磁盘I/O操作时间。
7．虚拟存储管理技术的分类：分页技术、分段技术、分段加分页技术。二、请求分页虚拟存储管理
在分页式存储管理系统中，如果允许只将进程的一部分页面装入内存就启动运行，进程执行过程中再根据需要陆续将所需页面调入，并将内存中暂时不需要的页面换出内存，便可以在逻辑上实现对内存容量进行扩充，即实现虚拟存储器。
请求分页虚拟存储管理方式正是在分页式存储管理方式上增加了支持虚拟存储器而形成的一种存储管理方式。为了支持虚拟存储器，讲求分页虚拟存储管理方式增加了请求调页功能和页面置换功能。要实现请求调页功能和页面置换功能，必须有相应的硬件和软件支持。
分页系统中的地址转换
（1）直接映象的页地址转换
① 首先将逻辑地址左边表示页号部分的页号抽取出来。
② 以页号作为索引查找该进程页表，找出该页存放的主存页架号。
③ 用此号架号取代逻辑地址的左边部分，并与右边的页内地址合并成相应的主存的绝对地址，实现了地址映象
/
三、页面置换算法
页面置换：当系统无空闲页架时，将某些页面放入外存，以及将某些页纳入页架的过程。
目标：把未来不再使用的或短期内较少使用的页面调出，通常只能在局部性原理指导下依据过去的统计数据进行预测；
页面置换算法：选择淘汰页面的算法。
1）选择哪些页面淘汰
2）是局部置换还是全局置换
置换算法的评价
缺页率：作业在执行的过程中页面置换的频率。
缺页率 = f/a
其中：a:访问的总次数
f：访问失败的次数
常用置换算法：
1、最佳置换算法
基本思想：选择“将来不再使用的”或“在最远的将来才被访问的”页面被置换。
特点：
1）无法实现，因为无法预知未来页面的访问情况
2）常用作评价其他算法的依据 2、先进先出置换算法（FIFO）
基本思想：选择最早装入的页面被置换
实现 ：设置一个链表，将所有页面按先后次序链成一个队列，并设置一个指针指向最早的页面。
/
共缺页中断7次缺点
1）性能较差：与进程实际运行的规律不相适应，因为较早调入的页面，往往是经常被访问的(含有全局变量、常用函数等)。
2）存在Belady现象。
Belady现象：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。
Belady现象的描述：一个进程P要访问M个页，OS分配N个内存页面给进程P；对一个访问序列S，发生缺页次数为PE（S,N）。当N增大时，PE(S, N)时而增大，时而减小。
Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。
Belady现象的例子
进程P有5页程序访问页的顺序为：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5；
如果在内存中分配3个页面，则缺页情况如下：12次访问中有缺页9次；如果在内存中分配4个页面，则缺页情况如下：12次访问中有缺页10次；3、最近最少使用置换算法（LRU）
基本思想：选择最近一段时间内最长时间未使用的页面淘汰。
实现 ：
1）系统设置一个64位计数器，自动计数；
2）每个页表目有一个字段保留计数器，页表被访问时，将计数器的当前值保存在页表目计数字段内，
3）发生缺页时，淘汰最小计数的页表。
4）一般，设置一个矩阵。N个页架需要设置一个NxN矩阵。淘汰二进值最小的页面。
特点:
1）局部性原理的近似，性能最接近最佳算法
2）需要记录页面使用时间的先后次序，硬件开销大
3）实现起来比较困难 4、最近未使用置换算法(NUR )
基本思想：选择最近一段时间内未使用的页面淘汰，希望优先淘汰最近未使用并且其页内数据没有被修改的页面。
实现：
1）给每个页面定义两个标记属性 :
a）访问位：记为A，= 0，该页尚未被访问； = 1， 该页已经被访问。
b）修改位：记为M，= 0，该页尚未被修改； =1，该页已经被修改。
2)初始时，所有页面的A和M均为0；当某页被访问时，A置为1，当被修改时M置为1。
3)定时对所有页面的访问位置0。定时的长度确定比较关键。太长，会出现所有A位1，太短，则A为0的页面过多。
4)淘汰顺序：1，2，3，4。
A=0, M=0：最佳淘汰，1
A=0, M=1：次佳淘汰，2
A=1, M=0：此差淘汰，3
A=1, M=1：最差淘汰，4
例：计算缺页次数
某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5
/四、分段存储管理
1．分段概述
（1）虚拟分段与简单分段的区别
简单分段：一个运行进程的各段都必须装入主存。
虚拟分段：只需把进程当前常用的一少部分段装入主存即可。
（2）虚拟分段的优点
① 简化对可以任意增长和收缩的数据段的管理。
② 分别编译的段的连接简单。
③ 如果一个段的过程被修改并重新编译，不会引起其他段修改。
④ 便于在进程间共享过程和数据。
⑤ 段是程序员可见逻辑上实体。对不同段，程序员可以安排不同保护类型。
2．分段的地址转换
/五、请求段页式虚拟存储管理
请求段页式虚拟存储管理系统是在段页式存储管理系统基础上提出的一种虚拟存储器系统。
首先按照程序自身的逻辑结构把程序划分为若干个不同的分段，再将每个分段划分成固定大小的页面；内存空间根据页面大小划分为若干物理块，内存以物理块为单位进行离散分配；进程不必将所有页面装入内存便可以启动运行，进程运行过程中若要访问的页面不在内存，便会产生缺页中断，若该页所在的段也不在内存，则首先产生缺段中断，再产生缺页中断，由相应的中断处理程序到外存找到该段，并将该段中所需要的页面调入内存。若进程要访问的页面已在内存，则对页面的管理与段页式存储管理相同。 重要考点
一、单项选择题
1、实现虚拟存储器的目的是（ ）。
A．实现存储保护
B．实现程序浮动
C．扩充辅存容量
D．扩充主存容量
答案：D二、判断题
1、虚拟存储管理技术分为分页技术、分段技术以及段页式技术三种。（ ）
A．正确
B．错误
答案：A
解析：虚拟存储管理技术一般分为三种，即题目的三种技术。三、简答题
1、在分页存储管理系统中，页面访问序列为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数为3时，回答以下两个问题。
(1)计算采用最佳置换算法(OPT算法)时的缺页率(假设开始执行时主存中没有页面)。
(2)根据算法完善以下表格。
走向
4
3
2
1
4
3
5
4
3
2
1
5
块1
4
2
2
块2
空
3
1
块3
空
5
5
缺页
缺
缺
缺
答案：（1）缺页率为7/12（2）
走向
4
3
2
1
4
3
5
4
3
2
1
5
块1
4
4
4
4
4
4
4
4
4
2
2
2
块2
空
3
3
3
3
3
3
3
3
3
1
1
块3
空
空
2
1
1
1
5
5
5
5
5
5
缺页
缺
缺
缺
缺
否
否
缺
否
否
缺
缺
否
解析：缺页率需要从表格中得出，从表格看出共12次，其中缺页的是7次。OPT算法是淘汰在将来再也不被访问，或者是在最远的将来才被访问的页。
南开答案可以联系QQ 761296021
页:
[1]