第五章 存储管理VIP

.,1,第五章存储管理,主存的管理,.,2,第五章存储管理,5.1存储管理的功能5.2分区存储管理5.3覆盖和交换5.4页式管理5.5段式与段页式管理5.6局部性原理与抖动问题,.,3,5.1存储管理的功能,5.1.1虚拟存储器5.1.2地址变换5.1.3内外存数据传输的控制5.1.4内存的分配与回收5.1.5内存信息的共享与保护,.,4,5.1.1虚拟存储器,内存由顺序编址的块组成，内存的每个存储单元都有一个编号，这种编号称为内存地址（或称为物理地址，绝对地址）。内存地址的集合称为内存空间（或物理地址空间）。,.,5,5.1.1虚拟存储器,用户编程所用的地址称为逻辑地址（或虚地址）。由逻辑地址组成的空间称为逻辑地址空间（或虚拟地址空间）。,.,6,5.1.1虚拟存储器,源程序目标代码地址安排？按照物理存储器中的位置赋予实际物理地址。优点：CPU执行目标代码时的执行速度高。缺点：能装入内存并发执行的进程数大大减少，对于某些较大的进程可能会无法执行；编译程序将非常复杂，编译程序必须知道内存的当前空闲部分及其地址，并且把一个进程的不同程序段连续地存放起来,.,7,由编译链接程序编译后链接（静态、动态）到一个以0地址为始地址的线性或多维虚拟地址空间（逻辑地址空间）。每个进程都拥有一个虚拟地址空间。每个指令或数据单元都在这个虚拟空间中拥有确定的地址，把这个地址称为虚拟地址（virtualaddress）(逻辑地址)。,.,8,5.1.1虚拟存储器,虚拟存储器：进程中的目标代码、数据等的虚拟地址组成的虚拟空间称为虚拟存储器。,.,9,实现虚拟内存的基本原理,将程序正在使用的部分内容放在内存，而暂时不用的部分放在外存，在需要时由系统调入内存，并将不需要（或暂不需要）的部分调出内存。由于程序在执行时，在一段时间内一般仅使用它的程序的一部分（或一小部分），所以程序仅有部分装入内存完全能够正确执行。要由操作系统结合相关硬件来完成上述工件，这样计算机好象为用户提供了一个容量远大于内存的存储器，这个存储器称为虚拟存储器。,.,10,5.1.1虚拟存储器,虚拟存储器呈现在用户面前的是一个在物理上只受内存和外存总容量限制的存储系统，这要求存储管理系统只把进程执行时频繁使用和立即需要的指令与数据等存放在内存中，而把那些暂时不需要的部分存放在外存中，待需要时自动调入，以提高内存的利用率和并行执行的作业道数。虚拟存储器不考虑物理存储器的大小和信息存放的实际位置，只规定每个进程中互相关联的信息的相对位置。每个进程都拥有自己的虚拟存储器，且虚拟存储器的容量是由计算机的地址结构和寻址方式确定的。,.,11,5.1.2地址变换,地址重定位：从虚拟地址到内存地址的转换称为地址重定位，或称为地址映射。地址映射的方式：1、静态地址重定位2、动态地址重定位,.,12,1、静态地址重定位,在虚拟空间程序执行之前由装配程序完成地址映射的工作。不能实现虚拟存储器假定程序装入内存的首地址为BA，程序地址为VA，内存地址为MA，则地址映射按下式进行：MA=(BA)+(VA)。,.,13,例,程序装入内存的首地址为1000，则装配程序就按MA=1000+VA对程序中所有地址部分进行修改，修改后指令LoadA，200就变为LoadA，1200,.,14,静态地址重定位的优缺点,优点：不需要硬件的支持。缺点：程序必须占用连续的内存空间，程序和数据不能共享；程序一旦装入内存之后就不能再移动，并且必须在程序执行之前将有关部分全部装入。,.,15,2、动态地址重定位,动态地址重定位是在程序执行的过程中，在CPU访问内存之前，将要访问的程序地址转换为内存地址。一般来说这种转换是由专门的硬件机构来完成的。在地址重定位机构中，有一个基地址寄存器BR和一个程序地址寄存器VR，一个内存地址寄存器MR。MA=(BR)+(VR),.,16,2、动态地址重定位,动态地址重定位的具体过程：程序装入内存后，它所占用的内存区的首地址由系统送入基地址寄存器BR中。在程序执行的过程中，若要访问内存，将访问的逻辑地址送入程序地址寄存器VR中。地址转换机构把VR和BR中的内容相加，并将结果送入MR中，作为实际访问的物理地址。,.,17,图5.3动态地址重定位,.,18,2、动态地址重定位,动态地址重定位的优点可以对内存进行非连续分配。程序占用的内存空间是动态可变的，当程序从某个存储区移到另一个区域时，只需要修改相应的寄存器BR的内容即可。提供了实现虚拟存储器的基础。一个程序不一定要求占用一个连续的内存空间。可以部分地装入程序运行。便于多个进程共享同一个程序的代码。,.,19,2、动态地址重定位,动态地址重定位的代价：需要硬件的支持。实现存储管理的软件算法较为复杂。,.,20,5.1.3内外存数据传输的控制,内外存数据传输的控制：用户程序自己控制：覆盖技术用户负担很大，程序段的最大长度受内存容量限制，不能实现虚拟存储器。操作系统控制：交换(swapping)方式：不同的进程或作业之间请求调入(ondemand)方式和预调入(onprefetch)方式,.,21,5.1.4内存的分配与回收,要完成内存的分配和回收工作，要求设计者选择和确定以下几种策略和结构：分配结构调入策略放置策略交换策略回收策略,.,22,5.1.4内存的分配与回收,分配结构分配结构是用来登记内存使用情况的数据结构。如空闲区表、空闲区队列等。调入策略用户程序在何时、怎样调入内存的策略。放置策略用户程序调入内存时，确定将其放置在何处的策略。,.,23,5.1.4内存的分配与回收,交换策略当需要将某个用户程序调入内存而内存空间又不够时，就要确定哪个或哪些程序可以从内存中移走。回收策略确定回收的时机和对所回收的内存空闲区和已存在的内存空闲区进行调整。,.,24,5.1.5内存信息的共享与保护,保证在内存中的多道程序只能在给定的存储区域内活动并互不产生干扰。包括：防止地址越界防止越权(对共享区有访问权),.,25,5.1.5内存信息的共享与保护,内存保护的方法：硬件法、软件法和软硬件法。上下界保护法：硬件法1、在CPU中设置一对下限寄存器和上限寄存器存放用户作业在主存中的下限和上限地址2、每当CPU要访问主存，硬件自动将被访问的主存地址与界限寄存器的内容进行比较，以判断是否越界3、如果未越界，则按此地址访问主存，否则将产生程序中断越界中断（存储保护中断）,.,26,图5.4上、下界寄存器保护法,.,27,5.1.5内存信息的共享与保护,保护键法：软件法为每一个被保护的存储块分配一个单独的保护键。在程序状态字中设置相应的保护键开关字段，访问过程中比较保护开关字段的内容和保护键是否匹配，匹配则允许访问，否则产生访问出错中断。,.,28,图5.5保护键保护法,.,29,5.1.5内存信息的共享与保护,界限寄存器与CPU的用户态或核心态工作方式相结合的保护方式。软硬件法用户态进程只能访问那些在界限寄存器所规定范围内的内存部分，而核心态进程则可以访问整个内存地址空间。,.,30,5.2分区存储管理,把整个内存划分为若干大小不等的区域，操作系统占用一个区域，其它区域供系统中的多个进程共享，这种方法称为分区存储管理。5.2.1分区存储管理的基本原理5.2.2分区的分配与回收5.2.3有关分区管理其他问题讨论,.,31,5.2.1分区存储管理的基本原理,基本原理：给每一个内存中的进程划分一块适当大小的存储区,以连续存储各进程的程序和数据，使各进程得以并发执行。这是最简单的一种存储管理，按分区划分的时机可分为：1、固定分区2、动态分区,.,32,1、固定分区,固定分区：把内存固定地划分为若干个大小不等的区域。分区的划分由计算机的操作员或者由操作系统给出，并给出分区说明表。在调度作业时，由存储管理根据所需量在分区说明表中找出一个单元分配给它。,.,33,1、固定分区,分区说明表,.,34,图5.6固定分区法,.,35,1、固定分区,在作业大小和出现频率均已知的情况下，固定分区是合适的。在这种情况下分区的大小选择与作业大小相当，这样内存的使用效率较高。但是若作业的大小和出现的频率不知道时，势必造成分区的大小和作业的大小相差甚远，这样就会造成存储空间的浪费，从而影响整个系统的效率。,.,36,2、动态分区,动态分区：在系统运行的过程中建立分区，并使分区的大小刚好与作业的大小相等。这种存储管理的方法解决了固定分区严重浪费内存的问题。是一种较为实用的存储管理方法。,.,37,图5.7动态分区内存初始分配情况,.,38,2、动态分区,在实现动态分区分配的时候需要涉及到以下三个方面的问题：动态分配中所用到的数据结构；分区的分配算法；分区的分配和回收操作。,.,39,2、动态分区,实现动态分区的数据结构：在动态分区存储管理中，要有相应的数据结构来登记空闲区的说明信息，它包括空闲区的大小和位置。其数据结构有：分区说明表、可用分区表（或自由链）、请求表。分区说明表可用分区表：用于为内存中每个还没有分区设置一个表项，每个分区表项包含分区序号、分区起始地址以及分区大小。（占用内存）,.,40,2、动态分区,实现动态分区的数据结构：自由链：利用每个内存空闲区的头几个单元存放本空闲区的大小和下个空闲区的起始地址，将所有空闲区组成一条链。（不占用内存）请求表：表的每个表目描述请求内存资源的作业或进程号以及所请求的内存大小。,.,41,图5.9可用表、自由链及请求表,.,42,图5.8内存分配变化过程,.,43,5.2.2分区的分配与回收,1、固定分区的分配与回收2、动态分区时的分配与回收3、动态分区时的回收与拼接4、几种分配算法的比较,.,44,1、固定分区的分配与回收,分配：当用户程序要装入执行时，通过请求表提出内存分配要求和所要求的内存空间大小。存储管理程序根据请求表要求查询分区说明表，从中找出一个满足要求的空闲分区，将其分配给申请者。P117图回收：回收时管理程序只需将对应的分区状态置为未使用即可。,.,45,2、动态分区时的分配与回收,主要解决的三个问题:(1)对于请求表中的要求内存长度，从可用表或自由链中寻找出合适的空闲区分配程序。(2)分配空闲区之后，更新可用表或自由链。(3)进程或作业释放内存资源时，和相邻的空闲区进行链接合并，更新可用表或自由链。,.,46,2、动态分区时的分配与回收,从可用表或自由链中寻找空闲区的常用的三种方法：最先适应法(firstfitalgorithm)最佳适应法(bestfitalgorithm)最坏适应法(worstfitalgoriathm)这三种方法要求可用表或自由链按不同的方式排列。,.,47,最先适应法,要求可用表或自由链按起始地址递增的次序排列。分配：当进程申请大小为SIZE的内存时，存储管理程序从空闲区表的第一个表目开始查询，直到首次找到等于或大于SIZE的空闲区。从该区中划出大小为SIZE的分区分配给进程，余下的部分仍作为一个空闲区留在空闲区表中，但要修改其首址和大小。,.,48,最先适应法,回收：按释放区的首址，查询空闲区表，若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个空闲区，将其大小和首址按照首地址大小递增的顺序插入到空闲区表的适当位置。,.,49,最先适应法的优点,释放某一存储区时，若与空闲区相邻则合并到相邻空闲分区中去，这种情况并不改变该区在表中的位置，只要修改其大小或首址。这种算法是尽可能地利用低地址空间，从而保证高地址空间有较大的空闲区。,.,50,最佳适应法,要求按空闲区大小从小到大的次序组成空闲区表（队列）。分配：当用户作业或进程申请一个存储区时，存储管理程序从表头开始查找，当找到第一个满足要求的空闲区时，停止查找，并且这个空闲区是最佳的空闲区（选中的空闲区是满足要求的最小空闲区）。如果该空闲区大于请求表中的请求长度，则与最先适应法时相同，将减去请求长度后的剩余空闲区部分留在可用表中。,.,51,最佳适应法,回收：按释放区的首址，查询空闲区表（队列），若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个空闲区插入空闲区表（队列）。分配和回收后要对空闲区表（队列）重新排序。,.,52,最佳适应算法的优点,在系统中若存在一个与申请分区大小相等的空闲区，必定会被选中，而最先适应法则不一定。若系统中不存在与申请分区大小相等的空闲区，则选中的空闲区是满足要求的最小空闲区，而不致于毁掉较大的空闲区。,.,53,最佳适应算法的缺点,空闲区的大小一般与申请分区大小不相等，因此将其一分为二，留下来的空闲区一般情况下是很小的，以致无法使用。随着时间的推移，系统中的小空闲区会越来越多，从而造成存储区的大量浪费。,.,54,最坏适应算法,要求空闲区按由大至小递减的顺序组织空闲区表（或队列）。分配：进程申请一个大小为SIZE的存储区时，总是检查空闲区表的第一个空闲区的大小是否大于或等于SIZE。若空闲区小于SIZE，则分配失败；否则从空闲区中分配SIZE的存储区给用户，然后修改和调整空闲区表。,.,55,最坏适应算法,回收：按释放区的首址，查询空闲区表（队列），若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个空闲区插入空闲区表（队列）。分配和回收后要对空闲区表（队列）重新排序。,.,56,最坏适应算法的优点,当程序装入内存中最大的空闲区后，剩下的空闲区还可能相当大，还能装下较大的程序。每次仅作一次查询工作。,.,57,3、动态分区时分区的回收,当某个进程释放某存储区时，系统首先检查释放区是否与系统中的空闲区相邻，若相邻则把释放区合并到相邻的空闲区中去，否则把释放区作为一个空闲区插入到空闲区表的适当位置。,.,58,图5.12空闲区的合并,.,59,空闲区的合并,释放区与上下两空闲区相邻：将三个空闲区合并为一个空闲区。新空闲区的起始地址为上空闲区的起始地址，大小为三个空闲区之和。空闲区合并后，取消可用表或自由链中下空闲区的表目项或链指针，修改上空闲区的对应项。释放区只与上空闲区相邻：将释放区与上空闲区合并为一个空闲区，其起始地址为上空闲区的起始地址，大小为上空闲区与释放区之和。合并后，修改上空闲区对应的可用表的表目项或自由链指针。,.,60,空闲区的合并,释放区与下空闲区相邻：将释放区与下空闲区合并，并将释放区的起始地址作为合并区的起始地址。合并区的长度为释放区与下空闲区之和。合并后修改可用表或自由链中相应的表目项或链指针。释放区不与任何空闲区相邻：释放区作为一个新可用区插入可用表或自由链。,.,61,4、三种分配算法的比较,三种算法的优缺点比较搜索速度：最先适应算法具有最佳性能，最佳适应算法和最坏适应算法都要求把不同大小的空闲区按大小进行排队；回收过程：最先适应算法具有最佳性能，因为最佳适应算法和最坏适应算法都必须重新调整空闲区的位置；空闲区利用：最佳适应法找到的空闲区是最佳的，但是会造成内存碎片较多，影响内存利用率，而最坏适用法的内存碎片最少，但是对内存的请求较多的进程有可能分配失败。总之，三种算法各有所长，针对不同的请求队列，它们的效率和功能是不一样的。,.,62,4、三种分配算法的比较,上述三种放置策略各有利弊，到底哪种最好不能一概而论，而应针对具体作业序列来分析。对于某一作业序列来说，某种算法能将该作业序列中所有作业安置完毕，那么我们说该算法对这一作业序列是合适的。对于某一算法而言，如它不能立即满足某一要求，而其它算法却可以满足此要求，则这一算法对该作业序列是不合适的。,.,63,例题,例1：有作业序列：作业A要求18K；作业B要求25K，作业C要求30K。系统中空闲区按三种算法组成的空闲区队列，现在请你分析哪种算法适合该作业序列？,.,64,例题,最先,分配前内存分配前内存自由链,请求表,.,65,例题,经分析可知：最佳适应法对这个作业序列是合适的，而其它两种对该作业序列是不合适的。因为最先适应算法和最坏适应算法对于作业C来说都不能为它分配所需要的内存空间。,.,66,练习,如果现在作业序列变为以下情况，分析哪种算法适合于这个作业序列？作业A要求21K，作业B要求30K，作业C要求25K。,.,67,5.2.3有关分区管理其他问题的讨论,1、关于虚存的实现2、关于内存扩充3、关于地址变换和内存保护4、分区存储管理的主要优缺点,.,68,1、关于虚存的实现,无法实现那种用户进程所需内存容量只受内存和外存容量之和限制的虚拟存储器。如果不采用内存扩充技术，每个用户进程所需内存容量是受到分区大小限制的。,.,69,2、关于内存扩充,可以使用覆盖或交换技术来扩充内存,.,70,3、关于地址变换和内存保护,静态地址重定位和动态地址重定位技术，都可用来完成分区式内存管理的地址变换。不能使用静态地址重定位的方法来完成动态分区时的地址变换。动态地址重定位中的一对硬件寄存器除了完成动态地址重定位的功能之外，还具有保护内存中数据和程序的功能。保护键法也可用来对内存各分区提供保护。,.,71,4、分区存储管理的主要优缺点,优点：实现了多个作业或进程对内存的共享，提高了系统的资源利用率。该方法要求的硬件支持少，管