第4章存储系统课件

第4章存储系统计算机组成原理2007.7.21计算机组成原理第4章存储系统本章介绍了计算机中各种常见存储器芯片的结构和工作原理，以及当存储器芯片不满足系统需求时，如何对存储器进行扩展，采用何种方式对存储器进行管理以提高存储空间的利用率。2007.7.22计算机组成原理本章要点：存储器分类及其工作原理芯片扩展方法存储空间管理方法2007.7.23计算机组成原理

4.1计算机存储系统组织方式

随着计算机和网络技术的发展，人们对计算机的要求逐渐提高，从最开始只需要计算机代替人进行计算，逐渐过渡到要求计算机系统能长时间保存大量信息，并且方便用户进行异地查询。为了满足人们对各类信息的查询要求，现在的计算机必须要配备容量较大的存储系统。但是计算机存储系统，特别是磁盘存储系统，自身存在很难克服的缺陷，如读取速度慢、寻道时间长等。然而，尽管存储器速度提升缓慢，处理器的处理能力却在快速提高。这就造成了新的矛盾，存储器的数据传输速度远远小于处理器处理数据的速度，使得存储器的性能成为计算机系统性能的瓶颈。2007.7.24计算机组成原理基于以上原因，计算机中配置存储器时，需要考虑两方面的问题：（1）如何利用有限的存储空间尽可能多地存储数据、方便快捷地读出数据。（2）如何将慢速的磁盘存储器和快速的处理器匹配起来。第1个问题的解决方法，我们将在4.5节中详细介绍。下面简单介绍第2个问题的解决方法。

为了同时满足用户对容量和速度的要求，计算机系统往往会采用以下的存储器配置方法，如图4-1所示。2007.7.25计算机组成原理2007.7.26计算机组成原理大容量磁盘存储器处于存储系统的最底层，其主要作用是给计算机系统提供一个较大的存储容量，因此，对它的要求主要是存储容量要尽可能大。在计算机中配置了磁盘存储器后已经解决了容量问题，为什么还要加内存呢？原因在于匹配CPU和磁盘的速度。从前面的分析我们可以知道，计算机中，CPU的处理速度比磁盘的读写速度快得多，如果不进行速度匹配，则会出现CPU长时间等待磁盘输入数据的情况，从而降低CPU利用率，影响系统性能。内存的读写速度比CPU的速度慢，但是比磁盘快，刚好可以起到速度匹配的作用，同时，因为内存解决的主要问题不是容量问题，所以对其容量的要求不是特别高。2007.7.27计算机组成原理寄存器和Cache都是CPU中的存储器，但是二者作用却不完全相同。寄存器的读写速度最快，主要用于直接提供CPU计算所需要的数据；Cache，又叫高速缓存，作用与内存相似，主要用于匹配相对低速的内存和高速的寄存器。由此可见，二者对速度的要求都很高，而对容量的要求则较小。基于以上的原因，目前市场上的主流磁盘容量都在160G以上，内存的容量大都是512M或1G，而Cache的容量则在1M左右。思考：联系实际，一台微型计算机存储系统包含那些部件？它们分别存在于计算机那些地方？作用是什么？

2007.7.28计算机组成原理4.2半导体存储器芯片介绍

目前，几乎所有的存储器都是用半导体材料做成的。但是根据存储器的使用特性可以将存储器分为两类：随机存取存储器（RandomAccessMemory，RAM）和只读存储器（Read-OnlyMemory，ROM）。只读存储器跟随机存储器不同，用户在使用时只能读取其中的数据，如果要对ROM中的数据进行修改，则必须采用特殊的方法进行，因此ROM可以用于保存不需要经常改变的程序和数据，如：设备驱动程序等。同时，ROM有掉电保护功能，可用于制造磁盘等能长时间保存信息且不受断电影响的存储器。常用ROM有以下五类：2007.7.29计算机组成原理掩模式（Masked）ROM：该种ROM不允许用户对其修改。可编程ROM（ProgrammableROM，PROM）：该种ROM允许用户对其进行一次修改，一旦程序或数据写入则不允许用户再次修改。可擦除PROM（ErasablePROM，EPROM）：该种ROM允许用户在第一次写入数据后再次进行修改，但是修改时必须先用紫外光擦除原来的数据。电可擦除PROM（Electrically

ErasableROM，EEPROM又叫E2PROM）：该种存储器与PROM一样可以对数据进行多次修改，但是不同的是E2PROM不需要紫外光擦除，而是采用加电的方式进行擦除。闪存（Flash

memory）。闪存是电可擦除只读存储器（EEPROM）的变种，所不同的是，闪存的删除写入是以字节为单位，而EEPROM是以整块芯片为单位。现在的U盘、MP3和MP4等都使用的是闪存。2007.7.210计算机组成原理4.2.1SRAM芯片的结构和工作原理1．内部存储单元SRAM的一个存储单元可以用来保存一位数据，即可保存一个“0”或一个“1”。电路如图4-2所示。图4-2SRAM内部存储单元电路中使用的T1、T2、T3、T4均是NMOS管。X是单元行地址选择线，Y是单元列地址选择线。作为存储单元电路,该电路至少应该有保持、写入和读出三种状态。2007.7.211计算机组成原理（1）保持图中T1、T2、T3、T4能构成一个双稳态电路。T1和T2在某一时刻只能有一个处于导通状态。当T1截止、T2导通时，节点A处于高电平状态，节点B处于低电平状态。A的高电平可以保证T2持续导通，B的低电平可以保证T1持续截止。反之亦然。如果没有外界因素的影响，该电路的状态将长时间保持。所以，SRAM不需要经常刷新。约定：T1截止、T2导通时表示该单元电路状态为“1”，T1导通、T2截止时表示该单元电路状态为“0”。从以上分析可以看出，A点的状态即为单元电路保存的信息状态，A为高电平时，单元信息为“1”，A为低电平时，单元信息为“0”。因此，读出时，只需要读出A点的状态即可。2007.7.212计算机组成原理（2）写入要对此单元进行写入操作，要选中该单元，并且要将数据放在数据线上。选中时，该单元的行选择线X和列选择线Y都处于高电平状态，X、Y的高电平，使得T5~T8全部导通。如果待写入的数据是“0”，则I/0数据线被置为低电平，数据线被置为高电平，不管A、B之前的状态如何，此时A点将被强制置为低电平，B点将被强制置为高电平，进而使得T1导通而T2截止。反之如果待写入数据为“1”，使得T1截止而T2导通。2007.7.213计算机组成原理（3）读出跟写入一样，读出单元数据时，也要先选中该电源。不同的是，此时往数据线上放数据。选中时，该单元的行选择线X和列选择线Y都处于高电平状态，X、Y的高电平，使得T5~T8全部导通。I/O数据线直接与A点相连，A两点的状态将通过数据线输出。2007.7.214计算机组成原理4.2.2DRAM芯片的结构和工作原理相对于SRAM来说，DRAM具有容易集成、位价格低、容量大和功耗低等优点，但是由于受到器件的限制，DRAM的存取速度比SRAM慢，而且需要定时刷新。1．内部存储单元跟SRAM一样，DRAM的一个存储单元也可以用来保存一位数据，即可保存一个“0”或一个“1”。常见的DRAM的基本存储电路可以分为多管型和单管型，下面以单管型为例介绍电路原理。单管型存储单元如图4-4所示。2007.7.215计算机组成原理电路中的电容C和NMOS管T是电路的核心器件。单元存储的信息是通过电容的高低电压来表示的。电容充电后的高电位表示“1”，放电后的低电位表示“0”，读出时只要能读出C的电位即可。T管的栅极接行选择信号，源极通过T2接数据线，其作用是控制对C的充电。当T管导通时，源极电位与电容电位相同。对单元电路的写入、读出和保持这三个基本操作的基本原理如下：2007.7.216计算机组成原理（1）写入要对单元进行写入，行列选择信号必须有效，且待写入数据需要放在数据线上。此时T1、T2导通，数据线与源极相连，而源极电位与电容电位相同，因此，数据线上的电位将强制修改电容的电位，从而完成写入操作。（2）读出该单元的行列选择地址有效时，T1、T2导通，所以电容电位的高低能通过数据线输出。（3）保持单元电路是通过C的高低电位表示信息，然而电容的电压不能长时间保持，如果不定期对C的数据进行刷新，则其保存的信息“1”经过一段时间后将会变为“0”导致数据丢失。通常每1～2ms就需要对其状态进行一次刷新。2007.7.217计算机组成原理2．典型芯片的工作原理下面我们以Intel2164A芯片为例介绍DRAM芯片的工作过程。（1）芯片简介Intel2164A芯片存储容量为64K×1位、最大存取时间为200ns、刷新时间间隔为2ms，采用双列直插式封装，有16个引脚，其引脚图如图4-5所示。各引脚功能：：行地址选通信号，用于锁存行地址,低电平有效，兼作芯片选择信号。为低电平时，表明芯片当前接收的是行地址；：列地址选通信号；地址总线上先送上行地址，后送上列地址，它们分别在RAS和CAS有效期间被锁存芯片中。A0～A7：地址线；用来分时接收CPU送来的8位行、列地址；DIN：数据输入；DOUT：数据输出；NC：未用引脚;VCC：+5V电源引脚；GND：接地引脚；：读写允许控制信号输入引脚，当其为低电平时，执行写操作；否则，执行读操作。2007.7.218计算机组成原理（2）工作原理2164A有64K×1位的存储空间，需要16位地址线才能寻址，由于其存储单元采用矩阵的方式设置，我们只要知道某个存储单元的行列地址就可以对该单元进行读写，所以芯片16位地址线又可以分成8位行地址线和8为列地址线，为了节约成本和减少芯片引脚数量，芯片只用了8位地址线，采用分时的方式分别传送行地址和列地址。传送地址时，先传送8位行地址，后传送8位列地址。为了区别行列地址，芯片设置了两个低电平有效的引脚（RowAddressStrobe）和（ColumnAddressStrobe）分别作为行地址选通信号和列地址选通信号。当信号为低电平时，把此时地址线上的8位地址信号送至内部的行地址锁存器，同理当信号为低电平时，把此时地址线上的8位地址信号送至内部的列地址锁存器。2007.7.219计算机组成原理与6116不同，2164A的输入输出数据线使用了不同的引脚，在实际使用时，常将这两位数据线与数据总线的同一位相连。为了保证正确的接收数据和输出数据，芯片设置了读写允许控制信号输入引脚。当＝0时，芯片接收数据，并根据行列地址信号将此数据写入到相应的存储单元；当＝1时，芯片根据行列地址信号读出相应的存储单元的数据，并且输出到数据总线上。2007.7.220计算机组成原理4.2.3ROM的结构和原理下面，我们以EPROM的典型芯片Intel2716为例介绍ROM芯片的工作原理。1．内部存储单元EPROM的基本电路如图4-6所示，其核心器件是浮置栅雪崩注入型场效管（FloatinggridAvalancheinjection，FAMOS）。图4-6EPROM内部存储单元在没有被写入数据前，FAMOS管的栅极没有电子，源漏极间没有形成导电沟道，不导通，此时保存的信息为“1”。对其进行写入操作后，其栅极上被注入电子，源漏极间形成导电沟道，管子导通，此时保存的信息为“0”。2007.7.221计算机组成原理2．典型芯片的工作原理（1）芯片简介Intel2716是容量为2K×8位，读出时间在350ns～450ns，有24个引脚，采用双列直插式封装的芯片。芯片引脚图如图4-7所示。各引脚功能如下：Al0～A0：地址信号输入引脚，可寻址芯片的2K个存储单元；O7～O0：双向数据信号输入输出引脚；：片选信号输入引脚，低电平有效，只有当该引脚转入低电平时，才能对相应的芯片进行操作；：数据输出允许控制信号引脚，低电平时允许数据输出；Vcc：+5V电源；VPP：+25V/+5V电源，用于在专用装置上进行写操作；GND：接地引脚。2007.7.222计算机组成原理（2）工作原理芯片有两个电源输入引脚VCC和VPP。引脚VCC作为芯片电源引脚，一直接高电平，即VCC＝1。引脚VPP用以控制是否对芯片进行写操作。当VPP＝+5V时，不允许对写芯片，但是当VPP＝+25V时，能对芯片读操作也能进行写操作。其工作原理如下：当VPP＝+5V、且时，允许对读芯片，芯片将地址信号所指定的单元的信息放到输出数据线O7～O0上；当VPP＝+5V、时，无论状态如何，芯片都将进入保持状态，此时不能对芯片进行读写，输出数据线呈高阻状态；当VPP＝+25V、为持续50ms的高电平、时，数据线上的信息将被写入到地址信息确定的单元里，此时芯片处于编程写入状态，数据线处于输入状态；编程完成后，需要验证写入芯片的数据是否正确，因此，Intel2176芯片还能提供程序校验功能，即当VPP＝+25V、、时，能对芯片内的存储单元进行读操作，根据读出的数据判断写入的程序是否正确；当VPP＝+25V、、时，不允许写芯片，此时数据线又将呈高阻状态。2007.7.223计算机组成原理4.2.4相联存储器相联存储器（associative

memory）是一种根据存储内容来进行存取的存储器，也称为按内容访问存储器（content

addressed

memory）。它跟一般的存储器不同，一般存储器进行读写时，需要控制芯片提供读写的单元地址，而相联存储器则是按顺序写入，根据需要读取的内容读出。严格地说，相联存储器是一种存取方法，而不是一种存储器。2007.7.224计算机组成原理任何一个记录都有很多的数据项，如学生的姓名、学号、联系方式等，每个数据项都是不完全相同的，特别是同一所学校的学生的学号是不可能重复的，因此，在对这类数据进行读出时，选定一个数据项作为相联关键字来代表要查找的对象，如学生的学号。读出时，根据中央处理单元给出的这个相联关键字，用它和存储器中所有单元中的一部分信息进行比较，如果相等，则将此单元中余下的信息读出。这是实现存储器并行操作的一种有效途径，特别适合于信息的检索和更新。现在的大部分数据库都是采用这种方法实现的。为了进行正确比较，存储器必须设置一定的机构来实现比较的过程，这些机构包括：比较寄存器，屏蔽寄存器，字选择寄存器，查找结果寄存器等。各寄存器作用如下：2007.7.225计算机组成原理（1）比较寄存器用来存放检索字，其位数和相联存储器的存储单元位数相等。（2）屏蔽寄存器用来存放屏蔽码，其位数和检索寄存位数相同。当按内容进行检索时，相应地把MR中要比较的位设置成“1”，不要比较的设置成“0”。置“1”的字段为关键字段。（3）查找结果寄存器：位数等于相联存储器的存储单元位数，每一位对应一个存储单元，位的序数即为相联存储器的单元地址。若比较结果第i个字满足要求，则将第i位置为“1”，其余的均为“0”。2007.7.226计算机组成原理（4）字选择寄存器：位数与记录的数据项的数量相同，用以确定哪些字参与检索，参与检索的则相应位为“1”，其余的为“0”。思考：目前，我们使用的那些存储产品采用的是半导体存储技术？2007.7.227计算机组成原理4.3主存储系统

主存储器主要有以下几个性能指标：存储容量：所谓存储容量即存储器能够保存的数据的数量。常用的单位有GB、MB、KB等。1GB=1024MB,1MB=1024KB,1KB=1024B。也可以用乘积的方式表示，公式为：容量＝字数×字长如1KB可以表示为1K×8位，1MB可以表示为1M×8位等。存取速度：所谓存取速度即是单位时间内存储器能读写的位数或字节数。该参数跟存储器的时钟频率有关。一般情况下，时钟频率越高，存取速度越快。如果用位数衡量，常用单位有Kb/s、Mb/s等；如果用字节数衡量，常用单位有KB/s、MB/s等。2007.7.228计算机组成原理读写周期：所谓读写周期是指读写一位或一个字节所需要的时间。该参数与存取速度成反比。存取速度越快，周期越短，反之亦然。前面我们介绍了几种常用的存储器芯片的结构、电路和工作原理。但是不同的应用场合会对芯片提出不同的要求。现有的芯片往往不能完全满足系统的需要，因此如何用现有的芯片来实现系统的性能要求就成为了存储系统必须解决的重要问题之一。芯片不满足使用的需要主要有以下几个方面：2007.7.229计算机组成原理1．位数不够如系统需要的存储容量为128K×8位，可选的芯片却只有128K×1位或者128K×4位的芯片。这种情况下，芯片能够满足128K的要求，而位数却不能满足8位的要求。此时需要对位数进行扩展，即位扩展。2007.7.230计算机组成原理2．字数不够如系统需要的存储容量为256K×8位，可选的芯片却只有64K×8位或者128K×8位的芯片。这种情况下，芯片能满足8位的要求，但却不能满足容量256K的要求。此时需要对字进行扩展，即字扩展。2007.7.231计算机组成原理3．字数位数均不够如系统需要的存储容量为256K×8位，可选的芯片却只有64K×4位或者128K×4位等芯片。这种情况下，芯片既不能满足8位的要求，又不能满足容量256K的要求。此时需要对位数和字同时进行扩展，即字位扩展。当芯片不能直接满足系统需求时，设计者就需要对存储器进行扩展。上述三种情况是对存储器进行扩展时的三种主要情况，因此对存储器的扩展又主要有位扩展、字扩展和字位扩展。2007.7.232计算机组成原理值得一提的是，如果发生下述情况：系统需要的存储容量为128K×8位，可选的芯片只有256K×8位的芯片，这时不需要进行芯片扩展，只需要在编程时仅使用低地址空间即可；系统需要的存储容量为128K×8位，可选的芯片只有128K×16位的芯片，这时也不需要进行芯片扩展，只需要在编程时只使用输出数据的低8位，高8位悬空或者置零即可。所以只有当可选芯片的字或位不够用时才需要进行芯片扩展。2007.7.233计算机组成原理4.3.1位扩展所谓位扩展，就是当单个芯片的容量能满足要求，但是输出位数不满足系统对存储器输出位数的要求时，通过几个芯片同时输出的方式对存储器的输出位数进行扩展。根据前面的介绍，我们知道了何时需要进行位扩展，那么如何用位数较少的芯片来扩展位数较多的存储器呢？比如，系统需要的存储容量为128K×8位，可选的芯片却只有128K×4位的芯片。其扩展过程如下：2007.7.234计算机组成原理（1）确定扩展类型：仔细分析系统要求可知，系统需要的容量跟芯片容量刚好相等，但是位数不同，因此我们需要进行位扩展；（2）需要确定所需芯片的数量，系统要求存储器每次输出8位数据，而一片芯片每次只能输出4位，则为了满足系统需求，每次要两片芯片同时输出，因此在对芯片进行选择时，这两片芯片的片选信号和地址线必须相同，实际连接电路时只需要将片选信号和地址线连在一起即可；（3）因为扩展时需要由两个4位组成一个8位进行输出，所以要确定哪4位为高4位，哪4位为低4位。根据以上步骤，可以得出如图4-8所示的扩展电路图。2007.7.235计算机组成原理2007.7.236计算机组成原理图中，两芯片的片选信号、读写控制信号和地址信号连在一起，当系统需要进行读写时，两块芯片将同时工作。现以读地址为1024的单元为例介绍扩展后的存储器工作过程：控制芯片将其与片选信号相连的引脚置为低电平；将与读写控制线相连的引脚置为低电平；将待读取地址（00100H）通过地址总线传送给存储器，因为两块芯片的以上三个信号相同，它们将同时把其1024单元中的地址放到数据线上输出，两组输出数据线分别连接控制芯片的数据线的高4位和低4位，所以控制器在发出一个读信号后，将收到一组8位的数据。从而实现了用两片4位输出芯片扩展为一个8位输出的存储器。2007.7.237计算机组成原理4.3.2字扩展所谓字扩展，就是当单个芯片输出位数满足系统要求，而容量不满足要求时，用多个芯片采用地址分段的方式对存储容量进行扩展，参与扩展的每个芯片的地址范围不同。注意：在学习本节内容的过程中，大家一定要注意字扩展和位扩展方法的不同。2007.7.238计算机组成原理下面用一个例子解释字扩展的方法：系统需要的存储容量为256K×8位，可选的芯片只有64K×8位。其扩展的步骤如下：（1）确定扩展类型分析系统要求可知，芯片输出数据的位数与系统需求一致，所以不需要进行位扩展；芯片容量只有系统需求的四分之一，所以本例中，为了满足系统需求，需要用多个小容量芯片组成一个较大容量的存储器，即字扩展。2007.7.239计算机组成原理（2）确定芯片数量系统需要256K的容量，如果用64K的芯片则需要4片才能满足系统需求。所以本例中，参加扩展的芯片数量为4。注意：如果实际需要的容量不是芯片容量的整数倍，则扩展后的容量不能比系统需要的容量小。（3）选择合适的扩展方法字扩展时常采用的方法有线选法、数字逻辑法和译码法。2007.7.240计算机组成原理下面分别对以上三种方法进行介绍。线选法：所谓线选法就是在产生片选信号（低电平有效）时，不是由几位地址线的组合状态经过运算后得出，而是用直接将控制器的一根地址线与芯片使能端相连。线选法是字扩展中最简单的方法，其优点是片选信号的产生过程简单，不容易出现错误。但是由于每个芯片都占用一根地址线，当芯片数量增多时要求控制器地址线数量很多，而且此方法会严重浪费控制器的逻辑地址空间，限制了程序的规模。2007.7.241计算机组成原理采用线选法对上述例子进行字扩展的电路图如图4-9所示。图中芯片的地址信号都是使用的A15～A0这16位低地址线，但是芯片的片选信号都分别占用了A16～A19中的一根地址线，则每个芯片的地址见表4-3所示。假设控制器的地址线共有20根，即A19～A0，寻址空间大小为1M。从上表中我们可以看出，被浪费的地址空间是00000H~6FFFFH、80000H~AFFFFH、C0000H~CFFFFH和F0000~FFFFFH四个范围，地址空间大小占768K，占控制器寻址空间的75％，对地址空间造成了严重的浪费，且当系统需求增大时，被浪费的地址也无法再被利用。2007.7.242计算机组成原理芯片编号A15～A0A19～A16地址范围10000H～FFFFH1110BE0000H～EFFFFH20000H～FFFFH1101BD0000H～DFFFFH30000H～FFFFH1011BB0000H～BFFFFH40000H～FFFFH0111B70000H～7FFFFH2007.7.243计算机组成原理2007.7.244计算机组成原理为了克服线选法对地址空间的浪费，我们常采用数字逻辑法和译码法进行字扩展。数字逻辑法：所谓数字逻辑法即用数字逻辑电路对两位高地址进行逻辑运算产生片选信号。各个芯片的存储单元的地址情况：256K的容量需要18根地址线（A17～A0），而64K的容量需要16根地址线，因此只需要从系统的18根地址线中取出低16位(A15～A0）即可对芯片内的每个存储单元进行寻址，剩余的两位高地址（A17、A16）有4种组合，每一种组合刚好可以用作产生片选信号。每个芯片的地址范围见表4-4所示。2007.7.245计算机组成原理芯片编号地址范围低16位地址范围（A15～A0）高2位地址（A17A16）100000H～0FFFFH0000H～FFFFH00B210000H～1FFFFH0000H～FFFFH01B320000H～2FFFFH0000H～FFFFH10B430000H～3FFFFH0000H～FFFFH11B2007.7.246计算机组成原理2007.7.247计算机组成原理从上述例子中，我们可以看出：逻辑运算法克服了线选法的缺点，地址空间的利用率达到了100％，同时也节省了两根地址线，所以存储器的容量还可以进一步扩展。但是片选信号的产生复杂，容易出现错误。随着扩展时所需芯片数量的增加，电路的复杂性将会成级数方式增加。为了达到地址空间100％的利用率和使用的地址线尽可能少的要求，克服逻辑运算法产生片选信号过程复杂的缺点，实际进行字扩展时常常采用第三种方法，即译码法。2007.7.248计算机组成原理译码法：所谓译码法就是对几根地址线的组合状态用译码器译码后产生片选信号。其原理与逻辑运算法类似，不同之处在于片选信号的产生方法，逻辑运算法是对地址状态经过组合逻辑电路运算后得出片选信号，而译码法则是用译码器译码产生。根据参与译码的地址线的数量，可以将译码法分为：完全译码法和部分译码法。完全译码法是指所有地址线状态都作为译码器输入的方法。部分译码法是指部分地址线状态作为译码器输入的方法。2007.7.249计算机组成原理译码法进行字扩展时，各芯片的地址空间跟逻辑运算法的芯片地址空间一样，如表4-5所示，因此只需要对两位地址通过2-4译码器译码，即可产生4块芯片需要的片选信号，所以采用的译码方法是部分译码法，芯片扩展后的电路图如图4-11所示。2007.7.250计算机组成原理2007.7.251计算机组成原理与逻辑运算法相比，译码法产生片选信号时，用译码器替代了复杂的数字组合逻辑电路。片选信号的产生简单明了，不容易出现错误，更降低了成本。译码法不仅继承了逻辑运算法的优点、克服了逻辑运算法的缺点，还方便存储容量再次扩展。比如：现在需要将系统容量从256K提高到512K，译码法只需要将2-4译码器更改为3-8译码器，然后将译码器输出与各芯片片选引脚相连即可；而采用逻辑运算时，需要重新计算每个片选信号与地址输入信号的关系，然后根据此关系式选择正确的门电路画出组合逻辑电路图，最后将每个组合逻辑电路的输出与各芯片片选信号相连。因此，译码法是较方便且不容易出错的字扩展方法。2007.7.252计算机组成原理4.3.3字位扩展所谓字位扩展，就是当单个芯片的输出位数和容量同时不满足系统要求时，用多个芯片结合位扩展和字扩展的方法对存储器进行扩展。在实际芯片扩展时，常常会需要用到这种扩展。2007.7.253计算机组成原理例子：如系统需要的存储容量为256K×8位，可选的芯片容量只有128K×4位。在这种情况下，存储器需要一次输出8位，而芯片却只能一次输出4位，需要进行位扩展；存储器要求容量为256K，而芯片容量却只有128K，需要进行字扩展。扩展过程中，需要用到位扩展的方法，也会用到字扩展的方法。扩展步骤如下：2007.7.254计算机组成原理（1）位扩展：根据位扩展的原理，此处需要两个芯片同时输出才能满足系统对位数的要求，因此，连接电路时，这两块芯片的片选引脚必须接同一个片选信号，保证两块芯片同时被选中。2007.7.255计算机组成原理（2）字扩展：位扩展时，虽然是两块128K的芯片同时工作，但是存储器容量仍然是128K，只是输出变成了8位，构成了128K×8位的芯片。因此要构成256K×8位的存储器，必须先将两块芯片构成一组，此时，这一组芯片可以当成一个128K×8位的芯片使用，然后由两组芯片组成系统需要的存储器。此处只需要两组就可以达到要求，所以片选信号产生时，没有用到译码器，而选择了一个非门；如果需要多组，则需要通过译码芯片产生片选信号。（3）连接数据输出线。字位扩展后的电路图如图4-12所示。2007.7.256计算机组成原理2007.7.257计算机组成原理电路中的4块芯片从左向右编号分别为1、2、3、4，其中1、2号芯片构成一组，3、4号芯片构成一组。从图中，我们可以看见每组芯片输出都是8位，地址线A16～A0能对组内128K的地址范围进行寻址。A17作为片选信号，当A17为低电平时，芯片1、2被选中，当A17为高电平时，芯片3、4被选中。因此，芯片1、2构成的芯片组地址范围是00000H～1FFFFH，2、3构成的芯片组地址范围是20000H～3FFFFH。2007.7.258计算机组成原理综上所述，可以得到以下结论，假定系统需要的存储容量为M×N位，可选的存储芯片容量只有x×y位（x<M，y<N），此时需要在字向和位向同时进行扩展，共需（M/x）×（N/y）块存储芯片。思考：假如计算机存储系统中单片ROM容量为4K×8，单片RAM容量为8K×8，请设计计算机存储系统电路图，要求ROM为16KB，RAM容量为64KB。2007.7.259计算机组成原理4.4高速缓冲存储器Cache

4.4.1Cache基本原理1．设置Cache的必要性计算机有两个核心器件，一个内存，另外一个则是CPU。二者是否能较好配合，将直接影响计算机性能。早期的CPU跟内存的速度相差不多，但是随着计算机硬件技术的发展，CPU的速度提高的比内存快，现在内存和CPU的读写速度相差2～3个数量级。如果仅仅依靠内存给CPU传输数据，那么CPU可能会长时间等待，降低资源利用率。所以，必须对二者速度进行匹配。2007.7.260计算机组成原理匹配内存和CPU的速度有以下三个方法：（1）降低CPU速度；（2）采用高速的SRAM作为内存的存储器；（3）根据程序执行的局部性原理，在二者之间设置一定的缓冲器。显然，第一个方法降低了计算机性能，不可能采用；第二个方法需要用价格昂贵的SRAM来制作容量高达几百兆的内存，成本过高。因此第三个方法则呈了现代计算机的首选方法。2007.7.261计算机组成原理实际的计算机系统中，常常在CPU和内存间设置一个容量不大（常常为几十至几百K）但是速度跟CPU速度相同的Cache作为缓冲器，把正在执行的指令代码单元附近的一部分指令代码或数据存入Cache中，CPU需要数据时，直接从Cache中读取，这种方法解决了速度不匹配的问题，又不会大幅度增加成本。2007.7.262计算机组成原理2.基本原理Cache又叫高速缓存，是高速缓冲存储器（CacheMemory）的简称。作为一种存储器，Cache有一定的存储空间，但Cache的主要作用不是进行数据存储，所以其存储空间较小。根据Cache所处位置的不同，可以将Cache分为一级Cache和二级Cache。与CPU集成在同一块芯片中的是一级Cache（简称L1Cache），其容量常常为几十KB～几百KB；不与CPU集成在同一块芯片中的是二级Cache（简称L2Cache），其容量常常为几百KB～2MB。目前市场上比较高档的CPU常常配有512KB、1MB或者2MB的Cache。配置了Cache的CPU和内存之间的存储结构如图4-13所示。2007.7.263计算机组成原理2007.7.264计算机组成原理在Cache控制器的作用下，CPU首先访问Cache，如其需要的数据在Cache中，则直接访问Cache即可，否则再访问内存。如果设置了L2Cache，则系统将按照L1Cache、L2Cache、内存的顺序访问。值得注意的是：Cache不能被用户直接访问，用户不能使用Cache地址进行编程。2007.7.265计算机组成原理Cache一般由SRAM、TRAM和控制器组成。其中，SRAM提供存储空间，它的容量即为Cache的容量；TRAM保存Cache中的数据在主存中的地址；控制器则是实现比较和控制Cache的读写操作等功能。当CPU需要内存中某一地址的数据时，控制器首先将该地址信号与TRAM中的地址进行比较，如果找到相同的地址，说明内存中的数据在Cache中，则CPU直接访问Cache，否则CPU将访问内存。当CPU所需要的数据没有在Cache中时，控制器还要完成对Cache的修改，将内存中的数据读取到Cache中，以保证Cache命中率尽可能高，提高数据访问速度。2007.7.266计算机组成原理4.4.2地址映像

Cache作为CPU和内存间的缓冲存储器，理想情况下，应该保证CPU每次需要访问的数据都在Cache中。但是，用户程序却是按照内存地址编写的，Cache所做的工作是在CPU访问内存前，根据程序执行的局部性原理，先将内存中的数据读出，当CPU需要时再提供给它。所以，“Cache所保存的数据到底是内存中的哪些数据，地址是什么？”就成了关键性问题。这一问题实际上也是Cache的存储空间与内存之间的地址映像问题。2007.7.267计算机组成原理常用的地址映像方式有三种：全相联映像、直接映像和组相联映像。1．全相联映像所谓全相联映像是指将内存和Cache按找固定的相同的大小进行分块。内存的块和Cache的块可以任意对应，即内存的任何一块都可以映像到Cache的任何一块，在Cache的存储空间被占满的情况下，也允许确实已被占满的Cache存储器中替换出任何一个旧块。2007.7.268计算机组成原理这种映像方式的优点是映像过程灵活，块冲突率低，只有在Cache中的块全部装满后才会出现冲突，Cache利用率高。缺点是块表查找的速度慢，由于Cache的速度要求高，全部比较和替换策略都要用硬件实现，控制复杂，实现起来也比较困难，成本高。全相联映像方式下内存与Cache对应的对应关系如图4-14所示：2007.7.269计算机组成原理2007.7.270计算机组成原理2．直接映像跟全相联映像一样，直接映像先将Cache分成若干块，每个块的大小相同，并对每个块进行编号，同时根据Cache容量大小将内存分成若干页，每个页的容量都跟Cache的容量相同，然后对内存进行分块，每块的大小跟Cache块的大小相同，同样对页内的块进行编号。映像时，内存的某个页的块只能保存在与其块号相同的内存块中。例如，如图4-15所示，内存各页中的第0块只能映像到Cache的第0块，而不能映像到其他块。2007.7.271计算机组成原理2007.7.272计算机组成原理直接映像的优点是地址变换简单、速度快，缺点是映像不灵活，块冲突率较高，Cache命中率低，特别是程序需要在两个页的相同块号的块之间往返执行时，Cache命中率将降得非常低。2007.7.273计算机组成原理3．组相联映像为了解决直接映像的冲突问题，组相联映像方式，先将Cache分成大小相同的若干区，一般分为2个或4个区，对每个区按照直接映像的方式进行分块，并且编号，因此，Cache中有多个编号相同的块。对内存按照Cache区的大小进行分页，再对每页按照Cache块的大小进行分块，每个内存块可以对应不同Cache区中的相同块号的块。例如，图4-16中内存第0页的第0块，可以对应Cache的第0区的第0块，也可以对应第j区的第0块。2007.7.274计算机组成原理组相联映像的减小了直接映像方式下的页冲突问题，提高了Cache的命中率，且Cache的容量越大，分区的数量越多，命中率越高，但是这中映像方式控制电路复杂。值得注意的是，如果只对Cache分1个区时，则组相联映像就是直接映像，因此，直接映像是组相联映像的一种特殊情况。2007.7.275计算机组成原理2007.7.276计算机组成原理4.4.3替换策略及更新策略1.替换策略不管采用何种映像方式，内存的每个块都对应Cache的某一个块。但是Cache容量远小于内存容量，不能将内存的所有块全部保存。因此，如果需要往Cache中调入一个新块，且Cache已经被占满时，就需要将Cache中的某一个块调出，而将新块调入Cache，这个过程就是替换。2007.7.277计算机组成原理采用不同的替换策略，将很大程度上影响Cache的命中率。常用的替换策略有：随机替换法：任意选择一个Cache块，将其调出。先进先出(FIFO)策略：替换出最先进入Cache的块近期最少使用(LRU)策略：这种替换策略需随时记录Cache存储器中各个字块的使用情况，以便确定哪个字块是近期最少使用的字块。这三种策略的算法将在4.5节中介绍，这里不再赘述。2007.7.278计算机组成原理2.更新策略当内存数据被修改时，与之对应的Cache的数据也需要相应修改，这个过程就是更新。但是，进行修改时，Cache无法向CPU提供数据，因此修改Cache的时机相当重要。常用的更新策略有：2007.7.279计算机组成原理及时更新策略：修改内存的同时对Cache进行修改。周期更新策略：对Cache的修改周期进行，修改周期到的时候，无论内存数据是否改变，都将Cache数据更新为与内存相同的数据。执行时更新策略：当CPU需要某个Cache块的数据时，将此块与内存中与之对应的块进行比较，二者不相同时，对Cache进行更新。思考：目前市场上主流微处理器（CPU）和最新技术的微处理器（CPU）的Cache的容量分别是多少？2007.7.280计算机组成原理4.5虚拟存储系统

程序要运行，需要CPU运算，而在计算机存储中，CPU只能从内存中读取数据，因此要运行的程序必须首先进入内存。此时，如果程序运行所需要的内存容量大于计算机配置的内存容量，则程序无法运行。而当前，很多的计算机软件对内存的需求都大于实际的内存容量，如果不采用一定的方法对内存进行扩充，则计算机的应用范围将受到很大限制。在4.3节中，我们学习了如何依靠芯片数量的增加来增大存储器容量的方法，能在一定程度上解决系统容量的问题，但是芯片数量的增加必然导致成本的急剧提高。因此如何在现有的存储容量基础上，通过对程序进出内存的方法进行设计以提高存储器利用率，让计算机能运行比自身内存大得多的程序便成了首要任务，于是虚拟技术便应运而生。2007.7.281计算机组成原理所谓虚拟存储，就是采用一定的方法将一定的外存容量模拟成内存，同时对程序进出内存的方式进行管理，从而得到一个比实际内存容量大得多的内存空间，使得程序的运行不受内存大小的限制。虚拟存储方法的实现依赖于程序的特性：2007.7.282计算机组成原理顺序性。所谓程序的顺序性，是指程序运行过程中，如果要运行第N＋1行语句，则大多数情况下需要先运行第N行语句，即程序是在顺序执行。局部性。为了减小程序的规模，很多的程序设计语言都会设计循环结构，如C语言中的for语句和while语句就是典型的循环语句，程序在执行这类循环语句时，程序的执行范围就限定在循环体中，而不会执行循环体外的语句。执行的语句限定在很小的范围内，即在局部范围内执行，这种情况经常会发生，这就是程序的局部性。2007.7.283计算机组成原理根据程序的以上两个特性，需要运行的程序不需要完全进入内存也可运行。具体方法如下：根据程序的顺序性和局部性原理，如果将程序分成几块，当前面一个块快运行结束时再将下一个块调入内存，则程序的执行将不会受到影响，而且程序所需要的内存容量也将变小。本节的几种虚拟存储实现的方法都是基于这一原理。2007.7.284计算机组成原理4.5.1页式存储系统在学习页式存储方法之前，我们先了解一下最简单的两种存储器分配方式。1.单一连续分配在单道环境下，计算机只允许一个作业运行，此时所有的计算机资源被该作业独占，包括存储器。所谓单一，是指此方式下，计算机只为一个作业分配存储空间。所谓连续，是指出了操作系统占用的存储空间外，剩余的内存空间将全部分配给作业，因此作业占用的存储空间不间断。其内存分配情况图4-17所示。2007.7.285计算机组成原理2007.7.286计算机组成原理系统运行必须要操作系统统一管理，因此尽管计算机只运行一个作业，也要将操作系统运行的内存空间留出来。但是不管操作系统是如图4-17（a）一样占据低地址空间，还是如图4-17（b）一样占据高地址空间，作业所占的地址都是连续的，而且除操作系统占用的那一部分内存外，剩余的所有内存空间均被作业独占。这种分配方式很容易造成内存空间的浪费。因为作业的大小跟剩余空间的大小往往不相等。如图4-17的两个图所示，内存容量为128KB，操作系统占用32KB，剩余空间内存96KB。如果作业大小为20KB，则剩余76KB的存储空间在该作业退出系统前将不会被利用。2007.7.287计算机组成原理为了解决单一分配时的空间浪费问题，在给作业分配存储空间之前，先将剩余空间分成若干区域，各区域大小可以相同也可以不同，然后再根据作业的需要进行分配，即分区分配。2007.7.288计算机组成原理2．分区分配根据分区分配时，区域的大小是否固定，分区分配又可以分为固定分区分配和可变分区分配。（1）固定分区分配。所谓固定分区分配，是指先将内存分成若干固定区域，区域大小一经确定将永远不再改变，每个作业占用一个区域。2007.7.289计算机组成原理分区过程中，要给作业分配内存，必须首先要知道哪些分区是空闲（未分配）的，这些空闲区的容量是多大。因此系统需要设置一种表格来纪录这些信息，常常采用的方法是分区分配表。为了满足正常分配的要求，分区分配表应该包含每个分区的起始地址、大小和分配情况等信息。分配前，系统先查找分区分配表，如果能找到一个满足作业要求的的分区，则将此分区分配给作业。在固定分区中，分区分配表直接决定了是否能正确给各作业分配存储空间，所以为了保证分区的正确性，需要随时更新分区分配表的信息。2007.7.290计算机组成原理常用的分区方法一般有两种：最佳适应法和最先适应法。所谓最佳适应法，是指在给作业分配空间时，首先遍查分区分配表找到一个能满足作业要求的最小分区分配给该作业。而最先适应法则是指在分区时，按地址从低到高查找分区分配表，将找到的第一个能满足作业运行要求的分区分配给作业。流程图分别如图4-20和图4-21所示2007.7.291计算机组成原理2007.7.292计算机组成原理2007.7.293计算机组成原理假如在图4-19（a）所示的情况下，又有一个需要23KB运行空间的作业3进入内存。如果采用最佳适应法进行分配，则通过查找分区分配表可知：能满足该作业要求的分区的序号分别为2、3和5，三个分区的大小分别为30KB、25KB和35KB，很显然分区3是容量最小的分区，则系统将此分区分配给作业3，同时将其分配状态和标志分别修改为已分配和作业3。如果采用最先适应算法进行分配，在查找分区分配表时，找到的第一个能满足作业要求的分区是分区2，则将该分区分配给作业3，同时跟最佳适应法一样修改分区2对应的分配情况和标志。2007.7.294计算机组成原理从上述分区过程中，我们不难看出，最佳适应法给作业分配的空间是最合适作业运行的空间，这就是“最佳”的原因，但是分配的速度较慢，在分配前系统要查找分区分配表的所有表项，然后才能找到最佳的分区，随着内存容量的增大、分区的增多，此查找过程所需要的时间将会很长；而最先适应算法分配空间的速度最快，不需要查找所有的表项，但是最先适应算法容易造成空间的浪费，如前所述，给作业3分配的分区为分区2，根据固定分区的思想，该分区的剩余空间不能在分配给其他作业，则作业2占用的空间为30KB，浪费的空间为7KB，如果再有一个28KB的作业进入系统，则势必将作业5分配给该作业，又再次造成7KB的空间浪费，降低了存储空间的利用率。因此，无论采用那种分配方式，固定分区都不能完全满足系统对速度和空间利用率的要求。2007.7.295计算机组成原理（2）可变分区分配所谓可变分区分配是指先不给内存分区，给作业分配时，根据作业运行时对内存的需要再从剩余空间中分出一部分给该作业。经过一段时间的分配后内存也将分为若干区域，因此，在可变分区中也需要设置分区分配表。2007.7.296计算机组成原理假设内存容量为256KB，有以下申请和释放内存的操作顺序：作业1申请20KB，作业2申请30KB，作业3申请40KB，作业4申请30KB，作业1释放20KB，作业3释放40KB。则其内存的分布情况如下所述。当4个作业申请完内存之后，内存分布情况如图4-22（a）所示，跟固定分区一样，为了对内存进行有效地管理，每次分区后也将对分区分配表进行修改，从而得到图4-22（b）所示的分区分配表。2007.7.297计算机组成原理20KB（作业1）30KB（作业2）40KB（作业3）30KB（作业4）136KB2007.7.298计算机组成原理分区序号起始地址（K）分区大小（KB）分配状态标志1020已分配作业122030已分配作业235040已分配作业349030已分配作业45120136未分配02007.7.299计算机组成原理与固定分区时的分区情况相同，给作业分配空间后，内存都被分成了很多大小不同的分区。但是他们的区别是：每个分区的大小的确定方法不同。固定分区中每个分区的大小在给作业分配之前就已经确定好了，而可变分区中每个分区的大小是在分配时根据作业的大小确定。空闲分区不同。固定分区中，空闲区要按分区前的分区大小分成几个空闲区，而可变分区中，空闲分区可能是一个连续的区域。作业1和作业3释放空间后的内存分配情况和分区分配表如图4-23所示。2007.7.2100计算机组成原理20KB30KB（作业2）40KB30KB（作业4）136KB2007.7.2101计算机组成原理分区序号起始地址（K）分区大小（KB）分配状态标志1020未分配022030已分配作业235040未分配049030已分配作业25120136未分配02007.7.2102计算机组成原理图4-23（a）所示的分区情况如果不加以修改，则会出现以下两种情况：如果还有一个需要140KB的运行空间的作业5进入系统。此时剩余空闲区的总和为196KB，比作业所需要的空间大，但是因此时的空闲空间被分成了三个区，每个区都不足以给作业5分配，从而导致作业5无法运行。如果还有一个需要38KB的运行空间的作业6进入系统，则系统将会从40KB空闲空间中分出38KB分配给作业6，产生2KB的剩余空间，但是因为空间太小，这2KB的剩余空间可能无法满足任何作业的运行需求，从而成为“碎片”。系统进行多次内存分配后，碎片问题将会越来越严重，导致内存空间被浪费，降低内存的利用率。2007.7.2103计算机组成原理因此，在采用可变分区方式的系统中，常常会采用以下方法来解决上述两个问题：（1）移动。如果内存中，有多段不连续的空闲区域，则将分配区域向低地址方向或高地址方向移动，使得空闲区域构成一个连续的区域。移动后，图4-23所示的内存分配将变成图4-24所示的内存分配情况。2007.7.2104计算机组成原理30KB（作业2）30KB（作业4）20KB40KB136KB2007.7.2105计算机组成原理分区序号起始地址（K）分区大小（KB）分配状态标志1030已分配作业223030已分配作业436020未分配048040未分配05120136未分配02007.7.2106计算机组成原理（2）合并。将空闲区域合并成一个较大的空闲区域。以便再次分配，满足作业要求。合并后的分区情况如图4-25所示。30KB（作业2）30KB（作业4）206KB2007.7.2107计算机组成原理分区序号起始地址（K）分区大小（KB）分配状态标志1030已分配作业223030已分配作业4360206未分配02007.7.2108计算机组成原理经过移动和合并之后，内存的所有不连续的小的空闲区组成了一个连续的大的空闲区，保证后面进入系统的作业能正常分配空间。然而，这种方法在能解决碎片问题和空闲区不连续的问题的同时，会产生一个新的问题，即移动时机的选择问题。对内存进行整体移动所需要花费的时间非常长，移动过程中，CPU将停止工作。所以，如果移动时机选择不当，将会严重影响系统性能。前面介绍的几种分区分配方式，都有自己的优点和不足，分配方法也各不相同，但是他们有一个共同点，就是：一个作业占用一段连续的内存空间，当空闲空间比作业运行所需要的空间小时，作业将无法进入系统。2007.7.2109计算机组成原理3.分页虚拟存储在可变分区分配中，为了解决空闲区不连续问题而采用了移动作业的内存空间的方法，系统开销非常大，而且采用的方法是让硬件适应软件的方法。其实解决上述问题的也可以从另一方面入手，那就是让软件去适应硬件。这里所说的软件是作业，硬件是内存。既然移动内存需要花费很多CPU时间，那就将作业划分为几个部分，每个部分存在一个空闲区域中，这样，要保存一个较大的作业就不需要找到一个比作业空间大的空闲空间，而只需要多个空闲块的容量之和大于作业容量即可。2007.7.2110计算机组成原理为了方便内存管理，人们首先想到的是将作业按统一的大小划分成多个“页”，同时也将内存按页面大小划分成若干个“物理块”（简称“块”），并对页和块按地址从低到高的顺序编号。分配内存时，因为页的大小与块的大小相同，所以每个页就对应一个块。此时，只要剩余块的数量不小于作业页的数量，则不需要作业占用的所有块地址都连续。也就不需要将内存的所有空闲区域移动到一起了。2007.7.2111计算机组成原理采用分页存储能用不连续的存储空间存储作业，但是也将引出新的问题，那就是如何让页的逻辑关系不变，即当前面的页运行完的时候，如何寻找下一个应该运行的页。为了解决这一问题，在分页存储中，需要一种新的数据结构――页表。页表的结构见表4-6所示。2007.7.2112计算机组成原理页号块号010145250325415……2007.7.2113计算机组成原理页表的每一行就是一个页面的信息，分为两项，第一项是页号，第二项是该页对应的块。作业执行时，所有程序和数据必须从内存块中取得。因此在执行某一个块的程序前，系统按页号从低到高的顺序查找页表，根据页表的记录找到该页对应的物理块，进而执行块中的程序和数据。分页时是按逻辑地址进行的，页的顺序就是程序执行的先后顺序，因此，尽管将一个作业分成很多页，作业的执行顺序也不会受到影响。然而，程序员是按照逻辑地址编程，程序却是按照其物理地址执行，因此，在分页式存储管理系统中，逻辑地址是否能转换为正确的物理地址，将直接影响作业执行的正确性。逻辑地址结构如图4-26所示。页号页内地址2007.7.2114计算机组成原理作业页的大小和物理块的大小相同，在地址转换时，页内地址可以直接作为块内地址。但是，页号和物理块号并不能一一对应，如表4-6中，0号页面对应于10号块，1号页面对应于45号块等等，因此不能用页号直接访问物理块。因为页表记录这页与块的对应关系，所以作业执行时，系统需要经常通过访问页表将逻辑地址转换为物理地址。其过程如图4-27所示。2007.7.2115计算机组成原理2007.7.2116计算机组成原理分页系统虽然克服了前面几种分区方法的缺点，很好地克服了碎片问题，但是系统的空闲物理块数量必须不小于作业的页数量时，否则作业也将无法运行。根据程序的顺序性和局部性原理，程序要执行并不需要所有的页面同时进入内存，只需要正在运行或马上即将运行的页面在内存中即可，即只允许少量页面进入内存，作业一样能运行。其中最简单可行的办法就是请求分页存储系统。2007.7.2117计算机组成原理4.请求分页虚拟存储所谓“请求”，是指不将作业的所有页同时放入内存，而是作业在运行过程中需要某个页时，如果该页没有在内存中，则请求中断，让系统将该页从外存放入内存。因此，在给作业分配空间时，不需要按作业的页数分配物理块，而是只给作业分配少量的物理块，然后通过一定的置换机制实现用少量的物理块运行较大的作业。所谓“置换”是指当作业需要某个没有在内存中的页时，如果系统分配给作业的几个物理块已经全部被占满，则根据一定的算法将内存中的页面调到外存，而将马上要运行的页调入内存。比如：系统分配给某作业三个物理块，此三个物理块分别保存作业的2、4和6号页，当作业需要运行5号页时，因为系统分配给该作业的三个块已经被占满，则需要从2、4和6号页中选择淘汰一个，将其调出内存，而将5号页面放入内存运行。如果置换算法设计不当，则页将会频繁地调入调出内存，增大系统开销，降低系统性能，特别是“颠簸”问题的存在，给置换算法提出了很高的要求。2007.7.2118计算机组成原理“颠簸”是指刚调出内存的页，由于马上又运行，则需要重新将此页面调入内存。所以选择何种置换算法将直接影响请求分页虚拟存储的性能。常用的页面置换算法主要有：先进先出置换算法、最久不用置换算法和最近最久未用置换算法。2007.7.2119计算机组成原理（1）先进先出置换算法采用先进先出（FIFO）置换算法，淘汰的页是最先进入内存的页先进先出置换算法利用了队列的特点得以实现。队列就是一种先进先出的数据结构，最先进入队列的元素排在队首，第二进来的元素排在队首后面，依此类推，最后进入的队列的元素排在队尾。不管队列中的元素如何变化，队首元素永远是队列所有元素中最先进入的，因此在采用队列的方法时，要淘汰一个页面的时候只需要将队首元素淘汰，此时第二个元素将成为新的队首元素，然后将作业需要的新页放在队尾位置，如此循环就可以实现新老页的替换。2007.7.2120计算机组成原理置换过程中要注意缺页和置换发生的时机。缺页是在作业要执行的页没有在内存中时发生，跟系统分配给作业的几个块是否被占满无关。而置换则是在作业要执行的页没有在系统中，且分配给作业的块已经被占满的时候发生。本例中的前3个页进入内存时，内存块没有被占满，所以只发生了缺页，没有发生置换；后面的新页进入内存时，内存块已经被占满，所以将同时发生缺页和置换。当然，实现FIFO还有其他方法，不过用队列实现FIFO，方法简单、不容易出错，建议读者熟悉此方法。2007.7.2121计算机组成原理（2）最久不用置换算法FIFO置换算法中，置换的页是最先进入内存的页，这种方法虽然实现简单，但是性能却并不好，容易出现“颠簸”现象。理论上，在相同的页面使用顺序时，最久不用置换算法是性能最好的算法，但是，实际上，作业执行过程中，很难确定页的使用顺序，也就无法确定内存中的哪个页为将来最久不会使用的页，因此该算法是无法实现的。2007.7.2122计算机组成原理（3）最近最久未用置换算法（LeastRecentlyUsed，LRU）FIFO置换算法虽然实现起来非常简单，但是性能较差；最久不用置换算法性能最好，但是无法实现。在实际使用时，这两种算法都很少使用，经常使用的是最近最近未用置换算法。2007.7.2123计算机组成原理根据程序执行的顺序性和局部性，当一个页刚刚被使用过，则该页被再次使用的几率较高；相反，越早使用过的页，被再次使用的几率越低。最近最久未用算法就是基于作业的这一特性设计的。最近最久未用置换算法在进行页面置换时，总是将处于内存的几个页中，最后一次使用时间距离当前时间最久的那一个页淘汰。在用该算法进行页面置换时，必须首先要确定哪个页是最后被使用的。2007.7.2124计算机组成原理4.5.2段式虚拟存储通过前面的学习，我们知道，页式虚拟存储因为页的大小跟物理块的大小相同，所以很大程度上解决了存储管理的碎片问题。但是按照固定的大小对作业进行分页，往往会破坏作业本身的逻辑结构，因为现在的程序大都按其功能分为很多的子程序，而子程序的大小各不相同，更不会是刚好页大小的整数倍，所以如果单纯对作业进行分页，则有的页可能会包含有一个子程序的结尾部分和另外一个页的开始部分。这就完全破坏了程序的模块化。然而模块化思想解决软件危机的最基本的思想，编程序时要注意程序模块化，存储管理时更要注意保持子程序的完整性。2007.7.2125计算机组成原理1.分段原理程序模块化的最基本的思想是为每一个功能都编制一段程序，比如学生学籍管理系统可以分为数据输入、数据维护、用户检索等功能，不同功能由不同的模块完成，模块间可能会互相调用。为了保证程序的正常执行和模块间的正确调用，每一个模块都必须有自己的标识符，系统也可以通过标识符区分不同功能的模块，因此可以用模块所完成的功能对模块进行命名，将模块名作为标识符，并对各模块进行编号。2007.7.2126计算机组成原理程序的每一个模块都可以作为一个段，模块的编号可以作为段的编号。为了对模块内的语句进行正确寻址，也需要有一个段内地址。因此，分段存储管理下，地址结构如图4-32所示。段号段内地址2007.7.2127计算机组成原理要对某个子程序中的某个语句进行访问，首先知道该语句所在的子程序的编号，即段号，其次要知道该语句相对于子程序的起始地址的偏移量，即段内地址。在如图4-32所示的结构中，当知道某个语句的地址时，系统将首先取出地址中的段号，根据段号找到相应的子程序，然后再通过地址中的段内地址找到语句。2007.7.2128计算机组成原理2.存储空间分配段式存储管理系统中，由于按照逻辑关系将作业分成了若干段，所以没有必要给作业分配一个连续的地址空间，只需要给每个段分配一个连续的空间即可。因此在段式存储管理方式下，逻辑相邻的段可能在物理地址上不连续。如图4-33所示。2007.7.2129计算机组成原理2007.7.2130计算机组成原理图4-33中，作业分成了4段，各段占用不连续的内存空间。段1大小为20KB，占用起始地址为80KB的空间；段2大小为30KB，占用起始地址为160KB的空间；段3大小为10KB，占用起始地址为130KB的空间；段4大小为40KB，占用起始地址为250KB的空间。2007.7.2131计算机组成原理3.段表图4-33中，假如作业按照段1、段2、段3、段4的顺序执行，段空间不连续，当作业执行完前一个段后，如何知道下一个段的内存起始地址呢？因此必须有种数据结构来保存各段对应的物理空间，其中应该包括段号、分给该段的空间的起始地址和长度等信息，段表就是这样一种数据结构，能记录段的空间的各种信息。图4-33所示的段空间分配状态所对应的段表如表4-7所示。2007.7.2132计算机组成原理段号起始地址（K）长度（KB）180202160303130104250402007.7.2133计算机组成原理设置段表后，当作业开始运行时，首先查找段表，找到第一个段的内存起始地址，并根据起始地址和长度计算出终止地址，当作业执行到第一段的终止地址时，根据段表记录再去查找第二个段对应的内存地址，如此反复，即可在段表的辅助下将作业的4个段正确执行。2007.7.2134计算机组成原理上述过程实际是将作业的逻辑地址转换成物理地址的过程。作业根据将要执行的语句的逻辑地址计算出段号和段内地址，然后根据逻辑地址查找段表，得到相应的内存段的起始地址，将此起始地址加上段内地址即是该语句的物理地址。此地址变换过程跟分页式存储管理地址变换过程类似，如图4-34所示。2007.7.2135计算机组成原理2007.7.2136计算机组成原理图中4-31所示地址转换过程中的最后一步是进行地址计算，意思是将段内地址和查段表得到与段对应的内存区的起始地址相加得到将要访问的语句的物理地址，从而实现逻辑地址到物理地址的转换。2007.7.2137计算机组成原理4.5.2段页式虚拟存储段式存储管理保证了程序的逻辑性不遭破坏，但是每个段需要占用一段连续的空间，因此，单纯的段式存储具有连续分配的缺点，即作业的空闲空间之和大于作业所需要的空间，但是每一个小的空闲空间不一定能满足各个段的需要。如图4-33所示，作业的4个段分别需要10KB、20KB、30KB和40KB