第四章 存储器管理 4.1-4.5.ppt

第四章存储器管理MemoryManagement 为多道程序的运行提供良好的环境提高存储器的利用率从逻辑上扩充存储器存储共享和保护 4 1存储体系4 2程序的链接和装入4 3连续分配方式4 4基本分页存储管理方式4 5基本分段存储管理方式4 6虚拟存储器的基本概念4 7请求分页存储管理方式4 8页面置换算法4 9请求分段存储管理方式 本章主要内容 4 1存储体系 4 1存储体系 存储层次结构 无限容量大 速度无限快 价格便宜 金钱 性能 存储管理 使主存储器在成本 速度和规模之间获得较好的权衡 4 2程序的链接和装入ProgramLinkingandLoading 一 用户程序的主要处理阶段二 程序的装入三 程序的链接 一 用户程序的主要处理阶段 将一个用户程序变为一个可在内存中执行的程序 通常要经过以下几步 1 编译 Compiling Sourcecode ObjectModule 2 链接 Linking ObjectModules Libraryfunction LoadModule 3 装入 Loading LoadModule InternalMemory 构造PCB 形成进程 使用物理地址 库 图4 1对用户程序的处理步骤 编译器只能在一个模块内部完成符号名到地址的转换 不同模块间的符号解析由链接器来完成的 地址映射 LoadA12003456 1200 物理地址空间 LoadAdata1data13456 源程序 LoadA2003456 0 100 200 编译连接 逻辑地址空间 BA 1000 符号地址 相对地址 绝对地址 基本概念 BasicConcept 地址映射 重定位 把逻辑地址空间中使用的逻辑地址变换成内存空间中的物理地址的过程 物理地址 内存是一块存储区域 存储单位是字节 字 每个字节都有地址 这种地址称为物理地址 绝对地址 所有的物理地址集合构成物理地址空间 逻辑地址 源程序经过编译连接形成可执行文件中的地址 通常从0开始 程序中其余指令中的地址都相对于首地址而编址 这种地址称为逻辑地址 相对地址 虚地址 所有逻辑地址的集合构成逻辑地址空间 符号地址 源程序中用字母和数字组成的符号代表存储器的地址 二 程序的装入ProgramLoading 一个程序运行装入到内存时 可有三种装入方式 1 绝对装入方式 AbsoluteLoadingMode 2 可重定位方式 RelocatableLoadingMode 3 动态运行时装入方式 dynamicRun TimeLoading 1绝对装入方式 AbsoluteLoadingMode 由装入程序根据装入模块中的地址 将程序和数据装入内存 装入模块的地址是编译时由编译程序产生的 是绝对地址 装入程序按装入模块装入内存时 不需修改地址 绝对地址可由程序员直接给出 或在编译或汇编时给出 这种方式要求事先已知程序将装入内存的位置 一般只在单道程序的环境才有可能实现 优点 装入过程简单 缺点 过于依赖硬件结构 不适于多道程序系统 例如 装入 2可重定位装入方式 RelocatableLoadingMode 由装入程序根据内存当时的实际使用情况 将装入模块装入到内存的适当地方 目标模块中为相对地址 逻辑地址 装入模块中的逻辑地址与实际装入内存的物理地址不同 装入内存时 要进行可重定装入方式采用的静态重定位 其地址变换方式为 物理地址 相对地址 内存起始地址 优点 不需硬件支持 可以装入有限多道程序 缺点 一个程序通常需要占用连续的内存空间 程序装入内存后不能移动 重定位 MOVax 2500 365 0 1000 2500 10000 11000 12500 MOVax 2500 365 逻辑空间 内存空间 0 12500 12500 10000 2500 物理地址 基地址 相对地址 例如 装入模块为相对地址 在装入内存时 并不立即变为物理地址 绝对地址 即装入后仍为相对地址 只有在程序真正执行到某一步时才对它进行地址转换 动态重定位 优点 OS可以将一个程序分散存放于不连续的内存空间 可以移动程序 有利用实现共享 缺点 该方式需要一定特殊硬件的支持 OS实现较复杂 3 动态运行时装入方式 dynamicRun TimeLoading 是实现虚拟存储的基础 作业1 处理机一侧 存储器一侧 1000 500 例如 重定位寄存器 相对地址 几个重要概念Severalimportantconcepts 绝对地址 AbsoluteAddress 物理地址 PhysicalAddress 相对地址 RelativeAddress 逻辑地址 LogicalAddress 符号地址 SymbolAddress 地址空间 AddressSpace 逻辑地址空间存储空间 storagespace 主存空间 物理地址空间重定位 Relocation 在把程序的目标程序装入到内存时的地址修改过程 即LA PA 静态重定位 StaticRelocation 动态重定位 DynamicRelocation 重定位 概念 程序和数据装入内存时 需要对目标程序中的地址进行修改 这种把逻辑地址转换为内存物理地址的过程叫做重定位 类型 根据重定位时间和技术的不同 分为 静态重定位 程序执行前 一次性将该作业中程序的指令地址和数据地址全部转换成绝对地址 装入内存 且以后不能移动 动态重定位 在程序执行过程中动态地进行地址转换 由地址变换机构 硬件 自动执行 三 程序的链接ProgramLinking 源程序经过编译后 可得到一组目标模块 利用链接程序将这组目标模块链接 形成装入模块 链接阶段产生的可执行目标程序在不运行时 通常作为一个二进制可执行文件驻留在硬盘上 根据链接时间的不同 可把链接分成如下三种 1 静态链接Staticlinking 2 装入时动态链接Load timedynamiclinking 3 运行时动态链接Run timedynamiclinking 在装入内存之前进行 链接后形成一固定的装入模块 也称为可执行程序 不再拆开 此方式需要解决 1 修改相对地址 2 变换外部调用符号 图4 4程序静态链接示意 printf OK 目标模块1 库模块 voidprintf 0 0 1200H printf OK voidprintf 装入模块 0 call1200H 1 静态链接 voidprintf 目标模块在装入内存时边装入边链接 2 装入时动态链接 printf OK 主模块 库模块 voidprintf 0 0 装入 printf OK 21200H call21200H 20000H 内存 1 便于修改和更新 由于各目标模块分开存放 只需对要修改的模块修改后编译即可 保证所有的软件同步升级 优点 每次都要链接装入所有的模块 不论是否用到 例如 IFTHENS1ELSES2 缺点 2 便于实现目标模块的共享 通常被链接的共享代码称为动态链接库 DLL Dynamic LinkLibrary 或共享库 sharedlibrary 实现多个模块共享一个DLL而不要每个程序都含有该模块的拷贝 3 便于运行环境适应 调用不同的DLL 就可适应多种使用环境和提供不同功能 如 不同的显卡只需厂商为其提供特定DLL 而OS和应用程序不必修改 3 运行时动态链接 printf OK printf OK 主模块 库模块 voidprintf 0 0 装入模块 voidprintf 装入 printf OK 执行 33600H call33600H 内存 一开始只链接装入部分模块 在运行过程中 若发现被调用模块不在内存 则发出请求 由OS查找 装入并链接到调用模块 通常链接和装入是一体的 其发展过程可分为三个阶段 1 静态链接 静态装入 2 静态链接 动态装入 3 动态链接 动态装入 4 3连续分配方式ContiguousMemoryAllocation 连续分配指为用户程序分配一个连续的内存空间 一 单一连续分配二 分区式分配 一 单一连续分配SingleContinuousAllocation 内存分为两个区域 系统区 用户区 单一连续分配 内存中仅驻留一道程序 整个用户区为一个用户独占 适用于单用户 单任务的OS 优点 简单 易于管理 缺点 内存中只装入一道作业运行 内存空间浪费大 资源利用率低 为了防止OS受到用户程序有意或无意的破坏 可以设置保护机构 如基址 重定位 寄存器和界限寄存器 内存的保护 二 分区式分配PartitionAllocation 固定分区分配动态分区分配可重定位分区分配伙伴系统 为了支持多道程序运行 提出了分区式分配存储管理方式 该方式中 内存用户区共多个用户程序使用 划分成若干分区 每个分区容纳一个作业 按照分区的划分和分配方式 常见的分区式分配有如下几种 1 固定分区分配 FixedPartitionAllocation 1 基本原理 将内存空间分为若干个固定大小的区域 每个分区装入一道作业 划分通常是在系统初使化时执行 2 划分分区的方法分区大小相同 主要用于控制多个相同对象的场合 即各处理对象的大小基本相同 分区大小不同 一般可划分多个小分区 适量中等分区 少量大分区 可适应多种类型的作业 3 内存分配数据结构 将分区按大小顺序排列 建立一张分区使用表 包含分区起始地址 大小 状态等 分配过程 有内容要装入时 在分区使用表中查找大小能满足且未分配出去的分区 若找到 则实施分配且修改分区表中的状态 否则 拒绝分配 OS 8K 用户分区1 16K 用户分区2 16K 用户分区3 32K 主存分配表 Job1 20K 0 Job1 例如 内存中已分配给作业但未被利用的区域称为 内零头 internalfragment 固定分区分配会有内零头产生 固定分区分配方法小结 优点 简单 缺点 实际系统运行时 往往无法预知分区大小 太大 等同于 单用户分区模式 主存空间利用率仍然较低 分区数目预先确定 限制了多道运行程序的数量 如今 几乎没有哪一种操作系统支持这种模式 2 动态分区分配 DynamicPartitionAllocation 在实现动态分区分配存储管理方式时 必须解决下述三个问题 动态分区分配中的数据结构 分区分配算法 分区的分配和回收 1 基本原理 内存不预先划分好 当进程装入时 根据进程的需求和内存空间的使用情况来决定是否分配 若空间足够 则按需要动态为之分配连续的内存空间 否则 令其等待主存空间例如 1 空闲分区表 用表记录内存中的所有空闲分区 每一分区占一表目 可包括序号 大小 始址等 2 空闲分区链 用链方式记录每一空闲分区 链上每一分区中存储有指向前后分区的指针及本分区的大小 状态 0表示可用 1表示已用 2 动态分区分配中的数据结构系统必须记录内存的使用情况 为分配提供依据 空闲分区链结点示意图 空闲分区表 空闲分区链 3 动态分区分配算法 将作业装入内存时 选择哪个的内存分区进行分配 常用的算法有如下几种 首次适应算法 First FitAlgorithm 循环首次适应算法 Next fitAlgorithm 最佳适应算法 Best fitAlgorithm 最坏适应算法 Worst fitAlgorithm 快速适应算法 Quick fitAlgorithm 作业 首次适应算法 First FitAlgorithm 要求 空闲分区以地址递增的次序链接 分配 从链首顺序查找 直至找到一个能满足大小的空闲分区为止 按需要对其进行划分 分配 保留 例 倾向 利用低址分区 优点 分区组织简单 高址部分可容纳大作业 缺点 低址处外零头 externalfragment 多 查找越来越困难 空闲分区表 解 按首次适应算法 申请作业100k 分配3号分区 剩下分区为20k 起始地址160K 例如 系统中的空闲分区表如下 现有三个作业分配申请内存空间100K 30K及7K 给出按首次适应算法的内存分配情况及分配后空闲分区表 20k 160k 申请作业30k 分配1号分区 剩下分区为2k 起始地址50K 申请作业7k 分配2号分区 剩下分区为1k 起始地址59K 2k 50k 1k 59k 作业1 作业2 作业3 作业4 2 3 4 1 0 0 1 0 2 3 4 1 5 0 在低地址部分会积累大量外零头 0 2 3 4 5 1 要求 空闲分区以地址递增的次序链接 且做成环形 设置一个起始查寻指针 分配 从上次找到的空闲分区的下一个分区开始查找 直至找到一个能满足大小要求的空闲分区 划分 例 倾向 平衡利用内存 优点 空闲分区组织简单 查找简单 缺点 无大的空闲分区 难满足大作业的要求 循环首次适应算法 Next fitAlgorithm 空闲分区表 解 按循环首次适应算法 申请作业100k 分配3号分区 剩下分区为20k 起始地址160K 例如 系统中的空闲分区表如下 现有三个作业分配申请内存空间100K 30K及7K 给出按循环首次适应算法的内存分配情况及分配后空闲分区表 20k 160k 申请作业30k 分配4号分区 剩下分区为301k 起始地址210K 申请作业7k 分配1号分区 剩下分区为25k 起始地址27K 25k 27k 301k 210k 最佳适应算法 Best fitAlgorithm 要求 空闲分区按大小从小到大进行链接 分配 从链表头进行顺序查找 直至第一个大小能满足的分区 则为能满足且最接近需要大小的分区 划分 例如 优点 避免 大材小用 缺点 外零头严重 分区组织 回收复杂 空闲分区表 解 按最佳适应算法 申请作业100k 分配3号分区 剩下分区为20k 起始地址160K 例如 系统中的空闲分区表如下 现有三个作业分配申请内存空间100K 30K及7K 给出按最佳适应算法的内存分配情况及分配后空闲分区表 申请作业30k 分配3号分区 剩下分区为2k 起始地址50K 申请作业7k 分配2号分区 剩下分区为1k 起始地址59K 20k 160k 2k 50k 59k 1k 2k 50k 1k 59k 要求 空闲分区按从大到小链接 分配 从头顺序查找 找到大小能满足的 则为能满足且划分后剩余空间最大的分区 划分 例如 优点 外零头较少 缺点 难满足大作业的要求 分区组织 空闲分区回收复杂 最坏适应算法 Worst fitAlgorithm 空闲分区表 例如 系统中的空闲分区表如下 现有三个作业分配申请内存空间100K 30K及7K 给出按最坏适应算法的内存分配情况及分配后空闲分区表 解 按最坏适应算法 申请作业100k 分配1号分区 剩下分区为231k 起始地址280K 申请作业30k 分配1号分区 剩下分区为201k 起始地址310K 申请作业7k 分配1号分区 剩下分区为194k 起始地址317K 231k 280k 201k 310k 194k 317k 分区分配算法的性能看其时间 空间复杂性而定 就算法本身来说 它们的复杂性由排序 地址大小 空闲区大小 和查找 查找所需自由区 两项决定 搜索速度 FF最佳 BF或WF要求按空间大小进行排序 因此速度较慢 回收过程 FF最佳 因为FF算法回收时不用改变空闲区位置 只需修改大小和起始地址 空闲区 BF最佳 但某些情况下会降低内存利用率 碎片 WF基于不留碎片空间为出发点 FF BF WF三种算法比较 上述三种分配算法各有利弊 好坏不能一概而论 应针对具体作业序列来分析 对某作业序列来说 若某算法能将该作业中所有作业安置完毕 则称该算法对这一作业序列是合适的 对某一算法而言 若不能立即满足作业序列的某一要求 则该算法对该作业序列是不合适的 FF算法以其简单 快速特性 在实际的操作系统中用得较多 其次是最佳适应算法 FF BF WF三种算法比较 续 动态分区管理方式中 主要操作是内存分配和回收 分配内存 MemoryAllocation 按某种算法根据请求的大小 在表或链中进行查找合适空闲区 找不到则结束 找到则划分 为减少外零头 可设一下限 若划分后零头小于该下限 则不划分直接分配 修改相应的数据结构 u size 请求的分区大小 m size 表中每个空闲分区的大小 size 事先规定的不再切割的剩余分区的大小 4 动态分区的分配和回收 按照分区分配算法 在空闲分区中查询 m size u size size m size 空闲区大小u size 请求分区大小size 分区大小下限 m size m size u size 将分区分配给用户 从空闲分区表 链 中移出 查找下一个 N Y 内存分配过程 m size u size 检索完否 m分区整块分配给u N Y N 返回 可能形成外零头 存在内零头 按照分区分配算法 Y 当内存运行完毕释放内存时 系统根据回收区的首址在相应的数据结构中查找插入点 此时可能出现四种情况之一 回收区上邻接一个空闲分区 合并 改大小 回收区下邻接一个空闲分区相邻 合并 改始址 大小 回收区上下邻接区相邻 合并 共用上空闲分区首址 改大小 取消下空闲分区 回收区不邻接空闲分区 单独建一表项 回收内存 ReturnMemory 回收内存举例 P1运行结束 P3运行结束 P1所占分区的上下都不空闲 在空闲分区链中添加一项 P3所占分区下边的分区F1空闲 应进行合并 在空闲分区链中找到F1节点 修改其起始地址和长度 P2运行结束 P2所占分区上边的分区F1空闲 应进行合并 在空闲链表中找到F1节点 修改其长度 P2 P1 P3 F1 F2 P1运行结束 P1所占分区上下边的分区F1和F2都空闲 应进行合并 在空闲链表中找到F1节点 修改其长度为F1 F2和P2所占分区的长度和 删除F2节点 动态分区分配举例 某计算机有2560K内存 采用可变分区模式管理内存 操作系统占用低地址的400K空间 剩余2160K的空间为用户区 分区分配采用首次适应算法 最初整个用户区为空闲 即只有一个分区 随着用户程序的创建和撤销 分区的个数和大小位置开始变化 分配回收过程如下所示 内存的初始状态 1000K 1560K P1 600K P1来 600K P2来 1000K 560K 2000K P2 1000K P3来 300K 2300K 260K P2结束 1000K P4来 700K 1700K P4 700K 300K P3 300K P1结束 600K P5来 500K 900K 100K P5 500K P4结束 1100K 3 可重定位分区分配Relocatablepartitionallocation 1 引入 紧凑 将内存中的作业进行移动 使它们相邻接 将分散的小分区拼接成一个大分区 从而利于作业的装入 以时间换空间 动态分区分配中 经多次划分后 常会出现大量的太小而无法利用的区域 外零头 为了充分利用内存空间 可采用紧凑 compaction 技术 紧凑后的作业在内存中位置发生了变化 则应对其中程序 数据等的地址做相应的修改 即重定位 P1 10K P3 a P7 P8 操作系统 15K 30K P1 10K P3 P8 操作系统 15K 25K 30K P7 55K b a 紧凑前 b 紧凑后 2 动态重定位的实现TheimplementationofdynamicRelocation 为支持作业在内存中的移动 应采用动态运行时装入方式 因此 允许作业在运行过程中在内存中移动的技术 必须获得硬件地址变换机构的支持 在系统中设置一个重定位寄存器 用于存放作业在内存中的起始地址 运行时 相对地址执行 物理地址 重定位寄存器 相对地址得到它在内存中的实际地址 如图所示 紧凑时 只需修改重定位寄存器值 使之存放新起始地址 3 可重定位分区分配算法DynamicRelocationPartitionAllocationAlgorithm 修改有关的数据结构 检索空闲分区链 表 进行紧凑形成连续空闲区 修改有关的数据结构 按动态分区方式进行分配 找到大于u size的可用区否 空闲分区总和 u size 返回分区号及首址 无法分配返回 请求分配u size分区 否 否 是 是 动态分区分配算法流程 可重定位分区分配小结 进程结束 释放分区时 如不与空闲区相邻 则紧凑 保持空闲区连续 花费多 分配进程分区时 若不满足 则紧凑 空闲区管理复杂 优点 消除内存碎片 提高内存利用率 缺点 提高硬件成本 紧凑时花费CPU时间 开销大 紧凑的时机 4 伙伴系统 BuddySystem 固定分区和动态分区方式都有不足之处 伙伴系统方式是对以上两种内存方式的一种折衷方案 伙伴系统规定 1 内存分区大小均为2的k次幂 k为整数 l k m 其中 21表示分配的最小分区的大小 2m表示最大分区的大小 通常为系统开始运行时可分配内存的大小 2 该方法通过不断划分大的空闲区来获得小的空闲区 直到获得所需内存块 空闲块的分配和合并均使用2的幂次方算法 3 当一个空闲块被对分后 其中一部分称为另一部分的伙伴 伙伴系统空闲块的组织 空闲分区根据分区的大小进行分类 对于每一类具有相同大小的所有空闲分区 单独设立一个空闲分区双向链表 这样 不同大小的空闲分区形成了k 0 k m 个空闲分区链表 伙伴系统内存的分配和回收 1Mblock 1M Request100K 512K 256K 128K A 128K 128K Request240K A 128K 128K 256K 512K B 256K Request64K A 128K 128K 64K 64K B 256K C 64 Request256K A 128K 512K C 64K 64K B 256K 256K 256K D 256K RelesetB A 128K C 64K 64K B 256K 256K D 256K 256K RelesetA A 128K B 256K 128K C 64K 64K 256K D 256K 256K 512K Request75K B 256K 128K E 128K C 64K 64K 256K D 256K 256K RelesetC E 128K C 64K 64K 64K RelesetE 128K 128K 256K 256K 512K 256K 512K D 256K RelesetD 256K 256K 512K 1M 伙伴系统内存的分配和回收 续 伙伴系统小结 EasytopartitionEasytocombineInternalfragmentationexisting NoexternalfragmentationThebuddysystemisusedforLinuxkernelmemoryallocation 在内存分区分配中考虑两个问题 1 若进程在运行过程中长度发生变化 则如果邻接内存区域为空白 可再分配 若邻接为一进程 则需要移动 等待 交换或撤销 2 作业调度时内存空间是否满足 因此 作业调度算法应同分区内存管理相结合 即在考虑调度顺利时 还要考虑到内存空间是否能满足 例如 作业到来次序所需存储量运行时间 160KB10s 2100KB5s 330KB20s 470KB8s 550KB15s OS 03940256 J1 J2 J3 26K 100K J4 30K 60K J5 10K 110K 主存总容量为257K OS占40K 系统采用FCFS作业调度 进程调度采用时间片 5s 轮转 216K 三 对换 Swapping 1 对换的引入 IntroductionofSwapping 对换 把内存中暂不能运行的进程或暂不用的程序 数据换到外存 以腾出足够内存空间 把已具备运行条件的进程 或进程所需要的程序和数据 换入内存 原因 多道程序环境下 内存中某些进程占据大量内存空间但无法运行 而外存中尚有许多作业 因无内存而不能运行 对换是提高内存的利用率的有效措施 原因 1 处于阻塞状态2 低优先级 确保高优先级进程运行 3 时间片用完 暂停执行内存中的进程 将要换出的进程的地址空间保存到外存的对换区中 换出 而将外存中由阻塞变为就绪的进程的地址空间读入内存 并将该进程送到就绪队列 换入 原理 1 整体对换 或 进程对换 对换以整个进程为单位 用于分时系统 以解决内存紧张 提高内存利用率 2 页面对换 或 分段对换 对换以 页 或 段 为单位进行 部分对换 支持虚存系统 可在系统中设一对换进程 以执行换进内存 换出至外存操作 实现 对换是系统行为 分类 系统提供的功能 对换空间的管理 ManagementofSwappingSpace 进程的换入 SwapinofProcess 进程的换出 SwapoutofProcess 为实现对换 系统需要三方面的功能 引入对换后 外存被分为两部分 文件区和对换区 文件区 用于存放文件 其管理目标为提高存储空间的利用率 因此采取离散分配方式 对换区 存放从内存换出的进程 它们在外存的存放时间较短 换入 换出频繁 其管理目标为提高进程换入换出的速度 因此采用连续分配方式 即一个文件可根据当前外存的使用情况 被分成多块 分别存到不邻接的多个内存存储区域中 即把一个换出的进程存放到一个连续的存储空间中 2 对换空间的管理 ManagementofSwappingSpace 对对换区的管理类似于内存的动态分区分配方式 进程的换入和换出由对换进程完成 1 进程的换出实质 把活动阻塞 就绪状态的进程转挂起状态 步骤 换出过程分以下两步 step1 选择被换出的进程处于阻塞状态的 优先级最低的进程 无阻塞 选择优先级低的就绪进程 考虑优先级低产生 换进 再换出 兼顾内存驻留时间 非共享的程序和数据段 若为共享 只能引用数为零后才能被换出 3 进程的换入与换出 SwapinandSwapoutofProcess step2 换出过程 申请对换空间 成功则执行 否则 重新选择 将程序和数据写入对换区 检查写入的正确性 无误 则调用释放内存过程 释放原内存 修改PCB 内存分配表等 若内存仍不足或仍有可换出进程 则回到 2 进程的换入实质 把挂起状态 活动就绪或阻塞 步骤 换入过程分以下两步 step2 换入过程 从PCB集合中查找 就绪且换出 的进程 有多个 则选择换出时间最长的 根据进程大小申请内存 成功则读入 否则要先执行换出 再换入 若还有可换入进程 则转向 直至无 就绪且换出 进程或无法获得足够内存空间为止 step1 选择换入进程有足够的内存空间 就绪挂起 优先于 阻塞挂起 同一队列中 优先级高 挂起时间长的优先换入 离散内存分配方式 把用户的程序空间划分成若干部分 化整为零 它们可以离散分配到内存中非连续的存储区域中 充分利用内存 即离散分配方式 根据程序划分时的基本单位不同 可分为三种 基本分页存储管理方式基本分段存储管理方式段页式存储管理方式 4 4基本分页存储管理方式BasicPagedMemoryManagement 一 基本分页存储管理原理二 基本概念三 内存分配和回收四 地址变换五 两级和多级页表 一 基本分页存储管理原理 将程序的逻辑地址空间划分为固定大小的页 页面 pageorpageframe 将物理内存划分为与页面大小相等的物理块 block 程序加载时 按页分配其所需的块 连续页面所分得物理块不必连续 需要CPU的硬件支持 内存 第2页 第1页 第4页 第3页 第5页 用户作业 02K 1 第2页 页长2K 02K 1 4号块 块长2K 页内碎片 第0页 基本分页存储管理示意图 把用户程序的逻辑地址空间划分成若干大小相等的 页 各页从0开始依次编页号0 1 2 页内地址相对于0编址 因此 分页系统中 每个逻辑地址都可用二元组 页号 页内地址 表示 二 基本概念 BasicConcept 把内存空间划分成若干和 页 大小相同的块 称为物理块 Block 或页框 frame 同样为它们编号0 1 物理地址同样用二元组 块号 块内地址 表示 2 页面大小 PageSize 分页系统中页面大小由机器地址结构决定 因此 机器的页面大小固定 用户程序页面划分由系统自动完成 一般为2的整数次幂 例如 IBMAS 400的页面大小为512B 小页面优点 减少碎片 提高内存利用率 缺点 页表过长 占用较多内存空间 且以页为单位进行换进 换出时效率低 大页面优点 页表小 换进换出时效率高 缺点 页内碎片相应较大 页面的大小通常在512B 4KB之间 3 逻辑地址形式 LogicAddress 在分页存储管理方式中 程序经过页面划分后 任一个逻辑地址都可转变 页号 页内位移量 如 一个32位的逻辑地址 可转化为如下方式 例如 有逻辑地址为 2170 页面大小为1KB 则P INT 2170 1024 2 W 2170MOD1024 122 逻辑地址A 在分页存储管理方式中 需要被转换成 页号 页内偏移 二元组地址形式 若页面大小为L 则转换过程为 逻辑地址转换过程 页号P INT A L 页内位移量W AMODL 若逻辑地址为二进制呢 变换通常由系统中的某些硬件完成 MMU 内存管理单元 设有一页式存储管理系统 向用户提供的逻辑地址空间最大为16页 每页2048字节 内存总共有8个存储块 试问逻辑地址至少应为多少位 内存空间有多大 问 三 内存的分配与回收MemoryAllocationandReturn 1 数据结构 DataStructer 作用 描述进程页面存放在内存中所对应的物理块 内容 页表中主要包括页号 物理块号 还可有存取控制字段 实现对存储块中内容的保护 如 注意 每个进程一个页表 全部页表集中存放在内存的系统专用区中 只有系统有权访问页表 保证安全 例 1 进程页表 页表 PageTable 3 空闲块表 记录内存当前空闲块 全系统1张 2 虚空间表 作业表 记录进程空间的情况 一个进程一个表项 记录进程页表在内存的存放情况 全系统仅1张 1 进程页表放在哪儿 2 进程页表的首地址和长度放在哪儿 问 内存 进程PCB 2 内存分配过程 MemoryAllocation 3 内存回收过程 MemoryReturn 根据进程页表的内容 把空闲块表中对应的物理页改为空闲 撤销该进程的进程页表 四 地址变换AddressTransformMechanism 功能 将逻辑地址转变为物理地址 页号到物理块号的转换 借助页表 进程页表 页号块号 越界中断 6 87 1 基本地址变换机构 BasicAddressTransformMechanism 分页系统的地址变换机构示意图 1 分页地址变换机构将相对地址分为 页号 页内地址 2 读取PTR中的页表长度 IF页号 页表长度THENGOTO3 ELSE越界中断 3 读取PTR中的页表始址 计算 页表始址 页号 页表项长度得到该页表项在页表中的位置 对应得到该页的物理块号 装入物理地址寄存器 4 将逻辑地址中的页内地址送入物理地址寄存器的块内地址字段 拼接 得到最后的物理地址 例如 地址变换过程 要解决的问题 主要考虑两个问题 加速逻辑地址到物理地址的变换问题 大页表问题 如果逻辑地址空间很大 页表也会很大 现代计算机至少使用32位的逻辑地址空间 而且64位变得越来越普遍 假设 页长为4KB 32位地址空间将有100万页 基本分页管理模式中 若要访问内存的数据需要访问内存几次 为什么 问 为了提高数据访问速度 在地址变换机构中引入快表 快表 转换检测缓冲区 Translationlookasidebuffer TLB 为一种具有并行查询能力的特殊高速缓冲存储器 内容为页表中的部分或全部 一般可存放16 512个页表项 CPU产生的逻辑地址的页首先在快表中寻找 若找到 命中 就找出其对应的物理块 若未找到 未命中 再到页表中找其对应的物理块 并将之复制到快表 若快表中内容满 则按某种算法淘汰某些页 2 具有快表的地址变换机构 AddressTransformMechanismwithFast table 局部性原理 快表 具有快表的地址变换机构 3 1250 关于快表的讨论 因成本关系 快表不是很大 通常只能存放16 512个页表项 这对中小作业 已有可能把全部页表放在其中 但对大型作业 只能放一部分 此时 配置快表的效果决定于快表访问时的命中率 如 检索快表时间为20ns 访问内存为100ns 若能在快表中检索到CPU给出的页号 则CPU存取一个数据共需120ns 否则 总需220ns的时间 再假定访问联想存储器时的命中率分别为0 50 80 90 98 时 其有效访问时间如下表所示 选用8 12项组成的快表 并采用适当的替换策略 在快表中匹配成功的可能性可达80 90 可见 由于增设了快表 可使访问数据的时间 比单周期的访问时间要延长40 22 但如果不引入快表 其时间将延长一倍 五 两级和多级页表 Two levelandMulti levelPageTable 1 问题引入问题 一个具有32位逻辑地址空间的分页系统 页面大小为212 4KB 每个页表项占4B 问 1 一个进程页表最多有多少个表项 2 一个进程页表最多需要占多大的内存 如何存放 220 1M个 1M 4B 4MB 页表需连续存放 则需连续的1K 1024 个内存物理块 解决方案 2 只将当前需要的部分页表项调入内存 大页表问题 1 页表本身采用离散分配方式 对页表进行分页 将各页面离散的分别放在不同物理块中 2 两级页表 0号小页表放在1011号物理块中 1号小页表1078号物理块 2号小页表2096号物理块 1023号小页表9500号物理块 如 上例中 将4M页表继续分页 一个物理块为4K 因此每1K 1024 个表项为一页 每个表项占4B 占一个物理块 外层页表需一个物理块 其地址放入进程PCB 二级页表实现 根据页面大小对逻辑地址空间分页 建立一个外层页表 外层页表的表项记录的是某页表分页 小页表 在内存中存放的物理块号 内层页表 进程页表 的表项记录的是某页在内存中的物理块号 如图将外层页表地址放在进程PCB中 设置一外层页表寄存器 存放外层页表的始址 该方式把连续变为离散 页表所占总空间不但没有减少反而增多 访问内存次数增加 3 地址变换 例如 一个具有32位逻辑地址空间的分页系统 页面大小为4KB 每个页表项占4B 其外层页表和页表如图所示 问 逻辑地址4098对应的物理地址应是多少 解答 根据题目确定地址结构为 求得4098的逻辑页号P和页内地址dP INT 4098 4K 1d 4098MOD4K 2 d 2 P 1 1号逻辑页所处的小页表号P1和在该小页表页内地址P2P1 INT 1 1024 0P2 1MOD1024 1 P1 0 P2 1 查找外层页表找到0号小页表的物理块号为1011 然后查找1011号物理块 从中找出第1个表项内容为4 即4号物理块 最终物理地址为 4 2 4 4K 2 16386 基本分页管理方式小结 优点 没有外碎片 每个页内碎片不超过页大小 内存利用率较高 一个程序不必连续存放 实现了离散分配 便于改变程序占用空间的大小 即随着程序运行而动态生成的数据增多 地址空间可相应增长 缺点 程序全部装入内存 作业 进程的大小仍受内存可用物理块数的限制 管理页表 需要硬件支持 尤其 快表 增大系统开销 内存访问的效率下降 不能实现真正的共享 不支持动态链接 分页存储管理的主要目的是提高内存的利用率 在分页管理模式中 逻辑地址空间是一维线性的 是连续的 页是根据内存地址空间按固定大小进行划分 因此每一页的内容逻辑上不一定相关 这影响了共享 换入换出时的效果 4 4基本分段存储管理方式BasicSegmentedMemoryManagement 分段存储管理方式的引入基本分段存储管理方式基本原理基本分段存储管理方式地址变换机构 一 分段存储管理方式的引入 IntroductionofSegmentedMemoryManagement 程序的模块化设计 作业由若干具有完整逻辑意义的信息段组成 以页为内存分配单位 页的大小相等 信息段大小不一 如何使内存管理符合程序的模块化设计思想 main 子程序1 子程序2 分段 以信息的逻辑单位为内存分配的基本单位 方便用户设计 模块化 CALL X 转移到子程序X中的入口点YLOAD1 A 将段A中的D单元的值读入寄存器1便于信息共享 信息保护 动态链接 动态增长 引入分段的优点 二 分段系统的基本原理 Basicprincipleofsegmentedsystem 1分段 作业的地址空间被划分为若干个段 每段定义了一组逻辑信息 各段长度不等 每段有段名 号 每段从0开始编址并采用一段连续的地址空间 分段系统中的逻辑地址是二维的 表示为 段号 段内地址 区分分页 如一个32位的逻辑地址 可为 可知每段最大长度为 216 64KB 最多允许有64K个段 内存的物理地址空间开始不作划分 类似于动态分区分配方式 但不再是以进程为单位进行连续区的分配 而是以段为基本单位 即为每段分配一个连续的内存区域 各段间的内存空间是可以不邻接 第0段 第1段 第2段 第3段 0 100K 150K 300K 500K 2 内存分配 各段处于内存的不同区域 在运行过程中为保证可以找到各段 要设置一个 段表 包括 段号 段长 段起始地址 基址 等 程序的每一个段占据段表的一个表项 作用是实现从逻辑段到物理内存区的映射 即对于某个段号 可以通过段表找到内存中该段的起始地址 段表和页表一样 可放于一组寄存器中 但更常见的是放于内存中 其起始地址和长度存入进程的PCB 3 段表 逻辑地址 分段系统的地址变换过程 设置一个段表寄存器 存放段表始址和段表长度TL 三 基本分段地址变换机构 比较段号S和段表长度TL 若S TL 则GOTO 否则产生越界中断 由段表寄存器中的段表始址和段号S 找到段表用及其中的对应表项 读出该段始址 比较段内地址D和段长SL 若D SL 则GOTO 否则产生越界中断 物理地址 该段始址 段内地址 若段表放在内存中 则每访问一个数据 都要访问两次内存 因此 在分段存储管理方式中 也可设置快表 以提高访问速度 地址变换过程 例如 段式存储器管理系统中 其段表如表所示 画出逻辑地址 2 100 的变换为物理地址的变换过程 三 信息共享 Informationsharing 因为段是信息的逻辑单位 代表一个较完整的模块 且每段有一个段名 所以有利于用户的共享和保护 基本分页相比分段不宜于实现共享和保护 因为分页方式下 一段共享代码 可重入码 纯代码 可能会在多个页中 因此共享或保护需对多个页操作 需要对多个表项操作 而分段系统中可把一段共享代码看作一个段 只对该段操作 只对段表的一个表项操作即可 是一段允许多个进程同时使用的代码 可重入性 代码多次被多个进程执行 结果仍保持正确 可重入性的保证 1 不允许任何进程对可重入代码修改 2 进程在可重入代码中使用自己的局部性数据区 即可重入代码中一般不使用全局数据 例如 可重入代码 纯代码 共享代码 分页系统中共享editor的示意图 分段系统中共享editor的示意图 1 页是信息的物理单位 分页目的 提高内存利用率 段是信息的逻辑单位 分段目的 满足用户需求 2 页大小固定由系统确定 逻辑地址划分由硬件实现 段大小不定 逻辑地址划分由编译程序等软件完成 3 分页的进程地址空间是一维的 分段的进程地址空间是二维的 基本分段管理方式小结 基本分段和分页的区别 分页和分段的优缺点 分页管理优点 解决了碎片问题便于管理缺点 不易实现共享不便于动态连接 分段管理优点 便于动态申请内存管理便于共享和动态链接满足用户需求通常段比页大 因而段表比页表短 可以缩短查找时间 提高访问速度缺点 产生碎片 四 段页式存储管理方式 Segment pagedMemorymanagement 1 基本原理用户程序分段 段内分页 每段有段名 段号 每段内部的页有一连续的页号 系统内存分块 每块装入一页 各块之间可以不连续 一个有效地址 段名 段内地址 段名 段内页号 页内地址 分段和分页结合 作业地址空间和地址结构 相应的应设置段表 页表 段表可包括 段号 本段的页表始址 页表长度 状态 标志本段在内 外存 等 页表包括 页号 物理块号等 段表 内存 2地址变换过程 段内位移量 设一段表寄存器 存放段表始址及长度 比较段号S和段表长度TL 若S TL GOTO 否则产生越界中断 由段表始址和段号找到该段在段表中的对应表项 得到该段的页表始址 取逻辑地址中的段内页号 与页表始址一同找到该页表项 读出物理块号 物理块号和页内地址构成物理地址 问 在段页式存储管理方式中 每访问一次数据 需访问几次内存 如何提高内存访问速度 三次 1段表 2页表 3数据 设置快表 表项中应包括段号 页号 物理块号 段页式存储管理的优缺点 同时具备分段和分页管理的优点 分散存储 内存利用率较高 便于代码或数据共享 支持动态链接等 访问效率下降 一次访问转换成了三次访问 分页 分段 段页式存储管理方式 重点掌握两个内容 1 思想 包括用户地址空间的划分 内存地址空间的划分 逻辑地址结构 内存的分配 2 逻辑地址到物理地址的变