|
|
|
对于本知识点，主要考查虚拟存储器（虚存），特别是页式存储管理。所谓虚拟存储技术，即在内存中保留一部分程序或数据，在外存中放置整个地址空间的副本。程序运行过程中可以随机访问内存中的数据或程序，但需要的程序或数据不在内存时，就将内存中部分内容根据情况写回外存，然后从外存调入所需程序或数据，实现作业内部的局部转换，从而允许程序的地址空间大于实际分配的存储区域。它在内存和外存之间建立了层次关系，使得程序能够像访问内存一样访问外存，主要用于解决内存的容量问题。其逻辑容量由内存和外存容量之和以及CPU可寻址的范围来决定，其运行速度接近于内存速度，成本也下降。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型及微型机中。
|
|
|
|
|
|
由进程中的目标代码、数据等的虚拟地址组成的虚拟空间称为虚拟存储器，虚拟存储器允许用户用比内存容量大得多的地址空间来编程，来运行比内存实际容量大得多的程序。用户编程所用的地址称为逻辑地址（虚地址），而实际的内存地址则称为物理地址（实地址）。每次访问内存时都要进行逻辑地址到物理地址的转换，这种转换是由硬件完成的，而内存和外存间的信息动态调度是硬件和操作系统两者配合完成的。
|
|
|
|
（1）静态重定位：静态重定位是在虚空间程序执行之前由装配程序完成地址映射工作。静态重定位的优点是不需要硬件的支持。缺点是无法实现虚拟存储器，必须占用连续的内存空间且难以做到程序和数据的共享。
|
|
|
|
（2）动态重定位：动态重定位是在程序执行过程中，在CPU访问内存之前，将要访问的程序或数据地址转换为内存地址。动态重定位依靠硬件地址变换机构完成，其优点主要有：可以对内存进行非连续分配；提供了虚拟存储器的基础；有利于程序段的共享。
|
|
|
|
|
|
虚拟存储器可以分为单一连续分区、固定分区、可变分区、可重定位分区、非请求页式、请求页式、段页式7种。
|
|
|
|
（1）单一连续分区。把所有用户区都分配给唯一的用户作业，当作业被调度时，进程全部进入内存，一旦完成，所有内存恢复空闲，因此，它不支持多道程序设计。
|
|
|
|
（2）固定分区。这是支持多道程序设计的最简单的存储管理方法，它把内存划分成若干个固定的和大小不同的分区，每个分区能够装入一个作业，分区的大小是固定的，算法简单，但是容易生成较多的存储器碎片。
|
|
|
|
（3）可变分区。引入可变分区后虽然内存分配更灵活，也提高了内存利用率，但是由于系统在不断地分配和回收中，必定会出现一些不连续的小的空闲区，尽管这些小的空闲区的总和超过了某一个作业要求的空间，但是由于不连续而无法分配，产生了碎片。解决碎片的方法是拼接（紧凑），即向一个方向（例如向低地址端）移动已分配的作业，使那些零散的小空闲区在另一方向连成一片。分区的拼接技术，一方面是要求能够对作业进行重定位，另一方面系统在拼接时要耗费较多的时间。
|
|
|
|
（4）可重定位分区。这是克服固定分区碎片问题的一种存储分配方法，它能够把相邻的空闲存储空间合并成一个完整的空区，还能够整理存储器内各个作业的存储位置，以达到消除存储碎片和紧缩存储空间的目的。紧缩工作需要花费大量的时间和系统资源。
|
|
|
|
（5）页式。页式存储组织的基本原理是将各进程的虚拟空间划分为若干个长度相等的页，把内存空间以与页相等的大小划分为大小相等的片或页面，采用请求调页或预调页技术实现内外存的统一管理。页式存储组织的主要优点是利用率高，产生的内存碎片小，内存空间分配及管理简单。主要缺点是要有相应的硬件支持，增加了系统开销；请求调页的算法如选择不当，有可能产生抖动现象。
|
|
|
|
（6）段式：一个作业是由若干个具有逻辑意义的段（如主程序、子程序、数据段等）组成。段式存储管理中，允许程序（作业）占据内存中若干分离的分区。分段系统中的虚地址是一个有序对（段号，段内位移）。系统为每一个作业建立一个段表，其内容包括段号与内存起始地址的对应关系、段长和状态等。状态指出这个段是否已调入内存，若已调入内存，则指出这个段的起始地址位置，状态同时也指出这个段的访问权限。如果该段尚未调入内存，则产生缺段中断，以便装入所需要的段。段式存储管理的主要优点是便于多道程序共享内存，便于对存储器的保护，各段程序修改互不影响。其缺点是内存利用率低，内存碎片浪费大。
|
|
|
|
现在，最常见的虚存组织有分段技术、分页技术、段页式技术3种。我们把这3种存储组织总结如下表所示。
|
|
|
|
|
|
|
|
说明：段内偏移也称为段内地址，页内偏移也称为页内地址。
|
|
|
|
例如：某页式存储系统的地址变换过程如下图所示。假定页面的大小为8K，下图中所示的十进制逻辑地址9612经过地址变换后，形成的物理地址a应为十进制多少呢？
|
|
|
|
|
|
|
|
因为8K=213，所以页内地址有13位。逻辑地址9612转换成二进制，得到10 0101 1000 1100，这里的低13位为页内偏移量，最高一位则为页号，所以逻辑地址9612的页号为1，根据上图的对照表，即物理块号为3（二进制形式为11）。把物理块号和页内偏移地址拼合得到110 0101 1000 1100，再转换为十进制，得到25996。
|
|
|
|
在现行的虚存组织方面，最常见的就是段页式管理。在进行虚实地址转换时，可以采用的公式如下：
|
|
|
|
|
|
其中x为基号，s为段号，p为段内页号，d为页内偏移，n的值为d的总位数，（x）表示x里的内容。
|
|
|
|
|
|
在虚拟存储器的管理中，涉及载入（调入）、放置（放入分区）和置换（swapping）等问题。
|
|
|
|
（1）调入策略：即何时将一页或一段从外存中调入内存，通常有两种策略，一种是请求调入法，即需要使用时才调入；另一种是先行调入法，即将预计要使用的页／段先行调入内存。
|
|
|
|
（2）放置策略：也就是调入后，放在内存的什么位置，这与内存管理基本上是一致的。
|
|
|
|
（3）置换策略：由于实际内存是小于虚存的，因此可能会发生内存中已满，但需要使用的页不在内存中这一情况（称为缺页中断）。这时就需要进行置换，即将一些内存中的页淘汰到外存，腾出空间给要使用的页，这个过程也称为swapping。
|
|
|
|
|
|
|
|
（1）最优（Optimized, OPT）算法：选择淘汰不再使用或最将来才使用的页，这是理想的算法，但难以实现，常用于淘汰算法的比较。
|
|
|
|
（2）随机（rand）算法：随机地选择淘汰的页，开销小，但可能选中立即就要访问的页。
|
|
|
|
（3）先进先出（First In and First Out, FIFO）算法：选择淘汰在内存驻留时间最长的页，似乎合理，但可能淘汰立即要使用的页。另外，使用FIFO算法时，在未给予进程分配足够的页面时，有时会出现给予进程的页面数越多，缺页次数反而增加的异常现象，这称为belady现象。例如，若某个进程访问页面的顺序（称页面访问序列）是432143543215，当进程拥有3个主存页面时，缺页率比拥有4个主存页面时要小。
|
|
|
|
（4）最近最少使用（Least Recently Used, LRU）算法：选择淘汰离当前点时刻最近的一段内使用得最少的页。例如，若某个进程拥有3个主存页面，已访问页面的顺序是4314，现在如果要访问第2页，则需要淘汰第3页，因为第1、4页刚刚使用了。这个算法的主要出发点是，如果某页被访问了，则它可能马上就要被访问。OPT算法和LRU算法都不会发生belady异常现象。
|
|
|
|
|
|
存储管理策略的基础是局部性原理，即进程往往会不均匀地高度局部化地访问内存。局部性分为时间局部性和空间局部性。时间局部性是指最近访问存储位置，很可能不久的将来还要访问；空间局部性是指存储访问有成组的倾向：当访问了某个位置后，很可能也要访问其附近的位置。
|
|
|
|
根据局部性原理的特征性，Denning阐述了程序性能的工作集理论。工作集是进程频繁访问的页面的集合。工作集理论指出，为使进程有效地运行，它的页面工作集应驻留内存中。否则，由于进程频繁地从外存请求页面，而出现称为“颠簸”（抖动）的过度的页面调度活动。此时，处理页面调度的时间超过了程序的执行时间。显然，此时CPU的有效利用率会急速下降。
|
|
|
|
通常用两种等价的方法确定进程的工作集，一种是将工作集确定为在定长的页面访问序列（工作集窗口）中的页面集合，另一种是将工作集确定为在定长时间间隔中涉及到页面的集合。工作集的大小依赖于工作集窗口的大小，在进程执行时，工作集会发生变化。有时，当进程进入另一个完全不同的执行阶段时，工作集会出现显著的变化。不过在一个进程的执行过程中，工作集的大小处于稳定状态的时间基本上占绝大多数。
|
|
|
|
另一种控制颠簸的技术是控制缺页率。操作系统规定缺页率的上下限，当一个进程的缺页率高于上限时，表明该进程需要更大的内存空间，则分配较多的内存页面给它，当进程的缺页率低于下限时，表明该进程占用的内存空间过大，可以适当地收回若干内存页面。
|
|
|
