操作系统概论第3章 存储管理

第3章存储管理重点：各种管理方式下的地址转换；可变分区方式的主存分配算法以及移动技术；页式虚拟存储管理的实现以及页面调度算法3.1计算机系统中的存储器存储器的层次结构：RegisterCache和主存磁盘处理机直接访问I/O控制系统的管理•寄存器:最贵,最快,最小,每个只存储一个字长,只放临时的工作数据和控制信息(指令寄存器,通用寄存器,控制寄存器)•高速缓存Cache：少量的、快速、昂贵、易变,以字节为单位编址•内存RAM：若干兆字节、中等速度、中等价格、易变•磁盘：数百兆或数千兆字节、低速、价廉、不易变的存储管理概述•内存的作用•为什么需要存储管理？–帕金森定律：你给程序再多内存,程序也会想尽办法耗光内存管理概述由存储单元（字节或字）组成的一维连续地址空间，用来存放当前正在运行的程序的代码或数据，是程序中指令本身（程序计数器）所指向的存储空间内存管理的目的•操作系统的“方便”性–便于用户装入程序，无须了解底层细节–可实现动态的存储空间伸缩，适应不同程序的需要•操作系统的“合理”性–合理分配内存空间，保证多道程序的顺利运行–合理保护内存空间，防止各种可能的破坏泄漏•操作系统的“有效性”–有效保持内存空间的可用性，防止对资源的浪费–有效实现“小空间大容量”，提高计算机的适应性–有效配合CPU的调度过程，实现系统运行的稳定内存管理概述内存管理的任务•内存空间的管理、分配和回收–内存空间的使用情况记录——位图、分配表、分区表–内存空间的分配与回收——定长与不定长、静态与动态•内存空间的地址映射（转换）–物理地址与逻辑地址的差别•内存空间的共享和保护–内存共享–内存保护：如何防止地址越界或操作越权？•内存空间的扩充–虚拟存储：如何使用小内存空间来运行大的程序？3.2重定位3.2.1绝对地址和逻辑地址(1)逻辑地址（相对地址，虚地址）(2)物理地址（绝对地址，实地址）(3)地址映射(重定位)地址映射BA=1000LoadA2003456。。1200物理地址空间LoadAdata1data13456源程序LoadA20034560100200编译连接逻辑地址空间逻辑地址（相对地址，虚地址）•用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都相对于首地址而编址•不能用逻辑地址在内存中读取信息物理地址（绝对地址，实地址）内存中存储单元的地址，可直接寻址以字节为单位进行编址3.2.2重定位•为了保证CPU执行指令时可正确访问存储单元，需将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址，这一过程称为重定位110012001300物理地址空间03456......LOADA200......0100200300.........LOADA2003456逻辑地址空间200VR+1000BR原因:当程序装入内存时,操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致,而CPU执行指令时，是按物理地址进行的，所以要进行地址转换静态重定位当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在连接装配时由软件完成）在作业装入过程中随即进行的地址变换方式称为静态重定位或静态地址映射movr1,[500]123movr1,[500+m]12301005005990mm+100256k-1作业地址空间存储空间m+500重定位装入程序动态重定位•在程序运行过程中要访问数据时再进行地址变换（即在逐条指令执行时完成地址映射。一般为了提高效率，此工作由硬件地址映射机制来完成。硬件支持，软硬件结合完成）•硬件上需要一对寄存器的支持在程序执行期间，随着每条指令和数据的访问自动地连续地进行地址映射movr1,[500]1230100500599作业地址空间0movr1,[500]1231000256k-1存储空间110015001600重定位寄存器1000500逻辑地址+静态地址映射动态地址映射在作业装入过程中在程序执行期间进行地址映射进行地址映射需软件需硬件地址变换机构重定位装入程序重定位寄存器需花费较多CPU时间地址变换快不灵活灵活静态地址映射与动态地址映射的区别3.3单用户连续存储管理•单用户系统在一段时间内，只有一个进程在内存，故内存分配管理十分简单，内存利用率低•内存分为两个区域，一个供操作系统使用，一个供用户使用•单道运行的计算机系统•存储保护:界限寄存器•分时系统:对换方式•静态定位方式单用户连续存储管理(cont.)•最简单的管理方式（只有分配与回收）–操作系统和用户程序共享RAM–除了嵌入式系统外，其他的计算机不再使用这种方式内存管理概述用户程序RAM中的OS用户程序ROM中的OS用户程序RAM中的OSROM：DEV早期大型机使用的内存管理方式少数掌上电脑和嵌入式系统使用的内存管理方式早期PC使用的内存管理方式（MS-DOS)3.4固定分区存储管理方案系统把内存用户区划分为若干分区，分区大小可以相等，也可以不等。一个进程占据一个分区固定分区可变分区•每个分区的大小可以相同也可以不同,但分区个数固定不变•每个分区装一个且只能装一个作业•存储分配：如果有一个空闲区,则分配给进程固定分区固定分区存储管理的问题•如何实现内存的分配与回收？–已知内存分区数为N，已知进程数为M，如何分配内存？–关于回收：OS维护的内存分区表中应该有哪些信息？•内存地址映射与存储保护–重定位问题与保护：物理地址和逻辑地址的映射关系•内存空间的扩充,提高主存空间利用率–使用固定分区的形式可以实现内存的扩充吗？3.4.1主存空间的分配和回收•如何知道那个分区被占用,那个空闲–分区分配表:说明各区的分配和使用情况•分区分配表–分区号,起始位置,长度,占用标志•内存的分配和回收–修改标志位分区号起始地址长度占用标志3.4.2地址转换和存储保护•地址转换:静态重定位(在调入内存时直接修改指令)•存储保护:引入界限寄存器(下限寄存器,上限寄存器)•下限寄存器=绝对地址上限寄存器3.4.3如何提高主存空间的利用率•每个作业占用一个分区,且只占用一部分•提高主存利用率:–根据经常出现的作业的大小和数量来划分分区–划分分区时,按分区的大小顺序排列.找到一个能满足作业要求的最小空闲分区分配给作业.–按作业对主存要求排成多个队列:能有效防止小作业进入大分区分区4分区3分区2分区1操作系统多个输入队列单个输入队列分区4分区3分区2分区1操作系统700K400K100K0划分分区的注意事项•可能出现的作业大小•作业频率•划分不当:某个作业队列长期为空,影响分区的使用效率3.5可变分区存储管理•基本思想：–内存不是预先划分好的–作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配–若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待内存空间--分区的长度不是预先确定的，按需划分--分区的个数也不是预先确定的，是由装入的作业数决定的•内存的分配–根据作业对主存的需要量，从空闲区划出一个与作业一致长度的分区来装入作业，剩余部分认为空闲区–当空闲区能满足需求时，作业可装入；超过，作业暂时不能转入3.5.1主存空间的分配和回收20KB0os作业1作业2作业3作业452KB66KB130KB230KB256KB1主存20KB0os作业1作业2作业352KB66KB130KB256KB1主存20KB0os作业152KB256KB1主存0os256KB1主存20KB20KB0os作业1作业252KB66KB256KB1主存作业1申请32KB作业2申请14KB作业3申请64KB作业4申请100KB作业5申请50KB•内存的回收：–当作业结束时，它的占用分区被收回。这个空闲区又可以根据新作业的大小重新用于分配，所以主存中的已占分区和空闲区的数目和大小都是在变化的–可以用“空闲区表”来记录和管理：记录空闲区的起始地址和长度20KB0os作业1作业2作业3作业452KB66KB130KB230KB256KB1主存20KB0os作业1作业2作业3作业452KB66KB130KB230KB256KB1主存20KB0os作业1作业2作业3作业452KB66KB130KB230KB256KB1主存作业2完成作业4完成•分区的分配与回收1.分区分配••分区分配程序在空闲块队列中找一个满足用户需要的空闲块；•若找到，以空闲块与请求的主存块大小之间的关系进行相应的处理，并返回所分配区域的首址；•否则，•主存分配策略–首次匹配(最先适应分配算法)–最佳匹配(最优适应分配算法)–最坏匹配(最坏适应分配算法)•首次适应算法(1)什么是首次适应算法首次适应算法是将输入的作业放置到主存里第一个足够装入它的可利用的空闲区中(2)特点空闲区地址由低到高排序尽可能地利用存储器中低地址的空闲区，而尽量保存高地址的空闲区•最佳适应算法(1)什么是最佳适应算法最佳适应算法是将输入的作业放置到主存中与它所需大小最接近的空闲区中(2)特点空闲区大小由小到大排序尽可能地利用存储器中小的空闲区，而尽量保存大的空闲区•最坏适应算法(1)什么是最坏适应算法最坏适应算法是将输入的作业放置到主存中最不适合它的空闲区中(3)特点空闲区大小由大到小排序尽可能地利用存储器中大的空闲区2.分区回收回收主存块的四种情况r上邻空闲区rf1作业2r上下邻空闲区rf1f2r上下邻已分配区r作业1作业2r下邻空闲区r作业1f2回收分区r上邻空闲区rf1作业2f1作业2r与f1合并成为一个大的空闲区f1回收分区r下邻空闲区r与f2合并成为一个大的空闲区f2作业1f2r作业1f2SS+LSS回收分区r上、下邻空闲区r与f1、f1合并成为一个大的空闲区f1回收分区r上、下邻分配区r成为一个新的空闲区frf1f2f1r作业1作业2f作业1作业23.5.2地址转换和存储保护•采用动态重定位方式装入作业，也就是每读一条指令，都要变换一次地址•变换要靠硬件支持，主要是两个寄存器：基址寄存器,限长寄存器以及加法线路，比较线路•基址寄存器则存放作业所占分区的起始地址，限长寄存器存放作业所占分区的最大地址，这两个值确定了一个分区的位置和大小•P49图3－13存储保护•转换时根据将逻辑地址加上基址寄存器中的值就得到了绝对地址基址寄存器内容＝绝对地址＝限长寄存器内容•满足上式，表示访问地址合法，否则形成“地址越界”中断，达到存储保护的目的•中断时，基址/限长寄存器内容PCB3.5.3移动技术•可变分区的存储方式采用动态定位方式装入作业，作业可以根据需要改变位置•把作业从一个存储区域移动到另一个存储区域的工作－－移动•目的：–集中分散的空闲区（碎片问题）–便于作业动态扩充主存移动技术注意事项•移动会增加系统开销。所以要尽量减少移动–移动作业的信息传送–修改PCB中分区的始址和末址，空闲区表•移动是有条件的，如果作业在执行过程中正等待与外围设备传输信息，就不能移动。因此在移动时首先要判定该作业是否与外设交换信息•可采用改变作业装入主存的方式达到减少移动的目的1、早期的单用户操作系统是（）存储管理功能2、存储管理是对主存的（）区域进行管理3、存储管理的目的是（）4、地址转换的工作是将（）5、动态重定位是需要由（）来实现6、经过（），目标程序可以不经过修改而装入物理内存单元7、固定分区存储管理中，每个分区的大小是（）8、碎片是指（），碎片的存在使得（）9、最容易形成碎片的可变分区分配算法是（）10、可变分区管理主存时（）程序在主存中不能移动3.6页式虚拟存储管理•问题的提出：–彻底解决碎片问题，提高主存的利用率–解决必须连续分配的问题–能否在较小的主存空间运行较大的作业3.6.1页式存储管理的基本原理•问题1:彻底解决碎片问题，提高主存的利用率•碎片问题:可变分区存储管理按照作业对存储的需求量进行分区的划分，因此它不出现内部碎片。但由此会招致某些分区过小而无法满足作业存储请求的情形，从而产生外部碎片。在那里，解决外部碎片的办法是通过