第5章 虚拟存储器.ppt

第5章虚拟存储器 5 0交换技术与覆盖技术5 1虚拟存储器概述5 2请求分页存储管理方式5 3页面置换算法5 4抖动与工作集5 5请求分段存储管理方式 5 0交换技术与覆盖技术 5 0 1覆盖技术覆盖 overlay 技术的目标是在较小的可用内存中运行较大的程序 常用于多道程序系统 与分区存储管理配合使用 覆盖技术不需要任何来自操作系统的特殊支持 可以完全由用户实现 即overlay 是用户程序自己附加的控制 1 覆盖技术的原理通常一个程序的几个代码段或数据段是按照时间先后来占用公共的内存空间的 它们装入时可以采用如下几种 1 将程序的必要部分 常用功能 的代码和数据常驻内存 2 将可选部分 不常用功能 在其他程序模块中实现 平时存放在外存中的覆盖文件中 在用到时才装入到内存 3 不存在调用关系的模块不必同时装入到内存 从而可以相互覆盖 覆盖技术的原理如图5 1所示 图5 1覆盖技术原理 2 覆盖技术的优缺点覆盖技术使一个作业能够有效地利用内存 但是它有如下的缺点 编程时必须划分程序模块和确定程序模块之间的覆盖关系 增加了编程复杂度 从外存装入覆盖文件 是以时间延长来换取空间节省的 各个作业占用的分区仍然存在着碎片 5 0 2交换技术交换技术 swapping 最早应用于麻省理工学院的兼容分时系统CTSS中 交换技术用于多个程序并发执行的系统中 当某一个作业的存储空间不够时 可以将暂时不能执行的程序所占用的地址空间换出到外存中 从而获得空闲内存空间来装入新程序 或读入保存在外存中而目前处于就绪状态的程序 交换单位为整个进程的地址空间 交换技术常用于多道程序系统或小型分时系统中 可与分区存储管理配合使用 它又称作 对换 或 滚进 滚出 roll in roll out 程序暂时不能执行的可能原因是 处于阻塞状态 低优先级 确保高优先级程序先执行 其处理方法同上 如果将简单的交换技术加以发展 就可用于固定分区或者可变分区的存储管理技术中 在采用可变分区存储管理的多道程序设计中 当要运行一个高优先级的作业而又没有足够的空闲内存时 可以按某一个算法从主存中换出一个或多个作业 腾出空间装入高优先级的作业 使之能够运行 在Windows操作系统中 就是利用交换技术运行多个任务的 交换技术的优点 增加并发运行的程序数目 并且给用户提供适当的响应时间 编写程序时不影响程序结构 交换技术的缺点 对换入和换出的控制增加了处理机开销 程序整个地址空间都进行传送 没有考虑执行过程中地址访问的统计特性 还存在两个问题 程序换入时的重定位问题 交换过程中传送的信息量特别大的问题 5 1虚拟存储 5 1 1虚拟存储管理的引入虚拟存储 virtualmemory 管理的基础是程序的局部性原理 principleoflocality 所谓局部性原理 是指程序在执行过程中的一个较短时期内 所执行的指令地址和指令的操作数地址分别局限于一定的区域 主要表现为 1 时间局部性 指一条指令的一次执行和下次执行 一个数据的一次访问和下次访问都集中在一个较短时期内 2 空间局部性 指当前指令和邻近的几条指令 当前访问的数据和邻近的数据都集中在一个较小区域内 局部性原理具体体现在以下几方面 程序中大部分是顺序执行的指令 少部分是转移和过程调用指令 过程调用的嵌套深度一般不超过5层 因此执行的范围不超过这组嵌套的过程 程序中存在相当多的循环结构 它们由少量指令组成 而被多次执行 程序中存在相当多的对一定数据结构的操作 如数组操作 这些操作往往局限在较小范围内 虚拟存储管理就是基于程序的局部性原理 利用大容量的磁盘作为后备 当作业要占用的内存空间不够大时 将作业的一部分暂时先放在磁盘上 当需要时再从磁盘上调入 虚拟存储的基本原理是在程序装入时 不必将其全部读入到内存 而只需将当前需要执行的部分页或段读入到内存 就可让程序开始执行 引入虚拟存储技术的好处是 可在较小的可用内存中执行较大的用户程序 可在内存中容纳更多程序并发执行 不必影响编程时的程序结构 与覆盖技术比较 提供给用户可用的虚拟内存空间通常大于物理内存 realmemory 在虚拟存储器中 允许一个作业分多次调入内存 如果采用连续存储分配方式时 应将作业装入一个连续的内存区域中 为此 须事先为它一次性地申请足够的内存空间 以便将整个作业先后分多次装入内存 这不仅会使相当一部分内存空间都处于暂时或永久的空闲状态 造成内存资源的严重浪费 而且也无法从逻辑上扩大内存容量 因此 虚拟存储器的实现 都毫不例外地建立在离散分配的存储管理方式的基础上 虚拟存储技术分为三类 请求分页 请求分段和请求段页式存储管理 5 2请求分页存储管理方式 虚拟页式存储管理 1 基本工作原理在分页式存储管理中 必须一次性将所有的页面全部装入 有可能造成其他的作业无法装入 从而造成系统的性能下降 有三个问题必须解决 1 如果不把一个作业全部装入内存 那么该作业能否开始运行并运行一段时间呢 2 在作业运行了一段时间之后 必然要访问没有装入的页面 也就是说 要访问的虚页不在内存 系统怎么发现呢 3 如果系统已经发现某一个虚页不在内存 就应该将其装入 怎么装入呢 答案是 1 程序在运行期间 往往只使用全部地址空间的一部分 2 根据程序局部性原理 程序员在写程序的时候总是满足结构化的思想 使得程序具有模块化的特点 3 使用缺页中断即可 而缺页中断是属于程序中断的 2 页表表项在请求分页系统中所使用的主要数据结构仍然是页表 它对页式存储系统中的页表机制进行了扩充 但其基本作用仍然是实现由用户地址空间到物理内存地址空间的映射 为了实现请求分页式存储管理 必须对分页式存储管理中的地址变换机构进行扩充 除了页号和对应的物理块号外 还增加了存在位 修改位 外存地址和访问统计等 如图5 2所示 图5 2扩充的页表 驻留位 中断位 存在位 presentbit 用于指示该页是否已经调入了物理内存中 修改位 modifiedbit 表示该页调入内存之后是否被修改过 外存地址 diskaddress 用于指出该页在外存上的地址 供调入该页时使用 访问统计位 描述了在近期内被访问的次数或最近一次访问到现在的时间间隔 可作为淘汰页面时的参数 3 缺页中断在请求分页存储系统中 由CPU的地址变换机构根据页表中的状态位判断是否产生缺页中断 pagefault 然后调用操作系统提供的中断处理例程 缺页中断的特殊性主要体现在如下两点 1 缺页中断是在指令执行期间产生和进行处理的 而不是在一条指令执行完毕之后 所缺的页面调入之后 重新执行被中断的指令 2 一条指令的执行可能产生多次缺页中断 如 swapA B指令 若指令本身和两个操作数A B都跨越相邻外存页的分界处 则产生5次缺页中断 不可能出现指令本身的两次缺页 如图5 3所示 图5 3一条指令的5次缺页中断 影响缺页次数的因素有以下几种 1 分配给进程的物理页面数 2 页面本身的大小 3 程序的编制方法 4 页面淘汰算法 例5 1在一个请求分页存储管理系统中 把主存分成大小为128字节的块 设有一个用户要把128 128的数组置成初值 0 在分页时把数组中的元素每一行放在一页中 假定分给用户可用来存放数组信息的工作区只有一块 只能放数组中的一行元素 用户编制了如下两个不同的程序来实现数字的初始化 1 varA array 1 128 ofarray 1 128 ofinteger forj 1to128dofori 1do128doA i j 0 那么 由于该程序按列把数组中的元素逐一地清0 所以每执行一次A i j 0就会产生一次缺页中断 假设一开始已经把第一页装入主存 则程序执行时就可以对A 1 1 赋0 但下一个元素A 2 1 不在该页中 就产生缺页中断 这样总共要产生128 128 1次缺页中断 2 varA array 1 128 ofarray 1 128 ofinteger fori 1to128doforj 1do128doA i j 0 那么 每装入一页就能对一行128个元素逐一的清零 之后才产生缺页中断 同样假设一开始已经把第一页装入主存 则程序执行时总共只产生128 1次缺页中断 4 页面调度策略1 页面调入策略页面调入策略决定了什么时候将一个页由外存调入物理内存 1 请求调页 demandpaging 只调入发生缺页时所需的页面 2 预调页 prepaging 在发生缺页需要调入一页时 一次调入该页以及相邻的几个页 通常对外存交换区的I O操作效率比文件区的高 关于调入页面 通常有两种做法 进程装入时将其全部页面复制到交换区 以后总是从交换区调入 执行时调入速度快 但要求交换区空间较大 是未被修改的页 都直接从文件区读入 而被置换时不需要调出 已被修改的页面 被置换时需要调出到交换区 以后从交换区调入 这种方式节省了交换区空间 但是也可能引发一些问题 2 页面置换策略当进程产生缺页中断时 内存管理器还必须确定将调入的虚拟页放在物理内存的什么地方 用于确定最佳位置的一组规则称为 置页策略 如果缺页中断发生时物理内存已满 则由 页面置换策略 确定哪个虚页面必须从内存中移出 为新的页面腾出空间 在请求分页系统中 可以采用两种分配策略 即固定分配和可变分配 在进行置换时 也可以采用两种策略 即全局置换和局部置换 将分配策略组合起来 有如下三种策略 不包括固定分配全局置换 因为对各进程进行固定分配时不可能进行全局置换 1 固定分配局部置换 fixedallocation localreplacement 采用该策略时 可以根据进程的类型 为每一个进程分配固定页数的内存空间 且在整个运行期间不再改变 2 可变分配全局置换 variableallocation globalreplacement 采用这种策略时 先为系统中的每一个进程分配一定数量的物理块 操作系统本身也保持一个空闲物理块队列 3 可变分配局部置换 variableallocaton localreplacement 采用这种策略时 同样根据进程的类型 为每一个进程分配一定数目的内存空间 3 物理块分配算法在采用固定分配策略时 如何将系统中可供分配的所有物理块分配给各个进程 可采用下述几种算法 1 平均分配算法这是将系统中所有可供分配的物理块平均分配给各个进程 例如 当系统中有100个物理块 有5个进程在运行时 每个进程可分得20个物理块 这种方式貌似公平 但实际上是不公平的 因它未考虑各进程本身的大小 如有一个进程其大小为200页 只分给它20块 显然会有很高的缺页率 而另一个进程只有10页 却又20个物理块闲置 2 按比例平均分配算法根据进程的大小按比例分配物理块的算法 如果系统中有n个进程 每个进程的页面数为Si 则系统中各进程页面数总和为 假定系统中可用的物理块总数为m 则每个进程能分到的物理块数为bi 将有 5 页面淘汰算法 pagereplacementalgorithm 页面淘汰 置换 算法决定在需要调入页面时 内存中哪个物理页面被置换 页面置换算法的出发点是把未来不再使用的或者短时期内较少使用的页面调出 页面置换常用的算法有以下几种 1 最佳算法 optimal OPT 置换 未来不再使用的 或 在离当前最远位置上出现的 页面 2 先进先出页面淘汰算法 FirstInFirstOut FIFO 置换建立最早的页面 3 第二次机会淘汰算法 SCR 按照先进先出算法选择某一页面 检查其访问位 如果为0 则淘汰该页 如果为1 则给第二次机会 并将访问位置0 4 页面缓冲算法 pagebuffering 是对FIFO算法的发展 通过被置换页面的缓冲 有机会找回刚被置换的页面 具体做法是 用FIFO算法选择被置换页 把被置换的页面放入两个链表之一 即如果页面未被修改 就将其归入到空闲页面链表的末尾 否则将其归入到已修改页面链表的末尾 需要调入新的物理页面时 将新页面内容读入到空闲页面链表的第一项所指的页面 然后将第一项删除 空闲页面和已修改页面仍停留在内存中一段时间 如果这些页面被再次访问 只需较小开销 而被访问的页面可以返回作为进程的内存页 当已修改页面达到一定数目后 再将它们一起调出到外存 然后将它们归入空闲页面链表 这样能大大减少I O操作的次数 5 最近最少使用页面淘汰算法 LRU 置换内存中最久未使用的页面 这是局部性原理的合理近似 其性能接近最佳算法 但由于需要记录页面使用时间的先后关系 因此硬件开销太大 硬件机构可以是 一个特殊的栈 把被访问的页面移到栈顶 于是栈底的就是最久未使用页面 每个页面设立移位寄存器 被访问时左边最高位置1 定期右移并且最高位补0 于是寄存器数值最小的就是最久未使用页面 LRU的软件解决方案 最不经常使用 NFU 淘汰访问次数最少的页面 实现的办法是设置一个软件计数器 一个页一个 初值为0 每次时钟中断时 计数器加R 发生缺页中断时 选择计数器值最小的一页淘汰 可以对此算法进行改进 当计数器在加R前先右移一位 R位加到计数器的最左端 这称为页面老化算法 最近未使用页面淘汰算法 NotRecentlyUsed NRU 也称轮转算法 clock 它是LRU和FIFO算法的折衷 具体做法是 每页有一个使用标志位 usebit 若该页被访问 则置userbit 1 置换时采用一个指针 从当前指针位置开始按地址先后检查各页 寻找userbit 0的页面作为被置换页 指针经过的userbit 1的页都修改为userbit 0 最后指针停留在被置换页的下一个页 Y N 替换指针 6 页面淘汰算法分析例5 2设页面走向为P 4 3 2 1 4 3 5 4 3 2 1 5 主存容量M 3 置换算法采用FIFO 则缺页中断次数和缺页率如表4 2所示 表5 2FIFO的性能分析 M 3 例5 3设M 4 其余同例5 2 缺页中断次数和缺页率如表5 3所示 表5 3FIFO的性能分析 M 4 缺页中断率与系统设定的内存页面数M有关 一般的 M的值越大 缺页中断率越小 但也有例外 此例当中 M增加 但f不减少反而增加了 称之Belady奇异现象 例5 4设页面走向同例5 2 M 3 置换算法为LRU 则系统模型如表4 4所示 由于采用了LRU算法 因此M中各列按访问的时间顺序排列 最近被访问的页面在最前面 由表可算出缺页中断次数F 10 缺页率f 10 12 83 表5 4LRU的性能分析 M 3 例5 5设M 4 其余同例4 4 则系统性能模型如表4 5所示 表5 5LRU的性能分析 M 4 5 4 抖动 与工作集1 颠簸 抖动 thrashing 在虚存中 页面在内存与外存之间频繁调度 以至于调度页面所需时间比进程实际运行的时间还多 此时系统效率急剧下降 甚至导致系统崩溃 这种现象称为颠簸或抖动 其产生的主要原因是 页面淘汰算法不合理和分配给进程的物理页面数太少 2 常驻集 residentset 1 常驻集与缺页率的关系 每个进程的常驻集越小 则同时驻留内存的进程就越多 可以提高并行度和处理器的利用率 另一方面 进程的缺页率上升 使调页的开销增大 进程的常驻集达到某个数目之后 再给它分配更多的页面 缺页率不再明显下降 2 常驻集大小的确定方式 依据常驻集大小在进程执行过程中是否可变 分为两种方式 固定分配 fixed allocation 常驻集大小固定 有如下三种分配技术 各进程平均分配 根据程序大小按比例分配 按优先权分配 可变分配 variable allocation 常驻集大小可变 可按照缺页率动态调整 增大或减小 常驻集 性能较好 但增加了算法运行的开销 3 置换范围 replacementscope 被置换的页面局限在本进程或允许在其他进程 实际上 置换算法所使用的访问统计数据 如使用位usebit 是包含在进程页表而不是在物理页面表里 即记录的是对虚拟页面而不是对物理页面的访问 所以进行局部置换应更容易 局部置换 localreplacement 容易进行性能分析 全局置换 globalreplacement 更为简单 容易实现 运行开销小 4 常驻集大小和置换范围的配合 有三种策略 不包括 固定分配全局置换 因为对各进程进行固定分配时不可能进行全局置换 固定分配 局部置换 这时的主要问题是进程开始前要依据进程的类型决定分配多少页面 多了会影响并发水平 少了会使缺页率过高 可变分配 全局置换 这时操作系统会一直维持一定数目的空闲页面 以进行快速置换 可变分配 局部置换 这时的操作系统也要维持一定数目的空间页面 但是对置换算法的选择却比第二种策略简单 因此它是比较好的策略 3 工作集 workingset 模型工作集模型是1968年由Denning提出的 引入工作集的目的是依据进程在过去的一段时间内访问的页面来调整常驻集大小 根据程序的局部性原理 一般情况下 进程在一段时间内总是集中访问一些页面 这些页面称为活跃页面 1 工作集的定义 工作集 workingset 是一个进程执行过程中所访问页面的集合 可用一个二元函数W t 表示 其中 t是执行时刻 是一个虚拟时间段 称为窗口大小 windowsize 它采用 虚拟时间 单位 即阻塞时不计时 大致可以用执行的指令数目或处理器的执行时间来计算 工作集是在 t t 时间段内所访问的页面的集合 W t 指工作集大小即页面数目 2 工作集的性质 随 单调递增 W t W t a 其中a 0 工作集大小范围 1 W t min n 其中n是进程的总页面数 3 工作集大小的变化 进程开始执行后 随着访问新页面而逐步建立较稳定的工作集 当内存访问的局部性区域的位置大致稳定时 工作集大小也大致稳定 当局部性区域的位置改变时 工作集快速扩张和收缩过渡到下一个稳定值 工作集大小的变化如图4 39所示 图4 39工作集大小的变化 4 利用工作集进行常驻集调整的策略 记录一个进程的工作集变化 定期从常驻集中删除不在工作集中的页面 总是让常驻集包含工作集 5 工作集的困难 工作集的过去变化未必能够预示工作集的将来大小或组成页面的变化 记录工作集变化要求开销太大 对工作集窗口大小 的取值难以优化 而且通常该值是不断变化的 4 缺页率算法 PageFaultFrequency PFF 1 PFF算法 页面被访问时的处理 每个页面设立使用位 usebit 在该页被访问时设置usebit 1 缺页时的处理 每次缺页时 由操作系统计算与上次缺页的 虚拟时间 间隔t 缺页时对常驻集的调整 定义一个 虚拟时间 间隔的阈值 threshold F 依据t和F来修改常驻集 2 和页面缓冲算法 pagebuffering 配合使用 可以获得良好的性能 3 缺页率算法的主要缺点 当局部性区域的位置改变时 工作集的变化处于过渡阶段 其快速扩张使较多新页面添加到进程的常驻集中 其中较少使用的页面至少还要经过一段F虚拟时间才会被淘汰 因而带来较多不必要的调页开销 4 可变采样间隔算法 Variable intervalSampledWorkingSet VSWS 1 VSWS算法 使用3个参数 采样间隔时间的下限M 采样间隔时间的上限L 一个采样间隔内允许发生的缺页次数的上限Q 常驻集的调整 每个页面设立使用位 userbit 在每个采样间隔的开始设置各页的userbit 0 而在每个采样间隔的结束只保留userbit 1的页面在常驻集中 其余页面从常驻集中删除 采样间隔划分 每次缺页时 对缺页次数加1 2 VSWS算法的优点 在局部性区域位置改变时 缺页率上升 通过缩短采样间隔 删除无用页面 可降低常驻集扩张的峰值 6 虚拟存储中的负载控制负载控制讨论的是操作系统要在内存中驻留多少个并发进程才是较好的 1 改善时间性能的途径 降低缺页率 缺页率越低 虚拟存储器的平均访问时间延长得越小 提高外存的访问速度 外存和内存的访问时间比值越大 则达到同样的时间延长比例所要求的缺页率就越低 2 负载控制 loadcontrol 策略负载控制策略是 在避免出现抖动的前提下 尽可能提高进程并发水平 1 基于工作集策略的算法 如PFF VSWS 它们隐含负载控制策略 只有那些常驻集足够大的进程才能运行 从而实现对负载的自动和动态控制 2 L S判据 策略 Denning 1980 让缺页的平均间隔时间 是指真实时间而不是虚拟时间 等于对每次缺页的处理时间 即缺页率保持在最佳水平 这时CPU的利用率达到最大 一种类似的策略称为 50 判据 策略 即让外存交换设备保持50 的利用率 这时CPU也达到最高的利用率 3 基于轮转置换算法的负载控制策略 定义一个轮转计数 描述轮转的速率 即扫描环形页面链的速率 当轮转计数少于一定的阈值时 表明缺页较少或存在足够的空闲页面 当轮转计数大于阈值时 表明系统的进程并发水平过高 需降低系统负载 4 7 4虚拟段式存储管理1 段表内容为实现虚拟段式存储管理的各项功能和管理需要 在进程段表中添加了如下各项 1 标志位 如存在位 presentbit 修改位 modifiedbit dirtybit 扩充位 该段是否增加过长度 2 访问统计位 如使用位 usebit 3 存取权限位 如读R 写W 执行X 4 外存地址 本段在外存的起始地址 2 越界中断处理进程在执行过程中 有时需要扩大分段 如数据段的扩充 由于要访问的地址超出原有的段长 所以引发越界中断 操作系统处理中断时 首先判断该段的 扩充位 如可扩充 则增加段的长度 否则按出错处理 3 缺段中断处理在请求分段系统中 采用的是请求调段策略 CPU的硬件逻辑要根据段表表项进行地址变换或者产生缺段中断 请求分段存储管理与请求分页存储管理不同之处在于 指令和操作系统一定不会跨越在段边界上 但是 在请求分段系统中 一般会增加存取权限的违法中断和段的越界中断 在请求调段时 先检查内存中是否有足够的空闲空间 若有 则装入该段 修改有关数据结构 中断返回 若没有 则检查内存中空闲区的总和是否满足要求 如是 则应采用紧缩技术 再转 否则 淘汰一些段 再转 4 请求分段系统的内存分配策略1 段的动态链接在程序开始运行时 只将主程序段装配好并调入内存 其他各段的装配是在主程序段的运行过程中逐步完成的 2 链接间接字机器指令可采用直接寻址或间接寻址方式 采用间接寻址时 间接地址指示的单元的内容称为间接字 在间接字中 包含了直接地址及附加的状态位 其格式如图4 40所示 图4 40链接间接字格式 3 链接中断处理链接中断处理的步骤是 1 根据链接间接字找出要访问段的符号名和段内地址 2 分配段号 检查该段是否在内存 若不在内存 则从外存调入 并登记段表 修改内存分配表 3 修改间接字 修改链接标志位为0 并修改直接地址 4 重新启动被中断的指令执行 5 6高速缓冲存储器 5 6 1高速缓存的组织由于CPU的指令处理速度与内存中指令的访问速度存在差异 可达到一个数量级的差异 如IntelPentiumPro平均一个时钟周期可执行3条指令 因此为提高CPU的利用率 在CPU与内存之间组织了一个高速缓存结构 如图4 41所示 图4 41高速缓存的组织结构 高速缓存由三部分组成 高速缓冲存储器 缓存目录和缓冲控制器 1 高速缓冲存储器 主要作用是缓存内存中数据 2 缓冲目录 描述各缓冲存储器块的状态 内存地址行号 相应缓存块对应的内存地址 24位 为行号 13位 列号 5位 字节数 6位 3个状态位描述相应缓存块的状态 3 缓存控制器 负责缓存目录的维护 并利用缓存淘汰算法进行缓存的更新 4 8 2缓存的工作过程在不同类型的内存操作时 缓存会有不同的工作过程 具体的缓存工作过程如下 1 CPU读数据 缓存控制器自动查找缓存目录 确定相应内存数据是否在缓存中 查找过程 依据读操作的地址确定查找缓存目录的列号 比较缓存目录相应列的各区行号与地址行号 判断有效位是否为0 依据查找结果 有两种可能的操作 如果在缓存 则从缓存中读数据 并修改访问标志 如果不在缓存 则从内存中读数据 同时该块内容被送到缓存相应列的某块 2 CPU写数据 查找缓存目录 确定相应地址是否在缓存中 如果在缓存 则修改缓存内容 并把缓存目录中相应修改位置1 这时有两种做法 立即写 在内存与缓存的相应块同时写 惰性写 数据只写入缓存 不马上写入内存 当该缓存块被淘汰时 才写回内存 如果不在缓存 则先把内存读入缓存 再在缓存中修改 3 通道向内存写数据 数据被写入内存 缓存控制器同时查找缓存目录 如果有 则修改相应表项的有效位为1 4 通道从内存读数据 如果在缓存中 则从缓存中读数据到通道 如果不在缓存中 则从内存中读数据到通道 但并不同时送到缓存 5 7内存管理实例分析 5 7 1UNIXS5的内存管理1 对换1 对换设备空间的管理对换设备是块设备 如经过构造的磁盘盘区 核心分配对换空间时是按连续的块为一组进行的 进程使用对换空间是临时性的 这取决于进程调度的方式 2 进程的换出和换入如果核心需要内存空间 它就把一个进程换出到对换设备中 这可能是由于下列原因引起的 创建子进程时必须为它分配空间 要增加进程的大小 栈区自然增长变大和核心期望把某些先前换出的进程重新换入内存 图4 42对换一个进程空间到对换设备上 对换程序算法 换入以前被换出的进程 换出其他进程 以腾出内存空间 输入 无输出 无 loop for 所有被换出的处于就绪状态的进程 挑选被换出时间最久的进程 if 没有找到这种进程 sleep 换入事件 gotoloop if 在内存中有供进程使用的足够空间 把进程换入内存 gotoloop loop2 在修改过的算法中从这里进行循环for 所有在内存 非终止态且未封锁的进程 if 有正在睡眠的进程 选择进程 其 优先数 驻留内存时间 在数值上最大 else 没有睡眠态进程选择进程 其 驻留内存时间 nice值 在数值上最大 if 被选进程没有睡眠或者驻留条件不满足要求 sleep 换出事件 else换出进程gotoloop 在修改过的算法中 应gotoloop2 2 请求分页1 数据结构核心提供了4个主要的数据结构用来支持低级的存储管理和请求分页 它们是 页表项 盘块描述字 页框数据表 pageframedatatable 和对换用表 一旦系统生成 核心就为页框数据表分配空间 而为其他结构动态地分配内存页面 页表项包括该页的内存地址 读 写或执行的保护位和下列信息位 有效 valid 位 访问 reference 位 修改 modify 位 复制写 copyonwrite 位和年龄 age 位 每一个页表项都与一个盘块描述字联系在一起 盘块描述字对逻辑页面的磁盘副本进行说明 如图4 43所示 图4 43页表项和盘块描述字 页框数据表对整个内存的每个页面进行描述 它是通过页面号进行索引的 每项包含以下内容 1 页面状态 说明该页面是在对换设备上或者是可执行文件 DMA当前正对该页面操作 从对换设备中读数据 或者该页面可以重新分配 2 访问该页面的进程数目 访问计数值等于访问该页的合法页表项目数 它可能不同于共享该页所在分区的进程数 如在fork算法中 3 逻辑设备 对换或文件系统 和该页所在的盘块号 4 指向在空闲页面链表上和在页面散列队列中的其他页框数据表项的指针 图4 44给出了页表项 盘块描述字 页框数据表项和对换用计数表间的关系 一个进程虚拟地址1493K映射到一个页表项 它指向物理页面794 该页表项的盘块描述字说明了该页存于对换设备1的2743块中 该虚拟页面的对换用计数值为1 说明只有一个页表项指向对话设备上的一个页面 图4 44请求分页数据结构间的关系 2 页面淘汰进程页面淘汰进程 又称页面窃取进程 pagestealerprocess 是一个核心进程 它把不再是进程工作集部分的那些页面换出内存 它是在系统初启时由核心创建的 在系统活动期间它一直存在 内存页面有两种状态 页面 老化 但还不适宜对换 页面适于对换且可用于重新分给其他虚拟页面 当页面淘汰进程决定换出一个页面时 它要考虑该页的副本是否在对换设备上 这有三种可能性 1 如在对换设备上没有该页的副本 则页面淘汰进程把它放在准备换出的队列中 然后继续找其他可以被换出的页 而在逻辑上认为对换已经完成 2 如该页面在对换设备上已有副本 并且内存中的内容未被修改过 页表项的修改位被清 则核心清除相应页表项的有效位 减少页框数据表项的访问次数 并把该页放到自由链的末尾 供以后分配使用 3 如该页在对换设备上有副本 但是其内存的内容被修改过 则核心将该页换出 并且释放它刚才占用过的的对换区 3 缺页缺页又称页面故障 pagefaults 系统可出现两类缺页 有效缺页和保护性缺页 1 有效缺页处理 对于进程虚拟地址空间以外的页面和虽在其虚拟地址空间内但当前未在内存的页面 它们的有效位是0 表示缺页 如果一个进程试图存取这样的一个页面 则导致有效缺页 此时核心调用有效缺页处理程序 有效缺页处理程序的算法如下 输入 进程出现缺页的地址输出 无 按照缺页地址找到分区表 页表项 盘块描述字 封锁分区表 if 地址在虚拟地址空间之外 向进程发信号 段越界 gotoout if 地址现在是有效的 进程可能已经在睡眠gotoout if 页面在自由链盘中 从自由链中移走该页 调整页表项 while 页面内容无效 先前已经有另外的进程出现过缺页sleep 页面内容有效事件 else 页面不在自由链中 给分区指派新页面 把新页面放入散列链 更新页框数据表项 if 页面以前未装入内存且页面 请求清0 把分到的页面清0 else 从对换设备或者执行文件中读取虚拟页面 sleep I O完成事件 唤醒诸进程 页面内容有效事件 置页面有效位 清除页面修改位和年龄位 重新计算进程优先数 out 封锁分区表 2 保护性缺页处理 它是由于进程对有效页面存取的权限不符合规定而引起的 例如 某进程试图对正文段进行改写 导致保护性缺页的另外一个原因是 一个进程想写一个页面 而该页面的复制写位在执行fork期间已经置位 核心必须确定导致保护性缺页的原因是上述哪一种 当发生保护性缺页事件后 硬件向其处理程序提供发生事件的虚拟地址 然后由处理程序进行处理 保护性缺页处理程序的算法如下 输入 进程缺页地址输出 无 按地址找到分区表 页表项 盘块描述字 页框数据表 封锁分区表if 页面不在内存 gotoout if 复制写位未置位 gotoout 实际程序错误 发信号if 页框表项访问计数大于1 与其他进程共享该页 分配内存新页面 复制老页面内容到新页面 减少老的页框表项访问计数 更新页表项 使它指向新内存页面 else 淘汰 页面 因为没有进程在用它 if 页面副本在对换设备上存在 释放该对换设备的空间 断开页面联系 if 页面在相应散列队列上 从散列队列上移走该页 设置修改位 清除页表项中的复制写位 重新计算进程优先数 检查信号 out 封锁分区表 4 9 2Windows2000 XP的内存管理内存管理器是Windows2000 XP执行程序的一部分 因此它存在于NT操作系统krnl exe中 在硬件抽象层 HAL 中没有内存管理器的任何部分 内存管理器由下列组件构成 1 一组执行程序系统服务程序 用于虚拟内存的分配 释放和管理 它们中的大多数通过Win32API或内核模式设备驱动程序接口实现 2 一个转换 translation not valid 和访问错误陷阱处理程序 用于解决硬件检测到的内存管理异常事件 并代表一个进程使虚拟页驻留 3 运行在6个不同内核模式系统线程环境中的几个关键组件 工作集管理程序 workingsetmanager 优先级为16 由平衡集管理程序 内核创建的系统线程 每秒调用一次 或在空闲内存低于某个值时调用 驱动所有的内存管理规则 例如工作集的休整 年龄和已修改页的写入 进程 栈交换程序 process stackswapper 优先级为23 执行进程和内核线程的栈换入和换出操作 修改页面的写入器 modifiedpagewriter 优先级为17 把在修改链表上的脏页面写入到正确的调页文件中 当需要减小修改链表的大小时可以唤醒这个线程 映射页面写入器 mappedpagewriter 优先级为17 把映射文件中的脏页面写入磁盘 废弃段线程 deferencesegmentthread 优先级为18 负责系统高速缓存和页面文件的增加和减少 清零页面线程 zeropagethread 优先级为0 将空闲链表内的页清零 以便使零页高速缓存能用于满足将来的零页错误 1 虚拟地址空间布局32位Windows2000 XP上的每个用户进程可以占有2GB的私有地址空间 addressspace 操作系统占有剩下的2GB地址空间 Windows2000 XP高级服务器和Windows2000 XP数据中心服务器支持一个导引选项 允许用户拥有3GB的地址空间 这两个地址空间的布局如图4 45所示 图4 45Windows2000 XP系统的虚拟地址空间布局 1 用户地址空间分布 在用户态和核心态都可访问的用户存储区为2GB 用户存储区为页交换区 可对换到外存 用户存储区的内容包括 专用进程地址空间 包括用户代码 数据和堆栈 线程环境块 TEB 包括用户态代码可修改的线程控制信息 进程环境块 PEB 包括用户态代码可修改的进程控制信息 共享用户数据页 包括系统存储区映像 为用户态可访问的系统空间 目的在于避免用户态与核心态的频繁切换 如系统时间 表4 6描述了2GB的Windows2000 XP用户地址空间的详细布局 表4 6Windows2000 XP用户地址空间的详细布局 2 系统地址空间分布 在核心态可访问的系统存储区为2GB 按交换特征 系统存储区可分为以下几个区 固定页面区 永不被换出内存的页面 如HAL特定的数据结构 页交换区 非常驻内存的系统代码和数据 如进程页表和页目录 直接映射区 常驻内存且其寻址由硬件直接变换的页面 访问速度最快 用于存放内核中频繁使用且要求快速响应的代码 如表4 7列出了带有2GB系统空间的X86系统的整体布局 X86体系结构在系统空间中有以下组成 系统代码 它包含了用于引导系统的操作系统映像 HAL和设备驱动程序 系统映射视图 它用于映射Win32 sys Win32子系统可加载内核模式部分以及它使用的内核模式图形驱动程序 会话空间 sessionspace 用于映射与用户会话相关的信息 会话工作集列表描述了驻留和正使用的区域空间部分 进程页面表 pagetable 和页面目录 pagedirectory 描述虚拟地址映射的结构 超空间 hyperspace 一个特殊的区域 被用来映射进程工作集列表和为下列操作临时映射物理页面 在自由列表中将页面清零 使其他页面表中的页面表项无效和在进程创建时设置新进程的地址空间 系统工作集列表 描述系统工作集的列表数据结构 系统高速缓存 systemcache 用于映射在系统高速缓存中打开的文件的页面 页交换区 pagedpool 可调页的系统内存堆 系统页面表项 PageTableEntries PTE 系统PTE的交换区 用于映射系统页面 例如I O空间 内核堆栈和内存描述列表 非页交换区 nonpagedpool 不可调页的系统内存堆 通常以两部分存在 一部分在系统空间较底端 一部分在系统空间较高端 崩溃转存信息 保留 用来记录有关系统故障状态的信息 HAL使用区域 为HAL相关的结构保留的系统内存 表4 7X86系统的整体布局 2 地址转换机构Windows2000 XP使用二级页表结构转换虚拟地址 一个32位虚拟地址被解释为三个独立的分量 分别是页目录索引 页表索引和字节索引 它们用于找出描述页面映射结构的索引 在二级页表结构中的第一级称为页目录 每个进程有一个页目录 第二级称为页表 每个页目录或页表有1024 210 个表项 每个表项为4个字节 由于每个页面为4KB 每个进程的地址空间可为4GB 210 210 212 如图4 46所示为X86系统中32位虚拟地址的构成 图4 46X86系统中32位虚拟地址的构成 页目录索引用于指出虚拟地址的页目录在页表中的位置 页表索引则用来确定页表项在页表中的具体位置 也就是说 页表项包含的虚拟地址被映射到物理地址 字节索引使得在物理页中能够寻找到某个具体的地址 如图4 47所示为这三个值之间的联系和它们从虚拟地址到物理地址的映射过程 其中 KPROCESS是系统核心进程 其块中保存着进程页目录的物理地址 图4 47X86系统中虚拟地址的变换 下面是虚拟地址变换的基本步骤 1 内存管理的硬件设备定位当前进程的页目录 2 页目录索引用于在页目录中指出页目录项 PageDirectoryEntry PDE 的位置 3 页表索引用于在页表中指明表项的位置 4 页表项用于确定页框的位置 5 当页表项指向了有效的页时 字节索引用于找到物理页内所需数据的地址 3 页面调度策略页面调度策略包括取页策略 置页策略和淘汰策略 1 取页策略 fetchpolicy Windows2000 XP采用按进程需要进行的请求取页和按集群方法进行的提前取页 2 置页策略 在线性存储结构中 简单地把装入的页放在未分配的物理页面即可 3 淘汰策略 采用局部FIFO置换算法 即在本进程范围内进行局部置换 利用FIFO算法把驻留时间最长的页面淘汰出去 4 工作集策略Windows2000 XP根据内存负荷和进程缺页情况自动调整工作集 1 进程创建时 指定一个最小工作集 可用SetProcessWorkingSetSize函数指定 2 当内存负荷不太大时 允许进程拥有尽可能多的页面 3 系统通过自动调整 保证内存中有一定的空闲页面存在 每个进程都以同样的默认的工作集的最大值和最小值开始 这些数值列在表4 8中 表4 8默认的工作集的最大值和最小值 4 页面状态Windows2000 XP的页面有6种状态 有效状态 某进程正在使用该页面 清零状态 空闲且已被清零 空闲状态 空闲但尚未被清零 备用状态 已标记为无效 但可快速回到有效状态 修改状态 已标记为无效 但对该页面内容的修改尚未写入外存 可快速回到有效状态 坏页状态 该页面产生硬件错 不能再用 链接举例这里以WindowsNT 2000 XP中的动态链接库为例来进一步对链接加以说明 1 构造动态链接库动态链接库 DLL 是包含函数和数据的模块 它的调用模块可为EXE或DLL 它由调用模块在运行时加载 加载时它被映射到调用进程的地址空间 在VisualC 中有一类工程用于创建DLL 说明如下 1 库程序文件 C相当于给出一组函数定义的源代码 2 模块定义文件 DEF相当于定义链接选项 也可在源代码中定义 如DLL中函数的引入和引出 源文件中的链接选项如下 Exampleofthedllimportanddllexportclassattributes declspec dllimport inti declspec dllexport voidfunc 或void declspec dllexport cdeclFunction1 void 3 编译程序利用 C文件生成目标模块 OBJ 4 库管理程序利用 DEF文件生成DLL输入库 LIB和输出文件 EXP 5 链接程序利用 OBJ和 EXP文件生成动态链接库 DLL 6 动态链接库映射到调用方进程的地址空间中 2 构造动态链接库的装入方法 1 装入时动态链接 load time 在编程时显式调用某个DLL函数 该DLL函数在可执行文件中称为导入 import 函数 链接时需利用 LIB文件 在可执行文件中为引入的每个DLL建立一个IMAGE IMPORT DESCRIPTOR结构 而在装入时由系统根据该DLL映射在进程中的地址改写ImportAddressTable中的各项函数指针 Hint是DLL函数在DLL文件中的序号 当DLL文件修改后 就未必指向原先的DLL函数了 在装入时 系统会查找相应的DLL 并把它映射到进程地址空间 获得DLL中各函数的入口地址 定位本进程中对这些函数的引用 如图4 5所示 图4 5装入时动态链接的过程 2 运行时动态链接 run time 在编程时通过LoadLibrary 给出DLL名称 返回装入和链接之后该DLL的句柄 FreeLibrary GetProcAddress 其参数包括函数的符号名称 返回该函数的入口指针 等API来使用DLL函数 这时不再需要引入库 importlibrary LoadLibrary或LoadLibraryEx把可执行模块映射到调用进程的地址空间并返回模块句柄 GetProcAddress获得DLL中特定函数的指针并返回 FreeLibrary把DLL模块的引用计数减1 当引用计数为0时 拆除DLL模块到