第4章存储管理-上.

第四章存储器管理存储器管理内容1.概述2.连续分配存储管理方式3.不连续分配存储管理方式页式存储管理段式存储管理段页式存储管理4.虚拟存储一、概述存储器的层次结构内存：无限容量大，速度无限快，永久性存储器金钱、技术存储管理寄存器高速缓存主存磁盘缓存磁盘可移动存储介质CPU寄存器主存辅存一、概述•存储管理的目的–主存的分配和管理–提高主存储器的利用率–“扩充”主存容量–存储保护二、概述-程序的装入和链接对用户程序的处理步骤库链接程序装入模块装入程序编译程序产生的目标模块第一步:编译第二步：链接第三步：装入内存…地址映射LoadA12003456。。1200物理地址空间LoadAdata1data13456源程序LoadA20034560100200编译连接逻辑地址空间BA=1000名空间、地址空间、存储空间2.1.程序的装入绝对装入方式–程序中所使用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。但在由程序员直接给出绝对地址时，不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。可重定位装入方式动态运行时装入方式–动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此,装入内存后的所有地址都仍是相对地址。绝对装入方式MOV1000,5CALL100printf0100400a1000逻辑地址空间MOV1000,5CALL100printf0100400a1000物理地址空间可重定位装入方式MOV1000,5CALL100printf0100400a1000逻辑地址空间MOV,5CALLprintf400041004400a5000物理地址空间50004100MOV1000,5CALL100printf400041004400a5000CPU+4000重定位寄存器MMUMOV1000,51000逻辑地址5000物理地址动态运行时装入方式2.2.程序的链接静态链接方式在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。装入时动态链接在装入内存时是边装入内存，边装入边链接，即在装入一个目标模块时，若发生一个外部模块调用，将引起装入程序去找出相应的外部目标模块，并将它装入内存。运行时动态链接对某些目标模块的链接，是在程序执行中需要该（目标）模块时，才对它进行的链接。静态链接方式在将这几个目标模块装配成一个装入模块时，须解决以下两个问题：–(1)对相对地址进行修改。–(2)变换外部调用符号。程序链接示意图装入时动态链接装入时动态链接方式有以下优点：(1)便于修改和更新。(2)便于实现对目标模块的共享。运行时动态链接(Run-timeDynamicLinking)近几年流行起来的运行时动态链接方式，是对上述在装入时链接方式的一种改进。这种链接方式是将对某些模块的链接推迟到执行时才执行，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。三、连续内存分配方式单一连续分配分区式分配固定分区式动态分区式动态重定位分配3.1单一连续分配（1）基本原理：内存分为两个区域：系统区，用于操作系统;用户区，用于用户进程。用户区某一时刻只能存放一个用户进程，称为“单道，单一”用户程序位于RAM中的操作系统0xFFF...0位于RAM中的操作系统用户程序0ROM中的设备驱动程序用户程序位于RAM中的操作系统0（2）内存的分配和回收一般用户单道系统用时分配，空闲回收（3）内存的保护为了防止用户程序破坏操作系统的代码和数据，要采取一些保护措施。采用动态重定位时加一些保护措施，用到两个寄存器：重定位寄存器：用户程序装入内存的起始地址界限寄存器：存放用户程序的长度物理地址CPU界限寄存器＋重定位寄存器内存逻辑地址是否地址错误3.2.固定分区分配1基本原理分区4分区3分区2分区1操作系统输入队列2划分分区的方法(1)分区大小相等,即使所有的内存分区大小相等。适用于控制多个相同对象。(2)分区大小不等。多个较小的分区，适量的中等分区及少量的大分区3.内存分配固定分区使用表如何回收3.3动态分区分配1基本原理根据进程的需要动态地分配连续的内存空间。实现时涉及到三个问题：分区分配中的数据结构、分区分配算法和分区的分配与回收。2分区分配中的数据结构空闲分区表空闲分区链0操作系统400K2560K－11000KP3,300K2000K2300K260K300KP4，700K100KP5,500K900K1700K起始地址长度900K100K1700K300K2300K260K空闲分区表900K100K1700K300K2300K260KNULL空闲分区链可变分区模式的工作流程先看一个例子。一个计算机有2560K内存，采用可变分区模式管理内存，操作系统占用低地址的400K空间，剩余2160K的空间为用户区。最初整个用户区是空闲的，就一个分区。然后随着用户程序的创建和撤销。分区的个数和大小位置开始变化。P1来，600K0操作系统400K2560K－1P1，600K1000K1560K内存的初始状态P2来，1000K0操作系统400K2560K－1P1，600K1000K560K2000KP2，1000K0操作系统400K2560K－12160KP3来，300K0操作系统400K2560K－1P1，600K1000KP3,300K2000KP2，1000K2300K260KP2结束0操作系统400K2560K－1P1，600K1000KP3,300K2000K2300K260K1000KP4来700KP1结束P5来500K0操作系统400K2560K－11000KP3,300K2000K2300K260K300KP4，700K600K1700K0操作系统400K2560K－11000KP3,300K2000K2300K260K300KP4，700K100KP5,500K900K1700K0操作系统400K2560K－1P1，600K1000KP3,300K2000K2300K260K300KP4，700K1700K3.分区分配算法首次适应算法FF循环首次适应算法最佳适应算法最坏适应算法快速适应算法•首次适应算法–该算法要求空闲分区链按照空闲分区起始地址递增的次序排序。–在分配内存时，每次都从链首开始查找，直至找到一个长度大于用户程序的分区，就进行分配。–倾向于优先利用内存中低址部分的内存，从而保留高址的大空闲区，但是低址部分会留下许多难以利用的、很小的内存空闲区，增加查找时间•循环首次适应算法–该算法是从首次适应算法演变而来的。在分配内存时，不再是每次都从链首开始找，而是从上次找到的空闲分区的下一个节点开始找。到了链尾，再从链首开始找。–内存中空闲区分布的比较均匀，减少查找时间，但会缺乏大的空闲区。•最佳适应算法–所谓“最佳”是指分配内存时，总是把满足要求的最小分区分配给用户程序。–为了加快分配速度，可以把空闲分区链按照空闲分区的大小递增的顺序排序，则找到的第一个满足要求的分区即是最佳的。–每次分配剩下的内存是最小的，导致存储区留下许多难以利用的小空闲区•最坏适应法–将空闲区从大到小分配，每次都分配最大的空闲区。–优点是可使剩下的空闲区不至于太小，产生碎片的几率最小，适合中小作业，同时分配算法查找效率最高。–缺点导致缺乏大空闲区。以上4种算法都为顺序搜索法•快速适应算法：又称为分类搜索法–将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，在内存中设立一张管理索引表，该表的每一表项对应了一个空闲分区类型并记录了该类型空闲分区链表表头的指针。空闲分区的分类是根据进程常用的空间大小进行划分，如2KB，4KB，8KB等。–优点：查找效率高，根据进程的长度，寻找到能容纳它的最小空闲区链表，取下第一块进行分配即可。能保持大空间需要，也不会产生内存碎片，–分区归还主存时算法复杂，系统开销较大。4.分区分配操作–分配内存从头开始查表检索完否？m.size＞u.size?m.size－u.size≤size?从该分区中划出u.size大小的分区将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出YNNYYN内存分配流程–回收内存根据回收区的首址，从空闲区链表中找到相应的插入点，可能出现以下4种情况：P2P1P3P1运行结束P2P1P3F1P3运行结束P1所占分区的上下都不空闲，在空闲分区链中添加一项，填写回收区的首址和大小P3所占分区下边的分区F1空闲，应进行合并。在空闲分区链中找到F1节点，修改其起始地址和长度P2P1P3F1P2运行结束P2所占分区上边的分区F1空闲，应进行合并。在空闲链表中找到F1节点，修改其长度P2P1P3F1F2P1运行结束P2P2所占分区上下边的分区F1和F2都空闲，应进行合并。在空闲链表中找到F1节点，修改其长度为F1、F2和P2所占分区的长度和。删除F2节点•伙伴系统固定分区和动态分区方式都有不足之处。固定分区方式限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，内存空间利用率很低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。伙伴系统方式是对以上两种内存方式的一种折衷方案。伙伴系统规定，无论已分配分区或空闲分区，其大小均为2的k次幂，k为整数，l≤k≤m，其中：21表示分配的最小分区的大小，2m表示分配的最大分区的大小，通常2m是整个可分配内存的大小。假设系统的可利用空间容量为2m个字，则系统开始运行时，整个内存区是一个大小为2m的空闲分区。在系统运行过程中，由于不断的划分，可能会形成若干个不连续的空闲分区，将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了k(0≤k≤m)个空闲分区链表。当需要为进程分配一个长度为n的存储空间时，首先计算一个i值，使2i－1n≤2i，然后在空闲分区大小为2i的空闲分区链表中查找。若找到，即把该空闲分区分配给进程。否则，表明长度为2i的空闲分区已经耗尽，则在分区大小为2i＋1的空闲分区链表中寻找。若存在2i＋1的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为2i的空闲分区链表中。若大小为2i＋1的空闲分区也不存在，则需要查找大小为2i＋2的空闲分区，若找到则对其进行两次分割：第一次，将其分割为大小为2i＋1的两个分区，一个用于分配，一个加入到大小为2i＋1的空闲分区链表中；第二次，将第一次用于分配的空闲区分割为2i的两个分区，一个用于分配，一个加入到大小为2i的空闲分区链表中。若仍然找不到，则继续查找大小为2i＋3的空闲分区，以此类推。由此可见，在最坏的情况下，可能需要对2k的空闲分区进行k次分割才能得到所需分区。•哈希算法以空闲分区大小为关键字建立适当的哈希函数，形成哈希表。该表的每一个表项记录了一个空闲分区链表表头指针。当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。6.可重定位分区分配1）动态重定位的引入碎片-紧凑-程序地址变化操作系统P110KP315KP730KP8操作系统P110KP315KP730KP8紧凑技术compaction2动态重定位示意图LOAD1,25003650100250050002500相对地址10000重定位寄存器＋LOAD1,2500365100