操作系统存储器管理OS4 (2)

第四章存储器管理 2 Review 1 存储器的层次结构Cache缓解了CPU处理速度和内存读取速度不匹配的矛盾 磁盘缓存缓解了内存读取速度和磁盘读取速度不匹配的矛盾 速度价格 容量 3 Review 程序的装入方式 绝对装入 程序中的逻辑地址与实际内存地址完全相同 无需进行重定位 可重定位装入 装入时对目标程序中指令和数据的逻辑地址进行修改 转换成对应的物理地址 动态运行时装入 装入模块装入内存后 并不立即把装入模块中的逻辑地址转换成物理地址 而是推迟到程序真正执行时才进行 需要重定位寄存器的支持 程序的链接方式 静态链接 在程序运行前 将各目标模块及它们所需的库函数 链接成一个完整的装配模块 以后不再拆开 装入时动态链接 装入内存时采用边装入边链接的方式 动态运行时 对某些模块的链接推迟到程序执行时才进行 4 本章主要内容 4 1存储器的层次结构4 2程序的装入和链接4 3连续分配方式4 4基本分页存储管理方式4 5基本分段存储管理方式4 6虚拟存储器的基本概念4 7请求分页存储管理方式4 8页面置换算法4 9请求分段存储管理方式 5 4 3连续分配方式 6 4 3连续分配方式 内存分为两个区域 系统区 用户区 最简单 适用于单用户 单任务的OS 采用静态链接 静态重定位技术 优点 易于管理 缺点 对要求内存空间少的程序 造成内存浪费 程序全部装入 很少使用的程序部分也占用内存 7 4 3连续分配方式 思想 是一种最简单的可运行多道程序的存储管理方式 将内存用户空间划分成若干个固定大小的区域 在每个分区中只装入一道作业 这样 用户空间分成了几个分区 便允许有几道作业并发运行 有空闲分区时 便可以再从外存的后备作业队列中选择一个适当大小的作业装入该分区 当该作业结束时 又可从后备队列中找到另一作业调入内存 JD90K JE40K 8 4 3连续分配方式 划分分区的方法 1 分区大小相等缺乏灵活性常用于利用一台计算机去控制多个相同对象的场合 因为这些对象所需的内存空间大小是相等的 如炉温群控系统 OS JA JB 0 30k 45k 60k 75k 2 分区大小不等把内存分成包含多个较小的分区 适量的中等分区及少量的大分区 9 4 3连续分配方式 分区的管理方法 通常按分区大小进行排队 并为之建立一张分区使用表 如图所示 分区说明表 存储空间分配情况 10 静态链接 静态重定位装入内存保护 用一对界限寄存器 优点 易于实现 开销小 缺点 内碎片造成浪费分区总数固定 限制了并发执行的程序数目 4 3连续分配方式 11 补充 内碎片和外碎片 内碎片 若存储块长度为n 该块存储的进程长度为m 则剩下的 n m 空间称为该块的内部碎片 外碎片 若存储块长度为n 在该系统所采用的调度算法下 较长时间无法选出一道长度不超过该块的作业 即该块长时间得不到使用 则称该块为外部碎片 12 根据进程的实际需要 动态地为之分配内存空间 用什么样的数据结构 分区分配时的方法 分配和回收操作 空闲分区表 每个空闲分区占一个表目 表目中包括分区序号 分区始址及分区大小等数据项 空闲区 块 链表 将所有的空闲区链成一个链表 位示图表示法Map i j 用一位 bit 表示一个空闲块 页框 0 空闲 1 占用 动态分区分配的数据结构 4 3连续分配方式 13 4 3连续分配方式 空闲分区表 空闲链结构 位示图表示法 14 15 申请分配时 用数组map i j 找为0的物理块 置1 对应的物理块号bno ni j此处n 16 一个字长释放时由bno 给定 换算出 i j 对应位置0i bnodivn j bnomodn 0 map i j 位示图表示法 4 3连续分配方式 16 4 3连续分配方式 1 何时分区 进程装入时 分区大小 作业大小分区个数 作业个数 2 如何实现 提供分区分配与回收算法 J1 J5依次进入内存 J1 J4完成 J6需要进入内存 如何分配内存 18 空闲区按某种规则链成队列 规则与具体算法有关 寻找一个 作业大小的空闲区 一分为二 若P J SIZEP 空闲区大小 J 作业大小SIZE 系统给定值 50 500 动态分区分配算法总体原则 若P J SIZE P全部分给作业 回收时合并相邻空闲区 插入空闲区队列 19 动态分区分配算法分类 顺序搜索法 分类搜索法 快速适应算法 分区分配算法 首次适应算法 循环首次适应算法 最佳适应算法 最坏适应算法 1 首次适应算法 空闲区按地址大小升序链成队列 分配时从队首开始查到第一个满足要求的空闲区进行分配 分配2k S1满足要求 余S1 3k 优点 尽量分配低地址部分 保留内存高端空闲区不被分割 以便运行大作业 缺点 分配时可能查遍整个队列 2 循环首次适应算法 空闲区按地址大小升序链成环形队列 从上次分配的分区后面开始查找 作业申请2k 回收时 有相邻空闲区要合并 优点 碎片均匀分布在队列中 回收时合并机率大 缺点 大空闲区难以保留 不利于大作业 3 最佳适应算法 被分割的空闲区最接近作业大小 空区按大小为序链成队列较大的空闲分区可以被保留 作业需要9k 只分割S3 不破坏S4 优点 总是能把满足要求 又是最小的空闲分区分配给作业 缺点 分配后剩余部分总是最小 存储器中会留下很多难以利用的小空闲区 4 最坏适应算法 将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链 查找时只要看第一个分区能否满足作业要求 剩下的空闲区不至于太小 产生碎片的几率最小 作业需要9k 分割S1 还剩11k 可能还可满足另一作业的需求 优点 产生碎片几率最小 对中 小作业有利 查找效率最高 缺点 缺乏大的空闲分区 5 快速适应算法 将所有的空闲分区按其容量大小进行分类 对于每一类具有相同容量的所有空闲分区 单独设立一个空闲分区链表 这样 系统中存在多个空闲分区链表 同时在内存中设立一张管理索引表 该表的每一个表项对应了一种空闲分区类型 并记录了该类型空闲分区链表表头的指针 优点 查找效率高 不会产生分区分割 不产生碎片 也能满足大作业的要求 缺点 回收分区时算法复杂 系统开销较大 分区只属于一个进程 因此在为进程所分配的一个分区中 或多或少地存在一定的浪费 空闲分区划分越细 浪费越严重 是典型的以空间换时间的方法 26 例题分析 某系统采用动态分区分配方式管理内存 内存空间为640K 高端40K用来存放操作系统 在内存分配时 系统优先使用空闲区低端的空间 对下列的请求序列 作业1申请130K 作业2申请60K 作业3申请100K 作业2释放60K 作业4申请200K 作业3释放100K 作业1释放130K 作业5申请140K 作业6申请60K 作业7申请50K 作业6释放60K 请分别画图表示出使用首次适应算法和最佳适应算法进行内存分配和回收后内存的实际使用情况 作业1申请130K 作业2申请60K 作业3申请100K 作业2释放60K 作业4申请200K 640K 作业3释放100K 作业1释放130K 作业5申请140K 作业6申请60K 140K 作业6释放60K 作业7申请50K 以上为首次适应算法的分配和回收情况 作业1申请130K 作业2申请60K 作业3申请100K 作业2释放60K 作业4申请200K 作业3释放100K 作业1释放130K 作业5申请140K 作业6申请60K 作业6释放60K 作业7申请50K 以上为最佳适应算法的分配和回收情况 内存分配和回收过程 130 60490 110 J1 0 130J3 190 100J4 290 200 130 60490 110 J1 0 130J3 190 100J4 290 200 J4申请200K 130 60290 310 J1 0 130J3 190 100 130 60290 310 J1 0 130J3 190 100 J2释放60K 290 310 J1 0 130J2 130 60J3 190 100 290 310 J1 0 130J2 130 60J3 190 100 J3申请100K 190 410 J1 0 130J2 130 60 190 410 J1 0 130J2 130 60 J2申请60K 130 470 J1 0 130 130 470 J1 0 130 J1申请130K 最佳适应 空闲 始址 大小 最佳适应 已分配 作业 始址 大小 首次适应 空闲 始址 大小 首次适应 已分配 作业 始址 大小 动作 140 150 4 290 2005 0 1406 490 607 550 50 250 40490 110 4 290 2005 0 1406 140 607 140 50 J7申请50K 490 60140 150 4 290 2005 0 1407 550 50 140 60250 40490 110 4 290 2005 0 1407 140 50 J6释放60K 550 50140 150 4 290 2005 0 1406 490 60 200 90490 110 4 290 2005 0 1406 140 60 J6申请60K 490 110140 150 4 290 2005 0 140 140 150490 110 4 290 2005 0 140 J5申请140K 490 1100 290 4 290 200 0 290490 110 4 290 200 J1释放130K 490 110130 160 1 0 1304 290 200 130 160490 110 1 0 1304 290 200 J3释放100K 最佳适应 空闲 最佳适应 已分配 首次适应 空闲 首次适应 已分配 动作 内存的实际使用情况图 首次适应算法 最佳适应算法 分区分配操作 从头开始查表 检索完否 m size u size m size u size size 从该分区中划出u size大小的分区 将该分区分配给请求者修改相关的数据结构 返回 返回 继续检索下一个表项 将该分区从链中移出 Y N Y m Size表示空闲分区大小 u Size表示请求分区大小 Size表示事先规定的不可再分割的剩余分区大小 图4 7内存分配流程 Y N N 39 回收内存 当进程运行完毕释放内存时 系统根据回收区的首址 从空闲链表中找到相应的插入点 此时可能出现以下四种情况 1 回收区与插入点的前一个空闲分区F1相邻 将回收区与插入点的前一分区合并 不必