第五章-存储管理.

第5章存储管理存储管理的功能5.1.1虚拟存储器内存：速度快，价格昂贵；外存：速度较慢，但价格便宜，适于存放大量信息；CPU所能直接访问的存储器只有内存和处理器内的寄存器。机器指令可以用内存地址作为参数，而不能用磁盘地址作为参数。因此，执行指令以及指令使用的数据必须在这些直接可访问的存储设备上。如果数据不在内存中，那么CPU使用前必须先把数据移到内存中。在一个进程的执行过程中，大部分程序和数据并不经常被访问。存储管理系统把进程中那些不经常被访问的程序段和数据放入外存中，待需要访问时才将它们调入内存。用户程序在执行前，需要经过几个步骤。在这些步骤中，地址有不同的表示形式。源程序中的地址通常用符号来表示（如count）。编译器通常将这些符号地址绑定在可重定位的地址（如“从本模块开始的第14字节”）。链接程序或加载程序再将这些可重定位的地址绑定成绝对地址（如74014）。5.1.1虚拟存储器每个进程都拥有一个空间。每个指令或数据单元都在这个虚拟空间中拥有确定的地址，这个地址称为虚拟地址。虚拟存储器：将进程中的目标代码、数据等的虚拟地址组成的虚拟空间。虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充，使得把程序的一部分装入内存便可运行，用户看起来内存容量比实际内存容量大得多的一种存储器系统。虚拟空间的划分虚拟空间的划分：与计算机系统结构有关图5.2VAX-11虚拟空间的划分5.1.1虚拟存储器图5.1地址变换与物理存储器5.1.1虚拟存储器虚拟存储器到物理存储器的变换是操作系统必须解决的问题。要实现这个变换，必须要有相应的硬件支持。5.1.1虚拟存储器通常，将指令与数据绑定到内存地址有以下几种情况：编译时：如果在编译时就知道进程将在内存中的驻留地址，那么就可以生成绝对代码。如果将来开始地址发生变化，就必须重新编译代码。MS-DOS的.COM格式程序就是在编译时绑定成绝对代码的。加载时：若编译时不知道进程将驻留在内存的什么位置，编译器就必须生成可重定位代码。此时，最后绑定会延迟到加载时才进行。若开始地址发生变化，只需重新加载用户代码。执行时：若进程在执行时可以从一个内存段移到另一个内存段，绑定就必须延迟到执行时才进行。采用这种方案需要特定的硬件，绝大多数通用计算机操作系统采用这种方法。5.1.2地址变换——程序的装入把虚拟空间中已链接和划分好的内容装入内存。将虚拟地址映射为内存地址，称为地址重定位或地址映射。1、绝对装入编译后，装入前已产生了绝对地址（内存地址），装入时不再做地址重定位。绝对地址的产生：（1）由编译器完成，（2）由程序员编程完成。对（1）而言，编程用符号地址。5.1.2地址变换——程序的装入2、静态地址重定位是在虚拟空间程序执行之前由装配程序完成，主要工作是对相对地址中的指令和数据地址的调整过程优缺点：不需要硬件支持，无法实现虚拟存储器，必须占用连续的内存3.动态地址重定位是在程序执行过程中，在CPU访问内存之前，将要访问的程序或数据地址转换成内存地址。优点：可以对内存进行非连续分配，可实现虚拟存储器，有利于程序段的共享缺点：需要硬件支持5.1.2地址变换地址重定位机构需要一个（或多个）基地址寄存器BR和一个（或多个）程序虚拟地址寄存器VR。指令或数据的内存地址MA与虚拟地址的关系为：MA=(BR)+(VR)。其中(BR)和(VR)分别表示寄存器BR与VR中的内容。动态重定位的过程：设置基地址寄存器BR，虚拟地址寄存器VR；将程序段装入内存，且将其占用的内存区首地址送BR中。例如(BR)＝1000.在程序执行过程中，将所要访问的虚拟地址送入VR中。例如执行LOADA500语句时，将所要访问的虚拟地址500放入VR中。地址变换机构把VR和BR的内容相加，得到实际访问的物理地址。5.1.2地址变换图5.3动态地址重定位5.1.2地址变换动态重定位的优点：可以对内存进行非连续分配。对于同一进程的各分散程序段，只要把各程序段在内存中的首地址统一存放在不同的BR中，则可以由地址变换机构变换得到正确的内存地址。提供了实现虚拟存储器的基础。可以在进程执行时部分地、动态地分配内存。有利于程序段的共享。5.1.4内存的分配与回收设计内存分配和回收方法时需考虑因素分配结构：登记内存使用情况，供分配程序使用的表格与链表。例如内存空闲区表、空闲区队列等。放置策略：确定调入内存的程序和数据在内存中的位置。这是一种选择内存空闲区的策略。交换策略：在需要将某个程序段和数据调入内存时，如果内存中没有足够的空闲区，由交换策略来确定把内存中的哪些程序段和数据段调出内存，以便腾出足够的空间。调入策略：外存中的程序段和数据段什么时间、按照何种控制方式进入内存。回收策略：回收策略包括两点，一是回收的时机，二是对所回收的内存空闲区和已存在的内存空闲区的调整。5.2分区存储管理5.2.1分区存储管理的基本原理把内存划分为若干个大小不等的区域，除操作系统占用一个区域之外，其余由多道环境下的各并发进程共享。固定分区法：把内存区固定划分为若干个大小不等的区域。划分原则一般由系统操作员或操作系统决定。例如可划分为长分区和短分区。分区一旦划分结束，在整个执行过程中每个分区的长度和内存的总分区个数将保持不变。动态分区法：在程序执行前并不建立分区，在进程执行过程中建立分区，且其大小可随进程对内存的要求而改变，提高了内存利用率。1.固定分区法特点：有n个分区，则可同时装入n个进程。系统对内存的管理和控制通过数据结构——分区说明表进行。分区说明表说明各分区号、分区大小、起始地址和是否空闲。内存的分配释放、存储保护及地址变换都利用了分区说明表。1.固定分区法图5.6固定分区法2.动态分区法系统启动时，除了操作系统中常驻内存部分之外，只有一个空闲分区。随后，分配程序将该区依次划分给调度选中的作业或进程。采用FIFO调度时的内存初始分配情况。2.动态分区法采用最先适应算法分配内存时的内存分配变化过程。2.动态分区法也使用分区说明表等数据结构对内存进行管理。除了分区说明表，还把内存中的可用分区单独构成可用分区表或可用分区自由链，来描述系统内的内存资源。可用分区表的每个表目记录一个空闲区，主要参数包括区号、长度和起始地址。采用表格结构，管理过程比较简单，但表的大小难以确定，可用表要占用一部分内存。可用分区自由链是利用每个内存空间区的头几个单元存放本空间区的大小及下个空闲区的起始地址，把所有的空闲区链接起来。然后，系统再设置一自由链首指针让其指向第一个空闲区。管理程序可通过链首指针查到所有的空闲区。采用自由链法管理空闲区，查找时要比可用表困难。但自由链指针利用了空闲区自身的单元，不必占用额外的内存区。请求内存资源的进程也构成一个内存资源请求表。请求表的每个表目描述请求内存资源的进程号以及所请求的内存大小。2.动态分区法图5.9可用表、自由链及请求表5.2.2分区的分配与回收1.固定分区时的分配与回收当用户程序要装入执行时，通过请求表提出内存分配要求和所要求的内存空间大小。存储管理程序根据请求表查询分区说明表，从中找出一个满足要求的空间分区，并将其分配给申请者。当进程执行完毕，不再需要内存资源时，管理程序将对应的分区状态置为未使用即可。2.动态分区时的分配与回收对于请求表中的要求内存长度，从可用表或自由链中寻找出合适的空间区分配给进程。分配空闲区之后，更新可用表或自由链。进程释放内存资源时，和相邻的空闲区进行链接合并，更新可用表或自由链。从可用表或自由链中寻找空闲区的常用方法有3种。最先适应法最佳适应法最坏适应法2.动态分区时的分配与回收最先适应法要求可用表或自由链按起始地址递增的次序排列。该算法的最大特点是一旦找到大于或等于所要求内存长度的分区，则结束探索。然后，该算法从所找到的分区中划出所要求的内存长度分配给用户，并把余下的部分进行合并(如果有相邻空闲区在)后留在可用表中，但要修改其相应的表项。2.动态分区时的分配与回收最佳适应算法要求按照从小到大的次序组成空闲区可用表或自由链。当用户进程申请一个空闲区时，存储管理程序从表头开始查找，当找到第一个满足要求的空间区时，停止查找。如果该空闲区大于请求表中的请求长度，则与最先适应法时相同，将减去请求长度后的剩余空闲区部分留在可用表中。最坏适应算法要求按大小递减的顺序组成空闲区可用表或自由链。当用户进程申请一个空闲区时，先检查空间区可用表或自由链的第一个空间可用区的大小是否大于或等于所要求的内存长度，若可用表或自由链的第一个项长度小于所要求的，则分配失败。否则从空闲区可用表或自由链中分配相应的存储空间给用户，然后修改和调整空闲区可用表或自由链。3.动态分区时的回收与拼接当用户进程执行结束时，存储管理程序要收回已使用完毕的空闲区，并将其插入空闲区可用表或自由链。空闲区回收时或在内存分配时，要进行空闲区拼接，以把不连续的零散空闲区集中起来。图5.12空闲区的合并4.几种分配算法的比较最先适应算法FF。要求：分区按低址――高址链接特点：找到第一个大小满足的分区，划分。低址内存使用频繁。最佳适应算法分区按大小递增排序；分区释放时需插入到适当位置。最坏适应算法分区按大小递减排序；分区释放时需插入到适当位置。4.几种分配算法的比较可从查找速度、释放速度及空闲区的利用这3个方面对算法进行比较。从搜索速度上看，最先适应算法具有最佳性能。最佳适应算法或最坏适应算法看上去能很快地找到一个最适合的或最大的空闲区，但都要求首先把不同大小的空闲区按其大小进行排队。这实际上是对所有空闲区进行一次搜索。从回收过程来看，最先适应算法也是最佳的。因为无论被释放区是否与空闲区相邻，都不用改变该区在可用表或自由链中的位置，只需修改其大小或起始地址。而最佳适应算法和最坏适应算法都必须重新调整该区的位置。最先适应算法的另一个优点就是尽可能地利用了低地址空间，从而保证高地址有较大的空闲区来放置要求内存较多的进程。4.几种分配算法的比较反过来，最佳适应法找到的空闲区是最佳的，也就是说，用最佳适应法找到的空闲区或是正好等于用户请求的大小，或是能满足用户要求的最小空闲区。不过，尽管最佳适应法能选出最适合用户要求的可用空间区，但这样做在某些情况下并不一定能提高内存的利用率。例如，当用户请求小于最小空间区不太多时，分配程序会将其分配后的剩余部分作为一个新的小空间区留在可用表或自由链中。这种小空闲区有可能永远得不到再利用(除非与别的空闲区合并)，而且也会增加内存分配和回收时的查找负担。最坏适应算法正是基于不留下碎片空闲区这一出发点的。它选择最大的空闲区来满足用户要求，以期分配后的剩余部分仍能进行再分配。如果内存不够怎么办？程序占用空间太大了，，，运行的进程太多了，分给每个进程的不够用，，5.3覆盖与交换技术5.3.1覆盖技术把程序划分为若干个功能上相对独立的程序段，按照程序的逻辑结构让那些不会同时执行的程序段共享同一块内存区。通常，这些程序段都被保存在外存中，当有关程序段之前的程序段已经执行结束后，再把后续程序段调入内存覆盖前面的程序段。要求程序员提供一个清楚的覆盖结构。即程序员必须完成把一个程序划分成不同的程序段，并规定好它们的执行和覆盖顺序的工作。操作系统根据程序员提供的覆盖结构来完成程序段之间的覆盖。要求程序员既要清楚了解程序所属进程的虚拟空间及各程序段所在虚拟空间的位置，又要求程序员懂得系统和内存的内部结构与地址划分，因此，程序员负担较重。5.3.2交换技术5.3.2交换技术将阻塞进程，暂时不用的程序、数据换出，将具备运行条件的进程换入。类型：整体交换：进程交换，解决内存紧张部分交换：页面交换/分段交换：提供虚存支持换出与换入换出•选出被换出进程：优先级，驻留时间，进程状态•换出过程：对于共享段：计数减1，是0则换出，否则不换修改PCB和MCB（或内存分配表）