第5章 存储管理1

操作系统原理PrinciplesofOperatingSystem,主讲：孔宪君,第5章存储管理,存储器是计算机的记忆部件，计算机系统的主要用途是执行程序，在执行程序时，这些程序及其所访问的数据必须在内存里。由于内存通常太小不足以永久地容纳所有数据和程序，因此计算机系统必须提供外存（如硬盘）以扩充内存的技术。内存是一个关键性的资源。能否合理而有效地使用它，在很大程度上反映了操作系统的性能，并直接影响整个计算机系统作用的发挥。,5.1.1存储器的层次,三级存储器结构高速缓存（cache）内存（primarystorage）外存（secondarystorage）,5.1.2存储管理的功能,1.内存分配和回收内存的利用率与内存分配的技术、方式和策略有直接关系。2.内存保护内存保护就是确保多个进程都在各自分配到内存区域内操作，互不干扰，防止一个进程破坏其他进程的信息。3.内存扩充内存“扩充”包含了存储器利用的提高和扩充两方面的内容。为用户提供比内存物理空间大得多的地址空间。比较典型的内存扩充是虚拟存储器。4.地址映射地址映射就是将进程的逻辑地址变换为内存中的物理地址。我们需要实现从逻辑地址到物理地址的变换，即实现从虚地址到实地址的变换。这种变换就是重定位。,5.1.3存储空间与地址空间,逻辑地址逻辑地址就是指令在程序中的地址，源程序经编译（或解释）后编排的地址。逻辑地址也叫相对地址或虚拟地址。逻辑地址空间逻辑地址空间就是某程序的逻辑地址的集合，逻辑地址空间可简称为地址空间。物理地址物理地址就是进程中的指令和数据在内存中的地址，指令和数据存放在内存中的内存单元编号。物理地址也叫绝对地址或实地址。物理地址空间物理地址空间是指进程在内存中一系列存储信息的物理单元的集合。物理地址空间也叫存储空间，存储空间与地址空间既相互关联，又相互独立，是内存管理的核心概念。,6,5.1.4进程的装入方式,直接装入方式程序员编程或编译器编译时就知道进程将在内存中的驻留地址，那么就可以生成绝对代码。此时进程可以采用直接装入方式。如MS-DOS的命令文件（.COM）就是在编译时捆绑成绝对代码的。重定位装入方式如果在编译时编译器不知道进程将驻留在内存何处，那么编译器就必须生成可重定位代码。对这种情况，最后绑定会延迟到加载时才进行。此时进程可以采用重定位装入方式，重定位可分为静态重定位和动态重定位。,5.1.5重定位,静态重定位装入程序在装入进程时，一次性绑定（binding）进程在内存中的物理地址，即物理地址基址+逻辑地址。优点：简单，无需增加硬件就可以实现。缺点：要求连续的内存存储空间，程序装入内存后就不可移动，且难以做到程序和数据的共享，内存的利用率差,动态重定位进程在装入内存时不进行地址绑定，在指令执行期间CPU每次访问内存时进行地址重定位，这种重定位方法需要硬件的支持，系统中需设置一个地址变换机构。,优点：内存空间的占有量可以改变，容易实现共享。缺点：需硬件支持，成本增加。动态重定位是一种允许进程在执行过程中在内存中移动的技术，必须获得硬件地址变换机构的支持。在多任务操作系统中，多个进程在内存中并发执行，进程的创建与撤消，多个进程之间频繁的上下文切换，其内存分配呈现动态性和随机性。静态重定位仅适应于连续分配，不能满足多任务操作系统动态性和随机性的要求，因此多任务操作系统存储管理适合采用离散分配，必须采用动态重定位。,5.2分区式存储管理,内存分配方式可分为连续分配方式和离散分配方式。分区式存储管理是连续分配方式，为一个进程分配一个连续的存储空间。分区式存储管理支持多道程序系统和分时系统，但内存分配存在不可利用的内存空间，即碎片问题。碎片一般可分为内碎片和外碎片。,5.2.1单一连续分配,单一连续分配内存分配优缺点如下：优点：实现简单，不需要复杂的软、硬件支持。缺点：存在内碎片问题。资源利用率低，由于存储资源利用率低而造成其他资源利用率低。,5.2.2固定分区分配,固定分区(fixedpartitioning)也叫静态分区，固定分区存储管理是实现多道程序设计和分时系统的简单存储管理技术。如图所示，固定分区的优缺点优点：易于实现，开销小，内存分配和回收算法简单，支持多任务。缺点：存在内碎片问题，造成内存的浪费。分区总数固定，限制了并发执行的进程数目。,5.2.3动态分区,动态分区分配可谓“量体裁衣”。与固定分区相比较，动态分区的优点是没有内碎片。但却引入了另一种碎片，即外碎片。1空闲分区链表,2空闲分区链表,每个空闲分区的前后两个单元，放置空闲分区的说明信息和指针。如图所示，系统设立一个链首指针Free，指向第一个空闲分区。空闲分区排列需按照一定的规律（如按大小、按地址），分配进程可以依照空闲分区链表，来查找适合的空闲分区进行分配。,2.动态分区的分配算法,首次适应算法首次适应算法的空闲链是对空闲分区按照地址从低到高的顺序排列起来。为进程选择分区时总是按地址从低到高搜索，只要找到可以容纳该进程的空闲区，就把该空闲区切割出进程大小，分配给该进程，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败返回。其缺点是低址部分不断被划分，会留下许多难以利用的、很小的空闲分区（即碎片），而每次查找又都是从低址部分开始，这无疑会增加查找可用空闲分区链时的开销。,循环首次适应算法循环首次适应算法的空闲链是对空闲分区按照地址从低到高的顺序排列起来（同上）。每次分区时，总是从上次查找结束的地方开始，只要找到一个足够大的空闲区，就把该空闲区切割出进程大小，分配给该进程，余下的空闲分区仍留在空闲链中。该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区。,最佳适应算法最佳适应算法的空闲链是按空闲区从小到大顺序排列。为进程选择分区时总是寻找其大小最接近进程所要求的存储区域。所谓“最佳”是指每次为进程分配内存时，总是把能满足要求、又是最小的空闲分区分配给进程，避免“大材小用”。因为每次分配后所切割下来的剩余部分总是最小的，这样将加速碎片的形成。,最差适应算法最差适应算法的空闲链是按空闲区从大到小顺序排列。与最佳适应法相反，它为进程选择存储区时，总是寻找最大的空白区。最差适应算法可以延缓小空闲区的形成，但是无法保留大空闲区。这给以后到达尺寸大的进程分配内存空间带来了困难。内存紧缩(compaction)技术,3动态分区内存的分配与回收。,规定不再切割尺寸大小为size。从空闲分区链表中找到所需大小的分区。设进程请求的尺寸大小为u.size，空闲分区的大小可表示为m.size。若m.size-u.sizesize，说明多余部分太小，可不再切割，将整个分区分配给进程；,内存回收情况一：前邻空闲区，回收区与插入点的前一个空闲区F1相邻接。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区Fl的大小，大小为两者之和。情况二：前后邻空闲区，回收区同时与插入点的前空闲区F1和后空闲区F2两个空闲区邻接。此时将三个分区合并，使用前空闲区F1的首址作为新空闲区的首址，大小为三者之和，取消F2的表项。情况三：后邻空闲区，回收分区与插入点的后一空闲区F2相邻接。此时也可将两分区合并，形成新的空闲分区，用回收区的首址作为新空闲区的首址，大小为两者之和。情况四：前后不邻接空闲区，回收区不与空闲区邻接。这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。,5.2.4伙伴系统,其实现原理如下：一个伙伴系统内存的用户可用空间为2U。进程申请存储空间时，系统总是为其分配大小为2I的一个空闲分区。其中SIU，2S是系统允许的最小分区尺寸。在实际操作系统中，最小分区尺寸一般为212。如果进程申请的存储空间大小为K，且2I-1K2I，则将整个2I大小的分区分配给该进程；否则，该分区被分割成两个大小相等的伙伴分区，大小为2I-1；再判断K是否满足条件：2I-2K2I-1，若满足条件，则将两个伙伴中的任何一个分配给该进程。否则，将其中一个伙伴又分成两个大小相等的伙伴分区；此过程一直继续进行，直到产生的分区满足条件I-JS并2I-J-1K2I-J，将2I-J大小的分区分配给该进程；当I-J-1S时，系统不再分割成两个大小相等的伙伴分区，将2S大小的分区分配给该进程。当进程执行完毕，释放一个尺寸为2I的分区时，系统用下面的算法回收该分区。如果被回收空闲分区没有空闲伙伴分区，那么保留该分区为一个独立的空闲分区，否则执行；合并回收分区及其伙伴分区，从而得到一个尺寸（2I+1）更大的回收空闲分区，转移到；,一个伙伴系统内存分配与回收的例子,23,伙伴系统克服了固定分区和动态分区存储管理技术的缺陷。但是伙伴系统存在一个问题，即内存空间需要不断地进行分裂和合并，频繁的伙伴分区合并操作会浪费很多时间。一种直接的解决方法是延缓合并，不是在伙伴回收时进行合并，而是在必要时才进行伙伴合并。,24,5.2.5整理内存碎片5.2.6覆盖技术5.2.7交换技术覆盖技术与交换技术是在多道程序环境下扩充内存的两种方法。,在现代操作系统中，更多地采用分页或分段存储管理技术，以及虚拟存储技术，但伙伴系统在一些操作系统中仍然是一种有效的存储管理方法。随着内存技术的发展，内存容量的不断扩大，伙伴系统作为存储分配的一种合理有效技术将得到进一步发展，比较典型的技术是Linux系统采用的伙伴堆算法。,5.3分页存储管理方式,分页存储管理允许进程的存储空间是离散的，把进程逻辑地址空间与实际存储空间分离，增加存储管理的灵活性。将一个进程分散存储到许多不连续的空间，就可以避免内存碎片。离散分配方式分为以下三种：分页存储管理分段存储管理段页式存储管理,5.3.1页与页帧,在分页存储管理方式中，将一个进程的逻辑地址空间分成若干个大小相等的片，称为页(page)或页面。每页从0开始依次编号称为页号(pagenumber)。内存空间也分成与页相同大小的若干个存储块，称为页帧(pageframe)或物理块。每帧从0开始依次编号称为帧号或块号。页和帧为分页存储管理进行分配内存的基本单位。进程的最后一页经常装不满一块，而形成不可利用的碎片，称为页内碎片。通常页的大小是2的幂，即在512B8KB之间。随着内存技术的发展，容量的不断增大，页的大小也应该适度增大为佳。,5.3.2分页存储管理的实现,1分页存储管理的数据结构页表：如图所示，为了便于找到进程的每个页号对应的内存帧号，系统为每个进程建立一张页面映象表，简称页表。页表用于完成进程地址空间的逻辑页号到存储空间物理帧号的映射。系统为每一个进程建立一个页表，一个页号对应一个帧号。页表的表项也称为页描述子，一般包括：页号、帧号、权限等。物理页帧表：整个系统有一个物理页帧表，描述物理内存空间的分配使用状况，其数据结构可采用位示图和空闲页帧链表。,2分页存储管理的实现分页存储管理可谓“见缝插针”，解决了外碎片问题，具体实现技术如下：逻辑地址空间分页，将用户进程的逻辑地址空间分成若干大小相等的页。内存存储空间分帧，将内存的用户区划分成与页大小相同的页帧。内存分配原则，以页帧为单位来分配内存，将进程若干个逻辑上连续的页面装入若干个离散的页帧中，由页表提供进程的页号到存储空间帧号的映射。在分页存储管理中，调度进程运行时，必须将进程的所有页面一次调入内存，若内存中没有足够的物理帧，则进程等待。,3分页存储管理的地址结构如果逻辑地址空间为2m，页大小为2n，那么逻辑地址的高m-n位表示页号p，而低n位表示偏移量d(offset)。如图4-17所示，逻辑地址结构为页号p|偏移量d，物理地址结构为帧号f|偏移量d。若给定一个逻辑地址空间中的地址为A，页的大小为L，则页号p和偏移量d可按下式求得:p=A/Ld=A%L例如，其系统的页面大小为1KB，设A=2180，则由上式可以求得p2，d132。,5.3.3分页存储管理的地址变换机构,页表寄存器存放CPU正在处理的进程所对应页表的起始地址和该进程长度（总页数）。在分页存储管理系统中，其地址变换过程如图所示，指令所给出的逻辑地址：页号p|偏移量d。CPU中的内存管理单元(MMU)按页号通过查找页表得帧号，形成物理地址：帧号f|偏移量d。CPU每次访问一个在内存中的操作数，需要两次访问内存。,32,例如，某分页存储管理系统中，逻辑地址长度为16位，每页4KB。假定某用户进程一共6页，已经全部换入内存，且第0、1、2、3、4、5页依次存放在内存帧的帧号为3、6、9、11、8、12中。设逻辑地址为5A5CH，如图所示其对应的物理地址求解如下：,该分页系统的逻辑地址结构为:页号p（4位）|偏移量d（12位），逻辑地址为5A5CH的页号p=5，该页存放在12号内存帧中。物理地址结构为：帧号f|偏移量d，求得对应的物理地址为CA5CH。,具有快表的地址变