第四章 存储器管理

null第四章 存储器管理第四章 存储器管理null4.1 存储器的层次结构 4.1.1 多级存储器结构 对于通用计算机而言，存储层次至少应具有三级： 最高层为CPU寄存器， 中间为主存， 最底层是辅存。 在较高档的计算机中，还可以根据具体的功能分工细划为 寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6层。如图4-1所示，null在存储层次中越往上，存储介质的访问速度越快，价格也越 高，相对存储容量也越小。其中，寄存器、高速缓存、主存储 器和磁盘缓存均属于操作系统存储管理的管辖范畴，掉电后它 们存储的信息不再存在。固定磁盘和可移动存储介质属于设备 管理的管辖范畴，它们存储的信息将被长期保存。 　 null图4-1 计算机系统存储层次示意 null4.1.2 主存储器与寄存器 　　1．主存储器 　　主存储器(简称内存或主存)是计算机系统中一个主要部件，用于保存进程运行时的程序和数据，也称可执行存储器，其容量对于当前的微机系统和大中型机，可能一般为数十MB到数GB，而且容量还在不断增加，而嵌入式计算机系统一般仅有几十KB到几MB。CPU的控制部件只能从主存储器中取得指令和数据，数据能够从主存储器读取并将它们装入到寄存器中，或者从寄存器存入到主存储器。CPU与外围设备交换的信息一般也依托于主存储器地址空间。由于主存储器的访问速度远低于CPU执行指令的速度，为缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存。 null　　2．寄存器 　　寄存器访问速度最快，完全能与CPU协调工作，但价格却十分昂贵，因此容量不可能做得很大。寄存器的长度一般以字(word)为单位。寄存器的数目，对于当前的微机系统和大中型机，可能有几十个甚至上百个；而嵌入式计算机系统一般仅有几个到几十个。寄存器用于加速存储器的访问速度，如用寄存器存放操作数，或用作地址寄存器加快地址转换速度等。 null4.1.3 高速缓存和磁盘缓存 　　1．高速缓存 　　高速缓存是现代计算机结构中的一个重要部件，其容量大于或远大于寄存器，而比内存约小两到三个数量级左右，从几十KB到几MB，访问速度快于主存储器。 　　根据程序执行的局部性原理(即程序在执行时将呈现出局部性规律，在一较短的时间内，程序的执行仅局限于某个部分)，将主存中一些经常访问的信息存放在高速缓存中，减少访问主存储器的次数，可大幅度提高程序执行速度。null通常，进程的程序和数据时存放在主存储器中，每当使用时， 被临时复制到一个速度较快的高速缓存中。当CPU访问一组特 定信息时，首先检查它是否在高速缓存中，如果已存在，可直 接从中取出使用，以避免访问主存，否则，再从主存中读出信 息。null　　2．磁盘缓存 　　由于目前磁盘的I/O速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。磁盘缓存本身并不是一种实际存在的存储介质，它依托于固定磁盘，提供对主存储器存储空间的扩充，即利用主存中的存储空间，来暂存从磁盘中读出(或写入)的信息。主存也可以看做是辅存的高速缓存，因为，辅存中的数据必须复制到主存方能使用；反之，数据也必须先存在主存中，才能输出到辅存。 null　　一个文件的数据可能出现在存储器层次的不同级别中，例如，一个文件数据通常被存储在辅存中(如硬盘)，当其需要运行或被访问时，就必须调入主存，也可以暂时存放在主存的磁盘高速缓存中。大容量的辅存常常使用磁盘，磁盘数据经常备份到磁带或可移动磁盘组上，以防止硬盘故障时丢失数据。有些系统自动地把老文件数据从辅存转储到海量存储器中，如磁带上，这样做还能降低存储价格。 4.2 程序的装入和链接4.2 程序的装入和链接在多道程序环境下，程序要运行必须为之创建进程，而创建进 程的第一件事，就是要将程序和数据装入内存。如何将一个用 户源程序变为一个可在内存中执行的程序， 通常要经过以下几步 （1）编译。由编译程序（Compiler）将用户源代码编译成若干 个目标模块（Object Module）； （2）链接。由链接程序（Linker）将编译后形成的目标模块以 及它们所需要的库函数，链接在一起，形成一个装入模块 （Load Module）； （3）装入。由装入程序（Loader）将装入模块装入内存。 null图4-2　对用户程序的处理步骤 null4.2.1 程序的装入 一、绝对装入方式（Absolute Loading Mode） 绝对装入程序按照装入模块中的地址,将程序和数据装入内存. 装入模块被装入内存后,由于程序中的逻辑地址与实际内存地址 完全相同,故不须对程序和数据的地址进行修改。 二、可重定位装入方式（Relocatable Loading Mode） 绝对装入方式只适用于单道程序环境 在多道程序环境下，所得到的目标模块的起始地址通常是从0 开始的，程序中的其他地址也都是相对于起始地址计算的，此 时应采用可重定位装入方式，根据内存的当前情况，将装入模 块装入到内存的适当位置。null注意：作业地址空间到内存地址空间的转换 例：图4-3（见下页） 重定位：在装入时对目标程序中指令和数据的修改过程 静态重定位 null图4-3　作业装入内存时的情况null 三、动态运行时装入方式（Dynamic Run-Time Loading） 动态运行时的装入程序，在把装入模块装入内存后，并不立即 把装入模块中的相对地址转换为绝对地址，而是把这种地址转 换推迟到程序真正要执行时才进行。因此，装入内存后的所有 地址都仍是相对地址。 重定位寄存器null4.2.2 程序的链接 一、静态链接 在程序运行之前，先将各目标模块及它们所需的库函数，链接 成一个完整的装配模块，以后不再拆开。 在将几个目标模块链接装配成一个装入模块时，需要解决以下 两个问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ： 1．对相对地址进行修改 2．变换外部调用符号 例：图4-4 null图 4-4　程序链接示意图 null二、装入时动态链接（Load-Time Dynamic Linking） 用户源程序经编译后所得的目标模块，是在装入内存时，边装 入边链接的，即在装入一个目标模块时，若发生一个外部模块 调用事件，将引起装入程序去找出相应的外部目标模块，并将 它装入内存。 装入时动态链接方式有以下优点： 1．便于修改和更新 2．便于实现目标模块共享null三、运行时动态链接（Run-Time Dynamic Linking） 将对某些模块的链接推迟到执行时才执行，亦即，在执行过程 中，当发现一个被调用模块尚未装入内存时，立即由OS去找到 该模块并将之装入内存，把它链接到调用者模块上。凡在执行 过程中未被用到的目标模块，都不会被调入内存和被链接到装 入模块上。4.3 连续分配方式4.3 连续分配方式连续分配是指为一个用户程序分配一个连续的内存空间。 4.2.1 单一连续分配 这是最简单的一种存储管理方式，但只能用于单用户、单任务 的操作系统中。采用这种存储管理方式时，内存分为以下两个 分区： （1）系统区。 （2）用户区。null4.3.2 固定分区分配 一、划分分区的 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 将内存空间划为若干个固定大小的分区，可用下述两种方法： 1．分区大小相等 即使所有的内存分区大小相等。其缺点是缺乏灵活性，即当程 序太小时，会造成内存空间的浪费；当程序太大时，一个分区 又不足以装入该程序，致使该程序无法运行。尽管如此，这种 划分方式仍被用于利用一台计算机去控制多个相同对象的场 合，因为这些对象所需的内存空间是大小相等的。例如，炉温 群控系统，就是利用一台计算机去控制多台相同的冶炼炉。 null2．分区大小不等 为了克服分区大小相等而缺乏灵活性的这个缺点，可把内存区 划分成含有多个较小的分区、适量的中等分区及少量的大分 区。这样，便可根据程序的大小为之分配适当的分区。 null二、内存分配 为了便于内存分配，通常将分区按大小进行排队，并为之建立 一张分区使用 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf ，其中各表项包括每个分区的起始地址、大小 及状态(是否已分配)，见图4-5(a)所示。当有一用户程序要装入 时，由内存分配程序检索该表，从中找出一个能满足要求的、 尚未分配的分区，将之分配给该程序，然后将该表项中的状态 置为“已分配”；若未找到大小足够的分区，则拒绝为该用户程 序分配内存。存储空间分配情况如图4-5(b)所示。 null图 4-5　固定分区使用表 null4.3.3 动态分区分配 动态分区分配是根据进程的实际需要，动态地为之分配连续的 内存空间。在实现可变分区分配存储管理方式时，必须解决下 述三个问题： （1）分区分配中所用的数据结构； （2）分区的分配算法； （3）分区的分配和回收操作。 null—、分区分配中的数据结构 (1) 空闲分区表。在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区序号、分区始址及分区的大小等数据项。 (2) 空闲分区链。为了实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针；在分区尾部则设置一后向指针，通过前、后向链接指针，可将所有的空闲分区链接成一个双向链，如图4-6所示。为了检索方便，在分区尾部重复设置状态位和分区大小表目。当分区被分配出去以后，把状态位由“0”改为“1”，此时，前、后向指针已无意义。 null图4-6　空闲链结构 null　　2．分区分配算法 　　1) 首次适应算法(first fit) 　　我们以空闲分区链为例来说明采用FF算法时的分配情况。FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区。这给为以后到达的大作业分配大的内存空间创造了条件。其缺点是低址部分不断被划分，会留下许多难以利用的、很小的空闲分区，而每次查找又都是从低址部分开始，这无疑会增加查找可用空闲分区时的开销。 null　　2) 循环首次适应算法(next fit) 　　该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。为实现该算法，应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式，即如果最后一个(链尾)空闲分区的大小仍不能满足要求，则应返回到第一个空闲分区，比较其大小是否满足要求。找到后，应调整起始查寻指针。该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区。 null　　3) 最佳适应算法(best fit) 　　所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。这样，第一次找到的能满足要求的空闲区，必然是最佳的。孤立地看，最佳适应算法似乎是最佳的，然而在宏观上却不一定。因为每次分配后所切割下来的剩余部分总是最小的，这样，在存储器中会留下许多难以利用的小空闲区。 null　　4) 最坏适应算法(worst fit) 　　最坏适应分配算法要扫描整个空闲分区表或链表，总是挑选一个最大的空闲区分割给作业使用，其优点是可使剩下的空闲区不至于太小，产生碎片的几率最小，对中、小作业有利，同时最坏适应分配算法查找效率很高。该算法要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。但是该算法的缺点也是明显的，它会使存储器中缺乏大的空闲分区。最坏适应算法与前面所述的首次适应算法、循环首次适应算法、最佳适应算法一起，也称为顺序搜索法。 null　　5) 快速适应算法(quick fit) 　　该算法又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，这样，系统中存在多个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。空闲分区的分类是根据进程常用的空间大小进行划分，如2 KB、4 KB、8 KB等，对于其它大小的分区，如7 KB这样的空闲区，既可以放在8 KB的链表中，也可以放在一个特殊的空闲区链表中。 null　　该算法的优点是查找效率高，仅需要根据进程的长度，寻找到能容纳它的最小空闲区链表，并取下第一块进行分配即可。另外该算法在进行空闲分区分配时，不会对任何分区产生分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片。 　　该算法的缺点是在分区归还主存时算法复杂，系统开销较大。此外，该算法在分配空闲分区时是以进程为单位，一个分区只属于一个进程，因此在为进程所分配的一个分区中，或多或少地存在一定的浪费。空闲分区划分越细，浪费则越严重，整体上会造成可观的存储空间浪费，这是典型的以空间换时间的作法。 null　　3．分区分配操作 　　1) 分配内存 　　系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为u.size，表中每个空闲分区的大小可表示为m.size。若m.size-u.size≤size(size是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分配给请求者；否则(即多余部分超过size)，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链(表)中。然后，将分配区的首址返回给调用者。图4-7示出了分配流程。 null图 4-7　内存分配流程 null　　2) 回收内存 　　当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一： 　　(1) 回收区与插入点的前一个空闲分区F1相邻接，见图4-8(a)。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。 　　(2) 回收分区与插入点的后一空闲分区F2相邻接，见图4-8(b)。此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。 null　　(3) 回收区同时与插入点的前、后两个分区邻接，见图4-8(c)。此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。 　　(4) 回收区既不与F1邻接，又不与F2邻接。这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。 null图 4-8　内存回收时的情况 F2null4.3.4　伙伴系统 　　固定分区和动态分区方式都有不足之处。固定分区方式限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，内存空间利用率很低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙伴系统方式是对以上两种内存方式的一种折衷方案。 　　伙伴系统规定，无论已分配分区或空闲分区，其大小均为2的k次幂，k为整数，l≤k≤m，其中：21表示分配的最小分区的大小，2m表示分配的最大分区的大小，通常2m是整个可分配内存的大小。 null　　假设系统的可利用空间容量为2m个字，则系统开始运行时，整个内存区是一个大小为2m的空闲分区。在系统运行过程中，由于不断的划分，可能会形成若干个不连续的空闲分区，将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了k(0≤k≤m)个空闲分区链表。 null　　当需要为进程分配一个长度为n的存储空间时，首先计算一个i值，使2i－1 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 。如果页面大小仍采用4 KB即212 B，那么还剩下52位，假定仍按物理块的大小(212位)来划分页表，则将余下的42位用于外层页号。此时在外层页表中可能有4096 G个页表项，要占用16 384 GB的连续内存空间。这样的结果显然是不能令人接受的，因此必须采用多级页表，将外层页表再进行分页，也就是将各分页离散地装入到不相邻接的物理块中，再利用第2级的外层页表来映射它们之间的关系。 　　null4.5　基本分段存储管理方式 4.5.1　分段存储管理方式的引入 　　1) 方便编程 　　通常，用户把自己的作业按照逻辑关系划分为若干个段，每个段都是从0开始编址，并有自己的名字和长度。因此，希望要访问的逻辑地址是由段名(段号)和段内偏移量(段内地址)决定的。例如，下述的两条指令便是使用段名和段内地址： LOAD 1，[A] |〈D〉； STORE 1，[B] |〈C〉； 其中，前一条指令的含义是将分段A中D单元内的值读入寄存器1；后一条指令的含义是将寄存器1的内容存入B分段的C单元中。 null　　2) 信息共享 　　在实现对程序和数据的共享时，是以信息的逻辑单位为基础的。比如，共享某个例程和函数。分页系统中的“页”只是存放信息的物理单位(块)，并无完整的意义，不便于实现共享；然而段却是信息的逻辑单位。由此可知，为了实现段的共享，希望存储管理能与用户程序分段的组织方式相适应。 null　　3) 信息保护 　　信息保护同样是对信息的逻辑单位进行保护，因此，分段管理方式能更有效和方便地实现信息保护功能。 　　4) 动态增长 　　在实际应用中，往往有些段，特别是数据段，在使用过程中会不断地增长，而事先又无法确切地知道数据段会增长到多大。前述的其它几种存储管理方式，都难以应付这种动态增长的情况，而分段存储管理方式却能较好地解决这一问题。 　　null　　5) 动态链接 　　动态链接是指在作业运行之前，并不把几个目标程序段链接起来。要运行时，先将主程序所对应的目标程序装入内存并启动运行，当运行过程中又需要调用某段时，才将该段(目标程序)调入内存并进行链接。可见，动态链接也要求以段作为管理的单位。 null4.5.2　分段系统的基本原理 　　1. 分段 　　在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。例如，有主程序段MAIN、子程序段X、数据段D及栈段S等，如图4-17所示。每个段都有自己的名字。为了实现简单起见，通常可用一个段号来代替段名，每个段都从0开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。整个作业的地址空间由于是分成多个段，因而是二维的，亦即，其逻辑地址由段号(段名)和段内地址所组成。 　null分段地址中的地址具有如下结构： null　　2．段表 　　在前面所介绍的动态分区分配方式中，系统为整个进程分配一个连续的内存空间。而在分段式存储管理系统中，则是为每个分段分配一个连续的分区，而进程中的各个段可以离散地移入内存中不同的分区中。为使程序能正常运行，亦即，能从物理内存中找出每个逻辑段所对应的位置，应像分页系统那样，在系统中为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项，其中记录了该段在内存中的起始地址(又称为“基址”)和段的长度，如图4-17 所示。段表可以存放在一组寄存器中，这样有利于提高地址转换速度，但更常见的是将段表放在内存中。 null图4-17　利用段表实现地址映射 null　　3．地址变换机构 　　为了实现从进程的逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器，用于存放段表始址和段表长度TL。在进行地址变换时，系统将逻辑地址中的段号与段表长度TL进行比较。若S>TL，表示段号太大，是访问越界，于是产生越界中断信号；若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存的起始地址，然后，再检查段内地址d是否超过该段的段长SL。若超过，即d>SL，同样发出越界中断信号；若未越界，则将该段的基址d与段内地址相加，即可得到要访问的内存物理地址。 　　图4-18示出了分段系统的地址变换过程。 　　null图4-18　分段系统的地址变换过程 null　　像分页系统一样，当段表放在内存中时，每要访问一个数据，都须访问两次内存，从而极大地降低了计算机的速率。解决的方法也和分页系统类似，再增设一个联想存储器，用于保存最近常用的段表项。由于一般情况是段比页大，因而段表项的数目比页表项的数目少，其所需的联想存储器也相对较小，便可以显著地减少存取数据的时间，比起没有地址变换的常规存储器的存取速度来仅慢约10%～15%。 null　　4．分页和分段的主要区别 　　由上所述不难看出，分页和分段系统有许多相似之处。比如，两者都采用离散分配方式，且都要通过地址映射机构来实现地址变换。但在概念上两者完全不同，主要表现在下述三个方面。 　　(1) 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。 null　　(2) 页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。 　　(3) 分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。 null4.5.3　信息共享 　　分段系统的一个突出优点，是易于实现段的共享，即允许若干个进程共享一个或多个分段，且对段的保护也十分简单易行。在分页系统中，虽然也能实现程序和数据的共享，但远不如分段系统来得方便。我们通过一个例子来说明这个问题。例如，有一个多用户系统，可同时接纳40个用户，他们都执行一个文本编辑程序(Text Editor)。如果文本编辑程序有160 KB的代码和另外40 KB的数据区，则总共需有 8 MB的内存空间来支持40个用户。如果160 KB的代码是可重入的(Reentrant)，则无论是在分页系统还是在分段系统中，该代码都能被共享，在内存中只需保留一份文本编辑程序的副本，此时所需的内存空间仅为1760 KB(40×40+160)，而不是8000 KB。 null　　假定每个页面的大小为4 KB，那么，160 KB的代码将占用40个页面，数据区占10个页面。为实现代码的共享，应在每个进程的页表中都建立40个页表项，它们的物理块号都是21#～60#。在每个进程的页表中，还须为自己的数据区建立页表项，它们的物理块号分别是61#～70#、71#～80#、81#～90#，…，等等。图4-19是分页系统中共享editor的示意图。 null图4-19　分页系统中共享editor的示意图 null　　在分段系统中，实现共享则容易得多，只需在每个进程的段表中为文本编辑程序设置一个段表项。图4-20是分段系统中共享editor的示意图。 图 4-20　分段系统中共享editor的示意图 null4.5.4　段页式存储管理方式 　　1．基本原理 　　段页式系统的基本原理，是分段和分页原理的结合，即先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。图4-21示出了一个作业地址空间的结构。该作业有三个段，页面大小为4 KB。在段页式系统中，其地址结构由段号、段内页号及页内地址三部分所组成，如图4-22所示。 null图 4-21　作业地址空间和地址结构 null图4-22　利用段表和页表实现地址映射 null　　2．地址变换过程 　　在段页式系统中，为了便于实现地址变换，须配置一个段表寄存器，其中存放段表始址和段表长TL。进行地址变换时，首先利用段号S，将它与段表长TL进行比较。若S 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 语言(如FORTRAN语言、PASCAL语言)及C语言规律的研究中被证实。 　null　　(2) 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但经研究看出，过程调用的深度在大多数情况下都不超过5。这就是说，程序将会在一段时间内都局限在这些过程的范围内运行。 　　(3) 程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行。 　　(4) 程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内。 null　　局限性还表现在下述两个方面： 　　(1) 时间局限性。如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问。产生时间局限性的典型原因是由于在程序中存在着大量的循环操作。 　　(2) 空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。 null　　3．虚拟存储器的定义 　　基于局部性原理，应用程序在运行之前，没有必要全部装入内存，仅须将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂留在盘上。程序在运行时，如果它所要访问的页(段)已调入内存，便可继续执行下去；但如果程序所要访问的页(段)尚未调入内存(称为缺页或缺段)，此时程序应利用OS所提供的请求调页(段)功能，将它们调入内存，以使进程能继续执行下去。如果此时内存已满，无法再装入新的页(段)，则还须再利用页(段)的置换功能，将内存中暂时不用的页(段)调至盘上，腾出足够的内存空间后，再将要访问的页(段)调入内存，使程序继续执行下去。null这样，便可以使一个大的用户程序能在较小的内存空间中运 行；也可以在内存中同时装入更多的进程使它们并发执行。从 用户的角度看，该系统所具有的内存容量，将比实际内存容量 大得多。但用户所看到的大容量只是一种感觉，是虚的，所以 人们把这样的存储器成为虚拟存储器。 所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻 辑上对内存容量加以扩充的一种存储器系统。null4.6.2　虚拟存储器的实现方法 　　1．分页请求系统 　　这是在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允许只装入少数页面的程序(及数据)，便启动运行。以后，再通过调页功能及页面置换功能，陆续地把即将要运行的页面调入内存，同时把暂不运行的页面换出到外存上。置换时以页面为单位。为了能实现请求调页和置换功能，系统必须提供必要的硬件支持和相应的软件。 null　　1) 硬件支持 　　主要的硬件支持有： 　　① 请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构； 　　② 缺页中断机构，即每当用户程序要访问的页面尚未调入内存时，便产生一缺页中断，以请求OS将所缺的页调入内存； 　　③ 地址变换机构，它同样是在纯分页地址变换机构的基础上发展形成的。 2) 实现请求分页的软件 null　　2．请求分段系统 　　这是在分段系统的基础上，增加了请求调段及分段置换功能后所形成的段式虚拟存储系统。它允许只装入少数段(而非所有的段)的用户程序和数据，即可启动运行。以后再通过调段功能和段的置换功能将暂不运行的段调出，同时调入即将运行的段。置换是以段为单位进行的。null　　为了实现请求分段，系统同样需要必要的硬件支持。一般需要下列支持： 　　(1) 请求分段的段表机制。这是在纯分段的段表机制基础上增加若干项而形成的。 　　(2) 缺段中断机构。每当用户程序所要访问的段尚未调入内存时，产生一个缺段中断，请求OS将所缺的段调入内存。 　　(3) 地址变换机构。 null4.6.3　虚拟存储器的特征 　　1．多次性 　　多次性是指一个作业被分成多次调入内存运行，亦即在作业运行时没有必要将其全部装入，只需将当前要运行的那部分程序和数据装入内存即可；以后每当要运行到尚未调入的那部分程序时，再将它调入。多次性是虚拟存储器最重要的特征，任何其它的存储管理方式都不具有这一特征。null　　2．对换性 　　对换性是指允许在作业的运行过程中进行换进、换出，亦即，在进程运行期间，允许将那些暂不使用的程序和数据，从内存调至外存的对换区(换出)，待以后需要时再将它们从外存调至内存(换进)；甚至还允许将暂时不运行的进程调至外存，待它们重又具备运行条件时再调入内存。换进和换出能有效地提高内存利用率。null　　3．虚拟性 　　虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。这是虚拟存储器所表现出来的最重要的特征，也是实现虚拟存储器的最重要的目标。 　　值得说明的是，虚拟性是以多次性和对换性为基础的，或者说，仅当系统允许将作业分多次调入内存，并能将内存中暂时不运行的程序和数据换至盘上时，才有可能实现虚拟存储器；而多次性和对换性又必须建立在离散分配的基础上。 null4.7　请求分页存储管理方式 4.7.1　请求分页中的硬件支持 　　1．页表机制 　　在请求分页系统中所需要的主要数据结构是页表。其基本作用仍然是将用户地址空间中的逻辑地址变换为内存空间中的物理地址。由于只将应用程序的一部分调入内存，还有一部分仍在盘上，故须在页表中再增加若干项，供程序(数据)在换进、换出时参考。在请求分页系统中的每个页表项如下所示： null　　现对其中各字段说明如下： 　　(1) 状态位P：用于指示该页是否已调入内存，供程序访问时参考。 　　(2) 访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供选择换出页面时参考。null　　(3) 修改位M：表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不需再将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。简言之，M位供置换页面时参考。 　　(4) 外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。 null　　2．缺页中断机构 　　在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。缺页中断作为中断，它们同样需要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤。但缺页中断又是一种特殊的中断，它与一般的中断相比，有着明显的区别，主要表现在下面两个方面： 　　(1) 在指令执行期间产生和处理中断信号。通常，CPU都是在一条指令执行完后，才检查是否有中断请求到达。若有，便去响应，否则，继续执行下一条指令。然而，缺页中断是在指令执行期间，发现所要访问的指令或数据不在内存时所产生和处理的。 null　　(2) 一条指令在执行期间，可能产生多次缺页中断。在图4-24中示出了一个例子。如在执行一条指令COPY A TO B时，