搜索
1第四章存储器管理存储器是计算机系统的重要组成部分。目前，存储器仍然是一种宝贵资源。如何对它有效管理不仅影响到存储器的利用率而且还对系统性能有重大影响。存储器管理的主要对象是内存。理想存储器：速度快；容量大；价格低。但目前无法同时满足这三个条件。24.1.1多级存储结构存储器的功能是保存数据，存储器的发展方向是高速、大容量和小体积。存储组织是指在存储技术和CPU寻址技术许可的范围内组织合理的存储结构。其依据是访问速度匹配关系、容量要求和价格寄存器-内存-外存结构寄存器-缓存-内存-外存结构微机中的存储层次组织：访问速度越慢，容量越大，价格越便宜最佳状态应是各层次的存储器都处于均衡的繁忙状态（如：缓存命中率正好使主存读写保持繁忙）4.1存储器的层次结构3存储器的层次结构存储器在信息处理中占据重要位置。但是在现有技术下，任何一种存储装置，都无法同时从速度与容量两方面，满足用户的需求。实际上它们组成了一个速度由快到慢，容量由小到大的存储装置层次。书P116图4-1存储层次示意44.1.2.主存储器与寄存器主存储器：主存储器(简称内存或主存)，用于保存进程运行时的程序和数据，也称可执行存储器。其容量从数十MB到数GB。CPU的控制部件只能从主存中取得指令和数据：数据从主存读取并将它们装入到寄存器中,或从寄存器存入到主存。由于主存的访问速度远低于CPU执行指令速度,为缓和这一矛盾引入寄存器和高速缓存。寄存器：CPU内部，访问速度最快，完全能与CPU协调工作，但价格十分昂贵，因此容量不可能做得很大。一般以字(word)为单位。寄存器的数目，对于当前的微机系统和大中型机，可能有几十个甚至上百个。54.1.3高速缓存和磁盘缓存高速缓存Cache(10-100ns)容量大于或远大于寄存器，而比主存约小两到三个数量级，从几十KB到几MB；其访问速度快于主存,为缓和内存和CPU速度上的矛盾而产生。进程的程序和数据通常是存放在主存中，当使用时被临时复制到一个速度较快的高速缓存中。当CPU访问一组特定信息时，首先检查它是否在高速缓存中,如果已存在，可直接从中读出以避免访问主存，否则再从主存中读出信息。如大多数计算机有指令高速缓存，用来暂存下一条要执行指令，若没有指令高速缓存，CPU将空等若干个周期，直到下一条指令从主存中取出。6磁盘缓存：并不是一种实际存在的存储介质，是主存的一部分。即利用主存中的存储空间，来暂存从磁盘中读出或写入的信息。由于目前磁盘的I/O速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。由操作系统协调这些存储器的使用一个文件的数据可能出现在存储器层次的不同级别中：先存放在辅存中（如硬盘）；当需要运行或被访问时，就必须调入主存，也可以暂存在磁盘缓存中。74.2程序的装入和链接8图4-2对用户程序的处理步骤程序在成为进程之前的准备工作编辑：形成源文件（符号地址）编译：形成目标模块（模块内符号地址解析）链接：由多个目标模块或函数库生成可执行文件。（模块间的符号地址解析）装入：构造PCB，形成进程（使用物理地址）,完成装入模块中的逻辑地址到物理地址的映射。94.2.1程序的装入1.绝对装入方式编译时就知道程序将驻留内存的位置源文件（符号地址）目标文件中的数字地址是物理地址编译装入程序按照装入模块中的地址，将程序和数据装入内存。装入后由于程序中的逻辑地址与实际内存地址完全相同，故不须对程序和数据的地址进行修改。10程序中使用的绝对地址，可在编译或汇编时给出,也可由程序员直接赋予。但要求程序员熟悉内存使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。优点：装入过程简单缺点：只能将目标模块装入到内存中事先指定的位置。在多道程序环境下，编译程序不可能预知所编译的目标模块应放在内存的何处，因此只适用于单道程序环境。过多依赖于硬件结构，不适于多道程序。112.可重定位装入方式(静态）在多道程序环境下，所得到的目标模块的起始地址通常是从0开始的，程序中的其它地址也都是相对于起始地址计算的。此时应采用可重定位装入方式，根据内存的当前情况，将装入模块装入到内存的适当位置。把在装入时对目标模块中的指令和数据的地址的修改过程称为重定位。又因为地址变换是在装入时一次完成的，以后不再改变，故称为静态重定位。12图4-3作业装入内存时的情况目标模块中的数字地址是逻辑地址，在装入时将其转换为物理地址。并且地址变换是一次完成的，之后不再改变。优点：可将装入模块装入到内存中任何允许的位置，故可用于多道程序环境。可以装入有限的多道程序，不需要硬件的支持。缺点：常占用连续的内存空间，程序装入后不能移动，不易实现共享。133.动态运行时装入方式-动态可重定位动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。优点：可以移动，有利于实现共享，是虚拟存储实现的基础。144.2.2程序的链接1.静态链接方式源程序经过编译后，可得到一组目标模块，再利用链接程序将这组目标模块链接，形成装入模块。根据链接时间不同，可分为三种：在程序运行之前，先将各目标模块及所需的库函数，链接成一个完整的装入模块，以后不再拆开。这种事先进行链接的方式称为静态链接。15（1）对相对地址进行修改。（2）将每个模块中所有的外部调用符号也都变换为相对地址。162.装入时动态链接装入时动态链接方式有以下优点：(1)便于修改和更新某个目标模块。(2)便于实现对目标模块的共享。源程序经编译后所得的目标模块，是在装入内存时边装入边链接的，即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，还要按照上图的方式修改目标模块中的相对地址。173.运行时动态链接将对某些模块的链接推迟到执行时才链接，即在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，并把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。184.3连续分配连续分配方式，是指为一个用户程序分配一个连续的内存空间。可分为：单一连续分配固定分区分配动态分区分配动态重定位分区分配194.3.1单一连续分配方式在单道环境下，不管是单用户系统还是单道批处理系统，进程（作业）执行时除了系统占用一部分主存外，剩下的主存区域全部归它占用。主存可以划分为三部分：系统区、用户区、空闲区。用户区是一个连续的存储区，所以又称单一连续区存储管理。单用户系统在一段时间内，只有一个进程在内存，故内存分配管理十分简单，内存利用率低。内存分为两个区域，一个供操作系统使用，一个供用户使用。20用户程序位于RAM中的操作系统0xFFF...0位于RAM中的操作系统用户程序0单一连续区存储分配示意图21工作流程单一连续区分配采用静态分配和静态重定位方式，亦即作业或进程一旦进入主存，就一直等到它运行结束后才能释放主存。如下图所示的主存分配与回收法。并且由装入程序检查其绝对地址是否超越，即可达到保护系统的目的。22工作流程(续)23单用户系统缺点不支持多道。主存利用率不高程序全部装入，很少使用的程序部分也占用主存。程序的运行受主存容量限制。244.3.2固定分区分配是最简单的一种可运行多道程序的存储管理方式。把内存分为一些大小相等或不等的分区，在每个分区中只装入一道作业，这样，把用户空间划分成为几个分区，便允许有几道作业并发运行。操作系统只占用其中一个分区。适用于多道程序系统和分时系统，支持多个程序并发执行，但难以进行内存分区的共享。25预先把可分配的主存空间分割成若干个连续区域，称为一个分区。每个分区的大小可以相同也可以不同，如图所示。但分区大小固定不变，每个分区装一个且只能装一个作业。存储分配：如果有一个空闲区,则分配给某个作业。1.划分分区的方法26分区4分区3分区2分区1操作系统多个等待队列单个等待队列分区4分区3分区2分区1操作系统固定分区示意图272.内存分配管理固定分区使用表设置内存分配表20283固定分区分配优缺点优点：易于实现，开销小。缺点：内部碎片造成浪费，分区总数固定，限制了并发执行的程序数目。294.3.3动态分区分配（可变分区分配）根据进程的实际需要，动态地为之分配内存空间。在实现可变分区分配时，将涉及三个问题：分区分配中所用的数据结构、分区分配算法、分区的分配与回收基本思想：内存不是预先划分好的，而是当作业装入时，根据作业需求和内存空间使用情况来决定是否分配内存：设置内存空闲块表—记录了空闲区起始地址和长度分区分配：动态分配分区回收：当某一块归还后，前后空间合并，修改内存空闲块表303132331.分区分配中的数据结构(1)空闲分区表(2)空闲分区链书P123图4-6空闲链结构340K15K38K48K68K80K110K120K空闲区表已分配分区表始址长度标志15K23K未分配48K20K未分配80K30K未分配始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ4分区分配表：分区分配表350K15K38K48K68K80K110K120K空闲区表已分配区表始址长度标志15K23K未分配48K20K未分配98K12K未分配始址长度标志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98K362.分区分配操作1)分配内存（系统利用某种分配算法从空闲分区链或表中找到所需大小的分区的过程）图4-7内存分配流程空闲分区大小为m.size请求分区大小为u.sizesize是事先规定的不再切割的剩余分区的大小372)回收内存（当进程运行完毕释放内存时，系统根据回收区的首址，从空闲分区链或表中找到相应的插入点，将回收区插入到空闲分区链或表中适当位置。(1)回收区与插入点的前一个空闲分区F1相邻接(2)回收区与插入点的后一空闲分区F2相邻接(3)回收区与插入点的前、后两个分区相邻接(4)回收区既不与F1邻接，又不与F2邻接。以上四种情况处理见书P125383.可变分区分配算法为把一个新作业装入内存，须按照一定的分配算法，从空闲分区链或表中选出一分区分配给该作业。动态内存分配有以下四种算法：首次适应法下次适应法（循环首次适应法）最佳适应法最坏适应法39分配：当进程申请大小为SIZE的内存时，系统从空闲区表的第一个表目开始查询，直到首次找到等于或大于SIZE的空闲区。从该区中划出大小为SIZE的分区分配给进程，余下的部分仍作为一个空闲区留在空闲分区链中，但要修改其首址和大小。回收：按释放区的首址，查询空闲分区链，若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个新的空闲区，将其大小和首址按照首地址大小递增的顺序插入到空闲分区链中的适当位置。要求空闲分区按首址递增的次序组织空闲分区链或表。首次适应法40分析注意：每次分配和回收后空闲分区链表都要按首址递增的次序排列。首次适应法的优点：释放某一存储区时，若与空闲区相邻则合并到相邻空闲分区中去，这种情况并不改变该区在表中的位置，只要修改其大小或首址。这种算法是尽可能地利用低地址空间，从而保证高地址空间有较大的空闲区。首次适应法的缺点：低址部分不断被划分，会留下许多难以利用的，很小的空闲分区称为碎片。每次查找都是从低址部分开始，增加了查找时的开销。41下次适应法（循环首次适应法）类似首次适应法。每次分区时，总是从上次查找结束的地方开始，找到一个足够大的空白区分配。为实现该算法应设置一个起始查寻指针，用于下一次起始查寻的空闲分区，并采用循环查找方式，即如果链尾空闲分区的大小仍不能满足要是，则应返回到第一个空闲分区进行查寻。找到