计算机操作系统-存储器管理

第四章存储器管理存储器是计算机系统的重要组成部分之一。对存储器加以有效管理，不仅直接影响存储器的利用率，而且对系统性能有重大影响。内存管理的主要对象是内存，对外存的管理在文件管理中。第四章存储器管理存储器的层次结构多级存储器结构主存CPU寄存器辅存寄存器高速缓冲存储器磁盘缓存磁盘可移动存储介质主存存储器的层次结构1、主存储器CPU只能从主存储器中取得指令和数据。但运行速度远低于CPU执行指令的速度。2、寄存器访问速度最快，但价格昂贵。3、高速缓存容量远大于寄存器，但比主存小两三个数量级。4、磁盘缓存利用主存中的存储空间。第四章存储器管理4.1程序的装入和链接4.2连续分配方式4.3基本分页存储管理方式4.4基本分段存储管理方式4.5虚拟存储器的基本概念4.6请求分页存储管理方式4.7页面置换算法4.8请求分段存储管理方式本章重点难点1、掌握地址变换机构及实现方法。2、掌握虚拟存储器概念和虚拟存储技术。3、掌握页面置换算法。4.1程序的装入和链接在多道程序环境下，要使程序运行，必须为之先建立进程。创建进程的第一件事是将程序和数据装入内存。将用户源程序变为可在内存中执行的程序的步骤：1、编译：由编译程序将用户源代码编译成若干个目标模块2、链接：由链接程序将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块3、装入：由装入程序将装入模块装入内存4.1程序的装入和链接库链接程序装入模块装入程序…编译程序产生的目标模块第一步第二步第三步内存4.1程序的装入和链接4.1.1程序的装入将一个装入模块装入内存时，有三种方式：绝对装入方式可重定位装入方式动态运行时装入方式4.1程序的装入和链接1.绝对装入方式在编译时，如果知道程序驻留在内存的什么位置，那么编译程序将产生绝对地址的目标代码。装入模块装入内存后，程序中的逻辑地址与实际内存地址完全相同，不须对程序和数据的地址进行修改。程序中所使用的绝对地址，可在编译或汇编时给出，也可由程序员赋予。只适合于单道程序环境4.1.1程序的装入4.1程序的装入和链接2.可重定位装入方式在多道程序环境下，目标模块的起始地址通常从0开始，程序中的其他地址都是相对于起始地址计算的。因此应采用可重定位装入方式，根据内存的当前情况，将装入模块装入到内存的适当位置。注意：在采用可重定位装入方式将装入模块装入内存后，会使装入模块中的所有逻辑地址与实际装入内存的物理地址不同。4.1程序的装入和链接365LOAD1,2500365LOAD1,2500~~~~010002500500010000110001250015000作业地址空间内存空间在装入时对目标程序中指令和数据的修改过程称为重定位。地址变换在装入时一次完成，以后不再改变，称为静态重定位。4.1程序的装入和链接3.动态运行时装入方式动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。为使地址转换不影响指令的执行速度，应设置一个重定位寄存器。4.1程序的装入和链接4.1.2程序的链接程序经过编译后得到一组目标模块，再利用链接程序将目标模块链接，形成装入模块。根据链接时间的不同，把链接分成三种：1、静态链接：在程序运行前，将目标模块及所需的库函数链接成一个完整的装配模块，以后不再拆开。2、装入时动态链接：指将用户源程序编译后所得的一组目标模块，在装入内存时，采用边装入边链接的链接方式。3、运行时动态链接：指对某些目标模块的链接，是在程序执行中需要该目标模块时，才对它进行链接。1.静态链接方式：事先进行链接，以后不再拆开4.1.2程序的链接模块ACALLB;Return;0L-1模块BCALLC;Return;0M-1模块CReturn;0N-1模块AJSR“L”Return;0L-1模块BJSR“L+M”Return;LL+M-1模块CReturn;L+ML+M+N-1目标模块装入模块将目标模块装配成装入模块时需解决的两个问题：(1)对相对地址进行修改(2)变换外部调用符号4.1.2程序的链接2.装入时动态链接：用户源程序经编译后所得的目标模块，是在装入内存时，边装入边链接的，即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，还要修改目标模块中的相对地址。优点：便于修改和更新便于实现对目标模块的共享3.运行时动态链接：运行时动态链接是将对某些模块的链接推迟到执行时才执行，即在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡执行过程中未被用到的目标模块，不会调入内存和链接，这样不仅加快程序的装入过程，而且节省大量的内存空间。4.1.2程序的链接第四章存储器管理4.1程序的装入和链接4.2连续分配方式4.3基本分页存储管理方式4.4基本分段存储管理方式4.5虚拟存储器的基本概念4.6请求分页存储管理方式4.7页面置换算法4.8请求分段存储管理方式4.2连续分配方式内容及要求四种连续分配方式；理解和掌握动态分区分配及动态重定位分区分配方式；掌握动态分区分配算法4.2连续分配方式连续分配方式，是指为一个用户程序分配一个连续的内存空间。单一连续分配固定分区分配动态分区分配可重定位分区分配4.2.1单一连续分配方式把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常放在内存低址部分，用户区是指除系统区以外的全部内存空间，提供给用户使用。但只能用于单用户、单任务的操作系统中。系统区（OS）用户区内存4.2连续分配方式连续分配方式，是指为一个用户程序分配一个连续的内存空间。单一连续分配固定分区分配动态分区分配可重定位分区分配4.2.2固定分区分配1.原理将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业，便可以有多道作业并发执行。当有一空闲分区时，便可以再从外存的后备作业队列中，选择一个适当大小的作业装入该分区，当该作业结束时，可再从后备作业队列中找出另一作业调入该分区。2.划分分区的方法(1)分区大小相等：所有的内存分区大小相等，缺乏灵活性(2)分区大小不等：把内存区划分成含有多个较小的分区、适量的中等分区及少量的大分区。3.实现为便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)。当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”；若未找到大小足够的分区，则拒绝为该用户程序分配内存。未分配1281284已分配64643已分配32322已分配20121状态起址(K)大小(K)分区号分区说明表作业C作业B作业A操作系统20K32K64K128K256K存储空间分配情况4.2.2固定分区分配4.2连续分配方式连续分配方式，是指为一个用户程序分配一个连续的内存空间。单一连续分配固定分区分配动态分区分配可重定位分区分配4.2.3动态分区分配1.原理动态分区分配是根据进程的实际需要，动态地为之分配内存空间。作业装入内存时，把可用内存分出一个连续区域给作业，且分区的大小正好适合作业大小的需要。分区的大小和个数依装入作业的需要而定2.实现在实现过程中涉及如下问题：分区分配中的数据结构分区分配算法分区分配及回收操作1）分区分配中的数据结构（1）空闲分区表示空闲分区表：记录每个空闲分区的情况。每个空闲分区占一个表目。空闲分区链：在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针；在分区尾部则设置一后向指针,将所有的空闲分区链接成一个双向链。2.实现4.2.3动态分区分配序号大小起址状态148k116k可用2252k260k可用（a）空闲分区表作业号大小起址132k20k264k52k496K164K（C）已占分区表（2）已占分区说明表结构：作业号；起始地址；大小2）分区分配算法为把一个新作业装入内存，需按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。常用的分配算法：(1)首次适应算法FF(2)循环首次适应算法(3)最佳适应算法4.2.3动态分区分配(1)首次适应算法FFFF算法要求空闲分区表以地址递增的次序排列。在分配内存时，从表首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表中。若从头到尾不存在满足要求的分区，则分配失败。优点：优先利用内存低址部分的内存空间,保留了高址部分的大空闲区。缺点：低址部分不断划分，产生小碎片（内存碎块、内存碎片、零头）；每次查找从低址部分开始，增加了查找的开销4.2.3动态分区分配(2)循环首次适应算法在分配内存空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。为实现算法，需要：设置一起始查寻指针采用循环查找方式优点：使内存空闲分区分布均匀，减少查找的开销缺点：缺乏大的空闲分区4.2.3动态分区分配(3)最佳适应算法所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。缺点：产生许多难以利用的小空闲区4.2.3动态分区分配3）分区分配及回收操作分配内存利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为u.size，表中每个空闲分区的大小表示为m.size，若m.size-u.sizesize(规定的不再切割的分区大小)，将整个分区分配给请求者，否则从分区中按请求的大小划出一块内存空间分配出去，余下部分留在空闲链中，将分配区首址返回给调用者。4.2.3动态分区分配4.2.3动态分区分配回收内存当进程运行完毕释放内存时，系统根据回收区首址，在空闲分区链(表)中找到相应插入点，可能有四种情况：(1)回收区与插入点的前一个分区F1邻接：(2)回收区与插入点的后一个分区F2邻接：(3)回收区与插入点的前后两个分区F1、F2邻接：(4)回收区既不与F1邻接，又不与F2邻接：4.2连续分配方式连续分配方式，是指为一个用户程序分配一个连续的内存空间。单一连续分配固定分区分配动态分区分配可重定位分区分配4.2.4可重定位分区分配1.动态重定位的引入在连续分配方式中，必须把系统或用户程序装入一连续的内存空间。如果在统统中只有若干个小分区，即使它们的容量总和大于要装入的程序，但由于这些分区不相邻，所以无法将程序装入内存。20KB0os作业1作业3作业452KB116KB166KB256KB紧凑后20KBos作业1作业3作业452KB66KB130KB230KB256KB紧凑前180KB014K50K26K80K解决方法：将内存中的所有作业进行移动，使它们全部邻接，这样可把原来分散的小分区拼接成大分区，这种方法称为“拼接”或“紧凑”。缺点：用户程序在内存中的地址发生变化，必须重定位。20KB0os作业1作业3作业452KB116KB166KB256KB紧凑后20KBos作业1作业3作业452KB66KB130KB230KB256KB紧凑前180KB014K50K26K80K2.动态重定位的实现在动态运行时装入的方式，将相对地址转换为物理地址的工作在程序指令真正要执行时才进行。地址转换需要重定位寄存器的支持。程序执行时访问的内存地址是相对地址与重定位寄存器中的地址相加而成。地址变换过程是在程序执行过程期间，随着对每条指令的访问自动进行的，称为动态重定位。Load1,2500365Load1,2500365010050059901000