操作系统原理：第五章 存储器管理学习辅导资料

第五章存储器管理5.1知识点汇总1、存储器的层次操作系统的内存管理功能，使之操作系统中负责管理内存使用的那部分功能子集，又称主存管理。 在现代计算机系统中，存储器是信息外理的来源与归宿，占据重要位置。但是，在现有技术条件下，任何一种存储装置，都无法同时从速度与容量两方面，满足用户的需求。实际上它们组成了一个速度由快到慢，容量由小到大的存储装置层次。图5-1三级存储器结构2、内存管理的目的主存的分配和管理：当用户需要内存时,系统为之分配相应的存储空间；不需要时，及时回收，以供其它用户使用。提高主存储器的利用率：不仅能使多道程序动态地共享主存，提高主存利用率，最好还能共享主存中某个区域的信息。“扩充”主存容量：为用户提供比主存物理空间大得多的地址空间，以至使用户感觉他的作业是在这样一个大的存储器中运行。(虚拟内存技术)存储保护：确保多道程序都在各自分配到存储区域内操作，互不干扰，防止一道程序破坏其它作业或系统文件的信息。 程序的各个阶段：编辑―――编译―――链接―――装入―――运行1).编辑阶段：创建源文件2).编译阶段：生成目标文件3).连接阶段：生成可执行文件4).装入阶段：重定位，装入内存5).运行阶段：得到结果图5-2程序的各个阶段3、存储器管理的功能存储器管理的功能：内存分配、地址映射、内存保护、内存扩充。4、存储器有关概念地址空间：程序用来访问信息所用地址单元的集合。逻辑（相对）地址的集合。由编译程序生成存储空间：主存中物理单元的集合物理（绝对）地址的集合由装配程序等生成（1）逻辑地址（相对地址，虚地址）用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都相对于首地址而编址。不能用逻辑地址在内存中读取信息（2）物理地址（绝对地址，实地址）：内存中各物理单元的地址是从统一的基地址顺序编址。（3）重定位：把作业地址空间中使用的逻辑地址变换成内存空间中的物理地址的过程。又称地址映射。1）绝对装入：编译后，装入前已产生了绝对地址（内存地址），装入时不再作地址重定位。绝对地址的产生：（1）由编译器完成，编程时使用符号地址（2）由程序员编程完成。 程序中所使用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。但在由程序员直接给出绝对地址时，不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。2）静态重定位：是在目标程序装入内存时，由装入程序对目标程序中的指令和数据的地址进行修改，即把程序的逻辑地址都改成实际的内存地址。重定位在程序装入时一次完成。图5-3程序静态运行3) 动态运行时装入：（动态重定位）在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。 图5-4动态重定位示意图 （4）程序的链接 1）静态链接：对相对地址的修改，变换外部调用符号。 图5-5程序的静态链接2）装入时动态链接：便于修改和更新，便于实现对目标模块的共享。（DLL动态链接库） 3）运行时动态链接：这种链接方式是将对某些模块的链接推迟到执行时才执行，即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。4)碎片：内存中容量太小、无法被利用的小分区。5、内存管理技术-分区管理三种基本的存储管理技术：分区法、可重定位分区法和对换技术（1）分区法：把内存划分成若干分区，每个分区里容纳一个作业。1）固定分区模式（定长分区模式）：是将内存用户区域划分为几个固定大小的区域，在系统运行过程中，每个区域任意时刻只存放一个程序，且连续完整存放。 通过设置内存分配表，内存分配简单，但内存利用率不高 分区的分配策略： 最先适配，任何时刻只要一个分区变成空闲的，队列中的第一个可装入的作业就被装入执行，经常把大分区分给小作业。 最优适配，一旦某分区变成空闲，便寻找可装入的最大作业，有待大作业而其实小作业，与优待小作业的处理机调度算法相互抵触。 固定分区在内存利用率上存在的问题：分区经常没有被填满。因为分区的大小是固定的，所以分给进程的多余存储空间将被浪费。被浪费的空间成为内部存储碎片。存在所有空闲分区总合够，但每个空闲分区太小而无法装入的现象。多道并行的程序数量受到分区数量的限制。2)动态分区 将内存用户区划分为若干个分区，每个分区内任意时刻只有一个程序，且为连续完整存放。但划分的实际、大小和位置时动态的，即在系统运行从开机到关机这段时间内，各分区的大小、位置等划分情况，是根据用户程序的来去而变化的。 动态分区的策略：=1\*GB3①必须维持一张内存空闲区表和已分配区表来动态地跟踪记录内存空闲块和已用块的分布情况。图5-6内存动态分区=2\*GB3②分配策略最先适配。为作业选择分区时总是按地址从高到低搜索，只要找到可以容纳该作业的空白块，就把该空白块分配给该作业。下次适配。总是从上次查找结束的地方开始，找到一个足够大的空白区分配。最佳适配。接到内存申请时，在空闲块表中找到一个不小于请求的最小空块进行分配，为作业选择分区时总是寻找其大小最接近于作业所要求的存储区域。特点：用最小空间满足要求。最坏适配。接到内存申请时，在空闲块表中找到一个不小于请求的最大空块进行分配，与最佳适应法相反，它在作业选择存储块时，总是寻找最大的空白区。特点：当分割后空闲块仍为较大空块快速适配=3\*GB3③分配多大的空闲块恰好分配法：分配大小正好是进程所需要的长度，适合无动态扩充要求的进程。预留空间法：分的大小大于进程的长度，适用于由动态扩充要求的进程。可变分区模式的特点相对于固定分区模式，工作复杂化了。相对于固定分区模式，提高地内存空间利用率，但仍存在空间的浪费，。主要是外部存储碎片，也存在内部存储碎片。 外部存储碎片。小的分不出去的空闲块。以及党内存所有空闲块长度之和足够装入一个进程，但各个空闲块长度都不够装入该进程时，称这些空闲块为外部存储碎片。 内部存储碎片。在已分配给某个进程的空间中，未被使用而被浪费的部分空间，称为内部碎片。6、虚拟存储器（1）虚拟存储器：是由操作系统提供的一个假想的特大存储器（2）虚拟存储器的基本特征：1)虚拟扩充：不是物理上，而是逻辑上扩充了内存容量2)部分装入：每个作业不是全部一次性地装入内存，而是只装入一部分3)离散分配：不必占用连续的空间，而是“见缝插针”。4)多次对换：所需的全部程序和数据要分成多次调入内存（3）虚拟存储器受到的限制：1)指令中表示地址的字长2)外存的容量7、页式内存管理将内存固定划分为等长的页面（物理页，frame）。将程序也划分为等长的页（逻辑页，logicalframe）。将程序的各页装入内存各空闲的页面。程序的逻辑编址是一维连续编址，即逻辑页是连续的。而存放到内存中的物理页时则不一定是连续的。 页模式分为：静态（实存）页式，要求程序要一次全部装入。动态（虚存）页式，程序可以不一次性全部装入。 在页式管理中，程序的逻辑地址分为页号和页内偏移两部分。（1）实存页式的基本工作过程与结构 由于内存空闲页面是动态随机分布的，所以需要一个数据结构来随时记录内存中哪些页面是空闲的，称为内存页表。通常采用位图的方式记录内存的使用情况。 图5-7内存页表由于一个程序的所有页对应的内存页面时随即分散的，因此存在运行时动态重定位的需要，这就需要为每个进程建立一张表，反映该进程在内存的分布情况，称为进程页表。其中列出了作业的逻辑地址与其在主存中的物理地址间的对应关系。表中的每一行称为页描述子 图5-8进程页表当一个要建立一个进程时。首先要得到进程所需长度（页数）。然后将空闲页分配给该进程，将使用到的空闲页号记录到进程页表，并修改内存页表。（2）虚存页式的基本工作过程与结构 虚存技术：虚存是为提高内存利用率而提出的一种技术。在一个操作系统下，不要求任一用户进程所实际占用的内存空间都大于等于该用户进程的逻辑地址空间。而且这种功能的实现对用户透明，则称该操作系统实现了虚存技术。 具体做法：在外存中划分出一块做为虚拟内存。跟内存统一编址，并划分页。当进程建立时，部分页放入真实内存的物理页中，部分页放在虚拟内存的页中。在进程页表中有一项表明该页在内存还是在虚拟内存中。查询进程页表，可以确定要访问的页是否在内存，若不在，则发生缺页中断。将页调入内存。然后再次访问该页。 当要将页调入内存时，发现内存不足，有三种应对策略。1）、等待，等待其他进程执行完毕释放内存，然后取得内存再执行。2）、拒绝，将进程撤销，以后再执行。3）、淘汰，将已经分配在内存空间中，不再使用的页或近期不在使用的页，释放。这称为淘汰技术。页淘汰的工作通常由一个系统进程来完成，称为页淘汰进程。被淘汰的页，被放在外存中，以后需要时再调入内存。在外存中专门存放淘汰页的外存区域称为盘交换区(swaparea,swapplace)。 淘汰策略有：FIFO，在内存中时间最长的页最先被淘汰。在内存时间最长的页，很可能是最长被访问的页。LRU，最近最少使用页被淘汰。每次访存都要对相应页做时间标记，开销很大。NRU，最近未使用页被淘汰（时钟算法）。（3）虚存的作用1）、解决了大程序在小空间内运行的问题。用户所使用的逻辑空间可以比实际内存空间大得多。2）、提高了内存的利用率，增加了多道数，提高了CPU的利用率和系统吞吐量。一个进程的一次执行中，未执行或未访问的那些代码页和数据页，不会进入内存。3）、相对于交换技术，虚存减少了装入或交换所需的I/O量。虚存每次换入换出是以页为单位，而交换技术则是整个进程空间。4）、相对于覆盖技术，程序员不必自己划分覆盖块，简化了编程任务。5）、使用户不必考虑空间大小，不必考虑实际地址。（4）进程页表的实现进程页表的存放1）、进程页表完全放在内存中（完全内存方案） 需要为每个进程建立一个进程页表基址寄存器。每次访问内存时，根据进程页表的基址寄存器值，及逻辑页号，访问当前进程的进程页表。 每次访存，实际上执行了两次访存，一次是访问进程页表，读出页描述子。第二次才是访问所要访问的页。这意味着，用户程序的执行时间将增长一倍，使总的处理速度明显下降。2）、进程页表完全放在一组寄存器中（完全快表方案） 将进程页表完全放在一组高速寄存器中（称为快表）。与上一个方案比，程序执行速度快了一倍。但高速寄存器成本较高，容量有限，不适用于大进程地址空间。3）、进程页表全部放在寄存器中，但部分正在使用的内容放在寄存器中（部分快表方案） 为了解决前面的问题，采用一组高速寄存器，存放当前访问过的页的页描述子。每次访问主存时，首先查找快表，若找到所需的页描述子，则快速形成物理地址。否则从页表中查找后形成物理地址，同时把页描述子写入快表。如果设计得当，快表的命中率可以很高。进程页表两级结构 现代的大多数计算机系统，都支持非常大的逻辑地址空间(232~264)。页表就变得非常大，要占用相当大的内存空间。 例如：一个32位的系统，一个进程的虚拟空间可达2GB，当页长为4KB时，该空间内有2的19次方个页。假如每个物理页的页号要4B,则该进程的页表，需要占用2MB的空间即512页。 因此将进程页表设计成两级结构，分为页目录(外层页)和页表页。图5-9进程两级页表逻辑地址结构如下图：（5）大而稀疏内存使用 之前讨论的进程虚址空间（逻辑地址空间）都是连续编址的。这样不适应用户程序中多处动态伸缩的需要。要适应这种需要，进程虚址空间就必须采用不连续编址。 通常有三种不连续编址方案：段式，段页式，页式稀疏编址。页式下，进程虚址空间的稀疏编址，称为大而稀疏内存使用。用户程序可以随意的指定其数据和代码的虚址空间，可以不连续。 稀疏编址通常都是基于二级页表结构为前提。表现为虚址的怠惰建立风格。在二级页表中表现为页表页的不一次性装入（怠惰建立风格）。无法从页表中获知哪个虚址已被使用。因此要实现稀疏编址需要建立一个数据结构来标识已用的虚址范围。 在页式中存在三次怠惰。第一次，稀疏编址，以怠惰风格分配虚址。第二次，二级页表结构中，页表页的怠惰分配。第三次，发生缺页中断时，怠惰地建立进程的某一页。 三次怠惰都是基于尽量少占用空间资源的思想。（6）页分配策略 1）、何时分配与装入（fetch策略） 立即调页是指在进程开始执行前，即进程建立时分配与装入。 请求调页是指在实际访问某页时才通过发生缺页中断，由缺页中断处理程序分配与装入该页（怠惰）。可能缺页中断次数过多，导致大大减慢进程执行速度。 预先调页是指由操作系统根据一定的算法，动态预测将来最近时间内最可能要访问哪些页，并在这些也被实际访问前就预先分配装入。 虚存页式大都采用后两种，而实存页式都用立即调页。 2）、写时复制 进程的创建时，通常的做法是为自进程重新分配物理空间，并把福进程空间的内容全盘复制到子进程空间中，其开销非常大。为了降低进程创建的开销，提出了写时复制技术：不复制父进程的空间，而是复制父进程的页表，使父进程和子进程共享物理空间，并将这个共享空间的访问权限设置为只读，当福进程和子进程的某一方进行写操作时，发生一个异常，这时才将要写的页进行复制，这样一来某些不被改变的页不被复制，降低了开销。（7）页长和页簇化 注意：页长指的是物理空间中划分的页的长度。页面长指的是逻辑空间中划分的页的长度。 页（面）长通常是2的整数次幂，这可以简化地址映射过程中的逻辑地址分解和物理地址计算。 页（面）长的确定主要考虑：页面大，则内部碎片就大。浪费存储空间和相应的I/O带宽，且启动时间长，但进程页表小，快表(TLB)项数少，快表命中率提高，因此减少了页调入调出次数。 页面长度是由CPU硬件规定的。不同CPU规定的页长不同，如：512b,1kb,2kb,4kb,8kb等等。目前4kb是最常见的。而且同一CPU规定的页长可能多个，这时操作系统通过CPU中的寄存器设置来指定页长。 一般情况下，页长与页面长是一样的，但实际上操作系统页面长可以是页长的整数倍，即用几个相邻的页组成一个页面（称为一簇），并把这样的页面做为最小的分配和映射的逻辑单元。这称为簇化技术。 页簇化，减小了页面管理代价。由于每一簇实际上是几个页，所以每次调页都是几个页同时调，减少了调页的I/O操作次数和缺页中断次数。 页簇化实际上是预先调页的一种情况。即预先调入与所缺页相邻的一些页。（8）工作集和颠簸 工作集:在进程运行的某一时刻，为确保进程能执行下去，在物理存储中必须有的最少页面数。 一个进程在不同时刻需要不同的工作集，当一个进程访问一个不在其工作集中的地址时就会发生缺页中断。当内存负担过重时，进程所分配到的物理存储小于最小工作集，导致连续地，过多地产生缺页中断。并频繁产生刚淘汰的页很快又被调入的情况，称为抖动（颠簸）. 出现颠簸的时候，几乎所有的CPU时间都用于页的调入调出，而不是用于正常的程序执行。 系统对颠簸的处理通常是，选中一个或若干个进程，整个调出内存，直至有足够空闲页面，不再颠簸为止。 如果一个系统不断发生颠簸现象，说明该系统没有安装足够的内存。8、分段存储管理技术（1）、特点将用户程序空间按逻辑划分为几个部分，每一部分称为一段，每个段内连续编址，段间则不一定两续编址。每个程序的逻辑地址空间是二维编址的（段号和段内偏移），这需要便衣程序的支持，但对高级语言程序员通常是透明的。以段为单位，划分进程空间，连续完整存放。即，段内是连续存放，段间不连续存放。段模式分实存段式与虚存段式两种，进程在建立的时候要求全部装入内存，则是实存段式，否则为虚存段式。段式和页式着两种不连续模式的区别在于，如何划分程序的逻辑地址空间。页式是等长划分，是非逻辑的，硬性的，固定的划分。段式是不等长划分，是逻辑的，按照程序的语义和结构进行的，自然的划分。分页与分段的区别分页信息的物理单位大小一样，由系统固定地址空间是一维的分段信息的逻辑单位大小不等，由用户确定地址空间是二维的（2）、用户内存观点 用户将程序看作一个带有许多子例程，过程，函数或模块的主程序，还可能有各种数据结构，表，殊足，栈，变量等。每个模块或数据元素通过名字存取。这些元素中的每个都是变长的。各段中的指令或数据，由他们相对于段首的位移确定。 段式就是支持这种用户内存观点的一种内存管理模式。一个逻辑地址空间是多个段的集合，每个段有一个名字和一个长度，地址由段名和段内位移两部分组成。 每个段可有其逻辑意义及功能，使得便于 1）方便编程； 2）分段共享； 3）分段保护； 4）动态链接； 5）动态增长；（如数据段的增长）（3）、段式的实现 首先，将一个用户程序划分为多个段。因此要每个进程要维护一个进程段表，该表中记录段的逻辑段号，段长度，段地址，其他信息。 以段为单位按照可变分区模式管理。因此与可变分区模式一样，系统中要维护一张内存空闲块表。P165图3.29 段式下逻辑地址由段号和段内偏移两部分组成。 段的划分除了考虑段长和段数因素外，还应考虑保护要求与共享要求。通常段式下一个进程的地址空间包含：代码段。数据段。栈段。共享内存段。其他段。（4）、段式的内存空间利用率和可变分区相比，仍然存在外部存储碎片。与页式比，同样是不连续，但不连续程度没有页式高。虚存段式下，不用到的段，不会进入内存，且用完不再用的，能调出内存，从而节约内存空间段式下也可以通过代码段共享来节省内存空间。（5）、段式存储的保护、共享、内存扩充和评价 段式下的保护机制除了根据段长进行越界检查之外，还可以在进程段表中增加权限位指出每段是只读的，可写的，只执行的灯，每次通过进程段表进行地址映射时，都检查此次内存访问是否符合该段的权限定义。 把保护要求不同的放在不同段，这样就充分实现了一个程序中不同内容的不容保护要求。比如把一个只读数据定义为单独一段。 对于殊足这样需要越界保护的结构也单独一段，自然实现了数组越界的保护。段式的共享 通过不同的进程段表中的某一条记录，指向同一个段地址来实现。段式的动态扩充 由于在逻辑编址上，采用了段号和段内偏移，二维的编址方式，使得段式可以实现多处伸缩。每个段的动态伸缩方式与可变分区类似，手是否有相邻空闲块的限制。对段式的评价 内存利用率比可变分区好，比页式差；保护和共享比之前所谈到的其他模式都好。9段页式存储管理 段页式是段式与页式的结合。利用了二者的优点，互补了二者的缺点。 段页式：将内存划分为等长的页，将每个用户程序先划分为段，再将每段划分为页面，页内必须连续完整存放，但页间可以不连续，也不一定要求所有的页都进入内存。 段页式的实现 每个进程一张进程段表，记录进程中各个段的页表位置。 每个段一张该段的页表，存放该段存放在内存中的各个页的位置。 段页式的评价 基本上结合了段式和页式的优点，克服了二者的缺点。 段页式的内存利用率比段式高，比页式低。段页式消除了段式中的外部碎片，但和页式一样存在内部碎片，其内部碎片比页式多，页式是平均每个程序有半页的内部碎片，而段页式是平均每段有半页内部碎片。 段页式的共享和保护实现与段式一样好，比页式好。 段页式的动态扩充比段式和页式都要好，既不受逻辑编址相邻的限制，也不受物理相邻的限制。 段页式的表空间支出（进程段表，每个段的页表）高，地址映射时间等管理代价比段式与页式都高。10、动态页式管理中的页面置换算法（1）先进先出法（FIFO）：将最先进入内存的页换出内存。例如内存块数量为3时，采用FIFO页面置换算法，下面页面走向情况下，缺页次数是多少？70120304230321201701772222444000777000333222111001110003332221

∴缺页次数=15次(2).最佳置换法（OPT）：将将来不再被使用或是最远的将来才被访问的页例如内存块数量为3时，采用OPT页面置换算法，下面页面走向情况下，缺页次数是多少？70120304230321201701772222227000040001133311∴缺页次数=9次(3).最近最少使用置换法（LRU）：将最近一段时间里最久没有使用过的页面换出内存。例如内存块数量为3时，采用LRU页面置换算法，下面页面走向情况下，缺页次数是多少？70120304230321201701772224440111000000333001133222227∴缺页次数=12次(4).最近未使用置换法（NUR）：是LRU近似方法，比较容易实现，开销也比较小。实现方法：在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1。需要淘汰一页时，把该位为0的页淘汰出去，因为最近一段时间里它未被访问过。5.2例题解析例5.2解引入逻辑地址有如下原因：物理地址的程序只有装入程序所规定的内存空间上才能正确执行，如果程序所规定内存空间不空闲或不存在，程序都无法执行；使用物理地址编程意味着由程序员分配内存空间，这在多道程序系统中，势必造成程序所占内存空间的相互冲突；在多道程序系统中，程序员门无法事先协商每个程序所应占的内存空间的位置，系统也无法保证程序执行时，它所需的内存空间都空闲。基于上述原因，必须引入一个统一的、在编程时使用的地址，它能够在程序执行时根据所分配的内存空间将其转换为对应的物理地址，这个地址就是逻辑地址。逻辑地址的引入为内存的共享、保护和扩充提供方便。例5.2实现容易，无需增加硬件地址变换机构；一般要求为每个程序分配一个连续的存储区；在重定位过程中，装入内存的代码发生了改变；在程序执行期间不在发生地址的变换；在程序执行期间不能移动，且难以做到程序和数据的共享，其内存利用率低。例5.2动态重定位的实现要依靠硬件地址变换机构，且存储管理的软件算法比较复杂；程序代码是按原样装入内存的，在重定位的过程中也不发生变化，重定位产生的物理地址存放在内存地址寄存器中，因此不会改变代码；同一代码中的同一逻辑地址，每执行一次都需要重位一次；只要改变基地址，就可以很容易地实现代码在内存中的移动；动态重定位可以将程序分配到不连续的存储区中；实现虚拟存储器需要动态重定位技术的支持；尽管动态重定位需要硬件支持，但他支持程序浮动，便于利用零散的内存空间，利于实现信息共享和虚拟存储，所以现代计算机大都采用动态重定位。例5.2（1）便于软件版本的修改和更新在采用装入时动态链接方式时，要修改或更新各个目标模块，是件非常容易的事，但对于经静态链接以装配在一起的装入模块，如果要修改或更新其中的某个目标模块时，则要求重新打开装入模块，这不仅是低效的，而且对于普通用户是不可能的。（2）便于实现目标模块共享若采用装入时动态链接方式，OS能够将一个目标模块链接到几个应用程序中去。即实现多个应用程序对该模块的共享；然而，采用静态链接方式时每个应用模块都必须含有该目标模块的拷贝，则无法实现共享。例5.2解覆盖技术与虚拟存储技术的本质不同是：虚拟存储器对于程序员时透明的，不需要程序员了解程序结构、覆盖的区域、时机，不需要精心的设计程序及其数据结构，所有的操作由操作系统自动完成。覆盖的程序段的最大长度要受到物理内存容量的限制，而虚拟存储器的最大长度不受物理内存容量的限制，只受计算机地址结构的限制。交换技术与虚存中使用的调入调出技术相同和不同之处：主要相同点是都要在内存与外存之间交换信息；主要区别在于交换技术换出换进一般是整个进程(proc结构和共享正文段除外)，因此一个进程的大小受物理存储器的限制；而虚存中使用的调入调出技术在内存与外存之间来回传递的是存储页或存储段，而不是整个进程，从而使得进程映射具有了更大的灵活性，且允许进程的大小比可用的物理存储空间大的多。例5.2.7有一计算机系统，内存容量为段号段内地址2920190求其虚拟存储器的实际容量？解虚拟内存的实际大小由系统的逻辑地址结构、主存辅存容量共同决定。虚拟内存容量的理论值是210*220=1G；最大段内地址为220=1M，远大于内存容量，其段长超过512K的内存容量，故最大实际段长为512k而不是1M所以可计算虚拟存储容量为210*512K=210*0.5M=0.5G。0.5G<2G，因此虚拟存储器的实际容量是0.5G例5.2解在段页式系统中，为了获得一条指令或数据，需三次访问内存。第一次访问，是访问内存中的段表，从中取得页表始址；第二次访问，是访问内存中的页表，从中取出逻辑页面对应的内存物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问，才是真正从第二次访问所得的地址中，取出指令或数据。例5.2解实存管理的方法主要分成：用户程序需要占用连续的内存空间，如分区存储管理；用户程序不需要占用连续的内存空间，如分页、分段、段页等管理，一个用户程序在内存可能是不连续的，如果它有不只一页或一段的话。例5.2.解“链接”（link），本应是编译系统的任务，但是，随着程序执行方式的改进，当出现了“动态链接”之后，“程序链接”就不仅仅是编译系统的事情，它还需要OS的支持。程序的静态链接，指的是在程序装入内存之前，由链接程序将已编译好的多个目标模块（.obj文件）链成一个统一的可执行文件。其特点是：①链接好的可执行文件可以重复使用和执行；②被链接的模块一般不可能再拆开，因而不便修改和更新；③不便于多个程序共享某些模块，需使用同一模块的多个程序需分别将该模块链入自己的程序空间。装入时动态链接，指的是在程序加载入内存（准备执行）时，由OS中的装入程序（如exec()）将存放在盘上的诸多目标模块边装入边在内存链接成一个统一的可执行程序。其特点是：①链接好的可执行程序只存在于内存，因而每次执行都要重新链接；②被链接的诸目标模块在盘上是各自独立存放的，因而便于修改；③便于共享，当多个程序需使用同一模块时，该模块在内存只需一个副本。执行时动态链接，是把程序的链接推迟到程序执行时根据执行的需要动态地装入和链接。它除了有与“装入时动态链接”相同的特点外，还有一个显著的特点，是不会将本次执行中不需要的模块（如错误处理模块）装入内存，从而减少时空开销。当然，它也增加了链接的复杂性，且需要一定的硬件支持。动态链接需要OS的支持和服务。例5.2解“重定位”，在实际上指的是这样相互联系的两件事情：一是确定一个待执行程序在内存中的位置；二是将程序中的逻辑地址转换成物理地址。说它们是相互联系的，是因为后一件事情是由前一件事情决定的。静态重定位，指的是在程序装入时实现的重定位。具体的讲，就是将程序装入内存后，立即根据其装入位置将程序中需重定位的逻辑地址转换成物理地址，包括指令地址、数据地址、子程序入口地址等。这种“定位”的特点是“定位”之后，内存中的代码发生了变化，程序不能在内存移动，CPU按物理地址运行程序。动态重定位，是在程序执行的过程中，根据执行的需要动态地装入、链接和定位。它不是根据程序在内存的位置立即将指令和数据的逻辑地址转换成物理地址，而是把这种位置信息送入一个称之为“地址映射机构”的硬件中，然后，CPU按逻辑地址执行程序。在执行中，由“映射机构”将逻辑地址及时地转换成正确的访存物理地址。这种定位方法的主要特点是重定位后，内存中的代码没有发生了变化，允许程序在执行的过程中在内存移动位置，这只要更换“映射机构”中的启址信息就可将同一程序映射到内存不同的地方。这种位置移动对提高内存空间的利用率是有好处的。例5.2解空间分配的“边界要求”，指的是要求所分得的空间的起始地址落在所分得空间的大小的整数倍上。例如，若要求分一个4K大的空间，则实际分得的空间的起始地址应是0，4K，8K，12K，…；有的系统之所以有这种要求，主要是为了便于机器的判断和管理。例如，在分页存储管理系统内，每一个页面在内存的起始地址都应是页面大小的整数倍，这样才能正确地将一个地址划分成页号和页内位移量两部分，并正确地实现分页管理下的地址映射；又如，若为一个数组分配空间，则所分空间的起始地址也应落在数组元素个数（假定一个元素需要偶数个字节）的整数倍上，这样就可以根据当前地址算出当前处理的是第几个元素，并且，当数组中的所有元素都处理一遍后，此时地址的低部分会与数组起始地址的低部分相同，这样，机器就很容易判断该数组已处理完一遍。例5.2.解这是因为用于地址变换的页表或段表也是存放在内存的，为了将CPU给出的逻辑地址变成物理地址，首先就要访问内存的页表和段表，然后，根据形成的物理地址再取指令或数据，这就要两次访存。解决这一问题的办法是提供一个称之为“快表”的硬件，用以存放当前运行进程的页表或段表的部分内容，“快表”的访问时间很快，因此可以节约访问页表和段表的时间。存储器访问具有时间和空间的“局部性”，因此快表的命中率一般可达70%到90%；页表和段表是在系统执行过程中，每时每刻都需要访问的，因此，访问时间的微小缩短，其累计节约的时间却可以达到很大。例5.2.14在分页存储管理系统中，存取一次内存的时间是8us，查询一次快表的时间是1us，缺页中断的时间是求对某一数据进行一次次存取可能需要的时间？现连续对同一页面上的数据进行4次连续读取，求每次读取数据可能需要的时间?解当系统对数据进行存取时，有3种可能性。所存取的数据的页面在内存，其页表项已经存储到快表，此时存取数据的时间是：查询快表的时间+存取内存数据的时间=1us+8us=9us所存取的数据的页面在内存，但是其页表项没有存储到快表，没有命中快表，此时存取数据的时间是：查询页表的时间+存取内存数据的时间=8us+8us=16us所存取的数据的页面不在内存，发生缺页中断，此时存取数据的时间是：查询页表的时间+缺页中断的时间+查询页表的时间+存取内存数据的时间=8us+20us+8us+8us=44us当对某一数据进行4次连续读取时：第1次可能的时间为：1us+8us=9us；8us+8us=16us；8us+20us+8us+8us。②第2次时，对应页面的页表项已经交换到快表中。因为存取是连续的，不存在页面被淘汰的可能性，所以第2次、第3次、第4次的存取时间是一样的，消耗的时间为1us+8us=9us。例5.2解在分页和分段存储管理系统中，多个进程并发运行，共享同一内存块里的程序或数据是可行的。为了实现共享，必须在各共享者的段表或页表中分别有指向共享内存块的表目。对分段式系统，被共享的程序或数据可作为单独的一段。在物理上它是一段，在不同的进程中，可以对应不同的逻辑段，相对来说比较易于实现。对分页管理，则要困难的多。首先，必须保证被共享的程序或数据占有整数块，以便与非共享部分分开。其次，由于共享程序或数据被多个进程访问，所以每个进程对共享程序或数据的访问都应该是有限制条件的。因此，从共享和保护的实现上来看，须共享的程序段或数据段是一个逻辑单位，而分段存储管理中被共享的程序或数据作为一个整体（一段）,实现共享和保护就要方便得多。分段系统的共享是通过两个（或多个）进程的段表之相应表目都指向同一个物理段，并设置共享计数来实现的。每段设置访问方式，就可以实现段的保护。例5.2解主要是因为段是一个有意义的逻辑整体，如主程序、子程序、数据表格、工作空间等，就如书本上的一章或一个自然段。而页只是一个物理尺寸，不一定有完整的意义，如书本上的一页。程序共享当然希望被共享的对象是一个有意义的整体，如一个子程序；至于程序保护，指的是每个进程都应按所拥有的存取权访问不同的程序，而存取权(R,W,E等)当然对一个有完整意义的对象才更有意义。所以就共享和保护而言，分段管理比分页管理更有意义。例5.2解从原理上讲，单道程序设计系统也可实现虚存管理，但从实际上看，虚存主要是应用在多道程序设计系统中。虚存的实现需要程序的动态重定位技术的支持，因为程序的对换会导致同一部分程序多次进出内存并有可能在内存中不断地移动位置。虚存与程序的动态链接没有必然的因果关系，但程序的动态链接可以避免无用的程序进入内存，使虚存的效率提高实现；虚存需要覆盖和交换技术的支持，但覆盖和交换与虚存是不同的概念。在实存管理下覆盖和交换是一种可以节省内存的技术，对用户是不透明，覆盖和交换的区由程序结构和程序员决定。而在虚存下的交换和覆盖对程序员是透明的，操作是由OS根据某种算法决定的。例5.2.18解页面置换算法的异常现象，也叫Belady异常，是在局部置换前提下的一种现象。所谓局部置换，指的是当一进程创建时，分给其一定数量的页面（例如8页），然后，在运行过程中，若该进程需调入新页且须置换一个页面时，则只能置换其自己的一个页面而不能置换别的进程的页面。页面置换的异常现象，是指在一定置换算法和一定页面走向下，分给进程的页面数增多其页面失效率反而增加这样一种情况。这种异常，只在一定的算法和一定的页面走向下才会出现。许多算法，如OPT.和LRU，在任何情况下都不会有异常现象。LRU之所以不会有“异常”，是因为最近的过去使用的n个页面一定在最近的过去使用的n+1个页面之中。例5.2解抖动现象，是在虚存管理下，用于页面（在内、外存之间）对换的时间比程序的有效运行时间还要多的这样一种现象。它可以是一进程内部的局部性抖动，也可以是整个系统的全局性抖动。造成这种情况固然与置换算法和页面走向有关，但其根本原因是多道系统内的进程数太多，从而分给每个进程的页面数太少。因此，解决这一问题的最有效的办法是减少系统内的进程数。Denning于1980年提出了“L=S准则”，即调整系统内的进程数，使得产生缺页的平均间隔时间（L）等于系统处理进程缺页的平均时间（S）。理论和实践表明，此时的CPU利用率最高。例5.2.20有这样一种页面置换算法，它给每一个内存块(块与页大小相等若某进程分得4个内存块，现对1、2、3、4、5、3、4、1、6、7、8、7、8、9、7、8、9、5、4、5、4、2，解答如下问题：求在上述算法下的页面失效数；求在OPT.算法下的页面失效数。解（1）求解过程如下表所示页面号√1√2√3√4√534√1√6√7√878√9789√5√454√2B11111555555888888888882B222222211111199999999B33333336666666665555B4444444777777777444C11111222222333333333334C2011111122222233333333C30011111122222222233333C40001111112222222223333注：打“√”的表示缺页，共有13次缺页。说明：在上面的求解过程中，B1～B4表示进程分得的4个块号，C1～C4表示与这4块对应的计数器；表中的每一列记录了每一块当前装入的页面及其计数器的值。（2）在OPT.算法下的页面失效次数为11。例5.2.21在可变分区分配的存储管理方案中，基于链表的存储分配算法有哪几种？它们的思想是什么？解：在可变式分区分配的存储管理方案中，基于链表的存储分配算法主要有三种：首次适应算法、循环首次适应算法和最佳适应算法。（1）首次适应算法在首次适应算法中，每个空白区按其位置的顺序链在一起，即每个后继的空白区其起始地址总是比前者的大。当系统要分配一个存储块时，就按照空白块链的顺序，一次查询，直到找到第一个满足要求的空白块为止。由这种算法确定的空白块其大小不一定刚好满足要求。如果找到的这个空白区比要求的大，则把它分成两个分区，一个为已分配分区，其大小刚好等于所要求的；另一个仍然为空白块，且留在链中原来的位置上。若是在空白链中从头到尾找一遍，找不到满足要求的空白块，则返回“暂不能分配”。系统在回收一个分区时，首先检查该分区是否有邻接的空白块，如果有，则应将这个分区与之合并，并将该空白块保留在链中原来的位置。如果回收的分区不和空白块邻接，则应根据其起始地址大小，把它插在链中的相应位置上。首次适应算法的实质是，尽可能地利用存储器低地址部分的空白块，尽量保存在高地址部分的大空白块。其优点在于：当需要一个较大的分区时，便有希望找到足够大的空白块以满足要求。其缺点是：在回收一个分区时，需要花费较多的时间去查找链表，确定它的位置。（2）循环首次适应算法循环首次适应算法与首次适应算法类似，只是在每次分配分区时，系统不是从第一个空白块开始查找，而是从上次分配的空白块处查找。当查找至链尾时，便从链首继续查找，直到找完整个链表。在系统回收一个分区时，为了减少在插入一个空白区时查询链表的时间，如果这个分区不和空白块邻接，则把它插入到前向指针链的最后一个空白块后；如果有空白块相邻，则根据情况作相应处理。由此可见，这些空白块在链中的位置没有一定的规则。这种循环首次适应算法的实质是，使得小的空白块均匀地分布在可用存储空间内。这样，当回收一个分区时，它和一个较大空白块相邻的可能性比较大，因而合并后可得到大的空白块。和首次适应算法相比，它产生过小空白块的现象比较小。（3）最佳适应算法在最佳适应算法中，空白块按大小顺序链在一起。系统在寻找空白块时，总是从最小的一个开始。这样，第一次找到的满足要求的空白块必然是最适合的，因为它最接近于要求的大小。这种算法的优点是：如果存储空间中具有正好是所要求大小的空白块，则必然被选中；如果不存在这样的空白块，也只对比要求稍大的空白块划分，而绝不会去划分一个更大的空白块。此后，遇到有大的存储要求时，就比较容易满足了。最佳适应算法的缺点在于：寻找一个较大空白块时花费的时间较长；回收一个分区时，把它插入到空白块链中合适的位置上也较为费时；此外，由于每次都划分一个与要求大小最接近的空白块，使得系统中小的空白块较多。其实质是，在系统中寻找与要求的空间大小最接近的一个空白块。例5.2.22在虚拟页式存储系统为什么要引入缺页中断？缺页中断实现由哪几部分组成，并分别说明其实现方法。解页式虚存管理是在页式存储管理的基础上实现虚拟存储器的，作业在执行时并不是所有的页均放在主存，若欲访问的页面不在主存，则须由操作系统把当前所需页面从辅存装入主存。这一过程就交由中断系统完成，称为缺页中断。缺页中断由缺页处理和页淘汰组成，缺页处理过程如下：中断触发：在地址变换过程中，当查询页表时，发现逻辑页面不在内存，即其状态位为0，则发生缺页中段。页面调入：OS在页表中找到对应页面的辅存地址，进行页面的淘汰，将所缺页调入内存；修改页表：将该页面的内存地址填入页表，修改状态位为1；缺页中断结束，恢复现场，重新执行指令。页面淘汰处理如下：如果内存有空闲的页面，直接调入外存的页面，修改页表；（2）如果内存没有空间，根据页面淘汰算法，在内存中找到可淘汰的页面；（3）如果被淘汰页面修改位为0，则直接调入外存页面将其覆盖，修改页表；（4）如果被淘汰页面修改位为1，则要申请一块交换空间，将该内存的内容保存到交换区中，然后将辅存的页面调入其中，修改页表。例5.2.23何谓虚拟机存储器，并举一例说明操作系统如何实现虚拟内存的？解虚拟存储器通过把主、辅存统一起来管理，给用户造成一种仿佛系统内有巨大主存供用户使用的假象。例如页式存储管理，一道作业被划分成若干页，其中较活跃的几页放在内存，而其余不活跃的页被放在辅存，当需要访问辅存内的页时，就可通过页面调度将其调入内存运行；但用户感觉不到这种变化，他会以为作业的所有部分都存在于主存。这样可以让更多的作业进入主存，提高系统的效率。例5.2.24在内存管理中，“内零头”和“外零头”各指的是什么？在固定式分区分配、可变式分区分配、页式虚拟存储系统、段式虚拟存储系统中，各会存在何种零头？为什么？解内零头（又称内部碎片）：给一个作业分配的存储单元长度为n，该块存储的作业长度为m，则剩下的长度为（n-m）的空间，成为该单元的内部碎片；若存储单元长度为n，在该系统所采用的调度算法下，较长时间内无法选出一道长度不超过该块的作业，则称该块为外零头（外部碎片）。在固定式分区分配中两种零头均会存在，因为空间划分是固定的，无论作业长短，存储单元均不会随之变化，若作业短而存储块长则产生内零头，若作业长而存储块短则产生外零头。在可变式分区分配中只有外零头而无内零头，因为空间划分是依作业长度进行的，是要多少给多少，但剩下的部分太短而无法再分，则称为外零头。页式虚存中会存在内零头而无外零头，因存储空间与作业均分为等长单元，所以不存在无法分配的单元，但作业长度并不刚好为页面大小的整数倍，因此在最后一页会有剩余空间，即为内零头。段式虚存中会存在外零头而无内零头，因段式的空间划分类似于可变分区分配，根据段长分配，要多少给多少，但会剩余小空间无法分配，则为外零头。例5.2.25常用的内存信息保护方法有哪几种？它们各自的特点是什么？解常用的内存保护方法有硬件法、软件法和软硬件结合保护法三种。界地址保护法，即上下界保护法，是一种常用的