操作系统5存储n

第五章存储§5.1计算机系统中的存储体系§5.2分区存储管理§5.3页式存储管理§5.4段式存储管理§5.5段页式存储管理§5.6虚拟存储§5.1计算机系统中的存储体系高速缓存（Cache）：

少量使用、非常快速、昂贵内存（主存、RAM）：

数百M字节、中等速度、中等价格外存（辅存、硬盘）：数十G字节、低速、价廉

OS协调这些存储器的使用。存储管理主要指内存管理，内存是系统中仅次于CPU的宝贵资源，“瓶颈”资源。Cache内存外存价格速度高低慢快存储器的层次结构：一、有关存储管理的基本概念§5.1计算机系统中的存储体系内存储器（简称内存、主存、物理存储器）处理机能直接访问的存储器。用来存放系统和用户的程序和数据，其特点是存取速度快，存储方式是以新换旧，断电信息丢失。外存储器（简称外存、辅助存储器）处理机不能直接访问的存储器。用来存放用户的各种信息，存取速度相对内存而言要慢得多，但它可用来长期保存用户信息。在文件系统中介绍。二、内存§5.1计算机系统中的存储体系内存是由存储单元组成的一维连续的地址空间，简称内存空间（存储空间、物理空间）。每个存储单元存放一个字节。内存单元的地址从0开始编址，具有唯一性，内存单元地址称为内存的“物理地址”或“绝对地址”。内存用来存放当前正在运行的程序代码及数据。内存可被CPU直接访问（外存不能）。内存可以分为：系统区：存放操作系统用户区：装入并存放用户程序和数据与地址有关：20根 220＝1M32根 232＝4G三、逻辑地址与逻辑地址空间§5.1计算机系统中的存储体系程序编制过程：使用高级语言(或汇编语言)编写源程序(ASCII码)；编译程序(或汇编程序)将源程序加工成目标程序；（目标程序是二进制机器代码，它以0地址为起点来安排程序和数据）与其它目标程序和库函数一起链接装配成执行程序。（执行程序是二进制机器代码组成，形成了一个地址空间，一个相对于0地址编址的地址空间）该地址空间就是程序的“逻辑地址空间”（相对地址空间）；其中的地址是“逻辑地址”（相对地址）。用户提交给OS运行的程序就是执行程序，执行程序中各部分的地址取决于程序中逻辑关系。§5.1计算机系统中的存储体系DATASEGMENTADB14BDB26CDB13SDB0DATAENDSCOSEGSEGMENTS1:MOVAX,DATAMOVDS,AXMOVAL,AADDAL,BSUBAL,CMOVS,ALCOSEGENDSENDS100101010000100111000000010001110110110001010000000000000000000000000001000000110000000010000000000000110000000100000000010100010000000110000000011110100源程序执行程序010111000一个相对于0地址编址的地址空间编译链接存储空间0系统区用户区运行§5.1计算机系统中的存储体系OS接受用户提交运行的程序，就是这种相对于0编址的执行程序。执行程序装入内存后，如果不做任何变更，就直接运行，是不行的。因为程序中的逻辑地址不可能和真正装入内存后的物理地址相一致，而CPU执行指令时，是按物理地址进行的。若不实行适当的地址变换，程序的执行肯定导致出错。§5.1计算机系统中的存储体系程序A的逻辑地址空间0100001010011K2K

jmp100内存(存储空间)3K020K0010100120K+10021K22K20K+2500jmp10023K系统区占内存0~20K的区域。程序A装入到内存20K~23K区域。若不对“jmp100”中的逻辑地址100做相应调整，则程序的执行将跳转到系统区。100系统区2500四、地址重定位（地址映射）§5.1计算机系统中的存储体系执行程序的正确运行依赖于：OS把程序装入到存储空间（内存）中。即将整个逻辑地址空间安排到内存中的具体物理位置。OS将程序中的逻辑地址变换成适当的物理地址。在装入过程完成后，根据装入的起始位置，来调整修改程序指令中要访问的地址，将逻辑地址改为物理地址。物理地址=BA+逻辑地址

BA是基地址寄存器，存放程序装入内存后起始地址。地址重定位：OS在把用户程序装入内存时，将指令中的逻辑地址变换成物理地址的过程。§5.1计算机系统中的存储体系00101001jmp20580内存(存储空间)010020K20K+10021K22K20K+250023K当执行程序装入内存，OS进行地址重定位，把“jmp100”中的逻辑地址100调整成20580，调整是依据该次装入的起始地址为20K：20×1024+100在多道程序环境里，一个程序的多次运行，其每次运行的装入起始位置并不一定。如某次装入起始位置为22K，则“jmp100”中的逻辑地址100调整成22628：22×1024+100五、静态重定位§5.1计算机系统中的存储体系静态重定位：当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，程序开始运行前，程序中各与地址相有关的项均已重定位完(即已将程序中的相对地址转换成绝对地址了)。以后不再转换（一般在装入内存时由软件完成）OS的“重定位装入程序”进行静态重定位。该程序依据内存分配情况，按照为用户程序分配的区域的起始地址，逐一地调整程序中的地址，使这些地址反映了自己在内存中正确位置，保证程序的正确运行。§5.1计算机系统中的存储体系地址映射LoadA2003456

．．．

1200物理地址空间LoadAdata1data13456源程序LoadA20034560100200编译连接逻辑地址空间BA=10001100六、动态重定位§5.1计算机系统中的存储体系

在程序运行过程中，当执行到某一条指令，其要访问数据时，即时进行的地址变换。一般为了提高效率，此工作由硬件地址映射机制来完成。需要硬件的支持，软硬件结合完成调度一用户程序运行时，把所在分区起始地址送入重定位寄存器；CPU每执行一条指令，就把指令中逻辑地址与重定位寄存器中数值相加，得到物理地址；CPU按物理地址访问内存。§5.1计算机系统中的存储体系011000110LOADA2000100200300LOADA20011000110地址空间110012001300存储空间200+1000…………………重定位寄存器1000系统区逻辑地址空间物理地址空间七、两种重定位的比较§5.1计算机系统中的存储体系1.地址转换时刻静态重定位在程序运行之前完成；动态重定位在指令执行时进行。2.完成的形式静态重定位在装入时一次性全部完成；动态重定位是每执行一条指令时，完成该指令中的地址变换。§5.1计算机系统中的存储体系存储管理目的(或用户对内存的使用要求)(1)、充分利用内存，为多道程序并发执行提供存储基础(2)、尽可能方便用户使用自动装入用户程序、用户程序中不必考虑硬件细节(3)、系统能够解决程序空间比实际内存空间大的问题(4)、程序在执行时可以动态伸缩(5)、内存存取速度快(6)、存储保护与安全(7)、共享与通信(8)、了解有关资源的使用状况(9)、实现的性能和代价§5.2分区存储管理系统把内存用户区划分为若干分区，分区大小可以相等，也可以不等。一个进程占据一个分区。有以下几种具体方案：单一分区存储管理固定分区存储管理动态分区存储管理一、单一连续分区存储管理§5.2分区存储管理最简单的分区方法，早期单道程序系统中采用。

基本思想：把内存分为两个分区：供操作系统使用的系统区。供用户程序使用的用户区，整个用户区仅供一个用户使用。缺点：仅供单道程序使用，系统效率低；若作业小于用户区，就形成碎片（内碎片），浪费；碎片：不连续的小块空闲区若作业大于用户区，就无法运行。二、固定分区存储管理§5.2分区存储管理

基本思想：预先把内存中的用户区分割成若干个连续的分区；每个分区的大小可以相同也可以不同，分割后内存中分区个数和分区大小固定不变；每个分区装一个且只能装一个作业。系统区1分区8K2分区32K3分区64K4分区132K20K28K60K124K0§5.2分区存储管理OS设置一“分区分配表”，记录各分区情况和当前使用信息。“状态”项为0指分区未分配。分配分区方法：当一个程序要求装入，系统检索分区表，查找状态项为0、且容量能满足程序要求的分区。若有，就分配之，将状态项改为1；如找不到，说明本次分配无法进行。回收分区方法：当一个程序运行结束，释放其占有的内存分区时，OS就在分区表中，把该分区的使用状态改写为0，使其成为可供分配的资源。§5.2分区存储管理系统区1分区8K2分区32K3分区64K4分区132K20K28K60K124K分区号起始地址容量状态占用程序120K8K1P1228K32K0360K64K1p24124K132K0分区分配表固定分区图表§5.2分区存储管理固定分区分配算法要求xk大小的分区取分区说明表的第一项该分区空闲吗？分区大小xk表结束吗？返回分区号状态位置1无法分配取下一项NNNYYY§5.2分区存储管理特点：最简单的多道程序存储管理方法，易于实现。为一程序分配某分区时，程序一次性全部装入。实施静态重定位。程序大小与分区大小不大可能正好符合，会产生内碎片。分区总数固定，如此，限制了并发执行的程序数量。三、动态分区存储管理§5.2分区存储管理基本思想：内存不进行预先划分，而是当作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配、如何分配。若有足够的空间，则划分出一个与作业逻辑地址空间同样大小的分区给该作业；否则令其等待内存空间。也称可变分区存储管理§5.2分区存储管理动态分区管理思想示意：a：系统初启，整个用户区是空闲区b、c、d：作业A、B、C先后装入内存，系统逐一为它们划分符合其大小的分区。分区数可变，每个分区的大小随作业需要可变。系统区系统区系统区系统区作业A作业A作业A作业B作业B作业Cabcd空闲区空闲区空闲区空闲区§5.2分区存储管理随着进程的执行，会出现一系列的装入和释放过程，内存中分区情况会动态地发生变化。系统区作业A作业C空闲区空闲区系统区作业A作业C作业D作业B释放作业D装入系统区作业D作业C作业A释放空闲区空闲区空闲区空闲区空闲区§5.2分区存储管理为实现动态分区，采用空闲分区表或空闲分区链表等数据结构，OS据此进行内存分配。空闲分区表：记录内存中现有各分区和各分区的情况，OS配置了“已分配区表”和“空闲区表”，记录了各分区的起始地址、尺寸、状态。以下图例表明利用空闲分区表进行内存分配的样例。该例中可看到，从80K开始的空闲分区，原有30K之大，由于2次分配，现缩小成98K开始的12K大小的空闲分区，即随着分区数目逐渐增大，空闲分区尺寸有逐渐缩小趋势，将导致分区太小分不出去，即形成了“外碎片”。外碎片：无法分配给用户程序的空闲分区。内碎片：已分给了用户而用户未用的存储区。§5.2分区存储管理0K15K38K48K68K80K110K120K空闲区表已分配区表始址尺寸状态15K23K未分配48K20K未分配80K30K未分配空空始址尺寸状态0K15KJ138K10KJ268K12KJ3110K10KJ4空空§5.2分区存储管理0K15K38K48K68K80K110K120K空闲区表已分配区表始址尺寸状态15K23K未分配48K20K未分配98K12K未分配空空始址尺寸状态0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98K§5.2分区存储管理(i)分配算法申请分配一个xk大小的分区置空白区号F＝1(F)的状态＝可用？空白区F大小xk？loc(F)的始址否是请求－主存块程序框图F＝未分配表的结尾？置空白区F，F的状态＝空表目(F)的大小－xk(F)的大小loc+xk(F)的始边在分配表中找一个状态＝空表目的分区P置P分区的大小＝xk置P分区的地址＝loc置状态＝已分配返回一个分区号P本次无法分配一个分区F+1F><=是否(是自由还是空表目)空表目分配与回收§5.2分区存储管理检查是否与空白区相邻，是则合并成一个大空白区修改两个表(返回分配区与空白区序号和始址)(ii)分区回收算法§5.2分区存储管理空闲分区的内存分配算法(1).首次适应算法（NF，next—fit）接到内存申请时，查空闲区表，找到第一个不小于请求的空闲区块，将其分割并分配特点：简单、快速分配，但可能产生许多小分区(2).最佳适应算法（BF，best—fit）接到内存申请时，在空闲区表中找到一个不小于请求的最小空闲区进行分配特点：用最小空间满足要求，保证大空区存在，费时(3).最坏适应算法（WF，Worst－fit）将空白区排序(按从大到小)，找最大空白区特点：不会出现小的空白区。§5.3页式存储管理之前介绍的分区存储管理采用的是连续分配方式，把地址空间的整体安排在内存的连续空间中，这样会在内存中形成许多“碎片”。以下介绍的页式存储管理，采用了离散分配方式，特点是，OS把一个用户程序的地址空间分散地分配到许多不相邻接的分区中，还是能够保证程序运行的正确。现代OS的存储管理一般都使用离散分配方式。一、页式存储管理的基本思想§5.3页式存储管理分块，把内存存储空间划分成大小一定的块，称为物理块（页框、实页）；分页，把用户程序的逻辑地址空间划分成大小一定的块，称为页面（逻辑页、虚页）；分页过程是系统内部进行的，从系统外部，用户眼中是不可见的，或者说对用户是透明的。§5.3页式存储管理...用户作业的逻辑地址空间内存4K24K28K32K36K40K44K48K0256K0~4块第5块第6块第7块第8块第9块第10块第11块第0页第1页第2页系统区08K11K12K逻辑地址空间划分成大小一定页面；内存空间划分成大小一定物理块；页与块大小相等，分别为它们进行编号，从0开始编。20K§5.3页式存储管理...用户作业的逻辑地址空间内存4K24K28K32K36K40K44K48K0256K0~4块第5块第6块第7块第8块第9块第10块第11块第0页第1页第2页系统区08K11K12KOS的存储管理将作业以页面为单位，分散地存放在内存的不连续的空闲物理块中（离散分配）。OS为每个进程设置了一个页表，记录了分配情况。20K§5.3页式存储管理...内存24K28K32K36K40K44K48K0256K0~4块第5块第6块第7块第8块第9块第10块第11块系统区20K分页存储管理的地址结构把整个内存空间划分成大小相等的许多分区，称为“块”（物理块）。物理块大小总是2的方幂（如512、1K、2K、4K等），这样，系统存储管理容易处理。系统内采用同样大小的块。物理块大小应选择适中，通常在512字节到4K字节范围内选择。§5.3页式存储管理用户作业的逻辑地址空间相对于0进行编址，形成一个连续的地址空间。将此空间参照物理块的大小进行划分，每一个分区称为“页面”，从0开始编号。右图中作业有11K，每个页面4K，则系统使其占有3个页面。该空间内的每一个地址采用二元组(页号,页内地址)形式表示。例：相对地址5188，其处在第1页，在该页中的页内地址是1092（5188-4096=1092，4K=4096），所以其逻辑地址采用二元组形式为：（1，1092）。10925188§5.3页式存储管理页式存储管理中，逻辑地址采用的二元组形式，由2部分组成：（页号P，

页内地址W）例：某一系统，地址长度为32位二进制。页内地址(0—～11)低12位[每页大小为212=4K]，页号(12—～31)高20位[地址空间最多220=1M页]；页号P=INT(A/L)

页内地址W=A%LA为逻辑地址，L为页面大小§5.3页式存储管理如何分页？页太小：分页就多，相应建立的页表就长，极端情况是程序变成指令执行。页太长：极端情况就像作业没有分页。不利于内存的多道运行。程序较小时，页大浪费空间。怎样分：一般以2的n次方为单位，便于计算机计算。§5.3页式存储管理例：系统地址结构为16位二进制，该地址空间为64K(216

，0~65535)。如页面长度为1K(1024)。现有一相对地址为3000，它的二进制表示如下图，其二元组形式经过计算，得到(2，952)。可依据页面长度在二进制表示中区分页号与页内位移，因现页面长度为1K，则在下图中第10位处用粗线划分，则低10位表示页内位移(现952与计算结果相同)，高6位表示页号(现2与计算结果相同)。这样就给计算机处理带来极大的便利，不用计算就可取得其二元组表示值。0000101110111000091015页号=2页内位移=952二、页式存储管理的地址转换§5.3页式存储管理1.页表OS为了知道一个作业的每一个页面存放在内存的哪个物理块中，专门建立了一个页、块对应表，即页表。每个进程设置一个页表。逻辑地址空间内的所有页面在页表中占一个表项，主要记录了：作业中各个页面的页号与内存中对应的物理块号。页表的作用：实现从页号到物理块号的地址映射。§5.3页式存储管理2．地址变换地址变换：地址空间中的逻辑地址→存储空间中的物理地址由地址变换机构实现。地址变换机构主要由页表与页表寄存器构成。页表：驻留在内存中（页表项可达几千—几十万个）页表寄存器：存放页表起始地址与页表的长度。一进程的页表起始地址和页表长度存放于本进程的PCB内，当该进程被调度到执行状态时，OS就将其从内存调到页表寄存器中。§5.3页式存储管理当进程访问某逻辑地址3081时，地址变换过程：（逻辑地址3081物理地址）

逻辑地址3081（页号,页内地址）(3,9)[页面长度1K]

比较：页号＞页表长度（页表寄存器中）越界中断

n表项在页表中位置=页表始址+页号×页表项长度

从表项中取得对应该页的物理块号，装入物理地址寄存器

(第3页面对应块号是11)逻辑地址寄存器的页内地址物理地址寄存器的块内地址物理块号11+块内地址9物理地址[11*1024+9=11273]§5.3页式存储管理页表地址越界比较

+页号3

页内地址9物理地址11273页表控制寄存器逻辑地址3081页式存储管理地址映射机制页表始址页表长度页号块号块号11块内地址9

311§5.3页式存储管理具有快表的地址变换机构CPU每读写一个数据，要2次访内（第1次读页表，第2次真正读数）。为提高地址变换速度，在地址变换机构中，增加具有并行查找能力的特殊高速缓冲器，又称“联想存储器”或“快表”。快表中存放当前访问的页表项。快表通常不大，一般存放16—512个页表项（成本关系）。由命中率看效果，一般命中率为80%—90%。§5.3页式存储管理当进程访问某逻辑地址时，地址变换过程（有快表）：（逻辑地址物理地址）

逻辑地址（页号，页内地址）

页号送入快表，在快表中寻找相应页表项找不到转A

找到

从快表的中取得物理块号，装入物理地址寄存器

逻辑地址的页内地址送入物理地址的块内地址

物理块号+块内地址物理地址A：找不到则到页表中查找，找到后须将页表项送快表§5.3页式存储管理页表地址越界比较

+页号

页内地址物理地址页表控制寄存器逻辑地址页表首址页表长度页号块号块号块内地址快表带快表的页式存储管理§5.3页式存储管理页式存储管理的优点不要求作业连续存放，有效地解决了“碎片”问题。与分区式比，不需移动作业；与多重分区比，无零星碎片产生.内存利用率高，不常用的页面尽量不留在内存；§5.3页式存储管理页式存储管理的缺点地址变換机构复杂，为提高速度采用硬件实现，增加了机器成本要处理页面中断、缺页中断处理等，系统开销较大；有可能产生“抖动”;§5.3页式存储管理例：一实现分页式存储管理的系统，内存块大小为2K/块，现有一用户作业，逻辑地址空间为0~5129字节，若将其装入内存，系统分配给它的存储容量为多少字节？有无碎片，大小为多少？解：作业对存储空间的需求为为5130字节；物理块大小为2048字节；INT（5130/2048）=3即需分配给它3个物理块。3物理块占用2048*3=6144字节，所以第2页内将出现1014字节的内部碎片（6144-5130=1014字节）。§5.3页式存储管理例：设一个逻辑地址空间有8个页面，每个页面大小为1024字节，映射到32块物理块的内存上，问：（1）逻辑地址要用多少位表示？（2）物理地址要用多少位表示？解：8=23，需3位二进制表示；

1024=210，需10位二进制表示；

∴逻辑地址要用13位二进制表示。

32=25，需5位二进制表示；

∴物理地址要用15位二进制表示。§5.3页式存储管理例：已知内存容量为64KB，某一作业A的逻辑地址空间共有4K，分为4个页面，页面0、1、2、3分别被分配到内存空间的2、4、6、7四个物理块中，在逻辑地址为200处有一条取数指令“LOAD1，3500”，（1）画出作业A的页表；（2）当指令“LOAD1，3500”执行时，产生的物理地址应是什么？解：（2）3500对应的数对为（3，428），

∴物理地址为（7，428），由于页面大小为1K∴物理地址为：7×1024+428=7596

§5.4段式存储管理一个用户程序往往由几个程序段（主程序、子程序和函数）所组成，当一个程序装入内存时，按段进行分配，每个段的大小是不相等的。程序地址的组成：S：W例:S1：XXXXS2：XXXXS3；XXXX§5.4段式存储管理...0S工作区段[B]主程序段[M]......0EP子程序段[X]0K...CALL[X][E].........CALL[Y][F]CALL[A]116......0FL子程序段[Y]0116N数组[A]12345...§5.4段式存储管理操作系统.....B0SA0NY0LX0PM0K逻辑段号01234作业1的地址空间10003200500060008000PKSLN主存K3200P1500L6000N8000S5000长度段地址01234操作系统§5.4段式存储管理用户程序划分按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的逻辑地址段号段内地址§5.4段式存储管理内存划分内存空间被动态的划分为若干个长度不相同的区域，这些区域被称为物理段，每个物理段由起始地址和长度确定内存分配

以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放§5.4段式存储管理管理段表：它记录了段号，段的首（地）址和长度之间的关系每一个程序设置一个段表，放在内存属于进程的现场信息段号012段首址段长度58K20K100K110K260K140K§5.4段式存储管理硬件支持系统设置一对寄存器段表始址寄存器：用于保存正在运行进程的段表的始址段表长度寄存器：用于保存正在运行进程的段表的长度（例如上图的段表长度为3）§5.4段式存储管理

Cl

Cb+段号S段内地址d比较比较b+d段表S>=Cl快表物理地址段表始址寄存器段表长度寄存器逻辑地址Lb...SLb地址越界d>=Ld>=L地址映射及存储保护机制地址越界地址越界比较§5.4段式存储管理段式存储管理的优越性:段的共享与动态分配，一般由硬件设备的多种支持，特别是近代的优化编译已进入CPU内部设计。段共享的先决条件是程序段可重入，即前面一段没有退出前，在不影响工作前提下，后面一段又可重新装入。而可重入程序的特点是执行程序中指令不变称纯代码（纯码）,而工作区和数据区由调用者自带。§5.4段式存储管理段式与页式存储管理的对比表段式页式由用户设计，有逻辑意义分页用户不可见，由OS划分段面是信息的逻辑单位页面是信息的物理单位便于段的共享和动态链接页一般不能共享段长不等，可动态增长页面大小相同，不能增长段具有二维地址空间页具有一维地址空间管理形式相似，但概念不同一维地址是指用一个逻辑地址就可以转换成相应的物理地址；而二维地址必须要两个地址才能寻址。页式管理中地址给定逻辑地址A，而段式管理需知道段号和段内地址，才能求得物理地址。

§5.5段页式存储管理产生背景及基本思想背景：结合了二者的优点克服了二者的缺点§5.5段页式存储管理基本思想：内存划分：按页式存储管理方案内存分配：以页为单位进行分配段号段内地址页号页内地址用户程序划分：按段式划分（对用户来讲，按段的逻辑关系进行划分；对系统讲，按页划分每一段）逻辑地址：§5.5段页式存储管理管理(1)段表：记录了每一段的页表始址和页表长度(2)页表：记录了逻辑页号与内存块号的对应关系（每一段有一个，一个程序可能有多个页表）(3)空块管理：同页式管理(4)分配：同页式管理§5.5段页式存储管理硬件支持段表始址寄存器段表长度寄存器相联存储器（快表）§5.6虚拟存储以CPU时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术一、概述§5.6虚拟存储

1、问题的提出

程序大于内存程序暂时不执行或运行完是否还要占用内存虚拟存储器的基本思想是：程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换虚拟存储器支持多道程序设计技术§5.6虚拟存储2、程序局部性原理

在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面时间局部性：

一条指令被执行了，则在不久的将来它可能再被执行空间局部性：

若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用§5.6虚拟存储3、虚拟存储技术虚存：把内存与外存有机的结合起来使用，从而得到一个容量很大的“内存”，这就是虚存实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存工作目的：提高内存利用率二、虚拟页式存储管理§5.6虚拟存储1、基本工作原理

在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面§5.6虚拟存储2、页表表项

驻留位（中断位）：表示该页是在内存还是在外存访问位：根据访问位来决定淘汰哪页（由不同的算法决定）修改位：查看此页是否在内存中被修改过页号中断位内存块号外存地址访问位修改位§5.6虚拟存储3、缺页中断（PageFault）在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的驻留位及相应的内存块号若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存三、页面淘汰算法§5.6虚拟存储先进先出页面淘汰算法（FIFO）

选择在内存中驻留时间最长的页并淘汰之第二次机会淘汰算法(SCR)

按照先进先出算法选择某一页面，检查其访问位，如果为0，则淘汰该页，如果为1，则给第二次机会，并将访问位置0理想淘汰算法—最佳页面算法（OPT）淘汰以后不再需要的或最远的将来才会用到的页面§5.6虚拟存储最近最少使用页面淘汰算法（LRU）

选择最后一次访问时间距离当前时间最长的一页并淘汰之即淘汰没有使用的时间最长的页实现代价很高时间戳或硬件方法§5.6虚拟存储LRU的软件解决方案：最不经常使用（NFU）

选择访问次数最少的页面淘汰之实现：软件计数器，一页一个，初值为0。每次时钟中断时，计数器加R