存储管理_lecture6.ppt

操作系统存储管理张其亮 1 summary 存储器 程序链接 装入方式 存储管理方式 虚拟存储技术 2 你知道有哪些存储设备 3 memory 4 question 程序从编写到运行要经过哪些环节 5 cc 6 namespace f cvoidmain inti i 2 f o 7 Spacechanges 8 link 静态链接方式 StaticLinking 装入时动态链接 Load timeDynamicLinking 运行时动态链接 Run timeDynamicLinking 9 StaticLinking 在程序运行之前将各个目标模块及所需的库函数 链接成一个完整的装入模块 可执行文件 运行时直接装入内存 静态链接方式 10 StaticLinking 对相对地址进行修改 变换外部调用符号 11 DynamicLinking 在装入时动态链接方式中 用户源程序经编译后所得到的目标模块 是在装入内存时边装入边链接的 即在装入一个目标模块时 若发生一个外部模块调用 将引起装入程序去找出相应的外部目标模块 将它装入内存并修改目标模块中的相对地址 1 便于修改和更新 2 便于实现对目标模块的共享 装入时动态链接 优点 12 DynamicLinking 这种链接方式是将对某些模块的链接推迟到执行时才执行 亦即 在执行过程中 当发现一个被调用模块尚未装入内存时 立即由OS去找到该模块并将之装入内存 把它链接到调用者模块上 运行时动态链接 扩展 13 Staticlib 14 Dynamiclib 15 Load 1 绝对装入方式 编译程序产生绝对地址目标代码 绝对装入程序按照装入模块中的地址 将程序和数据装入内存 装入程序装入内存后不需对地址进行修改 程序中所使用的绝对地址 可在编译或汇编时给出 也可由程序员直接赋予 通常是在程序中采用符号地址 然后在编译或汇编时 再将这些符号地址转换为绝对地址2 可重定位方式 由装入程序根据内存当时的实际使用情况 将装入模块装入到内存中的适当地方 在程序运行之前执行的3 动态运行时装入方式 程序执行期间执行的 16 load 绝对装入程序按照模块中的地址 将程序和数据装入内存 装入模块被装入内存后 由于程序中逻辑地址与实际内存地址完全相同 不需对程序和数据的地址进行修改 绝对装入方式 17 load 1 可重定位装入时 模块装入内存时会使装入模块中的所有逻辑地址与实际内存的物理地址不同 2 通常是在装入时对目标程序中指令和数据的地址进行修改 称为重定位 由于可重定位装入时地址变换是在装入时一次完成的 以后不再改变 称为静态重定位 可重定位装入方式 18 load 程序在运行过程中在内存中的位置可能会经常改变 故引入动态运行时装入方式 动态运行时装入方式 动态运行时的装入程序 在把装入模块装入内存后 并不立即把装入模块中的相对地址转换为绝对地址 而是把这种地址转换推迟到程序真正要执行时才进行 因此 装入内存后的所有地址都仍是相对地址 重定位寄存器支持 19 example b c 哪一种是可重定位方式 哪种是动态运行时方式 20 memory 21 memory 一般由单道系统采用 整个内存空间的用户区可看成是单一连续存储管理方式 单一连续区管理 22 part 把主存的用户区划分成若干区域 每个分区给一个用户程序使用 程序一次性装入 分区管理 固定分区管理 动态分区管理 23 part 固定分区管理 24 part 固定分区管理 FreeSpace 程序2 程序3 程序1 0k 4k 16k 64k 128k 1每个分区只能容纳一个程序2固定分区容易造成内碎片占用分区之内未被利用的空间 25 part 分区表 26 part 动态分区管理 对主存空间事先不划分 而是当作业装入时 根据作业的大小 在空闲区域划出一个连续的区域 空闲分区表 空闲分区链 27 example Job1 Job2 Job3 Job4 Job5 Job6 Job7 Job7 Job6 example 28 example 外碎片 动态分区分配算法 29 FF 按始地址升序排列 分配内存时 从链首开始查找 找到找到一个能满足要求的空闲分区为止 首次适应算法 30 FB 按分区大小递增的顺序排列 分配内存时总是能把满足要求 又是最小的空闲分区分配给程序 避免 大材小用 缺点 容易产生碎片 最佳适应算法 31 FW 按分区大小递减的顺序排列 最差适应算法 32 others 循环首次适应算法 快速适应算法 将空闲分区按大小进行分类 伙伴算法 33 example 某时刻系统中有三个空闲区其大小和首址为 35KB 100KB 12KB 156KB 28KB 200KB 有一作业系列 JOB1 12KB JOB2 30KB JOB3 28KB 采用哪种算法最合适 34 example 35 part 检查回收的分区是否与空白区邻接 如有则加以合并 使之成为一个连续的大空白区 修改可用表或自由链 空闲释放区与空闲区相邻有四种情况 动态分区回收 36 example 紧凑技术 37 reload 38 program 动态重定位分配 39 protect Howtoprotectthememory 界限寄存器方式 基址限长寄存器法 40 protect 界限寄存器方式 寄存器上界 寄存器下界 41 example 例 有一程序装入内存的首地址是500 末地址是1500 访问内存的逻辑地址是500 345 1200 下界寄存器 500上界寄存器 1500逻辑地址 装入内存的首地 物理地址1 500 500 1000500 1000 1500 2 345 500 845500 845 1500 3 1200 500 1700500 1700 1500 42 protect 基址限长寄存器 43 example 例 有一程序装入内存的首地址是500 末地址是1500 访问内存的逻辑地址是500 345 1200 基址寄存器 500限长寄存器 1000判别式 逻辑地址 限长寄存器1 500 1000 2 345 1000 3 1200 1000 44 questions 分区管理有哪些缺点 造成原因是什么 缺点 碎片问题 造成内存浪费 原因 连续存储 45 page 分区存储管理中作业占用的分区必须是一个连续的存储区域 容易产生碎片问题 故提出离散存储管理 纯分页管理 请求分页管理 46 纯分页管理 Dividevirtualmemoryintosmallpages Dividephysicalmemoryintosmallblocks Pagesize blocksize 47 example 实现了离散存储 还会产生碎片吗 48 example 页内碎片 较小 49 PageStructure 页面大小固定 e g 2k 4k 2的整数次幂 虚拟地址 页号p 虚拟地址 页面大小 取整页内偏移d 虚拟地址 页面大小 例如 设某系统的页面大小为1KB A 3456B 则P 3 d 384 50 page 块内偏移地址d 页内偏移地址d绝对地址 块号B 块大小 块内偏移地址 物理地址 51 page 页表 页表占据内存 52 example 53 page 地址转换 页大小1K 54 example 有一系统采用页式存储管理 有一作业大小是8KB 页大小为2KB 依次装入内存的第7 9 10 5块 试将虚地址3412B转换成内存地址 虚地址3412P INT 3412 2048 1D 3412mod2048 1364物理地址 9 2048 1364 19796 55 example example2 在32位计算机系统中 页大小位4k 程序页表如下 有一个逻辑地址28A6H 其对应的物理地址是多少 16进制表示 56 page 快表 在页式存储技术中 在执行一条访问内存指令时 实际上要访问多少次内存 并行查找 快表找到后结束 快表找不到继续查页表 57 page 58 page 需要页表 220 1M个页表项 假设一个页表项占4B页表大小 4B 1M 4M由于页表必须放在内存中 所以系统多个进程的页表将占据庞大的内存空间 而实际上 不是每个进程都有4G 即1M个页表项中 大部分处于空闲状态 因此采用这种分页结构实际上是对内存不必要的浪费 Normally4KBPages 以32位地址空间为例 如何解决 59 page 采用离散分配方式来解决难以找到一块连续的大内存空间的问题 只将当前需要的部分页表项调入内存 其余的页表项仍驻留在磁盘上 需要时再调入 多级页表 60 page 61 page 62 page 简单分页把作业地址空间划分成若干页面后 需要把所有的页面装入主存中 换句话说 当一个用户程序的页数大于当前总空闲内存块数时 系统就不能将该程序装入运行 请求分页方式中对于当前不使用的页面放在外存 当要访问的页面不在主存时 作业通过缺页中断向系统发出调页请求 由系统把所需的页面从外存调入内存 请求分页管理 63 page 64 page 状态位 该页是否在主存修改位 该页装入主存后是否被修改过 内存中的每一个页面在外存都有一份副本 若无修改 则不必写回外存 访问字段 该页被访问的次数或最近有多长时间未被访问等外存地址 该页在外存的存放位置 页表 65 page 程序访问的页面不在内存 发出缺页中断 中断程序保留CPU环境 分析中断原因 转入缺页中断处理程序 缺页中断处理程序查页表得到该页在外存的位置 如果此时内存能容纳新页将之调入 修改页表 若内存已满 则进行页面置换 选中一页换出内存 如果该页未修改过 不必将该页写回磁盘 如果修改过 必须写回磁盘 然后调用缺页中断程序 并修改页表相应位 页面调入过程 66 page Questions 选择哪些页面调出内存 67 page 好的页面算法要有较低的页面转换频率先进先出 FIFO 最近很久未使用算法 LRU 最佳置换算法 Optimal 简单Clock置换改进的Clock置换 页面调度算法 68 FIFO example 内存有三个物理块 allinitiallyfreestring ABCABDADBCB FIFO 总是淘汰最先进入内存的页面 69 FIFO FIFO 缺页 缺页 70 FIFO 抖动现象 71 LRU 根据页面的使用情况进行决策 赋予每个页面一个访问字段t t记录一个页面自上次访问以来所经历的时间 淘汰时选择t值最大的 即为最近最久未使用的 LRU example 内存有三个物理块 allinitiallyfreestring ABCABDADBCB 72 LRU 用一个栈来保存当前使用的各个页面的页面号 当进程访问某页时 便将该页的页面号从栈中移出 压入栈底 栈顶始终是最新访问的页面 用堆栈来处理LRU 73 Optimal 淘汰的页面是以后不会使用的或最长时间不会被访问的 由于人们无法预知一个进程在内存的若干个页面中 哪一个页面是未来最长时间内不被访问的 因此 该算法很难实现 最佳置换算法 example 内存有三个物理块 allinitiallyfreestring ABCABDADBCB 74 CLOCK Clock 75 EXAMPLE Clock 76 ImprovedCLOCK ImprovedClock 自学 77 example 练习 在一个请求分页存储管理系统中 一个作业的页面走向为4 3 2 1 4 3 5 4 3 2 1 5当分配给该作业的内存块分别为3 4个时 试分别计算采用下述页面淘汰算法时的缺页率 假设最初主存中没有页面 并比较所得结果 FIFOLRUClock 78 segment 问题的提出 前面介绍的几种存储管理技术中 提供给用户的逻辑地址空间是一维线形的 与内存的物理组织基本相同 但用户编写的程序逻辑结构却不是这样 79 segment 一维空间在分页时并不能保持原来的结构 页是存放信息的物理单位 并无完整意义 段却是信息的逻辑单位 有利于信息共享 动态链接以段为单位 分段存储管理 分段存储管理的引入 80 segment 按照作业的逻辑结构划分地址空间 每个段都从0开始编址 作业装入主存后 每个段占用一个连续的存储区域 而各段之间可以不连续 思想 81 segment 记录段的起始地址和段的长度 可通过段表从物理内存中找出每个逻辑段的位置 地址结构 地址空间是二维的 段表 82 segment 内存 地址变换 83 segment 段表放在内存中 要访问一个数据 须访问多少次内存 84 difference 页是信息的物理单位 分页仅仅是由于系统管理的需要 实现离散分配 减少碎片 而不是用户的需要 而段是信息的逻辑单位 它含有一组具有相对完整意义的信息 是处于用户的需要 页的大小固定且由系统确定 把逻辑地址分为页号和页内地址两部分功能 由机器硬件实现 而段的长度却不固定 由用户在编程时确定 或由编译程序在对源程序进行编译时 根据信息的性质来划分 分页的作业地址空间是一维的 即单一的线性地址空间 程序员只需用一个记忆符即可表示一个地址 而分段的作业地址空间则是二维的 1 2 3 85 segment 由于段是信息的逻辑单位 因而分段系统易于实现共享和保护 这也是分段系统的突出优点之一 举例 假定一个多用户系统可容纳40个用户 某应用程序包括160KB的TextEditor代码区和40KB的数据区 共200K 则需8M内存支持 若代码是可重入的 Reentrant 则代码去可共享 因而其所需内存空间为1760KB 160 40 x40 在分页系统中 假定每个页面大小4K 那么代码区占40个页面 数据区占10个页面 为了实现共享 每个进程的页表中都建立40个页表项使用相同的物理块号 代码区 另外建立10个数据区的页表项在分段系统中 实现共享则容易得多 如图所示 段共享 86 segment 87 example 段号段长段起始地址 0200500 14001000 21001400 39002000 虚地址 0 100 1 500 4 470 2 250 完成实地址转换 举例 88 segment page 分段能保持原来的逻辑结构 分页能减小碎片 提出了段页式存储管理 结合两者的优缺点 把作业空间分段 然后在段中进行分页 89 segment page 地址结构 90 段页式存储管理 地址变换 91 segment 程序运行之前 只需要先调入若干个分段 当程序执行发现所需的段不在内存时 请求OS调入所需要的段 参考请求分页管理 自学 92 question 在段页式存储管理中 为了获得一条指令或数据 需要访问内存多少次 问题 93 virtualmemory 内存有1G 操作系统占200M 程序1占500M 程序2有400M 能调入内存运行吗 94 virtualmemory 1 虚拟内存使用请求分页技术 2 将部分程序放在外存 用时调入 3 用户感觉不到 认为程序只要能运行 说明内存能容纳它 4 虚拟的 而非物理上扩充了内存 95 End 96 Practice 1 在可变分区存储管理中的紧凑技术优点在于 A 增加主存容量B 缩短访问周期C 加速地址转换D 集中空闲区2 以下存储管理技术中 支持虚拟存储器的技术是 A 动态分区法B 可重定位分区法C 请求分页技术D 对换技术3 在段式存储管理中 一个段是一个 区域 A 定长的连续B 不定长的连续C 定长的不连续D 不定长的不连续 97 4 存储管理中 页面抖动是指 A使用机器时 屏幕闪烁的现象B被调出的页面又立刻被调入所形成的频繁调入调出现象C系统盘有问题 致使系统不稳定的现象D由于主存分配不当 偶然造成主存不够的现象5 系统 抖动 现象的发生是由 引起的 A置换算法选择不当B交换的信息量过大C内存容量不足D请求页式管理方法6 在分区存储管理方法下 导致碎片的原因是 A 重定位B 分区的个数固定C 分区的大小固定D 作业连续存储 98 7 在页式存储管理系统中 整个系统的页表个数是 个 A1B2C与页面数相同D和装入主存的进程个数相同8 采用段式存储管理时 一个程序如何分段是在 决定的 A 分配主存时B 用户编程时C 装作业时D 程序执行时9 能够装入内存任何位置的代码程序必须是 A 可重入的B 可重定位C 可动态链接D 可静态链接 99 10 在下列有关请求分页管理的叙述中 正确的是 A 程序和数据是在开始执行前一次性装入的B 产生缺页中段一定要淘汰一个页面C 一个被淘汰的页面一定要写回外存D 在页表中要有 访问位 和 改变位 等信息11 采用 不会产生内部碎片 A 分页式存储管理B 分段式存储管理C 固定分区式存储管理D 段页式存储管理12 当程序经过编译或者汇编以后 形成了一种由机器指令组成的集合 被称为 A源程序B目标程序C可执行程序D非执行程序 100 13 经过 目标程序可以不经过任何改动而装入物理内存单元A静态重定位B动态重定位