存储器管理

1一、多级存储器结构通用计算机的三级存储层次:最高层为CPU寄存器,中间为主存,最底层是辅存;高档计算机中,根据具体的功能分工细划为寄存器,高速缓存,主存,磁盘缓存,固定磁盘,可移动存储介质等6层4.1存储器的层次结构其中寄存器,高速缓存,主存,磁盘缓存掉电后存储的信息不再存在;而固定磁盘,可移动存储介质存储的信息可长期保存。2MemoryHierarchyTradeoffbetweenefficiency&costDesignconcerns:Howmuch?Howfast?Howexpensive?HereexistsadilemmaRegistersCacheMainmemoryInboardmemoryOutboardstorageOff-linestorageMagneticdiskCD-ROMCD-RWMagnetictapeGodownwardalongthehierarchya)Decreasingcostperbitb)Increasingcapacityc)Increasingaccesstimed)Decreasingfrequencyofaccessofthememorybytheprocessorlocalityofreference(Clustering)Solution:employmemoryhierarchyinsteadofsinglelayerSmaller,moreexpensive,fastermemoriesaresupplementbylarger,cheaper,slowermemories3二主存储器与寄存器主存储器用于保存进程运行时的程序和数据,也称为可执行存储器。CPU的控制部件只能从主存中取得指令和数据,数据能够从主存读取装入到寄存器中,也能从寄存器存入主存主存的访问速度远低于CPU执行指令的速度,为缓和这一矛盾,在计算机系统中引入了寄存器和高速缓存1)主存储器2)寄存器寄存器访问速度最快,完全能与CPU协调工作,但价格相当昂贵,故容量不大,寄存器的长度一般以字为单位41)高速缓存高速缓存的容量大于寄存器而比内存小两到三个数量级左右,从几十KB到几MB,访问速度快于主存为提高程序的执行速度,可根据程序执行的局部性原理,将主存中一些经常访问的信息放在高速缓存中,减少访问主存的次数;高速缓存的速度越高价格越贵,故有的计算机系统设置了两级或多级高速缓存三、高速缓存和磁盘缓存2)磁盘缓存磁盘的I/O速度远低于对主存的访问速度,可将频繁使用的一部分磁盘数据和信息暂时存放在磁盘缓存中,以减少访问磁盘的次数;磁盘缓存是利用主存中的存储空间来暂存从磁盘中读出或写入的信息54.2程序的装入和链接源程序编译目标模块库…..链接程序装入模块装入程序内存64.2.1程序的链接将经过编译或汇编后所得到的一组目标模块以及它们所需要的函数，装配成一个完整的装入模块。实现链接的方法有三种：静态链接装入时动态链接运行时动态链接7一、静态链接模块ACALLB；Return；模块BCALLC；Return；模块CReturn；000L-1M-1N-1模块AJSR”L”Return；模块B模块CReturn；JSR”L+M”Return；0L-1LL+M-1L+ML+M+N-18二、装入时动态链接用户源代码经过编译后所得到的目标模块，是在装入内存时，边装入边链接的。在装入一个目标模块时，若发生一个外部模块调用，将引起装入程序去找出相应的外部目标模块，并将它装入内存。优点：1、便于软件版本的修改和更新2、便于实现目标模块共享9三、运行时动态链接这种链接方式是将某些目标模块的链接推迟到执行时才进行的。在执行时，若发现一个被调用模块尚未装入内存时，由OS去找到该模块，将它装入内存，并链接到调用者模块上。将所有模块链接在一起，再全部调入内存，效率是很低的。10将一个模块装入内存时，可采用三种方式：4.2.2程序的装入绝对装入方式AbsoluteLoadingMode可重定位方式RelocationLoadingMode动态运行时装入方式DynamicRun-timeLoading11一、绝对装入方式按照装入模块中的地址，将程序和数据装入内存。装入模块被装入内存时是不需要对程序和数据的地址进行修改的。只能用于单道程序环境12当一个程序装入与其地址空间不一致的存储空间中，就得要进行地址变换。也就是说将逻辑地址映射为内存地址，把这种作法叫做地址重定位。重定位地址重定位机构需要一个或多个基址寄存器BR和一个或多个程序虚地址寄存器VR。指令或数据的内存地址MA与虚地址的关系为：MA=(BR)+(VR)其中，(x)表示寄存器x中的内容1312345LoadA500500100012345LoadA500+15000100500虚拟空间（作业地址空间）内存空间VRBR…..14二、可重定位装入方式在装入一个作业时，把作业中的指令地址全部转换为绝对地址(地址转换工作是在作业执行前集中一次完成的)在作业执行过程中就无须再进行地址转换工作。静态地址重定位在多道程序环境下，内存使用情况未知。根据内存的当前使用情况，将装入模块装入到内存的某个位置。15三、动态运行时装入方式动态地址重地位是在程序执行过程中，在CPU访问内存之前,将要访问的程序或数据地址转换成内存地址.动态重定位依靠硬件地址变换机构完成。动态地址重定位：实际上程序在内存中的位置经常要改变。164.3连续分配存储方式连续分配是指为一个用户程序分配一个连续的内存空间。这种分配方式应用于20世纪60~70年代的OS中,至今仍有使用。分为以下几种：单一连续分配方式分区式分配方式固定分区分配动态分区分配（可变分区）动态重定位分区分配17这是一种最简单的存储管理方式，但只能用于单用户、单任务的操作系统，如在8位和16位微机上CP/M和MS-DOS。它将内存分为两个区：系统区：仅供OS使用，通常设置在内存的低段；用户区：指除系统区以外的全部内存空间，提供给用户使用。4.3.1单一连续分配18界限寄存器重定位寄存器(基址)+CPU内存地址错逻辑地址YN物理地址地址映射和存储保护措施如下图:194.3.2固定分区(FixedPartitioning)分配固定式分区是最早使用的一种可运行多道程序的存储管理方式。在作业装入之前，内存就被划分成若干个分区。划分工作可以由系统管理员完成，也可以由操作系统实现。然而一旦划分完成，在系统运行期间不再重新划分，即分区的个数不可变，分区的大小不可变，所以，又可称为静态分区。每一个分区中都可以装入一道作业，因此这多道作业就可以并发执行了。20系统设置一张分区说明表，每个表目说明一个分区的大小、起始地址和是否已分配的使用标志。一、划分分区的方法1、分区大小相等2、分区大小不等将内存的用户区域划分成大小不等的分区，以适应不同大小的作业的需要。二、内存分配21区号大小起址标志116KB20K已分配232KB36K已分配364KB68K已分配4124KB132K未分配(a)分区说明表0k：20k：第1分区（16kb）36k：第2分区（32kb）（已分配）68k：第3分区（64kb）（已分配）132k：第4分区(124kb)（未分配）256k：（b）内存分配图操作系统作业A（16k）作业B（26k）作业C（56k）22要求xk大小分区取分区说明表第一项状态位置正在使用取下一表项无法分配该分区空闲？分区长度≥xk?表结束？返回分区号否否否是是是固定分区分配算法23优点：固定式分区实现技术简单，适用于作业的大小和多少事先都比较清楚的系统中。它用于60年代的IBM-360的MFT操作系统中。缺点：内存的利用率不高，“零头”空间不能充分利用。24固定分区的两种保护法上下界保护法：上界寄存器（UR）≤物理地址≤下界寄存器(LR)基址/限长保护法：基址寄存器（BR）≤物理地址≤(BR)+(LR)LR为限长寄存器254.3.3动态(DynamicPartitioning)分区分配可变式分区是指在作业装入内存时，从可用的内存中划出一块连续的区域分配给它，且分区大小正好等于该作业的大小。可变式分区中分区的大小和分区的个数都是可变的，而且是根据作业的大小和多少动态地划分，因此又称为动态式分区。这种存储管理技术是固定式分区的改进，既可以获得较大的灵活性，又能提高内存的利用率。26可变式分区的分配和释放的基本思想：在分配时，首先找到一个足够大的空闲分区，即这个空闲区的大小比作业要求的要大，系统则将这个空闲分区分成两部分：一部分成为已分配的分区，剩余的部分仍作为空闲区。在回收撤除作业所占领的分区时，要检查回收的分区是否与前后空闲的分区相邻接，若是则加以合并，使之成为一个连续的大空间。27有两种数据结构可选用，空闲分区表FBT(FreeBlockTable)和空闲分区链FBC(FreeBlockChain)空闲分区表为每个尚未分配的分区设置一个表项，包括分区的序号、大小、始址和状态。空闲区链形式为了实现对空闲分区的分配和链接，在每个分区的起始部分，用两个字段设置一些用于控制分区分配的信息（如分区的大小和状态位），以及用于链接其它分区的前向指针；在分区尾部，用两个字段设置了一个后向指针，为了检索方便也设置了控制分区分配的信息。然后，通过前、后向指针将所有的分区链接成一个双向链表。一、分区分配数据结构280k：20k：52k：116k：164k：260k：512k：序号大小起址状态148k116k空闲2252k260k空闲3——空表目4——空表目5——空表目操作系统作业1（32k）作业2（64k）空闲区（48k）作业4（96k）空闲区（252k）N个字节可用（b）空闲链结构N+20前向指针后向指针N+20（a）空闲分区表（c）内存分配图29比较：FBT相当简单，每个表目记录空闲区的大小及其起始地址。由于空闲区的个数是动态改变的，因此FBT表目的最大个数难以确定：太小了有可能产生表目溢出，太大了会产生表目空间的浪费。不过此表目所占位数不多，浪费不算严重。FBC的设计技巧在于：它利用空闲区本身的空间记录空闲区的大小及前后空闲区的位置。当分配一空闲区时，用于成链的首尾两字也一起连同分配，这样就不再需用额外的存储空间来记录空闲区现状。30动态分区原则：存储空间的划分是在装作业时进行的。从可用的空闲存储空间内，划出一个大小正好等于作业大小的存储区，并分配给这一作业。进程A（8K）进程D（124K）进程B（16K）进程C（64K）…OS进程A进程B进程C进程DOS进程A进程B进程COS进程A进程BOS进程A31OSA（8K）24K空闲区B（16K）C完成（64K）空闲区D（124K）OSA（8K）8K空闲区B（16K）E（50K）D（124K）14K空闲区F（16K）OSA（8K）8K空闲区空闲区16KE（50K）D（124K）空闲合并124+14=138K进程E（50K）进程F（16K）进入内存进程B（16K）进程D（124K）完成内存分配变化过程32二、分区分配算法(PartitioningPlacementAlgorithm)把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中，选出一分区分配给作业，目前常用的分配算法有：最佳适应算法（BestFit）首次适应算法（FirstFit）循环首次适应算法(NextFit)最坏适应算法（WorstFit）快速适应算法（quickfit）33算法：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业。这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。特点：分配空间时尽量利用低地址部分的存储区域，而使高地址部分保持较大的自由区，有利于大进程的装入。首次适应算法（FirstFit）34从该空闲区中截取所需大小，修改调整可用表从空闲区表第一表目顺序查找从可用表中移去该表目，调整可用表取下一表项无法分配该空闲区长度≥SIZE？该