《存储管理上》PPT课件.ppt

第四章 存储器管理,存储器管理内容,1.概述 2.连续分配存储管理方式 3. 不连续分配存储管理方式 页式存储管理 段式存储管理 段页式存储管理 4.虚拟存储,一、概述,存储器的层次结构,内存：无限容量大，速度无限快，永久性存储器,金钱、技术,存储管理,一、概述,存储管理的目的 主存的分配和管理 提高主存储器的利用率 “扩充”主存容量 存储保护,二、概述-程序的装入和链接,对用户程序的处理步骤,地址映射,Load A 1200 3456 。 。,1200,物理地址空间,Load A data1 data1 3456,源程序,Load A 200 3456,0,100,200,编译 连接,逻辑地址空间,BA=1000,名空间、地址空间、存储空间,2.1.程序的装入,绝对装入方式 程序中所使用的绝对地址，可在编译或汇编时给出， 也可由程序员直接赋予。 但在由程序员直接给出绝对地址时， 不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。 可重定位装入方式 动态运行时装入方式 动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此,装入内存后的所有地址都仍是相对地址。,绝对装入方式,MOV 1000,5,CALL 100,printf,0,100,400,a,1000,物理地址空间,可重定位装入方式,动态运行时装入方式,2.2.程序的链接,静态链接方式 在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。 装入时动态链接 在装入内存时是边装入内存，边装入边链接，即在装入一个目标模块时，若发生一个外部模块调用，将引起装入程序去找出相应的外部目标模块，并将它装入内存。 运行时动态链接 对某些目标模块的链接，是在程序执行中需要该（目标）模块时，才对它进行的链接。,静态链接方式,在将这几个目标模块装配成一个装入模块时，须解决以下两个问题： (1) 对相对地址进行修改。 (2) 变换外部调用符号。,程序链接示意图,装入时动态链接,装入时动态链接方式有以下优点： 便于修改和更新。 (2) 便于实现对目标模块的共享。,运行时动态链接(Run-time Dynamic Linking),近几年流行起来的运行时动态链接方式，是对上述在装入时链接方式的一种改进。这种链接方式是将对某些模块的链接推迟到执行时才执行，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存， 把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。,三、连续内存分配方式,单一连续分配 分区式分配 固定分区式 动态分区式 动态重定位分配,3.1 单一连续分配,（1）基本原理： 内存分为两个区域： 系统区，用于操作系统; 用户区，用于用户进程。用户区某一时刻只能存放一个用户进程，称为“单道，单一”,（2）内存的分配和回收 一般用户单道系统 用时分配，空闲回收 （3）内存的保护 为了防止用户程序破坏操作系统的代码和数据，要采取一些保护措施。 采用动态重定位时加一些保护措施，用到两个寄存器： 重定位寄存器：用户程序装入内存的起始地址 界限寄存器：存放用户程序的长度,3.2.固定分区分配,1 基本原理,2 划分分区的方法 (1)分区大小相等,即使所有的内存分区大小相等。适用于控制多个相同对象。 (2) 分区大小不等。 多个较小的分区，适量的中等分区及少量的大分区,3.内存分配,固定分区使用表,如何回收,3.3 动态分区分配,1 基本原理 根据进程的需要动态地分配连续的内存空间。实现时涉及到三个问题：分区分配中的数据结构、分区分配算法和分区的分配与回收。 2 分区分配中的数据结构 空闲分区表 空闲分区链,空闲分区表,空闲分区链,可变分区模式的工作流程 先看一个例子。一个计算机有2560K内存，采用可变分区模式管理内存，操作系统占用低地址的400K空间，剩余2160K的空间为用户区。 最初整个用户区是空闲的，就一个分区。然后随着用户程序的创建和撤销。分区的个数和大小位置开始变化。,内存的初始状态,3.分区分配算法,首次适应算法FF 循环首次适应算法 最佳适应算法 最坏适应算法 快速适应算法,首次适应算法 该算法要求空闲分区链按照空闲分区起始地址递增的次序排序。 在分配内存时，每次都从链首开始查找，直至找到一个长度大于用户程序的分区，就进行分配。 倾向于优先利用内存中低址部分的内存，从而保留高址的大空闲区，但是低址部分会留下许多难以利用的、很小的内存空闲区，增加查找时间 循环首次适应算法 该算法是从首次适应算法演变而来的。在分配内存时，不再是每次都从链首开始找，而是从上次找到的空闲分区的下一个节点开始找。到了链尾，再从链首开始找。 内存中空闲区分布的比较均匀，减少查找时间，但会缺乏大的空闲区。,最佳适应算法 所谓“最佳”是指分配内存时，总是把满足要求的最小分区分配给用户程序。 为了加快分配速度，可以把空闲分区链按照空闲分区的大小递增的顺序排序，则找到的第一个满足要求的分区即是最佳的。 每次分配剩下的内存是最小的，导致存储区留下许多难以利用的小空闲区 最坏适应法 将空闲区从大到小分配，每次都分配最大的空闲区。 优点是可使剩下的空闲区不至于太小，产生碎片的几率最小，适合中小作业，同时分配算法查找效率最高。 缺点导致缺乏大空闲区。 以上4种算法都为顺序搜索法,快速适应算法：又称为分类搜索法 将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，在内存中设立一张管理索引表，该表的每一表项对应了一个空闲分区类型并记录了该类型空闲分区链表表头的指针。空闲分区的分类是根据进程常用的空间大小进行划分，如2KB，4KB，8KB等。 优点：查找效率高，根据进程的长度，寻找到能容纳它的最小空闲区链表，取下第一块进行分配即可。能保持大空间需要，也不会产生内存碎片， 分区归还主存时算法复杂，系统开销较大。,4.分区分配操作,分配内存,内存分配流程,回收内存 根据回收区的首址，从空闲区链表中找到相应的插入点，可能出现以下4种情况：,P1运行结束,P3运行结束,P1所占分区的上下都不空闲，在空闲分区链中添加一项，填写回收区的首址和大小,P3所占分区下边的分区F1空闲，应进行合并。在空闲分区链中找到F1节点，修改其起始地址和长度,P2运行结束,P2所占分区上边的分区F1空闲，应进行合并。在空闲链表中找到F1节点，修改其长度,P1运行结束,P2,P2所占分区上下边的分区F1和F2都空闲，应进行合并。在空闲链表中找到F1节点，修改其长度为F1、F2和P2所占分区的长度和。删除F2节点,伙伴系统 固定分区和动态分区方式都有不足之处。固定分区方式限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，内存空间利用率很低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙伴系统方式是对以上两种内存方式的一种折衷方案。 伙伴系统规定，无论已分配分区或空闲分区，其大小均为2的k次幂，k为整数，lkm，其中：21表示分配的最小分区的大小，2m表示分配的最大分区的大小，通常2m是整个可分配内存的大小。 假设系统的可利用空间容量为2m个字，则系统开始运行时，整个内存区是一个大小为2m的空闲分区。在系统运行过程中，由于不断的划分，可能会形成若干个不连续的空闲分区，将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了k(0km)个空闲分区链表。,当需要为进程分配一个长度为n的存储空间时，首先计算一个i值，使2i1n2i，然后在空闲分区大小为2i的空闲分区链表中查找。若找到，即把该空闲分区分配给进程。否则，表明长度为2i的空闲分区已经耗尽，则在分区大小为2i1的空闲分区链表中寻找。若存在2i1的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为2i的空闲分区链表中。若大小为2i1的空闲分区也不存在，则需要查找大小为2i2的空闲分区，若找到则对其进行两次分割：第一次，将其分割为大小为2i1的两个分区，一个用于分配，一个加入到大小为2i1的空闲分区链表中；第二次，将第一次用于分配的空闲区分割为2i的两个分区，一个用于分配，一个加入到大小为2i的空闲分区链表中。若仍然找不到，则继续查找大小为2i3的空闲分区，以此类推。由此可见，在最坏的情况下，可能需要对2k的空闲分区进行k次分割才能得到所需分区。,哈希算法 以空闲分区大小为关键字建立适当的哈希函数，形成哈希表。该表的每一个表项记录了一个空闲分区链表表头指针。 当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。,6. 可重定位分区分配,1）动态重定位的引入 碎片-紧凑-程序地址变化,2）动态重定位的实现,动态重定位示意图,3 ）动态重定位分区分配算法,动态分区分配算法流程图,7、交换（Swapping）,交换(Swapping)的引入 为了提高内存的利用率，出现了交换技术。 进程在运行过程中经常因为进行I/O操作和等待其他事件而阻塞，无法执行。系统在内存紧张时把这些进程暂时换出内存放入外存，腾出内存分配给有条件运行的进程。 所谓“对换”， 是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的有效措施。 以进程为单位进行交换,对换空间的管理 在外存上，系统管理着专门的空间用于存放从内存换出的进程，这空间称为对换区。 为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。其形式与内存在动态分区分配方式中所用数据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项， 即对换区的首址及其大小，它们的单位是盘块号和盘块数。,进程的换出与换入 进程的换出：每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。 其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改 选择阻塞、优先级低-将次进程保持到交换区-回收内存 进程的换入 交换区中选择“就绪”、时间最久-换入到内存。,四、基本分页存储管理,4.1 基本原理 把用户的程序空间(逻辑地址空间）划分成大小相等的块，称为页（面）、逻辑页，从0开始给页编号。 页的大小应是2的n次幂，通常是512B8KB 物理内存按照页的大小也划分成大小相等的区域，称为页框、物理页、物理块，从0开始编号 内存分配：将进程空间中的逻辑页面映射到物理空间中空闲的页面,.,.,.,要求要把程序的所有页都装入到内存后，程序才能运行。,用户程序分页逻辑地址的结构： 32位 011位页内地址（每页大小为4KB=212KB）；1231页号（地址空间最多允许有1M=220页）,对于某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：,其中，INT是整除函数，MOD是取余函数。例如，其系统的页面大小为1 KB，设A = 2170 B 则由上式可以求得P = 2，d = 122。,2、数据结构 （1）内存页表： 要完成内存物理页的分配，则必须知道哪些物理页空闲，哪些被占用。要用一个数据结构来随时记录内存的情况，这个数据结构称为内存页表。,问题：内存页表有多少项？与哪些因素有关？,回答： 内存页表的行数 内存的大小 / 页的大小,（2）进程页表 内存页表中的空闲物理页是随着不断的分配与回收而随机分布的。因此一个程序的所有页装入到哪些内存物理页也是随机的。这就需要为每一个进程建立一张表，来记录该进程的每一页都装入到哪个物理页去了，这张表称为进程页表。,进程页表,进程页表,问题：进程页表放在哪儿？,回答：内存,问题：进程页表的首地址放在哪儿？,回答：进程的PCB，页表的长度也放PCB,4.3分配与回收 分配过程,回收过程 根据进程页表的内容，把内存页表中对应的物理页改为空闲 撤销进程页表,4.4地址转换（重定位）问题,某系统逻辑地址32位，页的大小为4K,用户程序空间,进程页表,物理内存,8193应转换的物理地址是什么？,逻辑页号为2，页内地址1,由页表得知2号逻辑页装入到6号物理页，所以物理地址为：,64K1 24577,P=INTA/L d=AMOD L,1.基本的地址变换机构,注意：要求页表连续存放,PTR,问题：在这种分页管理模式中，若要访问内存的数据需要访问内存几次？为什么？,回答：2次。因为一次用于在地址转换时访问内存的页表，从而形成真正的物理地址；第二次通过真正的物理地址访问内存中的数据。,这会降低系统的性能,2.快表,为了解决上述问题，在地址变换结构中，采用一个具有并行查询能力的特殊高速缓冲区（联想存储器），存放当前访问过的页表项，称为快表。IBM-TLB 每次进行地址转换时，首先查找快表，若找到所需的页表项，则快速形成物理地址。否则从页表中查找后形成物理地址，同时把相应的页表项写入快表。如果设计得当，快表的命中率可以很高。,具有快表的地址变换机构,4.5.两级页表、多级页表,1.问题引入 大逻辑空间（232264）-大页表 32位系统，页面大小4k-1M页表项 * 1字节 = 1M 页表内存空间必须是连续的 解决思路 对页表所需的内存空间采用离散的分配方式 只有需要时才调用部分页项到内存，其余保存在磁盘,例如：一个32位的系统支持的逻辑空间最大为232 B,页的大小为4KB,即212，一个页表项占用4个字节,问：一个进程页表最多有多少个表项？,问：一个进程页表需要占多大的内存？,答：1M 4B 4MB,进程页表是要连续存放的，则4MB空间需要连续的4MB/4KB=1024个物理块。,2.两级页表,针对难以找到大的连续空间存放页表，采用对页表进行分页的方法,问题：一个物理块与页的大小相同也为4KB，能存放多少个进程页表表项？,问：应该记住每个小页表的位置，即被装入到哪个物理块去的信息，怎么记录？,答：用一个表格，称为外层页表，如下图,问：这个外层页表多大？需要几个物理块？,答：1024 4B 4KB，需要一个物理块，外层页表的地址放入进程的PCB。,两级页表下的地址转换,例如:一个逻辑地址4098，对应的物理地址应是多少？页的大小为4KB,4098的逻辑页号和页内地址是多少？,1号逻辑页，页内地址2,1号逻辑页对应的物理块号是多少？,1号逻辑页的信息处于的几个小页表？在该小页表中是第几项，即在小页表的页内地址？,1号逻辑页的信息处于第几个小页表？在该小页表中是第几项，即在小页表的页内地址？,查找外层页表找到0号小页表的物理块号为1011， 然后查找1011号物理块，从中找出第1个表项内容为4，即4号物理块。页号1对应的物理块为4。,两级页表下的逻辑地址结构,外层页表地址寄存器,逻辑地址,外层页表,小页表,内存块,二级页表结构及地址映射,4.6.分页中的保护,1.防止一个进程去破坏另一个进程的数据和代码 实现：在地址转换的过程中实现：越界错误 2.给每一页设置一个访问属性 如某页中代码是可执行的，不能修改 某页的数据是可读可写的 某页的数据是只读，不能修改 实现：在页表中增加一访问属性信息,五、分段存储管理,问题引入 在分页管理模式中，逻辑地址空间是一维的，逻辑地址是连续的 用户程序空间中的04095字节是第0页，40968191是第1页,，程序员和编译器并不知道分页的存在 在一个逻辑页内可能包含各种内容：如代码、数据等，这一页的信息是不相关的。 而分段管理模式按照程序中内容的逻辑关系，把用户程序划分成不同的部分。,0,116,N,五、分段存储管理,1）方便编程 2）信息共享 在实现对程序和数据的共享时，是以信息的逻辑单位为基础的。分页系统中的“页”只是存放信息的物理单位(块)，并无完整的意义，不便于实现共享；然而段却是信息的逻辑单位。 3)信息保护 信息保护同样是对信息的逻辑单位进行保护 4)动态增长 在实际应用中，往往有些段，特别是数据段，在使用过程中会不断地增长，而事先又无法确切地知道数据段会增长到多大。前述的其它几种存储管理方式，都难以应付这种动态增长的情况，而分段存储管理方式却能较好地解决这一问题。 5)动态链接,5.1分段存储基本原理,分段 在分段管理方式中，一个用户程序的地址空间就是许多段的集合。每一个段的地址都是从0开始到该段的最大值,每个段都有独立编号。 分段地址结构,31 16 15 0,在该地址结构中，允许一个作业最长有64K个段，每个段的最大长度为64KB,段X,段M,段B,段Y,段A,5.1分段存储基本原理,当用户程序请求运行时，系统根据用户程序中段的个数，把每个段装入到内存中一块够大的空闲分区中(可能要进行分割）。各分区之间不一定连续。 只有把所有的段都装入到内存后，程序才能运行。 若此时内存中没有足够多的够大的分区，则用户程序等待。 对内存的管理与可变分区模式相同。,5.1分段存储基本原理,段表：逻辑段-物理内存区的映射 段表存放在内存，其起始地址和长度存入进程的PCB,操作系统,逻辑地址00000000000000110000000000000010，物理地址是多少？,地址转换-动态重定位,Cl,Cb,+,比较,比较,b + d,比较,段表,S= Cl,快表,物理地址,段表始址寄存器,段表长度寄存器,逻辑地址,l,b,.,.,.,S,l,b,地址越界,d=1,d=l,地址映射及存储保护机制,地址越界,地址越界,比较,长度,始址,5.1分段存储基本原理,分页与分段的区别 页是信息的物理单位，段则是信息的逻辑单位 页的大小固定且由系