北京工业大学操作系统课OS3

122CONTENTSPAGE目录1存储管理概述实存储器管理虚拟存储器管理目录23第八章~第九章33TRANSITIONPAGE过渡•分级存储体系存储管理概述4第三章存储管理分级存储体系•存储器是计算机系统中的一种十分重要的资源•存储器的价格也十分昂贵快慢小大贵便宜5第三章存储管理程序执行过程•内存由一组字节组成，每个字节有一个地址•CPU根据PC寄存器的值从内存获取指令•这些指令可能还需要从内存中获取数据。6第三章存储管理存储管理的目的和任务•主存的分配和回收•地址映射/地址捆绑/重定位•存储保护•扩充主存77TRANSITIONPAGE过渡•存储管理相关概念•覆盖技术与交换技术•分区式存储管理•页式存储管理•段式存储管理•段页式存储管理实存储器管理技术88TRANSITIONPAGE过渡•存储管理相关概念•覆盖技术与交换技术•分区式存储管理•页式存储管理•段式存储管理•段页式存储管理实存储器管理技术9第三章存储管理逻辑地址物理地址•CPU生成的地址是逻辑地址•内存单元的地址是物理地址•程序生成的逻辑地址的集合是逻辑地址空间•所有物理地址的集合是物理地址空间10第三章存储管理地址映射/地址捆绑/重定位逻辑地址向物理地址的转换过程就是重定位11第三章存储管理重定位的发生时机•编译时•编译时就知道进程将在内存中驻留的地址，可以直接生成绝对代码。例如，MS-DOS的COM文件•加载时•编译生成可重定位代码，捆绑/重定位在加载时进行•静态重定位•执行时•若进程在执行时允许移动,则捆绑/重定位在执行时进行•动态重定位12第三章存储管理动态重定位的硬件实现•动态重定位是由内存管理单元（MMU）实现的•设置专门的寄存器，称为基址寄存器（重定位寄存器）和界限寄存器。•程序指令地址的重定位在指令执行的时候实现13第三章存储管理保护•保护操作系统不受用户进程的影响•保护用户进程不受其它用户进程影响•用基地址寄存器（重定位寄存器）和界限器存器1414TRANSITIONPAGE过渡•存储管理相关概念•覆盖技术与交换技术•分区式存储管理•页式存储管理•段式存储管理•段页式存储管理实存储器管理技术15第三章存储管理覆盖•在任何时候只能在内存中保留所需要的指令和数据。新的指令和数据可覆盖不用的指令和数据•不需要操作系统提供特别支持•例子•two-pass汇编程序符号表公共程序覆盖驱动程序16第三章存储管理交换•在内存不足的情况下，需要把一个进程整个换入和换出，称为交换•交换空间的分配•进程在被换出时分配交换空间每次换到不同的位置•进程分配固定的交换空间1717TRANSITIONPAGE过渡•存储管理相关概念•覆盖技术与交换技术•分区式存储管理•页式存储管理•段式存储管理•段页式存储管理实存储器管理技术18第三章存储管理为什么用分区式存储管理•前提•操作系统占用主存的固定部分•主存的其它部分被其它进程占用•采用多道程序设计可以提高CPU利用率•为了让主存中尽量多地保存进程而不会向互干扰，最简单的方法是将这一部分存储器分为有固定边界的区域。19第三章存储管理固定分区•把存储器分为大小相等的区•所需空间小于等于分区大小的进程可以调入可用分区•进程换入换出•所有的分区都是满的•没有进程处于就绪状态或运行状态20第三章存储管理固定分区的特点优点•简单缺点•程序可能太大而不能放入一个分区•程序员要设计一种覆盖的方法。•主存的应用效率低•小程序也要占用整个分区•限制了系统中可以激活的进程数目•因调入的数据小于分区而产生分区空间的浪费，称为内部碎片。•用不等长的分区来缓解，但不能根本解决。21第三章存储管理放置算法等长分区•主存中只要有可用的分区，进程就可以调入到那个分区中•如果所有的分区都被不能执行的进程占用，则其中的一个进程会被换出以放入新进程不等长分区•将进程放置在它最适合的最小的分区中•将所有进程排在一个队列中，当该调入一个进程进入主存中时，就选择可用的且可以保存这个进程的分区22第三章存储管理可变分区•系统中分区的长度和数目是可变的。•当有进程进入系统时,从主存按一定策略划出一块与进程所需空间相等的区分配给进程23第三章存储管理可变分区的特点•缺点•一开始运行得很好，但是在执行一段时间后,会出现一些小的洞。这种在分区外的洞称为外部碎片。•需要用内存紧缩（紧凑）方法解决。•分配多大的内存给进程。•简单方法：按照需求的大小进行分配。这样如果程序有可以动态增长的段，就有问题。•解决方法是为进程分配一些额外的内存。24第三章存储管理内存管理方法：位图•将内存按一定大小划分成分配单位，每个分配单位对应位图中的一位•用0表示空闲，1表示使用（或者反过来）•在内存大小确定的情况下，分配单位的大小决定了位图的大小。25第三章存储管理内存管理方法：链表•维护一个已分配和空闲内存段的链表。•每一个表项都有：P或H表示是进程还是空闲区域、起始地址、段长度和指向下一个表项的指针。26第三章存储管理链表方法的内存分配算法•从头至尾扫描，选择第一个足够的空间•按地址顺序排序首先适配•从上次放置位置开始找第一个足够的空间•按地址顺序排序下次适配•在整个存储区中找一个最接近需求的空间•按空间从小到大排序最佳适配•总是分配最大的空闲区•按空间从大到小排序最差适配27第三章存储管理实例：Buddy系统•固定分区和可变分区都有自己的优点和缺点•固定分区•固定分区机制限制了可以被激活的进程数目，并且对用户空间的是效率很低•可变分区•可变分区机制在维护上比较复杂，并且在紧凑时浪费处理器时间•Buddy系统是两者的结合28第三章存储管理实例：Buddy系统29第三章存储管理分区存储管理的问题•前面的存储器管理方式都要求一个进程在主存中占用连续的存储空间。•会产生小碎片，只能用紧凑的方式拼接成大的空间•开销大•如果进程可以分散到主存中不相邻的分区中，就不必进行紧凑。3030TRANSITIONPAGE过渡•存储管理相关概念•覆盖技术与交换技术•分区式存储管理•页式存储管理•段式存储管理•段页式存储管理实存储器管理技术31第三章存储管理页式存储管理•把主存分为定长的块•称为页框（帧）•把用户进程也分为与主存的块大小相等的块•称为页•内部碎片只在进程的最后一页中发生，没有外部碎片。•为页和页框分别编号，从0开始。32第三章存储管理如何实现地址重定位？1页=102433第三章存储管理页号页框号021524页表2000/1024=1…976页号页内位移5*1024+976=6096物理地址34第三章存储管理页表存储在什么地方？内存中有多少个页表？如何定位一个进程的页表？页表导致什么开销？35第三章存储管理硬件支持•内存管理单元（MMU）•在使用存储器时，逻辑地址不是直接送到内存总线上，而是送到内存管理单元（MMU）。•MMU由一个或一组芯片组成•其功能是把逻辑地址转换成物理地址•系统中设置一个页表寄存器PTR•用于存放进程页表的起始地址和长度•页表存放在内存中36第三章存储管理如何得到页号和页内位移•分页地址变换机构会自动将逻辑地址分为页号和页内地址位移两部分•如果页的大小是2的幂次就可以直接划分2000/1024=1…9760011111010000/10000000000=001…111101000037第三章存储管理地址映射过程001111101000010位页号页框号0000100011010101001011111010000①分页地址变换机构自动将逻辑地址分为页号和页内地址位移②以页号为索引去查询页表，得到页框号③页框号与页内地址位移相结合，获得物理地址38第三章存储管理页式存储管理内存保护•页表中增加保护位•读写•只读页号页框号000010001101010100读位写位00101139第三章存储管理页式存储管理共享和保护•代码共享的需求•可重入代码（纯代码）•例如•一个系统中有40个用户，每个执行一个文本编辑器•150k的代码+50k数据•40个用户需8000k•但是如果每个用户只保存自己的数据，文本编辑器作为共享代码则需2150k40第三章存储管理页式存储管理内存共享页号页框号000010001101010100读位写位00101141第三章存储管理页式存储管理的优缺点优点•碎片小，节省存储器空间•分页对程序员是透明的缺点•共享和保护不容易实现•程序员不能按照自己的方式组织程序4242TRANSITIONPAGE过渡•存储管理相关概念•覆盖技术与交换技术•分区式存储管理•页式存储管理•段式存储管理•段页式存储管理实存储器管理技术43第三章存储管理为什么需要段式管理•逻辑存储器是一维的，但是对于程序员来说，有两个或多个地址空间是有优势的•简化对变长的数据结构的管理•可以对程序分段编译再连接•有助于进程之间共享数据（例如共享库）•可以对不同的段实行不同的保护44第三章存储管理原理•让存储器提供多个相互独立的空间，称为段（segment）•每个段由0到最大的线性地址构成。•不同的段的长度不同，段的长度可以在运行期间改变。45第三章存储管理段表段号起始地址长度014001000163004002430040033200110044700100046第三章存储管理硬件支持•分段硬件负责将逻辑地址转换成物理地址•要求设置段基址寄存器和段界限寄存器47第三章存储管理地址映射段号起始地址长度0140010001630040024300400332001100447001000JMP2:2002:2004300+200=450048第三章存储管理段的保护•保护以段为单位•指令段只读或者只执行•数据段可读可写•段表加入相应位段号起始地址长度保护位014001000R16300400RW24300400W332001100RWX447001000X49第三章存储管理段的共享•以段为单位进行50第三章存储管理段式存储管理的优缺点优点•共享和保护容易实现•程序员可以按照自己的方式组织程序缺点•有碎片，浪费存储器空间5151TRANSITIONPAGE过渡•存储管理相关概念•覆盖技术与交换技术•分区式存储管理•页式存储管理•段式存储管理•段页式存储管理实存储器管理技术52第三章存储管理段页式存储原理•段页式管理是将用户的地址空间分段，段内按内存页框的大小分页。•逻辑地址由段号、段内页号和页内位移三部分组成。•操作系统在进行管理时，为每个进程维护一个段表和多个页表。•页表的结构与页式管理中的页表一样•段表中包含的是页表的起始地址和页表的长度及其它控制位。53第三章存储管理地址映射•段表?•段内页表?•如何进行地址映射?5454TRANSITIONPAGE过渡第五次作业55第三章存储管理•基础作业•1．内部碎片与外部碎片之间的区别？•2．内存按顺序有100k，500k，200k，300k，600k，用首次适应、最佳适应和最差适应如何放置212k，417k，112k，426k的进程？•3．假设一个有8个1k页面的逻辑地址空间，映射到一个32个页框的物理内存，问：逻辑地址多少位？物理地址多少位？56第三章存储管理•基础作业•4．（8.12）有段表段基地址长度02196001230014290100313275804195296•下面的物理地址是多少？•a)0,430;b)1,10;c)2,500;d)3,400;e)4,12257第三章存储管理•基础作业•5．在页面大小为4k的系统中，根据图中所示页表，下面的逻辑地址经过重定位之后的物理地址是什么？a)20;b)4100;c)8300•6．一台计算机为每个进程提供65536字节的地址空间，页面的大小为4k。一个程序有32768字节的正文，16386字节的数据，15870字节的堆栈，此程序是否能装入此地址空间？若页面大小为512字节呢？5858TRANSITIONPAGE过渡•程序局部性原理•请求页式存储管理基础•页表的其他形式•页面置换算法•请求段式存储管理虚拟存储器管理技术5959TRANSITIONPAGE过渡•程序局部性原理•请求页式存储管理基础•页表的