《《操作系统》第4章存储管理.ppt》由会员分享，可在线阅读，更多相关《《操作系统》第4章存储管理.ppt（30页珍藏版）》请在三一办公上搜索。
1、操作系统原理Principles of Operating System,2,第4章 存储管理,存储器是计算机的记忆部件，计算机系统的主要用途是执行程序，在执行程序时，这些程序及其所访问的数据必须在内存里。由于内存通常太小不足以永久地容纳所有数据和程序，因此计算机系统必须提供外存（如硬盘）以扩充内存的技术。在现代计算机系统中，内存是一个关键性的资源。能否合理而有效地使用它，在很大程度上反映了操作系统的性能，并直接影响整个计算机系统作用的发挥。所以，存储管理是目前人们研究操作系统的中心问题之一。本章我们将讨论多种不同存储管理方法,3,4.4.1 存储器的层次,三级存储器结构 高速缓存（cache
2、）内存（primary storage）外存（secondary storage）,4,4.1.2 存储管理的功能,1.内存分配和回收内存的利用率与内存分配的技术、方式和策略有直接关系。2.内存保护内存保护就是确保多个进程都在各自分配到内存区域内操作，互不干扰，防止一个进程破坏其他进程的信息。3.内存扩充内存“扩充”包含了存储器利用的提高和扩充两方面的内容。为用户提供比内存物理空间大得多的地址空间。比较典型的内存扩充是虚拟存储器。4.地址映射地址映射就是将进程的逻辑地址变换为内存中的物理地址。我们需要实现从逻辑地址到物理地址的变换，即实现从虚地址到实地址的变换。这种变换就是重定位。,5,几个重
3、要的概念,逻辑地址逻辑地址就是指令在程序中的地址，源程序经编译（或解释）后编排的地址。逻辑地址也叫相对地址或虚拟地址。逻辑地址空间逻辑地址空间就是某程序的逻辑地址的集合，逻辑地址空间可简称为地址空间。物理地址物理地址就是进程中的指令和数据在内存中的地址，指令和数据存放在内存中的内存单元编号。物理地址也叫绝对地址或实地址。物理地址空间物理地址空间是指进程在内存中一系列存储信息的物理单元的集合。物理地址空间也叫存储空间，存储空间与地址空间既相互关联，又相互独立，是内存管理的核心概念。,6,4.1.4 重定位,为使程序正确执行。一个程序装入内存，要进行逻辑地址到物理地址的重定位，实现从逻辑地址到物理
4、地址的变换，重定位可分为静态重定位和动态重定位。静态重定位进程装入内存时，由装入程序对进程中的指令和数据的地址进行修改，将程序中的逻辑地址变换成物理地址。即物理地址基址+逻辑地址。,7,优点：简单，无需增加硬件就可以实现。缺点：要求连续的内存存储空间，程序装入内存后就不可移动，且难以做到程序和数据的共享，内存的利用率差。动态重定位如图4-3所示，进程装入内存时不定位，在指令执行期间CPU每次访问内存时进行重定位，这种定位方法需要硬件的支持，系统中需设置一个地址变换机构。,8,优点：内存空间的占有量可以改变，容易实现共享。缺点：需硬件支持，成本增加。动态重定位是一种允许进程在执行过程中在内存中移
5、动的技术，必须获得硬件地址变换机构的支持。在多任务操作系统中，多个进程在内存中并发执行，进程的创建与撤消，多个进程之间频繁的上下文切换，其内存分配呈现动态性和随机性。静态重定位仅适应于连续分配，不能满足多任务操作系统动态性和随机性的要求，因此多任务操作系统存储管理适合采用离散分配，必须采用动态重定位。,9,4.2 分区式存储管理,内存分配方式可分为连续分配方式和离散分配方式，本节将讨论连续分配方式。分区式存储管理是连续分配方式，为一个进程分配一个连续的存储空间。分区式存储管理支持多道程序系统和分时系统，但内存分配存在不可利用的内存空间，即碎片问题。碎片一般可分为内碎片和外碎片。前者是指分区内不
6、可利用的内存空间，后者是指分区之间难以利用的小空闲分区。内碎片和外碎片都可以降低内存的利用率，但外碎片对系统的危害更大。关于碎片问题将在各种内存分配方式中详细讨论。,10,单一连续分配,单一连续分配内存分配优缺点如下：优点：实现简单，不需要复杂的软、硬件支持。缺点：存在内碎片问题。资源利用率低，由于存储资源利用率低而造成其他资源利用率低（如CPU、外设等），特别是不允许多个进程并发运行，这是不容忽视的缺点。CP/M和DOS20以下的版本就是采用此种方式。,11,固定分区分配,固定分区(fixed partitioning)也叫静态分区，固定分区存储管理是实现多道程序设计和分时系统的简单存储管理
7、技术。如图4-5所示，固定分区就是预先把内存空间分割成若干个连续区域，我们称为分区。每个分区的大小可以相同也可以不同，但分区大小固定不变，操作系统占用一个分区，其余每个分区只能存储一个进程，而且进程也只能在它所驻留的分区中运行。固定分区的优缺点优点：易于实现，开销小，内存分配和回收算法简单，支持多任务。缺点：存在内碎片问题，造成内存的浪费。分区总数固定，限制了并发执行的进程数目。,12,4.2.3 动态分区,动态分区分配是根据进程的实际需要动态创建分区，为之分配连续的存储空间。分区大小正好适合进程的需要，可谓“量体裁衣”。与固定分区相比较，动态分区的优点是没有内碎片。但却引入了另一种碎片，即外
8、碎片。系统启动后，初始化程序将内存空间分为两个区域：系统区和用户区。以后每当有进程申请进入，系统就划出一个大小合适的区域给进程。每当一个进程完成后，系统就收回该区域。经过一段时间运行，系统就产生了多个动态分区。这时动态分区的分区分配方式就是寻找某个空闲分区，其大小需大于或等于进程的要求。若是大于进程要求，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为“已分配”，将该分区分配给进程，而另一个分区为余下部分并标记为“空闲”。当进程运行完成时，回收进程释放分区时要考虑一个重要问题，就是将相邻的空闲分区合并成一个大的空闲分区。,13,1空闲分区链表,每个空闲分区的前后两个单元，放置空闲分区
9、的说明信息和指针。如图所示，系统设立一个链首指针Free，指向第一个空闲分区。空闲分区排列需按照一定的规律（如按大小、按地址），分配进程可以依照空闲分区链表，来查找适合的空闲分区进行分配。,14,2.动态分区的分配算法,首次适应算法首次适应算法的空闲链是对空闲分区按照地址从低到高的顺序排列起来。为进程选择分区时总是按地址从低到高搜索，只要找到可以容纳该进程的空闲区，就把该空闲区切割出进程大小，分配给该进程，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败返回。其缺点是低址部分不断被划分，会留下许多难以利用的、很小的空闲分区（即碎片），而每次查找又
10、都是从低址部分开始，这无疑会增加查找可用空闲分区链时的开销。,15,循环首次适应算法循环首次适应算法的空闲链是对空闲分区按照地址从低到高的顺序排列起来（同上）。每次分区时，总是从上次查找结束的地方开始，只要找到一个足够大的空闲区，就把该空闲区切割出进程大小，分配给该进程，余下的空闲分区仍留在空闲链中。该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区。,16,最佳适应算法最佳适应算法的空闲链是按空闲区从小到大顺序排列。为进程选择分区时总是寻找其大小最接近进程所要求的存储区域。所谓“最佳”是指每次为进程分配内存时，总是把能满足要求、又是最小的空闲分区
11、分配给进程，避免“大材小用”。因为每次分配后所切割下来的剩余部分总是最小的，这样将加速碎片的形成。,17,最差适应算法最差适应算法的空闲链是按空闲区从大到小顺序排列。与最佳适应法相反，它为进程选择存储区时，总是寻找最大的空白区。最差适应算法可以延缓小空闲区的形成，但是无法保留大空闲区。这给以后到达尺寸大的进程分配内存空间带来了困难。内存紧缩(compaction)技术,18,3动态分区内存的分配与回收。,规定不再切割尺寸大小为size。从空闲分区链表中找到所需大小的分区。设进程请求的尺寸大小为u.size，空闲分区的大小可表示为m.size。若m.size-u.sizesize，说明多余部分太
12、小，可不再切割，将整个分区分配给进程；,19,内存回收 情况一：前邻空闲区，回收区与插入点的前一个空闲区F1相邻接。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区Fl的大小，大小为两者之和。情况二：前后邻空闲区，回收区同时与插入点的前空闲区F1和后空闲区F2两个空闲区邻接。此时将三个分区合并，使用前空闲区F1的首址作为新空闲区的首址，大小为三者之和，取消F2的表项。情况三：后邻空闲区，回收分区与插入点的后一空闲区F2相邻接。此时也可将两分区合并，形成新的空闲分区，用回收区的首址作为新空闲区的首址，大小为两者之和。情况四：前后不邻接空闲区，回收区不与空闲区邻
13、接。这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。,20,4.2.6 伙伴系统,其实现原理如下：一个伙伴系统内存的用户可用空间为2U。进程申请存储空间时，系统总是为其分配大小为2I的一个空闲分区。其中SIU，2S是系统允许的最小分区尺寸。在实际操作系统中，最小分区尺寸一般为212。如果进程申请的存储空间大小为K，且2I-1K2I，则将整个2I大小的分区分配给该进程；否则，该分区被分割成两个大小相等的伙伴分区，大小为2I-1；再判断K是否满足条件：2I-2K2I-1，若满足条件，则将两个伙伴中的任何一个分配给该进程。否则，将其中一个伙伴又分成两个大
14、小相等的伙伴分区；此过程一直继续进行，直到产生的分区满足条件I-JS并2I-J-1K2I-J，将2I-J大小的分区分配给该进程；当I-J-1S时，系统不再分割成两个大小相等的伙伴分区，将2S大小的分区分配给该进程。当进程执行完毕，释放一个尺寸为2I的分区时，系统用下面的算法回收该分区。如果被回收空闲分区没有空闲伙伴分区，那么保留该分区为一个独立的空闲分区，否则执行；合并回收分区及其伙伴分区，从而得到一个尺寸（2I+1）更大的回收空闲分区，转移到；,21,一个伙伴系统内存分配与回收的例子,22,伙伴系统克服了固定分区和动态分区存储管理技术的缺陷。但是伙伴系统存在一个问题，即内存空间需要不断地进行
15、分裂和合并，频繁的伙伴分区合并操作会浪费很多时间。一种直接的解决方法是延缓合并，不是在伙伴回收时进行合并，而是在必要时才进行伙伴合并。在现代操作系统中，更多地采用分页或分段存储管理技术，以及虚拟存储技术，但伙伴系统在一些操作系统中仍然是一种有效的存储管理方法。随着内存技术的发展，内存容量的不断扩大，伙伴系统作为存储分配的一种合理有效技术将得到进一步发展，比较典型的技术是Linux系统采用的伙伴堆算法，即伙伴系统和分页存储管理技术相结合,将在本书的Linux系统中讨论。,23,4.3 分页存储管理方式,分页存储管理允许进程的存储空间是离散的，把进程逻辑地址空间与实际存储空间分离，增加存储管理的灵
16、活性。将一个进程分散存储到许多不连续的空间，就可以避免内存碎片。根据分配时所采用的基本单位的不同，可将离散分配方式分为以下三种：分页存储管理、分段存储管理和段页式存储管理，其中段页式存储管理是前两种管理方法结合的产物。,24,4.3.1 页与页帧,在分页存储管理方式中，将一个进程的逻辑地址空间分成若干个大小相等的片，称为页(page)或页面。每页从0开始依次编号称为页号(page number)。相应地，内存空间也分成与页相同大小的若干个存储块，称为页帧(page frame)或物理块。每帧从0开始依次编号称为帧号或块号。页和帧为分页存储管理进行分配内存的基本单位。由于进程的最后一页经常装不满
17、一块，而形成不可利用的碎片，称为页内碎片。通常页的大小是2的幂，即在512B8KB之间。随着内存技术的发展，容量的不断增大，页的大小也应该适度增大为佳。,25,4.3.2 分页存储管理的实现,1分页存储管理的数据结构页表：如图所示，为了便于找到进程的每个页号对应的内存帧号，系统为每个进程建立一张页面映象表，简称页表。页表用于完成进程地址空间的逻辑页号到存储空间物理帧号的映射。系统为每一个进程建立一个页表，一个页号对应一个帧号。页表的表项也称为页描述子，一般包括：页号、帧号、权限等。物理页帧表：整个系统有一个物理页帧表，描述物理内存空间的分配使用状况，其数据结构可采用位示图和空闲页帧链表。,26
18、,2分页存储管理的实现分页存储管理可谓“见缝插针”，解决了外碎片问题，具体实现技术如下：逻辑地址空间分页，将用户进程的逻辑地址空间分成若干大小相等的页。内存存储空间分帧，将内存的用户区划分成与页大小相同的页帧。内存分配原则，以页帧为单位来分配内存，将进程若干个逻辑上连续的页面装入若干个离散的页帧中，由页表提供进程的页号到存储空间帧号的映射。在分页存储管理中，调度进程运行时，必须将进程的所有页面一次调入内存，若内存中没有足够的物理帧，则进程等待。,27,3分页存储管理的地址结构如果逻辑地址空间为2m，页大小为2n，那么逻辑地址的高m-n位表示页号p，而低n位表示偏移量d(offset)。如图4-
19、17所示，逻辑地址结构为页号p|偏移量d，物理地址结构为帧号f|偏移量d。若给定一个逻辑地址空间中的地址为A，页的大小为L，则页号p和偏移量d可按下式求得:p=A/Ld=A%L例如，其系统的页面大小为1KB，设A=2180，则由上式可以求得p 2，d132。,28,分页存储管理的地址变换机构,页表寄存器存放CPU正在处理的进程所对应页表的起始地址和该进程长度（总页数）。在分页存储管理系统中，其地址变换过程如图所示，指令所给出的逻辑地址：页号p|偏移量d。CPU中的内存管理单元(MMU)按页号通过查找页表得帧号，形成物理地址：帧号f|偏移量d。CPU每次访问一个在内存中的操作数，需要两次访问内存。,29,具有快表的地址变换过程如下：CPU给出有效地址后，由地址变换机构自动将页号送入快表，并将此页号与快表中的所有关键字（页号）进行比较，而且这种比较是同时进行的。若其中有与此页号相匹配的关键字，表示要访问页描述子在快表中。于是可直接读出该页所对应的帧号，则快速形成物理地址。这样就无需访问内存中的页表如果快表中没有记录，即TLB失效，从页表中查找所需的页描述子中的帧号，形成物理地址，同时更新快表，把该页描述子及相邻的页描述子写入快表。页号在快表（TLB）中被查找到的百分比称为命中率（h）。,30,4.3.4 页表结构,1.多级页表2.哈希页表3.反置页表,
