第 5章 存储器理本章主要讲述内存的各种管理方式,其体包括分区式、页式、段式、段页式存储管理方式,以及虚拟存储器的基本概念和请求调页、请求调段存储管理方式等内容。
5.1基本内容
5.1.1存储器管理的基本概念操作系统中的存储管理主要是指内存管理
1.存储管理研究的课题
（1）存储分配,研究存储共享和各种分配算法；
（2）地址再定位,研究各种地址变换机构及动态和静态再定位；
（3）存储保护,研究存储保护方法；
（4）存储扩充,研究虚拟存储器问题及各种调度方法。
2.存储分配方式
（1）直接分配方式：程序员在编写程序或编译程序对源程序编译时采用实际存储地址。采用这种方式,必须事先划定作业的可用空间,因此这种直接指定方式的存储分配,存储空间的利用率不高,对用户使用也不方便。
（2）静态分配方式：在将作业装入内存时才确定它们在主存中的位置。采用这种分配方式,在一个作业装入时必须分配其要求的全部存储量；如果没有足够的存储空间,就不能装入该作业。此外,作业一旦进入内存后,在整个运行过程中不能在内存中移动,也不能再申请内存空间。
（3）动态分配方式：作业在存储空间中的位置也是在装入时确定的；但在其执行过程中可根据需要申请附加的存储空间。当一个作业已占用的存储区不再需要时,可以归还给系统。同时,在作业运行过程中允许它在存储空间中移动。
目前,绝大多数计算机系统都采用静态或动态存储分配方式。
3.地址再定位
（1）几种空间
①名空间：源程序中由符号名组成的空间。
②逻辑地址空间：由逻辑地址组成的空间。所谓逻辑地址是以0为基地址顺序进行编址的相对地址。
③物理地址空间：是物理地址的集合。所谓物理地址,就是存储（内存）地址。
（2）地址的再定位一个逻辑地址空间的程序装入到物理地址空间时,由于两个空间不一致,需要进行地址变换或地址映射,即地址的再定位。地址再定位有静态和动态两种方式：
①静态再定位：在程序运行之前,由再定位程序完成。其优点是易实现,不需要硬件支持；缺点是只能在连续区域分配程序的存储空间；再定位后不能移动，多个用户很难共享内存中的同一程序。
②动态再定位：在程序执行期间,每次访问存储器之前进行；由硬件再定位寄存器存放程序的起始地址。优点是程序占用的内存空间动态可变,充分利用主存,若干用户可共享同一程序。但需要硬件支持且管理软件算法较复杂。
4.虚拟存储器的概念
（1)局部性原理程序局部性原理是指程序在执行时将呈现出局部性规律,即在一较短的时间内,程序的执行仅局限于某个部分,相应地，它所访问的存储空间也仅局限于某个区域。
①时间局部性：如果程序中的某条指令一旦执行,则不久以后该指令可能再次执行；如果某个数据被访问,则不久以后该数据可能被再次访问。产生时间局部性的典型原因是由于程序中存在着大量的循环操作。
②空间局部性。一旦程序访问了某个存储单元,则不久以后,其附近的存储单元也将被访问,即程序在一段时间内所访问的地址,可能集中在一定的范围内,其典型情况便是程序的顺序执行。
（2)虚拟存储器：虚拟存储器是利用操作系统产生的一个其容量比主存大得多的存储器,实际上是一个地址空间。
基于局部性原理,应用程序在运行之前并不必全部装入内存,仅须将当前要运行到的那部分程序和数据装入内存便可启动程序的运行,其余部分仍驻留在外存上；当要执行的指令或访问的数据不在内存时,再由OS自动通过请求调入功能将它们调入内存,以使程序能继续执行:如果此时内存己满,则还需通过置换功能,将内存中暂时不用的程序或数据调至盘上,腾出足够的内存空间后,再将要访问的程序或数据调入内存,使程序继续执行。
这样,便可使一个大的用户程序能在较小的内存空间中运行:也可在内存中同时装入更多的进程使它们并发执行。从用户的角度看,该系统具有的内存容量比实际的内存容量大得多,我们将这种具有请求调入功能和置换功能、能从逻辑上对内存容量加以扩充的存储器系统称为虚拟存储器。
（3）实现虚拟存储器的物质基础：
①一定容量的主存；
②大容量的辅存
③ 动态地址变换机构。
虚存的容量受字长、速度(传送〉、使用频率的限制,其最大容量由计算机系统的地址机构确定。实现虚存的方案有：①分页式虚存(是请求分页)；②分段式虚存；③〉段页式虚存。
（4）虚拟存储器的主要特征
① 多次性：与常规存储管理的"一次性"相反,虚拟存储器将一个作业分成多次调入内存。多次性是虚拟存储器最重要的特征。
②对换性。与常规存储管理的"驻留性"相反,在作业运行期间,虚拟存储器允许将那些暂不使用的程序或数据从内存调至对换区,待以后需要时再调入内存,从而能有效地提高内存利用率。
③虚拟性。虚拟存储器对内存的扩充是逻辑上的,用户所看到的大容量只是一种感觉,并不实际存在,因此是虚的。虚拟性是实现虚拟存储器的目标。
5.1.2早期的存储管理
1.单一连续分配
(1)每次只有一个用户作业使用,它占用了全部资源(包括主存)。
(2)系统中的存储器被分成三个连续区域：①操作系统使用区域；②作业〈用户程序〉区域；③未用区域。
早期的存储管理有以下特点:
①优点：简单,易于实现。
②缺点:仅适用于单道程序,处理机和主存不能充分利用。
2.分区分配为满足多道程序设计和多用户系统的开发,把内存按不同的方法分区。
（1）固定式分区在系统生成时,将内存划分为若干个分区,大小可以不等,但事先固定,以后也不能改变。
特点：可以使多个作业共享内存,但内存利用不充分,浪费很大,有“内零头”。
（2）可变式分区即动态分区可变式分区需了解的几个概念：
①空白区：一块连续的未使用的内存区。
②空白区表：用于对空白区管理的目录表。
③碎片:一块小的不能使用的空白区。
④可变式分区有两种不同选择:其一是分区数目固定,其各自的大小可变；其二是允许分区的数目和大小都是可变的。
分配和释放分区的算法：
①最佳适应算法：空白区表是按空白区的容量,从小到大顺序排列。这种算法优点是查找速度较快,准确合理。
②最差适应算法:空白区表是按空白区的容量,从大到小顺序排列。这种算法优点是一次比较就可判定能否满足要求F分配后剩余区仍可使用。
③最先适应算法：空白区表是按空白区的起始地址,由小到大顺序排列。这种算法优点是在释放内存时,若有相邻空白区,可合并成一个较大区。在此算法中应尽量使用低地址部分,高地址部分留有较多、较大空白区。
（3）可再定位分区分配可再定位分区分配即浮动分区分配,是解决碎片问题的简单而有效的方法。其基本思想是:移动所有被分配的分区,使之成为一个连续区域,而留下一个较大的空白区。移动(靠拢〉时机应选择在以下时间:①某作业完成时；②某作业请求分区时；
可再定位分区分配的特点:优点是碎片可集中使用,内存利用率高；缺点是需要硬件支持,移动会降低速度。
（4）分区的保护措施
①界地址寄存器:下界寄存器存放作业分区的起始地址,上界寄存器存放下一分区的起始地址。每次寻址和访问时,先与这两个寄存器的内容进行比较,以实现对分区的保护。
②基址寄存器和限长寄存器:基址寄存器存放作业分区的起始地址,限长寄存器存放作业的最大偏移量〈长度〉。在作业运行过程中,在访问存储器时所计算出的存储地址如果超过限长,则发越界中断信号。
5.1.3分页存储管理
1.有关分页存储管理的几个概念
(1)页面：把逻辑地址空间划分为一些相等的片,这些相等的片称为页面(或页〉。页的大小通常在512B到4KB范围内,通常是2的幂。
(2)块：把物理地址空间划分为同页面同样大小的片,称之为块,也称存储块或页框。
(3)页表（PMT）：也称页面变换表。每个作业一张,该作业有多少页面就有多少表目,表目内记录对应的存储块号。它包含两部分,前一部分为页号P,后一部分为页内位移W。上述地址结构中,两部分构成的地址长度为16位。其中0-9位为页内地址,即每页大小为1K;10-15位为页号,地址空间最多允许有64页。
页号P
页内位移量W
15 10 9 0
2.地址变换机构
(1)动态地址变换机构(DAT)用页面变换地址寄存器指出页表始址。
(2)高速页面变换寄存器用硬件的高速寄存器来实现作业地址空间到物理地址空间的变换。
(3)联想存储器,也称快表,利用一组高速寄存器,连同管理它们的硬件,构成一个容量较小的存储器,称为联想存储器。联想存储器用于存放已在运行的作业的当前最常用的页号和相应的块号,它具有并行查询能力。
3.分页存储管理的实现分页原理的主要内容是:将逻辑地址空间划分成大小相同的页面,将物理地址空间划分成与页面同样大小的块,利用页面变换表（PMT）,建立页与块的对应关系,通过PMT实现地址变换。
用户作业 页 表 内 存
0页
1页
2页
┇
N页
0
2
1
4
2
7
┇
┇
4.地址变换机构
(1)动态地址变换机构(DAT)用页面变换地址寄存器指出页表始址。
(2)高速页面变换寄存器用硬件的高速寄存器来实现作业地址空间到物理地址空间的变换。
（3）所需的表格：作业表(JT),全系统一张；存储分块表（MBT）,全系统一张；页面变换表（PMT）,每个作业一张。由操作系统对以上表格进行管理。
（3）地址变换过程当进程要访问某个逻辑地址中的数据时,分页地址变换机构自动地将逻辑地址分为页号和页内位移两部分,再以页号为索引去检索页表。在执行检索之前,先将页号与页表长度进行比较,如果页号超过了页表长度,则表示本次所访问的地址已超越进程的地址空间,系统产生地址越界中断。如果页访问合法,则由页表起始地址和页号计算出相应页表项的位置,从中得到该页的物理块号。最后,将块号与逻辑地址中的页内位移拼接在一起,就形成了访问主存的物理地址。图5.4给出了页式存储管理系统中的地址变换过程。
越届中断页表寄存器 逻辑地址
页号 块号
在图5.4中,假定页面大小为lk字节,则逻辑地址2500(=2×1024+452〉的页号为2,页内地址为452。由页表可知第2页对应的物理块号为8。将块号8与页内地址452拼接(8×1024+452=8644)得到物理地址为8644。
(4)联想存储器：从上面介绍的地址变换过程可知,若页表全部放在主存,则要存取一个数据或一条指令至少要访问两次主存,一次是访问页表,确定所存取的数据或指令的物理地址,第二次才根据该地址存取数据或指令。显然,这种方法比通常执行指令的速度慢了一倍。为了提高查表速度,可在地址变换机构中增设一个具有并行查找能力的高速缓冲存储器(又称联想存储器或快表),将页表放在这个高速缓冲存储器中。高速缓冲存储器一般是由半导体存储器实现的,其工作周期与CPU的周期大致相同,但其造价较高。为了降低成本,通常是在快表中存放正在运行作业当前访问的那些页表项,页表的其余部分仍然存放在内存中。
引入快表以后的地址变换过程为:当CPU给出逻辑地址后,地址变换机构自动将此页号与联想存储器中的所有页号进行并行比较,若其中有与此匹配的页号,则表示所要访问的页表项在联想存储器中,于是取出该页对应的块号,与页内地址拼接形成物理地址。若联想存储器中的所有页号与所查找页号不匹配,则还需再访问主存中的页表。实际上,这两者的查找是同时进行的,一旦在联想存储器中发现了要查找的页号,则立即停止内存中页表的查找。如果地址变换是通过查找内存中的页表完成的,则还应将这次所查到的页表项存入联想存储器中,若联想存储器己满,则必须按某种原则淘汰一个表项以腾出位置。
采用这种方案,只要使用8—16个表项的联想存储器,就能使从联想存储器中找到所需页号的概率达到90%左右。
5.1.4请求分页存储管理在分页的基础上增加请求调页功能和页面置换功能,便形成了能支持虚拟存储器功能的请求分页系统。
1.请求分页的基本原理请求分页系统对地址空间和内存空间的管理采用与基本分页系统相同的方式,但它只要求将作业的部分页面装入内存,便可开始运行作业,作业的其余部分被存放在盘中。
由于这种管理方案在一个作业运行之前不要求将作业的整个地址空间调入主存,因此在作业的运行过程中,必然会出现要访问的页不在主存的情况。那么如何发现和处理这种情况就是请求页式存储管理必须解决的两个基本问题。
为了解决发现所访问页面不在主存的问题,必须对页表表目进行扩充。扩充后的页表表目结构如下所示:
页号
块号
状态位
访问字段
修改位
外存地址
在请求分页系统中,当进程需要访问某条指令或某个数据时,硬件地址变换机构将根据逻辑地址中的页号去检索内存中的页表,并根据相应页表项的状态位，来判断该指令或数据所在的页是否已装入内存。若己装入内存,则可立即从页表项中得到该页的内存块号,并与页内地址拼接形成指令或数据的物理地址,同时还需修改页表项中的访问位对于写指令,则还需将修改位置成"1"。若所要访问的页还未调入内存,便产生一缺页中断,此时,上述访问缺页的作业将被中断,控制将转向缺页中断处理程序。
缺页中断处理程序用来完成页面的调入工作。若系统中仍有空闲的内存块,则只需根据页表项中的外存地址将所缺的页装入内存,然后修改页表项中的存在位和内存块号即可；否则,若系统中无空闲的内存块,则需要根据置换算法淘汰内存中的某一页,对已被修改过的页先写盘,然后再将所缺的页调入内存。
2.内存分配策略和置换策略在请求分页系统中,可采取两种内存分配策略,即固定分配和可变分配。在进行置换时,也可采取两种策略,即全局置换和局部置换。于是,可组合出以下三种适用的策略:
(1)固定分配局部置换策略。采用该策略时,为进程分配的物理块数目,在进程的整个运行期间都固定不变,若进程因调入页面而需要换出某个页面,则只能换出它自己的内存页面。由于进程是动态的,即使在运行之前为它分配了适当数目的内存块,.在采用固定分配局部置换策略时,进程在运行过程中仍然可能会因内存块太少而频繁缺页,或者因内存块太多而浪费空间。
(2)可变分配全局置换策略。采用该策略时,系统先为每个进程分配一定数目的物理块当进程发生缺页时,若系统中有雪闲的物理块,则为其分配一个物理块并装入缺页；若系统中己没有雪闲的物理块,则从内存中选择一页换出,再装入缺页,被换出的页可以是系统中任一进程的页,这样,自然又会使那个进程的物理块减少,进而使其缺页率增加。
(3)可变分配局部置换策略。在采用该策略时,为每个进程分配一定数目的物理块后；若某个进程发生缺页,则只能将自己的某个内存页换出。如果进程在运行中频繁发生缺页中断,则系统须为该进程分配若干附加的物理块,直至其缺页率减少到适当程度为止；反之,若一个进程的缺页率特别低,则可适当减少分配给它的物理块,但不应引起其缺页率的明显增加。因此,可变分配局部置换策略可获得较高的内存空间利用率,同时又能保证每个进程有较低的缺页率。
3.调页策略
（1)请求调页策略：请求调页策略是指当进程在运行中需要访问某部分程序和数据时,若发现其所在的页面不在内存,便立刻发出缺页中断,请求OS将所需页面调入内存。单纯采用请求调页策略的系统,在进程刚启动时,缺页中断会发生得比较频繁,由于程序访问的局部性,一段时间后,缺页率会降至较低。对一个被整体换出的进程重新开始执行时;也具有上述情况。
（2)预调页策略：预调页策略是指将那些预计在不久之后便会访问到的几个页面,预先调入内存。如果这些页被存放在外存的一个连续区域中,则通过预调页将它们一次调入内存将比一次调入一页要高效得多。但预测哪些页面在不久之后便会被访问到是十分困难的,其成功率只有50%。故预调页策略主要用于进程首次调入和整体换入时,由程序员或系统指出应该先调入哪些页面,这样,可使刚开始执行的进程的缺页率明显降低。
（3）抖动:从主存中刚刚移走某页面后,根据请求马上又调入该页。这种反复进行入页和出页的现象称为"抖动",也叫系统颠簸。它会浪费大量的处理机时间,应尽可能避免。产生抖动的直接原因是页面置换算法选取不当。
4.页面置换算法
(1)最佳置换算法：置换策略是从主存中移出永远不再需要的页面,若无这样的页面存在,则应选择最长时间不需要访问的页面。最佳置换算法本身不是一种实际的方法,因为页面访问的未来顺序是不知道的。但是可将其他实用方法与之比较来评价这些方法的优劣,所以最佳置换算法具有理论上的意义。
(2)先进先出算法(FIFO)：总是先淘汰那些驻留在主存时间最长的页面。
(3)最近最久未用置换算法(LRU)：当需要置换一页时,选择在最近一段时间最久未用的页予以淘汰。
(4)LRU近似算法：在存储分块表MBT(或页表PMT)中设一"引用位",当页被访问时,该位由硬件自动置为"1",而由页面管理软件周期地把所有引用位置为"0"。在时间周期T内,根据引用位的状态来判断各页面最近的使用情况。
5.性能分析
(1)本方案消除了对主存容量的限制,能使更多的作业按多道程序同时执行,提高了系统效率。但应尽量减少缺页中断次数。
(2)为了减少缺页中断次数,应从程序设计的质量、页面的大小、主存的容量以及页面置换算法等几方面来考虑。
5.评价
(1)请求分页存储管理保留了分页存储管理的全部优点,特别是它解决了消除碎片的问题。另外,它还有如下优点:提供了大容量的多个虚拟存储器；作业地址空间不再受实存容量的限制；更有效地利用主存；有利于运行多道程序；提高了系统效率,方便了用户,特别是大作业用户。
(2)请求分页存储管理的缺点是：要求有相应的硬件支持,从而增加了成本。如动态地址变换机构、快表、缺页中断的产生等都要求有相应的硬件支持。缺页中断增加了处理机时间的开销,如页表的建立与管理、缺页中断处理等；页面淘汰算法如选择不当,有可能产生抖动现象，为防止抖动,会增加系统的复杂性；虽然消除了碎片,但每个进程的最后一页内总有一部分空间得不到利用。另外,页式存储管理系统中作业的地址空间仍受主存实际容量的限制。
5.1.5分段存储管理
1.分段原理一个用户作业的程序按其逻辑结构,可由用户划分为若干段。这些段中的每一段在逻辑上都是完整的,每一段都是一组逻辑信息,都有自己的名字,且都有一段连续的地址空间。可以用类似于分页管理用过的地址变换机构,实现分段管理的地址变换,只是采用的是段变换表SMT。地址变换是在作业执行过程中由硬件自动完成的。
2.段变换表SMT
分段存储管理系统中,作业地址空间的每一单元采用二维地址(S,W),其中S为段号,W为段内地址或位移量。
段式存储管理系统也可和请求页式存储管理系统一样,为用户提供一个比主存可用空间大得多的虚拟存储器。同样,虚拟存储器的实际容量由计算机的地址结构确定。
在段式虚拟存储系统中,一个作业各分段的副本都保存在辅存中,当其运行时,首先把当前需要的一段或几段调入主存,其他段在需要时再调入。为此,应对段表表目进行扩充,扩充后的内容如下,
段号
段长
主存始址
访问位
改变位
增补位
状态位
外存地址
段号、段长和内存始址三个信息是进行地址变换所必须的,当段在内存时,地址变换过程与段式存储管理相同:当段不在内存时,先将该段调入内存再进行地址变换。新增加的状态位用于标识此段是否在主存中,访问字段记录本段在一段时间内被访问的次数或最近已有多长时间未被访问,修改位表示该段在调入内存后是否被修改过,外存地址指出该段在外存上的地址。为了进行存储保护,还可以增加一个存取控制字段。
当被访问的段不在主存中时,产生一个缺段中断信号。操作系统处理该中断后,在主存中查找是否有足够大的分区存放该段。如没有这样的分区,则检查未分配分区的总和,确定是否需要对分区进行拼接,或者调出一个或几个分段后再装入所需要的分段。
3.段的共享与保护在段式系统中,分段的共享是通过两个作业的段表中相应表目都指向被共享过程的同一个物理副本来实现的。
与页式管理类似,段式管理的保护主要有两种。一种是地址越界保护法,另一种是存取控制保护法。
4.段式管理的特点
（1)分段存储管理的优点是：消除了碎片；提供了大容量的虚存；可动态增加段长；便于动态装入和连接；可共享一个程序;便于实现存储保护。
(2)分段存储管理的缺点是：地址变换和靠拢需CPU时间；表格需占存储空间；在辅存上管理可变长度的段较困难,段的最大长度受实存限制;也会出现系统抖动现象。
5、分页和分段存储管理的比较分页系统、分段系统有许多相似之处,比如:都采用离散分配方式来提高内存利用率,都要通过地址变换机构来实现地址变换；但在概念上两者是完全不同的,它们的主要区别表现在以下三个方面:
①分页是一个单一的线性地址空间,分段作业地址空间是二维的。
②"页"是信息的物理单位,大小固定，分页活动用户看不见,分页的目的是为了提高内存的利用率。而"段"是信息的逻辑单位,其长度不定，分段是用户可见的活动，分段的目的是为了能更好地满足用户的需要。。
③分页管理实现单段式虚拟存储系统,而分段存储管理实现多段式虚拟存储系统。
4.1.6段页式存储管理为了既能像分页系统那样有效地利用内存；又能像分段系统那样满足用户多方面的需要,操作系统中又引入了段页式存储管理方式。
1.基本思想
(1)用分段方法来分配和管理虚拟存储器。
(2)用分页方法来分配和管理实存储器。
段页式存储管理方式是分页和分段管理的结合,它先将地址空间中的用户程序分成若干个段,再将每个段分成若干个页。而内存空间则仍采用页式管理主式,即将内存分成与页同样大小的块,并以块为单位来进行内存的分配。
2.实现原理
(1)在段页存储管理中,地址空间还是二维的,每个逻辑地址包括段号和段内地址两部分,段内地址又将被地址变换机构根据页面大小自动分成段内页号和页内地址。因此，处理机给出的有效地址被划分为三部分:段号、页号和页内地址，即（S,P,W）。
（2）程序的分段可由程序员或编译程序按信息的逻辑结构来划分,而分页与程序员无关,它是由操作系统自动完成的。为了实现地址变换,系统必须为每个进程建立一张段表,并为每个分段建立一张页表,段表项给出了每个分段所对应的页表的内存始址和长度,页表项则给出了页所对应的内存块号二在进行地址变换时,首先根据段表寄存器中的段表始址和逻辑地址中的段号找到对应的段表项,从中获得该段的页表始址:然后再利用页表始址和逻辑地址中的段内页号来获得对应的页表项,从中获得该页的内存块号::由内存块号与页内地址拼接形成物理地址。
（3）由于段表和页表都存放在内存中,每存取一条指令或一个数据都需访问三次内存,故可在地址变换机构中增设快表,用来存放当前被频繁访问的页面所对应的段号、段内页号和物理块号等信息,以减少访问内存的次数,提高指令执行的速度。
从逻辑地址到物理地址的变换过程需要三次访问主存,一次是访问段表,一次是访问页表,再一次是访问主存物理地址。
3.评价
（1）段页式存储管理的优点是：保留了分段和请求分页存储管理的全部优点。其主要优点是提供了大量的虚存空间,能有效地利用主存,为组织多道程序运行提供了方便。
(2)段页式存储管理的缺点是：增加了硬件成本、系统的复杂性和管理上的开销,页面使用不充分；各种表格占用主存空间；有系统抖动的危险。
4.2重点难点学习提示本章的目的是了解各种存储器管理的方式和它们的实现方法,为此应对以下几个重点、难点问题作认真的学习,并切实掌握其中的内容。
1.重定位的基本概念重定位的实质是地址变换,它将作业地址空间中的逻辑地址转换为主存空间中的物理地址,从而保证作业能够正常执行。对下述两个方面的内容要有较好的理解:
(1)为什么要引入重定位,由重定位装入程序在装入作业时一次性完成的静态重定位适用于何种场合,它有何优缺点。
(2)动态重定位是为了解决什么问题而引入的,在连续分配方式、分页系统和分段系统中,分别是如何实现动态重定位的。
2.动态分区分配方式动态分区分配方式是一种曾经广为流行的内存分配方式,至今仍在内存分配中占有一席之地。应了解下述几个问题:
(1)如何提高内存利用率。动态分区分配方式是根据进程的实际需要,动态地为进程分配内存,造成动态分区分配方式内存空间浪费的主要原因是什么,可通过什么办法加以解决。
(2)分配算法。动态分区分配方式可采用空闲分区表或空闲分区链来描述分区的情况,并可采用首次适应、最佳适应等算法来进行内存的分配和回收,读者应了解在采用不同的分配算法时,系统是如何组织空闲分区表或空闲分区链的,它们又是如何进行分区的分配和回收的。
(3)如何进行分区的保护。该方式可利用界限寄存器或保护键来进行分区的保护,应了解它们分别是如何进行越界检查的；在检查到越界情况时,将由谁负责进行具体的处理。
3.分页和分段存储管理方式分页和分段存储管理方式不仅能有效地提高内存雪间的使用效率,而且是实现虚拟存储器的基础。应对下面几个方面的内容有较深刻的理解和掌握：
(1)分页存储管理方式。应了解是在什么推动力的作用下,使内存管理由动态分区分配方式发展为分页存储管理方式;分页系统是如何将地址空间中的作业划分为若干个页,它又是如何进行内存分配的。
(2)分页系统的地址转换。应掌握分页系统逻辑地址的结构,为了进行逻辑地址到物理地址的转换,分页系统必须为每个作业配置什么样的数据结构并提供哪些硬件支持,为什么引入快表可加快分页系统存取指令和数据的速度。
(3)分段存储管理方式。应了解由分页发展为分段,并进一步发展为段页式存储管理方式的主要推动力是什么,分段和段页式系统是如何管理作业的地址空间和内存空间的,它们的地址变换是如何完成的,并应注意对分段系统和分页系统加以比较。
(4)信息的共享和保护。分页系统和分段系统都可以实现信息的共享,并可通过越界检查和存取权限对信息进行保护。应了解为什么分段系统比分页系统更容易实现信息的共享和保护:对代码页(段)的共享有什么特别的要求,原因是什么。
4.虚拟存储器的基本概念虚拟存储管理技术己被广泛地应用于现代操作系统中,它的主要功能是从逻辑上扩充内存的容量。由于它是存储器管理中的重点部分,应对下述几个问题有较清楚和深入的理解:
(1)为什么要引入虚拟存储器。引入虚拟存储器主要是为了解决内存空间不足的问题,应了解虚拟存储器是如何扩充内存容量的,为什么一次性和驻留性并非是程序运行所必需的条件,或者说,为什么只需将部分程序和数据装入内存,便能完成整个程序的。
(2)虚拟存储器具有哪些特征。虚拟存储器具有多次性、对换性和虚拟性的特征,必须了解每种特征的具体含义,以及它们相互之间存在着什么样的关系,它们与离散分配之间又存在着什么样的关系。
(3)实现虚拟存储器的关键技术是什么。实现虚拟存储器的的关键是请求调页(段)技术和页(段)置换技术,应清楚地了解这些技术的实现需要得到哪些硬件支持和软件支持。
5.请求分页系统的基本原理请求分页系统是目前最常用的一种实现虚拟存储器的方式,它只需将作业当前要用到的部分页面装入内存,便可启动作业的运行。应对下述内容有较深刻的理解和掌握,
(1)页表机制。为实现虚拟存储器,必须扩充页表工页的内容,应了解除了内存块号和存取权限字段以外,页表中还必须增加哪些字段,为什么要增加这些字段。
(2)地址变换过程。请求分页系统的地址变换也必须通过地址变换机构进行,应了解请求分页系统的地址变换机构,是在基本分页系统的地址变换机构的基础上增加了哪些功能而形成的。
(3)页面置换算法。页面置换算法即选择换出页面的算法,它直接影响到系统的性能。应了解一些常用的页面置换算法,并进一步了解为什么LRU算法具有比较好的性能,它的主要缺点是什么,可用什么方法实现LRU近似算法。
5.3典型问题分析和解答
1.存储器管理的基本任务是为多道程序的并发执行提供良好的存储器环境。"良好的存储器环境"应包含哪几个方面?
答:存储器管理的基本任务是为多道程序的并发运行提供良好的存储器环境。它包括以下内容:
(1)能让每道程序"各得其所",并在不受干扰的环境中运行号还可以使用户从存储空间的分配、保护等繁琐事务中解脱出来。
(2)向用户提供更大的存储空间,使更多的作业能同时投入运行z或使更大的作业能在与较小的内存空间中运行。
(3)为用户对信息的访问、保护、共享以及动态链接等方面提供方便。
(4)能使存储器有较高的利用率。
2.何谓虚拟存储器?举一例说明操作系统是如何实现虚拟内存的。
答：在操作系统中,通过一些硬件和软件的措施为用户提供了一个其容量比实际主存大得多的存储器,称为虚拟存储器。
操作系统要实现虚拟内存,必须把主存和辅存统一管理起来,即大作业程序在执行时,有一部分地址空间在主存,另一部分在辅存,当访问的信息不在主存时,由操作系统将其调入主存并实现自动覆盖功能,使用户在编写程序时不再受主存容量的限制。
例如在请求分页存储管理系统中,用户作业的所有页面并不一定都在实存,在作业运行过程中再请求调入所用的虚页。为了实现从逻辑地址空间到物理地址空间的变换,在硬件上必须提供一套地址变换机构,动态地址变换机构自动地将所有的逻辑地址划分为页号和页内地址两部分,并利用页表将页号代之以块号,把块号和页内地址拼接就得到了内存的物理地址,从而实现了虚拟存储器。
3.什么叫重定位? 采用内存分区管理时,如何实现程序运行时的动态重定位?
答：所谓地址重定位,就是当一个程序装入到与其地址空间不一致的存储空间而进行的地址变换过程,即将地址空间给出的逻辑地址映射到内存的物理地址上。地址重定位有静态重定位和动态重定位两种方式。
采用内存分区管理时,在硬件上设置一个"重定位寄存器"可以实现程序运行时的动态重定位。这种情况下地址重定位是在程序执行期间由地址变换机构动态实现的,主要的计算依据是:
物理地址=逻辑地址+重定位寄存器的内容
4.某系统采用动态分区分配方式管理内存,内存空间为640K,高端40K用来存放操作系统。在内存分配时,系统优先使用空闲区低端的空间。对下列的请求序列:作业1申请130K、作业2申请6OK、作业3申请100K、作业2释放6OK、作业4申请200K、作业3释放l00k、作业1释放130K、作业5申请140K、作业6申请6OK、作业7申请5OK、作业6释放6OK,请分别画图表示出使用首次适应算法和最佳适应算法进行内存分配和回收后内存的实际使用情况。
分析：首次适应算法将空闲区按起始地址递增的次序拉链,而最佳适应算法则将空闲区按分区大小递增的次序拉链。在分配时飞它们都是从链首开始顺序查找,直至找到一个足够大的空闲分区为止,然后按作业大小从该分区中划出一块内存空间分配给请求者,余下的分区(如果有的话)仍按上述原则留在空闲分区链中;而在释放时,则需分别按地址递增或大小递增的次序将空闲分区插入空闲分区链,并都需要进行空闲分区的合并。
答：使用首次适应算法和最佳适应算法进行上述内存的分配和回收后，内存的实际使用情况如下图所示。
5.在请求分页存储管理系统中,试问:
（1）局部与全局页面淘汰算法有何区别? 为什么在多道系统中常用局部页面淘汰算法?
（2）试设计一个LRU淘汰算法的近似算法(指出所需的硬件支持、数据结构及软件处理流程)。
答：（1）局部页面置换只在当前进程分配的页面中选择一个被置换的页面:全局页面置换从整个存储器用户区的所有页面中选择一个被置换的页面。
在多道程序系统中,采用局部页面置换策略进行页面置换,即使某个进程出现了抖动现象,不致引起其他进程也产生抖动,-可以将抖动局限在较小的范围内。
（2）可以在MBT表中增设一个"引用位",当MBT表中的页被访问时"引用位"置1,在MBT表中再增设一个指针域,用于记录进入内存的页面顺序,另设一个替换指针指向最近刚刚进入内存的页面。可以根据引用位的状态来判别各页面最近的使用情况,当需要置换一页时,选择其引用位为0的页淘汰。该算法的程序流程图如图2.6所示:
N
Y
6.某系统采用页式存储管理策略,拥有逻辑空间32页,每页2K,拥有物理空间1M。
(1)写出逻辑地址的格式。
(2)若不考虑访问权限等,进程的页表有多少项?每项至少有多少位?
(3)如果物理空间减少一半,页表结构应相应作怎样的改变?
答:(1)该系统拥有逻辑空间32页,故逻辑地址中页号必须用5位来描述;而每页为2K,因此,页内地址必须用11位来描述,这样可得到它的逻辑地址格式如下:
15 11 10 0
页 号
页 内 地 址
(2)每个进程最多有32个页面,因此,进程的页表项最多为32项；若不考虑访问权限等,则页表项中只需给出页所对应的物理块块号,1M的物理空间可分成29个内存块,故每个页表项至少有9位。
（3）如果物理空间减少一半,则页表中页表项数仍不变,但每项的长度可减少1位。
7.假定某页式管理系统,主存为64KB,分成16块,块号为0,1,2,3,4,…,15。设某作业有4页,其页号为0,1,2,3,被分别装入主存的2,4,1,6块。试问:
(1)该作业的总长度是多少字节?(按十进制)
(2)写出该作业每一页在主存中的起始地址。
(3)若给出逻辑地址[0,100]、[1,50]、[2,0]、[3,60],请计算出相应的内存地址。
答:(1)每块的长度=64KB/16=4KB
因为块的大小与页面的大小相等,所以每页为4KB。因此,作业的总长度为4KB×4=16KB。
(2)因为页号为0,1,2,3的页分别被装入主存2,4,1,6块中,即PMT为:
页号
块号
0
2
1
4
2
1
3
6
所以该作业的：
第0页在主存中的起始地址为4K×2=8K
第1页在主存中的起始地址为4K×4=16K
第2页在主存中的起始地址为4K×1=4K
第3页在主存中的起始地址为4K×6=24K题
（3）逻辑地址[0,100]的内存地址为4K×2+100=8192+100=8292
逻辑地址[1,50]的内存地址为4K×4+50=16384+50=16434
逻辑地址[2,0]的内存地址为4K×1+0=4096
逻辑地址[3,60]的内存地址为4K×6+60=24K+60=24576+60=24636
8.对于下表所示的段表,请将逻辑地址(0,137),(1,4000),(2,3600),(5,230)转换成物理地址。
段号
内存地址
段 长
0
50K
10K
1
60K
3K
2
70K
5K
3
120K
8K
4
150K
4K
分析：在分段系统中进行地址转换时,地址变换机构首先将逻辑地址中的段号与段表长度作比较,如果段号超长,则产生越界中断;否则使以段号为索引去检索段表,从中得到段在内存的始址和段长;然后再将逻辑地址中的段内地址与段长作比较,若不越界,则由段的始址与段内地址相加,形成物理地址。
答:(1)段号0小于段表长5,故段号合法:由段表的第0项可获得段的内存始址为5OK,段长为1OK由于段内地址137,小于段长1OK,故段内地址也是合法的,因此可得出对应的物理地址为5OK+137=51337。
(2)段号1小于段表长,故段号合法:由段表的第1项可获得段的内存始址为60K,段长为3K;经检查,段内地址4000超过段长3K,因此产生越界中断。
(3)段号2小于段表长,故段号合法:由段表的第2项可获得段的内存始址为7OK,段长为5K;故段内地址3600也合法。因此,可得出对应的物理地址为7OK+3600=75280。
(4)段号5等于段表长,故段号不合法,产生越界中断。
9.己知页面走向为1、2、1、3、1、2、4、2、1、3、4,且开始执行时主存中没有页面。若只给该作业分配2个物理块,当采用FIFO页面淘汰算法时缺页率为多少?假定现有一种淘汰算法,该算法淘汰页面的策略为当需要淘汰页面时,就把刚使用过的页面作为淘汰对象,试问就相同的页面走向,其缺页率又为多少?
分析：在进行内存访问时,若所访问的页已在主存,则称此次访问成功;若所访问的页不在主存,则称此次访问失败,并产生缺页中断.若程序P在运行过程中访问页面的总次数为s,其中产生缺页中断的访问次数为f,则其缺页率为:f/s.
解:根据所给页面走向,采用FIFO淘汰算法的页面置换情况如下:
页面走向 1 2 1 3 1 2 4 2 1 3 4
物理块1 1 1 3 3 2 2 1 1 4
物理块2 2 2 1 1 4 4 3 3
缺页 缺 缺 缺 缺 缺 缺 缺 缺 缺
从上述页面置换图可以看出:页面引用次数为11次,缺页次数为9次,所以缺页率为9/11。
若采用后一种页面淘汰策略,其页面置换情况如下：
页面走向 1 2 1 3 1 2 4 2 1 3 4
物理块1 1 1 3 1 1 1 3 4
物理块2 2 2 2 4 2 2 2
缺页 缺 缺 缺 缺 缺 缺 缺 缺
从上述页面置换图可以看出：引用次数为11次,缺页次数为8次,所以缺页率为8/11。
10.考虑一个请求调页系统,它采用全局置换策略和平均分配内存块的算法(即若有m个内存块和n个进程,则每个进程分得m/n个内存块)。如果在该系统中测得如下的CPU和对换盘利用率,请问能否用增加多道程序的度数来增加CPU的利用率?为什么?
(1)CPU的利用率为13%,盘利用率为97%:
(2)CPU的利用率为87%,盘利用率为3%:
(3)CPU的利用率为13%,盘利用率为3%。
答:(1)这种情况表示系统在进行频繁的置换,以致绝大部分时间被花在页面置换上,此时,增加多道程序的度数会进一步增加缺页率,使系统性能进一步恶化,所以,不能用增加多道程序的度数来增加CPU的利用率。
(2)在这种情况下,CPU的利用率已相当高,但对换盘的利用率却相当低,这表示运行进程的缺页率很低,可以适当增加多道程序的度数来增加CPU的利用率。
(3)在这种情况下,CPU的利用率相当低,而且对换盘的利用率也非常低,表示内存中可运行的程序数不足,此时,应该增加多道程序的度数来增加CPU的利用率。
11.假如一个程序的段表如下所示,其中存在位为1表示段在内存,存取控制字段中W表示可写,R表示可读,E表示可执行。对下面的指令,在执行时会产生什么样的结果?
段号
存在位
内存始址
段长
存取控制
其他信息
0
0
500
100
W
1
1
1000
30
R
2
1
3000
200
E
3
1
8000
80
R
4
0
5000
40
R
(1)STORE R1,[0,70]
(2)STORE R1,[1,20]
(3)LOAD R1,[3,20]
(4)LOAD R1,[3,100]
(5)JMP [2,100]
分析：在执行指令的过程中,如果指令中包含有地址部分,则先必须进行逻辑地址到物理地址的转换。在地址转换过程中还要进行越界检查和存取控制权限的检查,只有在地址不越界、访问方式也合法,并形成物理地址后,才能去完成指令规定的操作。
答:(1)指令STORE R1,[0,70]。从段表的第0项可读出第0段的存在位为0,表示相应段未装入内存,因此地址变换机构将产生一缺段中断,以请求OS将其调入内存。
（2)指令STORE R1,[1，20]。从段表的第1项可以看出,虽然指令中的逻辑地址合法,段也已在内存,但本指令对内存的访问方式(写)与存取控制字段(只读)不符,故硬件将产生保护性中断信号。
(3)指令LOAD R1,[3,20]。从段表的的第3项可读出第3段的存在位为1,内存始址为8000,段长为80,存取控制为R,因此,逻辑地址合法,访问方式也合法,形成物理地址8020后,指令将把该单元的内容读到寄存器R1中。
(4)指令LOAD R1,[3,100]。从段表的的第3项可读出第3段的存在位为1,内存始址为8000,段长为80,存取控制为R,因此,指令的逻辑地址中段内地址超过了段伏,地址变换机构将产生越界中断信号。
(5)指令JMP[2,100]。从段表的第2项可读出第2段的存在位为1,内存始址为3000,段长为200,访问权限为E,因此逻辑地址与访问方式都合法,形成物理地址3100,指令执行后,将跳转到内存单元3100处继续执行。
5.3自测题
5.3.1基本题一．判断题(正确的在括号中记√,错误的记×)
1.为了减少内部碎片,页应偏小为好。 ( )
2.为了减少缺页中断率,页应该小一些。 ( )
3.为提高对换空间的利用率,一般对其使用离散的分配方式。 ( )
4.用户程序中出错处理部分不必常驻内存。 ( )
5.使用预分页的原因是每个进程在最初运行时需要一定数量的页面。 ( )
6.可变分区法可以比较有效地消除外部碎片,但不能消除内部碎片。 （ ）
7.分页存储管理方案易于实现用户使用内存空间的动态扩充。 ( )
8.LRU页面调度算法总是选择在主存驻留时间最长的页面被淘汰。 ( )
9.最佳适应算法比首次适应算法具有更好的内存利用率。 ( )
10.请求分段存储管理中,分段的尺寸要受主存空间的限制。 ( )
二．单项选择题，在每小题的四个备选答案中选出一个正确答案，并将其代码写在题干后面的括号内。不选、错选或多选者该题无分。
1.在可变式分区管理中,最佳适应算法是将空白区在空白区表中按______次序排列。
A.地址递增 B.地址递减 C.容量递增 D.容量递减
2.动态重定位技术依赖于_______.
A.重定位装入程序 B.重定位寄存器 C.地址机构 D.目标程序
3.请求分页存储管理方案的主要特点是__________。
A.不要求将作业装入内存 B.不要求将作业全部装入内存
C.不要求使用联想存储器 D.不要求缺页中断的处理
4.在存储管理方案中,___________可与覆盖技术配合。
A.页式管理 B.段式管理 C.段页式管理 D.可变分区管理
5.一个计算机系统虚存的最大容量是由__________决定的。
A.主存的容量 B.辅存的容量
C.主存容量+辅存容量 D.计算机的地址机构
6.在存储管理中,采用覆盖与交换技术的目的是_________。
A.节省主存空间 B.物理上扩充主存容量 C.提高CPU效率 D.实现主存共享
7.在可变式分区分配方案中,只需要进行一次比较就可以判定是否满足作业对主存空间要求的是______。
A.最先适应算法 B.最佳适应算法 C.最差适应算法 D.固定式分区方法
8.在虚拟存储系统中,若进程在内存中占3块(开始时为空〉,采用先进先出页面淘汰算法,当执行访问页号序列为1、2、3、4、1、2、5、1、2、3、4、5、6时,将产生次缺页中断。
A.7 B.8 C.9 D.10
9.下面对计算机存储器体系中的各个部分按速度从快到慢排列,其中正确的是______。
A.寄存器 cache 主存储器 后援存储器 磁盘设备 磁带设备
B.cache 寄存器 后援存储器 主存储器 磁盘设备 磁带设备
C.主存储器 cache 寄存器 后援存储器 磁盘设备 磁带设备
D.磁盘设备 主存储器 寄存器 cache 后援存储器 磁带设备
10.很好地解决了"零头"问题的存储管理方法是_______。
A.页式存储管理 B.段式存储管理 c.多重分区管理 D.可变式分区管理
11,有利于程序动态链接的内存管理方法是_______。
A.分段存储管理 B.分页存储管理 C.可变区分割分配 D.固定区分割分配
12.系统"抖动"现象的发生是由________引起的。
A.置换算法选择不当 B.交换的信息量过大 c.内存容量不足 D.请求页式管理方案
13.静态重定位是在作业的装入过程中进行的,动态重定位是在作业_________中进行的。
A.编译过程 B.装入过程 C.修改过程 D.执行过程
14.在可变式分区存储管理中的拼接技术可以________。
A.集中空闲区 B.增加主存容量 C.缩短访问周期 D.加速地址转换
15.在请求调页系统中,若逻辑地址中的页号超过页表控制寄存器中的页表长度,则会引起越界中断；否则,若所需的页不在内存中,则会引起_____________。
A.输入/输出中断 B.时钟中断 C.越界中断 D.缺页中断。
16.分区管理中采用"最佳适应"分配算法时,宜把空闲区按_____次序登记在空闲区表中。
A.长度递增 B.长度递减 C.地址递增 D.地址递减
17.虚拟存储器管理系统的基础是程序的局部性理论。此理论的基本含义是___________。
A.程序执行时对主存的访问是不均匀的 B.数据的局部性
C.变量的连续访问 D.空间的局部性
18.实现虚拟存储器的目的是________。
A.实现存储保护 B.实现程序浮动 C.扩充辅存容量 D.扩充主存容量
19.下述存储管理方式中,会产生内部碎片的是___________。
A.页式和段式 B.页式和段页式 C.动态分区和段式 D.动态分区和段页式
20.在固定分区分配中,每个分区的大小是__________。
A.相同 B.随作业长度变化
C.可以不同但预先固定 D.可以不同但根据作业长度固定
21.虚拟存储器最基本的特征是多次性，该特征主要是基于局部性原理，实现虚拟存储器最关键的技术是___________。
A.内存分配 B.置换算法 C.请求调页(段) D.对换空间管理。
22.作业在执行中发生了缺页中断,经操作系统处理后,应让其执行_____指令。
A.被中断的前一条 B.被中断的 C被中断的后一条 D.启动时的第一条
23.把作业地址空间中使用的逻辑地址变成内存中物理地址的过程称为______。
A.重定位 B.物理化 c.逻辑化 D.加载
24.在分页系统环境下,程序员编制的程序,其地址空间是连续的,分页是由________完成的。
A.程序员 B.编译地址 C.用户 D.系统
25.在请求分页存储管理中,若采用FIFO页面淘汰算法,则当分配的页面数增加时,缺页中断的次数_______。
A.减少 B.增加 C.无影响 D.可能增加也可能减少
26.虚拟存储管理系统的基础是程序的_______理论。
A.局部性 B.全局性 C.动态性 D.虚拟性
27.下述_________页面淘汰算法会产生Belady现象。
A.先进先出 B.最近最少使用 C.最不经常使用 D.最佳
28.如果一个程序为多个进程所共享,那么该程序的代码在执行的过程中不能被修改,即程序应该是_________。
A.可执行码 B.可重入码 C.可改变码 D.可再现码
29.下面关于请求分段存储管理的叙述中,正确的是_______。
A.分段的尺寸受内存空间的限制,且作业总的尺寸也受内存空间的限制。
B.分段的尺寸受内存空间的限制,但作业总的尺寸不受内存空间的限制。
C.分段的尺寸不受内存空间的限制,且作业总的尺寸不受内存空间的限制。
D.分段的尺寸不受内存空间的限制,但作业总的尺寸受内存空间的限制。
30．从下列关于非虚拟存储器的论述中,正确的是_________。
A.要求作业在运行前,必须全部装入内存,且在运行过程中也必须一直驻留内存。
B.要求作业在运行前,不必全部装入内存,且在运行过程中不必一直驻留内存。
C.要求作业在运行前,不必全部装入内存,但在运行过程中必须一直驻留内存。
D.要求作业在运行前,必须全部装入内存,但在运行过程中不必一直驻留内存。
三．多项选择
1.下面的程序设计技术和数据结构”适合于”于请式调页环境的有_________。
A.栈 B.杂凑符号表 C.顺序查找 D.折半查找 E.纯代码 F.向量操作
2.假定有一个请式调页系统,现测得相关成分的利用率为：CPU的利用率20%;分页磁盘99.7%
其他I/0设备5%。有可能改进CPU利用率的措施有___________。
A.增加一个更快速的CPU B.增添一个更大的分页盘 C.增加多道程序的度数
D.减少多道程序的度数 E.增加其他更快速的I/O设备
3,可用来存储页表的存储器有__________。
A.cache B.主存 C.后援存储器 D.高速磁盘 E.寄存器
4.下列关于存储器管理功能的论述中,正确的论述有___________。
A.即使在多道程序设计的环境下,用户也能设计用物理地址直接访问内存的程序。
B.内存分配最基本的任务是为每道程序分配内存空间,其所追求的主要目标是提高存储空间的利用率。
C.为了提高内存保护的灵活性,内存保护通常由软件实现。
D.交换技术已不是现代操作系统中常用的技术。
E.地址映射是指将程序空间中的逻辑地址变为内存空间的物理地址。
F.虚拟存储器是物理上扩充内存容量。
5.引入段页式系统的主要动力有___________。
A.提高内存利用率 B.提高系统吞吐量 C.满足用户需要
D.更好地满足多道程序运行的需要 E.既满足用户要求,又提高内存利用率
6.从下列关于虚拟存储器的论述中,正确的论述有________。
A.在请求段页式系统中,以页为单位管理用户的虚空间,以段为单位管理内存空间。
B.在请求段页式系统中,以段为单位管理用户的虚空间,以页为单位管理内存空间。
C.为提高请求分页系统中内存的利用率,允许用户使用不同大小的页面。
D.在虚存中,为了能让更多的作业同时运行,通常只应装入部分的作业后便启动运行。
E.实现虚拟存储器的最常用的算法是最佳适应算法OPT。
F.由于有了虚拟存储器,于是允许用户使用比内存更大的地址空间。
四、填空题
1.将作业地址空间中的逻辑地址转换为主存中的物理地址的过程称为______.
2.决定缺页中断时间的主要因素有________、__________和___________。
3.分区分配中的存储保护通常采用_________方法。
4.常用的解决外部碎片问题的方法是_____________________。
5.主存中一系列物理存储单元的集合称为________。
6._____________页面调度,简称_______,是最常用的虚拟存储器系统。
7.重定位的方式有_______和_________两种。
8.在某些页面替换算法中,缺页率可能随着可使用的块数量的增加而增长.这种情况称为_________。
9.页表表目的主要内容包括______和_______.
10.分页环境下的存储保护是由与每页相连的_______________来完成的。
11,分区管理中采用"首次适应"分配算法时,应将空闲区按_______次序登记在空闲区表中。
12.在请求调页系统中有着多种置换算法;选择最先进入内存的页面予以淘汰的算法称为______;选择在以后不再使用的页面予以淘汰的算法称为______；选择自上次访问以来所经历时间最长的页面予以淘汰的算法称为_________选择自某时刻开始以来,访问次数最少的页面予以淘汰的算法称为________。
13.对外存对换区的管理应以________为主要目标,对外存文件区的管理应以________为主要目标。
14.在动态分区式内存管理中,倾向于优先使用低址部分空闲区的算法是_______,能使内存空间中空闲区分布得较均匀的算法是_______;每次分配时,把既能满足要求,又是最小的空闲区分配给进程的算法是__________。
15.提高内存利用率主要是通过_______功能实现的,_______的基本任务是为每道程序做______。使每道程序能在不受干扰的环境下运行,主要是通过____________功能实现的。
16.在请求页式管理中,页面置换算法常用的是_______和____________。
17.在页式和段式管理中,指令的地址部分结构形式分别为________和_________。
18.段表表目的主要内容包括___________。
19.假设某程序的页面访问序列为1、2、3、4、5、2、3、1、2、3、4、5、1、2、3、4且开始执行时主存中没有页面,则在分配给该程序的物理块数是3且采用FIFO方式时缺页次数是______；在分配给程序的物理块数是4且采用FIFO方式时,缺页次数是______。在分配给该程序的物理块数是3且采用LRU方式时,缺页次数是________。在分配给该程序的物理块数为4且采用LRU方式时,缺页次数是____________。
20.把_________地址转换为__________地址的工作称为地址映射。
21.静态重定位在_________时进行;而动态重定位在_________时进行。
22.在虚存管理中,虚拟地址空间是指逻辑地址空间,实地址空间是指________;前者的大小只受________限制,而后者的大小受_________。
23.在段式虚拟存储管理中,程序所使用的最大段数以及段的最大长度是由_____来决定的。
24.在段页式存储管理系统中,每道程序都有一个________表和一组________表。
25.若选用的______算法不合适,可能会出现抖动现象。
26.在页式存储管理系统中,常用的页面淘汰算法有:______,选择淘汰不再使用或最远的将来才使用的页;________,选择淘汰在主存驻留时间最长的页;________,选择淘汰离当前时刻最近的一段时间内使用得最少的页。
27.在虚拟段式存储管理中,若逻辑地址的段内地址大于段表中该段的段长,则发生______.
28.在请求页式存储管理中,若采用FIFO页面淘汰算法,则当分配的页面数增加时,____的次数可能增加也可能减少。
五、简答题
1.存储管理的主要功能是什么?
2.什么是虚拟存储器?其特点是什么?
3.在什么情况下需要进行重定位?为什么要引入动态重定位?
4.动态分区式管理的常用内存分配算法有哪儿种?比较它们各自的优缺点。
5.简述什么是覆盖?什么是交换?覆盖和交换的区别是什么?
6.什么是页式管理?静态页式管理可以实现虚存吗?
7.什么是请求页式管理?
8.什么是Belady现象?
9.段式管理可以实现虚存吗?如果可以,简述实现方法。
10.为什么要提出段页式管理?它与段式管理及页式管理有何区别?
11.为什么说段页式管理时的虚拟地址仍是二维的?
12.段页式管理的主要缺点是什么?有什么改进办法?
13.常用的内存保护方法有哪些?其特点是什么?
14.段式存储器管理和页式存储管理的区别是什么?
15．什么是请求分页存储管理的缺页中断率?影响缺页中断率的因素有哪些?
16.内存保护是否可以完全由软件来实现?为什么?
17.在以进程为单位进行对换时,每次是否将整个进程换出?为什么?
18.在请求分页系统中,为什么说一条指令执行期间可能产生多次缺页中断?
19．存储管理的主要研究内容是什么?
20.什么是虚拟存储器?实现虚拟存储器的物质基础是什么?
一．解析题
1.试述缺页中断与一般中断的主要区别。
2,在置换算法中,LRU和LFU哪个更常用?为什么?
3.什么是虚拟存储器?如何实现页式虚拟存储器?
4.实现地址重定位的方法有哪几类?
5.什么是局部性原理?什么是抖动?你有什么办法减少承统的抖动现象?
6.动态重定位的实现方式有哪几种?
7.在虚拟段式存储系统中,引入了段的动态链接。
(1)试说明为什么引入段的动态链接。
(2)请给出动态链接的一种实现方法。
8.虚拟存储器具有哪些基本特征?实现虚拟存储器的几个关键技术是什么?
9.请求页式管理中有哪几种常用的页面置换算法?试比较它们的优缺点。
10.动态分区式管理的常用内存分配算法有哪儿种?比较它们各自的优缺点。
11.常用的内存信息保护才法有哪儿种?它们各自的特点是什么?
12．引起系统抖动的原因是什么?系统如何检测抖动?一旦检测出抖动后,系统怎样消除它?
13．假定有一个使用"基址/界限寄存器"的操作系统,为了也能提供页表,曾对机器作了修改。那么能否用页来模拟"基址/界限寄存器"?若能则说明如何模拟:若不能,则说明为什么。
14.考虑一个请式调页的计算机系统,它使用一个分页盘,利用全局LRU替换算法和一种把页块平均分给进程的分配策略(即若有m个页块和n个进程,则每一进程分得m/n个页块).多道程序设计的度数固定为4,测得系统的CPU和分页盘的利用率为:
(l)CPU的利用率为13%,盘利用率为97%:
(2)CPU的利用率为87%,盘利用率为3%:
(3)CPU的利用率为13%,盘利用率为3%.
上述每一种情形可能会出现什么问题?能否用增加多道程序的度数来增加CPU的利用率?分页是否有助于提高利用率?
15.试说明多级存储方法与虚拟方法的主要区别.
16.在一分页存储管理系统中,逻辑地址长度为16位,页面大小为4096字节,现有一逻辑地址为2F6AH,且第0、1、2页依次存放在物理块5、10、11中,间相应的物理地址为多少?
二．算法题
1.分段与分页很类似,只是其"页"的大小是可变的.试基于FIFO和LRU页面替换算法提出两个段替换算法.
2.己知某分页系统统,主存容量为64K,页面大小为1K,对一个4页大的作业;其0、1、2、3页分别被分配到主存的2、4、6、7块中。
（1）将十进制的逻辑地址1023、2500、3500、4500转换成物理地址。
(2) 以十进制的逻辑地址1023为例画出地址变换过程图。
3.在一采取局部置换策略的请求分页系统中,分配给某个作业的内存块数为4,其中存放的四个页面的情况如表5.3所示。
表5.3四个页面的情况物理块
虚页号
装入时间
最后二次访问时间
访问位
修改位
0
2
60
157
0
1
1
1
160
161
1
0
2
0
26
158
0
0
3
3
20
163
1
1
上面的所有数字均为十进制数,所有时间都是从进程开始运行时从0开始计数的时钟数。请问,如果系统采用下列置换算法,将选择哪一页进行换出?
(1)FIFO算法;
(2)LRU算法;
(3)改进的Clock算法。
4.某页式虚存储系统的物理空间共3K,页面大小为1K,一进程按下列地址顺序引用内存单元:3635,3632,1140,3584,2892,3640,0040,2148,1700,2145,3209,0000,1102,1100。如果上述数字均为十进制数,而内存中尚未装入任何页。)给出使用LRU算法时的缺页次数,并与FIFO时的情况进行比较。
求调页,
5.有一个二维数组:
Var A:ARRAY[1..100,1..100] OF integer;
按先行后列的次序存储。对一采用LRU置换算法的页式虚拟存储器系统,假设每页可存放200个整数。若分配给一个进程的内存块数为3,其中一块用来装入程序和变量i,j,另外两块专门用来存放数组(不作它用),且程序段已在内存,但数据页尚未装入内存。请分别就下列程序计算执行过程中的缺页次数。
程序1,程序2:
FOR i:=1 TO 100 DO FOR j:=1 TO 100 DO
FOR j:=l TO 100 DO FOR i:=1 TO 100 DO
A[i,j]:=0 A[i,j]:=0
6.某虚拟存储器的用户空间共有32个页面,每页1K,主存16K。假定某时刻系统为用户的第0、1、2、3页分配的物理块号为5、10、4、7,而该用户作业的长度为6页,试将十六进制的虚拟地址OMC、103C、1A5C转换成物理地址。
7.某段式存储管理系统中,有一作业的段表(SMT)如下表所示,求逻辑地址[0,65],[1,55],[2,90],[3,20]对应的主存地址(按十进制)。
段号
段长〈容量〉
主存起始地址
状态
0
1
2
3
200
50
100
150
600
850
1000
0
0
0
1
8.表5.2给出了某系统中的空闲分区表,系统采用可变式分区存储管理策略。现有以下作业序列296K、2OK、200K。若用首次适应算法和最佳适应算法来处理这些作业序列,试问哪一种算法可以满足该作业序列的请求,为什么?
表5.2空闲分区表分区号
大小
起始地址
1
32K
100K
2
10K
150K
3
5K
200K
4
218K
220K
5
96K
530K
9.在一个请求分页存储管理系统中,一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,当分配给该作业的物理块数分别为3、4时,试计算采用下述页面淘汰算法时的缺页率(假设开始执行时主存中没有页面),并比较所得结果。
(1)最佳置换淘汰算法
(2)先进先出淘汰算法
(3)最近最久未使用淘汰算法
10.在某系统中,采用固定分区分配管理方式,内存分区(单位字节)情况如图5.9所示。现有大小为lk、9K、33K、121K的多个作业要求进入内存,试画出它们进入内存后的空间分配情况,并说明主存浪费有多大?
11.设有一页式存储管理系统,向用户提供的逻辑地址空间最大为16页,每页2048字节,内存总共有8个存储块,试问逻辑地址至少应为多少位?内存空间有多大?
12.在一个段式存储管理系统中,其段表为:
段号 内存起始地址 段长
0 210 500
1 2350 20
2 100 90
3 1350 590
4 1938 95
试求下述逻辑地址对应的物理地址是什么?
段 号 段内位移
430
10
500
400
112
32
13.某操作系统采用可变分区分配存储管理方法,用户区为512K且始址为0,用空闲分区表管理空闲分区。若分配时采用分配空闲区低地址部分的方案,且初始时用户区的512K空间空闲,对下述申请序列:
申请300K,申请100k,释放300K,申请150K,申请3OK,申请4OK,申请6OK,释放3OK
回答下列问题:
(1)采用首次适应算法,空闲分区中有哪些空块(给出始址、大小)?
(2)采用最佳适应算法,空闲分区中有哪些空块(给出始址、大小)?
(3)如再申请look,针对(1)和(2)各有什么结果?
14.有一页式系统,其页表存放在主存中。
(1)如果对主存的一次存取需要15微秒,试问实现一次页面访问的存取时间是多少?
(2)如果系统加有快表,平均命中率为85%,当页表项在快表中时,其查找时间忽略为0,试问此时的存取时间为多少?
15.若在一分页存储管理系统中,某作业的页表如下所示。已知页面大小为1024字节,试将逻辑地址1011,2148,3000,4000,5012转化为相应的物理地址。
页号 块号
0 2
1 3
2 1
0 6
16,26.设一作业共有5页(第0—4页),其中程序占3页(第0—2页)、常数占1页(第3页)、工作单元占1页(第4页)。它们依次放在外存的45、46页和98、99、100页.现已由程序段分配在内存的7、10、19页中:而常数区和工作区尚未获得内存.请回答下述问题:
(l)页表应包括哪些项目?填写此页表，若工作区分配到内存的第9页,则页表如何变化?
(2)在运行中,因需使用常数而发生中断,假定此时内存无空闲页面,需要把第9页淘汰,操作系统应如何处理?页表又发生什么变化?
17,24.一个好的页面替换算法应使缺页中断次数最少，一种方法是将正使用的页均匀地分散在整个存储区中.可以给每一页块附加一个计数器,用它记录与该页块相关的页的个数，当进行页面替换时,选择其计数器之值最小的那个页块.
(1)利用上述思想,提出一个页面替换算法,并回答下面的问题:
A．该计数器的初值是多少?
B．该计数器何时增值?
C.该计数器何时减值?
D.如何选择被替换的页?
(2)若有4个页块,给定下面的页访问串,使用你的算法将会出现多少次缺页中断?
1,2,3,4,5,3,4,1,6,7,8,9,7,8,9,5,4,5,4,2
(3)给定(2)中同样的条件和访问串,若采用最佳页面替换算法,其缺页中断次数的最小值是多少?
18.考虑下面的页访问串:
1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6
假定分别有1,2,3,4,5,6,7个页块,应用下面的页面替换算法,各会出现多少次缺页中断?
(1)LRU:
(2)FIFO:
(3)Optima1.
19,18．对于所给定的如表4.2所示的段表,下面逻辑地址所对应的物理地址是什么?
(1)0,430； (2)1,10； (3)1,11； (4)2,500； (5)3,400； (6)4,112
表4-2
段
基址
长度
0
219
600
1
2300
14
2
90
100
3
1327
580
4
1952
96
20．对于下面的页面替换算法:
LRU；(2)FIFO；(3)Optimal；(4)Second Chance；
按照缺页中断从劣到优的顺序排列它们,并区分出它们是否有Belady异态。
21.在采用页式存储管理的系统中,某作业J的逻辑地址空间为4页(每页2048字节),且已知该作业的页面映象表(即页表)如下:
页号 块号
0 2
1 4
2 6
3 8
试借助地址变换图(即要求画出地址变换图)求出有效逻辑地址4865所对应的物理地址。
22.在虚拟页式存储管理中,为解决抖动问题,可采用工作集模型以决定分给进程的物理块数,有如下页面访问序列:
…2 5 1 6 3 3 7 8 9 1 6 2 3 4 3 4 3 4 4 4 3 4 4 3……
Δ t1 Δ t2
窗口尺寸A =9,试求t1、t2时刻的工作集。
答:一个进程在时间t的工作集可形式化地定义为:
W(t,h)={在时间t-h到t之间所访问的一串页面}
其中,h为工作集窗口尺寸。
由题目所给条件可知,t1时刻的工作集为:{1,2,3,6,7,8,9}
t2时刻的工作集为:{3,4}
4.4自测练习答案一、判断题
1.√ 2,× 3.× 4,√ 5.√ 6,× 7,√ 8.× 9,× 10,√
二、选择题
1.C 2.B 3.B 4.D 5.D 6.A 7.C 8.D 9.A 10.A 11.A 12.A 13.D
14.A 15.D 16.A 17.D 18.D 19.C 20.A 21.B 22.B 23.A 24.D 25.D 16.A 27.A 28.B 29.A 30.B
填空题
1.地址变换 2.中断服务时间 交换页面的时间 重启进程的时间
3.界限寄存器和存储保护键 4.压缩或移动 5.存储空间 6.请求式 请式调页
7.静态重定位 动态重定位 8.Beladv异态 9.页号 块号 10.保护位
11.地址递增 12.FIFO算法 OPT算法 LRU算法 LFU算法
13.提高存储空间的利用率 D.提高换入换出速度
14.首次适应算法 循环首次适应算法 最佳适应算法答
15.内存分配 分配内存 内存保护 16.先进先出 最近最久未使用
17.页号及页内位移 段号及段内位移 18.段号、段在内存的起始地址、段长度
19.13 14 14 12 20.逻辑 物理 21.程序装入内存 程序执行
22.物理地址空间 机器的地址长度 物理内存大小限制
23.逻辑地址结构答 24.段 页 25.页面置换答
26.最佳算法 先进先出算法 最近最少使用 27.地址越界中断 28.缺页中断四、简答题
1.答:存储管理的主要功能包括以下几点:
(1)在硬件的支持下完成统一管理内存和外存之间数据和程序段自动交换的虚拟存储器功能。
（2)将多个虚存的一维线性空间或多维线性空间变换到内存的唯一的一维物理线性地址空间。
(3)控制内外存之间的数据传输。
(4)实现内存的分配和回收。
(5)实现内存信息的共享与保护。
2,答:由进程中的目标代码、数据等的虚拟地址组成的虚拟空间称为虚拟存储器。虚拟存储器不考虑物理存储器的大小和信息存放的实际位置,只规定每个进程中相互关联信息的相对位置。每个进程都拥有自己的虚拟存储器,且虚拟存储器的容量是由计算机的地址结构和寻址方式来确定。
实现虚拟存储器要求有相应的地址转换机构,以便把指令的虚拟地址变换为实际物理地址;另外,由于内存空间较小,进程只有部分内容存放于内存中,待执行时根据需要再调入内存。
3,答:源程序经过编译产生的目标模块一般总是从0开始编址的,其中的地址都是相对于起始地址的相对地址。在将目标模块经过链接装入内存时,其分配到的内存空间的起始地址通常不为0,因此指令和数据的实际物理地址与装入模块中的相对地址是不同的。此时,为了使程序能够正确执行,必须将相对地址转换成物理地址,即进行重定位。
进程在运行过程中经常要在内存中移动位置〈如对换、紧凑时),引入动态重定位的目的就是为了满足程序的这种需要,动态重定位的实现需要一定的硬件支持,重定位的过程是由硬件地址变换机构在程序执行每条指令时自动完成的。
4,答:动态分区式管理的常用内存分配算法有最先适应法(FF)、最佳适应法(BF)和最坏适应法(WF)
优缺点比较：
①从搜索速度上看最先适应法最佳,最佳适应法和最坏适应法都要求把不同大小的空闲区按大小进行排队。
②从回收过程来看,最先适应法也是最佳,因为最佳适应法和最坏适应法都必须重新调整空闲区的位置。
③最佳适应法找到的空闲区是最佳的,但是会造成内存碎片较多,影响了内存利用率,而最坏适应法的内存碎片最少,但是对内存的请求较多的进程有可能分配失败。
总之,三种算法各有所长,针对不同的请求队列,它们的效率和功能是不一样的。
5.答:将程序划分为若干个功能上相对独立的程序段,按照程序的逻辑结构让那些不会同时执行的程序段共享同一块内存区的内存扩充技术就是覆盖。
交换是指先将内存某部分的程序或数据写入外存交换区,再从外存交换区中调入指定的程序或数据到内存中来,并让其执行的一种内存扩充技术。
与覆盖技术相比,交换不要求程序员给出程序段之间的覆盖结构,而且,交换主要是在进程或作业之间进行,而覆盖则主要在同一个作业或同一个进程内进行。另外,覆盖只能覆盖那些与覆盖程序段无关的程序段。
6.答:页式管理就是把各进程的虚拟空间划分为若干长度相等的页面,把指令按页面大小划分后存放在内存中执行或只在内存中存放那些经常被执行或即将被执行的页面,而那些不被经常执行以及在近期内不可能被执行的页面则存放于外存中,按一定规则调入的一种内存管理方式。
静态页式管理不能实现虚存,这是因为静态页式管理要求进程或作业在执行前全部被装入内存,作业或进程的大小仍受内存可用页面数的限制。
7.答:请求页式管理是动态页式内存管理的一种,它在作业或进程开始执行之前,不把作业或进程的程序段和数据段一次性的全部装入内存,而只装入被认为是经常反复执行和调用的工作区部分。其他部分则在执行过程中动态装入。请求页式管理的调入方式是,当需要执行某条指令而又发现它不在内存时,或当执行某条指令需要访问其他数据或指令时,而这些指令和数据又不在内存中,从而发生缺页中断,系统将外存中相应的页面调入内存。
8,答,Belady现象是指在使用FIFO算法进行内存页面置换时,在未给进程或作业分配足它所要求的全部页面的情况下,有时出现的分配的页面数增多,缺页次数反而增加的奇怪现象。
9.答:段式管理可以实现虚存。
段式管理把程序按照内容或过程〈函数〉关系分成段,每段拥有自己的名字。一个用户作业或进程所包含的段对应于一个二维线性虚拟空间〈段号s与段内相对地址w),也就是一个二维虚拟存储器。段式管理以段为单位分配内存,然后通过地址映射机构把段式虚拟地址转换成实际的内存物理地址。只把那些经常访问的段驻留内存,而把那些在将来一段时间内不被访问的段放入外存,待需要时产生缺段中断E自动调入。
10答:因为段式管理和页式管理各有所长。段式管理为用户提供了一个二维的虚拟地址空间,反映了程序的逻辑结构,有利于段的动态增长以及共事和内存保护等,这极大地方便了用户。而分页系统则有效地克服了碎片,提高了存储器的利用效率。从存储管理的目的来讲,主要是方便用户的程序设计和提高内存的利用率。所以人们提出了将段式管理和页式管理结合起来让其互相取长补短的段页式管理段页式管理与段式和页式管理相比,真访问时间较长。因此,执行效率低。
11.答:因为在段页式内存管理中,对每一段内的地址空间进行分页式管理只是为了克服在内存分配过程中产生的大量碎片,从而提高存储器的利用效率,它并没有改变段内地址空间的一维结构,所以段页式内存管理中的虚拟地址仍然和段式内存管理中的虚拟地址一样是二维结构的。
12.答:段页式管理的主要缺点是对内存中指令或数据进行存取时,至少需要对内存进行三次以上的访问。第一次是由段表地址寄存器取段表始址后访问段表,由此取出对应段的页表在内存中的地址。第二次则是访问页表得到所要访问的指令或数据的物理地址。只有在访问了段表和页表之后,第三次才能访问真正需要访问的物理单元。显然。这将大大降低CPU执行指令的速度。
改进办法是设置快速联想寄存器。在快速联想寄存器中,存放当前最常用的段号s,页号p和对应的内存页面地址与其他控制项。当需要访问内存空间某一单元时,可在通过段表、页表进行内存地址查找的同时,根据快速联想寄存器查找其段号和页号。如果所要访问的段或页的地址在快速联想寄存器中,则系统不再访问内存中的段表、页表而直接把快速联想寄存器中的值与页内相对地址d拼接起来得到内存地址。
13.答：常用的内存保护方法有硬件方法、软件方法以及软硬结合方法。
14.答：分页和分段都采用离散分配方式,它们的区别是:
(1)页式管理中源程序进行编译连接时是将主程序、子程序、数据区等按照线性空间的一维地址顺序排列起来。段式管理则是将程序按照内容或过程(函数)关系分成段,每段拥有自己的名字。一个用户作业或进程所包含的段对应于一个二维线性虚拟空间,也就是一个二维虚拟存储器。
(2)同动态页式管理一样,段式管理也提供了内外存统一管理的虚存实现技术。与页式管理不同的是:段式虚存每次交换的是一段有意义的信息,而不是像页式虚存管理那样只交换固定大小的页,从而需要多次的缺页中断才能把所需要的信息完整地调入内存。
(3)在段式管理中,段长可根据需要动态地增长。这对那些需要不断增加或改变新数据或子程序的段来说,将是非常有好处的。
(4)段式管理便于对具有完整逻辑功能的信息段进行共享。
(5)阶段式管理便于进行动态链接,而页式管理进行动态链接的过程比较复杂。
15.答：1.缺页中断率=缺页中断次数/访问页面的总次数影响请求分页缺页中断率的因素有,①分配给作业的主存块数；②页面的大小；③程序的局部化程度；④页面调度算法。
16.答:内存保护的主要任务是确保每道程序都只在自己的内存区内运行。这就要求系统能对每条指令所访问的地址进行越界检查。若发生越界,系统应能立即发现,并发出越界中断请求,以抛弃该指令。若每次检查完全用软件实现,则每执行→条指令时,都要增加铋若干条指令去行越界的检查功能,这无疑将降低程序的执行速度,因此,J越界检查通常由硬件实现,并使指令的执行与越界检查功能并行执行,从而不使程序的运行速度降低。当然,对发现有越界后的处理需与软件配合来完成。因此说内存保护功能是由硬件和软件协同完成的。
17.答:在以进程为单位进行对换时,并非每次都将整个进程换出。这是因为:
(1)从结构上讲,进程是由程序段、数据段和进程控制块组成的,其中进程控制块总有部分或全部常驻内存，不被换出。
（2）程序段和数据段可能正被若干进程共享，此时它们也不能换出。
18.答:因请求调页时,只要作业的部分页在内存,该作业就能执行,而在执行过程中发现所要访问的指令或数据不在内存时,则产生缺页中断,将所需的页面调入内存。在请求调页系统中,一条指令(如copy A to B)可能跨了两个页,而其中要访问的操作数可能与指令不在同一个页上,且操作数本身也可能跨两个页。当要执行这类指令,而相应的页都不在内存时,就将产生多次缺页中断。
19.答:存储管理的主要研究内容是主存存储分配、地址再定位、存储保护和存储扩充。
20.答:虚拟存储器简称虚存,是利用操作系统产生的一个其容量比实际主存大得多的存储器,实际上是一个地址空间。实现虚存的物质基础是:一定容量的主存;大容量的辅存和地址变换机构。虚存不可能无限大,它受字长、速度(传送速度〉、使用频率等因素的限制,其最大容量由计算机系统的地址机构决定。虚存可分为三类:分页式虚存、分段式虚存和段页式虚存。
解析题
1.答:缺页中断作为中断,同样需要经历保护CPU现场、分析中断原因、转缺页中断处理程序进行处理、恢复CPU现场等步骤。但缺页中断又是一种特殊的中断,它与一般中断的主要区别是:
（1）在指令执行期间产生和处理中断信号。通常,CPU都是在一条指令执行完后去检查是否有中断请求到达。若有便去响应中断;否则继续执行下一条指令。而缺页中断是在指令执行期间,发现所要访问的指令或数据不在内存时产生和处理的。
（2）一条指令在执行期间可能产生多次缺页中断。例如,对于一条读取数据的多字节指令,指令本身跨越两个页面,假定指令后一部分所在页面和数据所在页面均不在内存,则该指令的执行至少产生两次缺页中断。
2,答：LRU置换算法比LFU置换算法更常用。
置换算法总是希望被换出的页(段)在不久的将来再被访问的概率尽可能小。然而LFU算法往往不能实现这一点。因为在LFU算法中,某页被访问的次数是用计数器计数的,在有些情况下,刚被调入的页(段)由于局部性原理,可能立即被访问多次,因而其计数器的计数值会很大;但过了这一小段时间后,该页(段)又不再被访问。这样,在根据置换算法确定的原则选择某一页(段)将之换出时,这样的页(段)会被留在内存中,而将其他页(段)换出去。
虽然如此被调出的页(段)在刚才一段时间内其被访问次数的计数值较小,但有可能马上又要访问。可见,LFU算法的置换选择可能导致很坏的选择。
但在LRU算法中,由于是选择最近最久未被访问的页(段)置换出去,即预计在最近的将来该页被访问的概率也很小,因此,这种置换算法可能导致较好的选择,这使LRU算法或其近似算法获得了较好的应用。
3,答:虚拟存储器是指具有请求调入功能和置换功能,能从逻辑上对内存容量进行扩充的一种存储系统。从用户观点看,虚拟存储器具有比实际内存大得多的容量,其逻辑容量由逻辑地址结构以及内存和外存容量之和决定,其运行速度接近于内存的速度,而每位成本却又接近于外存。
为实现虚拟存储器,首先需要扩充页表,增加状态位以指出所需页是否在内存,增加外存始址以便调入页面,增加引用位以供置换算法用,增加修改位使得换出时减少写盘次数。另外,还要使用两种关键技术:
(1)请求调页技术:请求调页技术是指及时将进程所要访问的、不在内存中的页调入内存。该功能是由硬件(缺页中断机构发现缺页)和软件(将所需页调入内存)配合实现的。
(2)置换页技术:当内存中已无足够空间用来装入即将调入的页时,为了保证进程能继续运行,系统必须换出内存中的部分页,以腾出足够的空间。具体的置换操作并不复杂,其关键是应将哪些页换出,即采取什么置换算法。
4,答:实现地址重定位的方法有两种:静态地址重定位和动态地址重定位。
(1)静态地址重定位是在虚空间程序执行之前由装配程序完成地址映射工作。静态重定位的优点是不需要硬件支持,但是用静态地址重定位方法进行地址变换无法实现虚拟存储器。静态重定位的另一个缺点是必须占用连续的内存空间和难以做到程序和数据的共享。
(2)动态地址重定位是在程序执行过程中,在CPU访问内存之前由硬件地址变换机构将要访问的程序或数据地址转换成内存地址。动态地址重定位的主要优点有:
①可以对内存进行非连续分配。
②动态重定位提供了实现虚拟存储器的基础。
③动态重定位有利于程序段的共享。
5,答:局部性原理是指在几乎所有程序的执行过程中,在一段时间内,CPU总是集中地访问程序中的某一个部分而不是对程序的所有部分具有平均的访问概率。
抖动是指当给进程分配的内存小于所要求的工作区时,由于内存外存之间交换频繁,访问外存的时间和输入输出处理时间大大增加,反而造成CPU因等待数据而空转,使得整个系统性能大大下降。
在物理系统中,为了防止抖动的产生,在进行淘汰或置换时,一般总是把缺页进程锁住,不让其换出,从而防止抖动发生。
防止抖动发生的另一个办法是设置较大的内存工作区。
6,答:动态重定位的实现必须有硬件地址变换机构的支持,其具体的实现方式主要有：
(1)连续分配方式下的动态重定位。连续分配方式需在整个系统中设置一个重定位寄存器,用来存放正在执行的作业在内存中的起始地址。当CFU要存取指令或数据时,硬件的地址变换机构自动将逻辑地址与重定位寄存器的值相加,形成指令或数据的物理地址。
(2)离散分配方式下的动态重定位。离散分配方式主要是指分页和分段存储管理方式,此时,系统首先必须为每个作业配置一张页(段)表,用来记录作业的每个页(段)对应的内存块号(内存始址和段长),页(段)表被存放在内存中。而在整个系统中则只需设置一个页(段)表控制寄存器,用来存放正在执行的作业的页(段)表始址和长度。当CPU要存取指令或数据时,硬件的地址变换机构自动将逻辑地址分成页号和页内地址两部分(或直接从逻辑地址中获得段号),并根据页(段)号到控制寄存器所指示的页(段)表中获得对应的物理块号(或段的内存始址),并与页内地址(或段内存地址)拼接(或相加),形成物理地址。
7,答：(1)在作业装入内存运行前,应将各个目标程序定位后装入作业的地址空间,形成可执行程序的链接,称为静态链接。静态链接常常因为目标程序个数多而花费大量的CPU时间,而实际运行时又常常只用到其中的部分模块,因而也造成了存储空间的浪费。动态链接是作业运行时先装入主程序,运行过程中需要某模块时,再将该模块的目标程序调入内存并进行链接,它克服了静态链接的不足。
(2)分段存储管理就是最典型的动态链接。分段管理允许用户将作业按逻辑关系进行自然分段,各段的大小可以不同。逻辑段内的地址是由两部分组成的(s,段号,d：段内位移量),即分段地址空间是用户定义的三维空间。内存分配以段为单位,段可以在作业运行过程中根据请求而动态链接和装入。
8,答:虚拟存储器的基本特征有:
(1)多次性。作业只要部分装入内存便可后动执行;z共余部分可待需要时再调入内存,即一个作业将分成多次装入内存。
(2)对换性。在进程运行期间,允许将那些暂不使用的程序和数据从内存魄至外存的对换区(换出),待以后需要时再将它们从外存调入内存(换入)。
(3)离散性。实现虚拟存储器必须采用离散的分配技术,而连续的分配技术无法实现虚拟存储器的功能。
(4)虚拟性。虚拟存储器只是在逻辑上扩充内存容量,而实际的内存容量并没有真正扩大。
实现虚拟存储器的关键技术有以下两个:
(1)请求调页(段)技术。这是指及时将进程所要访问的、不在内存中的页(段)调入内存。
该功能是由硬件(缺页(段)中断机构)发现缺页(段)和软件(将所需页(段)调入内存)配合实现的。
(2)置换页(段)技术。当内存中已无足够空间用来装入即将调入的页(段)时,为了保证进程能继续运行,系统必须换出内存中的部分页(段),以腾出足够的空间,将所嚣的页(段)调入内存。具体的置换操作并不复杂,其关键是应将哪些页(段)换出,即采取什么置换算法。
9,答:比较常用的页面置换算法有:
(1)随机淘汰算法：即随机地选择某个用户页面并将其换出。
(2)轮转法RR：轮转法循回换出内存可用区内一个可以被换出的页,无论该页是刚被换进或已经换进内存很长时间。
(3)先进先出法FIFO：FIFO算法选择在内存驻留时间最长的一页将其淘汰。
(4)最近最久未使用页面置换算法LRU:该算法的基本思想是:当需要淘汰某一页时,选择离当前时间最近的一段时间内最久没有使用过的页面先淘汰。
(5)理想型淘汰算法OPT:该算法淘汰在访问串中将来再也不出现的或是在离当前最远的位置上出现的页面。
RR和FIFO都是基于CPU按线性顺序访问地址空间这一假设,但是实际上CPU在很多时候并非是按线性顺序访问地址空间的,因而官们的内存利用率不高。此外FIFO算法还存在着Belady现象。LRU算法的完全实现是相当困难的,因此在实际系统中往往要采取LRU的近似算法,常用的近似算法有最不经常使用页面淘汰算法LFU和最近没有使用页面淘汰算法(NUR)。OPT算法由于必须预先知道每一个进程的指令访问串,所以它是无法实现的。
10,答:动态分区式管理的常用内存分配算法有最先适应法(FF)、最佳适应法(BF)和最坏适应法(WF)
优缺点比较：
①从搜索速度上看最先适应法最佳,最佳适应法和最坏适应法都要求把不同大小的空闲区按大小进行排队。
②从回收过程来看,最先适应法也是最佳,因为最佳适应法和最坏适应法都必须重新调整空闲区的位置。
③最佳适应法找到的空闲区是最佳的,但是会造成内存碎片较多,影响了内存利用率,而最坏适应法的内存碎片最少,但是对内存的请求较多的进程有可能分配失败。
总之,三种算法各有所长,针对不同的请求队列,它们的效率和功能是不一样的。
11,答:常用的内存保护方法有硬件法、软件法和软硬件结合保护法三种。
上下界保护法是一种常用的硬件保护法。上下界存储保护技术要求为每个进程设置对上下界寄存器。上下界寄存器中装有被保护程序和数据段的起始地址和终止地址。在程序执行过程中,在对内存进行访问操作时首先进行访问地址合法性检查,即检查经过重定位之后的内存地址是否在上、下界寄存器所规定的范围之内。若在规定的范围之内,则访问是合法的，否则是非法的,并产生访问越界中断。
保护键法也是一种常用的软件存储保护法。保护键法为每一个被保护存储块分配一个单独的保护键。在程序状态字中则设置相应的保护键开关字段,对不同的进程赋予不同的开关代码以和被保护的存储块中的保护键匹配。保护键可以设置成对读写同时保护的或只对读写进行单项保护的。如果开关字段与保护键匹配或存储块未受到保护,则访问该存储块是允许的,否则将产生访问出错中断。
另外一种常用的硬软件内存保护方式是z界限存储器与CPIJ的用户态,核心态相结合的保护方式。在这种保护方式下,用户态进程只能访问那些在界限寄存器所规定范围内的内存部分,而核心态进程则可以访问整个内存地址空间。
12,解:由于分配给进程的页面数少于进程所需的最低页面数,导致出现接连不断的缺页中断,从而引起系统抖动.系统可以利用将CPU的利用率与多道程序的度数进行比较的方法来检测系统抖动,一旦发生抖动,可通过减少多道程序的度数的办法来消除它。
13.解:只要内存按固定大小的段分配,就可用页表模拟"基址/界限寄存器".在这种方法中,页表可记录段的基址,而其有效/无效"位用于指明该段在内存中的部分.此外,还要注意解决可能出现的内部碎片问题。
14.解(1)会出现抖动现象:
(2)CPU的利用率相当高,可以增加多道程序度数:
(3)增加多道程序的度数.
15解：所谓多级存储方法是指在主存以外再配上后援存储器来补充主存,先把用户作业放在后援存储器上,然后等到要真正执行它时再设法把这部分作业调入主存,它们之间的调度由用户自己负责,这造成用户使用上的困难.由于系统不同,其主存大小也会随之不同,用户往往不得不修改程序.在批量分时系统中多个用户同时共享主存,因此,用户就不能直接参与主存和后援存储器之间的调度了.这就需要由操作系统来对它进行统一的、自动的管理,并采用虚拟存储技术:有了虚拟存储器之后,用户就不感到主存和后援存储器之间的区别,而在统一的逻辑存储器上安排程序和数据.由于虚拟存储器比实际存储器大得多,因而可以同时装入许多作业。
16,由题目所给条件可知,本页式系统的逻辑地址结构为:
页号P
页内位移量W
15 12 11 0
逻辑地址2F6AH的二进制表示如下:
P W
0010 111101101010
由此可知逻辑地址2F6AH的页号为2,该页存放在第11号物理块中,用十六进制表示块号为B,所以物理地址为BF6AH。
二．算法题
1,解:FIFO查找第一个能容纳即将进入的段,若不允许重定位且没有一个段能容纳即将进入的段,则选择几个内存区域连续的段,它们"最靠近空闲空间表的首部",合并它们后能容纳即将进入的段.若允许重定位,则重新安排内存,使得能够容纳即将进入段的开始的N个段在内存中是连续的.在这两种情况都应将剩余空间并人空闲空间表中.
LRU选择一个未被使用的、时间周期最长的能容纳即将进入段的段,并将剩余空间加到空闲空间表中.若没有满足要求的段,则选择一组内存连续的、且合并起来满足要求的"最老"的段(不能重定位的情况).若可以重定位,则重新安排这组最老的段,使其在内存中是连续的,它们合并后可以满足即将进入段的要求。
注意:由于段的大小可以不同,因此,所选定被替换的段可能小于要替换它的那个段,需要分别考虑对能够重定位和不能重定位的情况.
2,分析：在分页系统中进行地址转换时,地址交换机构将自动把逻辑地址转化为页号和页内地址,如果页号不小于页表长度,则产生越界中断;否则便以页号为索引去检索页表,从中得到对应的块号,并把块号和页内地址分别送入物理地址寄存器的块号和块内地址字段中,形成物理地址。答:(1)对上述逻辑地址,可先计算出它们的页号和页内地址(逻辑地址除以页面大小，得到的商为页号,余数为页内地址),然后通过页表转换成对应的物理地址。
①逻辑地址1023:1023/1k,得到页号为0,页内地址为1023,查页表找到对应的物理块号为2,故物理地址为2×1K+1023=3071。
②逻辑地址2500：2500/1K，得到页号为2,页内地址为452,查页表找到对应的物理块号为6,故物理地址为6×1K+452=6596。
③逻辑地址3500:3500/1K,得到页号为3,:页内地址为428,查页表牛找到对应的物理块号为7,故物理地址为7×1K+428=7596。
④逻辑地址4500:4500/1K,得到页号为4,页内地址为404,因页号不小于页表长度,故产生越界中断。
(2)逻辑地址1023的地址变换过程如图4.12所示,其中的页表项中没考虑每页的访问权限。
3分析：FIFO算法即先进先出算法,它选择最先装入内存的页面进行换出;LRU算法即最近最久未用置换算法,它选择最近最长时间没被使用的页面进行换出;改进的Clock算法是一种常用的LRU近似算法,它优先选择访问位和修改位均为0的页面进行换出。
答,(1)FIFO算法选择的换出页是物理块3中的第3页。
(2)LRU算法选择的换出页是物理块0中的第2页。
(3)改进的Clock算法选择的换出页是物理块2中的第0页。
4答:(1)根据题意,分配给作业的内存块数为3,而页面的引用次序为:3、3、1、3、2、3、0、2、1、2、3、0、1、1。因此,可以计算出,采用LRU算法时,缺页次数为8,采用FIFO算法时,缺页次数为6。LRU算法用最近的过去来作为预测最近的将来的依据,一般认为其有较好的性能,但实现时,要记录最近在内存的每个页面的使用情况,比FIFO困难,其开销也大。有时,因页面的过去和未来的走向之间并无必然的联系,如上面,LRU算法的性能就没想象中那么。
5,答:对程序1,首次缺页中断（访问A[0,0]时产生）将装入数组的第1、2行共200个整数，由于程序是按行对数组进行访问的,只有在处理完200个整数后才会再次产生缺页中断；以后每调入一页,也能处理200个整数,因此,处理100×100个整数共将发生50次缺页。
对程序2,首次缺页中断同样将装入数组的第1、2行共200个整数,但由于程序是按列对数组进行访问的,因此在处理完2个整数后又会再次产生缺页中断:以后每调入一页,也只能处理2个整数,因此,处理100×100个整数共将发生5000次缺页。
6,答:由题目所给条件可知,该系统的逻辑地逻辑地址有15位,其中高5位为页号,低10位为页内地址;物理地址有14位,其中高4位为块号,低10位为块内地址。另外,由于题目中给出的逻辑地址是十六进制数,故可先将其转换成二进制数以直接获得页号和页内地址,再完成地址的转换。
（1）逻辑地址(OA5C)的页号为（00010），即2,故页号合法；从页表中找到对应的内存块号为4,即(0100)；与页内地址(10 0101 1100)拼接形成物理地址(010010 01011100),即(125C)。
(2)逻辑地址(103C)l6的页号为4,页号合法,但该页未装入内存,故产生缺页中断。
(3)逻辑地址。A5Ch的页号为6,为非法页号,故产生越界中断。
7,解：逻辑地址[0,65]：对应的主存地址为600+65=665
逻辑地址[1,55]:因段内地址超过段长,所以产生段地址越界中断。
逻辑地址[2,90]:对应的主存地址为1000+90=1090。
逻辑地址[3,2O]:因为状态位为1,即该段在辅存中,所以产生缺页中断。
8.分析：首次适应算法要求空闲分区按地址递增的次序排列,在进行内存分配时,总是从空闲分区农首开始顺序查找,直到找到第一个能满足其大小要求的空闲分区为止.然后,再按照作业大小,从该分区中划出一块内存空间分配给请求者,余下的空闲分区仍留在空闲分区表中。
最佳适应算法要求空闲分区按大小递增的次序排列,在进行内存分配时,总是从空闲分区农首开始顺序查找,直到找到第一个能满足其大小要求的空闲分区为止.如果该空闲分区大于作业的大小,则与首次适应算法相同,将剩余空闲区仍留在空闲区农中。
解：若采用最佳适应算法,在申请96K存储区时,选中的是5号分区,5号分区大小与申请空间大小一致,应从空闲分区表中删去该表项:接着申请2OK时,选中1号分区,分配后1号分区还剩下12IQ最后申请200K,选中4号分区,分配后剩下18K。显然采用最佳适应算法进行内存分配,可以满足该作业序列的需求。为作业序列分配了内存空间后,空闲分区表如表5.3(a)所示。
若采用首次适应算法,在申请96K存储区时,选中的是4号分区,进行分配后4号分区还剩下122IQ接着申请2OK,选中1号分区,分配后剩下12IQ最后申请200K,现有的五个分区都无法满足要求,该作业等待。显然采用首次适应算法进行内存分配,无法满足该作业序列的需求。这时的空闲分区表如表5.3(B)所示。
分区号
大小
起始地址
1
12K
100K
2
10K
150K
3
5K
200K
4
18K
220K
表5.3分配后的空闲分区表
(A) (B)
分区号
大小
起始地址
1
12K
100K
2
10K
150K
3
5K
200K
4
122K
220K
5
96K
530K
9,解:(1)根据所给页面走向,使用最佳页面淘汰算法时,页面置换情况如下:
走向 4 3 2 1 4 3 5 4 3 2 1 5
块1 4 4 4 4 4 2 2
块2 3 3 3 3 3 1
块3 2 1 5 5 5
缺页 缺 缺 缺 缺 缺 缺 缺
缺页率为:7/12
走向 4 3 2 1 4 3 5 4 3 2 1 5
块1 4 4 4 4 4 1
块2 3 3 3 3 3
块3 2 2 2 2
块4 1 5 5
缺页 缺 缺 缺 缺 缺 缺
缺页率为:6/12
由上述结果可以看出,增加分配给作业的内存块数可以降低缺页率。
(2)根据所给页面走向,使用先进先出页面淘汰算法时,页面置换情况如下:
走向 4 3 2 1 4 3 5 4 3 2 1 5
块1 4 4 4 1 1 1 5 5 5
块2 3 3 3 4 4 4 2 2
块3 2 2 2 3 3 3 1
缺页 缺 缺 缺 缺 缺 缺 缺 缺 缺
缺页率为:9/12
走向 4 3 2 1 4 3 5 4 3 2 1 5
块1 4 4 4 4 5 5 5 5 1 1
块2 3 3 3 3 4 4 4 4 5
块3 2 2 2 2 3 3 3 3
块4 1 1 1 1 2 2 2
缺页 缺 缺 缺 缺 缺 缺 缺 缺 缺 缺
缺页率为:10/12
由上述结果可以看出,对先进先出算法而言,增加分配给作业的内存块数反而使缺页率上升,这种异常现象称为Belady现象。
(3)根据所给页面走向,使用最近最久未使用页面淘汰算法时,页面置换情况如下:
走向 4 3 2 1 4 3 5 4 3 2 1 5
块1 4 4 4 1 1 1 5 2 2 2
块2 3 3 3 4 4 4 4 1 1
块3 2 2 2 3 3 3 3 5
缺页 缺 缺 缺 缺 缺 缺 缺 缺 缺 缺
缺页率为,10/12
走向 4 3 2 1 4 3 5 4 3 2 1 5
块1 4 4 4 4 4 4 4 5
块2 3 3 3 3 3 3 3
块3 2 2 5 5 1 1
块4 1 1 2 2 2
缺页 缺 缺 缺 缺 缺 缺 缺 缺
缺页率为,8/12
由上述结果可以看出,增加分配给作业的内存块数可以降低缺页率。
10,解:从图5.9可以看出,该系统中共有四个分区,第一分区的大小为8K,第二分区的大小为32K,第三分区的大小为120K,第四分区的大小为332K。作业进入系统后的内存分配情况,如图5.10所示:
操作系统
第一分区
第二分区
第三分区
第四分区
操作系统
1K的作业第一分区
9K的作业第二分区
33K的作业
第三分区
12K的作业
第四分区
0
20K
28K
60K
180K
512K-1
从图5.10可以看出,作业进入系统后,第一分区剩余空间为7K,第二分区剩余空间为23K,第三分区剩余空间为87K,第四分区剩余空间为211K。主存空间浪费328K。
11,分析：在页式存储管理中,用户作业的地址空间被划分成若干大小相等的区域,称为页或页面。相应地,将主存的存储空间也分成与页大小相等的区域,称为块或物理块。在为作业分配存储空间时,总是以块为单位来分配,可以将作业中的任意一页放到主存的任意一块中。页式存储管理系统中的逻辑地址结构为:
页号P
页内位移W
它包含两部分,前一部分为页号P,后一部分为页内位移W.
解:本题中,每页2048字节,所以页内位移部分地址需要占据11个二进制位:逻辑地址空间最大为16页,所以页号部分地址需要占据4个二进制位。故逻辑地址至少应为15位。
由于内存共有8个存储块,在页式存储管理系统中,存储块大小与页面的大小相等,因此内存空间为16K。
12,答：分析：在段式存储管理系统中,为了实现从逻辑地址到物理地址的转换,系统将逻辑地址中的段号与段表长度进行比较,若段号超过了段表长度,则表示段号太大,于是产生越界中断信号;若未越界,则根据段表始址和段号计算出该段对应段表项的位置,从中读出该段在内存的起始地址,然后,再检查段内地址是否超过该段的段长。若超过则同样发出越界中断信号;若未越界,则将该段的起始地址与段内位移相加,从而得到了要访问的物理地址如下:
(1)由于第0段的内存始址为210,段长为500,故逻辑地址[0,430]是合法地址。逻辑地址[0,430]对应的物理地址为210+430=640。
(2)由于第1段的内存始址为2350,段长为20,故逻辑地址[1,10]是合法地址。逻辑地址[1,10]对应前物理地址为2350+10=2360。
(3)由于第2段起始地址为100,段长为90,所给逻辑地址[2,500]非法。
(4)由于第3段的内存始址为1350,段长为590,故逻辑地址[3,400]是合法地址。逻辑地址[3,400]对应的物理地址为1350+400=1750。
(5)由于第4段的内存始址为1938,段长为95,所给逻辑地址[4,112]非法。
(6)由于系统中不存在第5段,所给逻辑地址[5,32]非法。
13.答：分析：为描述方便起见,本题用"(分区首址,分区长度)"的形式描述系统中的分区。由题中所给条件可知,最初系统中只有一个空闲区,大小为512K,始址为0,即(0,512K)。
（1）采用首次适应算法,在完成了题目所给的系列申请及释放内存操作后,空闲分区表如下所示。
分区 大小 起始地址
0 30K 150K
1 20K 280K
2 112K 400K
(2)采用最佳适应算法,完成了题目所给的系列申请及释放内存操作后,空闲分区表如下:
分区 大小 起始地址
0 30K 150K
1 42K 470K
2 90K 210K
(3)如再申请100K空间,由上述结果可知,采用首次适应算法后剩下的空闲分区能满足这一申请要求:而采用最佳适应算法后剩下的空闲分区不能满足这一申请要求。
14.答:若页表存放在主存中,则要实现二次页面访问需两次访问主存,一次是访问页表,确定所存取页面的物理地址,第二次才根据该地址存取页面数据。
(1)由于页表存放在主存,因此CPU必须两次访问主存才能获得所需数据,所以实现一次页面访问的存取时间是,1.5×2=3微秒
(2)在系统增加了快表后,在快表中找到页表项的概率为85%,所以实现一次页面访问的存取时间为,0.85×1.5+（1一0.85）×2×1.5=1.725微秒
15.答：分析：在页式存储管理系统中,当进程要访问某个逻辑地址中的数据时,分页地址变换机构自动地将这辑地址分为页号和页内位移两部分,再以页号为索引去检索页表.在执行检索之前,先将页号与页表长度进行比较,如果页号超过了页表长度,则表示本次所访问的地址已超越进程的地址空间,系统产生地址越界中断.如果页访问合法,则由页表始址和页号计算出相应页表项的位置,从中得到该页的物理块号,并将它装入物理地址寄存器的块号部分。与此同时,再将逻辑地址寄存器中的页内地址直接送入物理地址寄存器的块内地址部分。这样便完成了从逻辑地址到物理地址的变换。
本题中,为了描述方便,设页号为P,页内位移为W,逻辑地址为A,页面大小为L,则：
P=int(A/L)
W=A mod L
（1）对于逻辑地址1011
P=int(1011/1024)=O
W=1011 mod 1O24=1011
查页表第0页在第2块,所以物理地址为3059。
（2）对于逻辑地址2148
P=int(2148/1024)=2
W=2148 mod 1024=100
查页表第2页在第1块,所以物理地址为1124。
（3）对于逻辑地址3000
P=int(3000/1094)=2
W=3000 mod 1024=952
查页表第2页在第1块,所以物理地址为1976。
（4）对于逻辑地址4000
P=int(4000/1024)=3
W=4000 mod 1024=928
查页表第3页在第6块,所以物理地址为7072。
（5）对于逻辑地址5012
P=int(5012/1024)=4
W=5012 mod 1024=916
因页号超过页表长度,该逻辑地址非法。
16.答：(1)页表所包括的项目应有:作业页号、在内存标志、存取方式、所在外存页号、所在内存页号、修改标志等(见表4.7).
在表4.7中,存取方式E表示可执行、R表示可读、W表示可写.
表4.7
作业页号
在内存标志
存取方式
外存页号
内存页号
修改标志
0
1
E
45
7
1
1
E
46
10
2
1
E
98
19
3
0 1
R
99
9
4
0 1 0
RW
100
9
(2)在把第9页淘汰之前,先检查其修改标志,若此页内存已发生过写操作,则说明与外存对应的页面副本内存不一致,必须重新送往外存,然后才能分配给常数区.
生调页问题.
17.答：(1)回答问题如下:
A.该计数器的初值为0。
B.每当一个新页与该计数器对应的页块相关时,计数器增值。
C.每当与该计数器对应页块相关的那些页之一不再使用时,计数器减值。
D.查找一个其计数器之值最小的页块,选择被替换的页。
(2)14次缺页中断。
(3)11次缺页中断。
18.答：应用上面的算法,各会出现的缺页中断次数如表4.4所示.
注意:所给定的页块初始均为空,因此,首次访问一页时就会发生缺页中断.
表4.4
页块号
LRU
FIFO
Optimal
1
20
20
20
2
17
18
15
3
15
16
11
4
10
14
8
5
8
12
7
6
7
9
7
7
7
7
7
19,解:(1)219+430=649
(2)2300+10=2310
(3)2300+11=2311
(4)非法地址访问,自陷人操作系统。
(5)1327+400=1727
(6)非法地址访问,自陷入操作系统,
20.答：各算法按缺页中断率排列如表4.3所示.
表4.3
次序
算法
有无Belady异态
1
Optimal
无
2
LRU
无
3
Second Chance
有
4
FIFO
有
21.答:在本题中,一页大小为2048字节,则逻辑地址4865的页号及页内位移为:
页号 P为：4865/2048=2
页内位移W为：4865-2048×2=769
然后,通过页表查知物理块号为6,将物理块号与逻辑地址中的页内位移拼接,形成物理地址,即:6×2048=13057其地址变幻过程如图5.13所示。
越界页表寄存器 逻辑地址页表始址
页表长度
2
769
页号 块号
0
2
1
4
2
6
3
8
2
769
22,答:一个进程在时间t的工作集可形式化地定义为:
W(t,h)={在时间t-h到t之间所访问的一串页面}
其中,h为工作集窗口尺寸。
由题目所给条件可知,t1时刻的工作集为:{1,2,3,6,7,8,9}
t2时刻的工作集为:{3,4}
5.1基本内容
5.1.1存储器管理的基本概念操作系统中的存储管理主要是指内存管理
1.存储管理研究的课题
（1）存储分配,研究存储共享和各种分配算法；
（2）地址再定位,研究各种地址变换机构及动态和静态再定位；
（3）存储保护,研究存储保护方法；
（4）存储扩充,研究虚拟存储器问题及各种调度方法。
2.存储分配方式
（1）直接分配方式：程序员在编写程序或编译程序对源程序编译时采用实际存储地址。采用这种方式,必须事先划定作业的可用空间,因此这种直接指定方式的存储分配,存储空间的利用率不高,对用户使用也不方便。
（2）静态分配方式：在将作业装入内存时才确定它们在主存中的位置。采用这种分配方式,在一个作业装入时必须分配其要求的全部存储量；如果没有足够的存储空间,就不能装入该作业。此外,作业一旦进入内存后,在整个运行过程中不能在内存中移动,也不能再申请内存空间。
（3）动态分配方式：作业在存储空间中的位置也是在装入时确定的；但在其执行过程中可根据需要申请附加的存储空间。当一个作业已占用的存储区不再需要时,可以归还给系统。同时,在作业运行过程中允许它在存储空间中移动。
目前,绝大多数计算机系统都采用静态或动态存储分配方式。
3.地址再定位
（1）几种空间
①名空间：源程序中由符号名组成的空间。
②逻辑地址空间：由逻辑地址组成的空间。所谓逻辑地址是以0为基地址顺序进行编址的相对地址。
③物理地址空间：是物理地址的集合。所谓物理地址,就是存储（内存）地址。
（2）地址的再定位一个逻辑地址空间的程序装入到物理地址空间时,由于两个空间不一致,需要进行地址变换或地址映射,即地址的再定位。地址再定位有静态和动态两种方式：
①静态再定位：在程序运行之前,由再定位程序完成。其优点是易实现,不需要硬件支持；缺点是只能在连续区域分配程序的存储空间；再定位后不能移动，多个用户很难共享内存中的同一程序。
②动态再定位：在程序执行期间,每次访问存储器之前进行；由硬件再定位寄存器存放程序的起始地址。优点是程序占用的内存空间动态可变,充分利用主存,若干用户可共享同一程序。但需要硬件支持且管理软件算法较复杂。
4.虚拟存储器的概念
（1)局部性原理程序局部性原理是指程序在执行时将呈现出局部性规律,即在一较短的时间内,程序的执行仅局限于某个部分,相应地，它所访问的存储空间也仅局限于某个区域。
①时间局部性：如果程序中的某条指令一旦执行,则不久以后该指令可能再次执行；如果某个数据被访问,则不久以后该数据可能被再次访问。产生时间局部性的典型原因是由于程序中存在着大量的循环操作。
②空间局部性。一旦程序访问了某个存储单元,则不久以后,其附近的存储单元也将被访问,即程序在一段时间内所访问的地址,可能集中在一定的范围内,其典型情况便是程序的顺序执行。
（2)虚拟存储器：虚拟存储器是利用操作系统产生的一个其容量比主存大得多的存储器,实际上是一个地址空间。
基于局部性原理,应用程序在运行之前并不必全部装入内存,仅须将当前要运行到的那部分程序和数据装入内存便可启动程序的运行,其余部分仍驻留在外存上；当要执行的指令或访问的数据不在内存时,再由OS自动通过请求调入功能将它们调入内存,以使程序能继续执行:如果此时内存己满,则还需通过置换功能,将内存中暂时不用的程序或数据调至盘上,腾出足够的内存空间后,再将要访问的程序或数据调入内存,使程序继续执行。
这样,便可使一个大的用户程序能在较小的内存空间中运行:也可在内存中同时装入更多的进程使它们并发执行。从用户的角度看,该系统具有的内存容量比实际的内存容量大得多,我们将这种具有请求调入功能和置换功能、能从逻辑上对内存容量加以扩充的存储器系统称为虚拟存储器。
（3）实现虚拟存储器的物质基础：
①一定容量的主存；
②大容量的辅存
③ 动态地址变换机构。
虚存的容量受字长、速度(传送〉、使用频率的限制,其最大容量由计算机系统的地址机构确定。实现虚存的方案有：①分页式虚存(是请求分页)；②分段式虚存；③〉段页式虚存。
（4）虚拟存储器的主要特征
① 多次性：与常规存储管理的"一次性"相反,虚拟存储器将一个作业分成多次调入内存。多次性是虚拟存储器最重要的特征。
②对换性。与常规存储管理的"驻留性"相反,在作业运行期间,虚拟存储器允许将那些暂不使用的程序或数据从内存调至对换区,待以后需要时再调入内存,从而能有效地提高内存利用率。
③虚拟性。虚拟存储器对内存的扩充是逻辑上的,用户所看到的大容量只是一种感觉,并不实际存在,因此是虚的。虚拟性是实现虚拟存储器的目标。
5.1.2早期的存储管理
1.单一连续分配
(1)每次只有一个用户作业使用,它占用了全部资源(包括主存)。
(2)系统中的存储器被分成三个连续区域：①操作系统使用区域；②作业〈用户程序〉区域；③未用区域。
早期的存储管理有以下特点:
①优点：简单,易于实现。
②缺点:仅适用于单道程序,处理机和主存不能充分利用。
2.分区分配为满足多道程序设计和多用户系统的开发,把内存按不同的方法分区。
（1）固定式分区在系统生成时,将内存划分为若干个分区,大小可以不等,但事先固定,以后也不能改变。
特点：可以使多个作业共享内存,但内存利用不充分,浪费很大,有“内零头”。
（2）可变式分区即动态分区可变式分区需了解的几个概念：
①空白区：一块连续的未使用的内存区。
②空白区表：用于对空白区管理的目录表。
③碎片:一块小的不能使用的空白区。
④可变式分区有两种不同选择:其一是分区数目固定,其各自的大小可变；其二是允许分区的数目和大小都是可变的。
分配和释放分区的算法：
①最佳适应算法：空白区表是按空白区的容量,从小到大顺序排列。这种算法优点是查找速度较快,准确合理。
②最差适应算法:空白区表是按空白区的容量,从大到小顺序排列。这种算法优点是一次比较就可判定能否满足要求F分配后剩余区仍可使用。
③最先适应算法：空白区表是按空白区的起始地址,由小到大顺序排列。这种算法优点是在释放内存时,若有相邻空白区,可合并成一个较大区。在此算法中应尽量使用低地址部分,高地址部分留有较多、较大空白区。
（3）可再定位分区分配可再定位分区分配即浮动分区分配,是解决碎片问题的简单而有效的方法。其基本思想是:移动所有被分配的分区,使之成为一个连续区域,而留下一个较大的空白区。移动(靠拢〉时机应选择在以下时间:①某作业完成时；②某作业请求分区时；
可再定位分区分配的特点:优点是碎片可集中使用,内存利用率高；缺点是需要硬件支持,移动会降低速度。
（4）分区的保护措施
①界地址寄存器:下界寄存器存放作业分区的起始地址,上界寄存器存放下一分区的起始地址。每次寻址和访问时,先与这两个寄存器的内容进行比较,以实现对分区的保护。
②基址寄存器和限长寄存器:基址寄存器存放作业分区的起始地址,限长寄存器存放作业的最大偏移量〈长度〉。在作业运行过程中,在访问存储器时所计算出的存储地址如果超过限长,则发越界中断信号。
5.1.3分页存储管理
1.有关分页存储管理的几个概念
(1)页面：把逻辑地址空间划分为一些相等的片,这些相等的片称为页面(或页〉。页的大小通常在512B到4KB范围内,通常是2的幂。
(2)块：把物理地址空间划分为同页面同样大小的片,称之为块,也称存储块或页框。
(3)页表（PMT）：也称页面变换表。每个作业一张,该作业有多少页面就有多少表目,表目内记录对应的存储块号。它包含两部分,前一部分为页号P,后一部分为页内位移W。上述地址结构中,两部分构成的地址长度为16位。其中0-9位为页内地址,即每页大小为1K;10-15位为页号,地址空间最多允许有64页。
页号P
页内位移量W
15 10 9 0
2.地址变换机构
(1)动态地址变换机构(DAT)用页面变换地址寄存器指出页表始址。
(2)高速页面变换寄存器用硬件的高速寄存器来实现作业地址空间到物理地址空间的变换。
(3)联想存储器,也称快表,利用一组高速寄存器,连同管理它们的硬件,构成一个容量较小的存储器,称为联想存储器。联想存储器用于存放已在运行的作业的当前最常用的页号和相应的块号,它具有并行查询能力。
3.分页存储管理的实现分页原理的主要内容是:将逻辑地址空间划分成大小相同的页面,将物理地址空间划分成与页面同样大小的块,利用页面变换表（PMT）,建立页与块的对应关系,通过PMT实现地址变换。
用户作业 页 表 内 存
0页
1页
2页
┇
N页
0
2
1
4
2
7
┇
┇
4.地址变换机构
(1)动态地址变换机构(DAT)用页面变换地址寄存器指出页表始址。
(2)高速页面变换寄存器用硬件的高速寄存器来实现作业地址空间到物理地址空间的变换。
（3）所需的表格：作业表(JT),全系统一张；存储分块表（MBT）,全系统一张；页面变换表（PMT）,每个作业一张。由操作系统对以上表格进行管理。
（3）地址变换过程当进程要访问某个逻辑地址中的数据时,分页地址变换机构自动地将逻辑地址分为页号和页内位移两部分,再以页号为索引去检索页表。在执行检索之前,先将页号与页表长度进行比较,如果页号超过了页表长度,则表示本次所访问的地址已超越进程的地址空间,系统产生地址越界中断。如果页访问合法,则由页表起始地址和页号计算出相应页表项的位置,从中得到该页的物理块号。最后,将块号与逻辑地址中的页内位移拼接在一起,就形成了访问主存的物理地址。图5.4给出了页式存储管理系统中的地址变换过程。
越届中断页表寄存器 逻辑地址
页号 块号
在图5.4中,假定页面大小为lk字节,则逻辑地址2500(=2×1024+452〉的页号为2,页内地址为452。由页表可知第2页对应的物理块号为8。将块号8与页内地址452拼接(8×1024+452=8644)得到物理地址为8644。
(4)联想存储器：从上面介绍的地址变换过程可知,若页表全部放在主存,则要存取一个数据或一条指令至少要访问两次主存,一次是访问页表,确定所存取的数据或指令的物理地址,第二次才根据该地址存取数据或指令。显然,这种方法比通常执行指令的速度慢了一倍。为了提高查表速度,可在地址变换机构中增设一个具有并行查找能力的高速缓冲存储器(又称联想存储器或快表),将页表放在这个高速缓冲存储器中。高速缓冲存储器一般是由半导体存储器实现的,其工作周期与CPU的周期大致相同,但其造价较高。为了降低成本,通常是在快表中存放正在运行作业当前访问的那些页表项,页表的其余部分仍然存放在内存中。
引入快表以后的地址变换过程为:当CPU给出逻辑地址后,地址变换机构自动将此页号与联想存储器中的所有页号进行并行比较,若其中有与此匹配的页号,则表示所要访问的页表项在联想存储器中,于是取出该页对应的块号,与页内地址拼接形成物理地址。若联想存储器中的所有页号与所查找页号不匹配,则还需再访问主存中的页表。实际上,这两者的查找是同时进行的,一旦在联想存储器中发现了要查找的页号,则立即停止内存中页表的查找。如果地址变换是通过查找内存中的页表完成的,则还应将这次所查到的页表项存入联想存储器中,若联想存储器己满,则必须按某种原则淘汰一个表项以腾出位置。
采用这种方案,只要使用8—16个表项的联想存储器,就能使从联想存储器中找到所需页号的概率达到90%左右。
5.1.4请求分页存储管理在分页的基础上增加请求调页功能和页面置换功能,便形成了能支持虚拟存储器功能的请求分页系统。
1.请求分页的基本原理请求分页系统对地址空间和内存空间的管理采用与基本分页系统相同的方式,但它只要求将作业的部分页面装入内存,便可开始运行作业,作业的其余部分被存放在盘中。
由于这种管理方案在一个作业运行之前不要求将作业的整个地址空间调入主存,因此在作业的运行过程中,必然会出现要访问的页不在主存的情况。那么如何发现和处理这种情况就是请求页式存储管理必须解决的两个基本问题。
为了解决发现所访问页面不在主存的问题,必须对页表表目进行扩充。扩充后的页表表目结构如下所示:
页号
块号
状态位
访问字段
修改位
外存地址
在请求分页系统中,当进程需要访问某条指令或某个数据时,硬件地址变换机构将根据逻辑地址中的页号去检索内存中的页表,并根据相应页表项的状态位，来判断该指令或数据所在的页是否已装入内存。若己装入内存,则可立即从页表项中得到该页的内存块号,并与页内地址拼接形成指令或数据的物理地址,同时还需修改页表项中的访问位对于写指令,则还需将修改位置成"1"。若所要访问的页还未调入内存,便产生一缺页中断,此时,上述访问缺页的作业将被中断,控制将转向缺页中断处理程序。
缺页中断处理程序用来完成页面的调入工作。若系统中仍有空闲的内存块,则只需根据页表项中的外存地址将所缺的页装入内存,然后修改页表项中的存在位和内存块号即可；否则,若系统中无空闲的内存块,则需要根据置换算法淘汰内存中的某一页,对已被修改过的页先写盘,然后再将所缺的页调入内存。
2.内存分配策略和置换策略在请求分页系统中,可采取两种内存分配策略,即固定分配和可变分配。在进行置换时,也可采取两种策略,即全局置换和局部置换。于是,可组合出以下三种适用的策略:
(1)固定分配局部置换策略。采用该策略时,为进程分配的物理块数目,在进程的整个运行期间都固定不变,若进程因调入页面而需要换出某个页面,则只能换出它自己的内存页面。由于进程是动态的,即使在运行之前为它分配了适当数目的内存块,.在采用固定分配局部置换策略时,进程在运行过程中仍然可能会因内存块太少而频繁缺页,或者因内存块太多而浪费空间。
(2)可变分配全局置换策略。采用该策略时,系统先为每个进程分配一定数目的物理块当进程发生缺页时,若系统中有雪闲的物理块,则为其分配一个物理块并装入缺页；若系统中己没有雪闲的物理块,则从内存中选择一页换出,再装入缺页,被换出的页可以是系统中任一进程的页,这样,自然又会使那个进程的物理块减少,进而使其缺页率增加。
(3)可变分配局部置换策略。在采用该策略时,为每个进程分配一定数目的物理块后；若某个进程发生缺页,则只能将自己的某个内存页换出。如果进程在运行中频繁发生缺页中断,则系统须为该进程分配若干附加的物理块,直至其缺页率减少到适当程度为止；反之,若一个进程的缺页率特别低,则可适当减少分配给它的物理块,但不应引起其缺页率的明显增加。因此,可变分配局部置换策略可获得较高的内存空间利用率,同时又能保证每个进程有较低的缺页率。
3.调页策略
（1)请求调页策略：请求调页策略是指当进程在运行中需要访问某部分程序和数据时,若发现其所在的页面不在内存,便立刻发出缺页中断,请求OS将所需页面调入内存。单纯采用请求调页策略的系统,在进程刚启动时,缺页中断会发生得比较频繁,由于程序访问的局部性,一段时间后,缺页率会降至较低。对一个被整体换出的进程重新开始执行时;也具有上述情况。
（2)预调页策略：预调页策略是指将那些预计在不久之后便会访问到的几个页面,预先调入内存。如果这些页被存放在外存的一个连续区域中,则通过预调页将它们一次调入内存将比一次调入一页要高效得多。但预测哪些页面在不久之后便会被访问到是十分困难的,其成功率只有50%。故预调页策略主要用于进程首次调入和整体换入时,由程序员或系统指出应该先调入哪些页面,这样,可使刚开始执行的进程的缺页率明显降低。
（3）抖动:从主存中刚刚移走某页面后,根据请求马上又调入该页。这种反复进行入页和出页的现象称为"抖动",也叫系统颠簸。它会浪费大量的处理机时间,应尽可能避免。产生抖动的直接原因是页面置换算法选取不当。
4.页面置换算法
(1)最佳置换算法：置换策略是从主存中移出永远不再需要的页面,若无这样的页面存在,则应选择最长时间不需要访问的页面。最佳置换算法本身不是一种实际的方法,因为页面访问的未来顺序是不知道的。但是可将其他实用方法与之比较来评价这些方法的优劣,所以最佳置换算法具有理论上的意义。
(2)先进先出算法(FIFO)：总是先淘汰那些驻留在主存时间最长的页面。
(3)最近最久未用置换算法(LRU)：当需要置换一页时,选择在最近一段时间最久未用的页予以淘汰。
(4)LRU近似算法：在存储分块表MBT(或页表PMT)中设一"引用位",当页被访问时,该位由硬件自动置为"1",而由页面管理软件周期地把所有引用位置为"0"。在时间周期T内,根据引用位的状态来判断各页面最近的使用情况。
5.性能分析
(1)本方案消除了对主存容量的限制,能使更多的作业按多道程序同时执行,提高了系统效率。但应尽量减少缺页中断次数。
(2)为了减少缺页中断次数,应从程序设计的质量、页面的大小、主存的容量以及页面置换算法等几方面来考虑。
5.评价
(1)请求分页存储管理保留了分页存储管理的全部优点,特别是它解决了消除碎片的问题。另外,它还有如下优点:提供了大容量的多个虚拟存储器；作业地址空间不再受实存容量的限制；更有效地利用主存；有利于运行多道程序；提高了系统效率,方便了用户,特别是大作业用户。
(2)请求分页存储管理的缺点是：要求有相应的硬件支持,从而增加了成本。如动态地址变换机构、快表、缺页中断的产生等都要求有相应的硬件支持。缺页中断增加了处理机时间的开销,如页表的建立与管理、缺页中断处理等；页面淘汰算法如选择不当,有可能产生抖动现象，为防止抖动,会增加系统的复杂性；虽然消除了碎片,但每个进程的最后一页内总有一部分空间得不到利用。另外,页式存储管理系统中作业的地址空间仍受主存实际容量的限制。
5.1.5分段存储管理
1.分段原理一个用户作业的程序按其逻辑结构,可由用户划分为若干段。这些段中的每一段在逻辑上都是完整的,每一段都是一组逻辑信息,都有自己的名字,且都有一段连续的地址空间。可以用类似于分页管理用过的地址变换机构,实现分段管理的地址变换,只是采用的是段变换表SMT。地址变换是在作业执行过程中由硬件自动完成的。
2.段变换表SMT
分段存储管理系统中,作业地址空间的每一单元采用二维地址(S,W),其中S为段号,W为段内地址或位移量。
段式存储管理系统也可和请求页式存储管理系统一样,为用户提供一个比主存可用空间大得多的虚拟存储器。同样,虚拟存储器的实际容量由计算机的地址结构确定。
在段式虚拟存储系统中,一个作业各分段的副本都保存在辅存中,当其运行时,首先把当前需要的一段或几段调入主存,其他段在需要时再调入。为此,应对段表表目进行扩充,扩充后的内容如下,
段号
段长
主存始址
访问位
改变位
增补位
状态位
外存地址
段号、段长和内存始址三个信息是进行地址变换所必须的,当段在内存时,地址变换过程与段式存储管理相同:当段不在内存时,先将该段调入内存再进行地址变换。新增加的状态位用于标识此段是否在主存中,访问字段记录本段在一段时间内被访问的次数或最近已有多长时间未被访问,修改位表示该段在调入内存后是否被修改过,外存地址指出该段在外存上的地址。为了进行存储保护,还可以增加一个存取控制字段。
当被访问的段不在主存中时,产生一个缺段中断信号。操作系统处理该中断后,在主存中查找是否有足够大的分区存放该段。如没有这样的分区,则检查未分配分区的总和,确定是否需要对分区进行拼接,或者调出一个或几个分段后再装入所需要的分段。
3.段的共享与保护在段式系统中,分段的共享是通过两个作业的段表中相应表目都指向被共享过程的同一个物理副本来实现的。
与页式管理类似,段式管理的保护主要有两种。一种是地址越界保护法,另一种是存取控制保护法。
4.段式管理的特点
（1)分段存储管理的优点是：消除了碎片；提供了大容量的虚存；可动态增加段长；便于动态装入和连接；可共享一个程序;便于实现存储保护。
(2)分段存储管理的缺点是：地址变换和靠拢需CPU时间；表格需占存储空间；在辅存上管理可变长度的段较困难,段的最大长度受实存限制;也会出现系统抖动现象。
5、分页和分段存储管理的比较分页系统、分段系统有许多相似之处,比如:都采用离散分配方式来提高内存利用率,都要通过地址变换机构来实现地址变换；但在概念上两者是完全不同的,它们的主要区别表现在以下三个方面:
①分页是一个单一的线性地址空间,分段作业地址空间是二维的。
②"页"是信息的物理单位,大小固定，分页活动用户看不见,分页的目的是为了提高内存的利用率。而"段"是信息的逻辑单位,其长度不定，分段是用户可见的活动，分段的目的是为了能更好地满足用户的需要。。
③分页管理实现单段式虚拟存储系统,而分段存储管理实现多段式虚拟存储系统。
4.1.6段页式存储管理为了既能像分页系统那样有效地利用内存；又能像分段系统那样满足用户多方面的需要,操作系统中又引入了段页式存储管理方式。
1.基本思想
(1)用分段方法来分配和管理虚拟存储器。
(2)用分页方法来分配和管理实存储器。
段页式存储管理方式是分页和分段管理的结合,它先将地址空间中的用户程序分成若干个段,再将每个段分成若干个页。而内存空间则仍采用页式管理主式,即将内存分成与页同样大小的块,并以块为单位来进行内存的分配。
2.实现原理
(1)在段页存储管理中,地址空间还是二维的,每个逻辑地址包括段号和段内地址两部分,段内地址又将被地址变换机构根据页面大小自动分成段内页号和页内地址。因此，处理机给出的有效地址被划分为三部分:段号、页号和页内地址，即（S,P,W）。
（2）程序的分段可由程序员或编译程序按信息的逻辑结构来划分,而分页与程序员无关,它是由操作系统自动完成的。为了实现地址变换,系统必须为每个进程建立一张段表,并为每个分段建立一张页表,段表项给出了每个分段所对应的页表的内存始址和长度,页表项则给出了页所对应的内存块号二在进行地址变换时,首先根据段表寄存器中的段表始址和逻辑地址中的段号找到对应的段表项,从中获得该段的页表始址:然后再利用页表始址和逻辑地址中的段内页号来获得对应的页表项,从中获得该页的内存块号::由内存块号与页内地址拼接形成物理地址。
（3）由于段表和页表都存放在内存中,每存取一条指令或一个数据都需访问三次内存,故可在地址变换机构中增设快表,用来存放当前被频繁访问的页面所对应的段号、段内页号和物理块号等信息,以减少访问内存的次数,提高指令执行的速度。
从逻辑地址到物理地址的变换过程需要三次访问主存,一次是访问段表,一次是访问页表,再一次是访问主存物理地址。
3.评价
（1）段页式存储管理的优点是：保留了分段和请求分页存储管理的全部优点。其主要优点是提供了大量的虚存空间,能有效地利用主存,为组织多道程序运行提供了方便。
(2)段页式存储管理的缺点是：增加了硬件成本、系统的复杂性和管理上的开销,页面使用不充分；各种表格占用主存空间；有系统抖动的危险。
4.2重点难点学习提示本章的目的是了解各种存储器管理的方式和它们的实现方法,为此应对以下几个重点、难点问题作认真的学习,并切实掌握其中的内容。
1.重定位的基本概念重定位的实质是地址变换,它将作业地址空间中的逻辑地址转换为主存空间中的物理地址,从而保证作业能够正常执行。对下述两个方面的内容要有较好的理解:
(1)为什么要引入重定位,由重定位装入程序在装入作业时一次性完成的静态重定位适用于何种场合,它有何优缺点。
(2)动态重定位是为了解决什么问题而引入的,在连续分配方式、分页系统和分段系统中,分别是如何实现动态重定位的。
2.动态分区分配方式动态分区分配方式是一种曾经广为流行的内存分配方式,至今仍在内存分配中占有一席之地。应了解下述几个问题:
(1)如何提高内存利用率。动态分区分配方式是根据进程的实际需要,动态地为进程分配内存,造成动态分区分配方式内存空间浪费的主要原因是什么,可通过什么办法加以解决。
(2)分配算法。动态分区分配方式可采用空闲分区表或空闲分区链来描述分区的情况,并可采用首次适应、最佳适应等算法来进行内存的分配和回收,读者应了解在采用不同的分配算法时,系统是如何组织空闲分区表或空闲分区链的,它们又是如何进行分区的分配和回收的。
(3)如何进行分区的保护。该方式可利用界限寄存器或保护键来进行分区的保护,应了解它们分别是如何进行越界检查的；在检查到越界情况时,将由谁负责进行具体的处理。
3.分页和分段存储管理方式分页和分段存储管理方式不仅能有效地提高内存雪间的使用效率,而且是实现虚拟存储器的基础。应对下面几个方面的内容有较深刻的理解和掌握：
(1)分页存储管理方式。应了解是在什么推动力的作用下,使内存管理由动态分区分配方式发展为分页存储管理方式;分页系统是如何将地址空间中的作业划分为若干个页,它又是如何进行内存分配的。
(2)分页系统的地址转换。应掌握分页系统逻辑地址的结构,为了进行逻辑地址到物理地址的转换,分页系统必须为每个作业配置什么样的数据结构并提供哪些硬件支持,为什么引入快表可加快分页系统存取指令和数据的速度。
(3)分段存储管理方式。应了解由分页发展为分段,并进一步发展为段页式存储管理方式的主要推动力是什么,分段和段页式系统是如何管理作业的地址空间和内存空间的,它们的地址变换是如何完成的,并应注意对分段系统和分页系统加以比较。
(4)信息的共享和保护。分页系统和分段系统都可以实现信息的共享,并可通过越界检查和存取权限对信息进行保护。应了解为什么分段系统比分页系统更容易实现信息的共享和保护:对代码页(段)的共享有什么特别的要求,原因是什么。
4.虚拟存储器的基本概念虚拟存储管理技术己被广泛地应用于现代操作系统中,它的主要功能是从逻辑上扩充内存的容量。由于它是存储器管理中的重点部分,应对下述几个问题有较清楚和深入的理解:
(1)为什么要引入虚拟存储器。引入虚拟存储器主要是为了解决内存空间不足的问题,应了解虚拟存储器是如何扩充内存容量的,为什么一次性和驻留性并非是程序运行所必需的条件,或者说,为什么只需将部分程序和数据装入内存,便能完成整个程序的。
(2)虚拟存储器具有哪些特征。虚拟存储器具有多次性、对换性和虚拟性的特征,必须了解每种特征的具体含义,以及它们相互之间存在着什么样的关系,它们与离散分配之间又存在着什么样的关系。
(3)实现虚拟存储器的关键技术是什么。实现虚拟存储器的的关键是请求调页(段)技术和页(段)置换技术,应清楚地了解这些技术的实现需要得到哪些硬件支持和软件支持。
5.请求分页系统的基本原理请求分页系统是目前最常用的一种实现虚拟存储器的方式,它只需将作业当前要用到的部分页面装入内存,便可启动作业的运行。应对下述内容有较深刻的理解和掌握,
(1)页表机制。为实现虚拟存储器,必须扩充页表工页的内容,应了解除了内存块号和存取权限字段以外,页表中还必须增加哪些字段,为什么要增加这些字段。
(2)地址变换过程。请求分页系统的地址变换也必须通过地址变换机构进行,应了解请求分页系统的地址变换机构,是在基本分页系统的地址变换机构的基础上增加了哪些功能而形成的。
(3)页面置换算法。页面置换算法即选择换出页面的算法,它直接影响到系统的性能。应了解一些常用的页面置换算法,并进一步了解为什么LRU算法具有比较好的性能,它的主要缺点是什么,可用什么方法实现LRU近似算法。
5.3典型问题分析和解答
1.存储器管理的基本任务是为多道程序的并发执行提供良好的存储器环境。"良好的存储器环境"应包含哪几个方面?
答:存储器管理的基本任务是为多道程序的并发运行提供良好的存储器环境。它包括以下内容:
(1)能让每道程序"各得其所",并在不受干扰的环境中运行号还可以使用户从存储空间的分配、保护等繁琐事务中解脱出来。
(2)向用户提供更大的存储空间,使更多的作业能同时投入运行z或使更大的作业能在与较小的内存空间中运行。
(3)为用户对信息的访问、保护、共享以及动态链接等方面提供方便。
(4)能使存储器有较高的利用率。
2.何谓虚拟存储器?举一例说明操作系统是如何实现虚拟内存的。
答：在操作系统中,通过一些硬件和软件的措施为用户提供了一个其容量比实际主存大得多的存储器,称为虚拟存储器。
操作系统要实现虚拟内存,必须把主存和辅存统一管理起来,即大作业程序在执行时,有一部分地址空间在主存,另一部分在辅存,当访问的信息不在主存时,由操作系统将其调入主存并实现自动覆盖功能,使用户在编写程序时不再受主存容量的限制。
例如在请求分页存储管理系统中,用户作业的所有页面并不一定都在实存,在作业运行过程中再请求调入所用的虚页。为了实现从逻辑地址空间到物理地址空间的变换,在硬件上必须提供一套地址变换机构,动态地址变换机构自动地将所有的逻辑地址划分为页号和页内地址两部分,并利用页表将页号代之以块号,把块号和页内地址拼接就得到了内存的物理地址,从而实现了虚拟存储器。
3.什么叫重定位? 采用内存分区管理时,如何实现程序运行时的动态重定位?
答：所谓地址重定位,就是当一个程序装入到与其地址空间不一致的存储空间而进行的地址变换过程,即将地址空间给出的逻辑地址映射到内存的物理地址上。地址重定位有静态重定位和动态重定位两种方式。
采用内存分区管理时,在硬件上设置一个"重定位寄存器"可以实现程序运行时的动态重定位。这种情况下地址重定位是在程序执行期间由地址变换机构动态实现的,主要的计算依据是:
物理地址=逻辑地址+重定位寄存器的内容
4.某系统采用动态分区分配方式管理内存,内存空间为640K,高端40K用来存放操作系统。在内存分配时,系统优先使用空闲区低端的空间。对下列的请求序列:作业1申请130K、作业2申请6OK、作业3申请100K、作业2释放6OK、作业4申请200K、作业3释放l00k、作业1释放130K、作业5申请140K、作业6申请6OK、作业7申请5OK、作业6释放6OK,请分别画图表示出使用首次适应算法和最佳适应算法进行内存分配和回收后内存的实际使用情况。
分析：首次适应算法将空闲区按起始地址递增的次序拉链,而最佳适应算法则将空闲区按分区大小递增的次序拉链。在分配时飞它们都是从链首开始顺序查找,直至找到一个足够大的空闲分区为止,然后按作业大小从该分区中划出一块内存空间分配给请求者,余下的分区(如果有的话)仍按上述原则留在空闲分区链中;而在释放时,则需分别按地址递增或大小递增的次序将空闲分区插入空闲分区链,并都需要进行空闲分区的合并。
答：使用首次适应算法和最佳适应算法进行上述内存的分配和回收后，内存的实际使用情况如下图所示。
5.在请求分页存储管理系统中,试问:
（1）局部与全局页面淘汰算法有何区别? 为什么在多道系统中常用局部页面淘汰算法?
（2）试设计一个LRU淘汰算法的近似算法(指出所需的硬件支持、数据结构及软件处理流程)。
答：（1）局部页面置换只在当前进程分配的页面中选择一个被置换的页面:全局页面置换从整个存储器用户区的所有页面中选择一个被置换的页面。
在多道程序系统中,采用局部页面置换策略进行页面置换,即使某个进程出现了抖动现象,不致引起其他进程也产生抖动,-可以将抖动局限在较小的范围内。
（2）可以在MBT表中增设一个"引用位",当MBT表中的页被访问时"引用位"置1,在MBT表中再增设一个指针域,用于记录进入内存的页面顺序,另设一个替换指针指向最近刚刚进入内存的页面。可以根据引用位的状态来判别各页面最近的使用情况,当需要置换一页时,选择其引用位为0的页淘汰。该算法的程序流程图如图2.6所示:
N
Y
6.某系统采用页式存储管理策略,拥有逻辑空间32页,每页2K,拥有物理空间1M。
(1)写出逻辑地址的格式。
(2)若不考虑访问权限等,进程的页表有多少项?每项至少有多少位?
(3)如果物理空间减少一半,页表结构应相应作怎样的改变?
答:(1)该系统拥有逻辑空间32页,故逻辑地址中页号必须用5位来描述;而每页为2K,因此,页内地址必须用11位来描述,这样可得到它的逻辑地址格式如下:
15 11 10 0
页 号
页 内 地 址
(2)每个进程最多有32个页面,因此,进程的页表项最多为32项；若不考虑访问权限等,则页表项中只需给出页所对应的物理块块号,1M的物理空间可分成29个内存块,故每个页表项至少有9位。
（3）如果物理空间减少一半,则页表中页表项数仍不变,但每项的长度可减少1位。
7.假定某页式管理系统,主存为64KB,分成16块,块号为0,1,2,3,4,…,15。设某作业有4页,其页号为0,1,2,3,被分别装入主存的2,4,1,6块。试问:
(1)该作业的总长度是多少字节?(按十进制)
(2)写出该作业每一页在主存中的起始地址。
(3)若给出逻辑地址[0,100]、[1,50]、[2,0]、[3,60],请计算出相应的内存地址。
答:(1)每块的长度=64KB/16=4KB
因为块的大小与页面的大小相等,所以每页为4KB。因此,作业的总长度为4KB×4=16KB。
(2)因为页号为0,1,2,3的页分别被装入主存2,4,1,6块中,即PMT为:
页号
块号
0
2
1
4
2
1
3
6
所以该作业的：
第0页在主存中的起始地址为4K×2=8K
第1页在主存中的起始地址为4K×4=16K
第2页在主存中的起始地址为4K×1=4K
第3页在主存中的起始地址为4K×6=24K题
（3）逻辑地址[0,100]的内存地址为4K×2+100=8192+100=8292
逻辑地址[1,50]的内存地址为4K×4+50=16384+50=16434
逻辑地址[2,0]的内存地址为4K×1+0=4096
逻辑地址[3,60]的内存地址为4K×6+60=24K+60=24576+60=24636
8.对于下表所示的段表,请将逻辑地址(0,137),(1,4000),(2,3600),(5,230)转换成物理地址。
段号
内存地址
段 长
0
50K
10K
1
60K
3K
2
70K
5K
3
120K
8K
4
150K
4K
分析：在分段系统中进行地址转换时,地址变换机构首先将逻辑地址中的段号与段表长度作比较,如果段号超长,则产生越界中断;否则使以段号为索引去检索段表,从中得到段在内存的始址和段长;然后再将逻辑地址中的段内地址与段长作比较,若不越界,则由段的始址与段内地址相加,形成物理地址。
答:(1)段号0小于段表长5,故段号合法:由段表的第0项可获得段的内存始址为5OK,段长为1OK由于段内地址137,小于段长1OK,故段内地址也是合法的,因此可得出对应的物理地址为5OK+137=51337。
(2)段号1小于段表长,故段号合法:由段表的第1项可获得段的内存始址为60K,段长为3K;经检查,段内地址4000超过段长3K,因此产生越界中断。
(3)段号2小于段表长,故段号合法:由段表的第2项可获得段的内存始址为7OK,段长为5K;故段内地址3600也合法。因此,可得出对应的物理地址为7OK+3600=75280。
(4)段号5等于段表长,故段号不合法,产生越界中断。
9.己知页面走向为1、2、1、3、1、2、4、2、1、3、4,且开始执行时主存中没有页面。若只给该作业分配2个物理块,当采用FIFO页面淘汰算法时缺页率为多少?假定现有一种淘汰算法,该算法淘汰页面的策略为当需要淘汰页面时,就把刚使用过的页面作为淘汰对象,试问就相同的页面走向,其缺页率又为多少?
分析：在进行内存访问时,若所访问的页已在主存,则称此次访问成功;若所访问的页不在主存,则称此次访问失败,并产生缺页中断.若程序P在运行过程中访问页面的总次数为s,其中产生缺页中断的访问次数为f,则其缺页率为:f/s.
解:根据所给页面走向,采用FIFO淘汰算法的页面置换情况如下:
页面走向 1 2 1 3 1 2 4 2 1 3 4
物理块1 1 1 3 3 2 2 1 1 4
物理块2 2 2 1 1 4 4 3 3
缺页 缺 缺 缺 缺 缺 缺 缺 缺 缺
从上述页面置换图可以看出:页面引用次数为11次,缺页次数为9次,所以缺页率为9/11。
若采用后一种页面淘汰策略,其页面置换情况如下：
页面走向 1 2 1 3 1 2 4 2 1 3 4
物理块1 1 1 3 1 1 1 3 4
物理块2 2 2 2 4 2 2 2
缺页 缺 缺 缺 缺 缺 缺 缺 缺
从上述页面置换图可以看出：引用次数为11次,缺页次数为8次,所以缺页率为8/11。
10.考虑一个请求调页系统,它采用全局置换策略和平均分配内存块的算法(即若有m个内存块和n个进程,则每个进程分得m/n个内存块)。如果在该系统中测得如下的CPU和对换盘利用率,请问能否用增加多道程序的度数来增加CPU的利用率?为什么?
(1)CPU的利用率为13%,盘利用率为97%:
(2)CPU的利用率为87%,盘利用率为3%:
(3)CPU的利用率为13%,盘利用率为3%。
答:(1)这种情况表示系统在进行频繁的置换,以致绝大部分时间被花在页面置换上,此时,增加多道程序的度数会进一步增加缺页率,使系统性能进一步恶化,所以,不能用增加多道程序的度数来增加CPU的利用率。
(2)在这种情况下,CPU的利用率已相当高,但对换盘的利用率却相当低,这表示运行进程的缺页率很低,可以适当增加多道程序的度数来增加CPU的利用率。
(3)在这种情况下,CPU的利用率相当低,而且对换盘的利用率也非常低,表示内存中可运行的程序数不足,此时,应该增加多道程序的度数来增加CPU的利用率。
11.假如一个程序的段表如下所示,其中存在位为1表示段在内存,存取控制字段中W表示可写,R表示可读,E表示可执行。对下面的指令,在执行时会产生什么样的结果?
段号
存在位
内存始址
段长
存取控制
其他信息
0
0
500
100
W
1
1
1000
30
R
2
1
3000
200
E
3
1
8000
80
R
4
0
5000
40
R
(1)STORE R1,[0,70]
(2)STORE R1,[1,20]
(3)LOAD R1,[3,20]
(4)LOAD R1,[3,100]
(5)JMP [2,100]
分析：在执行指令的过程中,如果指令中包含有地址部分,则先必须进行逻辑地址到物理地址的转换。在地址转换过程中还要进行越界检查和存取控制权限的检查,只有在地址不越界、访问方式也合法,并形成物理地址后,才能去完成指令规定的操作。
答:(1)指令STORE R1,[0,70]。从段表的第0项可读出第0段的存在位为0,表示相应段未装入内存,因此地址变换机构将产生一缺段中断,以请求OS将其调入内存。
（2)指令STORE R1,[1，20]。从段表的第1项可以看出,虽然指令中的逻辑地址合法,段也已在内存,但本指令对内存的访问方式(写)与存取控制字段(只读)不符,故硬件将产生保护性中断信号。
(3)指令LOAD R1,[3,20]。从段表的的第3项可读出第3段的存在位为1,内存始址为8000,段长为80,存取控制为R,因此,逻辑地址合法,访问方式也合法,形成物理地址8020后,指令将把该单元的内容读到寄存器R1中。
(4)指令LOAD R1,[3,100]。从段表的的第3项可读出第3段的存在位为1,内存始址为8000,段长为80,存取控制为R,因此,指令的逻辑地址中段内地址超过了段伏,地址变换机构将产生越界中断信号。
(5)指令JMP[2,100]。从段表的第2项可读出第2段的存在位为1,内存始址为3000,段长为200,访问权限为E,因此逻辑地址与访问方式都合法,形成物理地址3100,指令执行后,将跳转到内存单元3100处继续执行。
5.3自测题
5.3.1基本题一．判断题(正确的在括号中记√,错误的记×)
1.为了减少内部碎片,页应偏小为好。 ( )
2.为了减少缺页中断率,页应该小一些。 ( )
3.为提高对换空间的利用率,一般对其使用离散的分配方式。 ( )
4.用户程序中出错处理部分不必常驻内存。 ( )
5.使用预分页的原因是每个进程在最初运行时需要一定数量的页面。 ( )
6.可变分区法可以比较有效地消除外部碎片,但不能消除内部碎片。 （ ）
7.分页存储管理方案易于实现用户使用内存空间的动态扩充。 ( )
8.LRU页面调度算法总是选择在主存驻留时间最长的页面被淘汰。 ( )
9.最佳适应算法比首次适应算法具有更好的内存利用率。 ( )
10.请求分段存储管理中,分段的尺寸要受主存空间的限制。 ( )
二．单项选择题，在每小题的四个备选答案中选出一个正确答案，并将其代码写在题干后面的括号内。不选、错选或多选者该题无分。
1.在可变式分区管理中,最佳适应算法是将空白区在空白区表中按______次序排列。
A.地址递增 B.地址递减 C.容量递增 D.容量递减
2.动态重定位技术依赖于_______.
A.重定位装入程序 B.重定位寄存器 C.地址机构 D.目标程序
3.请求分页存储管理方案的主要特点是__________。
A.不要求将作业装入内存 B.不要求将作业全部装入内存
C.不要求使用联想存储器 D.不要求缺页中断的处理
4.在存储管理方案中,___________可与覆盖技术配合。
A.页式管理 B.段式管理 C.段页式管理 D.可变分区管理
5.一个计算机系统虚存的最大容量是由__________决定的。
A.主存的容量 B.辅存的容量
C.主存容量+辅存容量 D.计算机的地址机构
6.在存储管理中,采用覆盖与交换技术的目的是_________。
A.节省主存空间 B.物理上扩充主存容量 C.提高CPU效率 D.实现主存共享
7.在可变式分区分配方案中,只需要进行一次比较就可以判定是否满足作业对主存空间要求的是______。
A.最先适应算法 B.最佳适应算法 C.最差适应算法 D.固定式分区方法
8.在虚拟存储系统中,若进程在内存中占3块(开始时为空〉,采用先进先出页面淘汰算法,当执行访问页号序列为1、2、3、4、1、2、5、1、2、3、4、5、6时,将产生次缺页中断。
A.7 B.8 C.9 D.10
9.下面对计算机存储器体系中的各个部分按速度从快到慢排列,其中正确的是______。
A.寄存器 cache 主存储器 后援存储器 磁盘设备 磁带设备
B.cache 寄存器 后援存储器 主存储器 磁盘设备 磁带设备
C.主存储器 cache 寄存器 后援存储器 磁盘设备 磁带设备
D.磁盘设备 主存储器 寄存器 cache 后援存储器 磁带设备
10.很好地解决了"零头"问题的存储管理方法是_______。
A.页式存储管理 B.段式存储管理 c.多重分区管理 D.可变式分区管理
11,有利于程序动态链接的内存管理方法是_______。
A.分段存储管理 B.分页存储管理 C.可变区分割分配 D.固定区分割分配
12.系统"抖动"现象的发生是由________引起的。
A.置换算法选择不当 B.交换的信息量过大 c.内存容量不足 D.请求页式管理方案
13.静态重定位是在作业的装入过程中进行的,动态重定位是在作业_________中进行的。
A.编译过程 B.装入过程 C.修改过程 D.执行过程
14.在可变式分区存储管理中的拼接技术可以________。
A.集中空闲区 B.增加主存容量 C.缩短访问周期 D.加速地址转换
15.在请求调页系统中,若逻辑地址中的页号超过页表控制寄存器中的页表长度,则会引起越界中断；否则,若所需的页不在内存中,则会引起_____________。
A.输入/输出中断 B.时钟中断 C.越界中断 D.缺页中断。
16.分区管理中采用"最佳适应"分配算法时,宜把空闲区按_____次序登记在空闲区表中。
A.长度递增 B.长度递减 C.地址递增 D.地址递减
17.虚拟存储器管理系统的基础是程序的局部性理论。此理论的基本含义是___________。
A.程序执行时对主存的访问是不均匀的 B.数据的局部性
C.变量的连续访问 D.空间的局部性
18.实现虚拟存储器的目的是________。
A.实现存储保护 B.实现程序浮动 C.扩充辅存容量 D.扩充主存容量
19.下述存储管理方式中,会产生内部碎片的是___________。
A.页式和段式 B.页式和段页式 C.动态分区和段式 D.动态分区和段页式
20.在固定分区分配中,每个分区的大小是__________。
A.相同 B.随作业长度变化
C.可以不同但预先固定 D.可以不同但根据作业长度固定
21.虚拟存储器最基本的特征是多次性，该特征主要是基于局部性原理，实现虚拟存储器最关键的技术是___________。
A.内存分配 B.置换算法 C.请求调页(段) D.对换空间管理。
22.作业在执行中发生了缺页中断,经操作系统处理后,应让其执行_____指令。
A.被中断的前一条 B.被中断的 C被中断的后一条 D.启动时的第一条
23.把作业地址空间中使用的逻辑地址变成内存中物理地址的过程称为______。
A.重定位 B.物理化 c.逻辑化 D.加载
24.在分页系统环境下,程序员编制的程序,其地址空间是连续的,分页是由________完成的。
A.程序员 B.编译地址 C.用户 D.系统
25.在请求分页存储管理中,若采用FIFO页面淘汰算法,则当分配的页面数增加时,缺页中断的次数_______。
A.减少 B.增加 C.无影响 D.可能增加也可能减少
26.虚拟存储管理系统的基础是程序的_______理论。
A.局部性 B.全局性 C.动态性 D.虚拟性
27.下述_________页面淘汰算法会产生Belady现象。
A.先进先出 B.最近最少使用 C.最不经常使用 D.最佳
28.如果一个程序为多个进程所共享,那么该程序的代码在执行的过程中不能被修改,即程序应该是_________。
A.可执行码 B.可重入码 C.可改变码 D.可再现码
29.下面关于请求分段存储管理的叙述中,正确的是_______。
A.分段的尺寸受内存空间的限制,且作业总的尺寸也受内存空间的限制。
B.分段的尺寸受内存空间的限制,但作业总的尺寸不受内存空间的限制。
C.分段的尺寸不受内存空间的限制,且作业总的尺寸不受内存空间的限制。
D.分段的尺寸不受内存空间的限制,但作业总的尺寸受内存空间的限制。
30．从下列关于非虚拟存储器的论述中,正确的是_________。
A.要求作业在运行前,必须全部装入内存,且在运行过程中也必须一直驻留内存。
B.要求作业在运行前,不必全部装入内存,且在运行过程中不必一直驻留内存。
C.要求作业在运行前,不必全部装入内存,但在运行过程中必须一直驻留内存。
D.要求作业在运行前,必须全部装入内存,但在运行过程中不必一直驻留内存。
三．多项选择
1.下面的程序设计技术和数据结构”适合于”于请式调页环境的有_________。
A.栈 B.杂凑符号表 C.顺序查找 D.折半查找 E.纯代码 F.向量操作
2.假定有一个请式调页系统,现测得相关成分的利用率为：CPU的利用率20%;分页磁盘99.7%
其他I/0设备5%。有可能改进CPU利用率的措施有___________。
A.增加一个更快速的CPU B.增添一个更大的分页盘 C.增加多道程序的度数
D.减少多道程序的度数 E.增加其他更快速的I/O设备
3,可用来存储页表的存储器有__________。
A.cache B.主存 C.后援存储器 D.高速磁盘 E.寄存器
4.下列关于存储器管理功能的论述中,正确的论述有___________。
A.即使在多道程序设计的环境下,用户也能设计用物理地址直接访问内存的程序。
B.内存分配最基本的任务是为每道程序分配内存空间,其所追求的主要目标是提高存储空间的利用率。
C.为了提高内存保护的灵活性,内存保护通常由软件实现。
D.交换技术已不是现代操作系统中常用的技术。
E.地址映射是指将程序空间中的逻辑地址变为内存空间的物理地址。
F.虚拟存储器是物理上扩充内存容量。
5.引入段页式系统的主要动力有___________。
A.提高内存利用率 B.提高系统吞吐量 C.满足用户需要
D.更好地满足多道程序运行的需要 E.既满足用户要求,又提高内存利用率
6.从下列关于虚拟存储器的论述中,正确的论述有________。
A.在请求段页式系统中,以页为单位管理用户的虚空间,以段为单位管理内存空间。
B.在请求段页式系统中,以段为单位管理用户的虚空间,以页为单位管理内存空间。
C.为提高请求分页系统中内存的利用率,允许用户使用不同大小的页面。
D.在虚存中,为了能让更多的作业同时运行,通常只应装入部分的作业后便启动运行。
E.实现虚拟存储器的最常用的算法是最佳适应算法OPT。
F.由于有了虚拟存储器,于是允许用户使用比内存更大的地址空间。
四、填空题
1.将作业地址空间中的逻辑地址转换为主存中的物理地址的过程称为______.
2.决定缺页中断时间的主要因素有________、__________和___________。
3.分区分配中的存储保护通常采用_________方法。
4.常用的解决外部碎片问题的方法是_____________________。
5.主存中一系列物理存储单元的集合称为________。
6._____________页面调度,简称_______,是最常用的虚拟存储器系统。
7.重定位的方式有_______和_________两种。
8.在某些页面替换算法中,缺页率可能随着可使用的块数量的增加而增长.这种情况称为_________。
9.页表表目的主要内容包括______和_______.
10.分页环境下的存储保护是由与每页相连的_______________来完成的。
11,分区管理中采用"首次适应"分配算法时,应将空闲区按_______次序登记在空闲区表中。
12.在请求调页系统中有着多种置换算法;选择最先进入内存的页面予以淘汰的算法称为______;选择在以后不再使用的页面予以淘汰的算法称为______；选择自上次访问以来所经历时间最长的页面予以淘汰的算法称为_________选择自某时刻开始以来,访问次数最少的页面予以淘汰的算法称为________。
13.对外存对换区的管理应以________为主要目标,对外存文件区的管理应以________为主要目标。
14.在动态分区式内存管理中,倾向于优先使用低址部分空闲区的算法是_______,能使内存空间中空闲区分布得较均匀的算法是_______;每次分配时,把既能满足要求,又是最小的空闲区分配给进程的算法是__________。
15.提高内存利用率主要是通过_______功能实现的,_______的基本任务是为每道程序做______。使每道程序能在不受干扰的环境下运行,主要是通过____________功能实现的。
16.在请求页式管理中,页面置换算法常用的是_______和____________。
17.在页式和段式管理中,指令的地址部分结构形式分别为________和_________。
18.段表表目的主要内容包括___________。
19.假设某程序的页面访问序列为1、2、3、4、5、2、3、1、2、3、4、5、1、2、3、4且开始执行时主存中没有页面,则在分配给该程序的物理块数是3且采用FIFO方式时缺页次数是______；在分配给程序的物理块数是4且采用FIFO方式时,缺页次数是______。在分配给该程序的物理块数是3且采用LRU方式时,缺页次数是________。在分配给该程序的物理块数为4且采用LRU方式时,缺页次数是____________。
20.把_________地址转换为__________地址的工作称为地址映射。
21.静态重定位在_________时进行;而动态重定位在_________时进行。
22.在虚存管理中,虚拟地址空间是指逻辑地址空间,实地址空间是指________;前者的大小只受________限制,而后者的大小受_________。
23.在段式虚拟存储管理中,程序所使用的最大段数以及段的最大长度是由_____来决定的。
24.在段页式存储管理系统中,每道程序都有一个________表和一组________表。
25.若选用的______算法不合适,可能会出现抖动现象。
26.在页式存储管理系统中,常用的页面淘汰算法有:______,选择淘汰不再使用或最远的将来才使用的页;________,选择淘汰在主存驻留时间最长的页;________,选择淘汰离当前时刻最近的一段时间内使用得最少的页。
27.在虚拟段式存储管理中,若逻辑地址的段内地址大于段表中该段的段长,则发生______.
28.在请求页式存储管理中,若采用FIFO页面淘汰算法,则当分配的页面数增加时,____的次数可能增加也可能减少。
五、简答题
1.存储管理的主要功能是什么?
2.什么是虚拟存储器?其特点是什么?
3.在什么情况下需要进行重定位?为什么要引入动态重定位?
4.动态分区式管理的常用内存分配算法有哪儿种?比较它们各自的优缺点。
5.简述什么是覆盖?什么是交换?覆盖和交换的区别是什么?
6.什么是页式管理?静态页式管理可以实现虚存吗?
7.什么是请求页式管理?
8.什么是Belady现象?
9.段式管理可以实现虚存吗?如果可以,简述实现方法。
10.为什么要提出段页式管理?它与段式管理及页式管理有何区别?
11.为什么说段页式管理时的虚拟地址仍是二维的?
12.段页式管理的主要缺点是什么?有什么改进办法?
13.常用的内存保护方法有哪些?其特点是什么?
14.段式存储器管理和页式存储管理的区别是什么?
15．什么是请求分页存储管理的缺页中断率?影响缺页中断率的因素有哪些?
16.内存保护是否可以完全由软件来实现?为什么?
17.在以进程为单位进行对换时,每次是否将整个进程换出?为什么?
18.在请求分页系统中,为什么说一条指令执行期间可能产生多次缺页中断?
19．存储管理的主要研究内容是什么?
20.什么是虚拟存储器?实现虚拟存储器的物质基础是什么?
一．解析题
1.试述缺页中断与一般中断的主要区别。
2,在置换算法中,LRU和LFU哪个更常用?为什么?
3.什么是虚拟存储器?如何实现页式虚拟存储器?
4.实现地址重定位的方法有哪几类?
5.什么是局部性原理?什么是抖动?你有什么办法减少承统的抖动现象?
6.动态重定位的实现方式有哪几种?
7.在虚拟段式存储系统中,引入了段的动态链接。
(1)试说明为什么引入段的动态链接。
(2)请给出动态链接的一种实现方法。
8.虚拟存储器具有哪些基本特征?实现虚拟存储器的几个关键技术是什么?
9.请求页式管理中有哪几种常用的页面置换算法?试比较它们的优缺点。
10.动态分区式管理的常用内存分配算法有哪儿种?比较它们各自的优缺点。
11.常用的内存信息保护才法有哪儿种?它们各自的特点是什么?
12．引起系统抖动的原因是什么?系统如何检测抖动?一旦检测出抖动后,系统怎样消除它?
13．假定有一个使用"基址/界限寄存器"的操作系统,为了也能提供页表,曾对机器作了修改。那么能否用页来模拟"基址/界限寄存器"?若能则说明如何模拟:若不能,则说明为什么。
14.考虑一个请式调页的计算机系统,它使用一个分页盘,利用全局LRU替换算法和一种把页块平均分给进程的分配策略(即若有m个页块和n个进程,则每一进程分得m/n个页块).多道程序设计的度数固定为4,测得系统的CPU和分页盘的利用率为:
(l)CPU的利用率为13%,盘利用率为97%:
(2)CPU的利用率为87%,盘利用率为3%:
(3)CPU的利用率为13%,盘利用率为3%.
上述每一种情形可能会出现什么问题?能否用增加多道程序的度数来增加CPU的利用率?分页是否有助于提高利用率?
15.试说明多级存储方法与虚拟方法的主要区别.
16.在一分页存储管理系统中,逻辑地址长度为16位,页面大小为4096字节,现有一逻辑地址为2F6AH,且第0、1、2页依次存放在物理块5、10、11中,间相应的物理地址为多少?
二．算法题
1.分段与分页很类似,只是其"页"的大小是可变的.试基于FIFO和LRU页面替换算法提出两个段替换算法.
2.己知某分页系统统,主存容量为64K,页面大小为1K,对一个4页大的作业;其0、1、2、3页分别被分配到主存的2、4、6、7块中。
（1）将十进制的逻辑地址1023、2500、3500、4500转换成物理地址。
(2) 以十进制的逻辑地址1023为例画出地址变换过程图。
3.在一采取局部置换策略的请求分页系统中,分配给某个作业的内存块数为4,其中存放的四个页面的情况如表5.3所示。
表5.3四个页面的情况物理块
虚页号
装入时间
最后二次访问时间
访问位
修改位
0
2
60
157
0
1
1
1
160
161
1
0
2
0
26
158
0
0
3
3
20
163
1
1
上面的所有数字均为十进制数,所有时间都是从进程开始运行时从0开始计数的时钟数。请问,如果系统采用下列置换算法,将选择哪一页进行换出?
(1)FIFO算法;
(2)LRU算法;
(3)改进的Clock算法。
4.某页式虚存储系统的物理空间共3K,页面大小为1K,一进程按下列地址顺序引用内存单元:3635,3632,1140,3584,2892,3640,0040,2148,1700,2145,3209,0000,1102,1100。如果上述数字均为十进制数,而内存中尚未装入任何页。)给出使用LRU算法时的缺页次数,并与FIFO时的情况进行比较。
求调页,
5.有一个二维数组:
Var A:ARRAY[1..100,1..100] OF integer;
按先行后列的次序存储。对一采用LRU置换算法的页式虚拟存储器系统,假设每页可存放200个整数。若分配给一个进程的内存块数为3,其中一块用来装入程序和变量i,j,另外两块专门用来存放数组(不作它用),且程序段已在内存,但数据页尚未装入内存。请分别就下列程序计算执行过程中的缺页次数。
程序1,程序2:
FOR i:=1 TO 100 DO FOR j:=1 TO 100 DO
FOR j:=l TO 100 DO FOR i:=1 TO 100 DO
A[i,j]:=0 A[i,j]:=0
6.某虚拟存储器的用户空间共有32个页面,每页1K,主存16K。假定某时刻系统为用户的第0、1、2、3页分配的物理块号为5、10、4、7,而该用户作业的长度为6页,试将十六进制的虚拟地址OMC、103C、1A5C转换成物理地址。
7.某段式存储管理系统中,有一作业的段表(SMT)如下表所示,求逻辑地址[0,65],[1,55],[2,90],[3,20]对应的主存地址(按十进制)。
段号
段长〈容量〉
主存起始地址
状态
0
1
2
3
200
50
100
150
600
850
1000
0
0
0
1
8.表5.2给出了某系统中的空闲分区表,系统采用可变式分区存储管理策略。现有以下作业序列296K、2OK、200K。若用首次适应算法和最佳适应算法来处理这些作业序列,试问哪一种算法可以满足该作业序列的请求,为什么?
表5.2空闲分区表分区号
大小
起始地址
1
32K
100K
2
10K
150K
3
5K
200K
4
218K
220K
5
96K
530K
9.在一个请求分页存储管理系统中,一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,当分配给该作业的物理块数分别为3、4时,试计算采用下述页面淘汰算法时的缺页率(假设开始执行时主存中没有页面),并比较所得结果。
(1)最佳置换淘汰算法
(2)先进先出淘汰算法
(3)最近最久未使用淘汰算法
10.在某系统中,采用固定分区分配管理方式,内存分区(单位字节)情况如图5.9所示。现有大小为lk、9K、33K、121K的多个作业要求进入内存,试画出它们进入内存后的空间分配情况,并说明主存浪费有多大?
11.设有一页式存储管理系统,向用户提供的逻辑地址空间最大为16页,每页2048字节,内存总共有8个存储块,试问逻辑地址至少应为多少位?内存空间有多大?
12.在一个段式存储管理系统中,其段表为:
段号 内存起始地址 段长
0 210 500
1 2350 20
2 100 90
3 1350 590
4 1938 95
试求下述逻辑地址对应的物理地址是什么?
段 号 段内位移
430
10
500
400
112
32
13.某操作系统采用可变分区分配存储管理方法,用户区为512K且始址为0,用空闲分区表管理空闲分区。若分配时采用分配空闲区低地址部分的方案,且初始时用户区的512K空间空闲,对下述申请序列:
申请300K,申请100k,释放300K,申请150K,申请3OK,申请4OK,申请6OK,释放3OK
回答下列问题:
(1)采用首次适应算法,空闲分区中有哪些空块(给出始址、大小)?
(2)采用最佳适应算法,空闲分区中有哪些空块(给出始址、大小)?
(3)如再申请look,针对(1)和(2)各有什么结果?
14.有一页式系统,其页表存放在主存中。
(1)如果对主存的一次存取需要15微秒,试问实现一次页面访问的存取时间是多少?
(2)如果系统加有快表,平均命中率为85%,当页表项在快表中时,其查找时间忽略为0,试问此时的存取时间为多少?
15.若在一分页存储管理系统中,某作业的页表如下所示。已知页面大小为1024字节,试将逻辑地址1011,2148,3000,4000,5012转化为相应的物理地址。
页号 块号
0 2
1 3
2 1
0 6
16,26.设一作业共有5页(第0—4页),其中程序占3页(第0—2页)、常数占1页(第3页)、工作单元占1页(第4页)。它们依次放在外存的45、46页和98、99、100页.现已由程序段分配在内存的7、10、19页中:而常数区和工作区尚未获得内存.请回答下述问题:
(l)页表应包括哪些项目?填写此页表，若工作区分配到内存的第9页,则页表如何变化?
(2)在运行中,因需使用常数而发生中断,假定此时内存无空闲页面,需要把第9页淘汰,操作系统应如何处理?页表又发生什么变化?
17,24.一个好的页面替换算法应使缺页中断次数最少，一种方法是将正使用的页均匀地分散在整个存储区中.可以给每一页块附加一个计数器,用它记录与该页块相关的页的个数，当进行页面替换时,选择其计数器之值最小的那个页块.
(1)利用上述思想,提出一个页面替换算法,并回答下面的问题:
A．该计数器的初值是多少?
B．该计数器何时增值?
C.该计数器何时减值?
D.如何选择被替换的页?
(2)若有4个页块,给定下面的页访问串,使用你的算法将会出现多少次缺页中断?
1,2,3,4,5,3,4,1,6,7,8,9,7,8,9,5,4,5,4,2
(3)给定(2)中同样的条件和访问串,若采用最佳页面替换算法,其缺页中断次数的最小值是多少?
18.考虑下面的页访问串:
1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6
假定分别有1,2,3,4,5,6,7个页块,应用下面的页面替换算法,各会出现多少次缺页中断?
(1)LRU:
(2)FIFO:
(3)Optima1.
19,18．对于所给定的如表4.2所示的段表,下面逻辑地址所对应的物理地址是什么?
(1)0,430； (2)1,10； (3)1,11； (4)2,500； (5)3,400； (6)4,112
表4-2
段
基址
长度
0
219
600
1
2300
14
2
90
100
3
1327
580
4
1952
96
20．对于下面的页面替换算法:
LRU；(2)FIFO；(3)Optimal；(4)Second Chance；
按照缺页中断从劣到优的顺序排列它们,并区分出它们是否有Belady异态。
21.在采用页式存储管理的系统中,某作业J的逻辑地址空间为4页(每页2048字节),且已知该作业的页面映象表(即页表)如下:
页号 块号
0 2
1 4
2 6
3 8
试借助地址变换图(即要求画出地址变换图)求出有效逻辑地址4865所对应的物理地址。
22.在虚拟页式存储管理中,为解决抖动问题,可采用工作集模型以决定分给进程的物理块数,有如下页面访问序列:
…2 5 1 6 3 3 7 8 9 1 6 2 3 4 3 4 3 4 4 4 3 4 4 3……
Δ t1 Δ t2
窗口尺寸A =9,试求t1、t2时刻的工作集。
答:一个进程在时间t的工作集可形式化地定义为:
W(t,h)={在时间t-h到t之间所访问的一串页面}
其中,h为工作集窗口尺寸。
由题目所给条件可知,t1时刻的工作集为:{1,2,3,6,7,8,9}
t2时刻的工作集为:{3,4}
4.4自测练习答案一、判断题
1.√ 2,× 3.× 4,√ 5.√ 6,× 7,√ 8.× 9,× 10,√
二、选择题
1.C 2.B 3.B 4.D 5.D 6.A 7.C 8.D 9.A 10.A 11.A 12.A 13.D
14.A 15.D 16.A 17.D 18.D 19.C 20.A 21.B 22.B 23.A 24.D 25.D 16.A 27.A 28.B 29.A 30.B
填空题
1.地址变换 2.中断服务时间 交换页面的时间 重启进程的时间
3.界限寄存器和存储保护键 4.压缩或移动 5.存储空间 6.请求式 请式调页
7.静态重定位 动态重定位 8.Beladv异态 9.页号 块号 10.保护位
11.地址递增 12.FIFO算法 OPT算法 LRU算法 LFU算法
13.提高存储空间的利用率 D.提高换入换出速度
14.首次适应算法 循环首次适应算法 最佳适应算法答
15.内存分配 分配内存 内存保护 16.先进先出 最近最久未使用
17.页号及页内位移 段号及段内位移 18.段号、段在内存的起始地址、段长度
19.13 14 14 12 20.逻辑 物理 21.程序装入内存 程序执行
22.物理地址空间 机器的地址长度 物理内存大小限制
23.逻辑地址结构答 24.段 页 25.页面置换答
26.最佳算法 先进先出算法 最近最少使用 27.地址越界中断 28.缺页中断四、简答题
1.答:存储管理的主要功能包括以下几点:
(1)在硬件的支持下完成统一管理内存和外存之间数据和程序段自动交换的虚拟存储器功能。
（2)将多个虚存的一维线性空间或多维线性空间变换到内存的唯一的一维物理线性地址空间。
(3)控制内外存之间的数据传输。
(4)实现内存的分配和回收。
(5)实现内存信息的共享与保护。
2,答:由进程中的目标代码、数据等的虚拟地址组成的虚拟空间称为虚拟存储器。虚拟存储器不考虑物理存储器的大小和信息存放的实际位置,只规定每个进程中相互关联信息的相对位置。每个进程都拥有自己的虚拟存储器,且虚拟存储器的容量是由计算机的地址结构和寻址方式来确定。
实现虚拟存储器要求有相应的地址转换机构,以便把指令的虚拟地址变换为实际物理地址;另外,由于内存空间较小,进程只有部分内容存放于内存中,待执行时根据需要再调入内存。
3,答:源程序经过编译产生的目标模块一般总是从0开始编址的,其中的地址都是相对于起始地址的相对地址。在将目标模块经过链接装入内存时,其分配到的内存空间的起始地址通常不为0,因此指令和数据的实际物理地址与装入模块中的相对地址是不同的。此时,为了使程序能够正确执行,必须将相对地址转换成物理地址,即进行重定位。
进程在运行过程中经常要在内存中移动位置〈如对换、紧凑时),引入动态重定位的目的就是为了满足程序的这种需要,动态重定位的实现需要一定的硬件支持,重定位的过程是由硬件地址变换机构在程序执行每条指令时自动完成的。
4,答:动态分区式管理的常用内存分配算法有最先适应法(FF)、最佳适应法(BF)和最坏适应法(WF)
优缺点比较：
①从搜索速度上看最先适应法最佳,最佳适应法和最坏适应法都要求把不同大小的空闲区按大小进行排队。
②从回收过程来看,最先适应法也是最佳,因为最佳适应法和最坏适应法都必须重新调整空闲区的位置。
③最佳适应法找到的空闲区是最佳的,但是会造成内存碎片较多,影响了内存利用率,而最坏适应法的内存碎片最少,但是对内存的请求较多的进程有可能分配失败。
总之,三种算法各有所长,针对不同的请求队列,它们的效率和功能是不一样的。
5.答:将程序划分为若干个功能上相对独立的程序段,按照程序的逻辑结构让那些不会同时执行的程序段共享同一块内存区的内存扩充技术就是覆盖。
交换是指先将内存某部分的程序或数据写入外存交换区,再从外存交换区中调入指定的程序或数据到内存中来,并让其执行的一种内存扩充技术。
与覆盖技术相比,交换不要求程序员给出程序段之间的覆盖结构,而且,交换主要是在进程或作业之间进行,而覆盖则主要在同一个作业或同一个进程内进行。另外,覆盖只能覆盖那些与覆盖程序段无关的程序段。
6.答:页式管理就是把各进程的虚拟空间划分为若干长度相等的页面,把指令按页面大小划分后存放在内存中执行或只在内存中存放那些经常被执行或即将被执行的页面,而那些不被经常执行以及在近期内不可能被执行的页面则存放于外存中,按一定规则调入的一种内存管理方式。
静态页式管理不能实现虚存,这是因为静态页式管理要求进程或作业在执行前全部被装入内存,作业或进程的大小仍受内存可用页面数的限制。
7.答:请求页式管理是动态页式内存管理的一种,它在作业或进程开始执行之前,不把作业或进程的程序段和数据段一次性的全部装入内存,而只装入被认为是经常反复执行和调用的工作区部分。其他部分则在执行过程中动态装入。请求页式管理的调入方式是,当需要执行某条指令而又发现它不在内存时,或当执行某条指令需要访问其他数据或指令时,而这些指令和数据又不在内存中,从而发生缺页中断,系统将外存中相应的页面调入内存。
8,答,Belady现象是指在使用FIFO算法进行内存页面置换时,在未给进程或作业分配足它所要求的全部页面的情况下,有时出现的分配的页面数增多,缺页次数反而增加的奇怪现象。
9.答:段式管理可以实现虚存。
段式管理把程序按照内容或过程〈函数〉关系分成段,每段拥有自己的名字。一个用户作业或进程所包含的段对应于一个二维线性虚拟空间〈段号s与段内相对地址w),也就是一个二维虚拟存储器。段式管理以段为单位分配内存,然后通过地址映射机构把段式虚拟地址转换成实际的内存物理地址。只把那些经常访问的段驻留内存,而把那些在将来一段时间内不被访问的段放入外存,待需要时产生缺段中断E自动调入。
10答:因为段式管理和页式管理各有所长。段式管理为用户提供了一个二维的虚拟地址空间,反映了程序的逻辑结构,有利于段的动态增长以及共事和内存保护等,这极大地方便了用户。而分页系统则有效地克服了碎片,提高了存储器的利用效率。从存储管理的目的来讲,主要是方便用户的程序设计和提高内存的利用率。所以人们提出了将段式管理和页式管理结合起来让其互相取长补短的段页式管理段页式管理与段式和页式管理相比,真访问时间较长。因此,执行效率低。
11.答:因为在段页式内存管理中,对每一段内的地址空间进行分页式管理只是为了克服在内存分配过程中产生的大量碎片,从而提高存储器的利用效率,它并没有改变段内地址空间的一维结构,所以段页式内存管理中的虚拟地址仍然和段式内存管理中的虚拟地址一样是二维结构的。
12.答:段页式管理的主要缺点是对内存中指令或数据进行存取时,至少需要对内存进行三次以上的访问。第一次是由段表地址寄存器取段表始址后访问段表,由此取出对应段的页表在内存中的地址。第二次则是访问页表得到所要访问的指令或数据的物理地址。只有在访问了段表和页表之后,第三次才能访问真正需要访问的物理单元。显然。这将大大降低CPU执行指令的速度。
改进办法是设置快速联想寄存器。在快速联想寄存器中,存放当前最常用的段号s,页号p和对应的内存页面地址与其他控制项。当需要访问内存空间某一单元时,可在通过段表、页表进行内存地址查找的同时,根据快速联想寄存器查找其段号和页号。如果所要访问的段或页的地址在快速联想寄存器中,则系统不再访问内存中的段表、页表而直接把快速联想寄存器中的值与页内相对地址d拼接起来得到内存地址。
13.答：常用的内存保护方法有硬件方法、软件方法以及软硬结合方法。
14.答：分页和分段都采用离散分配方式,它们的区别是:
(1)页式管理中源程序进行编译连接时是将主程序、子程序、数据区等按照线性空间的一维地址顺序排列起来。段式管理则是将程序按照内容或过程(函数)关系分成段,每段拥有自己的名字。一个用户作业或进程所包含的段对应于一个二维线性虚拟空间,也就是一个二维虚拟存储器。
(2)同动态页式管理一样,段式管理也提供了内外存统一管理的虚存实现技术。与页式管理不同的是:段式虚存每次交换的是一段有意义的信息,而不是像页式虚存管理那样只交换固定大小的页,从而需要多次的缺页中断才能把所需要的信息完整地调入内存。
(3)在段式管理中,段长可根据需要动态地增长。这对那些需要不断增加或改变新数据或子程序的段来说,将是非常有好处的。
(4)段式管理便于对具有完整逻辑功能的信息段进行共享。
(5)阶段式管理便于进行动态链接,而页式管理进行动态链接的过程比较复杂。
15.答：1.缺页中断率=缺页中断次数/访问页面的总次数影响请求分页缺页中断率的因素有,①分配给作业的主存块数；②页面的大小；③程序的局部化程度；④页面调度算法。
16.答:内存保护的主要任务是确保每道程序都只在自己的内存区内运行。这就要求系统能对每条指令所访问的地址进行越界检查。若发生越界,系统应能立即发现,并发出越界中断请求,以抛弃该指令。若每次检查完全用软件实现,则每执行→条指令时,都要增加铋若干条指令去行越界的检查功能,这无疑将降低程序的执行速度,因此,J越界检查通常由硬件实现,并使指令的执行与越界检查功能并行执行,从而不使程序的运行速度降低。当然,对发现有越界后的处理需与软件配合来完成。因此说内存保护功能是由硬件和软件协同完成的。
17.答:在以进程为单位进行对换时,并非每次都将整个进程换出。这是因为:
(1)从结构上讲,进程是由程序段、数据段和进程控制块组成的,其中进程控制块总有部分或全部常驻内存，不被换出。
（2）程序段和数据段可能正被若干进程共享，此时它们也不能换出。
18.答:因请求调页时,只要作业的部分页在内存,该作业就能执行,而在执行过程中发现所要访问的指令或数据不在内存时,则产生缺页中断,将所需的页面调入内存。在请求调页系统中,一条指令(如copy A to B)可能跨了两个页,而其中要访问的操作数可能与指令不在同一个页上,且操作数本身也可能跨两个页。当要执行这类指令,而相应的页都不在内存时,就将产生多次缺页中断。
19.答:存储管理的主要研究内容是主存存储分配、地址再定位、存储保护和存储扩充。
20.答:虚拟存储器简称虚存,是利用操作系统产生的一个其容量比实际主存大得多的存储器,实际上是一个地址空间。实现虚存的物质基础是:一定容量的主存;大容量的辅存和地址变换机构。虚存不可能无限大,它受字长、速度(传送速度〉、使用频率等因素的限制,其最大容量由计算机系统的地址机构决定。虚存可分为三类:分页式虚存、分段式虚存和段页式虚存。
解析题
1.答:缺页中断作为中断,同样需要经历保护CPU现场、分析中断原因、转缺页中断处理程序进行处理、恢复CPU现场等步骤。但缺页中断又是一种特殊的中断,它与一般中断的主要区别是:
（1）在指令执行期间产生和处理中断信号。通常,CPU都是在一条指令执行完后去检查是否有中断请求到达。若有便去响应中断;否则继续执行下一条指令。而缺页中断是在指令执行期间,发现所要访问的指令或数据不在内存时产生和处理的。
（2）一条指令在执行期间可能产生多次缺页中断。例如,对于一条读取数据的多字节指令,指令本身跨越两个页面,假定指令后一部分所在页面和数据所在页面均不在内存,则该指令的执行至少产生两次缺页中断。
2,答：LRU置换算法比LFU置换算法更常用。
置换算法总是希望被换出的页(段)在不久的将来再被访问的概率尽可能小。然而LFU算法往往不能实现这一点。因为在LFU算法中,某页被访问的次数是用计数器计数的,在有些情况下,刚被调入的页(段)由于局部性原理,可能立即被访问多次,因而其计数器的计数值会很大;但过了这一小段时间后,该页(段)又不再被访问。这样,在根据置换算法确定的原则选择某一页(段)将之换出时,这样的页(段)会被留在内存中,而将其他页(段)换出去。
虽然如此被调出的页(段)在刚才一段时间内其被访问次数的计数值较小,但有可能马上又要访问。可见,LFU算法的置换选择可能导致很坏的选择。
但在LRU算法中,由于是选择最近最久未被访问的页(段)置换出去,即预计在最近的将来该页被访问的概率也很小,因此,这种置换算法可能导致较好的选择,这使LRU算法或其近似算法获得了较好的应用。
3,答:虚拟存储器是指具有请求调入功能和置换功能,能从逻辑上对内存容量进行扩充的一种存储系统。从用户观点看,虚拟存储器具有比实际内存大得多的容量,其逻辑容量由逻辑地址结构以及内存和外存容量之和决定,其运行速度接近于内存的速度,而每位成本却又接近于外存。
为实现虚拟存储器,首先需要扩充页表,增加状态位以指出所需页是否在内存,增加外存始址以便调入页面,增加引用位以供置换算法用,增加修改位使得换出时减少写盘次数。另外,还要使用两种关键技术:
(1)请求调页技术:请求调页技术是指及时将进程所要访问的、不在内存中的页调入内存。该功能是由硬件(缺页中断机构发现缺页)和软件(将所需页调入内存)配合实现的。
(2)置换页技术:当内存中已无足够空间用来装入即将调入的页时,为了保证进程能继续运行,系统必须换出内存中的部分页,以腾出足够的空间。具体的置换操作并不复杂,其关键是应将哪些页换出,即采取什么置换算法。
4,答:实现地址重定位的方法有两种:静态地址重定位和动态地址重定位。
(1)静态地址重定位是在虚空间程序执行之前由装配程序完成地址映射工作。静态重定位的优点是不需要硬件支持,但是用静态地址重定位方法进行地址变换无法实现虚拟存储器。静态重定位的另一个缺点是必须占用连续的内存空间和难以做到程序和数据的共享。
(2)动态地址重定位是在程序执行过程中,在CPU访问内存之前由硬件地址变换机构将要访问的程序或数据地址转换成内存地址。动态地址重定位的主要优点有:
①可以对内存进行非连续分配。
②动态重定位提供了实现虚拟存储器的基础。
③动态重定位有利于程序段的共享。
5,答:局部性原理是指在几乎所有程序的执行过程中,在一段时间内,CPU总是集中地访问程序中的某一个部分而不是对程序的所有部分具有平均的访问概率。
抖动是指当给进程分配的内存小于所要求的工作区时,由于内存外存之间交换频繁,访问外存的时间和输入输出处理时间大大增加,反而造成CPU因等待数据而空转,使得整个系统性能大大下降。
在物理系统中,为了防止抖动的产生,在进行淘汰或置换时,一般总是把缺页进程锁住,不让其换出,从而防止抖动发生。
防止抖动发生的另一个办法是设置较大的内存工作区。
6,答:动态重定位的实现必须有硬件地址变换机构的支持,其具体的实现方式主要有：
(1)连续分配方式下的动态重定位。连续分配方式需在整个系统中设置一个重定位寄存器,用来存放正在执行的作业在内存中的起始地址。当CFU要存取指令或数据时,硬件的地址变换机构自动将逻辑地址与重定位寄存器的值相加,形成指令或数据的物理地址。
(2)离散分配方式下的动态重定位。离散分配方式主要是指分页和分段存储管理方式,此时,系统首先必须为每个作业配置一张页(段)表,用来记录作业的每个页(段)对应的内存块号(内存始址和段长),页(段)表被存放在内存中。而在整个系统中则只需设置一个页(段)表控制寄存器,用来存放正在执行的作业的页(段)表始址和长度。当CPU要存取指令或数据时,硬件的地址变换机构自动将逻辑地址分成页号和页内地址两部分(或直接从逻辑地址中获得段号),并根据页(段)号到控制寄存器所指示的页(段)表中获得对应的物理块号(或段的内存始址),并与页内地址(或段内存地址)拼接(或相加),形成物理地址。
7,答：(1)在作业装入内存运行前,应将各个目标程序定位后装入作业的地址空间,形成可执行程序的链接,称为静态链接。静态链接常常因为目标程序个数多而花费大量的CPU时间,而实际运行时又常常只用到其中的部分模块,因而也造成了存储空间的浪费。动态链接是作业运行时先装入主程序,运行过程中需要某模块时,再将该模块的目标程序调入内存并进行链接,它克服了静态链接的不足。
(2)分段存储管理就是最典型的动态链接。分段管理允许用户将作业按逻辑关系进行自然分段,各段的大小可以不同。逻辑段内的地址是由两部分组成的(s,段号,d：段内位移量),即分段地址空间是用户定义的三维空间。内存分配以段为单位,段可以在作业运行过程中根据请求而动态链接和装入。
8,答:虚拟存储器的基本特征有:
(1)多次性。作业只要部分装入内存便可后动执行;z共余部分可待需要时再调入内存,即一个作业将分成多次装入内存。
(2)对换性。在进程运行期间,允许将那些暂不使用的程序和数据从内存魄至外存的对换区(换出),待以后需要时再将它们从外存调入内存(换入)。
(3)离散性。实现虚拟存储器必须采用离散的分配技术,而连续的分配技术无法实现虚拟存储器的功能。
(4)虚拟性。虚拟存储器只是在逻辑上扩充内存容量,而实际的内存容量并没有真正扩大。
实现虚拟存储器的关键技术有以下两个:
(1)请求调页(段)技术。这是指及时将进程所要访问的、不在内存中的页(段)调入内存。
该功能是由硬件(缺页(段)中断机构)发现缺页(段)和软件(将所需页(段)调入内存)配合实现的。
(2)置换页(段)技术。当内存中已无足够空间用来装入即将调入的页(段)时,为了保证进程能继续运行,系统必须换出内存中的部分页(段),以腾出足够的空间,将所嚣的页(段)调入内存。具体的置换操作并不复杂,其关键是应将哪些页(段)换出,即采取什么置换算法。
9,答:比较常用的页面置换算法有:
(1)随机淘汰算法：即随机地选择某个用户页面并将其换出。
(2)轮转法RR：轮转法循回换出内存可用区内一个可以被换出的页,无论该页是刚被换进或已经换进内存很长时间。
(3)先进先出法FIFO：FIFO算法选择在内存驻留时间最长的一页将其淘汰。
(4)最近最久未使用页面置换算法LRU:该算法的基本思想是:当需要淘汰某一页时,选择离当前时间最近的一段时间内最久没有使用过的页面先淘汰。
(5)理想型淘汰算法OPT:该算法淘汰在访问串中将来再也不出现的或是在离当前最远的位置上出现的页面。
RR和FIFO都是基于CPU按线性顺序访问地址空间这一假设,但是实际上CPU在很多时候并非是按线性顺序访问地址空间的,因而官们的内存利用率不高。此外FIFO算法还存在着Belady现象。LRU算法的完全实现是相当困难的,因此在实际系统中往往要采取LRU的近似算法,常用的近似算法有最不经常使用页面淘汰算法LFU和最近没有使用页面淘汰算法(NUR)。OPT算法由于必须预先知道每一个进程的指令访问串,所以它是无法实现的。
10,答:动态分区式管理的常用内存分配算法有最先适应法(FF)、最佳适应法(BF)和最坏适应法(WF)
优缺点比较：
①从搜索速度上看最先适应法最佳,最佳适应法和最坏适应法都要求把不同大小的空闲区按大小进行排队。
②从回收过程来看,最先适应法也是最佳,因为最佳适应法和最坏适应法都必须重新调整空闲区的位置。
③最佳适应法找到的空闲区是最佳的,但是会造成内存碎片较多,影响了内存利用率,而最坏适应法的内存碎片最少,但是对内存的请求较多的进程有可能分配失败。
总之,三种算法各有所长,针对不同的请求队列,它们的效率和功能是不一样的。
11,答:常用的内存保护方法有硬件法、软件法和软硬件结合保护法三种。
上下界保护法是一种常用的硬件保护法。上下界存储保护技术要求为每个进程设置对上下界寄存器。上下界寄存器中装有被保护程序和数据段的起始地址和终止地址。在程序执行过程中,在对内存进行访问操作时首先进行访问地址合法性检查,即检查经过重定位之后的内存地址是否在上、下界寄存器所规定的范围之内。若在规定的范围之内,则访问是合法的，否则是非法的,并产生访问越界中断。
保护键法也是一种常用的软件存储保护法。保护键法为每一个被保护存储块分配一个单独的保护键。在程序状态字中则设置相应的保护键开关字段,对不同的进程赋予不同的开关代码以和被保护的存储块中的保护键匹配。保护键可以设置成对读写同时保护的或只对读写进行单项保护的。如果开关字段与保护键匹配或存储块未受到保护,则访问该存储块是允许的,否则将产生访问出错中断。
另外一种常用的硬软件内存保护方式是z界限存储器与CPIJ的用户态,核心态相结合的保护方式。在这种保护方式下,用户态进程只能访问那些在界限寄存器所规定范围内的内存部分,而核心态进程则可以访问整个内存地址空间。
12,解:由于分配给进程的页面数少于进程所需的最低页面数,导致出现接连不断的缺页中断,从而引起系统抖动.系统可以利用将CPU的利用率与多道程序的度数进行比较的方法来检测系统抖动,一旦发生抖动,可通过减少多道程序的度数的办法来消除它。
13.解:只要内存按固定大小的段分配,就可用页表模拟"基址/界限寄存器".在这种方法中,页表可记录段的基址,而其有效/无效"位用于指明该段在内存中的部分.此外,还要注意解决可能出现的内部碎片问题。
14.解(1)会出现抖动现象:
(2)CPU的利用率相当高,可以增加多道程序度数:
(3)增加多道程序的度数.
15解：所谓多级存储方法是指在主存以外再配上后援存储器来补充主存,先把用户作业放在后援存储器上,然后等到要真正执行它时再设法把这部分作业调入主存,它们之间的调度由用户自己负责,这造成用户使用上的困难.由于系统不同,其主存大小也会随之不同,用户往往不得不修改程序.在批量分时系统中多个用户同时共享主存,因此,用户就不能直接参与主存和后援存储器之间的调度了.这就需要由操作系统来对它进行统一的、自动的管理,并采用虚拟存储技术:有了虚拟存储器之后,用户就不感到主存和后援存储器之间的区别,而在统一的逻辑存储器上安排程序和数据.由于虚拟存储器比实际存储器大得多,因而可以同时装入许多作业。
16,由题目所给条件可知,本页式系统的逻辑地址结构为:
页号P
页内位移量W
15 12 11 0
逻辑地址2F6AH的二进制表示如下:
P W
0010 111101101010
由此可知逻辑地址2F6AH的页号为2,该页存放在第11号物理块中,用十六进制表示块号为B,所以物理地址为BF6AH。
二．算法题
1,解:FIFO查找第一个能容纳即将进入的段,若不允许重定位且没有一个段能容纳即将进入的段,则选择几个内存区域连续的段,它们"最靠近空闲空间表的首部",合并它们后能容纳即将进入的段.若允许重定位,则重新安排内存,使得能够容纳即将进入段的开始的N个段在内存中是连续的.在这两种情况都应将剩余空间并人空闲空间表中.
LRU选择一个未被使用的、时间周期最长的能容纳即将进入段的段,并将剩余空间加到空闲空间表中.若没有满足要求的段,则选择一组内存连续的、且合并起来满足要求的"最老"的段(不能重定位的情况).若可以重定位,则重新安排这组最老的段,使其在内存中是连续的,它们合并后可以满足即将进入段的要求。
注意:由于段的大小可以不同,因此,所选定被替换的段可能小于要替换它的那个段,需要分别考虑对能够重定位和不能重定位的情况.
2,分析：在分页系统中进行地址转换时,地址交换机构将自动把逻辑地址转化为页号和页内地址,如果页号不小于页表长度,则产生越界中断;否则便以页号为索引去检索页表,从中得到对应的块号,并把块号和页内地址分别送入物理地址寄存器的块号和块内地址字段中,形成物理地址。答:(1)对上述逻辑地址,可先计算出它们的页号和页内地址(逻辑地址除以页面大小，得到的商为页号,余数为页内地址),然后通过页表转换成对应的物理地址。
①逻辑地址1023:1023/1k,得到页号为0,页内地址为1023,查页表找到对应的物理块号为2,故物理地址为2×1K+1023=3071。
②逻辑地址2500：2500/1K，得到页号为2,页内地址为452,查页表找到对应的物理块号为6,故物理地址为6×1K+452=6596。
③逻辑地址3500:3500/1K,得到页号为3,:页内地址为428,查页表牛找到对应的物理块号为7,故物理地址为7×1K+428=7596。
④逻辑地址4500:4500/1K,得到页号为4,页内地址为404,因页号不小于页表长度,故产生越界中断。
(2)逻辑地址1023的地址变换过程如图4.12所示,其中的页表项中没考虑每页的访问权限。
3分析：FIFO算法即先进先出算法,它选择最先装入内存的页面进行换出;LRU算法即最近最久未用置换算法,它选择最近最长时间没被使用的页面进行换出;改进的Clock算法是一种常用的LRU近似算法,它优先选择访问位和修改位均为0的页面进行换出。
答,(1)FIFO算法选择的换出页是物理块3中的第3页。
(2)LRU算法选择的换出页是物理块0中的第2页。
(3)改进的Clock算法选择的换出页是物理块2中的第0页。
4答:(1)根据题意,分配给作业的内存块数为3,而页面的引用次序为:3、3、1、3、2、3、0、2、1、2、3、0、1、1。因此,可以计算出,采用LRU算法时,缺页次数为8,采用FIFO算法时,缺页次数为6。LRU算法用最近的过去来作为预测最近的将来的依据,一般认为其有较好的性能,但实现时,要记录最近在内存的每个页面的使用情况,比FIFO困难,其开销也大。有时,因页面的过去和未来的走向之间并无必然的联系,如上面,LRU算法的性能就没想象中那么。
5,答:对程序1,首次缺页中断（访问A[0,0]时产生）将装入数组的第1、2行共200个整数，由于程序是按行对数组进行访问的,只有在处理完200个整数后才会再次产生缺页中断；以后每调入一页,也能处理200个整数,因此,处理100×100个整数共将发生50次缺页。
对程序2,首次缺页中断同样将装入数组的第1、2行共200个整数,但由于程序是按列对数组进行访问的,因此在处理完2个整数后又会再次产生缺页中断:以后每调入一页,也只能处理2个整数,因此,处理100×100个整数共将发生5000次缺页。
6,答:由题目所给条件可知,该系统的逻辑地逻辑地址有15位,其中高5位为页号,低10位为页内地址;物理地址有14位,其中高4位为块号,低10位为块内地址。另外,由于题目中给出的逻辑地址是十六进制数,故可先将其转换成二进制数以直接获得页号和页内地址,再完成地址的转换。
（1）逻辑地址(OA5C)的页号为（00010），即2,故页号合法；从页表中找到对应的内存块号为4,即(0100)；与页内地址(10 0101 1100)拼接形成物理地址(010010 01011100),即(125C)。
(2)逻辑地址(103C)l6的页号为4,页号合法,但该页未装入内存,故产生缺页中断。
(3)逻辑地址。A5Ch的页号为6,为非法页号,故产生越界中断。
7,解：逻辑地址[0,65]：对应的主存地址为600+65=665
逻辑地址[1,55]:因段内地址超过段长,所以产生段地址越界中断。
逻辑地址[2,90]:对应的主存地址为1000+90=1090。
逻辑地址[3,2O]:因为状态位为1,即该段在辅存中,所以产生缺页中断。
8.分析：首次适应算法要求空闲分区按地址递增的次序排列,在进行内存分配时,总是从空闲分区农首开始顺序查找,直到找到第一个能满足其大小要求的空闲分区为止.然后,再按照作业大小,从该分区中划出一块内存空间分配给请求者,余下的空闲分区仍留在空闲分区表中。
最佳适应算法要求空闲分区按大小递增的次序排列,在进行内存分配时,总是从空闲分区农首开始顺序查找,直到找到第一个能满足其大小要求的空闲分区为止.如果该空闲分区大于作业的大小,则与首次适应算法相同,将剩余空闲区仍留在空闲区农中。
解：若采用最佳适应算法,在申请96K存储区时,选中的是5号分区,5号分区大小与申请空间大小一致,应从空闲分区表中删去该表项:接着申请2OK时,选中1号分区,分配后1号分区还剩下12IQ最后申请200K,选中4号分区,分配后剩下18K。显然采用最佳适应算法进行内存分配,可以满足该作业序列的需求。为作业序列分配了内存空间后,空闲分区表如表5.3(a)所示。
若采用首次适应算法,在申请96K存储区时,选中的是4号分区,进行分配后4号分区还剩下122IQ接着申请2OK,选中1号分区,分配后剩下12IQ最后申请200K,现有的五个分区都无法满足要求,该作业等待。显然采用首次适应算法进行内存分配,无法满足该作业序列的需求。这时的空闲分区表如表5.3(B)所示。
分区号
大小
起始地址
1
12K
100K
2
10K
150K
3
5K
200K
4
18K
220K
表5.3分配后的空闲分区表
(A) (B)
分区号
大小
起始地址
1
12K
100K
2
10K
150K
3
5K
200K
4
122K
220K
5
96K
530K
9,解:(1)根据所给页面走向,使用最佳页面淘汰算法时,页面置换情况如下:
走向 4 3 2 1 4 3 5 4 3 2 1 5
块1 4 4 4 4 4 2 2
块2 3 3 3 3 3 1
块3 2 1 5 5 5
缺页 缺 缺 缺 缺 缺 缺 缺
缺页率为:7/12
走向 4 3 2 1 4 3 5 4 3 2 1 5
块1 4 4 4 4 4 1
块2 3 3 3 3 3
块3 2 2 2 2
块4 1 5 5
缺页 缺 缺 缺 缺 缺 缺
缺页率为:6/12
由上述结果可以看出,增加分配给作业的内存块数可以降低缺页率。
(2)根据所给页面走向,使用先进先出页面淘汰算法时,页面置换情况如下:
走向 4 3 2 1 4 3 5 4 3 2 1 5
块1 4 4 4 1 1 1 5 5 5
块2 3 3 3 4 4 4 2 2
块3 2 2 2 3 3 3 1
缺页 缺 缺 缺 缺 缺 缺 缺 缺 缺
缺页率为:9/12
走向 4 3 2 1 4 3 5 4 3 2 1 5
块1 4 4 4 4 5 5 5 5 1 1
块2 3 3 3 3 4 4 4 4 5
块3 2 2 2 2 3 3 3 3
块4 1 1 1 1 2 2 2
缺页 缺 缺 缺 缺 缺 缺 缺 缺 缺 缺
缺页率为:10/12
由上述结果可以看出,对先进先出算法而言,增加分配给作业的内存块数反而使缺页率上升,这种异常现象称为Belady现象。
(3)根据所给页面走向,使用最近最久未使用页面淘汰算法时,页面置换情况如下:
走向 4 3 2 1 4 3 5 4 3 2 1 5
块1 4 4 4 1 1 1 5 2 2 2
块2 3 3 3 4 4 4 4 1 1
块3 2 2 2 3 3 3 3 5
缺页 缺 缺 缺 缺 缺 缺 缺 缺 缺 缺
缺页率为,10/12
走向 4 3 2 1 4 3 5 4 3 2 1 5
块1 4 4 4 4 4 4 4 5
块2 3 3 3 3 3 3 3
块3 2 2 5 5 1 1
块4 1 1 2 2 2
缺页 缺 缺 缺 缺 缺 缺 缺 缺
缺页率为,8/12
由上述结果可以看出,增加分配给作业的内存块数可以降低缺页率。
10,解:从图5.9可以看出,该系统中共有四个分区,第一分区的大小为8K,第二分区的大小为32K,第三分区的大小为120K,第四分区的大小为332K。作业进入系统后的内存分配情况,如图5.10所示:
操作系统
第一分区
第二分区
第三分区
第四分区
操作系统
1K的作业第一分区
9K的作业第二分区
33K的作业
第三分区
12K的作业
第四分区
0
20K
28K
60K
180K
512K-1
从图5.10可以看出,作业进入系统后,第一分区剩余空间为7K,第二分区剩余空间为23K,第三分区剩余空间为87K,第四分区剩余空间为211K。主存空间浪费328K。
11,分析：在页式存储管理中,用户作业的地址空间被划分成若干大小相等的区域,称为页或页面。相应地,将主存的存储空间也分成与页大小相等的区域,称为块或物理块。在为作业分配存储空间时,总是以块为单位来分配,可以将作业中的任意一页放到主存的任意一块中。页式存储管理系统中的逻辑地址结构为:
页号P
页内位移W
它包含两部分,前一部分为页号P,后一部分为页内位移W.
解:本题中,每页2048字节,所以页内位移部分地址需要占据11个二进制位:逻辑地址空间最大为16页,所以页号部分地址需要占据4个二进制位。故逻辑地址至少应为15位。
由于内存共有8个存储块,在页式存储管理系统中,存储块大小与页面的大小相等,因此内存空间为16K。
12,答：分析：在段式存储管理系统中,为了实现从逻辑地址到物理地址的转换,系统将逻辑地址中的段号与段表长度进行比较,若段号超过了段表长度,则表示段号太大,于是产生越界中断信号;若未越界,则根据段表始址和段号计算出该段对应段表项的位置,从中读出该段在内存的起始地址,然后,再检查段内地址是否超过该段的段长。若超过则同样发出越界中断信号;若未越界,则将该段的起始地址与段内位移相加,从而得到了要访问的物理地址如下:
(1)由于第0段的内存始址为210,段长为500,故逻辑地址[0,430]是合法地址。逻辑地址[0,430]对应的物理地址为210+430=640。
(2)由于第1段的内存始址为2350,段长为20,故逻辑地址[1,10]是合法地址。逻辑地址[1,10]对应前物理地址为2350+10=2360。
(3)由于第2段起始地址为100,段长为90,所给逻辑地址[2,500]非法。
(4)由于第3段的内存始址为1350,段长为590,故逻辑地址[3,400]是合法地址。逻辑地址[3,400]对应的物理地址为1350+400=1750。
(5)由于第4段的内存始址为1938,段长为95,所给逻辑地址[4,112]非法。
(6)由于系统中不存在第5段,所给逻辑地址[5,32]非法。
13.答：分析：为描述方便起见,本题用"(分区首址,分区长度)"的形式描述系统中的分区。由题中所给条件可知,最初系统中只有一个空闲区,大小为512K,始址为0,即(0,512K)。
（1）采用首次适应算法,在完成了题目所给的系列申请及释放内存操作后,空闲分区表如下所示。
分区 大小 起始地址
0 30K 150K
1 20K 280K
2 112K 400K
(2)采用最佳适应算法,完成了题目所给的系列申请及释放内存操作后,空闲分区表如下:
分区 大小 起始地址
0 30K 150K
1 42K 470K
2 90K 210K
(3)如再申请100K空间,由上述结果可知,采用首次适应算法后剩下的空闲分区能满足这一申请要求:而采用最佳适应算法后剩下的空闲分区不能满足这一申请要求。
14.答:若页表存放在主存中,则要实现二次页面访问需两次访问主存,一次是访问页表,确定所存取页面的物理地址,第二次才根据该地址存取页面数据。
(1)由于页表存放在主存,因此CPU必须两次访问主存才能获得所需数据,所以实现一次页面访问的存取时间是,1.5×2=3微秒
(2)在系统增加了快表后,在快表中找到页表项的概率为85%,所以实现一次页面访问的存取时间为,0.85×1.5+（1一0.85）×2×1.5=1.725微秒
15.答：分析：在页式存储管理系统中,当进程要访问某个逻辑地址中的数据时,分页地址变换机构自动地将这辑地址分为页号和页内位移两部分,再以页号为索引去检索页表.在执行检索之前,先将页号与页表长度进行比较,如果页号超过了页表长度,则表示本次所访问的地址已超越进程的地址空间,系统产生地址越界中断.如果页访问合法,则由页表始址和页号计算出相应页表项的位置,从中得到该页的物理块号,并将它装入物理地址寄存器的块号部分。与此同时,再将逻辑地址寄存器中的页内地址直接送入物理地址寄存器的块内地址部分。这样便完成了从逻辑地址到物理地址的变换。
本题中,为了描述方便,设页号为P,页内位移为W,逻辑地址为A,页面大小为L,则：
P=int(A/L)
W=A mod L
（1）对于逻辑地址1011
P=int(1011/1024)=O
W=1011 mod 1O24=1011
查页表第0页在第2块,所以物理地址为3059。
（2）对于逻辑地址2148
P=int(2148/1024)=2
W=2148 mod 1024=100
查页表第2页在第1块,所以物理地址为1124。
（3）对于逻辑地址3000
P=int(3000/1094)=2
W=3000 mod 1024=952
查页表第2页在第1块,所以物理地址为1976。
（4）对于逻辑地址4000
P=int(4000/1024)=3
W=4000 mod 1024=928
查页表第3页在第6块,所以物理地址为7072。
（5）对于逻辑地址5012
P=int(5012/1024)=4
W=5012 mod 1024=916
因页号超过页表长度,该逻辑地址非法。
16.答：(1)页表所包括的项目应有:作业页号、在内存标志、存取方式、所在外存页号、所在内存页号、修改标志等(见表4.7).
在表4.7中,存取方式E表示可执行、R表示可读、W表示可写.
表4.7
作业页号
在内存标志
存取方式
外存页号
内存页号
修改标志
0
1
E
45
7
1
1
E
46
10
2
1
E
98
19
3
0 1
R
99
9
4
0 1 0
RW
100
9
(2)在把第9页淘汰之前,先检查其修改标志,若此页内存已发生过写操作,则说明与外存对应的页面副本内存不一致,必须重新送往外存,然后才能分配给常数区.
生调页问题.
17.答：(1)回答问题如下:
A.该计数器的初值为0。
B.每当一个新页与该计数器对应的页块相关时,计数器增值。
C.每当与该计数器对应页块相关的那些页之一不再使用时,计数器减值。
D.查找一个其计数器之值最小的页块,选择被替换的页。
(2)14次缺页中断。
(3)11次缺页中断。
18.答：应用上面的算法,各会出现的缺页中断次数如表4.4所示.
注意:所给定的页块初始均为空,因此,首次访问一页时就会发生缺页中断.
表4.4
页块号
LRU
FIFO
Optimal
1
20
20
20
2
17
18
15
3
15
16
11
4
10
14
8
5
8
12
7
6
7
9
7
7
7
7
7
19,解:(1)219+430=649
(2)2300+10=2310
(3)2300+11=2311
(4)非法地址访问,自陷人操作系统。
(5)1327+400=1727
(6)非法地址访问,自陷入操作系统,
20.答：各算法按缺页中断率排列如表4.3所示.
表4.3
次序
算法
有无Belady异态
1
Optimal
无
2
LRU
无
3
Second Chance
有
4
FIFO
有
21.答:在本题中,一页大小为2048字节,则逻辑地址4865的页号及页内位移为:
页号 P为：4865/2048=2
页内位移W为：4865-2048×2=769
然后,通过页表查知物理块号为6,将物理块号与逻辑地址中的页内位移拼接,形成物理地址,即:6×2048=13057其地址变幻过程如图5.13所示。
越界页表寄存器 逻辑地址页表始址
页表长度
2
769
页号 块号
0
2
1
4
2
6
3
8
2
769
22,答:一个进程在时间t的工作集可形式化地定义为:
W(t,h)={在时间t-h到t之间所访问的一串页面}
其中,h为工作集窗口尺寸。
由题目所给条件可知,t1时刻的工作集为:{1,2,3,6,7,8,9}
t2时刻的工作集为:{3,4}
