第4章_内存管理

第4章内存管理4.1内存管理功能4.2分区管理4.3页式管理4.4段式管理4.5段页式管理4.1内存管理的功能●内存空间的分配和回收●地址转换●内存空间的共享和保护●内存空间的逻辑扩充4.1.1内存的分配与回收内存分配按分配时机的不同，可分为三种方式：1.直接分配采用物理内存地址编写程序。使用这种方式，必须事先划定内存的使用空间，因此，内存利用率不高，用户使用较困难。2.静态分配在作业运行之前各目标模块连接后，把整个作业一次性全部装入内存，并在作业的整个运行过程中，不允许作业再申请其他内存，或在内存中移动位置。也就是说，内存分配是在作业运行前一次性完成的。4.1.1内存的分配与回收3.动态分配作业要求的基本内存空间是在目标模块装入内存时分配的，但在作业运行过程中，允许作业申请附加的内存空间，或是在内存中移动，即分配工作可以在作业运行前及运行过程中逐步完成。4.1.2地址转换把用户程序装入内存时对有关指令的地址部分的修改定义为从程序地址到内存地址的地址转换，或称为地址重定位。1.物理地址与逻辑地址物理地址也称内存地址，它是用于唯一标识一个内存单元的编号。所有的物理地址构成了物理空间。4.1.2地址转换逻辑地址也称程序地址，它是指在源程序经过汇编或编译后形成的目标代码中，用于反映目标代码中指令或数据的相对位置关系的地址。逻辑地址都是以“0”为基址顺序进行编址的，这样生成的目标程序占据一定的地址空间，称为程序的逻辑地址空间，简称逻辑空间。用符号地址（符号名）表示的程序空间称为名空间。地址重定位的原因是什么?因为程序在装入内存后，其逻辑地址和物理地址不一致。地址映射LoadA2003456。。1200物理地址空间LoadAdata1data13456源程序LoadA20034560100200编译连接逻辑地址空间BA=1000（名空间）●静态重定位是在程序执行之前由操作系统的连接装入程序完成地址转换。优点：不需要硬件的支持。缺点：程序必须占用连续的内存空间；一旦程序装入后不能移动。2.地址重定位的方式●动态重定位在程序执行期间进行的地址转换，是由专门的硬件机构来完成的。优点：程序占用的内存空间是动态可变的，当程序从某个存储区移到另一个区域时，只需要修改相应的寄存器BR的内容即可。缺点：需要硬件的支持；实现存储管理的软件算法较为复杂。03456......LOADA200......0100200300.........LOADA2003456110012001300200VR+1000BR动态重定位示意图4.1.3内存的共享和保护内存空间的共享：在多道程序设计系统中，同时进入主存执行的作业可能需要调用相同的程序或数据，这就是内存的共享。例如，调用编译程序进行编译，把这个编译程序存放在某个区域中，各作业要调用时就访问这个区域，因此这个区域就是共享的。同样也可以实现公共数据的共享。4.1.3内存的共享和保护在实现内存分配与共享时，必须解决内存中信息的保护问题。存储保护的工作一般由硬件和软件配合实现。1.上、下界存储保护：系统可为每个作业设置一对上、下界寄存器，分别用来存放当前运行作业在内存空间的上、下边界地址，用它们来限制用户程序的活动范围。2.基址－限长存储保护：上、下界保护的一个变种是采用基址—限长存储保护。4.1.3内存的保护4.1.4内存空间的逻辑扩充对内存进行逻辑上的扩充，现在普遍采用覆盖、交换和虚拟存储器技术。虚拟存储器是具有请求调入功能和置换功能，能仅把作业的一部分装入内存便可运行作业的存储器系统，它是一种能从逻辑上对内存容量进行扩充的虚构的存储器系统。虚拟存储器的理论基础是程序的局部性原理。包括时间局部性和空间局部性。什么是时间局部性?什么是空间局部性?4.1.4内存空间的逻辑扩充虚拟存储器的基本思想是把有限的内存空间与大容量的外存统一管理，构成一个远大于实际内存的、虚拟的存储器。此时，外存是作为内存的直接延伸，用户并不会感觉到内、外存的区别，即把两级存储器当作一级存储器来看待。一个作业运行时，其全部信息装入虚存，实际上可能只有当前运行的必需一部分信息存入内存，其他则存于外存，当所访问的信息不在内存时，系统自动将其从外存调入内存。4.2.1单分区管理4.2.2固定分区4.2.3可变分区4.2.4覆盖与交换4.2分区管理4.2.1单分区管理这是一种最简单的连续存储管理方式。但只能用于单用户、单任务的操作系统中。●系统区：仅提供给操作系统使用，通常设置在内存的低址部分；●用户区：指除系统区以外的全部内存空间，提供给用户使用。●空闲区：指剩余部分存储区。4.2.2固定分区把可用空间划分成若干个固定大小的存储区，除操作系统占用一个区域外，其余区域为系统中多个用户共享，因为在系统运行期间，分区大小、数目都不变，所以固定分区也称为静态分区。分区说明表4.2.3可变分区1、基本思想：分区大小、数目可变，所以可变分区也称为动态分区。它是根据用户作业的大小，在作业要求装入主存时，动态地划分分区，使分区的大小正好适应作业的要求。可变分区存储管理方式必须解决三个问题：一是分区分配中所用的数据结构；二是分区的分配算法；三是分区的分配和回收。可变分区内存使用情况示意图2．可变分区管理中的数据结构●最先适应算法按空闲区地址递增的次序分配●最优适应算法按空闲区由小到大的次序分配●最坏适应算法按空闲区由大到小的次序分配3．内存的分配算法（1）最先适应分配算法（FF）它要求空闲分区表中的记录按地址递增的顺序排列。在每次分配主存时，总是从第1条记录开始顺序查找空闲分区表，找到第一个能满足作业长度要求的空闲区，分割这个空闲区。一部分分配给作业，另一部分仍作为空闲区。特点是算法简单，容易产生过多的主存碎片。主存碎片是指小的不能使用的主存空间；这种算法把大的空闲区分成了小的空闲区，当有大作业要求分配时，不能满足要求，降低了系统的效率。（2）最优适应分配算法（BF）它是从所有的空闲分区中挑选一个能满足作业要求的最小空闲区进行分配。这样可以保证不去分割一个更大的空闲区，使装入大作业时比较容易得到满足。为实现这种算法，把空闲区按长度递增次序登记在空闲分区表中，分配时，顺序查找。它的优点是解决了大作业的分配问题，不足是容易产生主存碎片，降低了主存空间的利用率。另外收回主存时，要按长度递增顺序插入到空闲分区表中，增加了系统开销。（3）最坏适应分配算法（WF）它每次分配主存时总是挑选一个最大的空闲区，分割一部分给作业使用，使剩下的部分不至于太小而成为主存碎片。为实现这种算法，把空闲区按长度递减的次序登记在空闲分区表中，分配时，顺序查找。它的优点是不会产生过多的碎片。不影响大作业的分配。另外收回主存时，要按长度递减的顺序插入到空闲分区表中，增加了系统开销。有作业序列：作业A要求18K；作业B要求25K，作业C要求30K。如下图。系统中空闲区按三种算法组成的空闲区队列如下，经分析可知：最佳适应法对这个作业序列是合适的，而其它两种对该作业序列是不合适的。举例有作业序列：作业A要求21K；作业B要求30K，作业C要求25K，分析使用哪种分配算法最佳？课堂练习：4．内存的回收当某一个用户作业完成释放所占分区时，系统应进行回收。在可变式分区中，应该检查回收区与内存中前后空闲区是否相邻：若相邻，则应进行合并，形成一个较大的空闲区，并对相应的链表指针进行修改；若不相邻，应将空闲区插入到空闲区链表的适当位置。回收的分区前后没有相邻的空闲分区。回收分区的前面有相邻的空闲分区。回收分区的后面有相邻的空闲分区。回收分区的前后都有相邻的空闲分区。5、分区保护存储保护是为了防止一个作业破坏操作系统或其他作业。1.上、下界寄存器保护法：上界寄存器≤物理地址≤下界寄存器，超出这个范围便产生保护性中断。2.基址、限长寄存器保护法：基址寄存器≤物理地址≤基址寄存器+限长寄存器，如果超过了限长，则发出越界中断信号，并停止作业的运行。3.存储保护键方法：系统为每个分区设一个保护键，在程序状态字中也设同样的保护键字段，访问内存时检查键的配对情况，如果不匹配则产生保护性中断。4.2.4碎片问题及其解决办法在分区分配方式中经过不断地分配和释放后，内存中空闲分区会变得越来越多和越来越小，产生了许多碎片。所谓碎片是指内存中出现的一些零散的小空闲区域。由于碎片都很小，故无法再利用。如果内存中碎片很多，将会造成严重的存储资源浪费。4.2.4碎片问题及其解决办法移动(紧凑/紧缩/拼接)技术：解决碎片的方法是移动所有的占用区域，使所有的空闲区合并成一片连续区域，这一技术称为移动技术（拼接）。移动技术可解决碎片问题，从而提高内存的利用率。移动技术可以集中分散的空闲区，便于作业动态扩充内存。4.2.5覆盖与交换覆盖：一个作业的若干程序段，或几个作业的某些部分共享某一个存储空间。程序段先保存在磁盘上，当有关程序段的前一部分执行结束，把后续程序段调入内存，覆盖前面的程序段。一般要求作业各模块之间有明确的调用结构，程序员要向系统指明覆盖结构，然后由操作系统完成自动覆盖。A8KE4KF10KC10KB8KD12K作业X的调用结构作业X的常驻区A（8K）覆盖区0（10K）覆盖区1（12K）BCDEF为什么引入交换技术？当内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域，这种技术是进程在内存与外存之间的动态调度。多用于分时系统中。2.交换与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构。交换与覆盖的不同之处：•交换发生在进程或作业之间，而覆盖发生在同一进程或作业内。•覆盖只能覆盖那些与覆盖段无关的程序段。2.交换4.3页式管理4.3.1页式管理概述1.基本原理：分页存储管理是将一个进程的地址空间划分成若干个大小相等的区域，称为页。相应地，将内存空间划分成与页相同大小的若干个物理块，称为块或页帧。在为进程分配内存时，将进程中若干页分别装入多个不相邻接的块中。4.3.1页式管理概述2.地址结构：分页系统的地址结构由两部分组成：前一部分为页号P；后一部分为位移量W，即页内位移。在下图中地址为32位，其中0～11位为页内位移（每页的大小为4K），12～31位为页号，所以允许地址空间的大小最多为1M个页。地址结构示例3112110页号P位移量W4.3.2静态分页基本思想是必须装入作业的全部页面后才能执行该作业。1.页表：系统为每个进程建立了一张页面映射表，简称页表。每个页在页表中占一个表项，记录该页在内存中对应的物理块号。进程在执行时，通过查找页表，就可以找到每页所对应的物理块号。页表的作用是实现从页号到物理块号的地址映射。页号块号021328页表用户程序0页1页2页3页4页5页…n页页表页号块号02132638495……内存012345678910地址空间物理空间4.3.2静态分页2.静态页式管理的分配与回收：内存空间以块为单位，要用数据结构记录内存中块的情况。1、位示图：每一位对应一个块，0空闲，1已分配。2、空闲块链：所有空闲块组成一个空闲块链，链首分配，链尾回收。3、内存分块表：表项包括块号，进程号，页号，状态等。状态为0，空闲，1，已分配。4.3.2静态分页3.地址转换：当进程要访问某个逻辑地址M中的数据时，需做如下地址变换：1、将地址空间的逻辑地址M转换为页式逻辑地址；2、以页号P为索引去检索页表，找到相对应表项＝页表始址＋页号P；从中读出对应的物理块号B；3、计算物理地址＝B×页长＋页内位移W。求出有效地址2044所对应的物理地址，要求写出地址转换过程。页式逻辑地址：页号：2044/1024=1，页内位移量：2044MOD1024=1020物理地址：5*1024+1020=6140在采用页面存储管理的系统中，某作业的逻辑地址空间为4页（每页1k），且已知该作业的页表如下：页号块号07152339分页中的地址转换机构页表始址页表长度页表寄存器页号P页内地址W页式逻辑地址越界中断块号p’块内地址W物理地址页表页号块号页号P块号p’＋①①②③4.引入快表的