操作系统第四章

第四章存储器管理第一节存储器的层次结构第二节程序的装入和链接第三节连续分配存储管理方式第四节对换（Swapping）第五节基本分页存储管理方式第六节基本分段存储管理方式序言存储器：主存（内存）、副存（外存）内存－进程、外存－文件内存管理：地址映射、内存分配与回收存储保护、内存扩充(虚拟内存)外存管理：文件管理存储器的层次结构计算机对存储器的要求：1.要求存储器的访问速度能跟上处理机的运行速度。2.要求存储器具有非常大的容量。3.要求存储器的价格便宜。基于以上三个要求，目前计算机系统都采用了多层结构的存储器系统。多层结构存储器系统1.存储器的多层结构通用计算机的存储器具有3层结构：由低到高分别为：辅存、主存、CPU寄存器。高档计算机的存储器结构分为：寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6层。存储器的特点：层次越高，存储介质的访问速度越快，价格越高，容量越小。存储器管理系统负责管理内存，外存作为文件管理内容。2.可执行存储器指寄存器和主存储器特点：对可执行存储器访问速度快，对辅存的访问需要通过I/O设备，因此耗费的时间远高于可执行存储器，一般至少相差3个数量级。主存储器与寄存器主存储器_内存用于保存进程运行时的程序和数据，又称为可执行存储器。CPU一般从主存中取出指令和数据分别存放于CPU中的指令寄存器和数据寄存器中，反之将寄存器数据存入主存中。主存早期容量为数10到数百KB，现在高达数10MB到数GB。但主存访问速度低，故引入了寄存器和高速缓存。寄存器寄存器的访问速度最快，与处理器运行速度相当，但价格非常昂贵，容量也很小。随着VLSI的发展，现在的微机系统中，寄存器数量已达到数10个到数百个。高速缓存和磁盘缓存1.高速缓存是现代计算机结构中的一个重要部件，介于寄存器和主存之间，用于备份主存中较常用的数据，以减少处理机对主存的访问次数，从而大幅提高程序执行速度。其容量远大于寄存器，从几10KB到几MB，其访问速度快于主存。特点：由于高速缓存的速度越高，价格越贵，故计算机系统会设置两个或多个高级缓存，一级缓存紧靠内存，速度最快，容量最小。2.磁盘缓存由于主存的访问速度远高于磁盘的访问速度，为了缓和两者间速度差异，设置了磁盘缓存，用于暂时存放频繁使用的一部分磁盘数据和信息，以减少访问磁盘的次数。特点：与高速缓存不同，磁盘缓存不是一种实际存在的存储器，而是利用主存中的一部分存储空间暂时存放磁盘信息。一个文件数据可能会出现在不同层次的存储器中：辅存—主存（磁盘缓存）程序的装入和链接用户提交的程序需要经过以下几个步骤才能被系统运行：1.编译2.链接3.装入从源程序到程序执行编译：编译程序由编译程序（Compiler）将用户源代码编译成若干个目标模块。链接：链接程序由链接程序（Linker）将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成装入模块。装入：装入程序由装入程序（Loader）将装入模块复制到内存中。库汇编编译主子1子2目标模块链接程序装入模块库主子1子2装入程序内存库主子1子2程序的装入就是把链接好的装入模块装入“内存”。装入方式绝对装入：只适用单道程序环境；装入内存的位置是可知的、固定的，故采用绝对装入方式，按照装入模块中的地址，将程序和数据装入内存，由于程序的逻辑地址与物理地址一致，故地址无需修改。程序中所使用的物理地址一般设置为在编译、汇编时再给出，此前由符号地址代替。可重定位装入（静态重定位）：适用于多道程序环境，存在很多的用户程序编译所形成的若干个目标模块，它们的起始地址都是从0开始的逻辑地址，可通过重定位方式装入内存合适的位置，但这会使装入模块的逻辑地址与实际装入内存后的物理地址不同，故需要对程序和数据的地址进行修改。动态运行时装入（动态重定位）：允许程序在运行时，在内存中移动位置。实际上，程序在内存中运行时，它在内存中的位置可能要经常改变。例如：在对换功能系统中，一个进程可能被多次换出，又多次换入。动态运行时装入程序：把装入模块装入内存后，并不立即把模块中的逻辑地址转换为物理地址，而是把这种地址转换推迟到程序真正要执行时才进行。重定位的概念重定位概念：把程序装入内存时，修改程序中所有与地址有关的项。逻辑地址变换为物理地址。重定位的类型静态重定位：程序执行前，一次性，链接装入程序。动态重定位：处理机每次访问主存时，有动态地址变换机构（硬件）自动执行。作业地址空间内存空间装入365LOAD1,2500500025001000365LOAD1,250015000125001000011000365LOAD1,1250015000125001000011000链接方式静态链接：程序在运行之前，先将目标模块及其所需库函数链接成一个完整的装配模块，以后不再拆开。这种事先进行链接的方式即为静态链接方式。（1）对相对地址进行修改，将目标模块的相对地址修改为相应的装入模块相对地址；（2）变换外部的调用符号，将每个模块中所用的外部调用符号也都变换为装入模块中的相对地址。程序的链接链接：把一个程序相关的一组目标模块和系统调用模块（库函数）链接形成一个整体——装入模块的过程。具体工作：对相对地址的修改；变换外部调用符号。模块ACallB;Return;0L-1模块BCallC;Return;0M-1模块C……;Return;0N-1链接模块AJSR‘L’;Return;0L-1模块BJSR‘L+M’;Return;LL+M-1模块C……;Return;L+ML+M+N-1装入模块目标模块使用的都是相对地址，其起始地址都为0，每个模块中的地址都是相对于起始地址计算的。长度链接方式装入时动态链接：在将目标模块装入内存时，边装入边链接的链接方式，即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，同时修改目标模块中的相对地址。优点：（1）便于修改和更新，由于各目标模块是分开存放的，所以要修改或更新各目标模块就很容易。（2）便于实现对目标模块的共享，在采用静态链接方式时，每个应用模块都必须含有其目标模块的拷贝，无法实现对目标模块的共享，但采用装入时动态链接的方式时，OS就很容易将一个目标模块链接到几个应用模块上，实现多个应用程序对该模块的共享。链接方式运行时动态链接：将对某些模块的链接推迟到程序执行时才进行。亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块，并将之装入内存，将其链接到调用者模块上。优点：凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅能加快程序的装入过程，而且可节省大量的内存空间。连续分配存储管理方式连续分配方式：为用户程序分配一个连续的内存空间，即程序中代码的逻辑地址相邻体现在内存空间分配时，物理地址的相邻。曾被广泛应用，且现在仍被采用。单一连续分配固定分区分配动态分区分配动态可重定位分区分配单一连续分配单一连续分配的基本思想把内存分为系统区和用户区，系统区供OS使用，通常放在内存的低址部分；系统区以外的全部内存空间是用户区，仅装有一道用户程序。单一连续分配的特点只能用于单用户、单任务的单道程序环境的OS中。软件简单，硬件要求低（可无需存储器保护措施）实例CP/M，MS-DOS，RT-11等单用户OSMS-DOS内存分区CP/M内存分配系统参数区BIOSCCPBDOS系统区系统区固定分区分配在多道程序环境中，为了防止装入内存中的多个程序间互相干扰，于是将整个内存用户空间划分为若干个固定大小的区域，将每个分区中只装入一道作业，即为固定分区分配。1.划分分区的方法（划分为若干个固定大小的分区）分区大小相等：缺乏灵活性：当程序太小会造成内存空间浪费，当程序太大又无法满足其运行。比较适用于一台计算机同时控制多个相同对象的场合。分区大小不相等：较上种方法灵活，通常将内存划分为多个较小的分区、适量中等分区、少量大分区。2.内存分区分配分区使用表（MBT）：分区号、大小、分区起址、状态分区按内存空间大小排队当用户程序要装入时，由内存分配程序检索分区使用表，找到满足要求、尚未分配的分区，将之分配给它。固定分区分配区号/键大小起址状态18K512K正使用232K520K正使用332K552K未使用4128K584K未使用5512K712K正使用…………系统区分区1分区4分区5分区2分区3系统区作业3分区4作业2作业1分区3分区使用表动态分区分配可变分区分配思想分区的位置和大小都不固定，应作业的要求而设置，为之动态分配内存空间。动态分区分配的数据结构的两种形式：空闲分区表（用于记录每个空闲分区）、空闲分区链：用于实现对空闲分区的分配和链接，在每个分区的头部、尾部分别设置了前向、后向指针，形成了双向链表。分区号始址大小状态12012k空闲24032k空闲310064k空闲4220128k空闲前向后向指针指针N+2N+200分区大小分区状态分区分配流程图分配内存分区大小与所需空间大小“匹配”：M.Size-U.Size≦Size（不再分割的小分区的尺寸）剩余部分挂接到空闲分区链（表）上。查找空闲分区链表第一项检索完否？m.sizeu.size?m.size-u.size≦size?划出u.size大小的分区修改有关的数据结构返回将该分区从链表中移出继续检索下一个表项YYYNNN空闲状态分区动态分区分配算法首次适应算法FF要求：1.空闲分区链以地址递增的次序链接2.每次从链首开始顺序查找第一个大小能满足要求的空闲分区，然后划分，余下的空闲分区仍留在空闲链中优先利用地址部分，保留高址部分的大空闲区碎片较多，每次从低址查找要增加查找的开销为了将一个新作业装入内存中，须按照一定的分配算法，从空闲分区表中选出一分区给该作业，接下来将介绍四种传统的顺序式搜索算法：循环首次适应算法：对首次适应算法的演变，从上次找到的下一个空闲分区开始找要求：1.设置一个起始查找指针2.采用循环查找方式内存中的空闲分区分布更均匀减少了查找空闲分区始的开销缺乏大的空闲分区最佳适应算法要求：1.将所有的空闲分区按其容量从小到大的顺序形成一空闲分区链2.从链首开始查找第一个大小适合的空闲分区第一次找得的是最佳即最恰好适合的分区能够避免“大材小用”同时，空闲分区每次分配切割留下的剩余部分总是最小的，留下大量的难以利用的碎片回收操作较困难最坏适应算法要求：1.将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链2.每次分配链首的第一个空闲分区每次利用是最大的分区，空闲分区每次分配切割留下的剩余部分总是最大的，避免留下大量的难以利用的碎片查询开销非常小但缺乏大空闲分区动态分区分配算法分配算法比较几种算法各有利弊，到底哪种最好不能一概而论，而应针对具体作业序列来分析。对于某一作业序列来说，某种算法能将该作业序列中所有作业安置完毕，那么我们说该算法对这一作业序列是合适的。对于某一算法而言，如它不能立即满足某一要求，而其它算法却可以满足此要求，则这一算法对该作业序列是不合适的。例：有作业序列：作业A要求20K；作业B要求28K，作业C要求30K。要求画出系统中空闲区按照首次适应算法，最佳适应算法、最坏适应算法形成的三种空闲分区队列，然后分析哪种算法对该序列是合适的？经分析可知：最佳适应法对这个作业序列是合适的，而其它两种对该作业序列是不合适的。练习有作业序列：作业A要求21K；作业B要求25K，作业C要求30K，那种分配算法适合该作业序列？动态分区分配算法基于索引搜索的动态分区分配算法由于顺序搜索的动态分区分配算法比较适用于较小的系统。当系统很大时，为了提高搜索空闲分区的速度，采用基于索引搜索的动态分区分配算法：1.快速适应算法2.伙伴系统3.哈希算法快速适应算法又称为分类搜索算法，是将空闲分区根据容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，同时在内存中设立一张管理索引表，其中的每一个索引表