分类： LINUX
2012-08-29 15:57:35
第4章 存储管理习题
四、名词解释
重定位（静态、动态）：重定位是把逻辑地址转变为内存的物理地址的过程。根据重定位时机的不同，又分为静态重定位（装入内存时重定位）和动态重定位（程序执行时重定位）。
虚拟存储器：虚拟存储器是一种存储管理技术，用以完成用小的内存实现在大的虚空间中程序的运行工作。它是由操作系统提供的一个假想的特大存储器。但是虚拟存储器的容量并不是无限的，它由计算机的地址结构长度所确定，另外虚存容量的扩大是以牺牲CPU工作时间以及内、外存交换时间为代价的。
页表: 每一个作业的虚页号到内存的页架号之间的映射关系的表。
快表: 很多页式系统都配有一组快速寄存器，用来存放当前运行作业的页表表项，以加速地址变换过程，这种页表称之为快表。快表由CPU中的高速cache或联想寄存器构成。
对换: 对换是指系统把内存中暂时不能运行的某部分作业写入外存交换区，腾出空间，把外存交换区中具备运行条件的指定作业调入内存。
联想存储器: 一种按内容进行并行查找的一组快速寄存器。当用作为页面快表时，在其输入端有一个输入值页号p时，在联想寄存器中存放页号为p的那一项就立即选中，并输出其变换值页架号b。由于访问联想寄存器比访问主存快得多，故极大地提高了地址变换速度。
碎片: 内碎片是指在页面内部没有被使用的存储区域，在页式存储方式中，会出现内碎片。外碎片是指没有得到分配权的存储区域，在段式存储方式中，会产生外碎片。
系统抖动: 抖动是指页面在内存和外存之间频繁地调入调出，以至于占用了过多的系统时间，导致系统效率急剧下降的现象。它是由进程发生的缺页率过高而引起的。
五、问答题
1、在存储管理中分页与分段的主要区别是什么？分页与分段两种方法中，哪个更易于实现共享，为什么？
|
分页 |
分段 |
|
单一连续逻辑地址空间 |
二维逻辑地址空间 |
|
页是信息的物理单位 页是面向系统的 页内的信息逻辑上可能不完整的 |
段是信息的逻辑单位 段是面向用户的 段内的信息在逻辑上是完整的 |
|
页的大小固定 由系统划分 对用户透明 |
段长度可变增长 用户可见 便于动态链接和存储保护 修改和共享 |
|
以页面为单位分配空间 存在内零头 不需要紧凑技术 |
以段大小为单位分配的空间 存在外零头 需采用紧凑技术 |
分段方法更易于实现共享。在实现对程序和数据的共享时，是以信息的逻辑单位为基础的。a. 对于分页系统，每个页面是分散存储的，为了实现信息共享和保护，则页面之间需要一一对应起来，为此需要建立大量的页表项；
b. 而对于分段系统，每个段都从0开始编址，并采用一段连续的地址空间，这样在实现共享和保护时，只需为所要共享和保护的程序设置一个段表项，将其中的基址与内存地址一一对应起来即可.
2、为什么说请求分页存储管理可以实现虚拟存储系统？
分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片即页面。
同时把内存空间分成与页面相同大小的若干的存储块即物理块。
然后将进程的若干个页面离散的存储在内存不同的物理块中,其中引进页表和地址变换机构，实现进程逻辑地址与内存物理地址的转换，引进快表加快速度。
页表寄存器在CPU中，逻辑地址在程序计数器中，使用的页表在内存中，如果是两级或多级页表，不使用的页表则放在硬盘的外部页表寄存器。逻辑地址中的页号+页表寄存器中的页表始址，然后通过页表找到内存中的物理地址。实现虚拟 <-> 线性 <-> 物理的转换。
3、在某段式存储管理系统中，有一作业的段表如下表所示，求逻辑地址【0，65】，【1，55】，【3，20】对应的主存地址。（【】内前者为段号，后者为段内位移）。
|
段号 |
段长 |
主存起始地址 |
状态 |
|
0 |
200 |
600 |
0 |
|
1 |
50 |
850 |
0 |
|
2 |
100 |
1000 |
0 |
|
3 |
150 |
―― |
1 |
逻辑地址【0，65】对应主存地址为665。
【1，55】50<55，越界中断。
【3，20】状态位为1，故不在主存，产生缺段中断。
4、已知主存容量为512KB，其中操作系统代码占低址部分126KB，有作业序列如下：
作业1 要求 80KB；
作业2 要求 56KB；
作业3 要求 120KB；
作业1 完成
作业3 完成
作业4 要求 156KB；
作业5 要求 80KB；
试用最佳适应算法处理上述作业序列；并做以下工作：
（1） 画出作业1，2，3进入系统后的内存分布情况；
（2） 画出作业1，3完成后内存分布情况；
（3） 画出作业4，5进入系统后的内存分布情况；
5、有一个100×200的矩阵，即int a[100][200];在一个虚拟系统中，采用LRU算法。系统分配给该进程五个页面来存储数据。设每页可存放200个整数，该程序要对数组进行初始化，按行存放。试计算下列两个程序各自的缺页次数。
程序一：For(i=0;i<100;i++)
for(j=0;j<200;j++)
a[i][j]=i*j;
缺页次数100次。分析：每个页面中存放每行上的200个整数，在内循环对列的访问中未产生缺页，每次换行初始化时才产生缺页，故缺页次数为100。
程序二：For(j=0;j<200;j++)
for(i=0;i<100;i++)
a[i][j]=i*j;
缺页次数100*200=20000次。分析：每个页面中存放每行上的200个整数，在内循环时每次初始化列时就会产生100次，加上外循环的200次，总共就会产生20000次缺页。
6、某采用页式存储管理的系统，接收了一个共7页的作业，作业执行时依次访问的页为1，2，3，4，2，1，5，6，2，1，3，7。若主存只有5块空间，当分别用FIFO和LRU置换算法时，作业执行过程中会产生多少缺页中断？写出依次产生缺页中断后淘汰的页。
（1）FIFO算法：缺页次数8次。
|
1 |
2 |
3 |
4 |
2 |
1 |
5 |
6 |
2 |
1 |
3 |
7 |
|
1 |
1 |
1 |
1 |
|
|
1 |
6 |
|
6 |
|
6 |
|
|
2 |
2 |
2 |
|
|
2 |
2 |
|
1 |
|
1 |
|
|
|
3 |
3 |
|
|
3 |
3 |
|
3 |
|
7 |
|
|
|
|
4 |
|
|
4 |
4 |
|
4 |
|
4 |
|
|
|
|
|
|
|
5 |
5 |
|
5 |
|
5 |
（2）LRU算法：缺页次数8次。
|
1 |
2 |
3 |
4 |
2 |
1 |
5 |
6 |
2 |
1 |
3 |
7 |
|
1 |
1 |
1 |
1 |
|
|
1 |
1 |
|
|
1 |
1 |
|
|
2 |
2 |
2 |
|
|
2 |
2 |
|
|
2 |
2 |
|
|
|
3 |
3 |
|
|
3 |
6 |
|
|
6 |
6 |
|
|
|
|
4 |
|
|
4 |
4 |
|
|
3 |
3 |
|
|
|
|
|
|
|
5 |
5 |
|
|
5 |
7 |
7、考虑一个仅460字节的程序的下述内存访问序列: 10，11，104，170，73，309，185，245，246，434，458，364。页面大小为100字节。
（1） 写出页面访问顺序。
（2） 假设内存中仅有200个字节可供程序使用且采用FIFO算法，那么共发生多少次缺页中断？
（3） 如果采用LRU算法，又会发生多少次缺页中断？
【解答】（1）访问顺序
|
10 |
11 |
104 |
170 |
73 |
309 |
185 |
245 |
246 |
434 |
458 |
364 |
|
0 |
0 |
1 |
1 |
0 |
3 |
1 |
2 |
2 |
4 |
4 |
3 |
（2）采用FIFO算法的情况如表所示。
|
|
0 |
0 |
1 |
1 |
0 |
3 |
1 |
2 |
2 |
4 |
4 |
3 |
|
块号0 |
0 |
|
0 |
|
|
3 |
|
3 |
|
4 |
|
4 |
|
块号1 |
|
|
1 |
|
|
1 |
|
2 |
|
2 |
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
采用FIFO算法产生的缺页中断为6次。
（3）采用LRU算法的情况如表所示(已改)用栈做，比较容易懂，
|
0 |
0 |
1 |
1 |
0 |
3 |
1 |
2 |
2 |
4 |
4 |
3 |
|
|
|
1 |
1 |
0 |
3 |
1 |
2 |
2 |
4 |
4 |
3 |
|
0 |
0 |
0 |
0 |
1 |
0 |
3 |
1 |
1 |
2 |
2 |
4 |
|
缺 |
|
缺 |
|
|
缺 |
缺 |
缺 |
|
缺 |
|
缺 |
采用LRU算法产生的缺页中断为7次。
8、在采用分页存储管理系统中，地址结构长度为18位，其中11至17位表示页号，0到10位表示页内位移。若有一作业的各页依次放入2，3，7号物理块中，请问：
（1）主存容量最大可为多少K？分为多少块？每块多大？
（2）逻辑地址1500应在几号页内？对应的物理地址为多少？
解：（1）主存容量为256K，可分为128块，每块大小为2K。
（2）逻辑地址在0号页内，物理地址等于5596。
分析： 由于0到10位表示页内位移，则块大小为2的11次方，即2K。
11至17位表示页号，则块数就为2的7次方，即128。
主存容量=块数*块的大小。
0号页内逻辑地址为0~2048，则作业放入了2号块中。
物理地址=逻辑地址+2*2K=5596
9、简述在段页式存储管理中，虚拟地址到物理地址的转换过程。
（详细参考书P140-P141）地址变换过程
首先，必须配置一段表寄存器，在其中存放段表始址和段长TL. 进行地址变换时，先利用段号S，与段长TL进行比较，若S
10、什么叫重定位？采用内存分区管理时，如何实现程序运行时的动态重定位？
重定位是把逻辑地址转变为内存的物理地址的过程。根据重定位时机的不同，又分为静态重定位（装入内存时重定位）和动态重定位（程序执行时重定位）。
采用内存分区管理时，可在硬件上设置一个“重定位寄存器”来实现程序运行中的动态重定位，此时程序执行的物理地址是通过程序的逻辑地址与重定位寄存器中的基址这两者之和得到的，其地址变换过程由地址变换机构自动实现。
11、简述请求式分页存储管理的思想。
请求页式管理的基本原理是将逻辑地址空间分成大小相同的页，将存储地址空间分块，页和块的大小相等，通过页表进行管理。页式系统的逻辑地址分为页号和页内位移量。页表包括页号和块号数据项，它们一一对应。根据逻辑空间的页号，查找页表对应项找到对应的块号，块号乘以块长，加上位移量就形成存储空间的物理地址。每个作业的逻辑地址空间是连续的，重定位到内存空间后就不一定连续了。
此外，页表中还包括特征位（指示该页面是否在内存中）、外存地址、修改位（该页的内容在内存中是否修改过）等。页式存储管理在动态地址转换过程中需要确定某一页是否已经调入主存。若调入主存，则可直接将虚地址转换为实地址，如果该页未调入主存，则产生缺页中断，以装入所需的页。页式存储管理将不常用的页面调出内存，使内存的利用率高；虚拟的容量大，用户不必担心内存不够；不要求作业连续存放，有效地解决了“碎片”问题。
