. 赵盈盈 2011210593 第五章作业 1. 存储管理的功能及目的是什么？ 答：存储管理功能：
内存分配与管理。（1）记住每个存储区域的状态。（2）实施分配。分配方式有两种：静态
分配与动态分配（3）回收。
内存共享。共享的信息包括：代码共享（纯代码），数据共享
存储保护。存储保护内容有：保护系统程序区不受用户有意无意的侵犯；不允许用户程序
写不属于自己地址空间的数据。（1）以防止地址越界；（2）以防止操作越权
“扩充”内存容量。具体实现是在硬件支持下，软件硬件相互协作，将内存与外存结合起
来统一使用。
地址映射。也称作重定位。将逻辑地址转换成物理地址。有两种方法：静态地址映射，动
态地址映射。
存储管理目的：
充分利用内存，为多道程序并发执行提供存储基础； 尽可能方便用户使用；
解决程序空间比实际内存空间大的问题； 程序在执行时可以动态伸缩； 内存存取速度快； 存储保护与安全； 共享与通信；
了解有关资源的使用状况； 实现的性能和代价；
2. 什么是逻辑地址？什么是物理地址？为什么要进行二者的转换工作？ 答：逻辑地址：就是cpu逻辑段管理内存而形成的地址。
物理地址：就是程序或数据在内存中的实际地址，即内存单元的地址，也就是被装入内存的内
存地址寄存器的地址。
转换原因：当程序装入内存时，操作系统要为之分配一个合适的内存空间，由于程序逻辑地址
与所分配到的内存物理地址编号不一致，而cpu执行指令时是按物理地址进行的，所以要进行地址转换。
3. 什么是动态地址重定位？试用图画出动态地址重定位的过程。
答：动态地址重定位就是指动态地址映射。是地址映射的一种方式。它是在程序执行过程中要访
问数据时在进行地址映射，即逐条指令执行时完成地址映射。 0 0 有效地址 1000 100 1000 LOAD 1500 500 LOAD 1500 500 3333
800 1500 3333 +
1800
内存空间
1 / 6
. 4. 在分区分配方案中，回收一个分区时有几种不同的邻接情况，在各种情况下应如何处理？ 答：有四种：上邻，下邻，上下相邻，上下不相邻。
（1）回收分区的上邻分区是空闲的，需要将两个相邻的空闲区合并成一个更大的空闲区，然后修改空闲区表。
（2）回收分区的下邻分区是空闲的，需要将两个相邻的空闲区合并成一个更大的空闲区，然后修改空闲区表。
（3）回收分区的上、下邻分区都是空闲的，需要将三个空闲区合并成一个更大的空闲区，然后修改空闲区表、
（4）回收分区的上、下邻分区都不是空闲的，则直接将空闲区记录在空闲区表中。
5. 如图1所示，主存中有两个空白区。现有这样一个作业序列：
作业1 要求 50KB； 作业2 要求 60KB； 作业3 要求 70KB。
0 0 mov r1, [3500] 1KB 50KB 120KB
2KB
3KB 250KB
12345 78KB 4KB-1
图2
图1
若用首次适应算法和最佳适应算法和最差适应算法分别来处理这个作业序列，试问哪一种算法可以分配得下，为什么？
答：（1）首次适应算法：原状态作业1?加入作业2?作业3 首先把120>50KB,分出50给作业1.出现空闲区70KB
其次，给作业二找空闲区刚出来的空闲区70KB>60KB,给作业二60KB，新出现10KB空闲区 最后给作业三找空闲区，10KB<70KB，78KB分给作业三70KB，先出现空闲区8KB。 此算法分配得下。最后状态如图（1）
（2）最佳适应算法：原状态作业1?加入作业2?作业3
首先，找到满足作业一的最小空间78KB>58KB，分出50KB给作业一；出现新空闲区28KB。 其次，为作业二找空闲区，28KB<60KB不满足作业二，另一空闲区120KB>60KB,分出60KB给作业二，出现新空闲区60KB。
最后，为作业三找空闲区，此时两个空闲区28KB<70KB,60KB<70KB,都无法满足作业三需求。 所以该算法不下。最后状态如图（2）。
（3）最差适应算法：原状态作业1?加入作业2?作业3
首先，为作业一找空闲区，最大的120KB>50KB,分割出50KB给作业一，产生新的空闲区70KB； 其次，作业二找空闲区，此时78KB>70KB，为最大的空心区，从78KB中分割出60KB给作业二，产生新的空闲区18KB；
最后，为作业三找空闲区，此时最大空闲区70KB正好等于作业三大小。分配给作业三。最终剩下一个空闲区18KB。该算法分配得下。最总状态如图（3）
2 / 6
. 作业一（50KB） 作业二（60KB） 空闲区10KB 作业三70KB 空闲区8KB 作业二（60KB） 空闲区60KB 作业一（50KB 空闲区28KB 作业一（50KB） 作业三（70KB） 作业二（60KB） 空闲区18KB
图（1）首次适应算法 图（2）最佳适应算法 图（3）最差适应算法
6. 已知主存有256KB容量，其中OS占用低纸20GB，可以有这样的一作业序列：
作业1 要求 80KB； 作业2 要求 16KB； 作业3 要求 140KB； 作业1 完成； 作业3 完成；
作业4 要求 80KB； 作业5 要求 120KB。
试用首次适应算法和最佳适应算法和最差适应算法分别处理上述作业序列（在序储分配时，从空白区高址处分割作为已分配区），并完成以下各步：
（1）画出作业1、2、3进入主存后，主存的分配情况。 答：（1） 首次适应算法、最佳适应算法、最差适应算法的分配方式都如下图（1）所示 0KB 19KB OS（20KB） 作业三（80KB） 160K176KB 225KB 作业二（16KB） 作业一（140KB） 160K176KB 225KB 作业二（16KB） 0KB 19KB OS（20KB） 图（1） 图（2） （2）作业1、3完成后，画出主存分配情况。 答：分配情况如上图（2）所示。
（3）画出两种算法中空白区的分区描述器信息（假定分区描述器所需占用的字节数已包含在作业所要求的主存容量中）及空白链接情况。
答：1.首次适应算法空白描述信息和空白区链接情况：
3 / 6
.
（4）哪种算法对该作业序列而言是适合的？
答：作业一和作业三完成之后按三种适应算法分配内存情况如下：
1、首次适应算法：作业三释放的空白区80KB，作业一释放空白区140KB。
为作业四找空白区，从140KB分割出80KB给作业四，产生新的空白区60KB，
为作业五找空白区，剩下两个空白区都小于120KB，所以无法满足作业五要求，所以该算 法分配不下。
2、最佳适应算法： 作业三释放的空白区80KB，作业一释放空白区140KB。 为作业四找空白区，从80KB分割出60KB给作业四，产生新的空白区20KB，
为作业五找空白区，20KB<120KB，140KB可以，从中分割出120KB给作业五，产生新的 空白区20KB。所以该算法是合适的。
3、最差适应算法：作业三释放的空白区80KB，作业一释放空白区140KB。 为作业四找空白区，从最大的空白区140KB分割出80KB给作业四，产生新的空白区60KB， 为作业五找空白区，剩下两个空白区都小于120KB，所以无法满足作业五要求，所以该算 法分配不下。
所以对该体而言，最好的算法是最佳适应算法
7. 已知主存容量为64K，某一作业A的地址空间如图2所示，它的4个页面（页面大小为1）0、1、2、3被分配到主存的2、4、6、7块中，要求并回答。
（1）画出作业A的页映像表。 答： 逻辑页号 内存块号 2 0 4 1
2 6
7 3
（2）当200号单元处有一条指令“mov r1,[3500]”执行时，如何进行正确的地址变换以使3500处的内容12345装入r1中？
答：3500/1024=3 所以在逻辑第三页。350024=428，所以页内偏移地址为428。 查看页表，第三页对应内存块号为7.所以对应内存首地址即物理地址为7*1024+428=7596
8. 什么是虚拟存储器？在页式系统中如何实现虚拟存储？
答：虚拟存储器是指：把内存与外存结合起来使用，从而得到一个容量很大的、速度足够快的“内存”，这就是虚拟存储器，简称虚存。
页式系统实现虚存的工作原理：在进程开始之前，不是装入全部页面，二十装入一个或零个界面，之后根据进程运行的需要，动态装入其他页面；当内存空间已满，而有需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。
9. 如果主存中的某页正在与外部设备交换信息，缺页中断时可以将这一页淘汰吗？为了实现正确的页面调度，应如何扩充页表的功能？
答：不可以。在使用虚拟页式存储管理时需要在页表中增加一些内容，得到页表内容为：页号、驻留位、内存块号、外存地址、访问位、修改位。其中驻留位，又称中断位，表示该页是在内存还
4 / 6
. 是在外存；访问位表示该页在内存期间是否被访问过，称为R位；修改为表示该页在内存中是否被修改过，称为M位。访问位与修改位可以用来决定置换哪个页面，具体由页面算法来决定。
10. 什么是置换算法？在页式系统中最常用的置换算法是什么？如何实现之？
答：在地址映射过程中，若在页表中发现所要访问的页面不在内存，则发生缺页中断。当发生缺页中断时，操作系统必须在内存中选择一个页面将其移除内存，以便为即将调入的页面让出空间。而，实现清除页面，调入新页面的算法就是页面置换算法。
页式系统中最常用的置换算法有：理想页面置换算法、先进先出页面置换算法、最近最少使用页面置换算法。
（1）理想页面置换算法（OPT），这是一个理想情况下的算法，实际上不可能实现。 （2）先进先出页面置换算法（FIFO），该算法很容易实现。以把装入内存的那些页面的页号按进入的先后次序排好队列，每次总是调出队首的页，当装入新的页面后，把新页的页号排到队尾。由操作系统维护一个所有当前在内存中的页面的链表，坐牢的链表在头上，最新的在表尾。当发生缺页时，淘汰表头的页面并把新调入的页面加到表尾。
（3）最近最少使用页面置换算法（LRU），该算法可以实现，在发生缺页时，淘汰最久未使用的页面。可以在页表中为每一页加一个“计时”标志，记录该页面自上次被访问以来经历的时间，每次访问一次都应从“0”，重新计时。当要装入新页时，检查页表中各页的计时标志，从中选出计时值最大的那一页调出（即最近一段时间里最长时间没有被使用过的页），并且把各页的计时标志全部记为“0”，重新计时。当再一次产生缺页中断时，又可找到最近最少使用的页，将其调出。这种实现方法必须对每一页的访问情况时时刻刻地加以记录和更新，实现起来比较麻烦并且开销大。 还有一种简单的方法实现LRU，用一些特殊的硬件实现，这要求有一个64位的计数器C，它在每一条指令执行完后自动增加1，每个页表项必须有一个足够容纳这个计数器值的域。在每次访问内存后，当前的C值被保存到被访问页面的页表项中。一旦发生缺页，操作系统检查所有的计数器的值找到最小的一个，这一页就是最久未使用的页。
11. 什么是进程在某时刻t的工作集？工作集与页面的调入和淘汰策略有什么关系？
答： 是指一个进程在t时刻访问页面的集合。利用工作集模式可以防止抖动，也可以进行页面置换。
工作集对存储器的有效利用和系统吞吐量的提高都有重要影响。对于给定的访问序列选取定长的区间，称为工作集窗口，落在工作集窗口中的页面集合就是工作集。如果分配给一个进程的工作集较少，进程过程中将频繁发生缺页中断；如果能为进程提供合适的工作集，则可以减少缺页中断次数；如果系统分配给进程的工作集较大，也不能显著减少交换次数，因而存储器的利用率会相对降低。
12. 说明页面和段的区别。 答：（1）页是信息的物理单位，段是信息的逻辑单位。
（2）页面的大小有系统决定，而且每页的大小都相同；各段的长度因段而异，由用户决定。 （3）分页的作业地址空间是一维的，分段的作业地址空间是二维的。 （4）分页的活动对用户是透明的，分段对用户是不透明的。
13. 页式系统和段式系统的地址变换过程十分相似，但二者之间又有本质的区别，请说明二者的区别是什么？为什么会有这个区别？ 答：（1）请求分页存储管理的作业地址空间是一个单一的线性地址空间，二分段存储管理的地址空间是一个二维的地址空间。
5 / 6
. （2）请求分页存储管理中，页的大小是固定的，分页活动用户是不可见的；分段存储管理中，段的大小是不定的，是信息的逻辑单位，用户是可见的。
（3）请求分页存储管理中，把程序地址分成页号p和页内偏移量w是硬件完成的功能；分段存储管理中，把程序地址分成段号s和段内偏移量d是软件的功能。 主要是作业地址的存储结构不同，所以地址映射方式也会不同。
14. 共享有什么好处？在段式系统中如何实现段的共享？
答：共享好处：信息化的时代，资源的共享更容易使得人们以及团队成员之间优势互补，互通有无，更容易实现共赢。共享提高了资源利用率，可以创造更多的财富。
段模式是以段为单位划分和连续完整存放。段间是不一定连续编址的，即为二维编址。进程逻辑空间（二维的）最接近用户观点，就像是高级程序设计语言更接近自然语言一样，这样就克服了页式的非逻辑划分给共享和保护与动态伸缩带来的不自然性。段模式提供的二维地址最符合用户观点和程序逻辑。段式最大的优点就是实现共享和保护。
15. 如何实现段式系统中的存取控制？
答：首先建立段表，段表包括逻辑段号，物理段起始地址和物理段长度三项内容。其次建立内存分配表。内存分配表包括已分配区表和空闲区表。段式存储管理为程序的每一个分段分配一个连续的内存空间。空闲区的分配也可以采用首先适应算法、最佳适应算法、最坏适应算法。进行内存分配的时候根据段长照出一个可以容纳该段的一个空闲区，分割这个空闲区，一部分用来装入该信息，另一部分仍为空闲区。但没有足够大的空闲区时，仍可采用拼接技术来合并分散的空闲区。
16. 试说明段页式地址变换过程。 答：（1）根据逻辑地址中的段号S查找快表。如果找不到，则形成物理地址，否则进行如下步骤。 （2）通过段表始址寄存器SB，查找段表在内存中的始址； （3）通过段表并根据段号S，查找页表所在位置；
（4）访问页表，根据逻辑页号P查找该页所在的内存块号P’；
（5）将内存块号P’和逻辑地址中的页内地址D拼接，形成访问内存单元的物理地址；
（6）将有关内容填入快表，如有必要，则根据淘汰算法淘汰快表的一行，一填入新的内容。
6 / 6
操作系统第5章作业答案
