存储器管理是指存储器资源（主要指内存）的管理存储空间课件_1

存储器管理是指存储器资源（主要指内存)的管理。 存储空间的分配与管理； 地址重定位（逻辑地址与物理地址的对应关系） 存储保护 存储空间扩充：虚拟存储器技术以及各种调度算 法。 1 n n 4.1 4.1 地址重定位地址重定位 n n 4.2 4.2 分区存储管理分区存储管理 n n 4.3 4.3 覆盖和交换覆盖和交换 n n 4.4 4.4 页面式存储管理页面式存储管理 n n 4.5 4.5 请求式页面存储管理请求式页面存储管理 n n 4.6 4.6 段式存储管理段式存储管理 n n 4.7 4.7 段页式存储管理段页式存储管理 2 4 4. .1 1 地址重定位地址重定位 主存储器分为两部分：系统区，用户区 存储管理主要管理用户区的存储空间 地址空间和存储空间地址空间和存储空间 名空间：程序中由符号名组成的空间。 逻辑地址（相对地址）：用户的程序经过汇编或 编译后形成目标代码，目标代码通常采用相对地 址的形式。相对于0编址。 逻辑地址空间（地址空间）：相对地址的集合。 物理地址（绝对地址）：主存储器中一系列物理 单元的编号。物理地址可直接寻址。 物理地址空间（存储空间）：物理地址的集合。 3 逻辑地址（相对地址，虚地址）：用户的程序经过 汇编或编译后形成目标代码，目标代码通常采用相 对地址的形式。 其首地址为0，其余指令中的地址都相对于首地址来编址 。 不能用逻辑地址在内存中读取信息。 物理地址（绝对地址，实地址）：内存中存储单元 的地址。物理地址可直接寻址。 地址映射：将用户程序中的逻辑地址转换为运行时 由机器直接寻址的物理地址。 逻辑地址、物理地址和地址映射逻辑地址、物理地址和地址映射 4 逻辑地址、物理地址和地址映射 地址映射 1100Load A,1200 3456 。 。 。 1200 物理地址空间 Load A,data1 data1 3456 源程序 Load A,200 3456 0 100 200 编译连接 逻辑地址空间 BA=1000 5 地址重定位：地址重定位：实现程序的相对地址空间到绝实现程序的相对地址空间到绝 对地址空间之间的映射。对地址空间之间的映射。 程序在成为进程前的准备工作 编辑：编辑：形成源文件(符号地址) 编译：编译：形成目标模块(模块内符号地址解析) 链接：链接：由多个目标模块或程序库生成可执行文件( 模块间符号地址解析) 装入：装入：构造PCB，形成进程(使用物理地址) 重定位方法：重定位方法： 静态重定位静态重定位 动态重定位动态重定位 地址重定位地址重定位 6 优点：容易实现，无需硬件支持。 缺点： 程序在主存中只能连续分配； 程序装入内存后不能移动； 对共享的同一程序，各用户必须使用自己 的副本，浪费存储空间。 在程序执行之前进行地址重定位，即可执行文 件中装入主存时，由操作系统中的加载程序来 完成地址映射。 重定位重定位项：项：程序中涉及直接寻址的每条指令都要 进行修改，需要修改的位置称为重定位项。 重定位重定位项表：项表：用相对地址给出需修改的位置。列 出各个需要重定位的地址单元和相对地址值。 静态重定位静态重定位 7 地址映射 1100Load A,1200 3456 。 。 。 1200 物理地址空间 Load A,data1 data1 3456 源程序 Load A,200 3456 0 100 200 编译连接 逻辑地址空间 BA=1000 静态重定位 8 可执行文件在内存中的重定位 说明：重定位表中列出所有修改的位置。如：重定位表的150 表示相对地址150处的内容为相对地址(即100为从0起头的相 对位置)。在装入时，要依据重定位后的起始位置(2000)修改 相对地址。 重定位修改：重定位表中的150-绝对地址2150(=2000+150) 内容修改：内容100变成2100(=100+2000)。 jmp 150 100150 . Relocation Table 0 jmp 150 21002150 . 2000 9 优点： OS可以将一个程序分散存放于不连续的内存空间 ；可以移动程序。 有利用实现共享。 缺点：需要硬件支持（通常是CPU），是虚拟 存储的基础。 在程序运行期间进行重定位，装入和执行时通过硬件 地址变换机构，完成虚拟地址到实际内存地址的变换 动态重定位动态重定位 10 动态重定位 0 100 200 300 . . . . . . . . . LOAD A,200 3456 逻辑地址空间 1100 1200 1300 物理地址空间 200 VR + 1000 BR（基址寄存器） LOAD A,200 3456 11 缺点：不能充分使用存储空间。 4 4. .2 2分区存储管理分区存储管理 基本思想：将主存储空间划分成若干个连续 的存储区，称为分区。每个分区只能存储一 道程序，一个程序只能访问其所在分区的存 储单元。 12 内存分为两个连续区域：系统区，用户 区。应用程序装入到用户区，可使用用 户区全部空间。 最简单，适用于单道程序设计的OS。 优点：易于管理。 缺点：对要求内存空间少的程序，造成 内存浪费（空闲存储区）。 4 4. .2 2分区存储管理分区存储管理 单一连续区存储管理单一连续区存储管理适用于单道程序系统 13 单一连续区存储管理 0H 7FFFH FFFFFH 操作系统 用户程序区 08000H 界限寄存器 中断矢量表 空闲区 14 基本思想：把内存分为一些大小相等或不等连续 区域分区(partition)，每个分区只能驻 留一个程序。操作系统占用其中一个分区。 特点：适用于多道程序系统和分时系统 支持多个程序并发执行 问题：存在碎片（小得难以使用的分区）问题， 可能存在内部碎片和外部碎片。 内部碎片：占用分区之内未被利用的空间 外部碎片：占用分区之间难以利用的空闲分区（通常 是小空闲分区）。 分区存储管理分区存储管理 15 分区大小相等：只适合于多个相同程序的 并发执行（处理多个类型相同的对象）。 分区大小不等：多个小分区、适量的中等 分区、少量的大分区。根据程序的大小， 分配当前空闲的、适当大小的分区。 把内存划分为若干个固定大小的连续分区。 一旦划分好，在系统运行期间不再重新划分 。 固定分区固定分区(fixed partitioning)(fixed partitioning) 16 固定分区(大小相同) 固定分区(多种大小) 17 优点：简单易于实现，开销小。 缺点： 内部碎片造成浪费 分区总数固定，限制了并发执行的程序数目。 采用的数据结构：分区表(分区说明表)记 录分区的大小和使用情况 Operating System 空闲分区 分区5 作业C 分区4 分区3 分区2 分区1 空闲分区 作业B 作业A 00000H 08000H 0A000H 12000H 1A000H 3A000H 区号起始地址大小使用 标标志 作业业 大小 108000H8KY6K 20A000H32KY24K 312000H32KN 41A000H128KY118K 53A000H512KN 内存分区说明表 18 动态分区：在装入作业和处理过程中，按其 要求的内存容量以及当时的内存资源使用情 况，将一块大小与所要求相近的存储区分配 给作业。 优点：没有内部碎片。 缺点：有外部碎片。 动态分区动态分区(dynamic partitioning)(dynamic partitioning) 19 Operating System 128 K 896 K Operating System Process 1 320 K 576 K Operating System Process 1 320 K Process 2224 K 352 K 20 Operating System Process 1 320 K Process 2 Process 3 224 K 288 K 64 K Operating System Process 1 320 K Process 3 224 K 288 K 64 K Operating System Process 1 320 K Process 3288 K 64 K Process 4 128 K 96 K 21 22 分区的数据结构：分区表，或分区链表 可以只记录空闲分区，也可以同时记录空闲和占 用分区 单一分区表中，表项数目随着内存的分配和释放 而动态改变，表长难以确定，分配回收分区时降 低查找速度。 分区表可以划分为两个表：空闲分区表，使用分 区表。从而减小每个表长度。空闲分区表（一般 常用链表结构）中按不同分配算法相应对表项排 序。 分区分配和释放算法 动态分区管理： 23 分区分配算法：寻找某个空闲分区，其大小 需大于或等于程序的要求。 分区释放算法：需要将相邻的空闲分区合并 成一个空闲分区。(这时要解决的问题是： 合并条件的判断和合并时机的选择) 分区分配算法和释放算法： 24 最先匹配法(first-fit)：按分区的先后次序，从头查找 ，找到符合要求的第一个分区 该算法的分配和释放的时间性能较好，较大的空闲分区可 以被保留在内存高端。 但随着低端分区不断划分而产生较多小分区，每次分配时 查找时间开销会增大。 最佳匹配法(best-fit)：找到其大小与要求相差最小的 空闲分区 从个别来看，外部碎片较小，但从整体来看，会形成较多 外部碎片。较大的空闲分区可以被保留。 最差匹配法(worst-fit)：找到最大的空闲分区 基本不留下小空闲分区，但较大的空闲分区不被保留。 分区分配算法 25 基本思想：分配算法与可变分区分配基本算 法基本相同，并对作业进程分区进行搬迁， 以形成大的连续的空闲分区。 特点：解决外部碎片问题的简单有效的方法 对占用分区进行内存数据搬移占用CPU时间 如果对占用分区中的程序进行“浮动”，则其重 定位需要硬件支持（提供基址界限寄存器对 ）。 实现空闲分区拼接的时机：每个分区释放后 ，或内存分配找不到满足条件的空闲分区时 动态重定位式分区分配动态重定位式分区分配 26 基本思想：一个作业由一些相对独立的程序段和 数据段组成，每个段占用一个连续分区，而相应 的各分区之间不要求是连续的。 特点：有效地解决外部碎片问题 要求： 相应的语言编译器能在作业的每个段内生成有效地址 （各段相对于0编址） 系统内设置多对基址界限寄存器。 优点： 可以实现分区共享 诸进程可以共享数据分区。 多重分区存储管理多重分区存储管理不拼接而解决碎片问题 27 引入：其目标是在较小的可用内存中运行较大 的程序。常用于多道程序系统，与分区存储管 理配合使用。 基本思想:一个作业的若干程序段，或几个作 业的某些部分共享同一存储区。 优点：解决小主存容量与大作业之间的矛盾。 缺点：实现覆盖管理的系统开销较大。 4 4. .3 3 覆盖和交换覆盖和交换 覆盖覆盖(overlay)(overlay) 28 注：另一种覆盖方法：(100K) A(20K)占一个分区：20K； B(50K)、D(20K)和E(40K)共用一个分区：50K； F(30K)和C(30K)共用一个分区：30K； 覆盖技术 不存在调用关系的模块不必同时装入到内存，从而可以相互覆 盖。(即不同时用的模块可共用一个分区) 29 缺点： 编程时必须划分程序模块和确定程序模块 之间的覆盖关系，增加编程复杂度。 从外存装入覆盖文件，以时间延长来换取 空间节省。 30 引入：解决主存容量不足的矛盾。多个程序并发执 行，可以将暂时不能执行的程序送到外存中，从而 获得空闲内存空间来装入新程序，或读入保存在外 存中而目前到达就绪状态的进程。交换单位为整个 进程的地址空间。常用于多道程序系统或小型分时 系统中，与分区存储管理配合使用。又称作“对换 ”或“滚进/滚出(roll-in/roll-out)”。 基本思想:暂停执行内存中的进程，将整个进程的地 址空间保存到外存的交换区中（换出swap out）， 而将外存中由阻塞变为就绪的进程的地址空间读入 到内存中，并将该进程送到就绪队列（换入swap in ）。 交换交换(swapping)(swapping) 31 优点：增加并发运行的程序数目，并且给用户提供 适当的响应时间；编写程序时不影响程序结构。 缺点： 对换入和换出的控制增加处理机开销；程序整个地 址空间都进行传送，没有考虑执行过程中地址访问 的统计特性。 考虑的问题： 程序换入时的重定位； 减少交换中传送的信息量，特别是对大程序； 对外存交换区空间的管理：如动态分区方法； 32 覆盖与交换的区别： l 覆盖由用户解决空间不足 l 交换由系统解决空间不足 33 引入：避开作业的连续性要求，将一个作业存放在 不连续的存储空间中，以很好地解决碎片问题。 基本思想:系统把内存物理空间等分为若干大小相等 、位置固定的块（或帧）。将程序的逻辑地址空间划 分为与块大小相同的页或页面(page or page frame)， 程序加载时，分配其所需的所有块，这些块不必连续 。需要CPU的硬件支持。 4 4. .4 4 页面式存储管理页面式存储管理 地址空间分成大小相同的部分 页 存贮空间分成大小相同的部分 块(页帧) 页大小块大小 34 页表(PMT) ：又称页面映象表，记录一个作业程序的页 号所对应的内存块号。 需要CPU的硬件支持。 页号块号 0 1 2 2 3 8 分配时页对 应块，但不 要求连续 页表包括：页号，块号 35 页帧19 Operating System 作业2（页0） 00000H 0B000H 0A800H 0B800H 0C000H 0E000H 作业1（页0） 作业2（页2） 作业1（页1） 作业2（页1） 作业3（页0） 物理地址空间 页帧0 页帧20 页帧21 页帧22 页帧23 页帧24 页帧25 页帧26 页帧27 页帧28 0C800H 0D000H 0D800H 0 1 逻辑地址空间 作业1(4K) 0 1 作业2(5K) 2 0 作业3(1.8K) 0 1 页表 0 1 2 0 页帧号 22 20 25 21 24 27 36 页面式存储管理硬件页面式存储管理硬件 地址变换：指令所给出地址分为两部分：逻 辑页号，页内偏移地址查进程页表，得物 理页号物理地址 页面大小：通常是几KB到几十KB（取2的幂）。 小内部碎片小；大页表短，管理开销小， 交换时对外存I/O效率高。 37 页式地址变换 38 分页存储管理算法分页存储管理算法 作业表：记录每个作业的状态和资源使用情况，包 括页表起始地址、页表长度。 空闲块表：页记录内存空闲块的帧号。以链表形式 组织内存空闲块。 建立进程时，作业调度程序调用存储管理程序为作 业进程分配存储空间。按作业请求的内存容量size计 算要分配的块数N=size/size_page(上取整) 一个作业终止时，系统调用存储管理程序，回收该 作业释放的物理页，修改空闲存储块链表。 39 引入：向用户提供大容量存储器，把内存和外存统 一考虑，外存作为存储信息的主要媒介，内存作为处 理机需要访问的数据缓冲区。 基本思想:运行一个作业程序时，并不要求把该作业 的全部程序和数据都装入内存，可只把目前要执行的 几页调入内存的空闲存储块，其余部分仍保存在外存 ，以后根据作业程序运行情况需要时再调入内存。 4 4. .5 5 请求式页面存储管理请求式页面存储管理 需解决的问题： 提供一种机制，检测访问的页是否在内存，若不在，为之 分配一物理页，修改页表项，并将逻辑页调入到物理页。 选择淘汰算法。40 分页故障处理分页故障处理 活动页：某一时刻驻留在内存的页，称为进程的活 动页。 非活动页：某一时刻驻留在外存的页。 作业的页表项包括该页是否在内存的信息。 存在位p=1:该逻辑页在内存 p=0:该逻辑页在外存，对该逻辑页的任何访 问都将产生“缺页故障”中断。 作业进程欲访问一条不在内存物理页中的指令或操 作数时，由地址变换机构硬件产生“缺页故障”中断 ，并由缺页故障中断处理程序实现物理页的调入、 调出操作。 41 淘汰算法淘汰算法 当外存上某页信息需调入内存而内存中 又无空闲存储块时，则需按某种淘汰算 法从内存中选择一页将其内容淘汰。 淘汰算法不合理将产生抖动现象刚 被调出的页马上又被要求调入。 42 最佳淘汰算法：从内存中淘汰永远不再使用 的页；如这样的页不存在，则选择最长时间 不再被访问的页为淘汰页。 老页：某时刻前，进程访问过的所有页 新页：某时刻，进程正在对某页进行第一次访问 。 自然页流：老页中以后还要访问的页和新页构成 进程的使用页集，使用页集的变动为进程的自然 页流。 特点：仅有理论意义，实际不可实现 明确知道各将来时刻对各页的访问情况，很难。 内存容量有限，使得某些页过早淘汰。 43 先进先出FIFO算法：采用先调入内存的页面 先被淘汰的策略；即总选择驻留内存时间最 长的一页淘汰。 原因：最早调入的页面不再使用的可能性要比最 近调入的要大。 以调入内存的时间先后顺序组织一个进程现行使 用的内存储块为FIFO队列 优点：仅在程序按线性顺序访问地址空间时才是理 想的。 缺点： 未考虑程序运行时的动态特性。 可能导致程序中常被访问的页，因其在内存中驻留时间最 长而被淘汰。 44 最近最少使用LRU(Least Recently Used) 算法 ：选择最近很长时间未被访问的一页淘汰。 原因：若一页刚被访问过，很可能最近还要被访 问；若一页最近很长时间未被引用，则最近访问 的可能性极小。 按照各页最近一次的访问时间进行排序 缺点：每访问一次要进行一次排序，系统开销大， 难以实现。 近似LRU算法（第二次机会淘汰算法） 45 举例： 设某作业占有7个页面，如果在主存中只允许装入 4个工作页面(即工作集为4)，作业运行时，实际访 问页面的顺序是1， 2， 3， 6， 4， 7， 3， 2， 1， 4， 7， 5， 6， 5， 2， 1。用FIFO与LRU页面调度 算法，列出各自的页面淘汰顺序和缺页中断次数。( 假设开始的4个页面已装入主存) FIFO： 页面淘汰顺序：1 2 3 6 4 7 缺页中断次数：6次 LRU： 页面淘汰顺序： 1 2 6 4 7 3 2 1 4 7 缺页中断次数： 10次 注：假定前面四页1 2 3 6 已在主存 46 最少使用LFU(Least Frequently Used) 算法： 淘汰在现在时刻之前某一段时间内访问频率 最低的页。 原因：过去一段时间最经常访问的页，将来访问 的可能性最大。 特点： 需要为每个内存页面设置一个“访问次数计数器” ，每当 页面被访问时，该页面的访问计数器加1； 应禁止淘汰最近一个时间间隔内调入内存的新页； 发生缺页中断时，淘汰计数值最小的页面，并将所有计 数清零。 47 请求调页(demand paging)：只调入发生缺页时 所需的页面。 优点：容易实现。 缺点：对外存I/O次数多，开销较大 预调页(prepaging)：在发生缺页需要调入某页时 ，一次调入该页以及相邻的几个页。 优点：提高调页的I/O效率。 缺点：基于预测，若调入的页在以后很少被访问，则 效率低。常用于程序装入时的调页。 调入策略确定在外存中的页面调入时机。在虚拟页式 管理中有两种常用策略。 分页虚拟存储管理调入策略分页虚拟存储管理调入策略 (fetch policy)(fetch policy) 48 存储保护的目的： 保护系统程序区不被用户侵犯（有意或无意的） 不允许用户程序读写不属于自己地址空间的数据（系统 区地址空间，其他用户程序的地址空间） 1. 存储保护 由于存储保护检查是针对每个存储访问操作进行的 ，必须由相应的处理器硬件机构支持。 页面的共享与保护页面的共享与保护 49 存储保护类型 界限保护（上界寄存器/下界寄存器或基址寄存器/限长寄存器 ）：所有访问地址必须在上下界之间；每个进程都有自己独 立的进程空间，如果一个进程在运行时所产生的地址在其地 址空间之外，则发生地址越界。 访问方式保护（保护键）：通过保护键匹配来判断存储访问 方式是否合法。对于允许多个进程共享的存储区域，每个进 程都有自己的访问权限。如果一个进程对共享区域的访问违 反了权限规定，则发生操作越权(即读写保护)。对每个内存区 域指定一个键值和若干禁止的访问方式，进程中也指定键值 ，如果访问时键值不匹配而且是被禁止的访问方式，则出错 ； 环保护：处理器状态分为多个环(ring)，分别具有不同的存储 访问特权级别(privilege)，通常是级别高的在内环，编号小（ 如0环）级别最高；可访问同环或更低级别环的数据；可调用 同环或更高级别环的服务。 50 共享页面：在物理页面表中有引用计数。只能共享 不被修改的页面。这对用户应用是透明的，完全由 操作系统控制，目的在于减少系统内的物理页面总 数。 当共享页从内存中淘汰或重新装入内存时，共享该页的所 有作业进程的页表中的相应页表项必须被同时更新。 写时复制(copy on write)：如果一个进程要改写共享页面， 则先把该页面复制一份，让该进程访问复制后的页面，而 让其他进程访问复制前的页面。 通过引用计数(reference count)来描述存储区的共享， 引用计数表示共享它的进程的数目： 2.存储共享 51 页式管理是把内存视为一维线性空间；而段式 管理是把内存视为二维空间，与进程逻辑相一 致。 段式存储管理基本思想： 将程序的地址空间划分为若干个段(segment)， 程序加载时，分配其所需的所有段（内存分区 ），这些段不必连续；物理内存的管理采用动 态分区。需要CPU的硬件支持。 4 4. .6 6 段式存储管理段式存储管理 52 地址结构如下： 段号S段内位移量d 通过段表实现逻辑地址到物理地址的映射 段表结构：该段在内存中的首地址；段长；访问权限 ，段存在位（该段是否在内存） 段表中各表项按段号从小到大顺序排列 53 B 0 S A 0 N Y 0 L X 0 P M 0 K 逻辑段号 0 1 2 3 4 作业 1 的地址空间 1000 3200 5000 6000 8000 P K S L N 主存 K 3200 P 1500 L 6000 N 8000 S 5000 长度 段地址 0 1 2 3 4 操作系统 54 地址转换地址转换 55 段式地址变换的步骤： (1) 分段寻址硬件把cpu产生的程序逻辑 地址划分为段号s和段内地址d，(s，d) (2) 用S检索段表，得到段基地址B (3) 如d0或d段表长度L则产生越界异 常中断 (4) (B+d)即为所需内存地址 56 程序通过分段(segmentation)划分为多个模块，如代 码段、数据段、共享段。 可以分别编写和编译 可以针对不同类型的段采取不同的保护 可以按段为单位来进行共享，包括通过动态链接进行代码 共享 优点： 没有内部碎片，外部碎片可以通过内存拼接来消除。 便于改变进程占用空间的大小。 便于模块化，便于处理共享问题。 缺点： 进程全部装入内存。 段的最大长度受限于主存空间，开销大。 57 页式管理和段式管理的比较 分页是出于系统管理的需要，分段是出于用户应用 的需要。 一条指令或一个操作数可能会跨越两个页的分界处，而 不会跨越两个段的分界处。 页大小是系统固定的，而段大小则通常不固定。 逻辑地址表示： 分页是一维的，各个模块在链接时必须组织成同一个地 址空间； 分段是二维的，各个模块在链接时可以每个段组织成一 个地址空间。 通常段比页大，因而段表比页表短，可以缩短查找 时间，提高访问速度。 58 段的共享与保护段的共享与保护 共享段：被连接或被释放一次则对引用计数加1或 减1，计数减至0则可将该