第五章 存 储 管 理 五章存储管理Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望第五章 存 储 管 理 5.1 存储管理的功能存储管理的功能存储器的扩充存储器的扩充地址变换和重定位地址变换和重定位存储空间分配存储空间分配存储保护存储保护5.1.1 虚拟存储器：虚拟存储器：利用利用OS的手段来实现存储器扩充的一种技术。不考虑物理存储器的大小的手段来实现存储器扩充的一种技术。不考虑物理存储器的大小和信息存放的实际位置，只规定每个进程中互相关联的信息的相对位置。和信息存放的实际位置，只规定每个进程中互相关联的信息的相对位置。每个进程都有自己的虚拟存储器，且虚拟的容量受计算机的地址结构和寻每个进程都有自己的虚拟存储器，且虚拟的容量受计算机的地址结构和寻址方式的影响。址方式的影响。第五章 存 储 管 理 虚地址空间和实地址空间虚地址空间和实地址空间程序访问的地址是虚地址，它可以访问的虚地址范围叫做程序的虚地址空间。程序访问的地址是虚地址，它可以访问的虚地址范围叫做程序的虚地址空间。在指定的计算机系统中，可使用的实地址范围叫做计算机的实地址空间。在指定的计算机系统中，可使用的实地址范围叫做计算机的实地址空间。实现虚拟存储技术注意的问题实现虚拟存储技术注意的问题需要有相当容量的辅存以便足以存放多个用户作业的地址空间需要有相当容量的辅存以便足以存放多个用户作业的地址空间要有一定容量的主存要有一定容量的主存地址变换机构存储保护地址变换机构存储保护源程序编译编译链接链接虚拟空间地址变换地址变换物理存储器地址变换和物理存储器地址变换和物理存储器第五章 存 储 管 理 5.1.2 地址变换和重定位地址变换和重定位1. 地址映射地址映射为保证程序正常运行为保证程序正常运行,必须将逻辑地址正确地转换为物理地址必须将逻辑地址正确地转换为物理地址,这种地址这种地址转换机构称为地址映射转换机构称为地址映射. 地址映射方式地址映射方式就是建立虚地址到实地址之间的对应关系就是建立虚地址到实地址之间的对应关系,也就是实现虚地址到实地址也就是实现虚地址到实地址的一个对应的一个对应.jump 1400load 2200100014002200jump 1400load 2200绝对地址绝对地址jump 1400load 220004001200jump 400load 1200相对地址相对地址绝对装入绝对装入第五章 存 储 管 理 引入相对地址的好处引入相对地址的好处:可以让OS进行分配空间减少了内存对于用户编写程序的制约2. 静态地址映射静态地址映射在作业装入过程中进行地址变换的方式称为静态重定位或静态地址映射在作业装入过程中进行地址变换的方式称为静态重定位或静态地址映射load 25003500100025005500load 12500350011000125001550010000作业装入内存的情况作业装入内存的情况第五章 存 储 管 理 优点优点: 不需要硬件支持不需要硬件支持缺点缺点:无法实现虚拟存储器无法实现虚拟存储器必须占用连续的内存空间必须占用连续的内存空间;难以做到程序和数据的共享难以做到程序和数据的共享3. 动态重定位动态重定位是在程序执行期间，随着每条指令和数据访问时，自动地进行地址转换。把相对地址与程序是在程序执行期间，随着每条指令和数据访问时，自动地进行地址转换。把相对地址与程序在内存中的起始地址相加得到正确的物理地址。在内存中的起始地址相加得到正确的物理地址。LOAD 1 4005432101004005500.一段程序所在的虚地址空间一段程序所在的虚地址空间400VR+1000BRLOAD 1 40054321100011001400.重定位寄存器重定位寄存器虚拟空间虚拟空间内存空间内存空间动态地址重定位动态地址重定位第五章 存 储 管 理 动态地址重定位的实现过程动态地址重定位的实现过程:设置基地址寄存器设置基地址寄存器BR,虚地址寄存器虚地址寄存器VR将程序装入内存将程序装入内存,且将其占用的内存区首地址且将其占用的内存区首地址BR中中.在程序执行过程中在程序执行过程中,将要访问的虚地址送入将要访问的虚地址送入VR中中.地址变换机构把地址变换机构把VR和和BR的内容相加的内容相加,得到实际的物理地址得到实际的物理地址.动态地址重定位的优点动态地址重定位的优点:可以不连续地分配内存空间可以不连续地分配内存空间.提供了实现虚拟存储的基础提供了实现虚拟存储的基础,实现了虚拟存储最基本的一个保障实现了虚拟存储最基本的一个保障,为今后的程序分段提供了有利的基础为今后的程序分段提供了有利的基础.有利于程序段的共享有利于程序段的共享.第五章 存 储 管 理 5.1.3 内存的分配和回收内存的分配和回收存储管理器的分配策略有以下三种存储管理器的分配策略有以下三种:(1) 放置策略放置策略:决定主存中放置信息的区域决定主存中放置信息的区域,这是确定为进程选择一个空闲区这是确定为进程选择一个空闲区 或若干空闲区的原则或若干空闲区的原则.(2) 调入策略调入策略:决定信息装入内存的时机决定信息装入内存的时机,是在需要时调入主存是在需要时调入主存.(3) 交换策略交换策略:在主存中没有任何可用的空闲区时在主存中没有任何可用的空闲区时,决定淘汰哪些信息决定淘汰哪些信息,以便把需要的以便把需要的 信息装入内存信息装入内存.对主存区域进行分配时对主存区域进行分配时,一般有一般有2种不同的主存区域划分方式种不同的主存区域划分方式:1将主存划分成大小不等的区域2将主存等分成一系列大小相等的块.此两种模式决定了内存分配时所采取的措施或情况此两种模式决定了内存分配时所采取的措施或情况第五章 存 储 管 理 5.1.4 存储保护与信息共享存储保护与信息共享现代现代OS采用多道程序技术采用多道程序技术,在内存当中可以驻留多个程序在内存当中可以驻留多个程序,为了防止被此破坏为了防止被此破坏或窃取内存信息或窃取内存信息,必须由硬件必须由硬件(软件配合软件配合)保证每道程序只能在给定的存储区域保证每道程序只能在给定的存储区域内活动内活动,这种措施叫这种措施叫存储保护存储保护.常用的存储保护手段常用的存储保护手段:(1) 上下界地址寄存器上下界地址寄存器10KB20KB上界寄存器上界寄存器UR下界寄存器下界寄存器LR(a) 上下界寄存器上下界寄存器10KB10KB基地址寄存器基地址寄存器长度寄存器长度寄存器10KB20KB10KB20KB(b) 基址、限长寄存器基址、限长寄存器第五章 存 储 管 理 (2) 存储保护键存储保护键为每一个存储块提供一个单独的保护键为每一个存储块提供一个单独的保护键.在程序状态字在程序状态字(PSW)在设置相应的在设置相应的保护键开关字段保护键开关字段.对不同的进程赋予不同的开关代码对不同的进程赋予不同的开关代码,以和被保护的存储块中以和被保护的存储块中的保护键匹配的保护键匹配.每当每当CPU访问主存时访问主存时,都将存储块的保护键和都将存储块的保护键和PSW中的开关中的开关字段进行匹配字段进行匹配,相同时允许访问相同时允许访问,不相同时不能方法不相同时不能方法.例例:A块B块C块110010010100100.1100.PSW保护位保护位1:要求保护要求保护0:不要求保护不要求保护第五章 存 储 管 理 5.2 分区存储管理分区存储管理单一连续分配：所谓单一单一连续分配：所谓单一,是指内存中只驻留一道作业是指内存中只驻留一道作业.为便于地址转换为便于地址转换,把作业连把作业连 续地存放在内存中续地存放在内存中,而不是离散地存放而不是离散地存放.主要用在早期的单道批处理系统中主要用在早期的单道批处理系统中,采用静态分配的方式采用静态分配的方式.优点优点:方法简单方法简单,易于实现易于实现.缺点缺点: 仅适用于单道程序仅适用于单道程序,不能处理多道不能处理多道.第五章 存 储 管 理 1. 固定分区法固定分区法分区管理的基本思想就是给每一个内存中的进程划分一块存储区分区管理的基本思想就是给每一个内存中的进程划分一块存储区,用以连续存放用以连续存放各进程的程序和数据各进程的程序和数据,使各进程并发执行使各进程并发执行.【主要特征：】【主要特征：】 内存中分区的个数是固定的，分区的大小也是固定的。内存中分区的个数是固定的，分区的大小也是固定的。【缺点【缺点:】一个作业和另一个作业之间总是存在着碎片。一个作业和另一个作业之间总是存在着碎片。区号分区长度起始地址进程号18k20k1230232k28k1831364k60k2064132k124k未分配分区说明表分区说明表OS进程进程A（6K)B(16K)进程进程B (25K)进程进程C(36K)内存内存第第1分区分区第第2分区分区第第3分区分区第第4分区分区第五章 存 储 管 理 3.4 动态分区法动态分区法是在作业装入到内存时，按照作业的大小去划分分区，使分区的大小正好适应作业的需要是在作业装入到内存时，按照作业的大小去划分分区，使分区的大小正好适应作业的需要A(1K)B(5K)C(9K)D(120K)OSAOSAOSAOSABBBBCCD【内存分配情况：】【内存分配情况：】第五章 存 储 管 理 区号分区长度起始地址进程号120k30k1230223k56k1831316k110k206412k200k1123分区表分区表序号可用空间长度可用空间起始地址15k50k230k80k373k127k可用空间表可用空间表第五章 存 储 管 理 动态分区表的数据结构动态分区表的数据结构40K16K78K100K24K9K序号可用空间长度可用空间起始地址11640k224k78k39k100k(a) 可用空间表可用空间表作业（进程号）作业（进程号）请求长度请求长度P113KP220K.(b) 请求表请求表(c) 自由链自由链第五章 存 储 管 理 分分区区的的分分配配与与回回收收要求Xk大小分区取分区说明表第一项表结束吗？无法分配是否该区空闲？是分区长度Xk状态位置为“正在使用否否取下一表项返回分区号固定分区分配算法固定分区分配算法第五章 存 储 管 理 动态分区时的分配与回收动态分区时的分配与回收对于请求表中的要求内存长度，分配程序从可用表或自由链中找出合适的空闲区分配给程序分配空闲区后，更新可用表或自由链进程释放内存资源时，和相邻的空闲区进行链接合并，更新可用表或自由链。第五章 存 储 管 理 某一时刻：某一时刻：C执行完毕并释放内存，进程执行完毕并释放内存，进程E(50K),进程进程F(16K)需要内存空间需要内存空间OSA（8K)B(16K)C完成完成(64K)空闲区空闲区D（124K)24K空闲区空闲区内存内存0256进程进程E（50K)进程进程F（16K)进入内存进入内存OSA（8K)B(16K)E (50K)D（124K)F(16K)内存内存025614K空闲区8K空闲区OSA（8K)B(16K)E (50K)F(16K)内存内存025612414138K空闲区8K空闲区进程进程B（16K)进程进程D（124K)完成完成16K空闲区第五章 存 储 管 理 例：例：ABC空闲区B完成完成AC空闲区空闲区D进入进入AC空闲区DE进入进入A完成完成EC空闲区D说明：动态分区管理模式可以把系统中一片连续的可用空间切割成多个不连续的可用空间第五章 存 储 管 理 常见的适应算法：常见的适应算法：1、最佳适应算法：、最佳适应算法：找到满足条件最小的那个内存空间。找到满足条件最小的那个内存空间。 优点：优点：平均而言，只要查找一半的表格便能找到最佳适应的空闲区平均而言，只要查找一半的表格便能找到最佳适应的空闲区如果有一个空闲区的容量正好满足要求，则它必被选中。如果有一个空闲区的容量正好满足要求，则它必被选中。如果不存在正好满足需要的空闲区，则选中一个容量接近的空闲区。如果不存在正好满足需要的空闲区，则选中一个容量接近的空闲区。缺点：缺点：剩下比较小的碎片剩下比较小的碎片要求：按空闲区大小从小到大的次序组成空闲区可用表或自由链。要求：按空闲区大小从小到大的次序组成空闲区可用表或自由链。 在进行内存分配时，首先从空闲区表（空闲分区链）首开始查找，直到在进行内存分配时，首先从空闲区表（空闲分区链）首开始查找，直到 找到第找到第1个能满足大小要求的空闲分区为止。个能满足大小要求的空闲分区为止。第五章 存 储 管 理 优点：优点：只要比较第一项就能判定能否满足要求，如满足，则立即分配。只要比较第一项就能判定能否满足要求，如满足，则立即分配。分配后剩下的空闲区可能较大，可供以后使用。分配后剩下的空闲区可能较大，可供以后使用。缺点：缺点： 由于最大空闲区总是首先被分配，当有大作业来时，其存储空间的申请往往得由于最大空闲区总是首先被分配，当有大作业来时，其存储空间的申请往往得不到满足。不到满足。3、最先适应算法：、最先适应算法：找到第找到第1个满足要求的空间进行分配。个满足要求的空间进行分配。要求：需求可用表或自由链按起始地址递增的次序排列要求：需求可用表或自由链按起始地址递增的次序排列 在进行内存分配时，找到第在进行内存分配时，找到第1个满足作业大小要求的空闲区为止。个满足作业大小要求的空闲区为止。优点：优点：释放内存时，如果有相邻的空闲区就进行合并，使其成为一个较大的释放内存时，如果有相邻的空闲区就进行合并，使其成为一个较大的空闲区。空闲区。优先利用内存低地址部分的空闲区，从而保留了高地址部分的大空闲优先利用内存低地址部分的空闲区，从而保留了高地址部分的大空闲区。区。缺点：缺点： 增加了查找可用空闲区的开销增加了查找可用空闲区的开销2、最差适应算法：、最差适应算法：比较可用空间，找到满足条件的最大那个内存空间进行分配。比较可用空间，找到满足条件的最大那个内存空间进行分配。 要求：按空闲区大小递减的顺序组成空闲区可用表或自由链。要求：按空闲区大小递减的顺序组成空闲区可用表或自由链。 在进行内存分配时，首先检查空闲区的第在进行内存分配时，首先检查空闲区的第1个分区，如果第个分区，如果第1个空闲分区个空闲分区 大小小于所要求的大小，则分配失败。大小小于所要求的大小，则分配失败。第五章 存 储 管 理 4、循环最先适应算法：、循环最先适应算法：要求：在进行内存分配时，不再每次从链首查找。而是从上次找到的空闲区的要求：在进行内存分配时，不再每次从链首查找。而是从上次找到的空闲区的 下一个空闲区开始查找，直到找到第下一个空闲区开始查找，直到找到第1个满足条件的空闲区。个满足条件的空闲区。优点：优点： 存储空间的利用更加均衡。存储空间的利用更加均衡。缺点：缺点： 导致缺乏大的空闲区。导致缺乏大的空闲区。第五章 存 储 管 理 例：例：下表给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。下表给出了某系统中的空闲分区表，系统采用可变式分区存储管理策略。现有以下作业序列：现有以下作业序列：96K,20K,200K。若用最先适应算法和最佳适应算法。若用最先适应算法和最佳适应算法来处理这些作业序列，哪种算法可以满足该作业序列的请求，为什么？来处理这些作业序列，哪种算法可以满足该作业序列的请求，为什么？分区号大小起始地址132K100K210K150K35K200K4218K220K596K530K空闲分区表空闲分区表第五章 存 储 管 理 1、采用最佳适应算法、采用最佳适应算法申请96K，选中的是5号分区，大小一样，从空闲表中删除5号分区申请20K时，选中1号分区，分配后还剩下12K.最后申请200K时，选中4号分区，分配后还剩下18K.分区号大小起始地址112K100K210K150K35K200K418K220K分配后的空闲分区表分配后的空闲分区表第五章 存 储 管 理 2、采用最先适应算法、采用最先适应算法申请96K，选中的是4号分区，剩余122K.申请20K时，选中1号分区，分配后还剩下12K.最后申请200K时，现有的5个分区都不能满足要求。分区号大小起始地址112K100K210K150K35K200K4122K220K596K530K分配后的空闲分区表分配后的空闲分区表第五章 存 储 管 理 例：例：在某系统中，采用固定分区分配管理方式，内存分区情况如下表所示。在某系统中，采用固定分区分配管理方式，内存分区情况如下表所示。现有大小为现有大小为1K,9K,33K,121K的多个作业要求进入内存。的多个作业要求进入内存。要求：画出它们进入内存后的空间分配情况，并说明主存浪费情况。要求：画出它们进入内存后的空间分配情况，并说明主存浪费情况。020K28K60K180K512K-1OS第第1分区分区第第2分区分区第第3分区分区第第4分区分区01K的作业的作业28K60K180K512K-1OS20K9K的作业的作业33K的作业的作业121K的作业的作业第第1分区分区第第2分区分区第第3分区分区第第4分区分区第五章 存 储 管 理 例：例：ABC碎片碎片解决此问题的策略：解决此问题的策略： 程序浮动：程序在内存中的移动。程序浮动：程序在内存中的移动。 多重分区：一个作业可以占据几个不连续的分区多重分区：一个作业可以占据几个不连续的分区D程序浮动的时机：程序浮动的时机： 只要出现碎片就进行程序浮动。只要出现碎片就进行程序浮动。 仅当一个作业到来，任何一个可用空间都不满足，但它们的和能仅当一个作业到来，任何一个可用空间都不满足，但它们的和能 够满足要求时进行程序的浮动。够满足要求时进行程序的浮动。ABC第五章 存 储 管 理 多重分区：一个作业可以占据几个不连续的分区。多重分区：一个作业可以占据几个不连续的分区。ABC碎片碎片作业作业第五章 存 储 管 理 进程进程A(8K)进程进程B(16K)进程进程C(64K)进程进程D（124K)OSAOSAOSAOSABBBBCCD【内存分配情况：】【内存分配情况：】第五章 存 储 管 理 存储空间的扩充：存储空间的扩充： 覆盖技术：指一个作业和其他作业，或者一个作业的若干个程序段共享内存的技术。覆盖技术：指一个作业和其他作业，或者一个作业的若干个程序段共享内存的技术。 要解决的问题：在小的存储空间中运行大作业的问题。要解决的问题：在小的存储空间中运行大作业的问题。 覆盖技术的实现方法：覆盖技术的实现方法： 将一个大的程序划分成功能独立的若干子程序，将执行时并不要求同时装入主将一个大的程序划分成功能独立的若干子程序，将执行时并不要求同时装入主 存的子程序分成一组，每一组分配到同一个存储区域。存的子程序分成一组，每一组分配到同一个存储区域。第五章 存 储 管 理 例：例：程序大小程序大小24K内存空间内存空间13K主程序A(子程序)B(子程序）CDEGFH3K1K4K4K4K4K3K3K2K主程序主程序A(B)4KC(D、E、F、G)4KH3K内存空间的分配情况内存空间的分配情况缺点：缺点：程序员必须完成把一个程序划分成不同的程序段，并规定它们的程序员必须完成把一个程序划分成不同的程序段，并规定它们的执行和覆盖顺序的工作。执行和覆盖顺序的工作。第五章 存 储 管 理 交换技术交换技术（对于交互式的作业而言）（对于交互式的作业而言） ： 将暂时不需要的部分移到辅存，让出主存以调入需要的部分，交换到辅存的可以再将暂时不需要的部分移到辅存，让出主存以调入需要的部分，交换到辅存的可以再 度被调入。度被调入。RUNREADY(A)READY(B)内存内存头头尾尾就绪队列就绪队列时间片到（换出）时间片到（换出） 调度调度（换入）（换入）第五章 存 储 管 理 5.5 页式管理页式管理1.页式管理的基本原理2.虚拟存储管理3.堆栈型替换算法4.抖动与程序局部性第五章 存 储 管 理 等分主存：把主存划分成相同大小的存储块，这个存储块称为页架。等分主存：把主存划分成相同大小的存储块，这个存储块称为页架。对于一个特定的计算机系统而言，页架大小通常是固定不变的。并给对于一个特定的计算机系统而言，页架大小通常是固定不变的。并给各页架从零开始依次编以连续的页架号为各页架从零开始依次编以连续的页架号为0、1、2、3.用户逻辑地址空间的分页：把用户的逻辑地址空间（虚地址空间）划用户逻辑地址空间的分页：把用户的逻辑地址空间（虚地址空间）划分成若干个与页架大小相同的部分，每部分称为页。并给各页从零开分成若干个与页架大小相同的部分，每部分称为页。并给各页从零开始依次编以连续的页号始依次编以连续的页号0、1、2、3逻辑地址的表示：用户的逻辑地址一般是从基地址逻辑地址的表示：用户的逻辑地址一般是从基地址”0“开始连续编开始连续编号，即是相对地址。在分页系统中，每个虚拟地址（相对地址）用一号，即是相对地址。在分页系统中，每个虚拟地址（相对地址）用一个数对（个数对（P,D)来表示。来表示。主存分配原则：分页情况下，系统以页架为单位把主存分给作业或进主存分配原则：分页情况下，系统以页架为单位把主存分给作业或进程，并且给一个作业的各页架不一定是相邻或连续的。程，并且给一个作业的各页架不一定是相邻或连续的。页表与页表地址寄存器：由于一个作业的各页并不全在主存中，只是页表与页表地址寄存器：由于一个作业的各页并不全在主存中，只是将最近需要的几页放在主存中，同时这几项又不可能分散地装入各页将最近需要的几页放在主存中，同时这几项又不可能分散地装入各页架。架。页面尺寸应是页面尺寸应是2的幂。的幂。 5.5.1 页式管理的基本原理页式管理的基本原理第五章 存 储 管 理 分页存储管理的地址结构分页存储管理的地址结构页内地址页内地址D页号页号P0111231页号页号P和页内地址和页内地址D按下式求得按下式求得:P= INT W/LD= W MOD L其中其中:INT是整除函数是整除函数,MOD是取余函数是取余函数,L为页面大小为页面大小例：例：系统的页面大小为系统的页面大小为1KB,设设W=2230,求求P和和D.P=2230/1024=2;D=2230 MOD 1024=182;1、 页面和页架页面和页架分页存储管理就是要实现逻辑地址空间到物理地址空间的一种变换分页存储管理就是要实现逻辑地址空间到物理地址空间的一种变换其中其中:W,L分分别表示表示逻辑地址空地址空间和和页面大小。面大小。第五章 存 储 管 理 2、 地址转换机构地址转换机构页地址映象表页地址映象表(页表页表):记录了一个作业的各个页面所对应的页架记录了一个作业的各个页面所对应的页架.地址转换过程：地址转换过程：当进程要访问某个逻辑地址中的数据时，分页地址变换机构自动将当进程要访问某个逻辑地址中的数据时，分页地址变换机构自动将逻辑地址分为页号和页内位移两部分逻辑地址分为页号和页内位移两部分以页号为索引检索页表，检索之前，将页号与页表长度进行比较，以页号为索引检索页表，检索之前，将页号与页表长度进行比较，如果页号超过页表长度，产生越界中断，否则访问合法。如果页号超过页表长度，产生越界中断，否则访问合法。将页表起始地址和页号计算出相应页表项的位置，得到该页的物理将页表起始地址和页号计算出相应页表项的位置，得到该页的物理块号。块号。将块号与逻辑地址中的页为位移拼接一起，形成主存的物理地址。将块号与逻辑地址中的页为位移拼接一起，形成主存的物理地址。第五章 存 储 管 理 例：例：设页面大小为设页面大小为1K,则逻辑地址为（则逻辑地址为（页表始地址页表长度页表寄存器页表寄存器2452逻辑地址逻辑地址021328页号页号块号块号8452物理地址物理地址越界中断越界中断250021024452） 的页号为的页号为2，页内地址为，页内地址为452。由页表可知第由页表可知第2页对应的物理块号为页对应的物理块号为8，则物理地址为（，则物理地址为（81024452）8644第五章 存 储 管 理 作业作业1010002000作业作业2作业作业3作业作业4010002000300001000010010410001120200024103000页号页号状态状态页架页架OS0200030003100310440005000.6000700080009000912010000ADD 1,2410LOAD 1,1120006802LOAD 1,1120ADD 1,24100068020062510y51y60y21y42y70y31y92n-3n-0y8第五章 存 储 管 理 例：例：一个一个3页长的进行具有进程号为页长的进行具有进程号为0、1、2，对应的页架号，对应的页架号4、5、9，页面长度为，页面长度为1KB,指令为指令为LOAD 1,2480的虚地址为的虚地址为200。页表始地址页表长度页表寄存器页表寄存器2432逻辑地址逻辑地址041529页号页号页架号页架号9432物理地址物理地址越界中断越界中断4296LOAD 2,24809648DATA地址转换具体过程地址转换具体过程第五章 存 储 管 理 3、 联想存储器联想存储器为了加快查页表速度，在地址变换机构中加入一组高速寄存器（为了加快查页表速度，在地址变换机构中加入一组高速寄存器（8个或个或16个）个）这些寄存器连同管理它们的硬件构成了一个容量较小的存储器，称之为高速这些寄存器连同管理它们的硬件构成了一个容量较小的存储器，称之为高速联想存储器，也称块表。联想存储器，也称块表。页表始地址页表长度页表寄存器页表寄存器页号页内地址逻辑地址逻辑地址041529页号页号页架号页架号物理地址物理地址越界中断越界中断地址转换具体过程地址转换具体过程0块表块表第五章 存 储 管 理 4、 页面尺寸大小的确定页面尺寸大小的确定为了加快查页表速度，在地址变换机构中加入一组高速寄存器（为了加快查页表速度，在地址变换机构中加入一组高速寄存器（8个或个或16个）个）这些寄存器连同管理它们的硬件构成了一个容量较小的存储器，称之为高速这些寄存器连同管理它们的硬件构成了一个容量较小的存储器，称之为高速联想存储器，也称块表。联想存储器，也称块表。例：例：设内存为设内存为M,作业平均尺寸为作业平均尺寸为J,一个页表项占一个页表项占1个单位个单位问：最佳页面尺寸问：最佳页面尺寸P=?第五章 存 储 管 理 例：例：设有一页式存储管理系统，向用户提供的逻辑地址空间最大为设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页页，每页2048字节。内存总共有字节。内存总共有8个存储块。个存储块。问：逻辑地址至少应为多少位？内存空间有多大？问：逻辑地址至少应为多少位？内存空间有多大？例：例：设有一页式存储管理系统，某作业设有一页式存储管理系统，某作业J的逻辑地址空间为的逻辑地址空间为4页（每页页（每页2048字节），字节），且已知该作业的页表如下：且已知该作业的页表如下：求出有效逻辑地址求出有效逻辑地址4865所对应的物理地址。所对应的物理地址。02142638页号页号页架号页架号第五章 存 储 管 理 5.5.2 虚拟存储管理虚拟存储管理1、虚拟存储管理应该解决的问题：、虚拟存储管理应该解决的问题：把哪部分装入内存把哪部分装入内存何时把页面装入何时把页面装入装入内存什么位置装入内存什么位置当内存没有空间时淘汰哪些页面当内存没有空间时淘汰哪些页面2、实现的策略、实现的策略： 拿来拿来策略：策略：就是程序执行过程当中，发现内存当中缺哪页就调入那页。就是程序执行过程当中，发现内存当中缺哪页就调入那页。 页面装入时机策略页面装入时机策略：预调页策略何请求调页策略预调页策略何请求调页策略 放置策略：放置策略： 哪有地方，就放在那。哪有地方，就放在那。第五章 存 储 管 理 3、对于页面的处理需要考虑的问题、对于页面的处理需要考虑的问题 每个虚页号不仅对应一个页架号，还增设一个该页是否在主存的中断位何该页在外存每个虚页号不仅对应一个页架号，还增设一个该页是否在主存的中断位何该页在外存 中的副本起始地址。中的副本起始地址。当内存中设有可以利用的页架时，根据一定的策略从内存中选择一个页面，当内存中设有可以利用的页架时，根据一定的策略从内存中选择一个页面，把它置换到外存，称为页面置换算法。把它置换到外存，称为页面置换算法。4、页面置换策略：、页面置换策略： 在页表当中适当的加入在页表当中适当的加入“是否被修改是否被修改”和和“访问频率访问频率”标志位。标志位。 先进先出算法（先进先出算法（FIFO):总是淘汰那些驻留在内存当中时机最长的页面。总是淘汰那些驻留在内存当中时机最长的页面。 最近最久未用置换最近最久未用置换算法（算法（LRU):当需要置换一页时，选择在最近一段时机当需要置换一页时，选择在最近一段时机 最久未适应的页面予以淘汰。最久未适应的页面予以淘汰。第五章 存 储 管 理 最近没有使用页面淘汰最近没有使用页面淘汰算法（算法（NRU):需要在页表中设一需要在页表中设一“引用位引用位”，当页面被访问时，当页面被访问时， 该位由硬件自动置位该位由硬件自动置位“1”。 最佳淘汰算最佳淘汰算法（法（OPT):淘汰今后将永远也不使用的页面，或者是长时机不使用的页面。淘汰今后将永远也不使用的页面，或者是长时机不使用的页面。例：例：在一个请求分页系统中，假定系统分给一个作业的物理块为在一个请求分页系统中，假定系统分给一个作业的物理块为3，并且此作业的页面走向，并且此作业的页面走向为为2，3，2，1，5，2，4，5，3，2，5，2。用用FIFO,LRU,OPT页面置换算法计算缺页次数。页面置换算法计算缺页次数。页面走向页面走向23215245325212222555533332333322222553111444442缺页缺页（1）FIFO算法算法第五章 存 储 管 理 页面走向页面走向23215245325212222222233332333555555553111444222缺页缺页（2）LRU算法算法页面走向页面走向23215245325212222224442222333333333333155555555缺页缺页+（3）OPT算法算法第五章 存 储 管 理 例：例：有一请求分页存储管理系统，页面大小为每页有一请求分页存储管理系统，页面大小为每页100字节，若在程序执行时内存字节，若在程序执行时内存中只要一个存储块用来存放数组信息。有一个中只要一个存储块用来存放数组信息。有一个5050的整型数组按行连续存放，的整型数组按行连续存放，每个整数占每个整数占2个字节，将数组初始化为个字节，将数组初始化为“0”的程序如下：的程序如下：问：该程序执行时产生多少次缺页中断？问：该程序执行时产生多少次缺页中断？int a5050;int I,j;for (i=0;i50;i+) for (j=0;j50;j+) aij=0;第五章 存 储 管 理 例：例：有一矩阵，有一矩阵，int a100100;按先行后列次序存储。在一虚存系统中，采用按先行后列次序存储。在一虚存系统中，采用LRU淘汰算法，一个进程有淘汰算法，一个进程有3页内存页内存空间，每页可以存放空间，每页可以存放200个整数。其中第个整数。其中第1页存放程序，且假定程序已在内存。页存放程序，且假定程序已在内存。分别就程序分别就程序A和程序和程序B的执行过程计算缺页次数。的执行过程计算缺页次数。int a100100;int i,j;for (i=0;i100;i+) for (j=0;j100;j+) aij=0;程序程序A:int a100100;int i,j;for (i=0;i100;i+) for (j=0;j100;j+) aji=0;程序程序B:第五章 存 储 管 理 例：例：在一个请求分页系统中，假定系统分给一个作业的物理块为在一个请求分页系统中，假定系统分给一个作业的物理块为3，并且作业执行序列，并且作业执行序列为为1，2，5，1，2，3，4，5。用用FIFO页面置换算法计算缺页次数。页面置换算法计算缺页次数。页面走向页面走向12512345111111333222222443555555缺页缺页FIFO算法算法现序列该为：现序列该为：1，2，3，4，1，2，5，1，2，3，4，5页面走向页面走向123412512345111144455555522221111133333332222244缺页缺页+FIFO算法算法*第五章 存 储 管 理 页面走向页面走向1234125123451111111555544222222211115333333322224444444333缺页缺页+*现将内存空间扩大到现将内存空间扩大到4个页架个页架*此题说明的问题：有些问题的想法跟人们的想法往往是不一致的。此题说明的问题：有些问题的想法跟人们的想法往往是不一致的。第五章 存 储 管 理 5.5.3 堆栈型替换算法堆栈型替换算法设设A是长度为是长度为L的任何页面地址流，的任何页面地址流，t为已经处理过的为已经处理过的 (t-1) 个页面的时间点，个页面的时间点，n 为分配为分配给该地址流的实存页架数，给该地址流的实存页架数，Bt(n) 表示在表示在t时间点，时间点，n个页架的实存中的页面集，个页架的实存中的页面集，Lt 表示表示到到t 时已经遇到过的地址流中相异页的页数，如果页面置换算法具有下列包含性：时已经遇到过的地址流中相异页的页数，如果页面置换算法具有下列包含性：nLt时，时，Bt(n)Bt(n+1)nLt时，时， Bt(n)=Bt(n+1)则称此置换是堆栈型的。则称此置换是堆栈型的。说明：说明：A是一个作业，是一个作业，L是页面的长度，是页面的长度，t为时间点，指的是当执行到为时间点，指的是当执行到t这个时刻已经处理这个时刻已经处理 了了(t-1)个页面。个页面。n为分配给作业为分配给作业A的实际内存的页架数。的实际内存的页架数。Bt(n)指的是：在指的是：在t这个时这个时 间点上，给它分配的间点上，给它分配的n个页架当中在个页架当中在t这个时刻保存的页面的集合。这个时刻保存的页面的集合。Lt表示经过表示经过t 这个时刻，已经处理过的和遇到过的不同的页面的个数。这个时刻，已经处理过的和遇到过的不同的页面的个数。第五章 存 储 管 理 例：例：对下列页地址流对下列页地址流A=1,2,3,4,1,2,5,1,2,3,4,5.时间时间t123456789101112页地址流页地址流123412512345111144455555522221111133333332222244缺页缺页+命中命中命中命中+命中命中1111111555544222222211115333333322224444444333缺页缺页+命中命中命中命中*n=3n=4*=堆栈型算法说明的问题：堆栈型算法说明的问题：在任何时刻，堆栈型算法都遵从这样一个特定：当内存扩充之后，在任何时刻，堆栈型算法都遵从这样一个特定：当内存扩充之后，扩充之后保存的页面和扩充之前保存的页面它们之间存在子集的关系。扩充之后保存的页面和扩充之前保存的页面它们之间存在子集的关系。栈式算法强调的是：栈式算法强调的是：当内存中有当内存中有n个和个和(n+1)个页架的时候，在任何时刻个页架的时候，在任何时刻t，这，这2个页架在内存个页架在内存当中页面的集合存在蕴含关系，凡是满足这样的蕴含关系，则称为栈式当中页面的集合存在蕴含关系，凡是满足这样的蕴含关系，则称为栈式算法。算法。第五章 存 储 管 理 1234567891011122321524532522321524532522321524532532152453333112444331111St(1)St(2)St(3)St(4)St(5)St(6)n=1页地址流页地址流An=2n=3n=4n=5时间时间t命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中命中第五章 存 储 管 理 5. 6 段式管理段式管理1.段式存储管理的基本思想段式存储管理的基本思想2.段式存储管理的地址转换段式存储管理的地址转换3.段的共享与保护段的共享与保护4.段式管理的特点段式管理的特点第五章 存 储 管 理 5.6.1 段式存储管理的基本思想段式存储管理的基本思想段式存储管理中以段为单位分配内存段式存储管理中以段为单位分配内存,每段分配一个连续的内存区每段分配一个连续的内存区.但各段之间不要求但各段之间不要求连续连续.内存的分配和回收与动态分区分配类似内存的分配和回收与动态分区分配类似.段是一个逻辑概念，就是用户在编写程段是一个逻辑概念，就是用户在编写程序的时候你就可以划分成段。序的时候你就可以划分成段。分段地址空间示例：分段地址空间示例：主程序01K分段分段A子程序0600分段分段B子程序0400分段分段C由于段式存储管理系统中作业的地址空间是二维的，因此地址结构包括由于段式存储管理系统中作业的地址空间是二维的，因此地址结构包括2部分：部分：段号和段内位移。段号和段内位移。段号段号S位移量位移量W0111231第五章 存 储 管 理 段的中断处理过程算法如下：段的中断处理过程算法如下：算法算法FOLD(新段新段X的长度）的长度）BEGIN IF (内存中的空闲区内存中的空闲区 X ) IF (内存中空闲区总和内存中空闲区总和 X) 按按FIFO、LRU算法淘汰老段；算法淘汰老段； ELSE 合并空闲区形成不小于合并空闲区形成不小于X段的空闲区；段的空闲区； 为为X段分配内存空闲区；段分配内存空闲区； 将将X段调入内存并改写段表；段调入内存并改写段表； RETURN; END 第五章 存 储 管 理 5.6.2 段式存储管理的地址转换段式存储管理的地址转换在段式管理地址变换过程中，和页式变换基本相同，先要为运行的进程建立一个段表在段式管理地址变换过程中，和页式变换基本相同，先要为运行的进程建立一个段表段号段长存取权限状态起始地址修改位增补位01R042800段段式式存存储储变变换换的的具具体体过过程程段表地址段表地址段表地址寄存器段表地址寄存器1124段号段长存取权限状态起始地址修改位增补位01R0428000234404在段式系统中，分段的共享是通过在段式系统中，分段的共享是通过2个作业的段表中相应表目都指向被共享部分的同个作业的段表中相应表目都指向被共享部分的同一物理副本来实现的。大多数实现共享的系统中，程序被分成过程区和数据区。一物理副本来实现的。大多数实现共享的系统中，程序被分成过程区和数据区。不能修改的过程称为纯过程或可重入过程，这样的过程和不能修改的数据是可以共享不能修改的过程称为纯过程或可重入过程，这样的过程和不能修改的数据是可以共享的，而可修改的程序和数据则不能共享。的，而可修改的程序和数据则不能共享。第五章 存 储 管 理 5.6.3 段的共享与保护段的共享与保护在段式系统中，分段的共享是通过在段式系统中，分段的共享是通过2个作业的段表中相应表目都指向被共享部分的同个作业的段表中相应表目都指向被共享部分的同一个物理副本来实现的。大多数实现共享的系统中，程序被分成过程区和数据区。一个物理副本来实现的。大多数实现共享的系统中，程序被分成过程区和数据区。不能修改的过程称为纯过程或可重入过程，这样的过程和不能修改的数据是可以共享不能修改的过程称为纯过程或可重入过程，这样的过程和不能修改的数据是可以共享的，而可修改的程序和数据则不能共享。的，而可修改的程序和数据则不能共享。第五章 存 储 管 理 5.6.4 段式管理的特点段式管理的特点优点优点:1.提供了内外统一管理的虚存实现方案提供了内外统一管理的虚存实现方案2.段式虚拟每次交换的是一个程序段或数据段。段式虚拟每次交换的是一个程序段或数据段。3.在段式管理中，段长可根据需要动态地调整。在段式管理中，段长可根据需要动态地调整。缺点：缺点：1.要求更多的硬件支持，提高了机器的成本。要求更多的硬件支持，提高了机器的成本。2.由于在内存空闲区管理方式上与分区管理相同，因而存在碎片问题。由于在内存空闲区管理方式上与分区管理相同，因而存在碎片问题。3.每段的长度受内存可用空闲区大小的限制。每段的长度受内存可用空闲区大小的限制。4.若淘汰算法选择不当，也有可能产生抖动。若淘汰算法选择不当，也有可能产生抖动。页式管理与页式管理与 段式管理的主要区别：段式管理的主要区别：页是信息的物理单位，分页是为了实现非连续分配，以便解决内存碎片问题。段页是信息的物理单位，分页是为了实现非连续分配，以便解决内存碎片问题。段是信息的逻辑单位，它含有一组意义相对完整的信息。分段的目的是为了更好实是信息的逻辑单位，它含有一组意义相对完整的信息。分段的目的是为了更好实现共享满足用户的需要。现共享满足用户的需要。页的大小固定且由系统确定，将逻辑地址划分成页号和页内地址是由机器硬件实页的大小固定且由系统确定，将逻辑地址划分成页号和页内地址是由机器硬件实现的。而段的长度却不固定，决定于用户所编写的程序。通常由编译程序再对源现的。而段的长度却不固定，决定于用户所编写的程序。通常由编译程序再对源程序进行编译时根据信息的性质来划分。程序进行编译时根据信息的性质来划分。分页的作业地址空间是一维的，分段的地址空间是二维的。分页的作业地址空间是一维的，分段的地址空间是二维的。第五章 存 储 管 理 5. 7 段页式存储管理段页式存储管理基本思想：把段式和页式二者的优点都结合起来，然后统一地进行考虑。一个逻辑地基本思想：把段式和页式二者的优点都结合起来，然后统一地进行考虑。一个逻辑地 址用址用3个参数表示：段号个参数表示：段号S,页号页号P,页内地址偏移量页内地址偏移量D.SPD为指出运行进程的段表地址，系统中有一个段表地址寄存器来指出进为指出运行进程的段表地址，系统中有一个段表地址寄存器来指出进程的段表起始地址和段表长度。程的段表起始地址和段表长度。第五章 存 储 管 理 段表地址段表长度段表寄存器段表寄存器段号S页号P页内地址D虚地址虚地址V(S,P,D)021321段号段号页表长度页表长度物理地址物理地址越界中断越界中断页表始地址页表始地址0213页号页号页架号页架号段页式存储管理中地址转换段页式存储管理中地址转换转换过程：转换过程：地址转换硬件将段表寄存器内容与指定地址场中的段号地址转换硬件将段表寄存器内容与指定地址场中的段号S按段表的表目进行适当按段表的表目进行适当的移位后相加，得到欲访问段的移位后相加，得到欲访问段S在该进程的段表中的段表项。在该进程的段表中的段表项。从该表的表目中得到该段的页表起始地址，并将其与地址场中的页号从该表的表目中得到该段的页表起始地址，并将其与地址场中的页号P相加后相加后得到欲访问页得到欲访问页P在该段的页表中的表目入口地址。在该段的页表中的表目入口地址。从该页表表目中取出其对应的页架号与指令地址场中的页内地址从该页表表目中取出其对应的页架号与指令地址场中的页内地址D拼装形成绝拼装形成绝对地址。对地址。若运行过程访问虚地址若运行过程访问虚地址V(S,P,D)，在没有联想寄存器下，地址转换过程如下：，在没有联想寄存器下，地址转换过程如下：第五章 存 储 管 理 段页式存储管理的优缺点：段页式存储管理的优缺点：优点优点：(1) 提供二维地址空间，有利于内存共享。提供二维地址空间，有利于内存共享。 (2) 便于段动态扩充，有利于实现动态数据结构。便于段动态扩充，有利于实现动态数据结构。 (3) 对于大型软件，只需在运行中动态链接需要的段。对于大型软件，只需在运行中动态链接需要的段。 (4) 把零头转换为页内零头，提高了存储空间的利用率。把零头转换为页内零头，提高了存储空间的利用率。 缺点缺点：(1) 复杂性和开销增加了。复杂性和开销增加了。 (2) 需要的硬件以及占用的内存页需要增加。需要的硬件以及占用的内存页需要增加。 (3) 如果不采用联想存储器，就会大大降低内存访问效率。如果不采用联想存储器，就会大大降低内存访问效率。 例：例：有一段页式系统，段表和页表存放在主存中。有一段页式系统，段表和页表存放在主存中。(1) 如果对主存的一次存取需要如果对主存的一次存取需要1.5微秒，问：实现一次页面访问的存取时微秒，问：实现一次页面访问的存取时间间 是多少？是多少？(2) 如果系统有快表，平均命中率为如果系统有快表，平均命中率为85。当页表项在快表中时，其查找时。当页表项在快表中时，其查找时 间忽略不计，问：此时的存取时间是多少？间忽略不计，问：此时的存取时间是多少？第五章 存 储 管 理 程序的局部性：是指在一段时间内程序仅仅集中访问某一部分地址空间，具体程序的局部性：是指在一段时间内程序仅仅集中访问某一部分地址空间，具体 包括时间局部性和空间局部性包括时间局部性和空间局部性5.5.4 抖动与程序局部性抖动与程序局部性缺页率：设进程访问内存成功的次数为缺页率：设进程访问内存成功的次数为S,缺页的次数为缺页的次数为F，则总访问次数为，则总访问次数为A， 缺页率缺页率W=F/A;抖动：指页面在内存与外存字节频繁地换入换出，以致于系统用于调度页面所需要的抖动：指页面在内存与外存字节频繁地换入换出，以致于系统用于调度页面所需要的 时间比进程实际运行作业所占用的时间还要多。时间比进程实际运行作业所占用的时间还要多。1、抖动的原因、抖动的原因抖动是由于页的缺页率很高而引起的，页的缺页率高的原因主要有下面两点：抖动是由于页的缺页率很高而引起的，页的缺页率高的原因主要有下面两点：分配给进程的物理页架数过少分配给进程的物理页架数过少页面置换算法不合理页面置换算法不合理程序结构程序结构第五章 存 储 管 理 2、抖动的处理、抖动的处理增加分给进程的物理页架数增加分给进程的物理页架数改进页面置换算法改进页面置换算法用户编写程序时也要充分考虑程序的局部性特征用户编写程序时也要充分考虑程序的局部性特征工作集：在某一个时间范围之内，进程实际上要访问的页的集合。所以把一个运行在工作集：在某一个时间范围之内，进程实际上要访问的页的集合。所以把一个运行在t-w到到t 这个时间间隔内所访问的页的集合称为该进程在时间这个时间间隔内所访问的页的集合称为该进程在时间t的工作集，记为的工作集，记为W(t,w),并称并称 w为为“工作集窗口尺寸工作集窗口尺寸”。工作集工作集.第五章 存 储 管 理 最少页架数最少页架数(1) 一个指令一个指令(2) 间接字间接字页式存储管理的优点页式存储管理的优点:提高了系统资源提高了系统资源(内存内存)的利用率的利用率,解决了固定、可变分区中的碎片问题。解决了固定、可变分区中的碎片问题。引入虚拟存储思想之后，能够实现存储器的扩充。引入虚拟存储思想之后，能够实现存储器的扩充。页式存储管理的缺点页式存储管理的缺点:共享内存问题。共享内存问题。