第四章 存储器管理.docx
《第四章 存储器管理.docx》由会员分享，可在线阅读，更多相关《第四章 存储器管理.docx（41页珍藏版）》请在冰点文库上搜索。
第四章存储器管理
第四章存储器管理
第一部分教材习题（P159）
1、为什么要配置层次式存储器？
2、可采用哪几种方式将程序装入内存？
它们分别适用于何种场合？
答:
绝对装入方式，在编译时，如果知道程序将驻留在内存的什么位置，那么编译程序将产生绝对地址的目标代码。
可重定位装入方式，在多道程序环境下，由于编译程序不能预知所编译的目标模块在内存的什么位置，因此目标模块的起始地址通常从0开始，程序中所有其他地址都相对于起始地址计算。
动态运行时装入方式，程序在装入内存中后，允许程序在运行中在内存中移动位置。
3、何谓静态链接？
何谓装入时动态链接和运行时的动态链接？
答:
静态链接:
在程序运行之前,先将各目标模块及它们所需的库函数,链接成一个完整的装入模块,以后不再拆开。
这种事先进行链接的方式叫静态链接方式。
装入时动态链接:
用户源程序编译后所得的一组目标模块,在装入内存时,采用边装入边链接的链接方式。
运行时的动态链接:
对某些目标模块的链接,是在程序执行中需要该目标模块时,才对它进行的链接。
4、在进行程序链接时，应完成哪些工作？
答：
在进行程序链接时，应完成：
对相对地址的修改
变换外部调用符号
5、在动态分区分配方式中，应如何将各空闲分区链接成空闲分区链？
答：
为了现实对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针，通过前、后向链接指针，可将所有的空闲分区链接成一个双向的链，如图所示（空闲链结构），为了检索方便，在分区尾部重复设置状态位的分区大小表目。
当分区被分配出去以后，把状态位由“0”改为“1”，此时，前、后向指针已没有意义。
6、为什么要引入动态重定位？
如何实现？
答：
在连续分配方式中，必须把一个系统或用户程序装入一连续的内存空间。
如果在系统中只有若干个小的分区，即使它们容量的总和大于要装入的程序，但由于这些分区不相邻接，也无法把该程序装入内存。
若想把作业装入，可采用的一种方法是：
将内存中的所有作业进行移动，使它们全都相邻接，这样，即可把原来分散的多个小分区拼接成一个大分区，这时就可把作业装入该区。
这种通过移动内存中作业的位置，以把原来多全分散的小分区拼接成一个大分区的方法方法，称为“拼接”或“紧凑”见图所示。
由于经过紧凑后的某些用户程序在内存中的位置发生了变化，此时若不对程序和数据的地址加以修改（变换），则程序必将无法执行。
为此，在每次“紧凑”后，都必须对移动了的程序或数据进行重定位，这也就引入的动态重定位。
7、在采用首次适应算法回收内存时，可能出现哪几种情况？
应怎样处理这些情况？
答:
当进程运行完毕释放内时，系统根据回收区的首址，从空闲区链中找到相应的插入点，此时可能出现以下四种情况之一：
●回收区与插入点的前一个空闲分区F1相邻，见图（a）。
此时应将回收区与插入点的前一区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。
●回收区与插入点的后空闲分区F2相邻接，见图（b）。
此时也可瘵两分区合并，形成拳的空闲分区，但用回收的首址作为新空闲分区的首址，大小为两者之和。
●回收区同时与插入点的前、后两个分区相邻接，见图（C）。
此时将三个分区合并使用F1的首址，取消F2的表项，大小为三者之和。
●回收区既不与F1相邻接，也不与F2相邻接。
这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。
8、令buddyk（x）表示大小为2k、地址为x的块的伙伴系统地址，试写出buddyk（x）的通用表达式。
9、分区存取管理中常用哪些分配策略？
比较它们的优缺点。
10、在系统中引入对换后可带来哪些好处？
答：
引入对换后，可以解决由于内存不足而无法同时容纳多个用户程序的问题，并可以进一步提高内存的利用率。
11、为实现对换，系统应具备哪几方面的功能？
答:
为了现实进程的对换，系统必须能实现三方面的功能：
对换空间的主管理，进程的换出，以及进程的换入。
12、在以进程为单位进行对换时，每次是否都将整个进程换出？
为什么？
答：
并非要将整个进程换出，换出程序（进程）要换出某个进程时，只能换出那些非共享的程序和数据段。
对于共享的程序段和数据段，则须先对每个段的引用计数执行减1操作。
若其结果值不为0时，表示仍有进程需要用它，因而不能换出；否则表示该程序段或数据段，已不被其他进程需要，于是可以将它们换出。
13、为实现分页存储管理，需要哪些硬件支持？
答：
为了实现请求分页，系统必须提供一定的硬件支持，除了需要一台具有一定容量的内存及外存的计算机以外，还需要有页表机制、缺页中断机构以及地址变换机构。
●页表机制：
作用是将用户地址空间是的逻辑地址变换为内存空间中的物理地址。
●缺页中断机构：
在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。
缺页中断作为中断，它们同样需要经历诸如保护CPU环境，分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤。
●地址变换机构：
请求分页系统中的地址变换机构，是在分页系统地址机构的基础上，再为实现虚拟存储器而增加了某种功能而形成的，如产生和处理缺页中民，以及从内存中换出一页的功能等。
在进行地址变换时，首先去检索快表，试图从中找出所要访问的页，若找到，便修改页表中的访问位，对于写指令还须将修改位置成“1”，然后利用页表中给出的物理号和页内地址，形成页内物理地址。
地址变换过程到此结束。
14、较详细地说明引入分段存储管理是为了满足用户哪几方面的需要。
答：
引入分段存储管理方式，主要是为了满足用户和程序员的下述一系列需要：
●方便编程：
通常，用户把自己的作业按照逻辑关系划分为若干个段，每个段都是从0开始编址，并有自己的名字和长度。
因此，在访问的逻辑地址是由段名（段号）和段内偏移量（段内地址）决定的。
●信息共享：
要实现对程序和数据的共享时，是发信息的逻辑单位为基础的。
比如，共享某个例程和函数。
分页系统中的“页”只是存放信息的物理单位（块），并无完整的意义，不便于实现共享，然而段却是信息的逻辑单位，上此可知，为了现实段的共享，希望存储器管理能与用户程序分段的组织方式相适应。
●信息保护：
信息保护同样是对信息的逻辑单位进程保护，，分段管理方式能更有效和方便地实现信息保护功能。
●动态增长：
在实际应用中，往往有些段，特别是数据段，在使用过程中会不断地增长，而事先又无法确切知道数据段会增长到多大。
前述的其它几种存储管理试，都难以应付这种动态增长的情况，而分段存储管理方式却能较好的解决这一问题。
●动态链接：
动态链接是指在作业运行之前，并不把目标程序段链接起来。
要运行时，先将主程序所对应的目标程序装入内存并启动运行，当运行过程中又需要调用某段时，才将该段（目标程序）调入内存，并进程链接，可见动态链接也要求以段作为管理的单位。
15、在具有快表的段页式存储管理方式中，如何实现地址变换？
16、为什么说分段系统比分页系统更易于实现信息的共享和保护？
答：
分段系统允许若干个进程共享一个或多个分段，对段的保护也十分简单易行。
在分页系统中，虽然也能实现程序和数据的共享，但远不如分段系统来的方便，可以通过一个例子来说明这个问题：
例如：
有一个多用户系统，可同时接纳40个用户，它们都执行一个文本编辑程序，如果文本编辑程。
序有160KB的代码和加外40KB的数据区，由总共需有8MB的内存空间来个用户。
如果160KB的代码是可重入的，则无论是在分页系统还是在分段系统中，该代码都能被共享，在内存中只需保留一份文本编辑程序的副本，此时所需要的内存空间仅为1760KB（160+40*40），假定每个页面的大小为4KB，那么160KB的代码将占用40个页面，数据区占10个页面。
为实现代码的共享，应在每个进程的页表中都建立40个页表项，它们的物理块号都是21#～～60#。
在每个进程的页表中，还须为自己的数据区建立页表项，它们的物理块号分别是61#～～70#，71#～～80#，81#～～90#，…，等等，如A图为分页系统中共享editor的示意图。
在分段系统中，实现共享则容易得多，只需要在每个进程的段中为文本编辑程序设置一个段表项。
图B是分段系统中共享editor的示意图。
17、分页和分段存储管理有何区别？
答：
分页和分段系统有许多相似之处。
比如，两者都采用离散分配方式，且都要通过地址映射机构来实现地址变换。
但在概念上两者完全不同，主要表现在下述的三个方面：
●页是信息的物理单位，分页是为离散实现分配方式，以消减内存的外零头，提高内存的利用率。
或者说，分页仅仅是由于系统管理的需要而不是用户的需要。
段由是信息的逻辑单位，它含有一组其意义相对完整的信息。
分段的目的是为了能更好地满足用户的需要。
●页的大小固定全由系统决定，由系统把逻辑地址划分产号和怘内的地址两部分，是由机器硬件实现的，因而在只能有一种大小的页面原则是段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编㡽时，根据信息的性质来划分。
●分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；分段的作业地址空间则是二维的，程序员在标识一个地址时，即需给出段名，又需给出段内地址。
分页
分段
信息单位
物理单位
逻辑单位
信息完整性
离散分配方式
意义相对完整
需要
系统管理的需要
用户的需要
页的大小
固定，由系统决定
不固定，由用户决定
地址空间
一维
二维
试述分页系统和分段系统的主要区别。
解：
分页和分段有许多相似之处，比如两者都不要求作业连续存放。
但在概念上两者完全不同，主要表现在以下几个方面：
（1）页是信息的物理单位，分页是为了实现非连续分配，以便解决内存碎片问题，或者说分页是由于系统管理的需要。
段是信息的逻辑单位，它含有一组意义相对完整的信息，分段的目的是为了更好地实现共享，满足用户的需要。
（2）页的大小固定且由系统确定，将逻辑地址划分为页号和页内地址是由机器硬件实现的。
而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时根据信息的性质来划分。
（3）分页的作业地址空间是一维的。
分段的地址空间是二维的。
18、试全面比较连续分配和离散分配方式?
答：
连续分配是指为一个用户程序分配一个连续的内存空间。
又可进一步分为单一连续分配、固定分区分配、动态分区分配和动态重定位分区分配四种方式。
连续分区方式可使一个进程分得一个连续的内存空间，这样一来有利于程序的执行，但同时又会产生很多的碎片，浪费大量的系统资源。
离散分区是采用段式或页式或段页式的分配方式将一个进程装入一些离散的内存中，这样有利于内存的利用，并且可以方便程序员在更大的空间进行编程工作。
19、虚拟存储器有哪些特征？
其中最本质的特征是什么？
答：
虚拟存储器有以下特征：
离散性。
所谓离散性是指在内存分配时采用离散分配方式，这是其它几个特征的基础。
保证作业分次调入内存而不浪费内存资源。
多次性。
所谓多次性是指将一个作业分次调入内存运行，而把当前要运行的内部分程序和数据先调入内存运行，其它等待。
对换性。
所谓对换性是指允许在作业的运行过程中换进、换出。
即当前要运行的程序调入内存（换进），暂不运行的调至外存的对换区（换出）。
虚拟性。
虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。
其中离散性是虚拟存储器最本质的特征。
20、实现虚拟存储器需要哪些硬件支持？
答：
主要的硬件支持有：
●请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构。
●缺页中断机构，即每当用户程序要访问的页面还没有调入内存时，便产生一缺页中断，以请求OS将所缺的页调入内存。
●地址变换机构，它同样是在纯分页地址变换机构的基础上形成的。
21、实现虚拟存储器需要哪几个关键技术？
答：
为实现虚拟存储器，首先需要扩充页表，增加状态位以指出所需页是否在内存，增加外存始址以便调入页面，增加引用位以供置换算法用，增加修改位使得换出时减少写盘次数。
另外，还要使用两种关键技术：
（1）请求调页技术。
指及时将进程所要访问的、不在内存中的页调入内存。
该功能是由硬件（缺页中断机构发现缺页）和软件（将所需页调入内存）配合实现的。
（2）置换页技术。
当内存中已无足够空间用来装入即将调入的页时，为了保证进程能继续运行，系统必须换出内存中的部分页，以腾出足够的空间。
具体的置换操作并不复杂，其关键是应将哪些页换出，即采用什么置换算法。
22、在请求分页系统中，页表应包括哪些数据项？
每项的作用是什么？
答：
在请求分页系统中的每一个页表项如下：
●状态位P：
用于指示该页是否已调入内存，供程序访问时参考。
●访问字段A：
用于记录本页在一段时间内被访问的次数，或记录本页已有多长时间没有被访问，供选择换出页面时参考。
●修改位M：
表示该页在调入内存后是否被修改过，由于内存中的每一页都在外存上保留一分副本，因此，若没有被修改，在置换该页时就不需再将该页写回到外存上，以减少系统的开销和启动磁盘的次数，若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。
简言之，M位供置换页面时参考。
●外存地址，用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。
23、在请求分页系统中，应从何处将所需页面调入内存？
答：
在请求分页系统中将页面调入内存大致分为三种：
系统拥有足够的对换空间，这时可以全部从对换区调入所需页面，以提高调页速度。
系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时就不必换出到对换区，以后再调入，仍从文件区直接调入。
对于可能被修改的部分，换出时须换到对换区，以后需要时就须从对换区调入。
对UNIX方式，由于系统中允许页面共享，某进程所请求的页面有可能已由其它进程调入内存，此时就无须再从对换区调入。
24、在请求分页系统中，常采用哪几种页面置换算法？
25、在请求分页系统中，通常采用哪种页面分配方式？
为什么？
26、在一个请求分页系统中，采用LRU、FIFO页面置换算法时，如果一个作业的页面走向为1、3、2、1、1、3、5、1、3、2、1、5，当分配给该作业的物理块数M分别为3和4时，试计算在访问过程中所发生的缺页次数和缺页率，并比较所得的结果。
答：
LRU
1
3
3
2
1
3
5
1
3
2
1
3
2
2
1
3
5
1
3
2
1
1
3
2
1
1
3
5
1
3
2
1
5
缺
缺
缺
缺
缺
缺
当物理块数为3时，缺页次数为6，缺页率为6/12。
2
2
2
5
5
3
1
3
3
2
1
3
5
1
3
2
1
3
2
2
1
3
5
1
3
2
1
1
3
2
1
1
3
5
1
3
2
1
5
缺
缺
缺
缺
当物理块数为4时，缺页次数为4，缺页率为4/12。
FIFO
1
1
1
1
3
2
5
1
1
3
1
3
3
3
3
2
5
1
3
3
2
1
3
2
2
2
2
5
1
3
2
2
5
缺
缺
缺
缺
缺
缺
缺
缺
当物理块数为3时，缺页次数为8，缺页率为8/12。
1
1
1
1
1
1
1
1
1
1
3
3
3
3
3
3
1
3
3
3
3
2
2
2
2
2
2
1
3
2
2
2
2
5
5
5
5
5
5
缺
缺
缺
缺
当物理块数为4时,缺页次数为4，缺页率为4/12。
27、实现LRU算法所需的硬件支持是什么？
答：
LRU算法须要有以下两类硬件支持：
●寄存器：
为了记录某进程在内存中各页的使用说明，须为每个在内存中的页面配置一个移位寄存器，可表示为：
R=Rn-1Rn-2Rn-3…R2R1R0,
当进程访问某物理块时，要将相应寄存器的Rn-1位置变成1，此时，定时信号将每隔一定时间将寄存器右移一位。
●栈：
可利用一个特殊的栈来保存当前使用的各个页面号，每当进程访问某页面时，便将该页面号从栈中移出，将它压入栈顶。
因此，栈顶始终是最新被访问页面的编号，而栈底则是最久没有使用的页面号，假定现有一进程所访问的页面号序列为：
4、7、0、7、1、0、1、2、1、2、6随着进程的访问，栈中页面号的变化情况如下图所示，在访问页面6时发生了缺页，此时页面4是最近最久没有被访问的页，应将它置换出去。
28、试说明改进型Clock置换算法的基本原理。
29、说明请求分页系统中的缺页中断处理过程。
30、如何实现分段共享？
答：
为了实现分段共享，可在系统中配置一张共享段表，所有各共享段都在共享段表中占有一表项。
表项中记录了共享段的段号、段长、内存始址、存在位等信息，并记录了人共享此分段的每个进程的情况。
共享段表如下图所示。
其中的各项说明如下：
●共享进程计数count。
非共享段仅为一个进程所需要。
当进程不再需要该段时，可立即释放该段，并由系统回收该段所有占用的空间。
而共享段是为多个进程所需要的，当某进程不再需要而释放它时，系统并不回收该段所占内存，仅当所有共享该段的进程全部都不再需要它时，才由系统回收该段所占内存区。
为了记录有多少个进程需要共享该分段，特设置了一个整型变量count.
●存取控制字段。
对于一个共享段，应给不同的进程以不同的存取权限。
例如，对于文件主，通常允许他读和写，而对其它进程，则可能只允许读，甚至只允许执行。
●段号。
对于一个共享段，不同的进程可以各用不同的段号去共享该段。
第二部分分析计算题
1、在一请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为1、3、1、1、3、5、1、3、2、1、5，当分配给该作业的物理块数M分别分3和4时，试计算在访问过程中所发生的缺页次数和缺页率，并比较所得到的结果。
M=3时：
缺页率为：
5/11=71.43%
M=4时：
缺页率为：
4/11=36.37%
比较：
利用此算法的好处为，当分配的物理块数足够多时，可以将缺页率降低到每页只一次调入（如M=4的情况）。
显然M=4时的缺页率小于M=3时的缺页率，但就内存的使用情况来就，M=3时的内存使用少于M=4时的内存，由此可见利降低缺页率是物理块为牺牲的。
2、表4.2给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。
现有以下作业序列：
96K、20K、200K。
若用首次适应算法和最佳适应算法来处理这些作业序列，试问哪一种算法可以满足该作业序列的请求，为什么？
[分析及相关知识]首次适应算法要求空闲分区按地址递增的次序排列，在进行内存分配时，总是从空闲分区表的首部开始顺序查找，直到找到第一个能满足其大小要求的空闲分区为止。
然后，再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表中。
最佳适应算法要求空闲分区按大小递增的次序排列，在进行内存分配时，总是从空闲分区表首开始顺序查找，直到找到第一个能满足其大小要求的空闲分区为止。
如果该空闲分区大于作业的大小，则与首次适应算法相同，将剩余空闲区仍留在空闲区表中。
表4.2空闲分区表
分区号
大小
起始地址（递增）
1
32K
100K
2
10K
150K
3
5K
200K
4
218K
220K
5
96K
530K
解：
（1）若采用最佳适应算法，在申请96K存储区时，选中的是5号分区，5号分区大小与申请空间大小一致，应从空闲分区表中删去该表项；接着申请20K时，选中1号分区，分配后1号分区还剩下12K；最后申请200K，选中4号分区，分配后剩下18K。
显然采用最佳适应算法进行内存分配，可以满足该作业序列的需求。
为作业序列分配了内存空间后，空闲分区表如表4.3（a）所示。
（2）若采用首次适应算法，在申请96K存储区时，选中的是4号分区，进行分配后4号分区还剩下122K；接着申请20K时，选中1号分区，分配后剩下12K；最后申请200K，现有的五个分区都无法满足要求，该作业等待。
显然采用首次适应算法进行内存分配，无法满足该作业序列的需求。
这时的空闲分区表如表4.3（b）所示。
表4.3空闲分区表
（a）
分区号
大小
起始地址
1
12K
100K（120?
）
2
10K
150K
3
5K
200K
4
18K
220K（420?
）
（b）
分区号
大小
起始地址
1
12K
100K
2
10K
150K
3
5K
200K
4
122K
220K
5
96K
530K
3、某操作系统采用可变分区分配存储管理方法，用户区为512K且始址为0，用空闲分区表管理空闲分区。
若分配时采用分配空闲区低地址部分的方案，且初始时用户区的512K空间空闲，对下述申请序列：
申请300K，申请100K，释放300K，申请150K，申请30K，申请40K，申请60K，释放30K
回答下列问题：
（1）采用首次适应算法，空闲分区中有哪些空块（给出始址、大小）？
（2）采用最佳适应算法，空闲分区中有哪些空块（给出始址、大小）？
（3）如再申请100K，针对
（1）和
（2）各有什么结果？
[分析及相关知识]为描述方便起见，本题用“（分区首址，分区长度）”的形式描述系统中的分区。
由题中所给条件可知，最初系统中只有一个空闲区，大小为512K，始址为0，即（0，512K）。
操作
已分配空间
空闲块
初始
无
（0，512K）
申请300K
（0，300K）
（300K，212K）
申请100K
（0，300K）
（300K，100K）
（400K，112K）
释放300K
（300K，100K）
（0，300K）
（400K，112K）
申请150K
（0，150K）
（300K，100K）
（150K，150K）
（400K，112K）
申请30K
（0，150K）
（150K，30K）
（300K，100K）
（180K，120K）
（400K，112K）
申请40K
（0，150K）
（150K，30K）
（180K，40K）
（300K，100K）
（220K，80K）
（400K，112K）
申请60K
（0，150K）
（150K，30K）
（180K，40K）
（220K，60K）
（300K，100K）
（280K，20K）
（400K，112K）
释放30K
（0，150K）
（180K，40K）
（220K，60K）
（300K，100K）
（150K，30K）
（280K，20K）
（400K，112K）
升级会员 