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