第四章
一、为什么要配置层次式储存器？
为了使存储器跟上处理机的运行速度，提高处理机的使用率，同时尽量降低存储器的成本，采用多层结构的存储器系统是性价比最高的方案
二、可采用哪几种方式将程序装入内存？它们分别适合用于何种场合？
绝对装入方式：将目标模块装入到内存中事先指定的位置，计算机系统很小时，完全有可能知道程序将驻留在内存的什么位置。因此可采用绝对装入的方式将程序装入内存指定位置中
可重定位装入方式：可以根据内存使用的具体情况将装入模块装入到内存的适当位置，但不允许程序运行时在内存中移动位置，这种方式适用于在多道程序环境下
动态运行时的装入方式：程序在运行过程中，内存的位置因为页面的置换而经常发生改变，这种方式适用于拥有段页式储存管理的操作系统中
三、何谓静态链接？静态链接时需要解决两个什么问题？
在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的装配模块，以后不再拆开。静态链接时需要解决对相对地址进行修改和变换外部调用符号这两个问题
对相对地址进行修改：编译产生的模块中，内存地址都是从0开始，在装入内存时需要进行内存偏移操作，即加上相对地址L
变换外部调用符号：将每个模块中所用的外部调用符号变换为相对地址
四、何谓装入时动态链接？装入时动态链接方式有何优点？
用户将源程序编译后所得的一组目标模块，在装入内存时，采用边装入边链接的方式。该方式便于修改和更新库函数，便于实现对库函数模块的共享
五、何谓运行时动态链接？运行时动态链接方式有何优点？
对某些模块和链接推迟到程序执行时才进行，这种方式不仅能加快程序的装入过程，还能节省大量的内存空间
六、在动态分区分配方式中，应如何将各空闲分区连接成空闲分区链？
使用空闲分区表：在系统中设置一张空闲分区表，用于记录每个空闲分区的情况
使用空闲分区链：对每一个分区设置一个前向指针和后向指针，用于链接前一个空闲分区和后一个空闲分区
七、为什么要引入动态重定位？如何实现？
为了充分利用内存空间中的碎片空间，并且降低计算机整理内存的频次，由此引入了动态重定位。动态重定位使用了一个重定位寄存器，用于记录偏移的地址量，在每次取址时用程序的逻辑地址加上重定位寄存器中的地址，得到内存中的物理地址，在进行内存碎片整理之后，只需要修改重定位寄存器中的地址即可
八、什么是基于顺序搜索的动态分区分配算法？它可以分为哪几种？
在内存空闲链中，依次搜索空闲分区上的空闲分区，寻找一个大小能满足要求的分区，它可以分为以下4种算法：
- 首次适应（first fit, FF）算法：该算法要求空闲分区链以地址递增的次序链接，在分配内存时从链的头部开始寻找，直至找到一个大小能满足要求的空闲分区
- 循环首次适应算法（next fit, NF）：为避免低地址部分留下许多很小的空闲分区，该算法从上次找到的空闲分区开始向后寻找，直至找到一个能满足要求的空闲分区
- 最佳适应（best fit, BF）算法：该算法要求将所有的空闲分区按照容量从小到大的顺序形成空闲分区链。总是把能满足要求的、又是最小的空闲分区分配给作业
- 最坏适应（worst fir, WF）算法：与最佳适应算法相反，总是把最大的空闲区分割一部分存储空间给作业使用
九、在采用首次适应算法回收内存时，可能出现哪几种情况？应该怎样处理这种情况？
回收区与插入点的前一个空闲分区相邻接：此时应该将回收区与插入点的前一分区合并
回收区与插入点的后一个空闲分区相邻接：此时应该将两个分区合并，回收区的首地址作为新空闲区的地址，更新空闲分区链表信息
回收区同时与插入点的前、后两个空闲分区邻接：此时将三个分区合并，使用前分区的地址作为新空闲区的地址，更新空闲分区链表信息
回收区与前后空闲分区不邻接：此时应单独为回收区新建一个表项，并插入到空闲分区链表中的适当位置
十、什么是基于索引搜索的动态分区分配算法？它可分为哪几种？
利用空闲分区索引快速搜索空闲分区，分配空闲分区的算法，它可以分为以下三种算法：
- 快速适应（quick fit）算法：又称为分类搜索法，对于每一类具有相同容量的所有空闲分区，单独设立一张管理索引表。首先根据进程长度，从索引表中找到能够容纳它的最小空闲区链表，再从链表中取下第一块进行分配。该算法的优点是分配速度快，但缺点是内存回收整理时算法十分复杂
- 伙伴系统（buddy system）：将所有分区划分为大小均为2的k次幂的空间，将相同大小空间的分区使用双向链表建立索引。在伙伴系统中，空间的分配和回收性能取决于查找空闲分区的位置和分割、合并空闲分区所花费的时间。该算法比快速适应算法好，比顺序搜索算法略差
- 哈希算法：利用哈希快速查找的优点，以及空闲分区在可利用空闲区表中的分布规律，建立哈希函数，构造哈希表。当空闲分区进行分配时，根据所需空闲分区大小，通过哈希函数计算，获得分区在哈希表中的位置，从而得到相应的空闲分区链表，实现最佳分配策略
十一、分区储存管理中常用哪些分配策略？比较它们的优缺点。
常用的分配策略：首次适应算法，循环首次适应算法，最佳适应算法，最坏适应算法
- 首次适应算法：保留了高位地址部分较大的储存空间，有利于后来的大型作业分配，但同时低位地址不断被划分，碎片化更加严重
- 循环首次适应算法：内存空间分配均匀，减少了系统查找的开销，但缺乏大空间内存区域，导致不能装入大型作业
- 最佳适应算法：每次给进程分配的空间区域都最适合该进程，在内存中留下难以利用的空间
- 最坏适应算法：剩下的空间都不太小，产生碎片的几率小，对中小型作业的分配有利，但不利于大型作业的分配
十二、为什么要引入对换？对换可分为哪几种类型？
一方面由于内存中的某些进程由于某事件尚未发生而被阻塞运行，却占用了大量的内存空间，导致内存空间不足，使系统的吞吐量下降，为了解决这个问题而引入了对换功能。对换可以分为：整体对换，页面对换
十三、对文件区管理的目标和对对换空间管理的目标有何不同？
对文件区的管理目标：首先是提高文件储存空间的利用率，然后才是提高对文件的访问速度
对对换空间的管理目标：提高进程换入和换出的速度，然后才是提高文件储存空间的利用率
十四、为实现对换，系统应具备哪几方面的功能？
系统应具备的功能：进程的换出，进程的换入，对换空间管理
十五、在以进程为单位进行对换时，每次是否将整个进程换出？为什么？
不一定将整个进程换出，因为进程中包含了进程信息，程序代码和数据。其中的数据可能由几个进程共享使用，因此不一定将整个进程换出
十六、基于离散分配时所用的基本单位不同，可将离散分配分为哪几种？
可分为：分页储存管理，分段储存管理，段页式储存管理
十七、什么是页面？什么是物理块？页面的大小应如何确定？
页面是进程逻辑地址空间的划分，一个进程可以划分为若干个页面
物理块是内存物理地址空间的划分，并对每个块加以编号
页面太小会导致页表过长，占用内存且降低效率，页面太长会导致内存空间的浪费，降低换进换出的效率。因此页面一般划分为1KB～8KB
十八、什么是页表？页表的作用是什么？
页表中记录了每个页面所对应的物理块，实现了从页号到物理块号的地址映射
十九、为实现分页存储管理，需要哪些硬件支持？
动态重定位技术，虚拟储存技术，多道程序设计技术
二十、在分页系统中是如何实现地址变换的？
首先通过页表去寻找该进程的内存基址，然后检查该地址是否合法，最后通过内存偏移计算，得出逻辑地址
二十一、具有快表时是如何实现地址变换的？
在CPU给出有效地址之后，由地址变换机构自动地将页号P送入高速缓冲寄存器，并将此页号与高速缓存中的所有页号进行比较，若其中有与此相匹配的也好，便表示所要访问的页表在快表中，则可以直接从快表中读出该页所对应的物理块号，并送到物理地址寄存器中。如在快表中未找到对应的页表项，则需要访问内存中的页表，找到之后把页表读出的物理块号送往地址寄存器，同时更新快表项
二十二、在具有快表的段页式存储管理方式中，如何实现地址变换？
首先通过快表直接查找目标块号，若越界则执行中断操作，如果找到则直接送往地址寄存器，未找到则在内存页表中查找，找到之后送往地址寄存器
二十三、为什么说分段系统比分页系统更易于实现信息的共享和保护？
分页系统中的“页”只是单纯地存放物理信息，并没有完整的数据逻辑意义，而段是信息的逻辑单位，因此更容易实现信息的共享和保护
二十四、分页和分段存储管理有何区别？
页是信息的物理单位，分页是为了实现离散的分配方式，而段是信息的逻辑单位，其包含了有意义的、完整的信息。页的大小由系统决定，而段的大小是不确定的。分页的地址空间是一维的，只需要一个记忆符号就可以表示一个地址，段的地址空间是二位的，需要同时给出段名和段内地址
第五章
一、常规储存器管理方式具有哪两大特征？它对系统性能有何影响？
一次性：作业必须一次性地全部装入内存后才能开始运行
驻留性：作业被装入内存之后，整个作业需要一直驻留在内存中，直至作业运行结束
这两个特征占据了大量的内存空间，使得一些需要运行的作业因为内存不足而无法装入运行，降低了系统的吞吐量
二、什么是程序运行时的时间局限性和空间局限性？
时间局限性：如果程序中的某条指令被执行，则不久以后该指令可能再次执行。产生的原因是在程序中存在着大量的循环操作
空间局限性：一旦程序访问了某个储存单元，在不久之后，其附近的储存单元也将被访问，典型的情况便是程序的顺序执行
三、虚拟存储器有哪些特征？其中最本质的特征是什么？
多次性：作业不需要一次性地装入内存后运行，而是将当前要运行的一部分装入运行，通过多次的装入完成整个作业的运行
对换性：允许作业在运行过程中，在内存与外存之间换入换出
虚拟性：能够从逻辑上扩充内存容量，使小容量的内存能够运行比它容量更大的程序
其中多次性是最本质的特征，有了多次性的特征，作业能够在内存和外存之间交换
四、实现虚拟存储器需要哪些硬件支持？
请求分页的页表机制和请求分段的段表机制
缺页中断机构和缺段中断机构
地址变换机构
五、实现虚拟存储器需要哪几个关键技术？
请求调页的软件和实现页面置换的软件，请求调段的软件和实现段置换的软件
六、在请求分页系统中，页表应包括哪些数据项？每项的作用是什么？
页号：分页系统中的页面号码
物理块号：内存中的物理地址
状态位P：表示该页是否已调入内存，供程序访问时参考
访问字段A：记录本页在一段时间内被访问的次数
修改位M：标示该页在调入内存后是否被修改过
外存地址：指出该页在外存上的地址，通常是物理块号
七、在请求分页系统中，应从何处将所需页面调入内存？
分为以下三种情况：
- 系统拥有足够的对换区空间：这时可以全部从对换区调入所需页面，以提高调页的速度
- 系统缺少足够的对换区空间：这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改，则不必再将它们重写到磁盘，以后都直接调入。但对于那些可能被修改的部分，在将它们换出时便需要调到对换区，以后需要时再从对换区调入
- UNIX方式：由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应该从文件区调入。而对于曾经运行过但又被换出的页面就放在对换区，在下次调入时从对换区调入
八、试说明在请求分页系统中页面的调入过程。
首先向CPU发出缺页中断，中断处理程序保留当前运行环境，分析中断原因后转入缺页中断处理程序。该程序通过查找页表得到该页在外存的物理块后，如果此时内存能够容纳新页，则启动磁盘I/O，将所缺页面调入内存，然后修改页表。如果内存已满，则需要先按照某种置换算法，从内存中选出一页准备换出，如果该页面的修改位为1，则需要将其写入对换区中，如果修改位为0，则可以直接将要换入的页面写到该页面上，然后修改页表。最后程序将页表写入到快表中，同时形成所要访问数据的物理地址，再去访问内存数据
九、在请求分页系统中，常采用哪几种页面置换算法？
最佳置换（Optimal）算法：选择的被淘汰的页面将是以后永不使用的，或者是未来最长时间内不会被访问的页面。但由于程序运行无法预知，因此该算法无法实现
先进先出（FIFO）算法：总是淘汰最先进入内存的页面，即在内存驻留最久的页面将被淘汰
最近最久未使用（LRU）算法：选择最近一段时间内最久没有被访问的页面，然后将其淘汰
最少使用（LFU）算法：选择最少使用的页面予以淘汰
十、在一个请求分页系统中，采用FIFO页面置换算法时，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数M分别为3和4时，试计算在访问过程中所发生的缺页次数和缺页率，并比较所得结果。
M为3时，总共发生了10次缺页，缺页率为83.4%
M为4时，总共发生了7次缺页，缺页率为58.4%
十一、试说明改进型Clock置换算法的基本原理。
在简单的Clock置换算法的基础上再添加一个“置换代价”因素，描述该因素的字段是修改位，也就是优先选择最近即未被访问、又未被修改的页面作为淘汰页面。整个算法的过程就是，在页表中检查表项，如果有未访问的页面，则将其选择为被淘汰页面，如果该页面已被防伪，则在检查下一项的同时将检查到的表项的访问位置0。这样子一轮下来，整个页表的访问位都会被重置为0，第二次寻找修改位为0的页面即可。如果仍然选不出淘汰页面，则在第三次寻找时选修改位为1的页面，此时一定可以选出淘汰页面
十二、在请求分页系统中，产生“抖动”的原因是什么？
同时在系统中运行的进程太多，分配给每一个进程的页面太少，致使每个进程在运行时频繁地发生缺页，系统频繁地进行页面换入换出，而因为磁盘I/O较慢的原因，每个进程把大量时间用于页面的置换，几乎不能有效地工作，导致处理机的利用率极具下降并趋近于0
十三、何谓工作集？它是基于什么原理确定的？
工作集是只某段时间间隔中，进程实际所要访问的页面的集合。它是基于程序访问页面的序列和窗口大小确定的
十四、当前可以利用哪几种方法来防止“抖动”？
采用局部置换策略，把工作集算法融入到处理机调度中，利用“L=S”准则调节缺页率，选择暂停的进程