操作系统_full第4章存储器管理

《操作系统_full第4章存储器管理》由会员分享，可在线阅读，更多相关《操作系统_full第4章存储器管理（164页珍藏版）》请在金锄头文库上搜索。

1、第4章 存储器管理,第4章 存储器管理,用户程序的主要处理阶段 连续分配方式 离散分配方式（分页式、分段式、页段式） 虚拟存储器的基本特征,存储器管理的功能,存储分配和回收：是存储管理的主要内容。讨论其算法和相应的数据结构。 地址变换：可执行文件生成中的链接技术、程序加载时的重定位技术，进程运行时硬件和软件的地址变换技术和机构。 存储共享和保护：代码和数据共享，对地址空间的访问权限（读、写、执行）。 存储器扩充：它涉及存储器的逻辑组织和物理组织。 由应用程序控制：覆盖； 由OS控制：交换（整个进程空间），请求调入和预调入（部分进程空间）,逻辑地址空间与物理地址空间,逻辑地址,也称虚地址（vir

2、tual address）、相对地址 由CPU执行指令时生成的地址（本条指令所需数据的地址或下一条指令的地址） 物理地址,也称绝对地址、实地址 实际的内存单元地址,逻辑地址和物理地址,将逻辑地址空间与物理地址空间相分离，是内存管理的核心。 逻辑地址（虚地址）与物理地址是相同: 地址映像工作在编译阶段或加载阶段完成 重定位 进程的逻辑地址空间不同于物理地址空间，所以存储管理模块（MMU）要解决逻辑地址到物理地址的映射问题 也称地址映射、地址映像 在执行阶段完成,地址空间,4.1 程序的装入和链接,编程得到可执行文件的步骤：编译、链接、装入。 编辑：得到如test.cpp ,a.asm等源文件 装

3、入模块再由OS装入内存，成为进程。,4.1 程序的装入和链接,4.1.1 程序的装入,1.绝对装入(absolute loading) 编译程序知道程序将驻留在内存的地址，产生绝对地址的目标代码； 绝对装入模块装入时直接定位在上述内存地址，不需修改程序和数据的地址。 优点：装入过程简单。 缺点：过于依赖于硬件结构，不适于多道程序系统。,load,在多任务下OS无法保证程序每次装入同一位置，比如下次装在1000开始,2. 可重定位装入(relocatable loading) 在多道程序环境下，目标模块的起始地址通常从0开始，程序的其它地址也都是相对于起始地址计算的。装入时采用可重定位装入。 在

4、可执行文件中，列出各个需要重定位的地址单元和相对地址值（可重定位表），装入时再根据所定位的内存地址去修改每个重定位地址项，添加相应偏移量。,4.1.1 程序的装入,代码部分,头部分,例：,200,（2）装入,（3）OS根据读入 的头对内存浮动项 装配,JMP(1200),1300,头标志,（1）头部分由 OS读入,4.1.1 程序的装入,优点： 不需硬件支持，可以装入有限多道程序。 缺点： 一个程序通常需要占用连续的内存空间，程序装入内存后不能移动。不易实现共享。 地址变换是由装入程序在装入目标模块时一次完成，进程装入内存后不能移动，故称为静态重定位。,3. 动态运行时装入(dynamic r

5、un-time loading) 进程开始执行时，未全部装入内存，而是部分装入，运行时，需要哪个模块再装入哪个模块。 程序装入内存后，并不立即将相对地址转换为绝对地址，地址转换推迟到程序真正要执行时才进行，即动态重定位。 装入内存中进程的所有地址都是相对的。 优点： OS可以将一个程序分散存放于不连续的内存空间，可以移动程序，有利于实现共享。 能够支持程序执行中产生的地址引用，如指针变量（而不仅是生成可执行文件时的地址引用） 缺点：需要硬件支持（通常是CPU），OS实现较复杂是虚拟存储的基础,4.1.1 程序的装入,4.1.2 程序的链接,源程序经过编译后，得到一组目标模块，再利用链接程序将这

6、组目标模块链接，形成装入模块，根据链接时间的不同，链接分为： 静态链接 装入时动态链接 运行时动态链接,4.1.2 程序的链接,1. 静态链接(static-linking) 在程序运行前，先将各目标模块及它们所需的库函数，链接成一个完整的装入模块，以后不再拆开。要解决两个问题： 修改相对地址 变换外部调用符号 对多用户、多任务系统显然有冗余，比如多个用户调用了sin(x)，则每个目标代码中都有这部分代码，装入到内存则也都有这部分代码。,2. 装入时动态链接(dynamic-linking) 源程序编译得到的目标模块是在装入内存时，边装入边链接的，即在装入一个目标模块时，若发现一个外部模块调用

7、事件，装入程序去找出相应的外部目标模块，并将它装入内存，同时修改相对地址。 优点 共享：多个进程可以共用一个目标模块，节省内存，减少文件交换。 便于修改和更新。各目标模块是分开存放的，便于修改。,4.1.2 程序的链接,3. 运行时动态链接（Run-time Dynamic Linking) 应用程序运行时，每次运行的模块可能不同。但事先又无法知道，在前两种链接方式中，只能将所有模块都装入内存，并在装入时都链接在一起。显然低效。 运行时动态链接是将某些模块的链接推迟到执行时。即，执行时发现调用的模块未被装入，由OS找到该模块并装入，并将其链接到调用者模块上。 优点： 部分装入：一个进程可以将多

8、种操作分散在不同的DLL中实现，而只将与当前操作相对应的DLL装入内存。 便于局部代码修改：即便于代码升级和代码重用；只要函数的接口参数（输入和输出）不变，则修改函数及其DLL，无需对可执行文件重新编译或链接。 便于适应运行环境：调用不同的DLL，就可以适应多种使用环境和提供不同功能。如：不同的显示卡只需厂商为其提供特定的DLL，而OS和应用程序不必修改。 缺点： 链接开销：增加了程序执行时的链接开销； 管理开销：程序由多个文件组成，增加管理复杂度。,4.1.2 程序的链接,地址生成,地址安全检查,逻辑地址空间由base基址寄存器和limit界址寄存器定义 仅OS能设置base和limit 特

9、权指令,地址安全检查,在用户模式中验证所产生的地址 如果发现不好的地址，中断进入内核,例：在虚拟内存管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是 A 编辑 B 编译 C 链接 D装载 答 C,4.2 连续分配存储管理方式,连续分配是指为一个用户进程分配一个连续的内存空间。可进一步分为： 单一连续分配 固定分区分配 动态分区分配 动态重定位分区分配,4.2.1 单一连续分配,内存分为两个区域：系统区，用户区。应用程序装入到用户区，可使用用户区全部空间。未采取存储保护措施。 最简单，适用于单用户、单任务的OS。CP/M和MS-DOS 优点： 易于管理。 缺点： 对要求内存空

10、间少的程序，造成内存浪费； 程序全部装入，很少使用的程序部分也占用内存,分区式存储管理,为了支持多道程序系统和分时系统，支持多个程序并发执行，引入了分区式存储管理。 分区式存储管理是把内存分为一些大小相等或不等的分区，操作系统占用其中一个分区，其余的分区由应用程序使用，每个应用程序占用一个或几个分区。 内碎片和外碎片： 前者是占用分区之内未被利用的空间 后者是占用分区之间难以利用的空闲分区（通常是小空闲分区）。,4.2.2 固定分区分配(fixed partitioning),最简单的一种运行多道程序的存储管理方式 把内存划分为若干个固定大小的连续分区，每个分区只装入一个作业。 划分分区的方法

11、 分区大小相等：只适合于多个相同进程的并发执行（处理多个类型相同的对象）。 分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。,单一连续分配,固定分区分配 （分区相等）,固定分区分配 （分区不等）,4.2.2 固定分区分配(fixed partitioning),内存分配 OS将分区按大小进行排队，并建立一张分区使用表或位示图。 可以和覆盖、交换技术配合使用运行较大的用户进程。 优点： 易于实现，开销小。 缺点： 内碎片造成浪费，分区总数固定，限制了并发执行的程序数目。,4.2.3 动态分区分配(dynamic partitioning),

12、4.2.3 动态分区分配(dynamic partitioning),动态分区分配是指OS根据进程的实际需要为各进程分配连续的物理内存。 分区分配中的数据结构 为了管理内存空闲分区建立了空闲分区表或空闲分区链表。 表中各表项一般包括每个分区的起始地址、大小及状态(是否已分配)。 分区表中，表项数目随着内存的分配和释放而动态改变，可以规定最大表项数目。 分区表可以划分为两个表格：空闲分区表和占用分区表。从而减小每个表格长度。空闲分区表中按不同分配算法对表项排序。,分区分配算法： 某个新作业装入内存，需寻找一个空闲分区，其大小需大于或等于进程的要求。 若是大于要求，则将该分区分割成两个分区，其中一

13、个分区为要求的大小并标记为“占用”，而另一个分区为余下部分并标记为“空闲”。,4.2.3 动态分区分配(dynamic partitioning),4.2.3 动态分区分配(dynamic partitioning),（1）首次适应算法(first-fit) 按分区的先后次序，从头查找，找到符合要求的第一个分区。 该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。 但随着低端分区不断划分而产生较多小分区，每次分配时查找时间开销会增大。,4.2.3 动态分区分配(dynamic partitioning),（2）循环首次适应算法（下次适应法next-fit) 按分区的先后次序

14、，从上次分配的分区的下一个位置开始查找（到最后一个分区时再回到开头），找到符合要求的第一个分区。 实现算法，要设置起始查询指针。 该算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大的空闲分区不易保留。,4.2.3 动态分区分配(dynamic partitioning),（3）最佳适应法(best-fit) 找到其大小与要求相差最小的空闲分区。 为了加速寻找，该算法要求空闲分区表将空闲分区按容量由小到大排序。 从个别来看，外碎片较小，但从整体来看，会形成较多外碎片。较大的空闲分区可以被保留。,（4）最坏适应法(worst-fit) 找到最大的空闲分区。 算法要求空闲分区表将空闲分

15、区按容量由大到小排序。 基本不留下小空闲分区，但较大的空闲分区不被保留。,4.2.3 动态分区分配(dynamic partitioning),（5）快速适应算法 又称分类搜索法。 将空闲分区根据容量大小分类，每类分区容量相同。为每类分区设立一个空闲分区链表。系统中设立一张管理索引表，每个表项记录的是每类空闲分区链表的表头。 优点： 查找空闲分区效率高。 能保留大分区。 缺点： 回收分区时，系统开销大。 空闲分区划分越细，浪费则越严重。,4.2.3 动态分区分配(dynamic partitioning),分区分配操作 分配内存 利用某种分配算法，从空闲分区表（链）中找到所需大小的分区 回收内

16、存，有以下四种情况： 与前一个空闲分区相邻 与后一个空闲分区相邻 与前、后空闲分区都相邻 不与任何空闲分区相邻,4.2.3 动态分区分配(dynamic partitioning),回收区与插入点的前一个空闲区F1相邻接,回收区与插入点的后一空闲分区F2相邻接,回收区同时与插入点的前后两个分区邻接,例：某系统采用动态分区分配方式管理内存，用户区主存空间为512k，在内存分配时，系统优先使用空闲区低端地址。对于如下申请序列，分别画图表示使用首次适应算法和最佳适应算法进行内存分配和回收后，内存的最终映像图。 J1 req (300KB) J2 req (100KB) J1 release (300KB) J3 req (30KB) J4 req (40KB) J3 release (30KB) J5 req (60KB),4.2.4 伙伴系统,伙伴系统方式是动态分区分配和固定分区分配的一种折衷方案。 伙伴系统规定，分配的分区和空闲分区大小都是2k，k为整数，lk m。2l表示分配的最小分区大小，2m表示分配的最大分区大小。2m是整个可分配的内存大小。系统中也要