第4章存储器管理

计算机操作系统第四章存储器管理本章内容4.1存储器的层次结构4.2程序的装入和链接4.3连续分配方式4.4对换4.5分页存储管理方式4.6分段存储管理方式4.1存储器的层次结构4.1.1多级存储器结构4.1.2主存储器与寄存器1．主存储器主存储器(简称内存或主存)是计算机系统中一个主要部件，用于保存进程运行时的程序和数据，也称可执行存储器CPU的控制部件只能从主存储器中取得指令和数据，数据能够从主存储器读取并将它们装入到寄存器中，或者相反主存储器的访问速度远低于CPU执行指令的速度，引入寄存器和高速缓存。2．寄存器寄存器访问速度最快，完全能与CPU协调工作，但价格却十分昂贵，因此容量不可能做得很大寄存器用于加速存储器的访问速度，如用寄存器存放操作数，或用作地址寄存器加快地址转换速度等4.1.2主存储器与寄存器4.1.3高速缓存和磁盘缓存1．高速缓存高速缓存是现代计算机结构中的一个重要部件，其容量大于或远大于寄存器，而比内存约小两到三个数量级左右。1．高速缓存（续）根据程序执行的局部性原理，将主存中一些经常访问的信息存放在高速缓存中，减少访问主存储器的次数，可大幅度提高程序执行速度。进程的程序和数据是存放在主存储器中，每当使用时，被临时复制到一个速度较快的高速缓存中。当CPU访问一组特定信息时，首先检查它是否在高速缓存中，如果已存在，可直接从中取出使用，以避免访问主存，否则，再从主存中读出信息。2．磁盘缓存由于目前磁盘的I/O速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。磁盘缓存本身并不是一种实际存在的存储介质，它依托于固定磁盘，提供对主存储器存储空间的扩充，即利用主存中的存储空间，来暂存从磁盘中读出(或写入)的信息。主存也可以看做是辅存的高速缓存。一个文件的数据可能出现在存储器层次的不同级别中，例如，一个文件数据通常被存储在辅存中(如硬盘)，当其需要运行或被访问时，就必须调入主存，也可以暂时存放在主存的磁盘高速缓存中。大容量的辅存常常使用磁盘，磁盘数据经常备份到磁带或可移动磁盘组上，以防止硬盘故障时丢失数据。2．磁盘缓存（续）本章内容4.1存储器的层次结构4.2程序的装入和链接4.3连续分配方式4.4对换4.5分页存储管理方式4.6分段存储管理方式4.2程序的装入和链接如何将一个用户源程序变成一个可在内存中执行的程序，通常要经过3步骤：1.编译2.链接3.装入图4-2对用户程序的处理步骤编译:由编译程序（Compiler）将用户源代码编译成若个目标模块图4-2对用户程序的处理步骤链接:由链接程序（Linker）将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块图4-2对用户程序的处理步骤装入:由装入程序（Loader）将装入模块装入内存。4.2.1程序的装入在将一个装入模块装入内存时，可以有绝对装入方式、可重定位装入方式、动态运行时装入方式。1．绝对装入方式如果知道程序将驻留在内存的什么位置，那么，编译程序将产生绝对地址的目标代码。绝对装入程序按照装入模块中的地址，将程序和数据装入内存。装入模块被装入内存后，由于程序中的逻辑地址与实际内存地址完全相同，故不需对程序和数据的地址进行修改。为了便于程序的修改,对编译的程序采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。只适合单道程序环境。1．绝对装入方式2．可重定位装入方式目标模块的起始地址通常是从0开始的，程序中的其它地址也都是相对于起始地址计算的。由装入程序将装入模块装入内存后，装入模块中程序所访问的所有逻辑地址与实际装入内存的物理地址不同，必须进行变换。4.2.1程序的装入示例：作业装入内存时的情况2．可重定位装入方式（续）把在装入时对目标程序中指令和数据的变换过程称为重定位。因为地址变换是在装入时一次完成的，以后不再改变，故称为静态重定位。采用静态重定位方法将程序装入内存,称为可重定位装入方式。3．动态运行时装入方式装入程序将目标模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序执行时进行，在硬件地址变换机构的支持下，随着对每条指令或数据的访问自动进行地址变换，故称为动态重定位。•采用动态重定位方法将程序装入内存，称为动态运行时装入方式。4.2.2程序的链接★源程序经过编译后，可得到一组目标模块，再利用链接程序将这组目标模块链接形成装入模块。根据链接时间的不同，可把链接分成如下三种：1、静态链接方式在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块（又称执行模块），以后不再拆开。我们把这种事先进行链接的方式称为静态链接方式。B的起始地址变为L，C的起始地址变为L+M图4-4程序链接示意图（1）对相对地址进行修改由编译程序产生的所有目标模块中，使用的都是相对地址，其起始地址都为0，在链接成一个装入模块时修改模块的相对地址。即把原B中的所有相对地址都加上L，把原C中所有相对地址都加上L＋M。（2）变换外部调用符号将每个模块中所用的外部调用符号也都变换为相对地址。例如将callB变换为JSR“L”1、静态链接方式（续）2、装入时动态链接是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存。2、装入时动态链接装入时动态链接方式有以下优点：（1）便于修改和更新采用动态链接方式，由于各目标模块是分开存放的，所以要修改或更新各目标模块，是件非常容易的事。（2）便于实现对目标模块的共享在采用静态链接方式时，每个应用模块都必须含有其目标模块的拷贝，无法实现对目标模块的共享。但采用装入时动态链接方式时，OS则很容易将一个目标模块链接到几个应用模块上，实现多个应用程序对该模块的共享。这是指对某些目标模块的链接，是在程序执行中需要该目标模块时，由OS去找到该模块并将之装入内存并把它链接到调用者模块上。优点：凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。3、运行时动态链接本章内容4.1存储器的层次结构4.2程序的装入和链接4.3连续分配方式4.4对换4.5分页存储管理方式4.6分段存储管理方式4.3连续分配方式连续分配方式，是指为一个用户程序分配一个连续的内存空间。连续分配方式有四种：1.单一连续分配2.固定分区分配3.动态分区分配4.重定位分区分配4.3.1单一连续分配仅适用于单用户，单任务的OS。把内存分为系统区和用户区两部分1.系统区仅提供给OS使用，通常是放在内存的低址部分；2.用户区是指除系统区以外的全部内存空间，提供给用户使用。3.配置了存储器保护机构，用于防止用户程序对操作系统的破坏。后来取消了，因为：1）节约硬件；2）破坏微不足道。4.3.2固定分区分配固定分区分配：将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业。用户空间分为几个，就允许有几道作业并发运行。分区空闲时或作业结束后，从外存后备作业中装入。4.3.2固定分区分配（续）1．划分分区的方法两种：（1）分区大小相等当程序太小时，会造成内存空间的浪费。当程序太大时，一个分区又不足以装入该程序，致使该程序无法运行。主要用在一台计算机控制多个相同对象的场合。（2）分区大小不等可把内存区划含有多个较小的分区、适量的中等分区及少量的大分区。2．内存分配固定分区式分配的实现。为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表。如图所示：4.3.2固定分区分配（续）2．内存分配（续）固定分区式分配的优缺点：可运行多道程序的存储管理方式。存在“内零头”会造成存储空间的浪费。内零头——在分区内没有利用的部分称为内零头。4.3.2固定分区分配（续）4.3.3动态分区分配★动态分区分配是根据进程的实际需要，动态地为之分配内存空间。1．分区分配中的数据结构为了实现分区分配，系统中配置相应的数据结构，描述空闲分区以及已分配分区，为分配提供依据。常用的数据结构有以下两种形式：（1）空闲分区表在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占有一个表目，表目中包括分区序号，分区始址以及分区大小等。（2）空闲分区链。为了实现对空闲分区的分配和链接，设置前向指针和后向指针，通过前、后向链接指针将所有的空闲分区链接成一个双向链。图4-6空闲链结构（1）首次适应算法FF要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后按照作业大小在该区划分所需空间，余下部分仍然放在空闲分区链中。该算法的优缺点：为大作业分配大的内存空间创造了条件。低址部分不断被划分，会留下许多难以利用的、很小的空闲分区。增加查找可用空闲分区的开销。2．分区分配算法（2）循环首次适应算法:不从链首开始，从上次找到的空闲分区的下一个空闲分区开始查找，找到为止；将所有的空闲分区构成一个循环链表。采用循环查找方式，设置一个起始查寻指针，用于指示下一次起始查寻的空闲分区。该算法的优缺点：能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区。2．分区分配算法（续）（3）最佳适应算法最佳：指每次为作业分配内存时，把满足要求又是最小的空闲分区分配给作业，避免“大材小用”该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链该算法的优缺点为大作业分配大的内存空间创造了条件每次分配后所切割下来的剩余部分总是最小的，在存储器中会留下许多难以利用的小空闲区2．分区分配算法（续）在动态分区存储管理方式中，主要的操作是分配内存和回收内存。（1）分配内存系统应利用某种分配算法，从空闲分区链中找到所需大小的分区。3．分区分配操作Size是事先规定的不再切割的剩余分区的大小。（3）分区回收（内存回收）当进程运行完毕释放内存时，需合并相邻的空闲分区，形成大的分区，称为合并技术。需要合并的情况有如下图所示的三种，不论哪种情况，只需修改相应的分区信息来完成合并即可。回收分区前有空闲分区回收分区后有空闲分区回收分区前后都有空闲分区4.3.4伙伴系统伙伴系统规定，无论已分配分区或空闲分区，其大小均为2的k次幂，k为整数，l≤k≤m其中：21表示分配的最小分区的大小，2m表示分配的最大分区的大小，通常2m是整个可分配内存的大小。4.3.4伙伴系统（续）假设系统的可利用空间容量为2m个字节，则系统开始运行时，整个内存区是一个大小为2m的空闲分区。在系统运行过程中，由于不断的划分，可能会形成若干个不连续的空闲分区，将这些空闲分区根据分区的大小进行分类，对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。不同大小的空闲分区形成了k(0≤k≤m)个空闲分区链表分配当需要为进程分配一个长度为n的存储空间时，首先计算一个i值，使2i－1n≤2i，然后在空闲分区大小为2i的空闲分区链表中查找。若找到，即把该空闲分区分配给进程。否则，表明长度为2i的空闲分区已经耗尽，则在分区大小为2i+1的空闲分区链表中寻找。4.3.4伙伴系统（续）若存在2i+1的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为2i的空闲分区链表中。若大小为2i+1的空闲分区也不存在，则需要查找大小为2i+2的空闲分区4.3.4伙伴系统（续）若找到则对其进行两次分割：第一次，将其分割为大小为2i＋1的两个分区，一个用于分配，一个加入到大小为2i＋1的空闲分区链表中；第二次，将第一次用于分配的空闲区分割为2i的两个分区，一个用于分配