计算机操作系统第7章.ppt

主存管理主存管理主存管理主存管理主存管理概述主存管理概述主存管理概述主存管理概述主存管理的功能主存管理的功能主存管理的功能主存管理的功能分区存储管理分区存储管理分区存储管理分区存储管理页式存储管理页式存储管理页式存储管理页式存储管理段式及段页式存储管理段式及段页式存储管理段式及段页式存储管理段式及段页式存储管理LinuxLinux系统的存储管理系统的存储管理系统的存储管理系统的存储管理1主存管理主存管理主要内容主要内容2主存管理主存管理主存管理概述主存管理概述1.1.主存共享方式主存共享方式主存共享方式主存共享方式大小不等的区域大小不等的区域大小不等的区域大小不等的区域分区存储管理分区存储管理段式存储管理段式存储管理大小相等的区域大小相等的区域大小相等的区域大小相等的区域页式存储管理页式存储管理二者结合二者结合二者结合二者结合段页式存储管理段页式存储管理3主存管理主存管理主存管理概述主存管理概述2.2.程序的逻辑组织程序的逻辑组织程序的逻辑组织程序的逻辑组织一维地址结构一维地址结构一维地址结构一维地址结构一个程序是一个连续、线性的 地址结构；确定线性地址空间中的指令地 址或操作数地址只需要一个信息。程序地址空间程序地址空间01 n-1 4主存管理主存管理主存管理概述主存管理概述二维地址结构二维地址结构二维地址结构二维地址结构一个程序由若干个分段组成，每个分段是一个连续的地址区；确定任一线性地址空间中的指令地址或操作数地址需要两个信息，一是该信息所在的分段，另一个是该信息在段内的偏移量。code_addr4KB 10代码分段代码分段data_addr3KB 10数据分段数据分段stack_addr2KB 10栈段栈段11 51.1.几个概念几个概念几个概念几个概念物理地址物理地址物理地址物理地址 (绝对地址、实地址绝对地址、实地址绝对地址、实地址绝对地址、实地址)物理地址是计算机主存单元的真实地址，又称为绝对地址或实地址。主存空间主存空间主存空间主存空间 物理地址的集合所对应的空间组成了主存空间。逻辑地址逻辑地址逻辑地址逻辑地址 (相对地址、虚地址相对地址、虚地址相对地址、虚地址相对地址、虚地址)用户的程序地址(指令地址或操作数地址)均为逻辑地址。作业地址空间作业地址空间作业地址空间作业地址空间 用户程序所有的逻辑地址集合对应的空间。主存管理主存管理主存管理功能主存管理功能6作业地址空间与主存空间作业地址空间与主存空间作业地址空间与主存空间作业地址空间与主存空间主存管理主存管理主存管理功能主存管理功能主存空间主存空间01m-1作业作业1地址空间地址空间01n-1作业作业 i 地址空间地址空间01k-1 7主存管理主存管理主存管理功能主存管理功能2.2.主存管理功能主存管理功能主存管理功能主存管理功能实现逻辑地址到物理主存地址的映射实现逻辑地址到物理主存地址的映射实现逻辑地址到物理主存地址的映射实现逻辑地址到物理主存地址的映射主存分配主存分配主存分配主存分配 存储保护存储保护存储保护存储保护主存扩充主存扩充主存扩充主存扩充 8主存管理主存管理地址映射地址映射3.3.地址映射地址映射地址映射地址映射什么是地址映射什么是地址映射什么是地址映射什么是地址映射 将程序地址空间中使用的逻辑地址变换成主存中的物理地址的过程，称为地址映射。mov r1,5001230100500599作业地址空间作业地址空间mov r1,50012301000110015001599256k-1存储空间存储空间9主存管理主存管理地址映射地址映射在作业装入时确定地址映射关系在作业装入时确定地址映射关系 在作业装入过程中随即进行的地址变换方式称为静态地址映射静态地址映射。mov r1,500mov r1,500+m01005005990mm+100256k-1作业地址空间作业地址空间存储空间存储空间m+500重定位重定位装入程序装入程序123123地址映射的时机和类别地址映射的时机和类别地址映射的时机和类别地址映射的时机和类别编程或编译时确定地址映射关系编程或编译时确定地址映射关系 在程序编写或程序编译时确定虚、实地址之间的对应关系，结果 是一个不能浮动的程序模块。10主存管理主存管理地址映射地址映射在程序运行时确定地址映射关系在程序运行时确定地址映射关系 在程序执行期间，随着每条指令和数据的访问自动地 连续地进行地址映射，这种地址变换方式称为动态地动态地 址映射址映射。重定位寄存器重定位寄存器 1000 500逻辑地址+0 mov r1,500 1000256k-1存储空间110015001600123mov r1,5000100500599作业地址空间12311主存管理主存管理地址映射地址映射静态地址映射与动态地址映射的区别静态地址映射与动态地址映射的区别静态地址映射与动态地址映射的区别静态地址映射与动态地址映射的区别 静态地址映射静态地址映射 动态地址映射动态地址映射 在作业装入过程中在作业装入过程中 在程序执行期间在程序执行期间 进行地址映射进行地址映射 进行地址映射进行地址映射 需软件需软件 需硬件地址变换机构需硬件地址变换机构 重定位装入程序重定位装入程序 重定位寄存器重定位寄存器 需花费较多需花费较多CPUCPU时间时间 地址变换快地址变换快 不灵活不灵活 灵活灵活 12主存管理主存管理主存管理功能主存管理功能4.4.主存分配主存分配主存分配主存分配构造分配用的数据结构构造分配用的数据结构构造分配用的数据结构构造分配用的数据结构 主存资源信息块主存资源信息块主存资源信息块主存资源信息块：等待队列；空闲区队列；主存分配程序制定策略制定策略制定策略制定策略主存分配策略主存分配策略 在众多个请求者中选择一个请求者的原则放置策略放置策略 在可用资源中，选择一个空闲区的原则调入策略调入策略 决定信息装入主存的时机 预调策略：预先将信息调入主存 请调策略：当需要信息时，将信息调入主存淘汰策略淘汰策略 在主存中没有可用的空闲区(对某一作业而言)时，决定哪些信息从主存中移走，即确定淘汰已占用的内存区的原则。实施主存分配与回收实施主存分配与回收实施主存分配与回收实施主存分配与回收13主存管理主存管理主存管理功能主存管理功能5.5.主存扩充主存扩充主存扩充主存扩充可行性可行性可行性可行性实现方法实现方法实现方法实现方法程序的全部代码和数据存放在辅存中；将程序当前执行所涉及的那部分程序代码放入主存中；程序执行时，当所需信息不在主存，由操作系统和硬件相配合来完成主存从辅存中调入信息，程序继续执行。什么是虚拟存储器什么是虚拟存储器什么是虚拟存储器什么是虚拟存储器 由操作系统和硬件相配合来完成主存和辅存之间的信息的动态调度。这样的计算机系统好像为用户提供了一个其存储容量比实际主存大得多的存储器，这个存储器称为虚拟存储器。局部性特征局部性特征14主存管理主存管理主存管理功能主存管理功能虚拟存储器的核心虚拟存储器的核心虚拟存储器的核心虚拟存储器的核心逻辑地址与物理地址分开逻辑地址与物理地址分开存储空间与虚地址空间分开存储空间与虚地址空间分开提供地址变换机构提供地址变换机构实现虚拟存储器的物质基础实现虚拟存储器的物质基础实现虚拟存储器的物质基础实现虚拟存储器的物质基础有相当容量的辅存有相当容量的辅存有相当容量的辅存有相当容量的辅存 足以存放应用程序的虚地址空间有一定容量的主存有一定容量的主存有一定容量的主存有一定容量的主存 存放进入主存的多进程的信息地址变换机构地址变换机构地址变换机构地址变换机构 15主存管理主存管理主存管理功能主存管理功能6.6.存储保护存储保护存储保护存储保护什么是存储保护什么是存储保护什么是存储保护什么是存储保护 在多用户环境中，主存储器按区分配给各用户程序使用。为了互不影响，必须由硬件(软件配合)保证各用户程序只 能在给定的存储区域内活动，这种措施叫做存储保护。实现方法实现方法实现方法实现方法界地址保护存储键保护16主存管理主存管理主存管理功能主存管理功能界地址保护界地址保护界地址保护界地址保护上下界防护上下界防护 例：作业大小为4KB，主存首址为20KB。mov r1,500 123020KB256KB 1存储空间存储空间24KB下界寄存器下界寄存器 20KB上界寄存器上界寄存器 24KB如何如何设置上下界寄存器内容设置上下界寄存器内容？如何判断是否越界如何判断是否越界？若若 20KBD24KB 允许访问；否则发生越界中断17主存管理主存管理主存管理功能主存管理功能界地址保护界地址保护界地址保护界地址保护基地址、限长防护基地址、限长防护 例：作业大小为4KB，主存首址为20KB。如何如何设置基址、限长寄存器设置基址、限长寄存器内容内容？如何判断是否越界如何判断是否越界？若若 逻辑地址 4KB 允许访问；否则发生越界中断 mov r1,500 123020KB256KB 1存储空间存储空间24KB基址寄存器基址寄存器 20KB限长寄存器限长寄存器 4KB181.1.动态分区分配动态分区分配动态分区分配动态分区分配什么是动态分区分配什么是动态分区分配什么是动态分区分配什么是动态分区分配 在处理作业的过程中，建立分区，依用户请求的大小分配分区。动态分区的分配、回收过程动态分区的分配、回收过程动态分区的分配、回收过程动态分区的分配、回收过程动态分区的分配过程动态分区的分配过程 主存管理主存管理分区存储管理分区存储管理19主存管理主存管理分区存储管理分区存储管理作业作业1申请申请 32KB 0 256KB 1主存主存20KBos20KB 0 52KB256KB 1主存主存os作业1作业作业2申请申请 14KB20KB 0 52KB66KB256KB 1主存主存os作业1作业2作业作业3申请申请 64KB20KB 0 52KB66KB130KB256KB 1主存主存os作业1作业2作业3作业作业4申请申请 100KB20KB 0 52KB66KB130KB230KB256KB 1主存主存os作业1作业2作业3作业4作业作业5申请申请 50KB20主存管理主存管理分区存储管理分区存储管理动态分区的回收过程动态分区的回收过程 作业作业2 完成完成 作业作业4 完成完成 20KB 0 52KB66KB130KB230KB256KB 1主存主存作业1作业2作业3作业4os20KB 0 52KB66KB130KB230KB256KB 1主存主存作业1作业3作业4os20KB 0 52KB66KB130KB230KB256KB 1主存主存os作业1作业3211.1.动态分区分配动态分区分配动态分区分配动态分区分配什么是动态分区分配什么是动态分区分配什么是动态分区分配什么是动态分区分配 在处理作业的过程中，建立分区，依用户请求的大小分配分区。分区分配结构分区分配结构分区分配结构分区分配结构主存资源信息块主存资源信息块主存资源信息块主存资源信息块 (M_RIB)分区描述器分区描述器分区描述器分区描述器 (PD)(PD)主存管理主存管理分区存储管理分区存储管理 等待队列头指针 空闲区队列头指针 主存分配程序入口地址M_RIBflag：为 0 空闲区 为 1 已分配区 size：分区大小 next：空闲区自由主存队列中的勾链字 已分配区此项为零 分配标志 flag 大小 size 勾链字 nextPD22空闲区队列结构空闲区队列结构空闲区队列结构空闲区队列结构主存管理主存管理分区存储管理分区存储管理20KB 0 52KB66KB130KB230KB256KB 1主存主存os作业1作业3作业452KBm-rib 空闲区队列空闲区队列230KB014KB026KB 232.2.分区的分配与回收分区的分配与回收分区的分配与回收分区的分配与回收分区分配思路分区分配思路分区分配思路分区分配思路依申请者所要求的主存区的大小，分区分配程序在自 由主存队列中找一个满足用户需要的空闲块；若找到了所需的空闲区，有两种情况空闲区与要求的大小相等，将该空闲区分配并从队列中摘除；空闲区大于所要求的的大小，将空闲区分为两部分：一部分成 为已分配区，建立已分配区的描述器；剩下部分仍为空闲区。返回所分配区域的首址；否则，告之不能满足要求。主存管理主存管理分区存储管理分区存储管理24分区回收思路分区回收思路分区回收思路分区回收思路检查释放分区(即为回收分区)在主存中的邻接情况；若上、下邻接空闲区，则合并，成为一个连续的空 闲区；若回收分区不与任何空闲区相邻接，建立一个新的空 闲区，并加入到空闲区队列中。主存管理主存管理分区存储管理分区存储管理253.3.放置策略放置策略放置策略放置策略什么是放置策略什么是放置策略什么是放置策略什么是放置策略 选择空闲区的策略，称为放置策略。常用的放置策略 首次匹配(首次适应算法)最佳匹配(最佳适应算法)最坏匹配(最坏适应算法)主存管理主存管理分区存储管理分区存储管理26首次适应算法首次适应算法首次适应算法首次适应算法首次适应算法是将输入的作业放置到主存里第一个足 够装入它的地址最低的空闲区中。主存管理主存管理分区存储管理分区存储管理 作业作业A 18KB首次适应算法的例首次适应算法的例空闲区队列结构空闲区队列结构 空闲区地址由低到高排序首次适应算法的特点首次适应算法的特点首次适应算法的特点首次适应算法的特点 尽可能地利用存储器中低 地址的空闲区，而尽量保 存高地址的空闲区。在使用在使用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存主存os27最佳适应算法最佳适应算法最佳适应算法最佳适应算法最佳适应算法是将输入的作业放置到主存中与它所需 大小最接近的空闲区中。主存管理主存管理分区存储管理分区存储管理 作业作业A 18KB最佳适应算法的例最佳适应算法的例空闲区队列结构空闲区队列结构 空闲区大小由小到大排序最佳适应算法的特点最佳适应算法的特点 尽可能地利用存储器中小的 空闲区，而尽量保存大的空 闲区。在使用在使用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存主存os28最坏适应算法最坏适应算法最坏适应算法最坏适应算法最坏适应算法是将输入的作业放置到主存中与它所需 大小差距最大的空闲区中。主存管理主存管理分区存储管理分区存储管理 作业作业A 18KB最坏适应算法的例最坏适应算法的例空闲区队列结构空闲区队列结构 空闲区大小由大到小排序最坏适应算法的特点最坏适应算法的特点 尽可能地利用存储器中大的 空闲区。在使用在使用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存主存os29三种放置策略的讨论三种放置策略的讨论三种放置策略的讨论三种放置策略的讨论作业A要求18KB；作业B要求25KB；作业C要求30KB。用首次适应算法、最佳适应算法、最坏适应算法来处理 该作业序列，看哪种算法合适。主存管理主存管理分区存储管理分区存储管理30三种放置策略的讨论三种放置策略的讨论三种放置策略的讨论三种放置策略的讨论首次适应算法、最佳适应算法、最坏适应算法的队列结构。首次适应算法、最佳适应算法、最坏适应算法的队列结构。主存管理主存管理分区存储管理分区存储管理 在使用在使用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存主存os(a)首首次次适适应应算算法法的的空空闲闲区区队队列列 20KB 0 30KB 100KB 0 20KB 160KB 0 5KB 210KB 0 46KB (a)最最佳佳适适应应算算法法的的空空闲闲区区队队列列160KB 0 5KB 100KB 0 20KB 20KB 0 30KB 210KB 0 46KB (a)最最坏坏适适应应算算法法的的空空闲闲区区队队列列210KB 0 46KB 20KB 0 30KB 100KB 0 20KB 160KB 0 5KB 31三种放置策略的讨论三种放置策略的讨论三种放置策略的讨论三种放置策略的讨论首次适应算法首次适应算法 主存管理主存管理分区存储管理分区存储管理 作业A要求18KB 作业B要求25KB 作业C要求30KB 首次适应算法对该作业序列是不合适的首次适应算法对该作业序列是不合适的 在使用在使用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存主存os(a)首首次次适适应应算算法法的的空空闲闲区区队队列列 20KB 0 30KB 100KB 0 20KB 160KB 0 5KB 210KB 0 46KB 32最佳适应算法最佳适应算法 主存管理主存管理分区存储管理分区存储管理 作业A要求18KB 作业B要求25KB 作业C要求30KB 最佳适应算法对该作业序列是合适的最佳适应算法对该作业序列是合适的 在使用在使用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存主存os(a)最最佳佳适适应应算算法法的的空空闲闲区区队队列列160KB 0 5KB 100KB 0 20KB 20KB 0 30KB 210KB 0 46KB 33最坏适应算法最坏适应算法 主存管理主存管理分区存储管理分区存储管理 作业A要求18KB 作业B要求25KB 作业C要求30KB 最坏适应算法对该作业序列是不合适的最坏适应算法对该作业序列是不合适的 os在使用在使用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存主存(a)最最坏坏适适应应算算法法的的空空闲闲区区队队列列210KB 0 46KB 20KB 0 30KB 100KB 0 20KB 160KB 0 5KB 344.4.碎片问题及拼接技术碎片问题及拼接技术碎片问题及拼接技术碎片问题及拼接技术什么是碎片问题什么是碎片问题什么是碎片问题什么是碎片问题在已分配区之间存在着的一些没有被充分利用的空闲区 主存管理主存管理分区存储管理分区存储管理如何解决碎片问题？如何解决碎片问题？什么是拼接技术什么是拼接技术什么是拼接技术什么是拼接技术 所谓拼接技术是指移动存储器中某些已分配区中的信息，使本来分散的空闲区连成一个大的空闲区。20KB 54KB58KB135KB254KB256KB 1主存主存138KB作业2 0os作业3作业拼接前20KB 0 54KB131KB247KB256KB 1主存主存os作业作业2作业3拼接后351.1.页式系统的基本概念页式系统的基本概念页式系统的基本概念页式系统的基本概念页面页面页面页面 程序的地址空间被等分成 大小相等的片，称为页面，又称为虚页。主存块主存块主存块主存块主存被等分成大小相等的片，称为主存块，又称为实页。页面与主存块的关系页面与主存块的关系页面与主存块的关系页面与主存块的关系主存管理主存管理页式存储管理页式存储管理02KB4KB254KB256KB 102KB4KB6KB0页1页2页3页主存主存作业地址空间作业地址空间36页表页表页表页表什么是页表什么是页表什么是页表什么是页表 为了实现从地址空间到物理主存的映象，系统建立的 记录页与内存块之间对应关系的地址变换的机构称为 页面映像表，简称页表。页表的组成页表的组成页表的组成页表的组成高速缓冲存储器 地址变换速度快，但成本较高主存区域 地址变换速度比硬件慢，成本较低主存管理主存管理页式存储管理页式存储管理37分页映像存储的例分页映像存储的例分页映像存储的例分页映像存储的例主存管理主存管理页式存储管理页式存储管理01KB01KB2KB3KB 1主存主存作业作业2地址空间地址空间2KB3KB4KB5KB6KB7KB8KB9KB10KB 101KB2KB 1作业作业1地址空间地址空间01KB 1作业作业3地址空间地址空间0516页号页号块号块号02140827作业作业1页表页表作业作业2页表页表作业作业3页表页表osos382.2.页式地址变换页式地址变换页式地址变换页式地址变换页表页表页表页表 记录页与块之间对应关系的地址变换的机构地址变换的机构。虚地址结构虚地址结构虚地址结构虚地址结构 当CPU给出的虚地址长度为16位，页面大小为1KB时，在分页系统中地址结构的格式如下：主存管理主存管理页式存储管理页式存储管理 p w15 10 9 0页号页号P页内位移页内位移Wmov r1,250012301KB2KB3KB 1作业作业2地址空间地址空间391页式地址变换页式地址变换页式地址变换页式地址变换页式地址变换的例页式地址变换的例 作业2地址空间中，设100号单元处有如下指令：mov r1,2500。当这条指令执行时，如何进行正确的 地址变换。主存管理主存管理页式存储管理页式存储管理2500 21024 +452 p=2 w=4520000100111000100 000010 0111000100mov r1,250012301KB2KB3KB 1作业作业2地址空间地址空间40页式地址变换过程页式地址变换过程主存管理主存管理页式存储管理页式存储管理页表始址寄存器页表始址寄存器mov r1,250012301KB2KB3KB 1作业作业2地址空间地址空间+021427页表页表 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 015 10 9 0页号页号P页内位移页内位移W250001KB主存主存2KB3KB4KB5KB6KB7KB8KB9KB10KB 1ososmov r1,2500123第第1页页页号页号P页内位移页内位移W 15 10 9 00 0 0 1 1 10 1 1 1 0 0 0 1 0 071024+452=762041页式地址变换步骤页式地址变换步骤CPU给出操作数地址(为2500)；由分页机构自动地把逻辑地址分为两部分，得到页 号p和页内相对位移w(p=2，w=452)；根据页表始址寄存器指示的页表始地址，以页号为 索引，找到第2页所对应的块号(为7)；将块号b和页内位移量w拼接在一起，就形成了访问 主存的物理地址 (7*1024+452=7620)主存管理主存管理页式存储管理页式存储管理42采用联想存储器加快查表速度采用联想存储器加快查表速度采用联想存储器加快查表速度采用联想存储器加快查表速度什么是联想存储器什么是联想存储器 高速、小容量半导体存储部件，又称缓冲存储器。快表快表 在缓冲存储器中存放正在运行的进程当前用到的页号 和对应的块号，又称为快表。主存管理主存管理页式存储管理页式存储管理43利用快表进行地址映射利用快表进行地址映射 主存管理主存管理页式存储管理页式存储管理 a +P w 仅在联想映像不匹配时进行仅在联想映像不匹配时进行页号页号 b w首首先先选选择择联想存储器联想存储器所有页表在主存中所有页表在主存中物理地址物理地址pbba+pa443.3.请调页面的机制请调页面的机制请调页面的机制请调页面的机制两种页式系统两种页式系统两种页式系统两种页式系统简单页式系统简单页式系统 装入一个作业的全部页面才能投入运行。请求页式系统请求页式系统 装入一个作业的部分页面即可投入运行。(1)(1)简单页式系统需要解决什么问题？简单页式系统需要解决什么问题？简单页式系统需要解决什么问题？简单页式系统需要解决什么问题？(2)(2)请求分页系统需要解决什么问题请求分页系统需要解决什么问题请求分页系统需要解决什么问题请求分页系统需要解决什么问题?主存管理主存管理页式存储管理页式存储管理请求页式系统需解决的问题请求页式系统需解决的问题请求页式系统需解决的问题请求页式系统需解决的问题 扩充页表功能扩充页表功能扩充页表功能扩充页表功能 页号页号 主存块号主存块号 中断位中断位 辅存地址辅存地址中断位中断位I 标识该页是否在主存 若i=1，表示此页不在主存；若i=0，表示该页在主存辅存地址辅存地址 该页面在辅存的位置45缺页处理缺页处理缺页处理缺页处理 主存管理主存管理页式存储管理页式存储管理作业作业2在请求分页系统中的存储映像在请求分页系统中的存储映像01KB2KB4KB 1作业作业2地址空间地址空间mov r1,2120add r1,3410006251 006802 3KB01KB主存主存2KB3KB4KB5KB6KB7KB8KB9KB10KB 102142作业作业2页表页表osos作业2 第 1页作业2 第 0页3页号页号 辅存地址辅存地址 中断位中断位 块号块号 0011地址地址地址地址46主存管理主存管理页式存储管理页式存储管理缺页处理的例缺页处理的例 作业2的主存块数为 m2=3，讨论程序执行 “mov r1，2120”指令时的情况。CPU产生的虚地址为2120分页机构得 p=2，w=72查页表。该页中断位i=1发生缺页中断发生缺页中断！如主存中有空白块，且如主存中有空白块，且n m 则直接调入则直接调入如主存中无空白块，或如主存中无空白块，或n m，则需淘则需淘汰该作业在主存中的一页汰该作业在主存中的一页01KB2KB4KB 1作业作业2地址空间地址空间mov r1,2120add r1,3410006251 006802 3KB47主存管理主存管理页式存储管理页式存储管理缺页处理缺页处理 启动要处理的指令启动要处理的指令给出虚地址给出虚地址 得到页号得到页号该该页页在在主主存存?有空闲块有空闲块?缺页中断缺页中断执行完该指令执行完该指令 准备执行下条指令准备执行下条指令选一页淘汰选一页淘汰 从外存读入所需的页从外存读入所需的页 调整存储分配表和页表调整存储分配表和页表 重新启动被中断的指令重新启动被中断的指令 调整存储分配表和页表调整存储分配表和页表要重写入要重写入?该页写入外存该页写入外存YNNY硬件硬件软件软件YN484.4.淘汰机制与策略淘汰机制与策略淘汰机制与策略淘汰机制与策略什么是淘汰策略什么是淘汰策略什么是淘汰策略什么是淘汰策略用来选择淘汰哪一页的规则叫做置换策略，或称淘汰算法。用来选择淘汰哪一页的规则叫做置换策略，或称淘汰算法。主存管理主存管理页式存储管理页式存储管理如何决定如何决定淘汰哪一页？淘汰哪一页？扩充页表功能扩充页表功能扩充页表功能扩充页表功能 引用位引用位 标识该页最近是否被访问标识该页最近是否被访问 为“0”该页没有被访问；为“1”该页已被访问改变位改变位 表示该页是否被修改表示该页是否被修改 为“0”该页未被修改；为“1”该页已被修改 页页 号号 主存块号主存块号 中断位中断位 辅存地址辅存地址 引用位引用位 改变位改变位49颠簸颠簸 颠簸(thrashing)，又称为“抖动”。简单地说，导致系统效率急剧下降的主存和辅存之间的 频繁页面置换现像称为“抖动”。主存管理主存管理页式存储管理页式存储管理缺页中断率缺页中断率假定程序p共有n页，系统分配m块，有 1mn；若程序p在运行中：成功的访问次数为s，不成功的访 问次数为f；缺页中断率：缺页中断率：f=f/(s+f)f=f(r，m，p)；r：置换算法；p：程序特征；m：系统分配的块数50主存管理主存管理页式存储管理页式存储管理最佳算法最佳算法(OPT算法算法)当要调入一新页而必须先淘汰一旧页时，所淘汰的那一页应是以 后不再要用的，或者是在最长的时间以后才会用到的那页。先进先出淘汰算法先进先出淘汰算法(FIFO算法算法)什么是先进先出淘汰算法什么是先进先出淘汰算法 总是选择在主存中居留时间最长(即最早进入主存)的一页淘汰。先进先出淘汰算法的实现先进先出淘汰算法的实现建立一个页面进入主存的先后次序表；建立一个替换指针，指向最早进入主存的页面；当需要置换一页时，选择替换指向的那一页，然后调整替换指 针的内容。51主存管理主存管理页式存储管理页式存储管理页号表页号表 页面进入主存的先后次序：2451 替换指针替换指针 指向最老的一页指向最老的一页页号页号 2 4 5 16 当要调入第当要调入第6页时：页时：置换第2页将第2页改为6替换指针指向第4页 52主存管理主存管理页式存储管理页式存储管理在存储分块表中建立次序表在存储分块表中建立次序表 页面进入主存的先后次序：4512 当要调入第6页时：如何处理?512 67102345642516 74 2替换指针替换指针块号块号 页号页号 指针指针710234566251 274 6替换指针替换指针 块号块号 页号页号 指针指针53主存管理主存管理页式存储管理页式存储管理最久未使用淘汰算法最久未使用淘汰算法(LRU算法算法)什么是最久未使用淘汰算法什么是最久未使用淘汰算法 总是选择最长时间未被使用的那一页淘汰。最久未使用淘汰算法的实现最久未使用淘汰算法的实现用引用位考察页面的使用情况；当访问页面时，将引用位置1，并记时；当要淘汰一页时，选择时间最长的一页淘汰。要精确实现很困难要精确实现很困难硬件方法：采用计数器硬件方法：采用计数器软件方法：采用页号栈软件方法：采用页号栈54主存管理主存管理页式存储管理页式存储管理软件方法：采用页号栈软件方法：采用页号栈 页面访问轨迹：451 2 5 64512访问第访问第5页页 访问第访问第6页页 淘汰第淘汰第4页页 41251256访问4、5、1、2页后栈的内容 访问第5页后，调整栈的内容 访问第6页后，栈的内容 55主存管理主存管理页式存储管理页式存储管理LRU近似淘汰算法近似淘汰算法 入口入口读出替换指针指向的块号读出替换指针指向的块号移动指针指向下一个存储块移动指针指向下一个存储块 引用位为引用位为0?选择该页淘汰，记录该页的页号选择该页淘汰，记录该页的页号、块号、块号将该页所在的将该页所在的块号送到块号送到替换指针替换指针返回返回置引用位为置引用位为0YN56主存管理主存管理页式存储管理页式存储管理LRULRU近似淘汰算法举例近似淘汰算法举例近似淘汰算法举例近似淘汰算法举例7102345642514172 4替换指针替换指针 块号块号 页号页号 引用位引用位 指针指针60017102345642564072 7替换指针替换指针 块号块号 页号页号 引用位引用位 指针指针6011当要调入第当要调入第6页时，如何处理页时，如何处理?571.1.段式地址空间段式地址空间段式地址空间段式地址空间什么是段什么是段什么是段什么是段 分段是程序中自然划分的一组逻辑意义完整的信息集合。分段的例：代码分段、数据分段、栈段页。作业地址空间作业地址空间作业地址空间作业地址空间 由若干个逻辑分段组成，每个分段有自己的名字，对于一个分段而 言，它是一个连续的地址区。主存管理主存管理段页式存储管理段页式存储管理code_addr4KB 10代码分段代码分段data_addr3KB 10数据分段数据分段stack_addr2KB 10栈段栈段58段式地址结构段式地址结构段式地址结构段式地址结构 主存管理主存管理段页式存储管理段页式存储管理 段段 号号 s 段段 内内 位位 移移 w2.2.段式地址变换段式地址变换段式地址变换段式地址变换 L B s w B+w第S段段号 段内位移段号 长度 基址段式地址步骤段式地址步骤段式地址步骤段式地址步骤取出程序地址(s，w)；用s检索段表；如w0或wL则主存越界；(Bw)即为所需主存地址593.3.页式系统与段式系统的区别页式系统与段式系统的区别页式系统与段式系统的区别页式系统与段式系统的区别用户地址空间的区别用户地址空间的区别用户地址空间的区别用户地址空间的区别页式系统中用户地址空间页式系统中用户地址空间一维地址空间一维地址空间段式系统中用户地址空间段式系统中用户地址空间二维地址空间二维地址空间 分段和页面的区别分段和页面的区别分段和页面的区别分段和页面的区别 分段分段 页面页面 信息的逻辑划分信息的逻辑划分 信息的物理划分信息的物理划分 段长是可变的段长是可变的 页的大小是固定的页的大小是固定的 用户可见用户可见 用户不可见用户不可见 w字段的溢出字段的溢出 w字段的溢出字段的溢出自自动动 将产生越界中断将产生越界中断 加入到页号中加入到页号中 主存管理主存管理段页式存储管理段页式存储管理604.4.段页式系统段页式系统段页式系统段页式系统 在段式存储管理中结合分页存储管理技术，在一个分段内在段式存储管理中结合分页存储管理技术，在一个分段内 划分页面，就形成了段页式存储管理。划分页面，就形成了段页式存储管理。段页式地址结构的用户地址空间段页式地址结构的用户地址空间段页式地址结构的用户地址空间段页式地址结构的用户地址空间主存管理主存管理段页式存储管理段页式存储管理code_addr4KB 10代码分段代码分段data_addr3KB 10数据分段数据分段stack_addr2KB 10栈段栈段61主存管理主存管理段页式存储管理段页式存储管理段页式系统中段表、页表与主存的关系段页式系统中段表、页表与主存的关系段页式系统中段表、页表与主存的关系段页式系统中段表、页表与主存的关系01n段号段号 页表长度页表长度 页表始址页表始址 23页号页号1块号块号其他其他0段页表段页表主存主存段表段表 01块号块号其他其他1段页表段页表2页号页号0621.Linux1.Linux系统段页式地址变换系统段页式地址变换系统段页式地址变换系统段页式地址变换LinuxLinux系统的分段系统的分段系统的分段系统的分段Linux系统处在用户态时，使用用户代码段和用户数据 段来对指令和数据寻址在核态时，使用内核代码段和内核数据段来对指令和 数据寻址每个分段是一个连续的线性地址空间，从0开始直到 2321的寻址长度。主存管理主存管理LinuxLinux系统存储管理系统存储管理6380 x8680 x86分页结构分页结构分页结构分页结构 80 x86微处理器的分页单元处理4KB的页。一个32位的 线性地址分为3个域。主存管理主存管理LinuxLinux系统存储管理系统存储管理 页目录页目录 页表页表 页内位移页内位移31 22 21 12 11 0页目录页目录字段指向页目录项；页表页表字段指向进程的一个页表项；页内位移页内位移则是页内偏移量 64主存管理主存管理LinuxLinux系统存储管理系统存储管理三级页表三级页表三级页表三级页表 第一级：全局目录第一级：全局目录(PGD)PGD中的表项指向页目录中的一个表项二级页表：页目录二级页表：页目录(PMD)PMD中的表项指向页表PTE中的一个表项三级：页表三级：页表 该表项指向物理页(页框)的主存地址 65主存管理主存管理LinuxLinux系统存储管理系统存储管理线性地址转换为物理地址线性地址转换为物理地址线性地址转换为物理地址线性地址转换为物理地址地址转换过程地址转换过程 Linux系统通过三级页表完成线性地址到物理地址的转换页目录页目录 页表页表 页内位移页内位移31 22 21 12 11 0cr3+：+：页目录表页目录表页表页表物理页物理页+66主存管理主存管理LinuxLinux系统存储管理系统存储管理地址变换步骤地址变换步骤 由cr3指示的当前页目录的物理地址与分页结构中的 页目录字段的内容相加指向页目录表项；由页目录表项内容得到当前使用的页表的始地址，通过分页结构中的页表字段的内容找到该页表项；由页表项指示的该页的物理页(页框)的主存地址与 分页结构中的页内位移相加，得到最终的物理地址。672.Linux2.Linux系统动态内核管理系统动态内核管理系统动态内核管理系统动态内核管理物理页的描述物理页的描述物理页的描述物理页的描述Linux系统主存分配的基本单位是物理页系统主存分配的基本单位是物理页(又称为页框又称为页框)主存管理单元主存管理单元MMU以页为单位进行分配和处理以页为单位进行分配和处理 32位体系结构支持位体系结构支持4KB的页，的页，64位体系结构支持位体系结构支持8KB的页的页内核用内核用struct page结构描述页框结构描述页框 struct page flags;/*页的状态页的状态*/_count;/*该页被引用的次