第5章存储器管理.ppt

《第5章存储器管理.ppt》由会员分享，可在线阅读，更多相关《第5章存储器管理.ppt（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第5 5章章 存储器管理存储器管理（一）（一）主存的共享方式主存的共享方式（二）（二）主存管理的功能主存管理的功能（三）（三）分区存储管理技术分区存储管理技术（四）（四）页式存储管理技术页式存储管理技术（五）（五）段式及段页式存储管理技术段式及段页式存储管理技术（一）（一）主存的共享方式主存的共享方式一一.存储器存储器 (storage,(storage,memmorymemmory)能接收数据和保存数据、而且能根据命令提供这些数据的装置。二二.存储器的分类存储器的分类n n 内内存存储储器器（简简称称内内存存、主存）主存）n n 外外存存储储器器（简简称称外外存存、辅存）辅存）n n处处理

2、理机机能能直直接接访访问问的的存存储储器器。用用来来存存放放系系统统和和用用户户的的程程序序和和数数据据，其其特特点点是是存取速度快，存存储储方方式式是是以以新新换换旧旧，断电信息丢失。n n 处处理理机机不不能能直直接接访访问问的的存存储储器器。用用来来存存放放用用户户的的各各种种信信息息，存存取取速速度度相相对对内内存存而而言言要要慢慢得得多多，但但它它可可用用来来长期保存用用户户信信息息。在在文文件件系系统中介绍。统中介绍。三三.主存的共享方式主存的共享方式空间分片空间分片n n 大小不等的区域大小不等的区域 分区存储管理分区存储管理 分段存储管理n n 大小相等的片大小相等的片 页式存

3、储管理页式存储管理n n 两者结合两者结合 段页式存储管理段页式存储管理（二）主存管理的功能（二）主存管理的功能一一.几个概念几个概念1.1.物物理理地地址址（绝绝对对地地址址、实地址）：实地址）：把内存分成若干个大小相等的存储单元，每个单元给一个编号，这个编号称为内存地址，是计算机主存单元的真实地址。存储单元占8位，称作字节（byte）。2.2.物理地址空间：物理地址空间：物理地址的集合称为物理地址空间（主存地址空间），它是一个一维的线性空间。3.3.逻辑地址（相对地址、虚地址）逻辑地址（相对地址、虚地址）:用用户户编编程程序序时时所所用用的的地地址址。基基本本单单位位可可与与内内存存的的基

4、基本本单位相同，也可以不相同。单位相同，也可以不相同。4.4.作作业业地地址址空空间间（逻逻辑辑地地址址空空间间、虚虚地地址址空空间间）:用用户户程程序序地地址址的的集集合合称称为为逻逻辑辑地地址址空空间间，它它的的编编址址总总是是从从0 0开开始始的的，可可以以是是一一维维线线性性空空间间，也也可可以以是是多多维维空间。5.5.作业地址空间与主存空间作业地址空间与主存空间二二.主存管理的功能主存管理的功能1.地址映射地址映射将程序地址空间中使用的逻辑地址变换成主存中物理地址的过程.2.主存分配主存分配 按照一定的算法把某一空闲的主存区分配给作业或进程。3.存储保护存储保护 保证用户程序(或进

5、程映象)在各自的存储区域内操作，互不干扰。4.主存扩充（提供虚拟存储技术）主存扩充（提供虚拟存储技术）向用户提供一种不受物理存储器大小和结构限制的用户编程时使用的存储器。即使在用户程序比主存容量还要大的情况下，程序也能正确运行。三三.主存映射主存映射1.1.什么是地址映射什么是地址映射（1）为什么要进行地址映射）为什么要进行地址映射 作业的相应进程在处理机上运行时，所要访问的指令和数据的实际地址和地址空间中的地址是不同的。（2）地址映射的定义）地址映射的定义 将程序地址空间中使用的逻辑地址变换成主存中的地址的过程称为地址映射。有时也称为地址重定位。2.2.地址映射的方式地址映射的方式（1）编程

6、或编译时确定地址映射关系不能浮动的程序模块（2）静态地址映射（3）动态地址映射（1）静态地址映射（静态重定位）静态地址映射（静态重定位）评价评价:n优点是实现简单，不要硬件的支持。n缺点是程序一旦装入内存，移动就比较困难。有时间上的浪费。在程序装入内存时要将所有访问内存的地址转换成物理地址。在程序装入内存时程序装入内存时完成从逻辑地址到物理地址的转换的。（重定位装入程序）（2）动态地址映射）动态地址映射在在程程序序执执行行期期间间，随随着着每每条条指指令令和和数数据据的的访访问问自自动动地地连连续续地地进进行行地地址址映映射射。一一般般由由系系统统硬硬件件完完成成从从逻逻辑辑地地址址到到物物理

7、理地址的转换的。地址的转换的。系系统统中中设设置置了了重重定定位位寄存器寄存器。n n动态地址映射由硬件执行时完成，程序中不执行的程序就不做地址映射的工作，这样节省了CPU的时间。n n动态地址映射技术能满足以下目标：（1）具有给用户程序任意分配内存区的能力（2）可实现虚拟存储（3）具有重新分配的能力（4）对于用户程序，可以分配到多个不同的存储区3.3.静态地址映射与动态地址映射的区别静态地址映射与动态地址映射的区别 静态地址映射静态地址映射 动态地址映射动态地址映射 在作业装入过程中 在程序执行期间 进行地址映射 进行地址映射 需软件 需硬件地址变换机构 重定位装入程序 重定位寄存器 需花费

8、较多CPU时间 地址变换快 不灵活 灵活 四四.主存分配主存分配1.1.构造分配用的数据结构构造分配用的数据结构 主存资源信息块：等待队列头指针 自由主存队列头指针 主存分配程序地址 2.2.制定分配策略制定分配策略（1）放置策略：决定内存中放置信息的区域（或位置），即如何在若干个空闲区中选择一个或几个空闲区的原则（2）调入策略：决定信息装入内存的时机预调策略：在执行前将信息预先调入内存预调策略：在执行前将信息预先调入内存请调策略：在用户请求时将信息调入主存请调策略：在用户请求时将信息调入主存（3）淘汰策略：在主存中没有任何可用的空闲区（内存不足）时，决定哪些信息从主存中移走，即确定淘汰已占用

9、的内存区的原则3.3.实施主存分配与回收实施主存分配与回收五五.主存扩充（提供虚拟存储器）主存扩充（提供虚拟存储器）1 1、问题的提出、问题的提出用户程序结构：n一维空间一维空间 一个用户程序就是一个程序，并且程序和数据是不分离的n二维空间二维空间 程序由主程序和若干个子程序（或函数）组成，并且程序与数据是分离的 nn维空间维空间 即一个大型程序，由一个主模块和多个子模块组成，其中，各子模块又由主程序和子程序（或函数）组成n物理存储器的结构是个一维的线性空间，容量是有限的。n用户程序可能比内存容量小，也可能比内存容量大，有时候要大得多。n在主存容量十分紧张的情况下，如何让用户使用计算机不受主存

10、容量的限制？如何将与物理内存结构不同，且大于物理内存容量的用户程序装入运行？2.2.解决问题的思路解决问题的思路 装入部分程序地址空间，它还能正确地执行？3.3.实现方法实现方法 程序的全部代码和数据存放在辅存中；将程序当前执行所涉及的那部分程序代码放入主存中；程序执行时，当所需信息不在主存，由操作系统和硬件相配合来完成主存从辅存中调入信息，程序继续执行。4.4.什么是虚拟存储器什么是虚拟存储器 n由操作系统和硬件相配合来完成主存和辅存之间的信息的动态调度。这样的计算机系统好像为用户提供了一个其存储容量比实际主存大得多的存储器（虚拟存储器）。n现代计算机操作系统都采用了这种技术，使得用户编程序

11、时不需要考虑物理内存的结构和容量，极大地方便了用户。n虚拟存储器需要大容量的外存储器的支持，或称物质基础。5.5.虚拟存储器的核心虚拟存储器的核心 逻辑地址与物理地址分开 主存空间与地址空间分开 提供地址变换机构 6.6.实现虚拟存储器的物质基础实现虚拟存储器的物质基础 有相当容量的辅存 足以存放多用户的作业的地址空间 有一定容量的主存 存放运行进程的当前信息 地址变换机构六六.存储保护存储保护1.1.什么是存储保护什么是存储保护在多道程序设计的环境下，系统中有系统程序和多个用户程序同时存在，如何保证用户程序不破坏系统程序，用户程序之间不相互干扰？主存储器按区分配给各用户程序使用。为了互不影响

12、，由硬件(软件配合)保证每道程序只能在给定的存储区域内活动，这种措施叫做存储保护。2.2.存储保护方法存储保护方法常用的存储保护有两种：界地址保护存储键保护3.3.界地址保护界地址保护（1）上下界防护）上下界防护n下界寄存器 存放程序装入内存后的始地址（首址）n上界寄存器 存放程序装入内存后的末地址n判别式：（下界寄存器）物理地址（上界寄存器）n n例：例：有一程序装入内存的首地址是500，末地址是1500，访问内存的逻辑地址是500、345、1000。下界寄存器：500 上界寄存器：1500 逻辑地址装入内存的首地 物理地址 1、500500 1000 500 1000 1500 2、345

13、500 845 500 845 1500 3、1000500 1500 500 1500 1500（2）基址、限长寄存器保护）基址、限长寄存器保护n基址寄存器：存放程序的起始地址。n限长寄存器：存放程序的长度（单位：字节）n判别式：0 程序地址 （限长寄存器）n n例：例：有一程序装入内存的首地址是500，末地址是1500，访问内存的逻辑地址是500、345、1000。基址寄存器：500 限长寄存器：1000 1、500 500 1000 2、500 345 1000 3、500 1000 10004.4.两种存储保护技术的区别两种存储保护技术的区别 1、寄存器的设置不同2、判别式中用的判别条

14、件不同上下界寄存器保护法用的是物理地址物理地址基址、限长寄存器保护法用的是程程序序的的逻辑地址地址（三）（三）分区存储管理分区存储管理一一.动态分区分配动态分区分配1.1.什么是动态分区分配什么是动态分区分配在在处处理理作作业业的的过过程程中中，建建立立分分区区，依依用用户户请求的大小请求的大小分配分区。分配分区。系统生成后，操作系统占用内存的一部分，一般在物理内存的开始处，比如，一个操作系统占20KB，装入系统后占用020KB的内存空间，剩下的部分作为一个空闲区，当一个用户程序（作业、进程）调入内存时，把这个空闲区的低地址部分的区域分配给它。2.2.动态分区的分配、回收过程动态分区的分配、回

15、收过程 (1)动态分区的分配过程动态分区的分配过程(2)动态分区的回收过程动态分区的回收过程 当有作业完成后释放所占用的存储区。在系统运行的过程中，系统中形成多个空闲的不连续的存储区，称主存空闲。二二.分区分配机构分区分配机构1.1.分区描述器分区描述器flagflag：为为 00空闲区空闲区 为为 11已分配区已分配区 sizesize：分区大小分区大小 nextnext：空闲区空闲区自由主存队列中的勾链字自由主存队列中的勾链字 已分配区已分配区此项为零此项为零分配标志flag大小size勾链字next2.2.自由主存队列结构自由主存队列结构三三.分区的分配与回收分区的分配与回收1.1.分区

16、分配分区分配 用户请求分配一个主存块 分区分配程序在自由主存队列中找一个满足用户需要的空闲块 若找到，则返回所分配区域的首址，否则，告之不能满足要求。n 切割空闲区有两种方法：从空闲区头开始 从空闲区尾开始n 空闲区大小50KB，首址156KB，申请34KB。分区分配算法分区分配算法requestrequest以空闲内存队列的数据结构进行分配。注：注：1、分配算法中切割空闲区是从低低地地址址开始的，例如，一个空闲区大小是100KB，首址是230KB，一申请者要求80KB，分配时将从230KB开始的80KB分配给申请者，剩下的部分仍作为一个空闲区，其首址是310KB，大小是20KB。2、门门限限

17、值值是切割空闲区后剩下的区域若小于门限值，就不切割该空闲区，统统分给申请者。2.2.分区回收分区回收 回收分区回收分区r 上邻空闲区上邻空闲区 回收分区回收分区r 下邻空闲区下邻空闲区r与 f1 合并成为一个大的空闲区f1 r与 f2 合并成为一个大的空闲区f2 回收分区回收分区r 回收分区回收分区r 上、下邻空闲区上、下邻空闲区 上、下邻已分配区上、下邻已分配区 r与 f1、f2 合并成为一个大的空闲区f1 r成为一个新的空闲区f分区回收算法分区回收算法releaserelease当一个进程（或程序）释放某内存区时，要调用存储区释放算法release,它将首先检查释放区是否与空闲区表（队列）

18、中的其它空闲区相邻，若相邻则合并成一个空闲区，否则，将释放为一个空闲区插入空闲区表（或队列）中的适当位置。四四.放置策略放置策略1.1.什么是放置策略什么是放置策略选择空闲区的策略，称为放置策略。空闲区表的组织有两种方法：1、按空闲区大小的升序（降序）组织；2、按空闲区首址升序（降序）组织。根据空闲区表组织的方法的不同，有不同的放置策略：最最佳佳适适应应算法、首首次次适适应应算法和最最坏坏适适应应算法三种。2.2.首次适应算法首次适应算法(1)什么是首次适应算法什么是首次适应算法首首次次适适应应算算法法是是将将输输入入的的作作业业放放置置到到主主存存里里第一个足够装入它的可利用的空闲区中。它的

19、可利用的空闲区中。首首次次适适应应算算法法的的表表是是按按空空闲闲区区首首址址升升序序的的（即空闲区表是按空闲区首址从小到大）方法组织的。(2)首次适应算法的例子首次适应算法的例子(3)特点特点 这种算法的实质是尽可能地利用低地址部分的空闲区，而尽量地保留高地址部分的大空闲区，使其不被切削成小的区，其目的是保证在大的作业到来时有足够大的空闲区满足请求者。3.3.最佳适应算法最佳适应算法(1)什么是最佳适应算法什么是最佳适应算法最佳适应算法是将输入的作业放置到主存中与它所需大小最接近的空闲区中。最佳适应算法的空闲区表按空空闲闲区区大大小小升序升序方法组织。（2）最佳适应算法的例子）最佳适应算法的

20、例子(3)特点特点尽可能地利用存储器中小的空闲区，而保留尽量大的空闲区。这种算法最大的缺点是分割后的空闲区将会很小，直至无法使用，而造成浪费。4.4.最坏适应算法最坏适应算法(1)什么是最坏适应算法什么是最坏适应算法最坏适应算法是将输入的作业放置到主存中最不适合它的空闲区中。最坏适应算法的空闲区表是按空空闲闲区区大大小小降降序序的方法组织的（从大到小的顺序）。（2）最坏适应算法的例子最坏适应算法的例子（3）特点特点克服了最佳适应算法把空闲区切割得大小不等的缺点。即每次分配时，总是将最最大大的空闲区切去一部分分配给请求者，其依据是当一个很大的空闲区被切割了一部分后可能仍是一个较大的空闲区。尽可能

21、地利用大的空闲区，而不分割小的空闲区。5.5.几种放置策略的比较几种放置策略的比较例如：某时刻系统中有三个空闲区，其大小和首址为：(35KB，100KB)、(12KB，156KB)、(28KB，200KB)有一作业序列：(JOB1，12KB)、(JOB2，30KB)、(JOB3，28KB)用首次适应算法、最佳适应算法和最坏适应算法来处理该作业序列，看哪种算法合适。0 035KB156KB首次适应算法0 012KB200KB0 028KBNULL100KB作业1（12KB）放到首址100KB的空闲区0 023KB156KB0 012KB200KB0 028KBNULL112KB作业2（30KB）

22、不能分配作业3（28KB）放到首址200KB的空闲区0 012KB200KB最佳适应算法0 028KB100KB0 035KBNULL156KB作业1（12KB）放到首址156KB的空闲区0 028KB100KB0 035KBNULL200KB作业2（30KB）放到首址100KB的空闲区作业3（28KB）放到首址200KB的空闲区0 05KB200KB0 028KBNULL130KB0 035KB200KB最坏适应算法0 028KB156KB0 012KBNULL100KB作业1（12KB）放到首址100KB的空闲区作业2（30KB）不能继续分配作业3（28KB）放到首址200KB的空闲区0

23、028KB112KB0 023KB156KB0 012KBNULL200KB五五.碎片问题及拼接技术碎片问题及拼接技术1.1.什么是碎片问题什么是碎片问题在已分配区之间存在着的一些没有被充分利用的空闲区。如何解决碎片问题？如何解决碎片问题？2.2.拼接技术拼接技术所谓拼接技术是指移动存储器中某些已分配区中的信息，使本来分散的空闲区连成一个大的空闲区。3.3.解决碎片问题的图示解决碎片问题的图示 4.4.拼接时机的选择拼接时机的选择方案方案1 1：在某个分区回收时立即进行拼接，因此在在某个分区回收时立即进行拼接，因此在 主存中总是只有一个连续的空闲区而无碎主存中总是只有一个连续的空闲区而无碎 片

24、。片。缺点：拼接频率过高，系统开销大。缺点：拼接频率过高，系统开销大。方案方案2 2：当找不到足够大的空闲区，而空闲区的存当找不到足够大的空闲区，而空闲区的存 储容量总和却可以满足作业需要时进行拼储容量总和却可以满足作业需要时进行拼 接。接。缺点：空闲区的管理复杂一些。缺点：空闲区的管理复杂一些。（四）（四）页式存储管理页式存储管理一一.问题的提出问题的提出分区存储管理的主要问题是碎片问题，其实质是让存储器去适应程序对连续性的要求。在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费。造成这样问题的主要原因是用户程序装入内存时是整体装

25、入的，为解决这个问题，提出了分页存储管理技术。二二.页式系统的基本概念页式系统的基本概念1.1.页面页面程序的地址空间被等分成大小相等的片，称为页面，又称为虚页。2.2.主存块主存块主存被等分成大小相等的片，称为主存块，又称为实页。当一个用户程序装入内存时，以页页面面为单位进行分配。页面的大小是为2n,通常为1KB、2KB、2n KB等。3.3.作业页面与主存块的关系作业页面与主存块的关系4.4.页表页表（1）什么是页表）什么是页表为了实现从程序地址空间到物理主存的映象，系统建立的记录页与内存块之间对应关系的地址变换的机构称为页面映像表，简称页页表表。包括用户程序空间的页面与内存块的对应关系、

26、页面的存储保护和存取控制方面的信息。(2)页表的组成页表的组成 高速缓冲存储器组成特点：特点：地址变换速度快，但成本较高地址变换速度快，但成本较高。主存区域 特点：特点：地址变换速度比硬件慢，成本较低地址变换速度比硬件慢，成本较低。5.5.分页映像存储的例子分页映像存储的例子三三.页式地址变换页式地址变换1.1.页表页表记录页与块之间对应关系的地址变换的机构2.2.虚地址结构虚地址结构虚地址是用户程序中的逻辑地址，它包括页页号号和页页内地址内地址（页内位移）。区分页号和页内地址的依椐是页页的的大大小小，页内地址占虚地址的低位部分，页号占虚地址的高位部分。设虚地址长度为16位，页面大小为1KB：

27、页号 页内地址（位移量）P W 15 10 9 03.3.页式地址变换页式地址变换(1)页式地址变换的例子页式地址变换的例子作业地址空间中，设100号单元处有如下指令：mov r1,2500当这条指令执行时，如何进行正确的地址变换。2500 2*1024 +452 p=2 w=4520000100111000100 000010 0111000100例1 页面大小是1KB，虚地址是3BADH例2 页面大小是2KB，虚地址是3BADH(2)页式地址变换过程页式地址变换过程(3)页式地址变换的步骤页式地址变换的步骤 CPU给出操作数地址；由分页机构自动地把逻辑地址分为两部分，得到页号p和页内相对位

28、移w(p=2，w=452)根据页表始址寄存器指示的页表始地址，以页号为索引，找到第2页所对应的块号(为7)最后，将块号b和页内位移量w拼接在一起，就形成了访问主存的物理地址(7*1024+452=7620)1.虚地址以十六进制、八进制、二进制的形式给出n将虚地址转换转换成二进制二进制的数；n按页的大小分分离离出页页号号和位位移移量量（低位部分是位移量，高位部分是页号）；n根据题意产生页表页表；n将位移量位移量直接复制复制到内存地址寄存器的低位低位部分；n以页号查页表，得到对应页装入内存的块号，并将块块号号转换成二进制数填填入入地址寄存器的高高位位部分，从而形成内存地址。2.虚地址以十进制数给出

29、n页号虚地址页大小n位移量虚地址 mod 页大小n根据题意产生页表n以页号查页表，得到对应页装入内存的块号n内存地址块号内存地址块号页大小位移量页大小位移量n 虚地址0AFEH 0000 1010 1111 1110 P1 W010 1111 1110 MR0100 1010 1111 1110 4AFEHn 虚地址1ADDH 0001 1010 1101 1101 P3 W010 1101 1101 MR0010 1010 1101 11012ADDH例1：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH，1ADDH转换成

30、内存地址。例2：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。虚地址 3412 P3412 2048 1 W 3412 mod 2048 1364 MR=9*2048+1364=19796 虚地址3412的内存地址是：19796 虚地址 7145 P7145 2048 3 W7145 mod 2048 1001 MR=5*2048+1001=11241 虚地址7145的内存地址是：12414.4.采用联想存储器加快查表速度采用联想存储器加快查表速度在页式存储技术中，程序每访问一次内存，就要做两次访

31、问内存的工作：n查页表；n程序要求访问的内存。存取速度降低一倍，影响系统的使用效率。解决问题的方法？！解决问题的方法？！早期UNIX系统采用寄存器做页 地址映射机构中就有两套页表机构，叫做页地址映射寄存器组，一套用于核心态，另一套用于用户态。每组有8对寄存器（地址寄存器和说明寄存器），地址寄存器存放页的首地址，说明寄存器存放页的大小，访问方式，存储保护等信息。（1）联想存储器：高速、小容量半导体存储部件，又称缓冲存储器。（2）快表：在缓冲存储器中存放正在运行的进程当前用到的页号和对应的块号，又称为快表。四四.请调策略请调策略1.1.两种页式系统两种页式系统(1)简单页式系统简单页式系统装入一个

32、作业的全部页面才能投入运行。(2)请求页式系统请求页式系统只装入一个作业的部分页面即可投入运行。(1)简单页式系统需要解决什么问题？简单页式系统需要解决什么问题？(2)请求分页系统需要解决什么问题请求分页系统需要解决什么问题?2.2.请求分页系统需解决的问题请求分页系统需解决的问题 (1)怎样发现所访问的页面在不在主存？怎样发现所访问的页面在不在主存？(2)当发现所需访问的页面不在主存时如何处理当发现所需访问的页面不在主存时如何处理?3.3.扩充页表功能扩充页表功能 中断位 I标识该页是否在主存若i=1，表示此页不在主存若i=0，表示该页在主存 辅存地址该页面在辅存的位置页号主存块号 中断位

33、辅存地址4.4.缺页处理缺页处理(1)作作业2在在请求分求分页系系统中的存中的存储映像映像(2)缺缺页处理的例子理的例子作业2的主存块数为 m2=3当程序执行“mov r1，2120”时 CPU产生的虚地址为2120 分页机构得 p=2，w=72 查页表。该页中断位i=1，发生缺缺页中断中断 如主存中有空白块，且nm 则直接调入 如主存中无空白块，或n m，则需淘汰该作业在主存中的一页五五.淘汰策略淘汰策略1.1.什么是淘汰策略什么是淘汰策略用来选择淘汰哪一页的规则就叫做置换策略，或称淘汰算法。如何决定淘汰哪一页？根据页面在系统中的表现 如：使用的频繁程度进入系统时间的长短2.2.扩充页表的功

34、能扩充页表的功能页表应增加相应的内容，反映该页是否在内存，在外存的位置，在内存的时间的长短等。n 引用位：0 表示最近没有进程访问 1 表示最近有进程访问n 改变位：0 该页调入内存后没有修改 1 该页调入内存后修改过页号 主存块号中断位辅存地址 改变位改变位引用位引用位3.3.颠簸颠簸n颠簸(thrashing)，又称为“抖动”。简单地说，导致系统效率急剧下降的主存和辅存之间的频繁页面置换现像称为“抖动”。4.4.常用的淘汰算法常用的淘汰算法(1)先先进先出算法先出算法(FIFO算法算法)思想：优先淘汰最先进入内存的页面，即在内存 中驻留时间最长的页面。n先进入内存的页，先退出内存。n其理由

35、是：最早调入内存的页，不再被使用的可能性比近期调入内存的大。缺点：页面调入的先后次序并不能反映页面的使 用情况。性能比较差，实现简单。(2)最久未使用算法最久未使用算法(LRU算法算法)思想：总是选择最长时间未被使用的那一页 淘汰。n依据的理论是如果某页被访问，它可能马上还要被访问；相反，如果某页长时间未被访问，它可能最近也不可能被访问。n算法的实现（软件）：设置一个活动页面栈，当访问某页时，将此页号压入栈顶，然后，考察栈内是否有与此页面相同的页号，若有则抽出。淘汰一页时，总是从栈底抽出一个页号，它就是最久未使用的。(3)最少使用最少使用频率算法率算法(LFU算法算法)思想：选择淘汰最近时期使

36、用频率最少的页面。n实现时为每个页面设置一个访问计数器，用来记录该页面被访问的频率。n淘汰页面时，选择计数值最小的页面淘汰。（五）（五）段式及段页式段式及段页式存储管理技术存储管理技术一一.段式地址空间段式地址空间1.1.什么是段什么是段分段是程序中自然划分的一组逻辑意义完整的信息集合。2.2.作业地址空间作业地址空间由若干个逻辑分段组成，每个分段有自己的名字，对于一个分段而言，它是一个连续的地址区。3.3.段式地址结构段式地址结构二二.段式地址变换段式地址变换段式地址变换的步骤如下：取出程序地址（S，W）用S段检索段表 如W=L则主存越界。（BW）即为所需主存地址。三三.页式系统与段式系统的

37、区别页式系统与段式系统的区别 1.1.用户地址空间的区别用户地址空间的区别 页式系统中用户地址空间 一维地址空间 段式系统中用户地址空间 二维地址空间2.2.分段与分页的区别分段与分页的区别 分分 段段 分分 页页 信息的逻辑划分 信息的物理划分 段长是可变的 页的大小是固定的 用户可见 用户不可见 W字段的溢出 W字段的溢出将产生越界中断 自动加入到页号中四四.段页式存储管理段页式存储管理1.在段式存储管理中结合分页存储管理技术，在一个分段内划分页面，就形成了段页式存储管理。2.段页式系统中段表、页表与主存的关系第七章第七章 小结小结一一.基本概念基本概念1.逻辑地址、作业地址空间物理地址、

38、物理地址空间2.地址映射 定义类型：静态地址重定位 定义 实现 动态地址重定位动态地址重定位 定义 实现3.虚存 定义 4.存储保护定义方法二二.分区存储管理分区存储管理1.什么是动态分区分配2.分区分配方法：数据结构（自由主存队列结构）、分配算法、分区回收（回收分区的四种情况）3.放置策略：首次适应算法 定义 特点 最佳适应算法 定义 特点 两种放置策略的讨论4.分区分配的缺点及解决：碎片 拼接三三.页式存储管理页式存储管理1.页式地址变换：页面 块 页表地址变换过程2.请调策略：扩充页表功能 中断位 辅存地址3.淘汰策略：扩充页表功能 引用位 改变位抖动置换算法 定义 常用的两种算法4.段式系统的二维地址结构