操作系统内存管理.doc

《操作系统内存管理.doc》由会员分享，可在线阅读，更多相关《操作系统内存管理.doc（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、. .操作系统存管理 1. 存管理法 存管理主要包括虚地址、地址变换、存分配和回收、存扩大、存共享和保护等功能。 2. 连续分配存储管理式 连续分配是指为一个用户程序分配连续的存空间。连续分配有单一连续存储管理和分区式储管理两种式。2.1 单一连续存储管理 在这种管理式中，存被分为两个区域：系统区和用户区。应用程序装入到用户区，可使用用户区全部空间。其特点是，最简单，适用于单用户、单任务的操作系统。CPM和 DOS20以下就是采用此种式。这种式的最大优点就是易于管理。但也存在着一些问题和缺乏之处，例如对要求存空间少的程序，造成存浪费；程序全部装入，使得很少使用的程序局部也占用定数量的存。2.2

2、 分区式存储管理 为了支持多道程序系统和分时系统，支持多个程序并发执行，引入了分区式存储管理。分区式存储管理是把存分为一些大小相等或不等的分区，操作系统占用其中一个分区，其余的分区由应用程序使用，每个应用程序占用一个或几个分区。分区式存储管理虽然可以支持并发，但难以进展存分区的共享。 分区式存储管理引人了两个新的问题：碎片和外碎片。 碎片是占用分区未被利用的空间，外碎片是占用分区之间难以利用的空闲分区(通常是小空闲分区)。 为实现分区式存储管理，操作系统应维护的数据构造为分区表或分区链表。表中各表项一般包括每个分区的起始地址、大小及状态(是否已分配)。 分区式存储管理常采用的一项技术就是存紧缩

3、(paction)。2.2.1 固定分区(nxedpartitioning)。 固定式分区的特点是把存划分为假设干个固定大小的连续分区。分区大小可以相等：这种作法只适合于多个一样程序的并发执行(处理多个类型一样的对象)。分区大小也可以不等：有多个小分区、适量的中等分区以及少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。 优点：易于实现，开销小。 缺点主要有两个：碎片造成浪费；分区总数固定，限制了并发执行的程序数目。2.2.2动态分区(dynamic partitioning)。 动态分区的特点是动态创立分区：在装入程序时按其初始要求分配，或在其执行过程过系统调用进展分配或改变分区

4、大小。与固定分区相比较其优点是：没有碎片。但它却引入了另一种碎片外碎片。动态分区的分区分配就是寻找某个空闲分区，其大小需大于或等于程序的要求。假设是大于要求，那么将该分区分割成两个分区，其中一个分区为要求的大小并标记为“占用，而另一个分区为余下局部并标记为“空闲。分区分配的先后次序通常是从存低端到高端。动态分区的分区释放过程中有一个要注意的问题是，将相邻的空闲分区合并成一个大的空闲分区。下面列出了几种常用的分区分配算法： 最先适配法(nrst-fit)：按分区在存的先后次序从头查找，找到符合要求的第一个分区进展分配。该算法的分配和释放的时间性能较好，较大的空闲分区可以被保存在存高端。但随着低端

5、分区不断划分会产生较多小分区，每次分配时查找时间开销便会增大。 下次适配法(循环首次适应算法 next fit)：按分区在存的先后次序，从上次分配的分区起查找(到最后区时再从头开场，找到符合要求的第一个分区进展分配。该算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大空闲分区不易保存。 最正确适配法(best-fit)：按分区在存的先后次序从头查找，找到其大小与要求相差最小的空闲分区进展分配。从个别来看，外碎片较小；但从整体来看，会形成较多外碎片优点是较大的空闲分区可以被保存。 最坏适配法(worst- fit)：按分区在存的先后次序从头查找，找到最大的空闲分区进展分配。根本不留下

6、小空闲分区，不易形成外碎片。但由于较大的空闲分区不被保存，当对存需求较大的进程需要运行时，其要求不易被满足。 2.3 伙伴系统 固定分区和动态分区式都有缺乏之处。固定分区式限制了活动进程的数目，当进程大小与空闲分区大小不匹配时，存空间利用率很低。动态分区式算法复杂，回收空闲分区时需要进展分区合并等，系统开销较大。伙伴系统式是对以上两种存式的一种折衷案。 伙伴系统规定，无论已分配分区或空闲分区，其大小均为 2 的 k 次幂，k 为整数， lkm，其中： 21 表示分配的最小分区的大小， 2m 表示分配的最大分区的大小， 通常 2m是整个可分配存的大小。 假设系统的可利用空间容量为2m个字， 那么

7、系统开场运行时， 整个存区是一个大小为2m的空闲分区。在系统运行过中， 由于不断的划分，可能会形成假设干个不连续的空闲分区，将这些空闲分区根据分区的大小进展分类，对于每一类具有一样大小的所有空闲分区，单独设立一个空闲分区双向链表。这样，不同大小的空闲分区形成了k(0km)个空闲分区链表。 分配步骤： 当需要为进程分配一个长度为n 的存储空间时: 首先计算一个i 值，使 2(i1) <n 2i， 然后在空闲分区大小为2i的空闲分区链表中查找。 假设找到，即把该空闲分区分配给进程。 否那么，说明长度为2i的空闲分区已经耗尽，那么在分区大小为2(i1)的空闲分区链表中寻找。 假设存在 2(i1

8、)的一个空闲分区，那么把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于配， 而把另一个参加分区大小为2i的空闲分区链表中。 假设大小为2(i1)的空闲分区也不存在，那么需要查找大小为2(i2)的空闲分区， 假设找到那么对其进展两次分割： 第一次，将其分割为大小为 2(i1)的两个分区，一个用于分配，一个参加到大小为 2(i1)的空闲分区链表中； 第二次，将第一次用于分配的空闲区分割为 2i的两个分区，一个用于分配，一个参加到大小为 2i的空闲分区链表中。 假设仍然找不到，那么继续查找大小为 2(i3)的空闲分区，以此类推。 由此可见，在最坏的情况下，可能需要对 2k的

9、空闲分区进展 k 次分割才能得到所需分区。 与一次分配可能要进展屡次分割一样，一次回收也可能要进展屡次合并，如回收大小为2i的空闲分区时，假设事先已存在2i的空闲分区时，那么应将其与伙伴分区合并为大小为2i1的空闲分区，假设事先已存在2i1的空闲分区时，又应继续与其伙伴分区合并为大小为2i2的空闲分区，依此类推。 在伙伴系统中，其分配和回收的时间性能取决于查找空闲分区的位置和分割、合并空闲分区所花费的时间。与前面所述的多种法相比较，由于该算法在回收空闲分区时，需要对空闲分区进展合并，所以其时间性能比前面所述的分类搜索算法差，但比顺序搜索算法好，而其空间性能那么远优于前面所述的分类搜索法，比顺序

10、搜索法略差。 需要指出的是，在当前的操作系统中，普遍采用的是下面将要讲述的基于分页和分段机制的虚拟存机制，该机制较伙伴算法更为合理和高效，但在多处理机系统中，伙伴系统仍不失为一种有效的存分配和释放的法，得到了大量的应用。 2.4 存紧缩 存紧缩：将各个占用分区向存一端移动，然后将各个空闲分区合并成为一个空闲分区。 这种技术在提供了某种程度上的灵活性的同时，也存在着一些弊端，例如：对占用分区进展存数据搬移占用CPU时间；如果对占用分区中的程序进展“浮动，那么其重定位需要硬件支持。 紧缩时机：每个分区释放后，或存分配找不到满足条件的空闲分区时。 图8.12 堆构造的存储管理的分配算法： 在动态存储

11、过程中，不管哪个时刻，可利用空间都是-一个地址连续的存储区，在编译程序中称之为堆，每次分配都是从这个可利用空间中划出一块。其实现方法是：设立一个指針，称之为堆指针，始终指向堆的最低或锻联地址。当用户申请N个单位的存储块时，堆指针向高地址或 低地址称动N个存储单位，而移动之前的堆指针的值就是分配给用户的占用块的初始地址。例如，某个串处理系统中有A、B、C、D这4个串，其串值长度分别為12,6,10和8. 假设堆指针free的初值为零，那么分配给这4个串值的存储空间的初始地址分别为0.12.18和28,如图8.12(a)和b)所示，分配后的堆指针的值为36。 因此，这种堆构造的存储管理的分配算法非

12、常简单， 释放存空间执行存紧缩： 回收用户释放的空闲块就比较麻烦.由于系统的可利用空间始终是一个绝址连续的存储块，因此回收时必须将所释放的空间块合并到整个堆上去才 能重新使用，这就是存储策缩的任务.通常，有两种做法： 一种是一旦有用户释放存储块即进展回收紧缩，例始，图8.12 (a)的堆，在c串释放存储块时即回收紧缩，例如图8.12 (c)的堆，同时修改串的存储映像成图8.12(d)的状态； 另一种是在程序执行过程中不回收用户随时释放的存储块，直到可利用空同不够分配或堆指针指向最高地址时才进展存储紧缩。此时紧缩的目的是将堆中所有的空间块连成一块，即将所有的占用块部集中到 可利用空间的低地地区，

13、而剩余的高地址区成为一整个地继连续的空闲块，如图8.13所示，其中a为紧缩前的状态，(b)为紧缩后的状态 图8.13 a 紧缩前 b紧缩后 和无用单元收集类似，为实现存储紫编,首先要对占用块进展“标志，标志算法和无用单元收集类同(存储块的构造可能不同,其次需进展以下4步雄作： 1)计算占用块的新地址。从最低地址开场巡査整个存储空间，对每一个占用块找到它在紧缩后的新地址。 为此,需设立两个指针随巡查向前移动,这两个指针分别指示占用 块在紧缩之前和之后的原地址和新地址。因此,在每个占用块的第-个存储单位中，除了 设立长度域(存储该占用换的大小和标志域(存储区别该存储块是占用块或空闲块的标 志之外，

14、还需设立一个新地址城，以存储占用块在紧缩后应有的新地址，即建立一新， 旧地址的对照表m (2)修改用户触初始变量表，以便在存储紧缩后用户程序能继续正常运行*。 (3)检查每个占用块中存储的数据， 假设有指向其他存储换的指针，那么需作相应修改. (4)将所有占用块迁移到新地址走，这实质上是作传送数据的工作。 至此，完成了存储紧缩的操作，最后,将堆指针赋以新值即紧缩后的空闲存储区的最低地址。 可见,存储紧缩法比无用单元收集法更为复杂，前者不仅要传送数据进展占用块迁移，而且还有需要修改所有占用块中的指针值。因此，存储紧缩也是个系统操作，且非不得已就不用。 3. 覆盖和交换技术 3.1 覆盖技术 引入

15、覆盖 (overlay)技术的目标是在较小的可用存中运行较大的程序。这种技术常用于多道程序系统之中，与分区式存储管理配合使用。 覆盖技术的原理：一个程序的几个代码段或数据段，按照时间先后来占用公共的存空间。将程序必要局部(常用功能)的代码和数据常驻存；可选局部(不常用功能)平时存放在外存(覆盖文件)中，在需要时才装入存。不存在调用关系的模块不必同时装入到存，从而可以相互覆盖。 在任时候只在存中保存所需的指令和数据；当需要其它指令时，它们会装入到刚刚不再需要的指令所占用的存空间； 如在同一时刻，CPU只能执行B，C中某一条。B，C之间就可以做覆盖。 覆盖技术的缺点是编程时必须划分程序模块和确定程

16、序模块之间的覆盖关系，增加编程复杂度；从外存装入覆盖文件，以时间延长换取空间节省。 覆盖的实现式有两种：以函数库式实现或操作系统支持。3.2 交换技术 交换 (swapping)技术在多个程序并发执行时，可以将暂时不能执行的程序进程送到外存中，从而获得空闲存空间来装入新程序进程，或读人保存在外存中而处于就绪状态的程序。交换单位为整个进程的地址空间。交换技术常用于多道程序系统或小型分时系统中，因为这些系统大多采用分区存储管理式。与分区式存储管理配合使用又称作“对换或“滚进滚出(roll-inroll-out)。 原理：暂停执行存中的进程，将整个进程的地址空间保存到外存的交换区中换出swap ou

17、t，而将外存中由阻塞变为就绪的进程的地址空间读入到存中，并将该进程送到就绪队列换入swap in。 交换技术优点之一是增加并发运行的程序数目，并给用户提供适当的响应时间；与覆盖技术相比交换技术另一个显著的优点是不影响程序构造。交换技术本身也存在着缺乏，例如：对换人和换出的控制增加处理器开销；程序整个地址空间都进展对换，没有考虑执行过程中地址访问的统计特性。3.3 覆盖与交换比较 1与覆盖技术相比，交换不要求程序员给出程序段之间的覆盖构造。 2交换主要是在进程与作业之间进展，而覆盖那么主要在同一作业或进程进展。 另外覆盖只能覆盖那些与覆盖程序段无关的程序段。4. 页式和段式存储管理 在前面的几种

18、存储管理法中，为进程分配的空间是连续的，使用的地址都是物理地址。如果允将一个进程分散到多不连续的空间，就可以防止存紧缩，减少碎片。基于这一思想，通过引入进程的逻辑地址，把进程地址空间与实际存储空间别离，增加存储管理的灵活性。地址空间和存储空间两个根本概念的定义如下：地址空间：将源程序经过编译后得到的目标程序，存在于它所限定的地址围，这个围称为地址空间。地址空间是逻辑地址的集合。存储空间：指主存中一系列存储信息的物理单元的集合，这些单元的编号称为物理地址存储空间是物理地址的集合。根据分配时所采用的根本单位不同，可将离散分配的管理式分为以下三种：页式存储管理、段式存储管理和段页式存储管理。其中段页

19、式存储管理是前两种结合的产物。 5. 页式存储管理4.1 根本原理 将程序的逻辑地址空间划分为固定大小的页(page)，而物理存划分为同样大小的页框(pageframe)。程序加载时，可将任意一页放人存中任意一个页框，这些页框不必连续，从而实现了离散分配。该法需要CPU的硬件支持，来实现逻辑地址和物理地址之间的映射。在页式存储管理式中地址构造由两部构成，前一局部是页号，后一局部为页地址w位移量，如图4所示： 页式管理式的优点是： 1没有外碎片，每个碎片不超过页大比前面所讨论的几种管理式的最大进步是， 2一个程序不必连续存放。 3便于改变程序占用空间的大小(主要指随着程序运行，动态生成的数据增多

20、，所要求的地址空间相应增长)。 缺点是：要求程序全部装入存，没有足够的存，程序就不能执行。4.2 页式管理的数据构造 在页式系统中进程建立时，操作系统为进程中所有的页分配页框。当进程撤销时收回所有分配给它的页框。在程序的运行期间，如果允进程动态地申请空间，操作系统还要为进程申请的空间分配物理页框。操作系统为了完成这些功能，必须记录系统存中实际的页框使用情况。操作系统还要在进程切换时，正确地切换两个不同的进程地址空间到物理存空间的映射。这就要求操作系统要记录每个进程页表的相关信息。为了完成上述的功能，个页式系统中，一般要采用如下的数据构造。 进程页表：完成逻辑页号(本进程的地址空间)到物理页面号

21、(实际存空间，也叫块号)的映射。 每个进程有一个页表，描述该进程占用的物理页面及逻辑排列顺序，如图： 图4-1 页表 物理页面表：整个系统有一个物理页面表，描述物理存空间的分配使用状况，其数据构造可采用位示图和空闲页链表。 对于位示图法，即如果该页面已被分配，那么对应比特位置1，否置0. 图4-2 页面表 请求表：整个系统有一个请求表，描述系统各个进程页表的位置和大小，用于地址转换也可以结合到各进程的PCB(进程控制块)里。如图： 图4-3 请求表4.3 页式管理地址变换 在页式系统中，指令所给出的地址分为两局部：逻辑页号和页地址。 原理：CPU中的存管理单元(MMU)按逻辑页号通过查进程页表

22、得到物理页框号，将物理页框号与页地址相加形成物理地址(见图4-4)。 逻辑页号，页偏移地址>查进程页表，得物理页号>物理地址： 图4-4 页式管理的地址变换 上述过程通常由处理器的硬件直接完成，不需要软件参与。通常，操作系统只需在进程切换时，把进程页表的首地址装入处理器特定的存放器中即可。一般来说，页表存储在主存之中。这样处理器每访问一个在存中的操作数，就要访问两次存： 第一次用来查找页表将操作数的 逻辑地址变换为物理地址； 第二次完成真正的读写操作。 这样做时间上消耗重。为缩短查找时间，可以将页表从存装入CPU部的关联存储器(例如，快表) 中，实现按容查找。此时的地址变换过程是：

23、在CPU给出有效地址后，由地址变换机构自动将页号送人快表，并将此页号与快表中的所有页号进展比较，而且这 种比较是同时进展的。假设其中有与此相匹配的页号，表示要访问的页的页表项在快表中。于是可直接读出该页所对应的物理页号，这样就无需访问存中的页表。由于关联存储器的访问速度比存的访问速度快得多。 5. 段式存储管理5.1 根本原理 在段式存储管理中，将程序的地址空间划分为假设干个段(segment)，这样每个进程有一个二维的地址空间。在前面所介绍的动态分区分配式中，系统为整个进程分配一个连续的存空间。而在段式存储管理系统中，那么为每个段分配一个连续的分区，而进程中的各个段可以不连续地存放在存的不同

24、分区中。程序加载时，操作系统为所有段分配其所需存，这些段不必连续，物理存的管理采用动态分区的管理法。 在为某个段分配物理存时，可以采用首先适配法、下次适配法、最正确适配法等法。 在回收某个段所占用的空间时，要注意将收回的空间与其相邻的空间合并。 段式存储管理也需要硬件支持，实现逻辑地址到物理地址的映射。 程序通过分段划分为多个模块，如代码段、数据段、共享段：可以分别编写和编译可以针对不同类型的段采取不同的保护可以按段为单位来进展共享，包括通过动态进展代码共享 这样做的优点是：可以分别编写和编译源程序的一个文件，并且可以针对不同类型的段采取不同的保护，也可以按段为单位来进展共享。 总的来说，段式

25、存储管理的优点是：没有碎片，外碎片可以通过存紧缩来消除；便于实现存共享。缺点与页式存储管理的缺点一样，进程必须全部装入存。5.2 段式管理的数据构造 为了实现段式管理，操作系统需要如下的数据构造来实现进程的地址空间到物理存空间的映射，并跟踪物理存的使用情况，以便在装入新的段的时候，合理地分配存空间。进程段表：描述组成进程地址空间的各段，可以是指向系统段表中表项的索引。每段有段基址(baseaddress)，即段地址。 在系统中为每个进程建立一段映射表，如图：系统段表：系统所有占用段已经分配的段。空闲段表：存中所有空闲段，可以结合到系统段表中。5.3 段式管理的地址变换 图45 段式管理的地址变

26、换 在段式 管理系统中，整个进程的地址空间是二维的，即其逻辑地址由段号和段地址两局部组成。为了完成进程逻辑地址到物理地址的映射，处理器会查找存中的段表，由段号得到段的首地址，加上段地址，得到实际的物理地址(见图45)。这个过程也是由处理器的硬件直接完成的，操作系统只需在进程切换时，将进程段表的首地址装入处理器的特定存放器当中。这个存放器一般被称作段表地址存放器。 6. 页式和段式管理的区别 页式和段式系统有多相似之处。比方，两者都采用离散分配式，且都通过地址映射机构来实现地址变换。但概念上两者也有很多区别，主要表现在： 1)、需求：是信息的物理单位，分页是为了实现离散分配式，以减少存的碎片，提

27、高存的利用率。或者说，分页仅仅是由于系统管理的需要，而不是用户的需要。段是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了更好地满足用户的需要。 一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。 2)、大小：页大小固定且由系统决定，把逻辑地址划分为页号和页地址两局部，是由机器硬件实现的。段的长度不固定，且决定于用户所编写的程序，通常由编译系统在对源程序进展编译时根据信息的性质来划分。 3)、逻辑地址表示：页式系统地址空间是一维的，即单一的线性地址空间，程序员只需利用一个标识符，即可表示一个地址。分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段地址。 4)、比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。. .word.zl.