《存储系统》PPT课件.ppt

第6章 存储系统,6.1 存储器概述 6.2 随机读写存储器 6.3 只读存储器 6.4 高速缓冲存储器 6.5 虚拟存储器 6.6 存 储 保 护,6.1 存储器概述,6.1.1 存储器的分类 存储器是计算机系统中用于存放程序和数据的记忆设备。 1按存储介质分类 用半导体器件组成的存储器称为半导体存储器，目前半导体存储器有两大类：一类是双极型半导体存储器，一类是MOS型半导体存储器。,2按存取方式分类 有些存储器存储的内容既能读出又能写入，这种存储器称为随机存储器（Random Access Memory，RAM）。RAM中存储的信息会随着电源的断开而丢失，因此又称为易失性存储器。 有些半导体存储器存储的内容是固定不变的，即只能读出而不能写入，这种存储器称为只读存储器（Read Only Memory，ROM）。ROM可分为固定掩模式只读存储器（MROM）、可编程只读存储器（PROM）、光可擦除可编程只读存储器（EPROM）、电可擦除可编程只读存储器（EEPROM）。,3按信息的可保存性分类 断电后信息就消失的存储器称为非永久记忆存储器（易失性存储器），如RAM。断电后仍能保存信息的存储器称为永久性记忆存储器（非易失性存储器），如磁性材料做成的存储器。 4按在计算机系统中的作用分类 根据存储器在计算机系统中起的作用，可分为内存储器（主存储器）、外存储器（辅助存储器）和高速缓冲存储器等。,6.1.2 存储器的分级结构,存储器通常采用多级存储器体系结构，即用高速缓冲存储器（Cache）、主存储器和外存储器。CPU能够直接访问内存储器，包括高速缓冲存储器和主存储器。CPU不能直接访问外存储器，外存储器的信息必须被调入到内存储器后才能被CPU处理。存储器系统的层次结构如下图所示。,1高速缓冲存储器 高速缓冲存储器简称高速缓存，又称为Cache，它是计算机系统中的一个容量小而速度快的存储器，其价格也是最贵的。CPU可以直接访问Cache，因为其速度与CPU的速度差不多，从而可以提高CPU的利用率。 2主存储器 主存储器简称主存，是计算机系统中的主要存储器，用来存放计算机运行期间的大量程序和数据。它可以和Cache交换数据和指令。 3外存储器 外存储器简称外存，它是大容量的辅助存储器。目前主要使用磁盘存储器和光盘存储器。外存的特点是存储容量大、成本低，通常用来存放系统程序和大型数据文件及数据库等。,上述3类存储器构成计算机的多级存储管理系统，各级存储器承担的职能各不相同。其中Cache主要用来快速存取，以便使存取速度和CPU的运算速度相匹配；外存存储容量大，以满足计算机大容量存储的要求；主存介于Cache和外存之间，选取恰当的存储容量和存取周期，使它能容纳系统的核心软件和较多的用户程序。,6.1.3 存储器的性能指标,存储器的性能指标主要是存储容量、存取时间、存储周期和存储器带宽。 1存储容量 在一个存储器中可以容纳的存储单元总数为该存储器的存储容量，通常用字数或字节数来表示，如64KB。存储容量越大，能存储的信息就越多。在计算机中，1K相当于1024个存储单元。为了表示更大的存储容量，采用GB、TB等单位。其中1KB=210B，1MB=220B，1GB=230B。B表示字节，1B=8bit，即一个字通常是由8位二进制数组成。存储容量这一概念反映了存储空间的大小。 2存取时间 存取时间又称为存储器访问时间，是指从启动一次存储器操作到完成该操作所经历的时间，即将数据读入数据缓冲寄存器位置所经历的时间。,3存储周期 从存储器接到读命令到指定地址的信息被读出，并稳定在存储器数据寄存器或数据总线上的时间，称为读周期，反之将数据写入存储器的时间，称为写周期。从上一次访问存储器到下一次访问存储器所需要的最短时间，称为存储周期。存储周期表示存储的速度，内存的外频即存储周期的倒数。 4存储器带宽 存储器带宽是指单位时间内存储器所存取的信息量，通常以位/秒或字节/秒作为度量单位。,6.2 随机读写存储器（RAM）,目前，广泛使用的半导体存储器是MOS型半导体存储器。根据存储信息原理的不同，MOS型半导体存储器分为静态MOS存储器（SRAM）和动态MOS存储器（DRAM）。 半导体存储器的优点是存储体积小，可靠性高，价格低廉；缺点是断电后存储器不能保存信息。,6.2.1 SRAM存储器,1基本存储单元 基本存储单元是组成存储器的基础和核心，SRAM的基本存储单元电路是由6个MOS管组成的双稳态触发器，如左图所示。,图中，T3、T4管是负载管，T1、T2管为工作管，这个电路具有两个不同的稳定状态。当T1截止时，A点为高点位，使T2管导通，此时B点处于低点位，而B点的低电位又保证了T1的截止，这是一个稳定状态；反之，如果T1管导通，则A点处于低点位，使T2管截止，这也是一个稳定状态。因此，这两种状态分别可以用0或1表示。 T5T8管为控制管或开门管。由存储元组成存储器时，必须能够控制按地址选择存储单元的操作。利用T5、T6管作为触发器的读出、写入控制电路，由行地址选择信号的控制，就形成了如上页图所示的基本存储单元电路。, 写操作：写操作时，通过两条I/O线提供写入的数据信号。例如，写入1信号时，在I/O送低电平信号，在I/O送高电平信号，当地址译码线送来高电平信号，MOS管T5和T6将导通，使触发器状态保持不变，或使触发器状态翻转为1状态。而写入0信号时，则需在I/O送高电平信号，在I/O送低电平信号。 读操作：读操作时，只要该电路被选中，则T5、T6管导通，于是T1管的状态被送到I/O线上，T2管的状态被送到I/O线上，这就读出了原来存储的信息。此读取过程对存储信息是非破坏性的，即读操作后所存储的信息不变。,2SRAM存储器的组成 SRAM存储器是由存储器、读写电路、地址译码电路和控制电路等组成的，如下图所示：,图中所示存储体是一个由6464=4096个6管静态存储电路组成的存储矩阵。在存储矩阵中，同一行的64个存储电路的行选择端被接在同一根行选择线上，共有64根行选择线（X0，X2，X63），由X地址译码器的输出提供行选择信号。同一列中的64个存储电路用同一位线，由列选择线控制它们与I/O电路连通，共有64根列选择线(Y0，Y1，Y63)，由Y地址译码器的输出提供列选择信号。 地址码由12位地址码（A0，A1，A11）组成。其中A0A5经X地址译码器译码，选中存储矩阵中的某一行，此行中的所有存储电路的选通门都被打开。地址码A6A11经Y地址译码器译码，选中存储矩阵中的某一列，此列中的所有存储电路的选通门都被打开。只有行、列同时被选中的存储单元才能进行信息的读出与写入。,图中存储器的字长为1位，因此仅有一组I/O电路，对于字长为8位的存储器，则应有8个存储电路与外界交换信息，对于这种存储器，将列按8位分组，每根列选择线控制一组列的列向门同时打开。I/O电路也相应有8个，每一组的同一位共用一个I/O电路。 目前实用的存储器通常由多个RAM芯片组成来克服单个RAM芯片存储容量少的弱点。这样，地址不同的存储单元就有可能处于不同的芯片中，因此在地址选择时，应首先进行芯片的选择。在芯片的片选信号被置为有效后，便可以对该芯片进行读或写操作。,3SRAM存储器与CPU的连接方法 CPU对存储器进行读/写操作，首先由地址总线给出地址信号，然后发出读操作或写操作的控制信号，最后在数据总线上进行信息交流。因此，存储器与CPU连接时，要完成地址线、数据线和控制线的连接。 由于目前生产的存储器芯片的容量是有限的，所以需要在字向和位向两方面进行扩充才能满足实际存储器的容量要求，通常采用位扩展法、字扩展法和字位扩展法。,（1）位扩展法 位扩展法是进行位数的扩充（加大字长），存储器的字数与存储芯片的字数相同。假如使用8K1位的RAM存储器芯片，那么组成8K8位的存储器可采用如下图所示的位扩展法。,（2）字扩展法 字扩展法是仅在字上扩充，而位数不变，因此将芯片的地址线、片选线、读写控制线并联，而由片选信号来区分各片地址，将片选信号端连接到片选译码器的输出端。 例如，用16K8位的存储器芯片组成64K8位的存储器，需要用4片16K8的存储器芯片（如下页图所示）和4个芯片的数据线与数据总线D0D7相连，地址总线的位地址A0A13与4个芯片的14位地址端相连接，两位高地址A14、A15经译码器和4个片选端相连。,地址空间分配见下表,（3）字位扩展法 实际工作的存储器通常在字位方向上都要扩展。一个存储器的容量假定为MN位，若使用lk位的芯片（lM，kN），需要在字向和位向同时进行扩展，此时共需要（M/l）（N/k）个存储器芯片。例如，用256K8位的存储芯片设计容量为2048K32位的存储器，则需存储芯片数为：（2048K / 256K）（32 /8）= 32。由每组4片存储芯片完成位扩展，8组这样的存储芯片完成字扩展。,字位扩展法组成的2048K32位的RAM如下图所示：,4半导体存储器的设计步骤 （1）选择存储芯片 选择存储芯片时应该从存储速度的快慢、存储容量的大小、电源电压的稳定性、成本的高低等方面综合考虑存储器芯片的好坏。 （2）选定芯片数量 有时会遇到单个芯片不够用的情况：一种情况是单个芯片的位数不能够满足系统字长的要求，这时便需要多片芯片组合来满足要求，具体的芯片数=总字长/每片的字长；另一种情况是单个芯片在容量上难以满足系统的要求，此时要用到的芯片数=总容量/每片的容量。,（3）考虑CPU总线的负载能力 由于目前使用的半导体存储器多数是MOS电路，直流负载小，在小型机系统中可以与CPU直接连接。而在较大的系统中，就应当考虑CPU是否有足够的驱动能力，需要时必须选择有相当驱动能力的缓冲器。 （4）存储器的地址分配和选片 RAM和ROM组成了主存储器，而RAM内部又被分成了几个区，有的用于存放系统数据，有的用于存放用户数据，了解主存储器的地址分配无论对于了解硬件的工作原理还是编程都很有好处。 （5）连接控制专线 为了实现CPU对存储器的正确控制，除了有片内地址线、片选信号线、读/写控制线和数据线等的连接之外，还要考虑附加控制存储器等的连线。,6.2.2 DRAM存储器,静态存储器的优点是只需一个时钟脉冲控制，读出后也不必进行数据恢复工作，结构简单，可靠性高，速度快；缺点是电路中管子多，占用面积大，而且一直有电流流过，功耗大，不利于提高集成度和降低成本。 如果把信息以电荷的形式存储在电容上，用1表示有电荷，用0表示无电荷，读出或写入时，以电容的放电或充电形式进行，这样就组成了存储电路。MOS型动态存储电路就是基于这一设想。,下面介绍由4个MOS组成的DRAM的基本存储单元电路。 1DRAM存储器的工作原理 4管DRAM的基本存储单元电路是在6管SRAM的基本存储单元电路的基础上发展而来的。在6管静态存储元电路中，信息暂存于T1、T2管的栅极，这是因为管子总是存在着一定的电容。负载管T3、T4用于给这些存储电荷补充电荷。由于MOS的栅极电阻很高，故泄漏电流很小，在一定的时间内这些信息电荷可以维持住。为了减少管子以提高集成度，把负载管T3、T4去掉，这样就变成了4管的动态存储电路，如图所示。,T5、T6仍为控制管，由字选择线控制。当选择线为高电平时，T5、T6管导通，则存储电路的A、B点与位线D、D分别相连，再通过T7、T8管与外部数据线I/O和I/O相通。同时在一列的位线上接有两个公共的预充管T9、T10 。 （1）写操作：当写入时，I/O与I/O加相反的电平，字选择线的高电平打开T5、T6管，因而所存的信息送至A、B端，将信息存储在T1、T2管的栅极电容上。当T5、T6管截止时，靠T1、T2管栅极电容的存储作用，在一定时间内（2ms）可以保留所写入信息。 （2）读操作：当读出时，先给出预充信号，使T9、T10 管导通，于是电源就向位线D和D上的电容充电，使它们达到电源电压。当字选择线使T5、T6管导通时，存储的信息通过A、B端位线输出。若原存信息为1，则电容C2上存有电荷，T2管导通，而T1管截止，因此D上的预充电荷经T2管泄漏，故在D=0时，而D仍为1，信号通过I/O和I/O线输出。与此同时，D上的电荷可以通过A点向C2补充。故读出过程也是刷新的过程。,2DRAM存储器的刷新 DRAM存储器的存储单元以电容来存储信息，电路简单。但电容总有漏电存在，时间长了存放的信息就会丢失或出现错误。因此需要对这些电容定时充电，这个过程称为“刷新”，即定时地将存储单元中的内容读出再写入。由于需要刷新，所以这种RAM称为动态RAM。DRAM的存取速度与SRAM的存取速度差不多。其最大的优点是集成度高（目前DRAM芯片的容量已达几百兆比特），功耗低，价格比较便宜。 从上一次对整个存储器刷新结束到下一次对整个存储器全部刷新一遍所用的时间间隔称为刷新周期，一般为2ms、4ms、8ms。,常用的刷新方式有3种：一是集中式刷新，二是分散式刷新，三是异步式刷新。,（1）集中式刷新方式 如图 (a)所示，在2ms周期内集中地安排若干刷新周期，其余时间可用于正常工作状态，即读/写/保持状态。刷新周期数等于最大容量芯片的行数。在逻辑实现上，可由一个定时器每2ms请求一次，然后由刷新计数器控制一个计数循环，逐行刷新一遍。 采用这种方式的整个存储器的平均读/写周期，与单个存储器片的读/写工作所需的周期相差不多，所以这种刷新方式较适用于高速存储器。 集中式刷新方式的优点是主存利用率高，控制简单；缺点是在连续、集中的这段刷新周期内，不能使用存储器，因而形成一段死区。,（2）分散式刷新方式 如图 (b)所示，将每个存取周期分为两部分，前半周期可用于正常读/写/保持状态，后半周期用于刷新。也就是将各刷新周期分散地安排在读写周期之后。 分散式刷新方式的优点是时序控制简单，主存没有长的死区；缺点是主存利用率不高，速度大约降低一半，因为每个存取周期包含一个刷新周期，增加了一倍的时间。因此，分散式刷新方式只能用于低速系统中。 （3）异步式刷新方式 如图 (c)所示，按行数决定所需刷新周期数，并分散在2ms周期内。提出刷新请求时有可能CPU正在访问主存，可以等待CPU交出控制权后，再安排刷新周期，所以称为异步式刷新方式。大多数计算机系统都有一种DMA方式，可将动态刷新请求作为一种DMA请求，由DMA控制器控制DRAM的刷新，这已成为一种典型方式。 异步式刷新方式兼有前两种方式的优点：对主存速度影响最小，甚至可利用主存的空闲时间进行刷新，而且没有明显的死区。虽然控制上复杂些，但可以利用DMA实现。因此，大多数计算机系统采用异步式刷新方式。,6.3 只读存储器（ROM）,只读存储器（Read Only Memory，ROM）的特点是：当它在计算机系统中工作时，数据只读不写。其优点是可靠性高、集成度高、价格便宜，适宜大批量生产；缺点是不能重写。根据信息设置方法的不同，只读存储器分为MROM、PROM、EPROM和EEPROM 等4类。,6.3.1 掩模式只读存储器（MROM）,掩模式只读存储器是芯片制造厂根据ROM要存储的信息，对芯片图形（掩模）进行二次光刻生产出来的。其存储的内容固化在芯片内，用户可以读出，但不能改变。这种芯片存储的信息稳定，成本最低，适用于存放一些可批量生产的固定不变的程序或数据。 掩模式只读存储器的存储矩阵可采用单译码结构，也可采用双译码结构。通常，存储容量较小时，采用单译码结构，存储容量较大时，采用双译码结构。,6.3.2 可编程只读存储器（PROM）,如果用户要根据自己的需要来确定ROM的存储内容，则可使用可编程只读存储器（PROM）。PROM允许用户对其进行一次编程写入数据或程序。一旦编程之后，信息就永久性地固定下来。用户可以读出其内容，但再也无法改变它的内容。例如，双极型PROM有两种结构，一种是熔丝烧断型PROM，另一种是PN结击穿型PROM。由于可靠性差，加上只能一次性编程，目前已经被淘汰。,6.3.3 光可擦除可编程只读存储器,PROM只能写一次，为了能多次改变ROM中所存的内容，又出现了光可擦除可编程只读存储器，简称EPROM。目前使用最多的EPROM是用浮动栅雪崩注入型MOS管构成的，称为FAMOS，另外还有金属-绝缘-氧化物-硅型即MIOS型的EPROM。 1基本存储元电路,2典型ROM介绍 下面以一种典型的EPROM芯片Intel 2764 EPROM为例来介绍这类芯片的特点和应用。 （1）引线及功能。Intel 2764 EPROM的外部引线如下图所示：,各引脚的含意如下： A0Al2：13根地址输入线，用于寻址片内的8K个存储单元。 D0D7：8根双向数据线，正常工作时为数据输出线，编程时为数据输入线。 CE：选片信号，低电平有效，当CE=0时表示选中此芯片。 OE：输出允许信号，低电平有效，当OE=0时，芯片中的数据可由D0D7端输出。 PGM：编程脉冲输入端。对EPROM编程时，在该端加上编程脉冲。读操作时PGM=1。 VPP：编程电压输入端。编程时应在该端加上编程高电压，不同的芯片对VPP值的要求不一样，可以是+12.5V、+15V、+21V、+25V等。,（2）Intel 2764 EPROM的工作过程。Intel 2764 EPROM可以工作在数据读出、编程写入和擦除3种方式下。 数据读出：这是Intel 2764 EPROM的基本工作方式，用于读出存储的内容。其工作过程与RAM芯片非常类似，即先把要读出的存储单元地址送到A0A12地址线上，然后使CE= 0、OE= 0，就可在芯片的D0D7上读出需要的数据。 编程写入：对EPROM芯片的编程可以有两种方式，一种是标准编程，另一种是快速编程。 标准编程方式：标准编程是每给出一个编程负脉冲就写入一个字节的数据。这种方式有两个严重的缺点：一是编程脉冲太宽（50ms）而使编程时间太长；二是不够安全，编程脉冲太宽会使芯片功耗过大而损坏EPROM。 快速编程方式：快速编程与标准编程的工作过程是一样的，只是编程脉冲要窄得多。 擦除：EPROM的一个重要优点是可以擦除重写，而且允许擦除的次数超过上万次。擦除器利用紫外线光照射EPROM的窗口，一般经过1520分钟即可擦除干净。,6.3.4 电可擦除可编程只读存储器,电可擦除可编程只读存储器是在EPROM的基础上开发出来的，它可以在加电的情况下擦除存储器的全部或某一部分内容，然后在电路上直接改写其擦除过的单元内容，而不必像EPROM芯片那样需要从系统中取下来。从这一点讲，它的使用要比EPROM方便。另外，EPROM虽可多次编程写入，但整个芯片只要有一位写错，也必须从电路板上取下来全部擦掉重写，这给实际使用带来很大的不便。因为在实际使用中，多数情况下需要的是以字节为单位的擦除和重写，而EEPROM在这方面有很大的优越性。,6.4 高速缓冲存储器（Cache）,6.4.1 Cache的必要性和可行性 1Cache的必要性 如图所示，Cache是介于CPU与主存M2之间的小容量存储器，但存取速度比主存快。有了Cache就能高速地向CPU提供指令和数据，从而加快程序执行的速度。Cache可以视为主存的缓冲存储器，它通常由高速的双极型半导体存储器或SRAM组成，即Cache的功能全部由硬件实现，并对程序员透明。,2Cache的可行性 对大量典型程序运行情况的分析结果表明，在一个较短的时间内，由程序产生的地址往往集中在存储器逻辑地址空间的很小范围内，并且，在多数情况下，指令是顺序执行的。因此对这些地址的访问自然具有时间上集中分布的倾向。数据集中分布的倾向不如指令明显，但对数组的存储和访问以及工作单元的选择都可以使存储器地址相对集中。这种对局部范围的存储器地址的频繁访问，而对此范围以外的地址则访问甚少的现象，称为程序访问的局部性。 根据程序的局部性原理，在主存与CPU之间设置Cache，把正在执行的指令地址附近的一部分指令或数据从主存装入Cache中，供CPU在一段时间内使用是完全可行的。,6.4.2 Cache的工作原理,Cache的工作原理是基于程序和数据访问的局部性。Cache除包含SRAM之外，还要有控制逻辑。若Cache在CPU芯片外，它的控制逻辑一般与主存控制逻辑合成在一起，成为主存/Cache控制器；若Cache在CPU芯片内，则由CPU提供给它控制逻辑。 CPU与Cache之间的数据交换是以字为单位的，而Cache与主存之间的数据交换是以块为单位的。一个块由若干字组成，是定长的。当CPU读取主存中的一个字时，便发出此字的内存地址到Cache和主存。此时，Cache控制逻辑数据地址判断此字当前是否在Cache中：若是，此字立即传送给CPU；若非，则用主存读周期把此字从主存读出到CPU，与此同时，把含有这个字的整个数据块从主存读出送到Cache中。,如图所示为Cache的工作原理图。假设Cache读出时间为50ns，主存读出时间为250ns。存储系统是模块化的，主存中每个8K模块和容量16字的Cache相联系。 Cache分为4行，每行4个字。分配给Cache的地址存放在一个相联存储表CAM中，它是按内容寻址的存储器。,当CPU执行访存指令时，就把所要访问的字的地址送到CAM；如果字不在Cache中，则将字从主存送到CPU。与此同时，把包含字的有前后相继的4个字所组成的一行数据送入Cache，它替换了原来Cache中最近最少使用的一行数据。在此，由自始至终管理Cache使用情况的硬件逻辑电路来实现LRU替换算法。,6.4.3 主存与Cache之间地址映射的方法,与主存容量相比，Cache的容量小，它保存的内容只是主存内容的一个子集，且Cache与主存的数据交换是以块为单位。为了把主存块放到Cache中，必须应用某种方法把主存地址定位到Cache中，称为地址映射。这样当CPU访问存储器时，它所给出的一个字的内存地址会自动变成Cache的地址。根据这种地址的对应方法，地址映射方式有全相联映射、直接映射、和组相联映射3种方式。,1全相联映射 全相联映射是指主存的一个字（字块）可以映射到整个Cache的任何一个字（字块）中；反过来说，Cache的一个字（字块）中，在不同时刻可能存放的是整个主存中的任何一个字（字块）中的内容。全相联映射方式如图所示： 全相联映射的优点是灵活，Cache利用率高。缺点有两个：一是标记位数增加了，需要记录主存块块地址的全部信息，使得Cache的电路规模变大，成本变高；二是比较器难于设计和实现，通常采用按内容寻址的相联存储器。因此，只有小容量Cache才采用这种映射方式。,2直接映射 直接映射是指主存的一个字（字块）只能映像到Cache的一个确定的字（字块）中，Cache中的一个字（字块）中，在不同时刻存放的仅能是整个主存确定的某些字（字块）的内容，是完全硬性确定的。直接映射方式如图所示： 优点：实现与标志字段比较的线路简单，成本低。 缺点：使用缺乏灵活性，影响命中率。,3组相联映射 组相联映射是对全相联映射和直接映射的一种折中的处理方案，把Cache存储器组织为同等容量的多体结构，把主存地址划分为访问主存的区段（区段号）和区段内一个字块（区段内偏移量）这样两个部分。组相联映射方式如图所示： 优点：线路实现上不太复杂，方案简便易行。,6.4.4 Cache的有关问题,1替换策略 Cache的工作原理要求它尽量保存最新数据。当一个新的主存块需要复制到Cache，而允许存放那个主存块的行位置都被其他主存块占满时，就要进行替换。 替换问题与Cache的组织方式紧密相关。对直接映射的Cache来说，因一个主存块只有一个特定的行位置可存放，所以解决问题的方法很简单，只要把此特定位置上的原主存块换出Cache即可。对全相联映射和组相联映射Cache来说，就要从允许存放新主存块的若干特定行中选取一行换出。如何选取就涉及到替换策略，又称为替换算法。,（1）近期最少使用算法（LRU）。该替换算法总是替换掉Cache中最长时间没有用过的数据块，这种算法的核心思想同样利用了程序访问的局部性原理。在新的数据块读入时，替换掉该长时间没有访问的数据块是较为合理的。采用这种替换算法，数据块的命中率相当的高。 （2）先进先出算法（FIFO）。该替换算法总是替换掉Cache中存放时间最长的数据块。注意不要与LRU方法混淆，最近最少使用的数据块不一定就是最先进入Cache中存放时间最长的数据块。FIFO算法，实际上是利用了数据结构中的“队列结构”。该算法的硬件通过一个循环移位寄存器就可实现。 （3）随机替换算法（RANDOM）。这种替换算法不考虑使用情况，在Cache中通过一个随机数选择一个槽中的数据块进行替换。 所有在“CPU-Cache-主存”层次上的替换算法都是由硬件来实现的，不需要用户的干预；而对于“主存-Cache-辅存”层次上的替换算法一般都由操作系统来实现。,2写入策略 为了提高系统性能，CPU主要与Cache交换数据。它对主存数据的更改，首先是更改Cache中的内容，为保持Cache中的数据与主存中的数据的一致性，必然也要更改其对应的主存中的数据。如何保证这种数据的一致性就是写入策略的问题。下面主要介绍 “Cache-主存”层次的写入策略。 （1）全写法（Write-Through，WT）。采用这种写入策略时，在写入数据时需要同时写入Cache和主存中相应的数据块。如果在多处理机中存在多个Cache，要保证所有Cache中包含要写入数据块的内容同时得到刷新。如果主存中的某个数据块经写入后内容改变了，那么凡是在Cache中包含该数据块的内容都应该作废。显然这种策略存在过多的写入操作，它势必造成系统执行效率的降低，影响整个系统的速度。为了改变这种情况，可在系统内增设一些缓冲寄存器，用于接受CPU送来的写入数据和地址，从而不过多地占用CPU的写入时间周期，再由这些缓冲寄存器在下一个时钟周期到来时自动写入主存即可。,（2）回写法（Write-Back，WB）。采用这种写入策略进行写操作时，只修改Cache中的内容，而不修改主存中的内容。只有当已发生过写入数据的数据块被替换掉时，才将被修改过的数据块回写到主存之中，最后才能从主存中调入新的数据块，从而把Cache中的数据块替换掉。然而这种策略存在一个问题：主存中的部分内容在操作的过程中可能已经作废，如果使用可能造成错误。如果要保证使用过程中数据的有效性，I/O设备也应该从Cache中读/写信息。但是这样做又会使硬件设计实现的复杂度增加，制造成本加大，势必会使Cache成为计算机系统设计的“瓶颈”。 总的来说，Cache在计算机系统中起到两方面的作用：在单处理机中，它可以弥补主存与处理机在处理速度方面不匹配的矛盾；在多处理机中，它可以起到减轻互联网络中信息传送负担的作用。,6.5 虚拟存储器,6.5.1 虚拟存储器的基本概念 虚拟存储技术是建立在主存和大容量辅存物理结构基础之上，由附加硬件装置及操作系统内的存储管理软件组成的一种存储体系，它将主存和辅存（硬盘）的地址空间统一编址，提供了比实际物理内存大得多的存储空间。在程序运行时，存储器管理软件只是把虚拟地址空间的一小部分映射到主存储器，其余部分则仍存储在磁盘上。当用户访问存储器的范围发生变化时，处于后台的存储器管理软件再把用户所需要的内容从磁盘调入内存，用户感觉就好像是在访问一个非常大的线性地址空间。,虚拟存储器的工作原理和Cache十分类似：它将主存和用作虚拟存储器的辅存划分成小块，所有程序和数据开始时都存放在辅存中，只有在CPU需要访问时才将相应的块的内容装入到主存中，供CPU调用。主存装满后，如果还需要访问尚未装入主存的程序和数据，再通过一定的算法进行块替换，直到整个程序执行完毕。 虚拟存储器和Cache有许多共同之处，但同时也有着重要的区别。 首先，Cache和主存交换数据的频率比较高，每次交换的数据量也较小，也就是几个字节或十几个字节。而虚拟存储器和主存交换数据的频率比较低，大约每访问几百次到一千次主存才和虚拟存储器交换一次数据，但每次交换数据的量比较大，达几百到几千字节。 其次，由于Cache的主要目标是提高存储系统的访问速度，因此，Cache的所有功能，包括地址映像、字块替换等都是由硬件来实现的，效率很高，同时成本也不低；而对虚拟存储器来说，它要解决的主要问题是提高存储系统的容量，降低整个存储系统的价格。,6.5.2 虚拟存储器的管理方式,在虚拟存储器中，程序分别存放在主存和辅存中，都占有实际的主存区域与辅存区域。虚地址与主、辅存地址间的对应关系，称为地址映射。当访问主存时，进行虚地址到实地址的转换。根据地址映射方式的不同，虚拟存储器有3种管理方式：段式管理、页式管理和段页式管理。,1段式管理 段式管理的优点： （1）段的分界与程序的自然分界相对应。 （2）易于分别编译、管理、修改、保护。 （3）便于多道程序对段的共享。 段式管理的缺点：给主存空间的分配与管理带来麻烦，出现碎块，浪费存储器的有效可用容量。,2. 页式管理 虚拟地址到主存的实地址的转换是通过页表来实现的。页表的每条记录表示一个虚页号和它所对应的实页号，把实页号和虚拟地址中的低位字段拼接在一起，就是所要访问的字的实际主存地址。,3. 段页式管理 缺点：在地址的映射过程中需要多次查表。在这种系统中，虚拟地址转换成物理地址是通过一个段表和一组页表来进行定位的，段表中的每个表目对应一个段，每个表目有一个指向该段的页表的起始地址（页号）及该段的控制保护信息，由页表指明该段各页在主存中的位置以及是否装入、是否已经修改等信息。,6.5.3 虚拟存储器的工作过程,在说明虚拟存储器的工作过程之前，需要先说明两个问题：一是为了加快查表速度所采取的措施；二是虚地址与辅存地址，也就是磁盘地址的转换。下面以页式管理为例进行讲解。 1. 快表和目录表 为了提高地址转换速度，缩短查表时间，采用一个小容量的、高速的相关存储部件来存放当前最经常用到的那一部分页表，采取按内容相联方式进行访问。这样，查页表的时间就相当于访问小容量的相关存储器的时间，从而大大地提高了速度，这个小容量相关存储器称为快表，存放在主存中的页表称为慢表。 快表的内容是虚地址与实地址的对应关系。虚地址中包括用户号及虚页号，对应的是它存入主存的实页号。当进行地址转换时，将虚地址中的用户号和虚页号作为模式与快表中的各表目进行比较。同时将虚地址也送往主存，查找慢表。如果快表命中，立即可以得到对应的实页号。如果不命中，则由慢表求出实页号，然后替换快表内容。,采用快慢表进行地址变换如下图所示：,目录表法是采用一个小容量的高速存储器（按照内容访问的相关存储器，称为目录表），把那些已经调入页的地址对应关系存入其中。因为页表的容量是整个虚空间的页数，但实际上被用到的页表内容占整个页表容量的比例很小，因此可以把装入位为1的页表表目存入高速的目录表中。在CPU访问时，可先查目录表，凡已入驻主存的地址都记录在此目录表中，一般情况下都可查到它的主存地址。如果在目录表中没有查到，则说明此页尚未进入主存，此时需要由辅存将要访问的页全部送入主存。,采用目录表进行地址转换如下图所示：,2. 虚地址与磁盘实地址的转换 当CPU访问主存时， 虚地址通过页表转换成主存地址。当该虚地址所在的页尚没有调入主存时，就应当按照虚地址到辅存中寻找到该页，并通过输入/输出操作调入主存。因此需要将虚地址转换成辅存地址。虚地址与磁盘实地址（辅存地址）的转换也需建立一个对应关系表（外页表），它记录了虚地址与磁盘实地址的对应关系，转换过程如图所示。外页表的表目是按虚存页号顺序排放的，每个表目内只记录了该虚页对应的磁盘实地址及装入位。每一个用户具有一张外页表，外页表存放在主存中，通过执行软件进行表目的查找。外页表的首地址根据虚地址中的用户号来查找，再根据虚页号到外页表中查找该页对应的磁盘实地址。,图6-22 虚地址与磁盘实地址的转换,3. 页式管理虚拟存储器的工作原理 （1）系统中每个用户都有自己的页表基址寄存器、页表（慢表）及快表。当CPU需要访问时，首先查快表，如果命中则可以得到实页号，然后与页内地址组装成为主存的实际地址。 （