上海大学操作系统2复习资料

存储管理的主要功能存储管理的主要功能     地址转换（逻辑地址转为物理地址 存储器的分配和回收 存储保护 存储扩充 地址转换（重定位）地址转换（重定位） 逻辑地址物理地址；多道程序中编译程序不可能预支经编译后所得到的目标模块应放在 内存何处，不能用绝对装入，要用可重定位装入。 静态转换在装入时对目标程序中指令和数据地址进行修改 动态转换 地址转换推迟到真正执行时 静态的不允许程序运行时在内存中移动位置，动态的可以 分配方式分配方式 连续分配连续分配 单一连续分配 单个程序独占 固定分区分配 划分分区分区大小相等、不等 内存分配按大小排序，分区使用表 优点能在内存中装入多道程序 缺点存储空间浪费 动态分区分配 数据结构空闲分区表；空闲分区链 动态分区分配算法 顺序搜索算法（用于不太大的系统） 首次适应首次适应空闲分区地址递增，从链首开始寻找，满足要求后切割 优点优先利用低址，保留高址大空闲区，为以后到达的大作业 分配大的内存空间创造了条件 缺点低址部分被不断划分， 留下许多难以利用的、很小的空闲 分区 循环首次适应 空闲分区地址递增， 从上次找到的下个空闲分区开始 优点避免低址部分留下太多空闲分区 缺点缺乏大的空闲分区 最佳适应最佳适应空闲分区大小递增，找到的第一个 优点避免大材小用 缺点每次切割剩下的都是最小的，会留下难以利用的碎片 最坏适应找最大的一个空闲分区 优点使剩下的空间不会太小， 产生碎片的可能性最小， 对中小 作业有利 缺点缺乏大的空闲分区 索引搜索算法（大中型系统） 快速适应每一类相同容量的分区， 单独设一个链表，查找时先去索 引表，然后去链表取下第一块即可（可将其理解为一个菜单） 优点提高搜索速度 缺点 分区归还主存时较为复杂； 分配空闲分区时是以进程为单 位的，一个分区只属于一个进程，存在浪费（以空间换空间） 伙伴系统内容看书吧 时间性能 劣于快速适应，优于顺序搜索 空间性能劣于顺序搜索优于快速适应 哈希算法 直接根据分区大小利用哈希函数计算 分配内存m.size-u.sizeTL 则段号太大，访问越界，产生越界中断信号 分页分段管理比较 分页分段 大小 信息 目的 逻辑地址 固定、硬件决定 信息的物理单位 提高内存利用率 一维，页号页内地址 不固定、程序决定 独立的信息逻辑单元，更 便于共享 方便程序设计 二维，段号段内地址 段页式管理 既有分段系统的易于实现、分段可共享、 易于保护、动态链接等优点，也能像 分页系统那样，很好的解决内存的外部碎片问题 先将用户程序分成若干段， 再把每个段分成若干页， 并为每个段赋予一个段名 逻辑地址段号段内页号页内地址（二维） 数据结构每个进程一张段表（页表地址和页表长度） ，每个段一张页表，位 视图 地址转换硬件（段表寄存器）实现的动态地址转换机构，访问3 次内存 第一次访问内存中的段表， 得到页表始址；第二次访问内存中的页表， 去 除该页所在的物理块号， 并将该号与页内地址一起形成指令或数据的物理 地址，第三次访问从第二次访问得到的地址中取出指令或数据。 常规存储器常规存储器 一次性作业必须一次性装入内存后方能运行 驻留性作业被装入内存后，整个作业都一直驻留在内存中， 其中任何部分都不会被换 出，直至运行结束 局部性原理 在一较短时间内，程序的执行仅局限于某个部分， 相应地，它所访问的存储空间也 局限于某个区域。 时间局限性若程序的某条指令被执行， 则不久后这条指令可能再次被执行， 若某 条数据被访问过， 则这条数据可能再次被访问。 原因是程序中存在着大量的循环操 作 空间局限性一旦程序访问了某个存储单元， 在不久后，其附近的存储单元也将被 访问， 即程序在一段时间内所访问的地址可能集中在一定的范围内。 典型情况是程 序的顺序执行 虚拟存储器虚拟存储器 定义 具有请求调入功能和置换功能， 能从逻辑上对内存容量加以扩充的一种存储器系 统。逻辑容量由内存容量和外村容量之和决定， 运行速度接近于内存速度， 成本又接近 外存 特征 多次性 一个作业的程序和数据无需在作业运行时一次性全部装入内存， 而是允许 被分成多次调入内存运行， 只需将当前需要运行的那部分程序和数据装入内存即可 对换性一个作业的程序和数据， 无需在作业运行时一直常驻内存， 而是允许在作 业的运行过程中进行换进换出 虚拟性用户看到的内存容量远大于十级内存容量 实现方法 分页请求系统 分段请求系统 请求分页请求分页 数据结构 页号、物理块号、状态位P、访问字段 A、修改位 M、外存地址 状态位指示该页是否已调入内存 访问字段 记录本页在一段时间内被访问的次数或时多久未被访问， 提供给置 换算法进行换进换出时的参考 修改位标识该页是否被修改过，供置换页面参考 外存地址通常时物理块号，供调入该页时参考 动态地址转换 硬件软件 缺页中断缺页中断 内存分配 固定分配局部置换 进程物理块固定； 缺页时只能从分配给该页的n 个页面中选出 一页换出，然后再调入一页，以保证分配给进程的内存空间不变 可变分配全局置换 进程运行期间分配的物理块可调整； 缺页则将空闲的物理块分 配给该进程，分配给该进程的内存空间增加 可变分配局部置换 调入策略 预调页预先估计在不久后便会被访问的页面，将其调入内存 请求调页 进程发现需要访问某程序和数据， 但此页面不在内存， 便立即提出请求， 由 OS 将需要的页面调入内存 从哪里调入 对换区 系统拥有足够的对换区空间 （进程运行前将与该进程有关的文件从文 件去拷贝仅对换区 文件区系统缺少足够的对换区空间 UNIX 方式放在文件区的直接从文件区调入；曾经用过又换出的，由于放在 对换区，直接从对换区调入；由于 unix 系统允许页面共享，某进程请求的页 面若被其他进程调入内存，可直接使用 抖动刚被换出的页面很快又要被使用，需要重新调入，此时再选一页调出；而此 刚被调出的页面又很快要被访问， 又需要调入，如此频繁的更换页面， 以致一个进 程在运行中把大部分时间花费在页面置换工作上，称该进程发生了“抖动” 预防方法采用局部置换；把工作集算法融入处理机调度；利用“ LS” 准则调 节缺页率；选择暂停的进程 影响缺页率的因素置换算法、页面大小、进程分得的页块数量， 进程访问内存的 离散程度。 工作集 在某段时间间隔内，进程实际要访问页面的集合 置换算法 OPTOPT 最佳置换算法最佳置换算法理想化，性能最好，实际无法实现，以其作为标准衡量其他算 法的优劣 FIFOFIFO 先进先出算法先进先出算法最直观，性能最差，实际应用极少 LRULRU 最近最久未用算法最近最久未用算法 NRU 最近未用算法 LFU最近最少使用算法 请求分段请求分段     段的大小受到物理内存配置的限制 便于实现段的动态链接 便于实现段的共享共享段表 段的置换时，有时还要“紧