虚拟内存虚拟内存

虚拟内存计算机系统使用的各种内存管理策略。所有这些策略都为同一目的：同时将多个进程存放在内存中，以便多道程序设计。不过，这些策略都需要在进程执行之前将整个进程放在内存中。
虚拟内存技术允许执行进程不必完全在内存中。这种方案的一个显著优点是程序可以比物理内存大。而且，虚拟内存将内存抽象成一个巨大，统一的存储数组，进而将用户看到的逻辑内存与物理内存分开。这种技术允许程序员不受内存的限制。虚拟内存也允许进程很容易地共享文件和地址空间。还为创建进程提供了有效的机制。但是，虚拟内存的实现并不容易，如果使用不当可能会大大的降低性能。
背景
上一节介绍的内存管理算法都基于一个基本要求：执行指令必须在物理内存中。满足这一要求的第一种方法是将整个进程放在内存中。动态载入能帮助减轻这一限制，但是它需要程序员特别小心并且需要一些额外的工作。
指令必须都在物理内存的这一限制，这似乎是必须和合理的，但也是不幸的，因为这使得程序的大小被限制在物理内存的大小以内。事实上，研究实际程序会发现，在许多情况下并不需要将整个程序放在内存中。
能够执行只有部分在内存中的程序可带来很多好处：
程序不再受现有的物理内存空间限制。用户可以为一个巨大的虚拟地址空间(virtual address space)写程序，简化工作量。
因为每个用户程序使用了更少的物理内存，所以更多的程序可以同时执行，CPU使用率也相应增加，而响应时间或周转时间并不增加。
由于载入或交换每个用户程序到内存内所需的I/O会更少，用户程序会运行得更快。
虚拟内存（virtual memory）将用户逻辑内存与物理内存分开。

文章图片

进程的虚拟地址空间就是进程如何在内存中存放的逻辑（或虚拟）视图。通常，该视图为进程从某一逻辑地址（如地址0）开始，连续存放。物理地址可以按页帧来组织，且分配给进程的物理页帧也可能不是连续的。这就需要内存管理单元（MMU）将逻辑页映射到物理页帧。
如下图所示，允许随着动态内存分配，堆可向上生长。类似地，还允许随着子程序的不断调用，栈可以向下生长。堆与栈之间的巨大空白空间（或洞）为虚拟地址的一部分，只有在堆与栈生长时，才需要实际的物理页。包括空白的虚拟地址空间称为稀地址空间。采用稀地址空间的优点是：随着程序的执行，堆或栈的生长或需要载入动态链接库或（共享对象）时，这些空白可以填充。

文章图片

除了将逻辑内存与物理内存分开，虚拟内存也允许文件和内存通过共享页而为两个或多个进程所共享。

文章图片

通过将共享对象映射到虚拟地址空间，系统库可为多个进程所共享。虽然每个进程都认为共享库是其虚拟地址空间的一部分，而共享所用的物理内存的实际页是为所有进程所共享。通常库是按只读方式来链接每个进程的空间。
类似的，虚拟内存允许进程共享内存。两个或多个进程之间可以通过使用共享内存来通信。虚拟内存允许一个进程创建内存区域，以便与其他进程共享。共享内存区域的进程认为它是其虚拟地址空间的一部分，而事实上这部分是共享的。
虚拟内存可允许在用系统调用fork()创建进程期间共享页，从而加快进程创建。
按需调页
看看一个执行程序是如何从磁盘载入内存的。一种选择是在程序执行时，将整个程序载入到内存。不过，这种方法的问题是可能开始并不需要整个程序在内存。如有的程序开始时带有一组用户的可选的选项。载入整个程序，也就将所有选项的执行代码都载入到内存中，而不管这些选项是否使用。另一种选择是在需要时才调入相应的页。这种技术称为按需调页（demand paging）, 常为虚拟内存系统所采用。对于按需调页虚拟内存，只有程序执行需要时才载入页，那些从未访问的页不会调入到物理内存。
按需调页系统类似于使用交换的分页系统，进程驻留在第二级存储器上（通常为磁盘）。当需要执行进程时，将它换入内存。不过，不是将整个进程换入内存，而是使用懒惰交换（lazy swapper）。懒惰较厚安只有在需要页时，才将它调入内存。由于将进程看做是一系列的页，而不是一个大的连续空间，因此使用交换从技术上来讲并不正确。交换程序（swapper）对整个进程操作，而调页程序（paper）只是对进程的单个页进行操作。因此，在讨论有关按需调页，需要使用调页程序而不是交换程序。

文章图片

基本概念当换入进程时，调页程序推测在该进程再次换出之前会用到哪些页。调页程序不是调入整个进程，而是把那些必须的页调入内存。这样，调页程序就避免了读入那些不使用的页，也减少了交换时间和所需的物理内存空间。
对于这种方案，需要一定形式的硬件支持来区分那些页在内存中，哪些页在磁盘上。可以通过有效-无效位来设置。当该位设置为"有效"时，该值表示相关的页即合法也在内存中。当该位设置为"无效"时，该值表示相关的页为无效（也就是，不在进程的逻辑地址空间内），或者有效但是在磁盘上。对于调入内存的页，其也表条目的设置与平常一样；但是对于不在内存的页，其页表条目设置为无效，或包含该页在磁盘上的地址。
如果进程从不试图访问标记为无效的页，那么并没有什么影响。因此，如果推测正确并且只调入所有真正需要的页，那么进程就如同所有页都已调入一样正常运行。当进程执行和访问那些驻留在内存中的页时，执行会正常进行。

文章图片

但是当进程试图访问那些尚未调入到内存的页时，对标记为无效的访问会产生页错误陷阱（page-fault trap）。分页硬件，在通过页表转换地址时，将发现已设置了无效位，会陷入操作系统。这种陷阱时由于操作系统未能将所需的页调入内存引起的。
处理这种页错误的程序比较简单：

文章图片

检查进程的内部页表（通常与PCB一起保存），以确定该引用时合法还是非法的地址访问。
如果引用非法，那么终止进程。如果引用有效但是尚未调入页面，那么现在应调入。
找到一个空闲帧（例如，从空闲帧链表中选取一个）。
调度一个磁盘操作，以便将所需要的页调入刚分配的帧。
当磁盘读操作完成后，修改进程的内部表和页表，以表示该页已在内存中。
重新开始因陷阱而中断的指令。进程现在能访问所需的页，就好像它似乎总在内存中。

存粹按需调页：所有的页都不在内存中，就开始执行。
支持按需调页的硬件与分页和交换的硬件一样：
页表：该表能够通过有效-无效位或保护位的特定值，将条目设为无效。
次级存储器：该次级存储器用来保存不在内存中的页。次级存储其通常位快速磁盘。它通常称为交换设备，用于交换的这部分磁盘称为交换空间（swap space）。
请求调页的关键要求是能够在页错误后重新执行指令。在出现页错误时，保存中断进程的状态（寄存器，条件代码，指令计数器），必须能够按完全相同的位置和地址重新开始执行进，只不过现在所需的页已在内存中且可以访问。对绝大多数情况来说，这种要求容易满足。也错误可能出现在任何内存引用中。如果也错误出现在指令获取时，那么可以再次获取指令。如果页错误出现获取操作数时，那么可以再次获取指令、再次译码指令，然后再次获取操作数。
按需调页的性能按需调页对计算机系统的性能有重要影响。为了说明起见，下面计算一下关于按需调页内存的有效访问时间（effective access time）。只要没有出现页错误，那么有效访问时间等于内存访问时间（用ma表示）。然而，如果出现页错误，那么就必须从磁盘中读入相关页，再访问所需要的字。
设p为页错误的概率(0有效访问时间为：
有效访问时间=(1-p)*ma+p*页错误时间
为了计算有效时间，必须知道处理页错误需要多少时间。页错误会引起如下序列的动作产生：

陷入操作系统。
保存用户寄存器和进程状态。
确定中断是否为页错误。
检查页引用是否合法并确定页所在磁盘的位置。
从磁盘读入页到空闲帧中。
在该磁盘队列中等待，直到处理完请求。
等待磁盘的寻道和/或延迟时间。
开始将磁盘的页传到空闲帧。
在等待时，将CPU分配给其他用户（CPU调度，可选）。
从I/O子系统接收到中断（以示I/O完成）。
保存其他用户的寄存器和进程状态。
确定中断是否来自磁盘。
修正页表和其他表以表示所需页现已在内存中。
等待CPU再次分配给本进程。
恢复用户寄存器、进程状态和新页表，再重新执行中断的指令。

主要经历了两次上下文切换，以及磁盘的读取等待。
写时复制
通过采用类似页面共享的技术，采用系统调用fork创建进程的开始阶段可能需要按需调页。这种技术提供了快速进程创建，且最小化新创建进程必须分配的新页面的数量。
系统调用fork()是将子进程创建为父进程的复制品。传统上，fork()为子进程创建一个父进程地址空间的副本，复制属于父进程的页。然而，由于许多子进程在创建之后通常马上会执行系统调用exec(),所以父进程地址空间的复制可能没有必要。因此，可以使用一种称为写时复制（copy-on -write）的技术。这种技术允许父进程与子进程开始时共享同一页面。这些页面标记为写时复制页，即如果任何一个进程需要对页进行写操作，那么就创建一个共享页的副本。

文章图片

文章图片

例如，假设子进程试图修改含有部分栈的页，且操作系统能识别该页被设置为写时复制页，那么操作系统就会创建一个该页的副本，并将它映射到子进程的地址空间内。这样，子进程会修改其复制的页，而不是父进程的页。采用写时复制技术，很显然只有能被进程修改的页才会被复制；所有非修改页可为父进程和子进程所共享。
当确定一个页采用写时复制时，从哪些分配空闲页是很重要的。许多操作系统为这类请求提供空闲缓冲池（pool）。这些空闲页在进程栈或堆必须扩展时可用于分配。或用于管理写时复制页。操作系统通常采用按需填零(zero-fill-on-demand)的技术以分配这些页。按需填零页在需要分配之前先填零，因此清除了以前的内容。
页面置换

文章图片

基本页置换页置换采用如下方法。如果没有空闲帧，那么就查找当前没有使用的帧，并将其释放。可采用这样的方式来释放一个帧：将其内容写到交换空间，并改变页表（和所有其他表）以表示该页不在内存中。现在可使用空闲帧来保存进程出错的页。修改页错误处理程序以包括页置换：

文章图片

查找所需要页在磁盘上的位置。
查找一个空闲帧
如果有空闲帧，那么就使用它。
如果没有空闲帧，那么就是用页置换算法以选择一个 "牺牲"帧（victim frame）。
将"牺牲"帧的内容写到磁盘上，改变页表和帧表。
1. 将所需页读入（新）空闲帧，改变页表和帧表。
2. 重启用户进程。

注意，如果没有空闲帧，那么需要采用两个页传输（一个换出，一个换入）。这种情况实际上把也错误处理时间加倍了，且也相应地增加了有效访问时间。
可以通过使用修改位（modify bit）或脏位（dirty bit）以降低额外开销。每页或帧可以有一个修改位，通过硬件与之相关联。每当页内的任何字或字节被写入时，硬件就会设置该页的修改位以表示页已修改。如果修改位已设置，那么就可以知道自从磁盘读入后该页已发生了修改。在这种情况下，如果该页被选择位替换页，就必须要把该页写到磁盘上去。然而，如果修改位没有设置，那么也就知道自从磁盘读入都该页并没有发生修改。因此，磁盘上页的副本的内容没有必要重写，因此就避免了将内存页写回磁盘上：它已经在那里了。
为了实现按需调页，必须解决两个主要问题：必须开发帧分配算法（frame-allocation algorithm）和页置换算法（page-replacement algorithm）。
可以采用这样来评估一个算法：针对特定内存引用序列，运行某个置换算法，并计算出页错误的数量。内存的引用序列称为引用串（reference string）。为了降低数量量，可利用以下两个事实。
第一：对给定页大小（页大小通常由硬件或系统来决定），只需要考虑页码，而不需要完整地址。
第二：如果有一个对页p的引用，那么任何紧跟着对页p的引用决不会产生页错误。页p第一次引用时已在内存中，任何紧跟着的引用不会出错。

文章图片

针对某一特定引用串和页置换算法，为了确定页错误的数量，还需知道可用帧的数量。显然，随着可用帧数量的增加，页错误的数量会相应地减少。

文章图片

为了讨论页置换算法，将采用如下引用串：
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
而可用帧的数量位3.

FIFO页置换最简单的页置换算法时FIFO算法。FIFO页置换算法为每个页记录着该页调入内存的时间。当必须置换一页时，将选择最旧的页。注意并不需要记录调入一页的确切时间。可以创建一个FIFO队列来管理内存中的所有页。队列中的首页将被置换。当需要调入页时，将它加到队列的尾部。

文章图片

FIFO页置换算法性能并不总是很好。
为了说明与FIFO页置换算法相关可能问题，考虑如下引用串：

文章图片

页错误对现有帧数的曲线，这种最为令人难以置信的结果称为Belady异常（Belady's anomaly）:对有的页置换算法，页错误率可能会随着所分配的帧数的增加而增加，而原期望为进程增加内存会改善其性能。在早期研究中，研究人员注意到这种推测并不总是正确的。因此，发现了Belady异常。

文章图片

最优置换 Belady异常发现的结果之一是对最优页置换算法（optimal page-replacement algorithm）的搜索。最优置换算法是所有算法中产生错误率最低的，且绝没有Belady异常的问题。这种算法确实存在，它被称为OPT或MIN。它会置换将来最长时间不会使用的页。使用这种页置换算法确保对于给定数量的帧会产生最低可能的页错误率。

文章图片

最优置换算法难以实现，因为需要引用串的未来知识。因此，最优算法主要用于比较研究。如果知道一个算法不是最优的，但是与最优相比最坏不差于12.3%,平均不差于4.7%,那么也是很有用的。
LRU页置换 FIFO和OPT算法的关键区别在于，FIFO算法使用的是页调入内存的时间，OPT算法使用的是页将来使用的时间。如果使用离过去最近作为不远将来的近似，那么可置换最长没有使用的页，这种方法称为最近最少使用算法（least-recently-used(LRU) algorithm）

文章图片

LRU策略经常用做页置换算法，且被认为相当不错。其主要问题是如何实现LRU置换。LRU页置换算法可能需要一定的硬件支持。它的问题是为页帧确定一个排序序列，这个序列按页帧上次使用的时间来定。有两种可行实现。
计数器：最为简单的情况是，为每个页表关联一个使用时间域，并为CPU增加一个逻辑时钟或计数器。对每次内存引用，计数器都会增加。每次内存引用时，始终寄存器的内容会被复制到相应页所对应页表项的使用时间域内。用这种方式就得到每页的最近引用时间。置换具有最小时间的页。这种方案需要搜索页表以查找LRU页，且每次内存访问都要写入内存（到页表的使用时间域）。在页表改变时（因CPU调度）也必须保持时间。
栈：实现LRU置换的另一个方法时采用页码栈。每当引用一个页，该页就从栈中删除并放在顶部。这样，栈顶总是最近使用的页，栈底部总是LRU页。由于必须从栈中部删除项，所以该栈可实现为具有头指针和尾指针的双向链表。这样，删除一页并放在栈顶部在最坏情况下需要改变6个指针。虽然说更新有点费时，但是置换不需要搜索；尾指针指向栈底部，就是LRU页。

文章图片

【虚拟内存】最优置换和LRU置换都没有Belady异常。这两个都属于同一类算法，称为栈算法（stack algorithm）,都绝不可能有Belady异常。
近似LRU页置换页表内的每项都关联着一个引用位（reference bit）。每当引用一个页时（无论是对页的字节进行读或写），相应页表的引用位就被硬件置位。
开始，操作系统会将所有引用位清零。随着用户进程的执行，与引用页相关联的引用位被硬件置位（置为1）。之后，通过检查引用位，能够确定那些页使用过而那些页未使用过。虽然不知道使用顺序，但是知道那些页用过而那些页未用过。这些信息是许多近似LRU页置换算法的基础。
附加引用位算法：可以为位于内存内的每个表中的页保留一个8位的字节。在规定时间间隔内，时钟定时器产生中断并将控制转交给操作系统。操作系统把每个页的引用位转移到其8位字节的高位，而将其他位向右移一位，并抛弃最低位。这些8位移位寄存器包含着页在最近8个时间周期内的使用情况。如果将这8位字节作为无符号整数，那么具有最小值的页位LRU页，且可以被置换。注意这些数字并不唯一。可以置换所有具有最小值的页，或在这些页之间采用FIFO来选择置换。
在极端情况下，只有引用位本身。这种算法称为第二次机会页置换算法（second-chance page-replacement algorithm）。
二次机会算法
二次机会置换的基本算法是FIFO置换算法。当要选择一个页时，检查其引用位。如果其值为0，那么就直接置换该页。如果引用位为1，那么就给该页第二次机会，并选择下一个FIFO页。当一个页获得第二次机会时，其引用位清零，且其到达时间设为当前时间。获得第二次机会的页在所有其他页置换（或获得第二次机会）之前，是不会被置换的。另外，如果一个页经常使用以致其引用位总是被设置，那么它就不会被置换。
一种实现二次机会算法（有时称为时钟算法）的方法是采用循环队列。用一个指针表示下次要置换哪一页。当需要一个帧时，指针向前移动直到找到一个引用位位0的页。在向前移动时，它将清除引用位。一旦找到牺牲页，就置换该页，新页就插入到循环队列的该位置。

文章图片

注意：在最坏情况下，所有位均已设置，指针会遍历整个循环队列，以便给每个页第二次机会。它将清除所有引用位后再选择页来置换。这样，如果所有位均已设置，那么第二次机会置换就变成了FIFO置换。
增强二次机会算法：通过将引用位和修改位作为一有序对来考虑，可以改进二次机会算法。采用这两个位，有下面四种可能类型：
（0，0）最近没有使用且也没有修改-----用于置换的最佳页。
（0，1）最近没有使用但修改过——不是很好，因为在置换之前需要将页写出到磁盘
（1，0）最近使用过但没有修改——它有可能很快又要被使用
（1，1）最近使用过且修改过——它有可能很快又要被使用，且置换之前需要将页写出到磁盘。
每个页都属于这四种类型之一。当页需置换时，可使用时钟算法，不是检查所指页的引用位是否设置，而是检查所指页属于哪个类型。置换在低非空类中所碰到的页。注意在找到要置换页之前，可能要多次搜索整个循环队列。
这种方法与简单时钟算法的主要差别时这里给那些已经修改过的页以更高的级别，从而降低了所需I/O的数量。
基于计数的页置换还有许多其他算法可用于页置换。例如，可以为每个页保留一个用于记录其引用次数的计数器，并可形成如下两个方案。
最不经常使用页置换算法（least frequently used(LFU) page-replacement algorithm）要求置换计数最小的页。这种选择的理由是活动页应该有更大的引用次数。这种算法会产生如下问题：一个页在进程开始时使用很多，但以后就不再使用。由于其使用过很多，所以它有较大次数，所以即使不再使用仍然会在内存中。解决方法之一时定期地将次数寄存器右移一位，以形成指数衰减的平均使用次数。
最常使用页置换算法（most frequently used(MFU) page-replacement algorithm）是基于如下理论：具有最小次数的页可能刚刚调进来，且还没有使用。
页缓冲算法除了特定页置换算法外，还经常采用其他措施。例如，系统通常保留一个空闲帧缓冲池。当出现页错误时，会像以前一样选择一个牺牲帧。然而，在牺牲帧写出之前，所需要的页就从缓冲池中读到空闲内存。这种方法允许进程尽可能快地启动，而无须等待牺牲帧页地写出。当在牺牲帧以后写出时，它再加入到空闲帧池。
这种方法地扩展之一是维护一个已修改页地列表。每当调页设备空闲时，就选择一个修改页并写到磁盘上，接着重新设置其修改位。这种方法增加了当需要选择置换时干净页地概率而不必写出。
另一个修改是保留一个空闲帧池，但是要记住哪些页再哪些帧中。由于当帧写到磁盘上时其内容并没有修改，所以再该帧被重用之前如果需要使用原来页，那么原来页可直接从空闲帧池中取出来使用。这时并不需要I/O。当一个页错误发生时，先检查所需要页是否在空闲帧池中。如果不在，那么才必须选择一个空闲帧来读入所需页。
帧分配
如何在各个进程之间分配一定地空闲内存？如果有93个空闲帧和2个进程，那么每个进程各得到多少帧？
帧的最少数量分配至少最少数量地帧地原因之一时性能。显然，随着分配给每个进程地帧数量地减少，页错误会增加，从而减慢进程的执行。另外，记住：当在指令完成之前出现页错误时，该指令必须重新执行。因此，必须有足够的帧来容纳所有单个指令所引用的页。
分配算法在n个进程之间分配m个帧的最为容易的方法是给每个一个平均值，即m/n帧。例如，如果有93个帧和5个进程，那么每个进程可得到18个帧，剩余3个帧可以放在空闲帧缓存池中。这种方案称为平均分配（equal allocation）。
也可以使用比例分配（proportional allocation）。根据进程大小，而将可用内存分配给每个进程。设进程Pi的虚拟内存大小位Si，且定义

文章图片

这样，如果可用帧的总数为m，那么进程pi可分配到ai个帧，这里ai近似为：

文章图片

全局分配与局部分配为各个进程分配帧的另一个重要因素是页置换。当多有个进程竞争帧时，可将页置换算法分为两个大类：全局置换（global replacement）和局部置换（local replacement）。全局置换允许一个进程从所有帧集合中选择一个置换帧，而不管该帧是否已分配给其他进程，即一个进程可以从另一个进程中拿到帧。局部置换要求每个进程仅从其自己的分配帧中进行选择。全局置换允许高优先级进程从低优先级进程中选择帧以便置换。一个进程可以从自己的帧中或任何低优先级进程中选择置换帧。这种方法允许高优先级进程增加其帧分配而以损失低优先级进程为代价。因为局部置换不能使用其他进程的不常用的内存，所以阻碍一个进程。因此，全局置换通常会有更好的系统吞吐量，且更为常用。
系统颠簸
如果低优先级进程所分配的帧数量少于计算机体系结构所要求的最少数量，那么必须暂停进程执行。接着应换出其他所有剩余页，以便使其所有分配的帧空闲。这引入了中程CPU调度的换进换出层。
没有"足够"帧的进程。如果进程没有它所需要的活跃使用的帧，那么它会很快产生页错误。这时，必须置换某个页。然而，其所有页都在使用，它置换一个页，但又立刻再次需要这个页。因此，它会一而再地产生页错误，置换一个页，而该页又立刻出错且需要立即调进来。
这种频繁地页调度行为称为颠簸（thrashing）。如果一个进程在换页上用的时间要多余执行时间，那么这个进程就在颠簸。
系统颠簸的原因在早期调页系统中，操作系统在监视CPU的使用率，如果CPU使用率太低，那么向系统中引入新进程，以增加多道程序的程序。采用全局置换算法，它会置换页而不管这些页是属于哪个进程的。现在假设一个进程进入一个新执行阶段，需要更多的帧。它开始出现页错误，并从其他进程中拿到帧。然而，这些进程也需要这些页，所以它们也会出现页错误，从而从其他进程中拿到帧。这些页错误进程必须使用调页设备以换进和换出页。随着它们排队等待换页设备，就绪队列会变空，而进程等待调页设备，CPU使用率就会降低。CPU调度程序发现CPU使用率降低，因此会增加多道程序的程序。新进程试图从其他运行进程中拿到帧，从而引起更多页错误，形成更长的调页设备的队列。

文章图片

通过局部置换算法（local replacement algorithm）(或优先置换算法（priority replacement algorithm）)能限制系统颠簸。采用局部置换，如果一个进程开始颠簸，那么它不能从其他进程拿到帧，且不能使后者也颠簸。然而这个问题还没有完全得到解决，如果进程颠簸，那么绝大多数时间内也会排队来等待调页设备。由于调页设备的更长的平均队列，也错误的平均等待时间也会增加。因此，即使对没有颠簸的进程，其有效访问时间也会增加。
为了防止颠簸，必须提供进程所需的足够多的帧。但是如何知道进程"需要"多少帧呢？有多种技术。工作集合策略是研究一个进程实际正在使用多少帧。这种方法定义了进程执行的局部模型（locality model）。
局部模型说明，当进程执行时，它从一个局部移向另一个局部。局部是一个经常使用页的集合，一个程序通常由多个不同局部组成，它们可能重叠。

文章图片

例如，当一个子程序被调用时，它就定义了一个新局部。在这个局部里，内存引用包括该子程序的指令、其全局变量和全局变量的子集。当该子程序退出时，因为子程序的局部变量和指令现已不再使用，进程离开该局部。也可能在后面再次返回该局部。
可以看到局部是由程序结构和数据结构来定义的。局部模型说明了所有程序都具有这种基本的内存引用结构。局部模型是缓存的基础。如果对任何数据结构的访问是随机的而没有一定的模型，那么缓存就没有用了。

工作集合模型工作集合模型（working-set model）是基于局部性假设的。该模型使用参数定义工作集合窗口（working-set window）。其思想是检查最近个页的引用。这最近个引用过的页集合称为工作集合（working set）。如果一个页正在使用中，那么它就在工作集合内。如果它不再使用，那么它会在其上次引用的时间单位后从工作集合中删除。因此，工作集合是程序局部的近似。

文章图片

最为重要的工作集合的属性是其大小。如果经计算而得到系统内每个进程的工作集合为，那么就得到

文章图片

其中D为总的帧需求量。每个进程都经常要使用位于其工作集合内的页。因此，进程i需要帧。如果总的需求大于可用帧的数量（D>m），那么有的进程就会得不到足够得帧，从而出现颠簸。
一旦确定了，那么工作集合模型得使用就较为简单。操作系统跟踪每个进程的工作集合，并为进程分配大于其工作集合的帧数。如果还有空闲帧，那么可启动另一个进程。如果所有工作集合之和的增加超过了可用帧的总数，那么操作系统会选择暂停一个进程。该进程的页被写出，且其帧可分配给其他进程。挂起的进程可以在以后重启。
这种工作集合策略防止了颠簸，并尽可能提高了多道程序的程序。因此，它优化了CPU使用率。工作集合模型的困难是跟踪工作集合。工作集合窗口是移动窗口。在每次引用时，会增加新引用，而最老的引用会失去。如果一个页在工作集合窗口内被引用过，那么它就处于工作集合内。
页错误频率工作集合模型是成功的，工作集合知识能用于预先调页，但是用于控制颠簸有点不太灵活。一种更为直接的方法是采用页错误频率（page-fault frequency,PFF）策略。
这里的问题是如何防止颠簸，颠簸具有高的也错误率。因此，需要控制页错误率。当也错误率太高时，进程需要更多帧。类似地，如果页错误率太低，那么进程可能有太多的帧。可以为所期望的页错误率设置上限和下限。如果实际页错误率超过上限，那么为进程分配更多的帧；如果实际页错误率低于下限，那么可从该进程中移走帧。因此，可以直接测量和控制页错误率以防止颠簸。
与工作集合策略一样，也可能必须暂停一个进程。如果页错误增加且没有可用帧，那么必须选择一个进程暂停。接着，可将释放的帧分配给那些具有高页错误率的进程。

文章图片

文章图片

内存映射文件
考虑一下采用标准系统调用open(),read()和write()，并在磁盘上对文件进行一系列的读操作。文件每次访问时都需要一个系统调用和磁盘访问。另外一种方法时，可使用所讨论的虚拟内存技术来将文件I/O作为普通内存访问。这种方法称为文件的内存映射（memory mapping）,它允许一部分虚拟内存与文件逻辑相关联。
基本机制文件的内存映射可将一磁盘块映射成内存的一页（或多页）。开始的文件访问按普通请求页面调度来进行，会产生页错误。这样，一页大小的部分文件从文件系统读入物理页（有的系统会一次读入多个一页大小的内容）。以后文件的读写就按通常的内存访问来处理，由于是通过内存操作文件而不是使用系统调用read()和write()，从而简化了文件访问和使用。
多个进程可以允许将同一文件映射到各自的虚拟内存中，以允许数据共享。其中任一进程修改虚拟内存中的数据，都会为其他映射相同文件部分的进程所见。每个共享进程的虚拟内存表都指向物理内存的同一页，该页有磁盘块的复制。内存映射系统调用还支持写时复制功能，允许进程共享只读模式的文件，但也有它们所修改数据的各自副本。

文章图片

内核内存的分配
当用户态进程需要额外内存时，可以从内核所维护的空闲页帧链表中获取页。该链表通常由页替换算法来更新，且如前所述，这些页帧通常分散在物理内存中。另外，请记住，如果用户进程只需要一个字节的内存，那么会产生内部碎片，这是因为进程会得到整个页帧。
但是，内核内存的分配通常是从空闲内存池中获取的，而并不是从满足普通用户模式进程的内存链表中获取的。这主要有两个原因：

内核需要为不同大小的数据结构分配内存，其中有的不到一页。因此，内核必须谨慎使用内存，并试图减低碎片浪费。这一点非常重要，因为许多操作系统的内核代码与数据不受分页系统控制。
用户进程所分配的页不必要在连续的物理内存中。然而，有的硬件要直接与物理内存打交道，而不需要经过虚拟内存接口，因此需要内存常驻在连续的物理页中。

slab分配内核分配的另一种方案是slab分配。Slab是由一个或多个物理上连续的页组成的。高速缓存（cache）含有一个或多个slab。每个内核数据结构都有一个cache，如进程描述符、文件对象、信号量等。每个cache含有内核数据结构的对象实例。例如，信号量cache存储着信号量对象，进程描述符cache存储着进程描述对象。下图描述了slab，cache以及对象三者之间的关系。Slab分配算法采用cache存储内存对象。当创建cache时，起初包括若干标记为空闲的对象。对象的数量与slab的大小有关。
Slab分配器有两个主要优点：

没有因碎片而引起的内存浪费。碎片不是问题，这时因为每个内核数据结构都有相应的cache，而每个cache都由若干slab组成，而每个slab又分为若干个与对象大小相同的部分。因此，当内核请求对象内存时，slab分配器可以返回刚好可以表示对象所需的内存。
内存请求可以快速满足。Slab分配器对于需要经常不断分配内存、释放内存来说特别有效，而操作系统经常这样做。内存分配与释放可能费时。然而，由于对象预先创建，所以可从cache上快速分配。另外，当用完对象并释放时，只需要标记为空闲并返回给cache，以便下次再用。

文章图片

小结
需要能执行这样一个进程，其逻辑地址大于可用物理地址空间。虚拟内存允许将大逻辑地址空间映射到小的物理内存。虚拟内存允许极大的进程运行，且提高了多道程序的程序，增加CPU使用率。再者，它使得程序员不必考虑内存可用性。另外，虚拟内存允许进程共享系统库与内存。当父子进程共享内存页时，虚拟内存也允许采用写时复制来创建进程。
虚拟内存通常采用按需调页方式来实现。纯按需调页只有再引用页时才调入页。第一次引用就会使操作系统产生页错误。操作系统检查内部表以确定该页再备份仓库上的位置。接着，它找到空闲帧并从备份仓库中读入页。更新页表以反映这一修改，并重新执行产生页错误的指令。这种方法允许一个进程运行，即使完整内存影像不能同时在内存中。只要页错误率足够低，那么性能就可以被接受。
使用按需调页以降低分配给进程的帧数。这种安排能增加多道程序的程度（允许更多进程同时执行），且增加系统CPU使用率。即使进程内存需要超过总的物理内存，也能允许进程运行。这些进程可以在虚拟内存中运行。
如果总的内存需求超过了物理内存，那么有可能必须置换内存中的页以便为新页所用。可以使用各种页置换算法。FIFO页置换算法容易编程，但有Belady异常。最优页置换算法需要将来的知识。LRU页置换能近似最优算法，但是它也很难实现。绝大多数页置换算法，如二次机会算法，都是LRU置换的近似。
除了页置换算法，还需要帧分配策略。分配可以是固定的，如局部页置换算法；或动态的，如全局置换。工作集合模型假定进程在局部内执行。工作集是位于当前局部所有页的集合。相应地，每个进程应该为其当前工作集合分配足够多地内存以避免颠簸，可能需要进程交换和调度。
许多操作系统提供内存映射文件功能，如允许文件I/O像内存访问操作一样。Win32API通过内存映射来实现内存共享。
内核进程通常需要按物理连续方式来分配内存。Buddy系统允许内核进程按2的幂大小来分配，这会产生碎片。Slab分配器允许从由slab组成的cache进行分配，每个slab由若干物理连续的页组成。采用slab分配器，不会因碎片问题而产生内存浪费，内存请求可以很快得到满足。
除了要求解决页置换和帧分配的主要问题外，合理设计调页系统还要求考虑页大小，I/O、加锁、预调页、进程创建、程序结构和其他问题。