最新网站建设的软件,塘下建设银行网站,矿产网站开发,安装下载应用文章目录 0.前言9.1 背景9.2 按需调页9.2.1 基本概念9.2.2 按需调页的性能 9.3 写时复制9.4 页面置换9.4.1 基本页置换9.4.2 FIFO页置换9.4.3 最优(Optimal)置换9.4.4 LRU#xff08;Least Recently Used#xff09;页置换9.4.5 近似LRU页置换9.4.6 页缓冲算法 9.5 帧分配9.5… 文章目录 0.前言9.1 背景9.2 按需调页9.2.1 基本概念9.2.2 按需调页的性能 9.3 写时复制9.4 页面置换9.4.1 基本页置换9.4.2 FIFO页置换9.4.3 最优(Optimal)置换9.4.4 LRULeast Recently Used页置换9.4.5 近似LRU页置换9.4.6 页缓冲算法 9.5 帧分配9.5.1 帧的最少数量9.5.2 分配算法9.5.3 全局分配和局部分配 9.6 系统颠簸9.6.1 系统颠簸的原因 9.7 内存映射文件9.8 内核内存的分配9.8.1 buddy 系统9.8.2 slab分配 0.前言
第8章讨论了计算机系统的各种内存管理策略。所有这些策略都有相同的目标同时将多个进程保存在内存中以便允许多道程序。 然而这些策略都倾向于要求每个进程再执行之前应完全处于内存中。 虚拟内存技术允许执行进程不必完全处于内存。这种方案的一个主要优点是程序可以大于物理内存。此外虚拟内存将内存抽象成一个巨大的、统一的存储数组进而实现了用户看到的逻辑内存与物理内存的分离。这种技术使得程序员不在担忧内存容量的限制。虚拟内存还允许进程轻松共享文件和实现共享内存。此外他为创建进程提供了有效的机制。然而虚拟内存的实现并不容易并且使用不当还可能会大大降低性能。本章以请求调页为例来讨论虚拟内存并讨论其复杂性与开销。 本章目标 讨论虚拟内存系统的优点解释请求调页、页置换算法和页帧分配等概念讨论工作集模型原理讨论共享内存和内存映射文件之间的关系讨论如何管理内核内存 9.1 背景
第八章所介绍的内存管理算法都是基于一个基本要求执行指令必须在物理内存中满足这一要求的第一种方法是整个进程放在内存中。动态载入能帮助减轻这一限制但是它需要程序员特别小心地做一些额外的工作。
指令必须都在物理内存内的这一限制似乎是必须和合理的但也是不幸的因为这使得程序的大小被限制在物理内存的大小内。事实上研究实际程序会发现许多情况下并不需要将整个程序放到内存中。即使在需要完整程序的时候也并不是同时需要所有的程序。
因此运行一个部分在内存中的程序不仅有利于系统还有利于用户。
虚拟内存virtual memory将用户逻辑内存和物理内存分开。这在现有物理内存有限的情况下为程序员提供了巨大的虚拟内存。 进程的虚拟地址空间就是进程如何在内存中存放的逻辑或虚拟视图。通常该视图为进程从某一个逻辑地址如地址0开始连续存放。 根据第八章物理地址可以按页幁来组织且分配给进程的物理页帧也可能不是连续的。这就需要内存管理单元MMU将逻辑页映射到内存的物理页帧。 如上图显示运行随着动态内存的分配堆可向上生长。类似地还允许随着子程序的不断调用栈可以向下生长。堆与栈之间的巨大空白空间(或hole)为虚拟地址的一部分只有在堆与栈生长的时候才需要实际的物理页。包括空白的虚拟地址空间成为稀地址空间采用稀地址空间的优点是随着程序的执行栈或者堆段的生长或需要载入动态链接库或共享对象时这些空白可以填充。
除了将逻辑内存与物理内存分开虚拟内存也允许文件和内存通过共享页而为两个或者多个进程所共享这样带来了如下的有点 通过将共享对象映射到虚拟地址空间系统库可为多个进程所共享。虽然每个进程都认为共享库是其虚拟地址空间的一部分而共享库所用的物理内存的实际页是为所有进程所共享。通常库是按制度方式来链接每个进程的空间的。 类似的虚拟内存允许进程共享内存。两个或者多个进程之间可以通过使用共享内存来相互通信。虚拟内存允许一个进程创建内存区域以便与其他进程进行共享。共享该内存区域的进程认为它是其虚拟地址空间的一部分而事实上这部分是共享的。 虚拟内存可允许在用系统调用fork()创建进程期间共享页从而加快进程的创建。 9.2 按需调页
一个执行程序从磁盘载入内存的时候有两种方法:
选择在程序执行时将整个程序载入到内存中。不过这种方法的问题是可能开始并不需要整个程序在内存中。如有的程序开始时带有一组用户可选的选项。载入整个程序也就将所有选项的执行代码都载入到内存中而不管这些选项是否使用。另一种选择是在需要时才调入相应的页。这种技术称为按需调页(demand paging)常为虚拟内存系统所采用。
按需调页系统看类似于使用交换的分页系统进程驻留在第二级存储器上通常为磁盘。当需要执行进程时将它换入内存。不过不是讲整个进程换入内存而是使用懒惰交换(lazy swapper)。懒惰交换只有在需要页时才将它调入内存。由于将进程看做是一系列的页而不是一个大的连续空间因此使用交换从技术上来讲并不正确。交换程序(swapper)对整个进程进行操作而调页程序(pager)只是对进程的单个页进行操作。因此 在讨论有关按需调页时需要使用调页程序而不是交换程序。
9.2.1 基本概念
当换入进程时调页程序推测在该进程再次换出之前使用到的哪些页仅仅把需要的页调入内存。从而减少交换时间和所需的物理内存空间。
这种方案需要硬件支持区分哪些页在内存哪些在磁盘。采用有效/无效位来表示。当页表中一个条目的该位为有效时表示该页合法且在内存中反之可能非法也可能合法但不在内存中。 如果进程从不试图访问标记为无效的页那么并没有什么影响因此如果推测正确且只调入所有真正需要的页那么进程就可如同所有页都调入内存一样正常运行。 当进程试图访问这些尚未调入内存的页时会引起页错误陷阱page-fault trap。这种情况的处理方式如下 检查进程的内部页表通常与PCB一起保存。以确定该引用是的合法还是非法的地址访问。如果非法则终止进程如果引用有效但是尚未调入页面则现在进行调入。找到一个空闲帧如从空闲帧表中选取一个。调度一个磁盘操作以便将所需页调入刚分配的帧磁盘读操作完成后修改进程的内部表和页表表示该页已在内存中。重新开始因陷阱而中断的指令。 如果没有空闲帧时该如何处理呢
页替换在内存中找到一些不再使用的页将它换出去。一些页可能被多次加载如内存。 程序具有局部引用这使得按需调页的性能较为合理。
支持按需调页的硬件与分页和交换的硬件一样 页表该表通过有效-无效位或保护位的特定值该条件设为无效 次级存储器该次级存储器用来保存不再内存中的页。次级存储器通常为快速磁盘。它通常成为交换设备用于交换的这部分磁盘称为交换空间
9.2.2 按需调页的性能
按需调页对计算机系统的性能有重要影响下面计算一下关于按需调页内存的有效访问时间effective access time。
设p(0≤p≤1)为页错误的概率ma为内存访问时间: 有效访问时间(1−p)×map×页错误时间
如果p→0则不存在页错误 如果p→1则每次访问都存在页错误即纯粹按需调页(pure demand paging)。 其中页错误时间有很多主要是下面三种
处理页错误中断读入页页换入时间重新启动进程 按需调页的例子
内存存取时间 200 ns 平均页错误服务时间 8 ms EAT(1−p)×200 nsp×8000000
如果每次1000次访问中有1次页错误则EAT8.2ns。即因按需调页而慢40倍如果需要性能降低不超过10%则需要p0.0000025
因此来看对于按需调页降低页错误率至关重要。
另外是对交换空间的处理的使用。磁盘IO到交换空间通常比到文件系统要快因为交换空间是按大块进行分配并不使用文件查找和间接分配方法。因此在进程开始时将整个文件镜像复制到交换空间并从空间交换执行按页调度那么有可能获得更好的性能。
另一种选择是开始时从文件系统进行按需调页但置换出来的页写入交换空间而后的调页则从交换空间中读取。这种方法确保只有需要的页才从文件系统中调入又可以保证一定的性能。
9.3 写时复制
写时复制Copy-on-Write (COW) 运行父进程与子进程开始时共享同一页面这些页面标记为写时复制页即如果任何一个进程需要对页进行写操作那就创建一个共享页的副本。
因为指标及那些能够被修改的页所以创建进程的过程更有效率。
写时复制所需的空闲也老子一个空闲缓冲池系统通常用按需填零(zero-fill-on-demand) 的技术分配这些页。按需填零在需要分配之前先填零因此清除了以前的内容。
下面的两个过程提箱了进程1修改C前后的物理内存的情况。 before
9.4 页面置换
操作系统为何要进行页面置换呢 这是由于操作系统给用户态的应用程序提供了一个虚拟的“大容量”内存空间而实际的物理内存空间又没有那么大。所以操作系统就就“瞒着”应用程序只把应用程序中“常用”的数据和代码放在物理内存中而不常用的数据和代码放在了硬盘这样的存储介质上。如果应用程序访问的是“常用”的数据和代码那么操作系统已经放置在内存中了不会出现什么问题。但当应用程序访问它认为应该在内存中的的数据或代码时如果这些数据或代码不在内存中则根据上文的介绍会产生缺页异常。这时操作系统必须能够应对这种缺页异常即尽快把应用程序当前需要的数据或代码放到内存中来然后重新执行应用程序产生异常的访存指令。如果在把硬盘中对应的数据或代码调入内存前操作系统发现物理内存已经没有空闲空间了这时操作系统必须把它认为“不常用”的页换出到磁盘上去以腾出内存空闲空间给应用程序所需的数据或代码。
操作系统迟早会碰到没有内存空闲空间而必须要置换出内存中某个“不常用”的页的情况。如何判断内存中哪些是“常用”的页哪些是“不常用”的页把“常用”的页保持在内存中在物理内存空闲空间不够的情况下把“不常用”的页置换到硬盘上就是页面置换算法着重考虑的问题。容易理解一个好的页面置换算法会导致缺页异常次数少也就意味着访问硬盘的次数也少从而使得应用程序执行的效率就高。
下面提供了一种需要页置换的情况。
9.4.1 基本页置换
基本页置换采用方法如下。
查找需要页在磁盘上的位置。 查找一空闲帧
如果有空闲帧那么就使用它如果没有空闲帧那么就是用页置换算法选择一个**“牺牲”帧**victim frame将牺牲帧的内容放到磁盘上改变页表和帧表。 将所需页读入新空闲帧改变页表和帧表。 重启用户进程。 如果没有帧空闲那么需要采用两个页传输一个换出一个换入。可以通过使用修改位或脏位以降低额外开销。每当页内的任何字或字节被写入时硬件就会设置该页的修改位以表示该页已被修改。这样的话磁盘上页的副本的内容没有必要重写。
页置换是按需调页的基础。为实现按需调页必须解决两个主要问题必须开发帧分配算法(frame-allocation algorithm)和页置换算法(page-replacement algorithm)。如果在内存中有多个进程那么必须决定为每个进程各分配多少帧。而且当需要页置换时必须选择要置换的帧。
可以这样来评估一个算法针对特定内存引用序列运行某个置换算法并计算出页错误的数量。内存的引用序列成为引用串(reference string)。
第一对给定页大小页大小通常由硬件或系统来决定只需要考虑页码而不需要完整的地址。第二如果有一个页p的引用那么任何紧跟着对页p的引用绝不会产生页错误。页p在第一次引用时已在内存中任何紧跟着的引用绝不会出错。
页错误和帧数量图
9.4.2 FIFO页置换
该算法总是淘汰最先进入内存的页即选择在内存中驻留时间最久的页予以淘汰。只需把一个应用程序在执行过程中已调入内存的页按先后次序链接成一个队列队列头指向内存中驻留时间最久的页队列尾指向最近被调入内存的页。这样需要淘汰页时从队列头很容易查找到需要淘汰的页。FIFO算法只是在应用程序按线性顺序访问地址空间时效果才好否则效率不高。因为那些常被访问的页往往在内存中也停留得最久结果它们因变“老”而不得不被置换出去。FIFO算法的另一个缺点是它有一种异常现象Belady现象即在增加放置页的页帧的情况下反而使缺页异常次数增多。
问题随机一访问串和驻留集的大小通过模拟程序显示淘汰的页号并统计命中率。示例
输入访问串7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1
驻留集大小3 红色表示指针指向调入内存的页面中“最老“的页面
通过模拟程序输出淘汰的页号分别为7 0 1 2 3 0 4 2 3
命中率为51.3
**注意**内存的页面中“最老“的页面会被新的网页直接覆盖而不是“最老“的页面先出队然后新的网页从队尾入队。
9.4.3 最优(Optimal)置换
由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面将是以后永不使用的或许是在最长的未来时间内不再被访问的页面。采用最佳置换算法通常可保证获得最低的缺页率。但由于操作系统其实无法预知一个应用程序在执行过程中访问到的若干页中哪一个页是未来最长时间内不再被访问的因而该算法是无法实际实现但可以此算法作为上限来评价其它的页面置换算法。
9.4.4 LRULeast Recently Used页置换
FIFO置换算法性能之所以较差是因为它所依据的条件是各个页调入内存的时间而页调入的先后顺序并不能反映页是否“常用”的使用情况。
最近最久未使用LRU置换算法是根据页调入内存后的使用情况进行决策页是否“常用”。由于无法预测各页面将来的使用情况只能利用“最近的过去”作为“最近的将来”的近似因此LRU置换算法是选择最近最久未使用的页予以淘汰。该算法赋予每个页一个访问字段用来记录一个页面自上次被访问以来所经历的时间t,当须淘汰一个页面时选择现有页面中其t值最大的即最近最久未使用的页面予以淘汰。
问题随机一访问串和驻留集的大小通过模拟程序显示淘汰的页号并统计命中率。示例
输入访问串7 0 1 2 0 3 0 4 2 3 0 3 2
驻留集大小3
算法的实现由于LRU算法淘汰的是上次使用距离t时刻最远的页故需记录这个距离。 有两种方法 计数器为每个页表项关联一个使用时间域并为CPU增加一个逻辑时钟或计数器。对每次内存引用计数器都会增加。每次内存引用时时钟寄存器的内容会复制到相应页所对应页表项的使用时间域内。置换具有最小时间的页这种方案需要搜索页表以查找LRU页且每次内存访问都要写入内存。在页表改变时也必须要保证时间必须考虑时钟溢出。堆栈实现LRU置换的另一个方法是采用页码堆栈。每当引用一个页该页就从堆栈中删除并放在顶部这样堆栈底部总是LRU页该堆栈可实现为具有头指针和尾指针的双向链表 每次内存引用都必须更新时钟域或堆栈如果每次引用都采用中断以允许软件更新这些数据结构那么它会使内存引用慢至少10倍 红色表示每个页帧对应的计数器值
通过模拟程序输出淘汰的页号分别为7 1 2 3 0 4
命中率为413
LRU的另一种通俗理解
例如一个三道程序等待进入的是123442563421。先分别把123导入然后导入4置换的是1因为他离导入时间最远。然后又是4不需要置换然后是2也不需要因为内存中有到5的时候因为3最远所以置换3依次类推。
注意虽然两个算法都是用队列这种数据结构实现的但具体操作不完全遵从队列的原则。这一点不必纠结。
命中率是指在队满的情况下新的元素的加入不影响队列其它元素。即该元素已存在在队列中。
OPT、LRU以及FIFO算法的对比图如下所示
9.4.5 近似LRU页置换
很少有计算机系统能够提供足够的硬件来支持真正的LRU页置换。有的系统不提供任何支持因此必须使用其他置换算法。然而许多系统都通过应用为方式提供一定支持页表内的每项都关联着一个引用位(reference bit)每当引用一个页时相应页表的引用位就会被引脚置位。如添加一个8bit的引用位极端情况下只有一个引用位即二次机会算法。每个时钟都向右移位引用的话高位置1否则置0。
开始操作系统会将所有引用位都清零。随着用户进程的执行与引用页相关联的引用位被硬件置位。通过检查引用位能确定那些用过而那些没用过。这种部分排序信息导致了许多近似LRU算法的页置换算法。 附加引用位算法 可以为位于内存中的每个表中的页保留一个8bit的字节。操作系统把每个页的引用位转移到其8bit字节的高位而将其他位右移并抛弃最低位。如果将8bit字节作为无符号整数那么具有最小值的页为LRU页且可以被置换。二次机会算法 二次机会置换的基本算法是FIFO置换算法。当要选择一个页时检查其引用位。如果其值为0那么就直接置换该页。如果引用位为1那么就给该页第二次机会并选择下一个FIFO页。当一个页获得第二次机会时其引用位清零。且其到达时间设为当前时间。因此获得第二次机会的页在所有其他页置换之前是不会被置换的。另外如果一个页经常使用以致于其引用位总是得到设置那么它就不会被置换。 一种实现二次机会算法的方法是采用循环队列。用一个指针表示下次要置换哪个页。当需要一个帧时指针向前移动直到找到一个引用位为0的页。在向前移动时它将清除引用位。增强型二次机会算法 通过将引用位和修改位作为一个有序对来考虑能增强二次机会算法。有下面四种可能类型 1. (0,0)最近没有使用且也没有修改。—用于置换的最佳页 2. (0,1)最近没有使用但修改过。—不是很好因为在置换之前需要将页写出到磁盘 3. (1,0)最近使用过但没有修改—它有可能很快又要被使用 4. (1,1)最近使用过且修改过—它有可能很快又要被使用且置换之前需要将页写出到磁盘 当页需要置换时每个页都属于这四种类型之一。置换在最低非空类型中所碰到的页可能要多次搜索整个循环队列。
9.4.6 页缓冲算法
系统通常保留一个空闲帧缓冲池。当出现页错误时会像以前一样选择一个牺牲帧在牺牲帧写出之前所需要的页就从缓冲池中读到空闲内存。
9.5 帧分配
9.5.1 帧的最少数量
如何在各个进程之间分配一定的空闲内存 简单办法是将帧挂在空闲帧链表上当发生页错误之时即进行分配。进程终止时帧再次放回空闲帧链表。 帧分配策略受到多方面限制。例如 分配数不能超过可用帧数也必须分配至少最少数量。保证最少量的原因之一是性能。页错误增加会减慢进程的执行。并且在指令完成前出现页错误该指令必须重新执行。所以有足够的帧至关重要。 每个进程帧的最少数量由体系结构决定而最大数量是由可用物理内存数量决定。
9.5.2 分配算法
1平均分配每个进程一样多 2按进程大小使用比例分 3按进程优先级分 4大小和优先级组合分
9.5.3 全局分配和局部分配
全局置换允许进程从所有帧集合中选择一个进行置换而不管该帧是否已分配给其他进程即它可以从其他进程抢夺帧比如高优先级抢夺低优先级的帧局部分配则要求每个进程只能从自己的分配帧中分配。
局部置换要求每个进程仅从其自己的分配帧中进行选择 全局置换通常有更好的吞吐量且更为常用。一个问题是不能控制页错误率。因为局部置换不能使用其他进程的不常用的内存。
9.6 系统颠簸
如果一个进程在换页上用的时间多于执行时间那么这个进程就在颠簸thrashing颠簸其实就是频繁的页调度行为。
9.6.1 系统颠簸的原因
如果一个进程没有分配到足够的页那么就会导致页置换不断的发生这将导致
低CPU利用率 低CPU利用率导致系统认为需要引入新进程增加多道程序的程度。 进程分配到的帧会更少 …死循环
9.7 内存映射文件
文件的内存映射memory-mapping 允许一部分虚拟内存与文件逻辑相关联。这样的结果是能够通过虚拟内存技术来将文件IO作为普通内存来访问。利用虚拟内存技术将文件I/O作为普通内存访问的方法叫做文件的内存映射。
开始的文件访问按普通请求页面调度来进行会产生页错误。这样一页大小的部分文件从文件系统读入物理页以后文件的读写就按照通常的内存访问来处理
对于映射到内存的文件进行读写操作可能不会及时的更新到磁盘的文件当中。更新文件的操作通常由两种方式 一、通过定期检查内存映射页是否改变来判断是否应该写磁盘 二、在关闭文件的时候将内存映射页写回磁盘并从进程的虚拟内存中删除。
9.8 内核内存的分配
当用户态进程需要额外内存时可以从内核所维护的空闲页帧链表中获取页。但是内核内存的分配通常是从空闲内存池中获取的。
内核内存的分配与普通用户从进程空闲链表中获取不同
内核分配内存时有时需要的空间不到一页。因此需要谨慎的分配内存减少浪费。
有些硬件需要直接和物理内存交互因此需要分配连续的物理页9.8.1 buddy 系统
buddy系统是从物理上连续的大小固定的段上进行分配。每次分配的内存按2的幂次进行分配2KB、4KB…如果请求不为2的幂那么就按下一个2的幂次来分配如果请求11KB则分配16KB。 其分配是从最大的段开始尝试分配 如果满足要求那么段平均分为两部分取其中一半继续开始尝试分配 如果不满足要求那么就取上一次满足尝试分配的大小分配。 优点可通过合并快速的形成更大的段 缺点容易产生碎片如33KB的需求需要64KB才能满足 9.8.2 slab分配
slab提出的原因由于操作系统在运行中会不断产生、使用、释放大量重复的对象所以对这样的重复对象的生成进行改进可以大大提高效率。 简单解释
slab是Linux操作系统的一种内存分配机制。其工作是针对一些经常分配并释放的对象如进程描述符等。
这些对象的大小一般比较小如果直接采用buddy系统来进行分配和释放不仅会造成大量的内存碎片而且处理速度也太慢。
slab分配器是基于对象进行管理的相同类型的对象归为一类(如进程描述符就是一类)。
每当要申请这样一个对象slab分配器就从一个slab列表中分配一个这样大小的单元出去。
当要释放时将其重新保存在该列表中而不是直接返回给buddy系统从而避免这些内碎片。 slab分配器并不丢弃已分配的对象而是释放并把它们保存在内存中。当以后又要请求新的对象时就可以从内存直接获取而不用重复初始化。
具体实现 slab由一个或多个物理上的页组成 高速缓存cache含有一个或多个slab 每个内核数据结构含有一个cache如进程描述符文件对象信号量等。 每个cache含有内核数据结构的对象实例 当cache被创建时将所有的对象标记为空闲free 当需要内核数据结构的对象时可以从cache上直接获取并将该对象标记为使用used slab有三种状态 满的 slab中所有对象被标记为使用 空的 slab中所有对象被标记为空闲 部分 slab中部分对象被标记为使用 分配过程 slab分配器首先从部分空闲的slab进行分配 如没有部分空闲的slab则从空的slab进行分配 如没有空的slab则从物理连续页上分配新的slab并将该slab赋给一个cache再重复上述过程。 优点 没有因碎片引起的内存浪费 内存请求可以快速满足 预调页 按需调页的一个显著特性是当一个进程开始的时候会出现大量页错误这是由于试图将最初局部调入到内存的结果。
预调页的目的是阻止这种大量的初始调页其策略为同时将所需要的所有页一起调入内存中。
