4.2 虚拟存储器
例1：一个程序共有5个页面组成，分别为P1～P5。程序执行过程中的页地 址流（即程序执行中依次用到的页面）如下：P1，P2，P1，P5，P4，P1， P3，P4，P2，P4，假设分配给这个程序的主存储器共有3个页面。图中， 用"*"号标记下次将要被替换掉的页面。
4.2 虚拟存储器
内部地址变换：多用户虚拟地址Av变换成贮存实地址A 多用户虚拟地址中的页内偏移量D直接作为主存实地址中的页内偏移d 主存实页号p与它的页内偏移d直接拼接就得到主存是地址A
4.2 虚拟存储器
一个用户程序要访问虚拟存储器时，必须给出多用户虚拟地址Av。在操作系统和 有关硬件的共同管理下，首先进行内部地址变换。 如果变换成功（命中），得到主存实页号p。把主存实页号p与它的页内偏移d直 接拼接起来就得到主存实地址A，访问主存储器。 如果内部地址变换失败（未命中），表示要访问数据不在主存储器中，必须访问 磁盘存储器。这时，进行外部地址变换。 外部地址变换主要用软件实现，首先查外页表得到与虚页号P相对应的磁盘存储 器的实地址，然后再查内页表（主存实页表），看主存储器中是否有空页。如果主 存储器中还有空页，只要找到空页号。把磁盘存储器的实地址和主存储器的实页号 送入输入输出处理机（输入输出通道）等，在输入输出处理机的控制下，把要访问 数据所在的一整页都从磁盘存储器调入到主存储器。 如果主存储器中已经没有空页，则要采用某种页面替换算法，先把主存中暂时不 用的一页写回到磁盘存储器中原来的位置上，以便腾出空位置来存放新的页。 在进行外部地址变换时，如果没有命中，则表示所需要的页还不在磁盘存储器中。 这时，要在操作系统控制下，启动磁带机、光盘存储器等海量存储器，先把与所需 要数据相关的文件从海量存储器中调入磁盘存储器。
4.2 虚拟存储器
一、虚拟存储器工作原理 页式虚拟存储器是虚拟存储器中用得比较广泛的一种，另外的段式虚拟 存储器和段页式虚拟存储器主要是因为地址变换方法不同产生的。 页式虚拟存储器：把主存储器、磁盘存储器和虚拟存储器都划分成固定 大小的块--页（Page）. 主存储器的页称为实页，虚拟存储器中的页称为虚页。
4.2 虚拟存储器
5、最优替换算法，OPT算法（OPTimal replacemant algorithm）。 上面介绍的几种页面替换算法主要是以主存储器中页面调度情况的历史 信息为依据的，它假设将来主存储器中的页面调度情况与过去一段时间内 主存储器中的页面调度情况是相同的。显然，这种假设不总是正确的。最 好的算法应该是选择将来最久不被访问的页面作为被替换的页面。这种替 换算法的命中率一定是最高的。这就是最优替换算法，简称OPT算法。 要实现OPT算法，唯一的办法是让程序先执行一遍，记录下实际的页地 址流情况。根据这个页地址流才能找出当前要被替换的页面。显然，这样 做是不现实的。因此，OPT算法只是一种理想化的算法，实际上，经常把 这种算法用来作为评价其它页面替换算法好坏的标准。在其它条件相同的 情况下，哪一种页面替换算法的命中率与OPT算法最接近，那么，它就是 一种比较好的页面替换算法。 虚拟存储器中，实际上可能采用的只有FIFO、LRU两种算法。
4.2 虚拟存储器
地址变换方法：由用户号找到基址寄存器，读出段表起始地址，与虚 地址中段号相加得到段表地址，段标中的起始地址与段内偏移D相加得到 主存实地址。 N道程序-N个段表基址寄存器-N个段表 两次访存完成一次信息交换（首次访存查表，二次访存按地址取信息）
段名:实际由于段号与 行对应，省略掉。 装入位:是(1)否(0)已 调入主存。 地址:调入主存时，在 主存的起始(绝对)地址。 段长:段的大小，限制 偏移越界。 访问方式:只读、可写、 只执行，提供访问保护。
4.2 虚拟存储器
4.2 虚拟存储器
二、地址映像与变换 虚拟存储器中有三种地址空间，对应三种地址。 虚拟地址空间：虚存空间或虚拟存储器空间，是应用程序员用来编写 程序的地址空间，这个地址空间非常大。 主存储器的地址空间：主存地址空间、主存物理空间或实存地址空间 辅存地址空间：磁盘存储器的地址空间 虚拟地址：虚存空间上的地址，又称为虚存地址或者虚地址 主存地址：又称为主存实地址、主存物理地址、主存储器地址 磁盘存储器地址：又称为磁盘地址、辅存地址 地址映像：把虚拟地址空间映象到主存地址空间，具体地说，就是把用 户用虚拟地址编写的程序按照某种规则装入到主存储器中，并建立多用户 虚地址与主存实地址之间的对应关系。 地址变换：在程序被装入主存储器之后，实际运行时把多用户虚地址变 换成主存实地址（内部地址变换）或磁盘存储器地址（外部地址变换）。
4.2 虚拟存储器
3、近期最少使用算法，LFU算法（Least Frequently Used algorithm）。 这种算法选择近期最少访问的页面作为被替换的页面。显然，这是一种 非常合理的算法，因为到目前为止最少使用的页面，很可能也是将来最少 访问的页面。该算法既充分利用了主存中页面调度情况的历史信息，又正 确反映了程序的局部性。但是，这种算法实现起来非常困难。它要为每个 页面设置一个很长的计数器，并且要选择一个固定的时钟为每个计数器定 时计数。在选择被替换页面时，要从所有计数器中找出一个计数值最大的 计数器。因此，通常采用另外一种变通的办法，就是下面的LRU算法。 4、最久没有使用算法，LRU算法（Least Recently Used algorithm）。 这种算法把近期最久没有被访问过的页面作为被替换的页面。它把LRU 算法中要记录数量上的"多"与"少"简化成判断"有"与"无"，因此，实现起 来比较容易。
4.2 虚拟存储器
2、页式虚拟存储器 程序按页（虚页）划分，贮存按页（实页）分配 页面大小固定，一般指定为0.5KB的整倍数，通常为1KB至16KB。 与段式虚拟存储器相比，由于页长度固定，因此，不需要象段式虚拟存 储器中的段长度这一字段，另外，主存地址这一字段只需要指出主存储器 的页号，与段式虚拟存储器中的主存地址必须指出整个主存地址长度相比 要节省很多。 地址映像方法：
4.2 虚拟存储器
根据所采用的地址映象和地址变换方法不同，目前主要有页式虚拟存 储器、段式虚拟存储器和段页式虚拟存储器等三种。 1、段式虚拟存储器 程序按模块划分，主存按段分配 地址映像方法：每个程序从0地址开始编址，长度可长可短，可以在程 序执行过程中动态调整程序段的长度。 每一道程序（或一个用户、一个进程等）由一张段表控制，每个程序段 在段表中占一行。
4.2 虚拟存储器
虚拟地址空间中的每一个页面或每一个程序段，在外页表中都有对应 的一个存储字。在每一个存储字中除了必须有磁盘存储器的地址之外，至 少还应该包括一个装入位。
4.2 虚拟存储器
四、页面替换算法 页面替换发生时间：当发生页面失效时，要从磁盘中调入一个页面到主 存，如果主存中所有页面都已经被占用，必须从主存中淘汰掉一个已有页 面，以便存放新调入页面。 评价页面替换算法好坏的标准：命中率要高，算法要容易实现。 目前。在虚拟存储器常用的页面替换算法有如下几种： 1、随机算法，即RAND算法（Random algorithm）。 利用软件或硬件的随机数发生器来确定主存储器中被替换的页面。这种 算法最简单，而且容易实现。但这种算法完全没有利用主存储器中页面调 度情况的历史信息，也没有反映程序的局部性，所以命中率比较低。 2、先进先出算法，即FIFO算法（First-In First-Out algorithm）。 这种算法选择最先调入主存储器的页面作为被替换的页面。它的优点是 比较容易实现，能够利用主存储器中页面调度情况的历史信息，但是，没 有反映程序的局部性。因为最先调入主存的页面，很可能也是经常要使用 的页面。
4.2 虚拟存储器
3、段页式虚拟存储器 基本思想是对用户编写程序的虚拟存储空间采用分段的方法管理，对 主存物理空间采用分页的方法管理。同时获得段式虚拟存储器在程序模块 化方面的优点和页式虚拟存储器在管理主存和辅存物理空间方面的优点。 程序按段划分，段内分页，主存按页分配。 地址映像方法：每个程序段在段表中占一行，段表中给出页表长度和页 表起始地址，页表中给出每一页在主存中的实页号。
就本例而言，FIFO命中次数2次，命中率Hp=2/10=0.2 LRU命中次数4次，命中率Hp=4/10=0.4 OPT命中次数5次，命中率Hp=5/10=0.5 假设每个数据平均被访问30次，为了使LRU算法的失效率小于10-5，页 面应该至少多大？ （1-Hp）/n =（1-0.4）/30P <10-5 解得P>2000字，页面大小应该为2K字 FIFO算法的命中率最低，LRU算法的命中率与OPT算法很接近。这一结 论具有普遍意义。因此，在实际使用中，LRU算法是一种比较好的算法。 目前，许多机器的虚拟存储器都采用LRU算和联机工作的外部存储器共同组成。在目前 的计算机系统中，主存储器通常用动态随机存储器（DRAM）实现，它的 存储容量相对比较小，速度比较快，单位容量的价格比较贵。联机工作 的外部存储器通常为磁盘存储器，它的存储容量很大，与主存储器相比， 速度很低，单位容量的价格很便宜。这两个存储器在硬件和系统软件的 共同管理下，对于应用程序员，可以把它们看来是一个单一的存储器， 是一个存储容量非常大的主存储器。 虚拟存储器又称虚拟存储系统，或虚拟存储体系等，其概念是1961年英 国曼彻斯特大学的Kilbrn等人提出的。 到了70年代被广泛地应用于大中型计算机系统中。 目前，许多小型计算机，微型机也开始使用虚拟存储器。 页式虚拟存储器是虚拟存储器中用得比较广泛的一种，本节首先以页式 虚拟存储器为例介绍虚拟存储器的工作原理。然后再具体介绍页式、段 式和段页式三种虚拟存储器的地址变换方式及外部地址变换方式。
4.2 虚拟存储器
地址变换方法：先查段表，得到页表长度和页表起始地址，再查页表 找到要访问的主存实页号，把实页号p与页内偏移d拼接得到主存实地址。 三次访存，一次信息交换 在许多大中型计算机中，如IBM370/168、Multics、Amdahl470V/6等 都采用这种段页式虚拟存储器。