虚拟存储器

5.1  虚拟存储器概述

  第四章所介绍的各种存储器管理方式有一个共同的特点,即它们都要求将一个作业全部装入内存后方能运行。于是,出现了下面这样两种情况:

  (1) 有的作业很大,其所要求的内存空间超过了内存总容量,作业不能全部被装入内存,致使该作业无法运行;

  (2) 有大量作业要求运行,但由于内存容量不足以容纳所有这些作业,只能将少数作业装入内存让它们先运行,而将其它大量的作业留在外存上等待。

 

5.1.1  常规存储管理方式的特征和局部性原理

  1. 常规存储器管理方式的特征

  我们把前一章中所介绍的各种存储器管理方式统称为传统存储器管理方式,它们全都具有如下两个共同的特征:

  (1) 一次性

  (2) 驻留性

 

  2. 局部性原理

  程序运行时存在的局部性现象,很早就已被人发现,但直到1968年,P.Denning才真正指出:程序在执行时将呈现出局部性规律,即在一较短的时间内,程序的执行仅局限于某个部分,相应地,它所访问的存储空间也局限于某个区域。

  局限性又表现在下述两个方面:

  (1) 时间局限性。

  (2) 空间局限性。

 

  3. 虚拟存储器的基本工作情况

  基于局部性原理可知,应用程序在运行之前没有必要将之全部装入内存,而仅须将那些当前要运行的少数页面或段先装入内存便可运行,其余部分暂留在盘上。

 

5.1.2  虚拟存储器的定义和特征

  1. 虚拟存储器的定义

  当用户看到自己的程序能在系统中正常运行时,他会认为,该系统所具有的内存容量一定比自己的程序大,或者说,用户所感觉到的内存容量会比实际内存容量大得多。但用户所看到的大容量只是一种错觉,是虚的,故人们把这样的存储器称为虚拟存储器。

 

  2. 虚拟存储器的特征

  与传统的存储器管理方式比较,虚拟存储器具有以下三个重要特征:

  (1) 多次性。

  (2) 对换性。

  (3) 虚拟性。

 

5.1.3  虚拟存储器的实现方法

  1. 分页请求系统

  1) 硬件支持

  主要的硬件支持有:

  (1) 请求分页的页表机制。

  (2) 缺页中断机构。

  (3) 地址变换机构。

  2) 实现请求分页的软件

 

  2. 请求分段系统

  1) 硬件支持

  主要的硬件支持有:

  (1) 请求分段的段表机制。

  (2) 缺页中断机构。

  (3) 地址变换机构。

  2) 软件支持

 

5.2  请求分页存储管理方式

5.2.1  请求分页中的硬件支持

  为了实现请求分页,系统必须提供一定的硬件支持。计算机系统除了要求一定容量的内存和外存外,还需要有请求页表机制、缺页中断机构以及地址变换机构。

  1. 请求页表机制

  在请求分页系统中需要的主要数据结构是请求页表,其基本作用仍然是将用户地址空间中的逻辑地址映射为内存空间中的物理地址。为了满足页面换进换出的需要,在请求页表中又增加了四个字段。这样,在请求分页系统中的每个页表应含以下诸项:

 

  2. 缺页中断机构

  (1) 在指令执行期间产生和处理中断信号。

  (2) 一条指令在执行期间可能产生多次缺页中断。

 

图5-1  涉及6次缺页中断的指令

 

  3. 地址变换机构

  请求分页系统中的地址变换机构是在分页系统地址变换机构的基础上,为实现虚拟存储器,再增加了某些功能所形成的,如产生和处理缺页中断,以及从内存中换出一页的功能等等。图5-2示出了请求分页系统中的地址变换过程。

 

 

图5-2 请求分页中的地址变换过程

 

5.2.2  请求分页中的内存分配

  1. 最小物理块数的确定

  一个显而易见的事实是,随着为每个进程所分配的物理块的减少,将使进程在执行中的缺页率上升,从而会降低进程的执行速度。为使进程能有效地工作,应为它分配一定数目的物理块,但这并不是最小物理块数的概念。

 

  2. 内存分配策略

  在请求分页系统中,可采取两种内存分配策略,即固定和可变分配策略。在进行置换时,也可采取两种策略,即全局置换和局部置换。于是可组合出以下三种适用的策略。

  1) 固定分配局部置换(Fixed Allocation,Local Replacement)

  2) 可变分配全局置换(Variable Allocation,Global Replacement)

  3) 可变分配局部置换(Variable Allocation,Local Replacement)

 

  3. 物理块分配算法

  在采用固定分配策略时,如何将系统中可供分配的所有物理块分配给各个进程,可采用下述几种算法:

  (1) 平均分配算法,即将系统中所有可供分配的物理块平均分配给各个进程。

 

  (2) 按比例分配算法,即根据进程的大小按比例分配物理块。如果系统中共有n个进程,每个进程的页面数为Si,

则系统中各进程页面数的总和为:

  又假定系统中可用的物理块总数为m,则每个进程所能分到的物理块数为bi可由下式计算:

 

这里,bi应该取整,它必须大于最小物理块数。

 

  (3) 考虑优先权的分配算法。在实际应用中,为了照顾到重要的、紧迫的作业能尽快地完成,应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分:一部分按比例地分配给各进程;另一部分则根据各进程的优先权进行分配,为高优先进程适当地增加其相应份额。在有的系统中,如重要的实时控制系统,则可能是完全按优先权为各进程分配其物理块的。

 

5.2.3  页面调入策略

  为使进程能够正常运行,必须事先将要执行的那部分程序和数据所在的页面调入内存。现在的问题是:

  (1) 系统应在何时调入所需页面;

  (2) 系统应从何处调入这些页面;

  (3) 是如何进行调入的。

 

  1. 何时调入页面

  (1) 预调页策略。

  (2) 请求调页策略。

 

  2. 从何处调入页面

  (1) 系统拥有足够的对换区空间,这时可以全部从对换区调入所需页面,以提高调页速度。

  (2) 系统缺少足够的对换区空间,这时凡是不会被修改的文件,都直接从文件区调入;而当换出这些页面时,由于它们未被修改,则不必再将它们重写到磁盘(换出),以后再调入时,仍从文件区直接调入。但对于那些可能被修改的部分,在将它们换出时便须调到对换区,以后需要时再从对换区调入。

  (3)  NIX方式。

 

  3. 页面调入过程

  每当程序所要访问的页面未在内存时(存在位为“0”),便向CPU发出一缺页中断,中断处理程序首先保留CPU环境,分析中断原因后转入缺页中断处理程序。

 

  4. 缺页率

  假设一个进程的逻辑空间为n页,系统为其分配的内存物理块数为m(m≤n)。如果在进程的运行过程中,访问页面成功(即所访问页面在内存中)的次数为S,访问页面失败(即所访问页面不在内存中,需要从外存调入)的次数为F,则该进程总的页面访问次数为A    ,那么该进程在其运行过程中的缺页率即为

  事实上,在缺页中断处理时,当由于空间不足,需要置换部分页面到外存时,选择被置换页面还需要考虑到置换的代价,如页面是否被修改过。没有修改过的页面可以直接放弃,而修改过的页面则必须进行保存,所以处理这两种情况时的时间也是不同的。假设被置换的页面被修改的概率是β,其缺页中断处理时间为ta,被置换页面没有被修改的缺页中断时间为tb,那么,缺页中断处理时间的计算公式为

 

 

5.3  页面置换算法

  在进程运行过程中,若其所要访问的页面不在内存,而需把它们调入内存,但内存已无空闲空间时,为了保证该进程能正常运行,系统必须从内存中调出一页程序或数据送到磁盘的对换区中。但应将哪个页面调出,须根据一定的算法来确定。通常,把选择换出页面的算法称为页面置换算法(Page-Replacement Algorithms)。置换算法的好坏将直接影响到系统的性能。

5.3.1  最佳置换算法和先进先出置换算法

  1. 最佳(Optimal)置换算法

  最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法通常可保证获得最低的缺页率。但由于人们目前还无法预知,一个进程在内存的若干个页面中,哪一个页面是未来最长时间内不再被访问的,因而该算法是无法实现的,但可以利用该算法去评价其它算法。

 

图5-3 利用最佳页面置换算法时的置换图

 

  2. 先进先出(FIFO)页面置换算法

  FIFO算法是最早出现的置换算法。该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单,只需把一个进程已调入内存的页面按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应,因为在进程中,有些页面经常被访问,比如,含有全局变量、常用函数、例程等的页面,FIFO算法并不能保证这些页面不被淘汰。

 

图5-4  利用FIFO置换算法时的置换图

 

5.3.2  最近最久未使用和最少使用置换算法

  1.  LRU(Least Recently Used)置换算法的描述

  FIFO置换算法的性能之所以较差,是因为它所依据的条件是各个页面调入内存的时间,而页面调入的先后并不能反映页面的使用情况。最近最久未使用(LRU)的页面置换算法是根据页面调入内存后的使用情况做出决策的。

 

图5-5 LRU页面置换算法

 

  2. LRU置换算法的硬件支持

  1) 寄存器

  为了记录某进程在内存中各页的使用情况,须为每个在内存中的页面配置一个移位寄存器,可表示为

  

  当进程访问某物理块时,要将相应寄存器的Rn-1位置成1。此时,定时信号将每隔一定时间(例如100 ms)将寄存器右移一位。如果我们把n位寄存器的数看作是一个整数,那么,具有最小数值的寄存器所对应的页面,就是最近最久未使用的页面。