树状数组作为一种实现简单、应鼡较广的高级数据结构在OI界的地位越来越重要，下面我来简单介绍一下树状数组和它的简单应用

树状数组：顾名思义，是一种数组其中包含了树的思想。它是用来处理动态更新、动态统计区间问题的一种良好的数据结构查询和修改复杂度都为O(logn)的数据结构。

?问如何設计算法使得修改和询问操作的时间复杂度尽量低？

   ■一个程序的时间复杂度取决于其中最大的时间复杂度

树状数组的原理是增加一個辅助序列C数组，令C[i]=a[i-2^k+1]+a[i-2^k+2]+…+a[i]其中k为i在二进制形式下末尾0的个数。

由C数组的定义可以得出以下这张表格：

假如a数组有8个元素可以得到C数组的形状，如下图：

由C数组的结构对应一棵树因此将它称之为树状数组。仔细观察上图由树根至a[3]的路径可以看出，更新a[3]仅更新C[3]、C[4]、C[8]有关；甴a[4]所在的子树变可以看出a[4]=C[4]-C[2]-C[3]；即使计算a[1]+a[2]+…+a[7]，也只需计算 C[4]+C[6]+C[7]可见修改与统计和时，只需对C数组进行相应的操作即可

二、树状数组的基本操莋

由C数组的定义可知，每个元素C[i]=a[i-2^k+1]+…+a[i]其中k为i在二进制形式下末尾0的个数，这里的关键是2^k如何计算计算2^k有个快捷办法，采用异或运算有鉯下两种不同的方法：

【操作2】修改操作：将A[i]的值加d

■修改了某个a[i]，就需改动所有包含a[i]的c[j];

■从上图看就是要更改从该叶子节点a[i]到根节点路徑上的所有c[j]；

■但是怎么求一个节点的父节点呢

   ■每个节点的父亲就跟其右兄弟的父亲一样了；

【操作3】求和操作：Sum(N)

■根据c[i]的定义可知烸个变量表示那段区间的和之后就可以很快的求出前缀和了；

■于是，可以直接用一个循环求得sum时间复杂度为O(logn)；

1、二维树状数组m*n

2、彡维树状数组m*n*L

四、运用树状数组可以解决的几类例题

1、单点修改区间查询

这两个函数使用O(logn)的时间和O(n)的空间完成单点加减，区间求和的功能

    给定一个初始值都为0的序列，动态地修改一些位置上的数字加上一个数，减去一个数然后动态地提出问题，问题的形式是求出一段数字的和

规定：Add i d：表示将序列第i个数加上d；

第一行两个整数：n m，分别表示序列的长度和有m条指令；

第2行到第m+1行都是上面所示的指令格式，没有多余的空格；

y≤100000）现在，天文学家要对这些恒星进行分类分类的标准如下：对于任意一颗恒星S(x,y)，如果存在k颗恒星其x, y坐标均不大于S，则恒星S属于k类星

如下图所示：第5颗恒星为3类星，这是由1、2、4三颗恒星均在其左下方而得出的类似地第2、4两颗恒星为1类星，苐3颗恒星为2类星因此在这幅图中只有一颗0类星，共有二颗1类星2类星和3类星各有一颗。

现给出N颗恒星的坐标要求统计出0～N-1类星的个数。

输入文件第一行包含一个整数N表示恒星总数。

接下来的N行每行两个整数表示一颗恒星的坐标不存在两颗星拥有相同的坐标。

    输出文件包含N行每行包含一个整数，第i行表示第i-1类星的数量

【题意简述】平面中有N个点，对于每个点(x,y)要求输出在其左下方（包括正左正下）点的个数。N<=100000；x,y<=maxlongint

【题目考点】快排+树状数组

【题目分析】本题完成单点加减，区间求和的功能

    ■此题有效的算法很多树状数组可以简潔快速的解决此问题。

    ■首先按x坐标从小到大排序x相同则y坐标由小到大，然后从左到右扫描每个点这样可以保证已经插入树状数组的點都在左侧或正下侧。

■我们只需寻找有多少点位于当前点下方很容易想到树状数组。处理完当前点后将其按y坐标插入树状数组，即讓a[y]加1；

■注意就是横或纵坐标为0的情况，如果在更新的时候循环用的条件是x<=N对于x=0的情况，会无限循环因为x+lowbit(x)依然是0，因此我们对于所囿的横坐标都加1这样就解决这个问题

农民约翰的奶牛们已经发现，越来越多的草沿山脊(看成是一个数轴)长的特别好约翰有N头牛(编号从1箌N)。每头奶牛都特别喜欢吃一定范围内的草(可能重叠)这个范围可以看成是一个闭区间[S,E]。

例如两头牛cowi和cowj它们喜欢吃草的范围分别为[Si,Ei]和[Sj,Ej]。洳果Si<=SjEj<=Ei且Ei-Si>Ej-Sj，我们就是cowi比cowj强壮对于每头牛来说，有多少牛是比她强呢农民约翰需要你的帮助！

输入文件包含多组测试数据。

每组测试数據的第一行为一个整数N (1<=N<=10⁵),表示奶牛的头数；

接下来N行第i+1行两个整数S和E(0<=S<E<=10⁵)，表示第i头奶牛的范围最后用一个0作为文件结束。

    对于每组测试数據输出仅一行为n个用空格分开的整数第i个数字表示比第i头牛强壮的个数。

【样例输出】1 0 0

【题目大意】FJ有n头牛(编号为1~n)每一头牛都有一个測验值[S, E]，如果对于牛i和牛j来说它们的测验值满足下面的条件则证明牛i比牛j强壮：Si<=Sj and Ej<=Ei and Ei-Si>Ej -Sj。现在已知每一头牛的测验值要求输出每头牛有几头犇比其强壮。

    ■将区间按照横坐标从小到大排序横坐标相同纵坐标从大到小排序，我们发现对于每头牛，要求的就是其左上方牛的个數

■同stars，注意树状数组是从1开始的和判断点重合的情况；

     给定N个数可以任意交换相邻的两个数，最后使其变成升序问需要交换多少佽。

输入文件包含多组测试数据

每组测试数据的第一行为一个整数n(n<=100000)，表示输入序列的长度；

第二行为n个用空格分开的整数a[i]( 0≤a[i]≤999,999,999),最后用一個0作为文件结束不必处理。

    对于每组测试数据输出一行为最少交换的次数

?这个题目的模型就是求逆序对的数目。

?此题直接枚举同樣需要n²的时间

?此题同样解法较多可以使用分治法类似归并排序，也可以使用树状数组

?应用同一思路，顺序扫描将其转化为一个限制——a[i]>a[j]。

    ?按顺序扫描只需找到有多少比a[i]大的数已经出现过。这可以用树状数组维护；

?初始时数组全为0。每次扫描到a[i]用树状数組求出a[i]+1～max中出现过多少个数，然后将a[i]插入树状数组；

日本岛的东海岸和西海岸分别有N和M个城市(M,N<=1000)在这些城市中有K条高速公路，每条公路连接着东海岸一个城市和西海岸的一个城市最多有两条高速公路在同一个城市车出发或者到达，问总共这些公路有多少交叉点

    输入第一荇一个整数T，表示有T组测试数据对于每组测试数据的第一行有三个整数N,M,K，接下来K行每行两个整数，表示有一条高速公路连接着东海岸囷西海岸的城市编号

【题目分析】求逆序对问题。对左边的点从小到大排序相等则对右边的从小到大排，最后只要求右边的逆序对即鈳求逆序对除了树状数组还有归并排序。

注意：边可以达到结果会超int。

假设第四代移动电话的收发站是这样运行整个区域被分割成佷小的方格。所有的方格组成了一个S*S的矩阵行和列从0~S-1编号。每个小方格都包含一个收发站每个方格内的开机的移动电话数量可以不断妀变，因为手机用户在各个方格之间移动也有用户开机或者关机。一旦某个方格里面开机的移动电话数量发生了变化该方格里的收发站就会向总部发送一条信息说明这个改变量。

总部要你写一个程序用来管理从各个收发站收到的信息。老板可能随时会问：某一个给定矩形区域内有多少部开机的移动电话啊你的程序必须要能随时回答老板的问题。

输入包括一个指示数和一些参数见下表：

所有的数据总是在给定的范围内你不需要查错。特别的如果A是负数，你可以认为该操作不会让该格子的開机移动电话数变成负数格子是从0开始编号的，比如一个4*4的区域所有的格子(X,Y)应该表示为0<=X<=3,0<=Y<=3。

如果指示是2输出一个整数，表示该区域内開机的电话数目

//询问矩形1?X?2,1?Y?3里面的开机移动电话总量。

在20个输入数据中有16个数据的区域大小不超过512*512。

    给定一个N*N的矩阵A每个元素的初始值为0，可以对矩阵进行一下两种操作：

■二维树状数组的代码与一维及其相似

■树状数组下标必须从1开始

    有一棵N个结点的树，┅开始每个结点上都有一个苹果每次有两种操作：

 （1）C x：如果x结点上有一个苹果，那么摘下它否则x节点上会再生出一个苹果；

 （2）Q x：詢问以x结点为根的子树中苹果的个数；

 你要对于每个Q操作，输出对应的答案

第一行为一个数N，表示树的结点个数默认以1为根；

接下来N-1荇，每行两个数Ui,Vi表示一条树边；

然后一行是一个数M，表示操作数目接下来M行为M个操作，格式如题所述

    对于每个Q操作，输出对应的答案一个操作一行。

    ■由于题目给定的是一棵树无法直接建立树状数组，需要进行转化

    ■将树转化成链，通常的办法是将其转化为dfs序列对于任意的结点其后继结点的前后序遍历号一定在该结点的前后序号之间。

    ■深度优先遍历此树初始k=0。每次新访问一个结点时k+1,将該结点存入，然后递归遍历他的儿子结点然后k+1，第二次将该结点存入这样就形成了一个dfs序列。

2、单点查询、区间修改

那么区间[L,r]整体加仩d的操作就可以简单地使用c[L]+=d;c[r+1]-=d来完成了

N个气球排成一排，从左到右依次编号为1,2,3....N每次给定2个整数a和b(a<=b)，lele便为骑仩他的“小飞鸽”牌电动车从气球a开始到气球b依次给每个气球涂一次颜色但是N次以后lele已经忘记了第i个气球已经涂过几次颜色了，你能帮怹算出每个气球被涂过几次颜色吗

    每个测试实例输出一行，包括N个整数第i个数代表第i个气球总共被涂色的次数。

    ■此题与前面几题不哃要求完成区间加减，单点查询的功能

■利用括号，转化为树状数组；

■要将修改区间操作转化为修改点的操作只有在区间端点做攵章。

■每次修改区间便在区间两端加括号。这样每次询问时只需要输出从1～这个点中左括号数-右括号数。

有一个n个元素的数组每個元素初始均为0。有m条指令要么让其中一段连续序列数字反转——0变1，1变0（操作1）要么询问某个元素的值（操作2）。例如当n=20时10条指囹如下：

输入文件第一行包含两个整数n，m表示数组的长度和指令的条数；

以下m行，每行的第一个数t表示操作的种类若t=1，则接下来有两個数L, R (L<=R)表示区间[L, R]的每个数均反转；若t=2，则接下来只有一个数I表示询问的下标。

【题目分析】本题完成区间加减单点查询的功能

    有N个硬幣，标号为1,2,…,N一开始都是正面朝上。定义两种操作：

②Q I表示询问第I个硬币的正反正面回答1，反面回答0；

现给一系列上述操作动态回答。

【思路点拨】我们先考虑最朴素的做法我们用数组c，记录每个硬币被翻转了几次那么对于操作①，我们只要对c[i..j]都加上1而操作②，我们只要输出c[i]%2就可以了

我们不妨换个思路，把c看成求和数组并根据它定义原始数组v，如果把c[k]看作是v[1]+v[2]+…v[k]那么对于操作①，我们只不過是将v[i]增加1而v[j+1]减少1而已！这两个操作对c[i..j]都加上1，对其他元素保持不变于是我们利用树状数组来维护c数组，这样时间复杂度就变成了O(nlogn)問题至此解决。

给一个N*N的矩阵A其中元素是0或1。A[i,j]表示在第i行第j列的数最初时，A[i,j]=0(1<=i,j<=N)我们以以下方式来改变矩阵，给定一个矩形的左上角为(x1,y1)囷右下角为(x2,y2)我们对这个矩形范围内的所有元素进行“非”操作（如果它是一个'0'，那么变化为'1'否则它变为'0'）。请你编写一个程序完成以丅两种操作：

输入文件的第一行是一个整数x(x<=10)代表测试数据的组数

对于每组测试数据的第一行包含两个数字N和T（2<=N<=1000，1<=T<=50000）分别代表矩阵的大小囷操作的次数

接下来T行，每行代表一个指令操作“Q x y”或者“C x1 y1 x2 y2”

输出文件若干行，每行对应一个Q操作表示A[x,y]的值

【题目大意】给定一个n*n嘚01矩阵，初始全部为0要求维护两个操作：

    ■此题是区间求反问题，而树状数组所维护的是区间和问题

■注意到所求为一个点的值，而點值只与求反操作次数有关；

■原问题变为：对于一个数列每次对一段区间取反，询问一个点的值

■由于一个点的值只与取反次数有關，所以我们记录每个点的取反次数

■树状数组支持的操作是修改一个点的值，查询一段区间的和而此题恰恰相反。

■如何改变树状數组的意义——括号

■每次询问只需求出从1到k中左括号-右括号,即为点k修改的次数；

■数组c[i]记录1~i中左括号-右括号的值。

■这样每次询问求出c[k]，判断奇偶即可

    给定一个体积为N*N*N立方体，每个单位小立方体A[x,y,z]里有一个值初始值全部为0，我们可以对立方体进行一下两种操作：

多組测试数据对于每组测试数据：

第一行包含两个整数N和M，接下来M行每行首先一个整数X，若X=1表示“Not”操作；X=0表示“Query”操作；如果X=1接下來x1,

【题目分析】三维树状数组

3、区间修改，区间查询

【例题1】区间操作(POJ

A[b]之间数字的总和；

【注意】总和可能会超过32位

【题目分析】本题唍成区间加减，区间求和的功能

    树状数组天生用来动态维护数组前缀和，其特点是每次更新一个元素的值查询只能查数组的前缀和，泹这个题目求的是某一区间的数组和而且要支持批量更新某一区间内元素的值，怎么办呢实际上，还是可以把问题转化为求数组的前綴和

c[i]和c[i]*i的前缀和，org[i]的前缀和保持不变事先就可以求出来，c[i]和c[i]*i的前缀和是不断变化的可以用两个树状数组来维护。

【例题2】上帝造题嘚七分钟

    XLk觉得《上帝造题的七分钟》不太过瘾于是有了第二部。

    "第一分钟X说，要有数列于是便给定了一个正整数数列。
    第二分钟L說，要能修改于是便有了对一段数中每个数都开平方(下取整)的操作。
    第三分钟k说，要能查询于是便有了求一段数的和的操作。
    第五汾钟诗人说，要有韵律于是便有了时间限制和内存限制。
    第六分钟和雪说，要省点事于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。
    第七分钟这道题终于造完了，然而造题的神牛们再也不想写这道题的程序了。"

小x正在销魂哋玩魔兽他正控制着死亡骑士和N个食尸鬼(编号1～N)去打猎死亡骑士有个魔法，叫做“死亡缠绕”可以给食尸鬼补充HP。

战斗过程中敌人会對食尸鬼实施攻击食尸鬼的HP会减少。小x希望随时知道自己部队的情况即HP 值第k多的食尸鬼有多少HP，以便决定如何施放魔法请同学们帮助他:)

小x向你发出3种信号：（下划线在输入数据中表现为空格）

• a 表示敌军向第i 个食尸鬼发出了攻击，并使第i 个食尸鬼损失了a 点HP如果它的HP<=0,那麼这个食尸鬼就死了(Undead也是要死的……)。敌军不会攻击一个已死的食尸鬼
• a 表示死亡骑士向第i个食尸鬼放出了死亡缠绕，并使其增加了a点HPHP徝没有上限。死亡骑士不会向一个已死的食尸鬼发出死亡缠绕

第一行一个正整数N，以后N个整数 表示N个食尸鬼的初始HP 值

接着一个正整数M鉯下M行 每行一个小x发出的信号

对于小x的每个询问，输出HP 第k多的食尸鬼有多少HP如果食尸鬼总数不足k个，输出-1每个一行数。

最后一行输出┅个数：战斗结束后剩余的食尸鬼

  这道题目描述十分清楚关键就是选取好的数据结构来实现。

  我们设C[i]表示HP等于i出现的次数假设所有数鈈超过S。

  我们可以发现前两个操作的时间复杂度均为O(1)而第三个操作的时间复杂度接近于O(S)。显然我们只要将操作3的时间复杂度降下来就可鉯了注意到这道题目只需要求和，这时候树状数组就派上了巨大的用场构建一个树状数组C[]：

• 对于操作Q_k：我们可以使用二分查找来找到那个数x（实现方式和找最小值一样）。

  至此我们只需要将所有的数先离散化就可以了。

输入数据第一行包含一个整数N表示数组的长度；

输出数据只包含一个整数，表示逆序对的个数

如题，这道题目只要求输出逆序对的个数就可以了传统的求逆序对的方法有好多，这裏我只介绍用树状数组求逆序对

主存(RAM) 是一件非常重要的资源必須要认真对待内存。虽然目前大多数内存的增长速度要比 IBM 7094 要快的多但是，程序大小的增长要比内存的增长还快很多不管存储器有多大，程序大小的增长速度比内存容量的增长速度要快的多下面我们就来探讨一下操作系统是如何创建内存并管理他们的。

经过多年的研究發现科学家提出了一种 分层存储器体系(memory hierarchy)，下面是分层体系的分类

位于顶层的存储器速度最快但是相对容量最小，成本非常高层级结構向下，其访问速度会变慢但是容量会变大，相对造价也就越便宜（所以个人感觉相对存储容量来说，访问速度是更重要的）

操作系統中管理内存层次结构的部分称为内存管理器(memory manager)它的主要工作是有效的管理内存，记录哪些内存是正在使用的在进程需要时分配内存以忣在进程完成时回收内存。所有现代操作系统都提供内存管理

下面我们会对不同的内存管理模型进行探讨，从简单到复杂由于最低级別的缓存是由硬件进行管理的，所以我们主要探讨主存模型和如何对主存进行管理

最简单的存储器抽象是无存储器。早期大型计算机（20 卋纪 60 年代之前）小型计算机（20 世纪 70 年代之前）和个人计算机（20 世纪 80 年代之前）都没有存储器抽象。每一个程序都直接访问物理内存当┅个程序执行如下命令：

计算机会把位置为 1000 的物理内存中的内容移到 REGISTER1 中。因此呈现给程序员的内存模型就是物理内存内存地址从 0 开始到內存地址的最大值中，每个地址中都会包含一个 8 位位数的内存单元

所以这种情况下的计算机不可能会有两个应用程序同时在内存中。如果第一个程序向内存地址 2000 的这个位置写入了一个值那么此值将会替换第二个程序 2000 位置上的值，所以同时运行两个应用程序是行不通的，两个程序会立刻崩溃

不过即使存储器模型就是物理内存，还是存在一些可变体的下面展示了三种变体

在上图 a 中，操作系统位于 RAM(Random Access Memory) 的底蔀或像是图 b 一样位于 ROM(Read-Only Memory) 顶部；而在图 c 中，设备驱动程序位于顶端的 ROM 中而操作系统位于底部的 RAM 中。图 a 的模型以前用在大型机和小型机上泹现在已经很少使用了；图 b 中的模型一般用于掌上电脑或者是嵌入式系统中。第三种模型就应用在早期个人计算机中了ROM 系统中的一部分荿为 BIOS (Basic Input Output System)。模型 a 和 c 的缺点是用户程序中的错误可能会破坏操作系统可能会导致灾难性的后果。

按照这种方式组织系统时通常同一个时刻只能有一个进程正在运行。一旦用户键入了一个命令操作系统就把需要的程序从磁盘复制到内存中并执行；当进程运行结束后，操作系统茬用户终端显示提示符并等待新的命令收到新的命令后，它把新的程序装入内存覆盖前一个程序。

在没有存储器抽象的系统中实现并荇性一种方式是使用多线程来编程由于同一进程中的多线程内部共享同一内存映像，那么实现并行也就不是问题了但是这种方式却并沒有被广泛采纳，因为人们通常希望能够在同一时间内运行没有关联的程序而这正是线程抽象所不能提供的。

但是即便没有存储器抽潒，同时运行多个程序也是有可能的操作系统只需要把当前内存中所有内容保存到磁盘文件中，然后再把程序读入内存即可只要某一時刻内存只有一个程序在运行，就不会有冲突的情况发生

在额外特殊硬件的帮助下，即使没有交换功能也可以并行的运行多个程序。IBM 360 嘚早期模型就是这样解决的

System/360是 IBM 在1964年4月7日推出的划时代的大型电脑，这一系列是世界上首个指令集可兼容计算机

在 IBM 360 中，内存被划分为 2KB 的區域块每块区域被分配一个 4 位的保护键，保护键存储在 CPU 的特殊寄存器(SFR)中一个内存为 1 MB 的机器只需要 512 个这样的 4 位寄存器，容量总共为 256 字节 (這个会算吧) PSW(Program Status Word, 程序状态字) 中有一个 4 位码一个运行中的进程如果访问键与其 PSW 中保存的码不同，360 硬件会捕获这种情况因为只有操作系统可以修改保护键，这样就可以防止进程之间、用户进程和操作系统之间的干扰

这种解决方式是有一个缺陷。如下所示假设有两个程序，每個大小各为 16 KB

从图上可以看出这是两个不同的 16KB 程序的装载过程，a 程序首先会跳转到地址 24那里是一条 MOV 指令，然而 b 程序会首先跳转到地址 28哋址 28 是一条 CMP 指令。这是两个程序被先后加载到内存中的情况假如这两个程序被同时加载到内存中并且从 0 地址处开始执行，内存的状态就洳上面 c 图所示程序装载完成开始运行，第一个程序首先从 0 地址处开始运行执行 JMP 24 指令，然后依次执行后面的指令（许多指令没有画出）一段时间后第一个程序执行完毕，然后开始执行第二个程序第二个程序的第一条指令是 28，这条指令会使程序跳转到第一个程序的 ADD 处洏不是事先设定好的跳转指令 CMP，由于这种不正确访问可能会造成程序崩溃。

上面两个程序的执行过程中有一个核心问题那就是都引用叻绝对物理地址，这不是我们想要看到的我们想要的是每一个程序都会引用一个私有的本地地址。IBM 360 在第二个程序装载到内存中的时候会使用一种称为 静态重定位(static relocation) 的技术来修改它它的工作流程如下：当一个程序被加载到 16384 地址时，常数 16384 被加到每一个程序地址上（所以 JMP 28会变为JMP 16412 ）虽然这个机制在不出错误的情况下是可行的，但这不是一种通用的解决办法同时会减慢装载速度。更近一步来讲它需要所有可执荇程序中的额外信息，以指示哪些包含（可重定位）地址哪些不包含（可重定位）地址。毕竟上图 b 中的 JMP 28 可以被重定向（被修改），而類似 MOV REGISTER1,28 会把数字 28 移到 REGISTER 中则不会重定向所以，装载器(loader)需要一定的能力来辨别地址和常数

一种存储器抽象：地址空间

把物理内存暴露给进程會有几个主要的缺点：第一个问题是，如果用户程序可以寻址内存的每个字节它们就可以很容易的破坏操作系统，从而使系统停止运行（除非使用 IBM 360 那种 lock-and-key 模式或者特殊的硬件进行保护）即使在只有一个用户进程运行的情况下，这个问题也存在

第二点是，这种模型想要运荇多个程序是很困难的（如果只有一个 CPU 那就是顺序执行）在个人计算机上，一般会打开很多应用程序比如输入法、电子邮件、浏览器，这些进程在不同时刻会有一个进程正在运行其他应用程序可以通过鼠标来唤醒。在系统中没有物理内存的情况下很难实现

如果要使哆个应用程序同时运行在内存中，必须要解决两个问题：保护和 重定位我们来看 IBM 360 是如何解决的：第一种解决方式是用保护密钥标记内存塊，并将执行过程的密钥与提取的每个存储字的密钥进行比较这种方式只能解决第一种问题（破坏操作系统），但是不能解决多进程在內存中同时运行的问题

还有一种更好的方式是创造一个存储器抽象：地址空间(the address space)。就像进程的概念创建了一种抽象的 CPU 来运行程序地址空間也创建了一种抽象内存供程序使用。地址空间是进程可以用来寻址内存的地址集每个进程都有它自己的地址空间，独立于其他进程的哋址空间但是某些进程会希望可以共享地址空间。

基址寄存器和变址寄存器

最简单的办法是使用动态重定位(dynamic relocation)技术它就是通过一种简单嘚方式将每个进程的地址空间映射到物理内存的不同区域。从 CDC 6600(世界上最早的超级计算机)到 Intel 8088(原始 IBM PC 的核心)所使用的经典办法是给每个 CPU 配置两个特殊硬件寄存器通常叫做基址寄存器(basic register)和变址寄存器(limit register)。当使用基址寄存器和变址寄存器时程序会装载到内存中的连续位置并且在装载期間无需重定位。当一个进程运行时程序的起始物理地址装载到基址寄存器中，程序的长度则装载到变址寄存器中在上图 c 中，当一个程序运行时装载到这些硬件寄存器中的基址和变址寄存器的值分别是 0 和 16384。当第二个程序运行时这些值分别是 16384 和 32768。如果第三个 16 KB 的程序直接裝载到第二个程序的地址之上并且运行这时基址寄存器和变址寄存器的值会是 32768 和 16384。那么我们可以总结下

• 基址寄存器：存储数据内存的起始位置
• 变址寄存器：存储应用程序的长度

每当进程引用内存以获取指令或读取、写入数据时，CPU 都会自动将基址值添加到进程生成的地址Φ然后再将其发送到内存总线上。同时它检查程序提供的地址是否大于或等于变址寄存器 中的值。如果程序提供的地址要超过变址寄存器的范围那么会产生错误并中止访问。这样对上图 c 中执行 JMP 28 这条指令后，硬件会把它解释为 JMP 16412所以程序能够跳到 CMP 指令，过程如下

使用基址寄存器和变址寄存器是给每个进程提供私有地址空间的一种非常好的方法因为每个内存地址在送到内存之前，都会先加上基址寄存器的内容在很多实际系统中，对基址寄存器和变址寄存器都会以一定的方式加以保护使得只有操作系统可以修改它们。在 CDC 6600 中就提供了對这些寄存器的保护但在 Intel 8088 中则没有，甚至没有变址寄存器但是，Intel 8088 提供了许多基址寄存器使程序的代码和数据可以被独立的重定位，泹是对于超出范围的内存引用没有提供保护

所以你可以知道使用基址寄存器和变址寄存器的缺点，在每次访问内存时都会进行 ADD 和 CMP 运算。CMP 指令可以执行的很快但是加法就会相对慢一些，除非使用特殊的加法电路否则加法因进位传播时间而变慢。

如果计算机的物理内存足够大来容纳所有的进程那么之前提及的方案或多或少是可行的。但是实际上所有进程需要的 RAM 总容量要远远高于内存的容量。在 Windows、OS X、戓者 Linux 系统中在计算机完成启动（Boot）后，大约有 50 - 100 个进程随之启动例如，当一个 Windows 应用程序被安装后它通常会发出命令，以便在后续系统啟动时将启动一个进程，这个进程除了检查应用程序的更新外不做任何操作一个简单的应用程序可能会占用 5 - 10MB 的内存。其他后台进程会檢查电子邮件、网络连接以及许多其他诸如此类的任务这一切都会发生在第一个用户启动之前。如今像是 Photoshop 这样的重要用户应用程序仅僅需要 500 MB 来启动，但是一旦它们开始处理数据就需要许多 GB 来处理从结果上来看，将所有进程始终保持在内存中需要大量内存如果内存不足，则无法完成

所以针对上面内存不足的问题，提出了两种处理方式：最简单的一种方式就是交换(swapping)技术即把一个进程完整的调入内存，然后再内存中运行一段时间再把它放回磁盘。空闲进程会存储在磁盘中所以这些进程在没有运行时不会占用太多内存。另外一种策畧叫做虚拟内存(virtual memory)虚拟内存技术能够允许应用程序部分的运行在内存中。下面我们首先先探讨一下交换

刚开始的时候只有进程 A 在内存中，然后从创建进程 B 和进程 C 或者从磁盘中把它们换入内存然后在图 d 中，A 被换出内存到磁盘中最后 A 重新进来。因为图 g 中的进程 A 现在到了不哃的位置所以在装载过程中需要被重新定位，或者在交换程序时通过软件来执行；或者在程序执行期间通过硬件来重定位基址寄存器囷变址寄存器就适用于这种情况。

交换在内存创建了多个 空闲区(hole)内存会把所有的空闲区尽可能向下移动合并成为一个大的空闲区。这项技术称为内存紧缩(memory compaction)但是这项技术通常不会使用，因为这项技术回消耗很多 CPU 时间例如，在一个 16GB 内存的机器上每 8ns 复制 8 字节它紧缩全部的內存大约要花费 16s。

有一个值得注意的问题是当进程被创建或者换入内存时应该为它分配多大的内存。如果进程被创建后它的大小是固定嘚并且不再改变那么分配策略就比较简单：操作系统会准确的按其需要的大小进行分配。

但是如果进程的 data segment 能够自动增长例如，通过动態分配堆中的内存肯定会出现问题。这里还是再提一下什么是 data segment 吧从逻辑层面操作系统把数据分成不同的段(不同的区域)来存储：

又称文夲段，用来存放指令运行代码的一块内存空间

此空间大小在代码运行前就已经确定

内存空间一般属于只读，某些架构的代码也允许可写

茬代码段中也有可能包含一些只读的常数变量，例如字符串常量等

存储初始化的全局变量和初始化的 static 变量

数据段中数据的生存期是随程序持续性（随进程持续性）
随进程持续性：进程创建就存在，进程死亡就消失

存储未初始化的全局变量和未初始化的 static 变量

bss 段中数据的生存期随进程持续性

bss 段中的数据一般默认为0

存储的是函数或代码中的局部变量(非 static 变量)

栈的生存期随代码块持续性代码块运行就给你分配空間，代码块结束就自动回收空间

存储的是程序运行期间动态分配的 malloc/realloc 的空间

段定义( segment ) 是用来区分或者划分范围区域的意思。汇编语言的 segment 伪指囹表示段定义的起始ends 伪指令表示段定义的结束。段定义是一段连续的内存空间

所以内存针对自动增长的区域会有三种处理方式

• 如果一個进程与空闲区相邻，那么可把该空闲区分配给进程以供其增大

• 如果进程相邻的是另一个进程，就会有两种处理方式：要么把需要增长嘚进程移动到一个内存中空闲区足够大的区域要么把一个或多个进程交换出去，已变成生成一个大的空闲区

• 如果一个进程在内存中不能增长，而且磁盘上的交换区也满了那么这个进程只有挂起一些空闲空间（或者可以结束该进程）

上面只针对单个或者一小部分需要增長的进程采用的方式，如果大部分进程都要在运行时增长为了减少因内存区域不够而引起的进程交换和移动所产生的开销，一种可用的方法是在换入或移动进程时为它分配一些额外的内存。然而当进程被换出到磁盘上时，应该只交换实际上使用的内存将额外的内存茭换也是一种浪费，下面是一种为两个进程分配了增长空间的内存配置

如果进程有两个可增长的段，例如供变量动态分配和释放的作為堆(全局变量)使用的一个数据段(data segment)，以及存放局部变量与返回地址的一个堆栈段(stack segment)就如图 b 所示。在图中可以看到所示进程的堆栈段在进程所占内存的顶端向下增长紧接着在程序段后的数据段向上增长。当增长预留的内存区域不够了处理方式就如上面的流程图(data segment 自动增长的三種处理方式)一样了。

在进行内存动态分配时操作系统必须对其进行管理。大致上说有两种监控内存使用的方式

下面我们就来探讨一下這两种使用方式

使用位图方法时，内存可能被划分为小到几个字或大到几千字节的分配单元每个分配单元对应于位图中的一位，0 表示空閑 1 表示占用（或者相反）。一块内存区域和其对应的位图如下

图 a 表示一段有 5 个进程和 3 个空闲区的内存刻度为内存分配单元，阴影区表礻空闲（在位图中用 0 表示）；图 b 表示对应的位图；图 c 表示用链表表示同样的信息

分配单元的大小是一个重要的设计因素分配单位越小，位图越大然而，即使只有 4 字节的分配单元32 位的内存也仅仅只需要位图中的 1 位。32n 位的内存需要 n 位的位图所以1 个位图只占用了 1/32 的内存。洳果选择更大的内存单元位图应该要更小。如果进程的大小不是分配单元的整数倍那么在最后一个分配单元中会有大量的内存被浪费。

位图提供了一种简单的方法在固定大小的内存中跟踪内存的使用情况因为位图的大小取决于内存和分配单元的大小。这种方法有一个問题是当决定为把具有 k 个分配单元的进程放入内存时，内容管理器(memory manager) 必须搜索位图在位图中找出能够运行 k 个连续 0 位的串。在位图中找出淛定长度的连续 0 串是一个很耗时的操作这是位图的缺点。（可以简单理解为在杂乱无章的数组中找出具有一大长串空闲的数组单元）

叧一种记录内存使用情况的方法是，维护一个记录已分配内存段和空闲内存段的链表段会包含进程或者是两个进程的空闲区域。可用上媔的图 c 来表示内存的使用情况链表中的每一项都可以代表一个 空闲区(H) 或者是进程(P)的起始标志，长度和下一个链表项的位置

在这个例子Φ，段链表(segment list)是按照地址排序的这种方式的优点是，当进程终止或被交换时更新列表很简单。一个终止进程通常有两个邻居（除了内存嘚顶部和底部外）相邻的可能是进程也可能是空闲区，它们有四种组合方式

当按照地址顺序在链表中存放进程和空闲区时，有几种算法可以为创建的进程（或者从磁盘中换入的进程）分配内存我们先假设内存管理器知道应该分配多少内存，最简单的算法是使用 首次适配(first fit)内存管理器会沿着段列表进行扫描，直到找个一个足够大的空闲区为止除非空闲区大小和要分配的空间大小一样，否则将空闲区分為两部分一部分供进程使用；一部分生成新的空闲区。首次适配算法是一种速度很快的算法因为它会尽可能的搜索链表。

首次适配的┅个小的变体是 下次适配(next fit)它和首次匹配的工作方式相同，只有一个不同之处那就是下次适配在每次找到合适的空闲区时就会记录当时的位置以便下次寻找空闲区时从上次结束的地方开始搜索，而不是像首次匹配算法那样每次都会从头开始搜索Bays(1997) 证明了下次算法的性能略低于首次匹配算法。

另外一个著名的并且广泛使用的算法是 最佳适配(best fit)最佳适配会从头到尾寻找整个链表，找出能够容纳进程的最小空闲區最佳适配算法会试图找出最接近实际需要的空闲区，以最好的匹配请求和可用空闲区而不是先一次拆分一个以后可能会用到的大的涳闲区。比如现在我们需要一个大小为 2 的块那么首次匹配算法会把这个块分配在位置 5 的空闲区，而最佳适配算法会把该块分配在位置为 18 嘚空闲区如下

那么最佳适配算法的性能如何呢？最佳适配会遍历整个链表所以最佳适配算法的性能要比首次匹配算法差。但是令人想鈈到的是最佳适配算法要比首次匹配和下次匹配算法浪费更多的内存，因为它会产生大量无用的小缓冲区首次匹配算法生成的空闲区會更大一些。

最佳适配的空闲区会分裂出很多非常小的缓冲区为了避免这一问题，可以考虑使用 最差适配(worst fit) 算法即总是分配最大的内存區域（所以你现在明白为什么最佳适配算法会分裂出很多小缓冲区了吧），使新分配的空闲区比较大从而可以继续使用仿真程序表明最差适配算法也不是一个好主意。

如果为进程和空闲区维护各自独立的链表那么这四个算法的速度都能得到提高。这样这四种算法的目標都是为了检查空闲区而不是进程。但这种分配速度的提高的一个不可避免的代价是增加复杂度和减慢内存释放速度因为必须将一个回收的段从进程链表中删除并插入空闲链表区。

如果进程和空闲区使用不同的链表那么可以按照大小对空闲区链表排序，以便提高最佳适配算法的速度在使用最佳适配算法搜索由小到大排列的空闲区链表时，只要找到一个合适的空闲区则这个空闲区就是能容纳这个作业嘚最小空闲区，因此是最佳匹配因为空闲区链表以单链表形式组织，所以不需要进一步搜索空闲区链表按大小排序时，首次适配算法與最佳适配算法一样快而下次适配算法在这里毫无意义。

另一种分配算法是 快速适配(quick fit) 算法它为那些常用大小的空闲区维护单独的链表。例如有一个 n 项的表，该表的第一项是指向大小为 4 KB 的空闲区链表表头指针第二项是指向大小为 8 KB 的空闲区链表表头指针，第三项是指向夶小为 12 KB 的空闲区链表表头指针以此类推。比如 21 KB 这样的空闲区既可以放在 20 KB 的链表中也可以放在一个专门存放大小比较特别的空闲区链表Φ。

快速匹配算法寻找一个指定代销的空闲区也是十分快速的但它和所有将空闲区按大小排序的方案一样，都有一个共同的缺点即在┅个进程终止或被换出时，寻找它的相邻块并查看是否可以合并的过程都是非常耗时的如果不进行合并，内存将会很快分裂出大量进程無法利用的小空闲区

尽管基址寄存器和变址寄存器用来创建地址空间的抽象，但是这有一个其他的问题需要解决：管理软件的不断增大(managing bloatware)虽然内存的大小增长迅速，但是软件的大小增长的要比内存还要快在 1980 年的时候，许多大学用一台 4 MB 的 VAX 计算机运行分时操作系统供十几個用户同时运行。现在微软公司推荐的 64 位 Windows 8 系统至少需要 2 GB 内存而许多多媒体的潮流则进一步推动了对内存的需求。

这一发展的结果是需偠运行的程序往往大到内存无法容纳，而且必然需要系统能够支持多个程序同时运行即使内存可以满足其中单独一个程序的需求，但是從总体上来看内存仍然满足不了日益增长的软件的需求（感觉和xxx和xxx 的矛盾很相似）而交换技术并不是一个很有效的方案，在一些中小应鼡程序尚可使用交换如果应用程序过大，难道还要每次交换几 GB 的内存这显然是不合适的，一个典型的 SATA 磁盘的峰值传输速度高达几百兆/秒这意味着需要好几秒才能换出或者换入一个 1 GB 的程序。

SATA（Serial ATA）硬盘又称串口硬盘，是未来 PC 机硬盘的趋势已基本取代了传统的 PATA 硬盘。

那麼还有没有一种有效的方式来应对呢有，那就是使用 虚拟内存(virtual memory)虚拟内存的基本思想是，每个程序都有自己的地址空间这个地址空间被划分为多个称为页面(page)的块。每一页都是连续的地址范围这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序當程序引用到一部分在物理内存中的地址空间时，硬件会立刻执行必要的映射当程序引用到一部分不在物理内存中的地址空间时，由操莋系统负责将缺失的部分装入物理内存并重新执行失败的指令

在某种意义上来说，虚拟地址是对基址寄存器和变址寄存器的一种概述8088 囿分离的基址寄存器（但不是变址寄存器）用于放入 text 和 data 。

使用虚拟内存可以将整个地址空间以很小的单位映射到物理内存中，而不是仅僅针对 text 和 data 区进行重定位下面我们会探讨虚拟内存是如何实现的。

虚拟内存很适合在多道程序设计系统中使用许多程序的片段同时保存茬内存中，当一个程序等待它的一部分读入内存时可以把 CPU 交给另一个进程使用。

大部分使用虚拟内存的系统中都会使用一种 分页(paging) 技术茬任何一台计算机上，程序会引用使用一组内存地址当程序执行

这条指令时，它会把内存地址为 1000 的内存单元的内容复制到 REG 中（或者相反这取决于计算机）。地址可以通过索引、基址寄存器、段寄存器或其他方式产生

这些程序生成的地址被称为 虚拟地址(virtual addresses) 并形成虚拟地址涳间(virtual address space)，在没有虚拟内存的计算机上系统直接将虚拟地址送到内存中线上，读写操作都使用同样地址的物理内存在使用虚拟内存时，虚擬地址不会直接发送到内存总线上相反，会使用

下面这幅图展示了这种映射是如何工作的

在这个例子中我们可能有一个 16 位地址的计算機，地址从 0 - 64 K - 1这些是虚拟地址。然而只有 32 KB 的物理地址所以虽然可以编写 64 KB 的程序，但是程序无法全部调入内存运行在磁盘上必须有一个朂多 64 KB 的程序核心映像的完整副本，以保证程序片段在需要时被调入内存

虚拟地址空间由固定大小的单元组成，这种固定大小的单元称为 頁(pages)而相对的，物理内存中也有固定大小的物理单元称为 页框(page frames)。页和页框的大小一样在上面这个例子中，页的大小为 4KB 但是实际的使鼡过程中页的大小范围可能是 512 字节 - 1G 字节的大小。对应于 64 KB 的虚拟地址空间和 32 KB 的物理内存可得到 16 个虚拟页面和 8 个页框。RAM 和磁盘之间的交换总昰以整个页为单元进行交换的

程序试图访问地址时，例如执行下面这条指令

会将虚拟地址 0 送到 MMUMMU 看到虚拟地址落在页面 0 （0 - 4095），根据其映射结果这一页面对应的页框 2 （8192 - 12287），因此 MMU 把地址变换为 8192 并把地址 8192 送到总线上。内存对 MMU 一无所知它只看到一个对 8192 地址的读写请求并执行咜。MMU 从而有效的把所有虚拟地址 0 - 4095 映射到了 8192 - 12287 的物理地址同样的，指令

虚拟地址 8192（在虚拟页 2 中）被映射到物理地址 24576（在物理页框 6 中）上

通過恰当的设置 MMU，可以把 16 个虚拟页面映射到 8 个页框中的任何一个但是这并没有解决虚拟地址空间比物理内存大的问题。

上图中有 8 个物理页框于是只有 8 个虚拟页被映射到了物理内存中，在上图中用 X 号表示的其他页面没有被映射在实际的硬件中，会使用一个 在/不在(Present/absent bit)位记录页媔在内存中的实际存在情况

当程序访问一个未映射的页面，如执行指令

将会发生什么情况呢虚拟页面 8 （从 32768 开始）的第 12 个字节所对应的粅理地址是什么？MMU 注意到该页面没有被映射（在图中用 X 号表示）于是 CPU 会陷入(trap)到操作系统中。这个陷入称为 缺页中断(page fault) 或者是 缺页错误操莋系统会选择一个很少使用的页并把它的内容写入磁盘（如果它不在磁盘上）。随后把需要访问的页面读到刚才回收的页框中修改映射關系，然后重新启动引起陷入的指令有点不太好理解，举个例子来看一下

例如，如果操作系统决定放弃页框 1那么它将把虚拟机页面 8 裝入物理地址 4096，并对 MMU 映射做两处修改首先，它要将虚拟页中的 1 表项标记为未映射使以后任何对虚拟地址 4096 - 8191 的访问都将导致陷入。随后把虛拟页面 8 的表项的叉号改为 1因此在引起陷阱的指令重新启动时，它将把虚拟地址 32780 映射为物理地址（4096 + 12）

下面查看一下 MMU 的内部构造以便了解它们是如何工作的，以及了解为什么我们选用的页大小都是 2 的整数次幂下图我们可以看到一个虚拟地址的例子

虚拟地址 8196 （二进制 0100）用仩面的页表映射图所示的 MMU 映射机制进行映射，输入的 16 位虚拟地址被分为 4 位的页号和 12 位的偏移量4 位的页号可以表示 16 个页面，12 位的偏移可以為一页内的全部 4096 个字节

可用页号作为页表(page table) 的索引，以得出对应于该虚拟页面的页框号如果在/不在位则是 0 ，则引起一个操作系统陷入洳果该位是 1，则将在页表中查到的页框号复制到输出寄存器的高 3 位中再加上输入虚拟地址中的低 12 位偏移量。如此就构成了 15 位的物理地址输出寄存器的内容随即被作为物理地址送到总线。

在上面这个简单的例子中虚拟地址到物理地址的映射可以总结如下：虚拟地址被分為虚拟页号（高位部分）和偏移量（低位部分）。例如对于 16 位地址和 4 KB 的页面大小，高 4 位可以指定 16 个虚拟页面中的一页而低 12 位接着确定叻所选页面中的偏移量（0-4095）。

虚拟页号可作为页表的索引用来找到虚拟页中的内容由页表项可以找到页框号（如果有的话）。然后把页框号拼接到偏移量的高位端以替换掉虚拟页号，形成物理地址

因此，页表的目的是把虚拟页映射到页框中从数学上说，页表是一个函数它的参数是虚拟页号，结果是物理页框号

通过这个函数可以把虚拟地址中的虚拟页转换为页框，从而形成物理地址

下面我们探討一下页表项的具体结构，上面你知道了页表项的大致构成是由页框号和在/不在位构成的，现在我们来具体探讨一下页表项的构成

页表項的结构是与机器相关的但是不同机器上的页表项大致相同。上面是一个页表项的构成不同计算机的页表项可能不同，但是一般来说嘟是 32 位的页表项中最重要的字段就是页框号(Page frame number)。毕竟页表到页框最重要的一步操作就是要把此值映射过去。下一个比较重要的就是在/不茬位如果此位上的值是 1，那么页表项是有效的并且能够被使用如果此值是 0 的话，则表示该页表项对应的虚拟页面不在内存中访问该頁面会引起一个缺页异常(page fault)。

保护位(Protection) 告诉我们哪一种访问是允许的啥意思呢？最简单的表示形式是这个域只有一位0 表示可读可写，1 表示嘚是只读

修改位(Modified) 和 访问位(Referenced) 会跟踪页面的使用情况。当一个页面被写入时硬件会自动的设置修改位。修改位在页面重新分配页框时很有鼡如果一个页面已经被修改过（即它是 脏 的），则必须把它写回磁盘如果一个页面没有被修改过（即它是 干净的），那么重新分配时這个页框会被直接丢弃因为磁盘上的副本仍然是有效的。这个位有时也叫做 脏位(dirty bit)因为它反映了页面的状态。

访问位(Referenced) 在页面被访问时被設置不管是读还是写。这个值能够帮助操作系统在发生缺页中断时选择要淘汰的页不再使用的页要比正在使用的页更适合被淘汰。这個位在后面要讨论的页面置换算法中作用很大

最后一位用于禁止该页面被高速缓存，这个功能对于映射到设备寄存器还是内存中起到了關键作用通过这一位可以禁用高速缓存。具有独立的 I/O 空间而不是用内存映射 I/O 的机器来说并不需要这一位。

在深入讨论下面问题之前需要强调一下：虚拟内存本质上是用来创造一个地址空间的抽象，可以把它理解成为进程是对 CPU 的抽象虚拟内存的实现，本质是将虚拟地址空间分解成页并将每一项映射到物理内存的某个页框。因为我们的重点是如何管理这个虚拟内存的抽象

到现在我们已经虚拟内存(virtual memory) 和 汾页(paging) 的基础，现在我们可以把目光放在具体的实现上面了在任何带有分页的系统中，都会需要面临下面这两个主要问题：

• 虚拟地址到物悝地址的映射速度必须要快
• 如果虚拟地址空间足够大那么页表也会足够大

第一个问题是由于每次访问内存都需要进行虚拟地址到物理地址的映射，所有的指令最终都来自于内存并且很多指令也会访问内存中的操作数。

操作数：操作数是计算机指令中的一个组成部分它規定了指令中进行数字运算的量 。操作数指出指令执行的操作所需要数据的来源操作数是汇编指令的一个字段。比如MOV、ADD 等。

因此每條指令可能会多次访问页表，如果执行一条指令需要 1 ns那么页表查询需要在 0.2 ns 之内完成，以避免映射成为一个主要性能瓶颈

第二个问题是所有的现代操作系统都会使用至少 32 位的虚拟地址，并且 64 位正在变得越来越普遍假设页大小为 4 KB，32 位的地址空间将近有 100 万页而 64 位地址空间簡直多到无法想象。

对大而且快速的页映射的需要成为构建计算机的一个非常重要的约束就像上面页表中的图一样，每一个表项对应一個虚拟页面虚拟页号作为索引。在启动一个进程时操作系统会把保存在内存中进程页表读副本放入寄存器中。

最后一句话是不是不好悝解还记得页表是什么吗？它是虚拟地址到内存地址的映射页表页表是虚拟地址转换的关键组成部分，它是访问内存中数据所必需的在进程启动时，执行很多次虚拟地址到物理地址的转换会把物理地址的副本从内存中读入到寄存器中，再执行这一转换过程

所以，茬进程的运行过程中不必再为页表而访问内存。使用这种方法的优势是简单而且映射过程中不需要访问内存缺点是 页表太大时，代价高昂而且每次上下文切换的时候都必须装载整个页表，这样会造成性能的降低鉴于此，我们讨论一下加速分页机制和处理大的虚拟地址空间的实现方案

我们首先先来一起探讨一下加速分页的问题大部分优化方案都是从内存中的页表开始的。这种设计对效率有着巨大的影响考虑一下，例如假设一条 1 字节的指令要把一个寄存器中的数据复制到另一个寄存器。在不分页的情况下这条指令只访问一次内存，即从内存取出指令有了分页机制后，会因为要访问页表而需要更多的内存访问由于执行速度通常被 CPU 从内存中取指令和数据的速度所限制，这样的话两次访问才能实现一次的访问效果，所以内存访问的性能会下降一半在这种情况下，根本不会采用分页机制

什么昰 1 字节的指令？我们以 8085 微处理器为例来说明一下在 8085 微处理中，一共有 3 种字节指令它们分别是 1-byte(1 字节)、2-byte(2 字节)、3-byte(3 字节)，我们分别来说一下

1-byte：1 芓节的操作数和操作码共同以 1 字节表示；操作数是内部寄存器并被编码到指令中；指令需要一个存储位置来将单个寄存器存储在存储位置中。没有操作数的指令也是 1-byte 指令

例如：MOV B,C 、LDAX B、NOP、HLT（这块不明白的读者可以自行查阅）

2-byte: 2 字节包括：第一个字节指定的操作码；第二个字节指定操作数；指令需要两个存储器位置才能存储在存储器中。

3-byte: 在 3 字节指令中第一个字节指定操作码；后面两个字节指定 16 位的地址；第二個字节保存低位地址；第三个字节保存 高位地址。指令需要三个存储器位置才能将单个字节存储在存储器中

大多数程序总是对少量页面進行多次访问，而不是对大量页面进行少量访问因此，只有很少的页面能够被再次访问而其他的页表项很少被访问。

基于这种设想提出了一种方案，即从硬件方面来解决这个问题为计算机设置一个小型的硬件设备，能够将虚拟地址直接映射到物理地址而不必再访問页表。这种设备被称为转换检测缓冲区(Translation Lookaside Buffer, TLB)有时又被称为 相联存储器(associate memory) 。

0
0
0

TLB 通常位于 MMU 中包含少量的表项，每个表项都记录了页面的相关信息除了虚拟页号外，其他表项都和页表是一一对应的

是不是你到现在还是有点不理解什么是 TLBTLB 其实就是一种内存缓存，用于减少访问内存所需要的时间它就是 MMU 的一部分，TLB 会将虚拟地址到物理地址的转换存储起来通常可以称为地址翻译缓存(address-translation cache)。TLB 通常位于 CPU 和 CPU 缓存之间它与 CPU 缓存是不同的缓存级别。下面我们来看一下 TLB

当一个 MMU 中的虚拟地址需要进行转换时硬件首先检查虚拟页号与 TLB 中所有表项进行并行匹配，判断虛拟页是否在 TLB 中如果找到了有效匹配项，并且要进行的访问操作没有违反保护位的话则将页框号直接从 TLB 中取出而不用再直接访问页表。如果虚拟页在 TLB 中但是违反了保护位的权限的话（比如只允许读但是是一个写指令）则会生成一个保护错误(protection

上面探讨的是虚拟地址在 TLB 中嘚情况，那么如果虚拟地址不再 TLB 中该怎么办如果 MMU 检测到没有有效的匹配项，就会进行正常的页表查找然后从 TLB 中逐出一个表项然后把从頁表中找到的项放在 TLB 中。当一个表项被从 TLB 中清除出将修改位复制到内存中页表项，除了访问位之外其他位保持不变。当页表项从页表裝入 TLB 中时所有的值都来自于内存。

直到现在我们假设每台电脑都有可以被硬件识别的页表，外加一个 TLB在这个设计中，TLB 管理和处理 TLB 错誤完全由硬件来完成仅仅当页面不在内存中时，才会发生操作系统的陷入(trap)

在以前，我们上面的假设通常是正确的但是，许多现代的 RISC 機器包括 SPARC、MIPS 和 HP PA，几乎所有的页面管理都是在软件中完成的

精简指令集计算机或 RISC 是一种计算机指令集，它使计算机的微处理器的每条指囹（CPI）周期比复杂指令集计算机（CISC）少

在这些计算机上TLB 条目由操作系统显示加载。当发生 TLB 访问丢失时不再是由 MMU 到页表中查找并取出需偠的页表项，而是生成一个 TLB 失效并将问题交给操作系统解决操作系统必须找到该页，把它从 TLB 中移除（移除页表中的一项）然后把新找箌的页放在 TLB 中，最后再执行先前出错的指令然而，所有这些操作都必须通过少量指令完成因为 TLB 丢失的发生率要比出错率高很多。

无论昰用硬件还是用软件来处理 TLB 失效常见的方式都是找到页表并执行索引操作以定位到将要访问的页面，在软件中进行搜索的问题是保存页表的页可能不在 TLB 中这将在处理过程中导致其他 TLB 错误。改善方法是可以在内存中的固定位置维护一个大的 TLB 表项的高速缓存来减少 TLB 失效通過首先检查软件的高速缓存，操作系统 能够有效的减少 TLB 失效问题

TLB 软件管理会有两种 TLB 失效问题，当一个页访问在内存中而不在 TLB 中时将产苼 软失效(soft miss)，那么此时要做的就是把页表更新到 TLB 中（我们上面探讨的过程）而不会产生磁盘 I/O，处理仅仅需要一些机器指令在几纳秒的时间內完成然而，当页本身不在内存中时将会产生硬失效(hard miss)，那么此时就需要从磁盘中进行页表提取硬失效的处理时间通常是软失效的百萬倍。在页表结构中查找映射的过程称为 页表遍历(page table walk)

上面的这两种情况都是理想情况下出现的现象，但是在实际应用过程中情况会更加复雜未命中的情况可能既不是硬失效又不是软失效。一些未命中可能更软或更硬（偷笑）比如，如果页表遍历的过程中没有找到所需要嘚页那么此时会出现三种情况：

• 所需的页面就在内存中，但是却没有记录在进程的页表中这种情况可能是由其他进程从磁盘掉入内存，这种情况只需要把页正确映射就可以了而不需要在从硬盘调入，这是一种软失效称为 次要缺页错误(minor page fault)。
• 基于上述情况如果需要从硬盤直接调入页面，这就是严重缺页错误(major page falut)
• 还有一种情况是，程序可能访问了一个非法地址根本无需向 TLB 中增加映射。此时操作系统会报告一个 段错误(segmentation fault) 来终止程序。只有第三种缺页属于程序错误其他缺页情况都会被硬件或操作系统以降低程序性能为代价来修复

还记得我们討论的是什么问题吗？（捂脸）可能讨论的太多你有所不知道了，我再提醒你一下上面加速分页过程讨论的是虚拟地址到物理地址的映射速度必须要快的问题，还有一个问题是 如果虚拟地址空间足够大那么页表也会足够大的问题，如何处理巨大的虚拟地址空间下面展开我们的讨论。

第一种方案是使用多级页表(multi)下面是一个例子

32 位的虚拟地址被划分为 10 位的 PT1 域，10 位的 PT2 域还有 12 位的 Offset 域。因为偏移量是 12 位所以页面大小是 4KB，公有 2^20 次方个页面

引入多级页表的原因是避免把全部页表一直保存在内存中。不需要的页表就不应该保留

多级页表是┅种分页方案，它由两个或多个层次的分页表组成也称为分层分页。级别1（level 1）页面表的条目是指向级别 2（level 2） 页面表的指针级别2页面表嘚条目是指向级别 3（level 3） 页面表的指针，依此类推最后一级页表存储的是实际的信息。

下面是一个二级页表的工作过程

在最左边是顶级页表它有 1024 个表项，对应于 10 位的 PT1 域当一个虚拟地址被送到 MMU 时，MMU 首先提取 PT1 域并把该值作为访问顶级页表的索引因为整个 4 GB （即 32 位）虚拟地址巳经按 4 KB 大小分块，所以顶级页表中的 1024 个表项的每一个都表示 4M 的块地址范围

由索引顶级页表得到的表项中含有二级页表的地址或页框号。頂级页表的表项 0 指向程序正文的页表表项 1 指向含有数据的页表，表项 1023 指向堆栈的页表其他的项（用阴影表示）表示没有使用。现在把 PT2 域作为访问选定的二级页表的索引以便找到虚拟页面的对应页框号。

针对分页层级结构中不断增加的替代方法是使用 倒排页表(inverted page tables)采用这種解决方案的有 PowerPC、UltraSPARC 和 Itanium。在这种设计中实际内存中的每个页框对应一个表项，而不是每个虚拟页面对应一个表项

虽然倒排页表节省了大量的空间，但是它也有自己的缺陷：那就是从虚拟地址到物理地址的转换会变得很困难当进程 n 访问虚拟页面 p 时，硬件不能再通过把 p 当作指向页表的一个索引来查找物理页而是必须搜索整个倒排表来查找某个表项。另外搜索必须对每一个内存访问操作都执行一次，而不昰在发生缺页中断时执行

解决这一问题的方式时使用 TLB。当发生 TLB 失效时需要用软件搜索整个倒排页表。一个可行的方式是建立一个散列表用虚拟地址来散列。当前所有内存中的具有相同散列值的虚拟页面被链接在一起如下图所示

如果散列表中的槽数与机器中物理页面數一样多，那么散列表的冲突链的长度将会是 1 个表项的长度这将会大大提高映射速度。一旦页框被找到新的（虚拟页号，物理页框号）就会被装在到 TLB 中

当发生缺页异常时，操作系统会选择一个页面进行换出从而为新进来的页面腾出空间如果要换出的页面在内存中已經被修改，那么必须将其写到磁盘中以使磁盘副本保持最新状态如果页面没有被修改过，并且磁盘中的副本也已经是最新的那么就不需要进行重写。那么就直接使用调入的页面覆盖需要移除的页面就可以了

当发生缺页中断时，虽然可以随机的选择一个页面进行置换泹是如果每次都选择一个不常用的页面会提升系统的性能。如果一个经常使用的页面被换出那么这个页面在短时间内又可能被重复使用，那么就可能会造成额外的性能开销在关于页面的主题上有很多页面置换算法(page replacement algorithms)，这些已经从理论上和实践上得到了证明

需要指出的是，页面置换问题在计算机的其他领域中也会出现例如，多数计算机把最近使用过的 32 字节或者 64 字节的存储块保存在一个或多个高速缓存中当缓存满的时候，一些块就被选择和移除这些块的移除除了花费时间较短外，这个问题同页面置换问题完全一样之所以花费时间较短，是因为丢掉的高速缓存可以从内存中获取而内存没有寻找磁道的时间也不存在旋转延迟。

第二个例子是 Web 服务器服务器会在内存中緩存一些经常使用到的 Web 页面。然而当缓存满了并且已经引用了新的页面，那么必须决定退出哪个 Web 页面在高速缓存中的 Web 页面不会被修改。因此磁盘中的 Web 页面经常是最新的同样的考虑也适用在虚拟内存中。在虚拟系统中内存中的页面可能会修改也可能不会修改。

下面我們就来探讨一下有哪些页面置换算法

最优的页面置换算法很容易描述但在实际情况下很难实现。它的工作流程如下：在缺页中断发生时这些页面之一将在下一条指令（包含该指令的页面）上被引用。其他页面则可能要到 10、100 或者 1000 条指令后才会被访问每个页面都可以用在該页首次被访问前所要执行的指令数作为标记。

最优化的页面算法表明应该标记最大的页面如果一个页面在 800 万条指令内不会被使用，另外一个页面在 600 万条指令内不会被使用则置换前一个页面，从而把需要调入这个页面而发生的缺页中断推迟计算机也像人类一样，会把鈈愿意做的事情尽可能的往后拖

这个算法最大的问题时无法实现。当缺页中断发生时操作系统无法知道各个页面的下一次将在什么时候被访问。这种算法在实际过程中根本不会使用

最近未使用页面置换算法

为了能够让操作系统收集页面使用信息，大部分使用虚拟地址嘚计算机都有两个状态位R 和 M，来和每个页面进行关联每当引用页面（读入或写入）时都设置 R，写入（即修改）页面时设置 M这些位包含在每个页表项中，就像下面所示

因为每次访问时都会更新这些位因此由硬件来设置它们非常重要。一旦某个位被设置为 1就会一直保歭 1 直到操作系统下次来修改此位。

如果硬件没有这些位那么可以使用操作系统的缺页中断和时钟中断机制来进行模拟。当启动一个进程時将其所有的页面都标记为不在内存；一旦访问任何一个页面就会引发一次缺页中断，此时操作系统就可以设置 R 位(在它的内部表中)修妀页表项使其指向正确的页面，并设置为 READ ONLY 模式然后重新启动引起缺页中断的指令。如果页面随后被修改就会发生另一个缺页异常。从洏允许操作系统设置 M 位并把页面的模式设置为 READ/WRITE

可以用 R 位和 M 位来构造一个简单的页面置换算法：当启动一个进程时，操作系统将其所有页媔的两个位都设置为 0R 位定期的被清零（在每个时钟中断）。用来将最近未引用的页面和已引用的页面分开

当出现缺页中断后，操作系統会检查所有的页面并根据它们的 R 位和 M 位将当前值分为四类：

• 第 0 类：没有引用 R，没有修改 M
• 第 1 类：没有引用 R已修改 M
• 第 2 类：引用 R ，没有修妀 M
• 第 3 类：已被访问 R已被修改 M

尽管看起来好像无法实现第一类页面，但是当第三类页面的 R 位被时钟中断清除时它们就会发生。时钟中断鈈会清除 M 位因为需要这个信息才能知道是否写回磁盘中。清除 R 但不清除 M 会导致出现一类页面

NRU(Not Recently Used) 算法从编号最小的非空类中随机删除一个頁面。此算法隐含的思想是在一个时钟内（约 20 ms）淘汰一个已修改但是没有被访问的页面要比一个大量引用的未修改页面好，NRU 的主要优点昰易于理解并且能够有效的实现

另一种开销较小的方式是使用 FIFO(First-In,First-Out) 算法，这种类型的数据结构也适用在页面置换算法中由操作系统维护一個所有在当前内存中的页面的链表，最早进入的放在表头最新进入的页面放在表尾。在发生缺页异常时会把头部的页移除并且把新的頁添加到表尾。

还记得缺页异常什么时候发生吗我们知道应用程序访问内存会进行虚拟地址到物理地址的映射，缺页异常就发生在虚拟哋址无法映射到物理地址的时候因为实际的物理地址要比虚拟地址小很多（参考上面的虚拟地址和物理地址映射图），所以缺页经常会發生

先进先出页面可能是最简单的页面替换算法了。在这种算法中操作系统会跟踪链表中内存中的所有页。下面我们举个例子看一下（这个算法我刚开始看的时候有点懵逼后来才看懂，我还是很菜）

• 初始化的时候没有任何页面，所以第一次的时候会检查页面 1 是否位於链表中没有在链表中，那么就是 MISS页面1 进入链表，链表的先进先出的方向如图所示
• 类似的，第二次会先检查页面 2 是否位于链表中沒有在链表中，那么页面 2 进入链表状态为 MISS，依次类推
• 我们来看第四次，此时的链表为 1 2 3第四次会检查页面 2 是否位于链表中，经过检索後发现 2 在链表中，那么状态就是 HIT并不会再进行入队和出队操作，第五次也是一样的
• 下面来看第六次，此时的链表还是 1 2 3因为之前没囿执行进入链表操作，页面 5 会首先进行检查发现链表中没有页面 5 ，则执行页面 5 的进入链表操作页面 2 执行出链表的操作，执行完成后的鏈表顺序为 2 3 5

第二次机会页面置换算法

我们上面学到的 FIFO 链表页面有个缺陷，那就是出链和入链并不会进行 check 检查这样就会容易把经常使用嘚页面置换出去，为了避免这一问题我们对该算法做一个简单的修改：我们检查最老页面的 R 位，如果是 0 那么这个页面就是最老的而且沒有被使用，那么这个页面就会被立刻换出如果 R 位是 1，那么就清除此位此页面会被放在链表的尾部，修改它的装入时间就像刚放进来嘚一样然后继续搜索。

这种算法叫做 第二次机会(second chance)算法就像下面这样，我们看到页面 A 到 H 保留在链表中并按到达内存的时间排序。

a）按照先进先出的方法排列的页面；b）在时刻 20 处发生缺页异常中断并且 A 的 R 位已经设置时的页面链表

假设缺页异常发生在时刻 20 处，这时最老的頁面是 A 它是在 0 时刻到达的。如果 A 的 R 位是 0那么它将被淘汰出内存，或者把它写回磁盘（如果它已经被修改过）或者只是简单的放弃（洳果它是未被修改过）。另一方面如果它的 R 位已经设置了，则将 A 放到链表的尾部并且重新设置装入时间为当前时刻（20 处）然后清除 R 位。然后从 B 页面开始继续搜索合适的页面

寻找第二次机会的是在最近的时钟间隔中未被访问过的页面。如果所有的页面都被访问过该算法就会被简化为单纯的 FIFO 算法。具体来说假设图 a 中所有页面都设置了 R 位。操作系统将页面依次移到链表末尾每次都在添加到末尾时清除 R 位。最后算法又会回到页面 A，此时的 R 位已经被清除那么页面 A 就会被执行出链处理，因此算法能够正常结束

即使上面提到的第二次页媔置换算法也是一种比较合理的算法，但它经常要在链表中移动页面既降低了效率，而且这种算法也不是必须的一种比较好的方式是紦所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面如下图所示

当缺页错误出现时，算法首先检查表针指向的頁面如果它的 R 位是 0 就淘汰该页面，并把新的页面插入到这个位置然后把表针向前移动一位；如果 R 位是 1 就清除 R 位并把表针前移一个位置。重复这个过程直到找到了一个 R 位为 0 的页面位置了解这个算法的工作方式，就明白为什么它被称为 时钟(clokc)算法了

最近最少使用页面置换算法

最近最少使用页面置换算法的一个解释会是下面这样：在前面几条指令中频繁使用的页面和可能在后面的几条指令中被使用。反过来說已经很久没有使用的页面有可能在未来一段时间内仍不会被使用。这个思想揭示了一个可以实现的算法：在缺页中断时置换未使用時间最长的页面。这个策略称为 LRU(Least Recently Used) 最近最少使用页面置换算法。

虽然 LRU 在理论上是可以实现的但是从长远看来代价比较高。为了完全实现 LRU会在内存中维护一个所有页面的链表，最频繁使用的页位于表头最近最少使用的页位于表尾。困难的是在每次内存引用时更新整个链表在链表中找到一个页面，删除它然后把它移动到表头是一个非常耗时的操作，即使使用硬件来实现也是一样的费时

然而，还有其怹方法可以通过硬件实现 LRU让我们首先考虑最简单的方式。这个方法要求硬件有一个 64 位的计数器它在每条指令执行完成后自动加 1，每个頁表必须有一个足够容纳这个计数器值的域在每次访问内存后，将当前的值保存到被访问页面的页表项中一旦发生缺页异常，操作系統就检查所有页表项中计数器的值找到值最小的一个页面，这个页面就是最少使用的页面

尽管上面的 LRU 算法在原则上是可以实现的，但昰很少有机器能够拥有那些特殊的硬件上面是硬件的实现方式，那么现在考虑要用软件来实现 LRU 一种可以实现的方案是 NFU(Not Frequently Used，最不常用)算法它需要一个软件计数器来和每个页面关联，初始化的时候是 0 在每个时钟中断时，操作系统会浏览内存中的所有页会将每个页面的 R 位（0 或 1）加到它的计数器上。这个计数器大体上跟踪了各个页面访问的频繁程度当缺页异常出现时，则置换计数器值最小的页面

NFU 最主要嘚问题是它不会忘记任何东西，想一下是不是这样例如，在一个多次（扫描）的编译器中在第一遍扫描中频繁使用的页面会在后续的掃描中也有较高的计数。事实上如果第一次扫描的执行时间恰好是各次扫描中最长的，那么后续遍历的页面的统计次数总会比第一次页媔的统计次数小结果是操作系统将置换有用的页面而不是不再使用的页面。

幸运的是只需要对 NFU 做一个简单的修改就可以让它模拟 LRU这个修改有两个步骤

• 首先，在 R 位被添加进来之前先把计数器右移一位；
• 第二步R 位被添加到最左边的位而不是最右边的位。

修改以后的算法称為 老化(aging) 算法下图解释了老化算法是如何工作的。

我们假设在第一个时钟周期内页面 0 - 5 的 R 位依次是 10，10，11，（也就是页面 0 是 1页面 1 是 0，頁面 2 是 1 这样类推）也就是说，在 0 个时钟周期到 1 个时钟周期之间0，24，5 都被引用了从而把它们的 R 位设置为 1，剩下的设置为 0 在相关的陸个计数器被右移之后 R 位被添加到 左侧 ，就像上图中的 a剩下的四列显示了接下来的四个时钟周期内的六个计数器变化。

CPU正在以某个频率湔进该频率的周期称为时钟滴答或时钟周期。一个 100Mhz 的处理器每秒将接收100,000,000个时钟滴答

当缺页异常出现时，将置换（就是移除）计数器值朂小的页面如果一个页面在前面 4 个时钟周期内都没有被访问过，那么它的计数器应该会有四个连续的 0 因此它的值肯定要比前面 3 个时钟周期内都没有被访问过的页面的计数器小。

这个算法与 LRU 算法有两个重要的区别：看一下上图中的 e第三列和第五列

它们在两个时钟周期内嘟没有被访问过，在此之前的时钟周期内都引用了两个页面根据 LRU 算法，如果需要置换的话那么应该在这两个页面中选择一个。那么问題来了我萌应该选择哪个？现在的问题是我们不知道时钟周期 1 到时钟周期 2 内它们中哪个页面是后被访问到的因为在每个时钟周期内只記录了一位，所以无法区分在一个时钟周期内哪个页面最早被引用哪个页面是最后被引用的。因此我们能做的就是置换页面3，因为页媔 3 在周期 0 - 1 内都没有被访问过而页面 5 却被引用过。

LRU 与老化之前的第 2 个区别是在老化期间，计数器具有有限数量的位（这个例子中是 8 位）这就限制了以往的访问记录。如果两个页面的计数器都是 0 那么我们可以随便选择一个进行置换。实际上有可能其中一个页面的访问佽数实在 9 个时钟周期以前，而另外一个页面是在 1000 个时钟周期之前但是我们却无法看到这些。在实际过程中如果时钟周期是 20 ms，8 位一般是夠用的所以我们经常拿 20 ms 来举例。

在最单纯的分页系统中刚启动进程时，在内存中并没有页面此时如果 CPU 尝试匹配第一条指令，就会得箌一个缺页异常使操作系统装入含有第一条指令的页面。其他的错误比如 全局变量和 堆栈 引起的缺页异常通常会紧接着发生一段时间鉯后，进程需要的大部分页面都在内存中了此时进程开始在较少的缺页异常环境中运行。这个策略称为 请求调页(demand paging)因为页面是根据需要被调入的，而不是预先调入的

在一个大的地址空间中系统的读所有的页面，将会造成很多缺页异常因此会导致没有足够的内存来容纳這些页面。不过幸运的是大部分进程不是这样工作的，它们都会以局部性方式(locality of reference) 来访问这意味着在执行的任何阶段，程序只引用其中的┅小部分

一个进程当前正在使用的页面的集合称为它的 工作集(working set)，如果整个工作集都在内存中那么进程在运行到下一运行阶段（例如，編译器的下一遍扫面）之前不会产生很多缺页中断。如果内存太小从而无法容纳整个工作集那么进程的运行过程中会产生大量的缺页Φ断，会导致运行速度也会变得缓慢因为通常只需要几纳秒就能执行一条指令，而通常需要十毫秒才能从磁盘上读入一个页面如果一個程序每 10 ms 只能执行一到两条指令，那么它将需要很长时间才能运行完如果只是执行几条指令就会产生中断，那么就称作这个程序产生了 顛簸(thrashing)

在多道程序的系统中，通常会把进程移到磁盘上（即从内存中移走所有的页面）这样可以让其他进程有机会占用 CPU 。有一个问题是当进程想要再次把之前调回磁盘的页面调回内存怎么办？从技术的角度上来讲并不需要做什么，此进程会一直产生缺页中断直到它的笁作集 被调回内存然后，每次装入一个进程需要 20、100 甚至 1000 次缺页中断速度显然太慢了，并且由于 CPU 需要几毫秒时间处理一个缺页中断因此由相当多的 CPU 时间也被浪费了。

因此不少分页系统中都会设法跟踪进程的工作集，确保这些工作集在进程运行时被调入内存这个方法叫做 工作集模式(working set model)。它被设计用来减少缺页中断的次数的在进程运行前首先装入工作集页面的这一个过程被称为 预先调页(prepaging)，工作集是随着時间来变化的

根据研究表明，大多数程序并不是均匀的访问地址空间的而访问往往是集中于一小部分页面。一次内存访问可能会取出┅条指令也可能会取出数据，或者是存储数据在任一时刻 t，都存在一个集合它包含所哟欧最近 k 次内存访问所访问过的页面。这个集匼 w(k,t) 就是工作集因为最近 k = 1次访问肯定会访问最近 k > 1 次访问所访问过的页面，所以 w(k,t) 是 k 的单调递减函数随着 k 的增大，w(k,t) 是不会无限变大的因为程序不可能访问比所能容纳页面数量上限还多的页面。

事实上大多数应用程序只会任意访问一小部分页面集合但是这个集合会随着时间洏缓慢变化，所以为什么一开始曲线会快速上升而 k 较大时上升缓慢为了实现工作集模型，操作系统必须跟踪哪些页面在工作集中一个進程从它开始执行到当前所实际使用的 CPU 时间总数通常称作 当前实际运行时间。进程的工作集可以被称为在过去的 t 秒实际运行时间中它所访問过的页面集合

下面来简单描述一下工作集的页面置换算法，基本思路就是找出一个不在工作集中的页面并淘汰它下面是一部分机器頁表

因为只有那些在内存中的页面才可以作为候选者被淘汰，所以该算法忽略了那些不在内存中的页面每个表项至少包含两条信息：上佽使用该页面的近似时间和 R（访问）位。空白的矩形表示该算法不需要其他字段例如页框数量、保护位、修改位。

算法的工作流程如下假设硬件要设置 R 和 M 位。同样的在每个时钟周期内，一个周期性的时钟中断会使软件清除 Referenced(引用)位在每个缺页异常，页表会被扫描以找絀一个合适的页面把它置换

随着每个页表项的处理，都需要检查 R 位如果 R 位是 1，那么就会将当前时间写入页表项的 上次使用时间域表礻的意思就是缺页异常发生时页面正在被使用。因为页面在当前时钟周期内被访问过那么它应该出现在工作集中而不是被删除（假设 t 是橫跨了多个时钟周期）。

如果 R 位是 0 那么在当前的时钟周期内这个页面没有被访问过，应该作为被删除的对象为了查看是否应该将其删除，会计算其使用期限（当前虚拟时间 - 上次使用时间）来用这个时间和 t 进行对比。如果使用期限大于 t那么这个页面就不再工作集中，洏使用新的页面来替换它然后继续扫描更新剩下的表项。

然而如果 R 位是 0 但是使用期限小于等于 t，那么此页应该在工作集中此时就会紦页面临时保存起来，但是会记生存时间最长（即上次使用时间的最小值）的页面如果扫描完整个页表却没有找到适合被置换的页面，吔就意味着所有的页面都在工作集中在这种情况下，如果找到了一个或者多个 R = 0 的页面就淘汰生存时间最长的页面。最坏的情况下是茬当前时钟周期内，所有的页面都被访问过了（也就是都有 R = 1）因此就随机选择一个页面淘汰，如果有的话最好选一个未被访问的页面吔就是干净的页面。

工作集时钟页面置换算法

当缺页异常发生后需要扫描整个页表才能确定被淘汰的页面，因此基本工作集算法还是比較浪费时间的一个对基本工作集算法的提升是基于时钟算法但是却使用工作集的信息，这种算法称为WSClock(工作集时钟)由于它的实现简单并苴具有高性能，因此在实践中被广泛应用

与时钟算法一样，所需的数据结构是一个以页框为元素的循环列表就像下面这样

最初的时候，该表是空的当装入第一个页面后，把它加载到该表中随着更多的页面的加入，它们形成一个环形结构每个表项包含来自基本工作集算法的上次使用时间，以及 R 位（已标明）和 M 位（未标明）

与时钟算法一样，在每个缺页异常时首先检查指针指向的页面。如果 R 位被昰设置为 1该页面在当前时钟周期内就被使用过，那么该页面就不适合被淘汰然后把该页面的 R 位置为 0，指针指向下一个页面并重复该算法。该事件序列化后的状态参见图 b

现在考虑指针指向的页面 R = 0 时会发生什么，参见图 c如果页面的使用期限大于 t 并且页面为被访问过，那么这个页面就不会在工作集中并且在磁盘上会有一个此页面的副本。申请重新调入一个新的页面并把新的页面放在其中，如图 d 所示另一方面，如果页面被修改过就不能重新申请页面，因为这个页面在磁盘上没有有效的副本为了避免由于调度写磁盘操作引起的进程切换，指针继续向前走算法继续对下一个页面进行操作。毕竟有可能存在一个老的，没有被修改过的页面可以立即使用

原则上来說，所有的页面都有可能因为磁盘I/O 在某个时钟周期内被调度为了降低磁盘阻塞，需要设置一个限制即最大只允许写回 n 个页面。一旦达箌该限制就不允许调度新的写操作。

那么就有个问题指针会绕一圈回到原点的，如果回到原点它的起始点会发生什么？这里有两种凊况：

在第一种情况中指针仅仅是不停的移动，寻找一个未被修改过的页面由于已经调度了一个或者多个写操作，最终会有某个写操莋完成它的页面会被标记为未修改。置换遇到的第一个未被修改过的页面这个页面不一定是第一个被调度写操作的页面，因为硬盘驱動程序为了优化性能可能会把写操作重排序

对于第二种情况，所有的页面都在工作集中否则将至少调度了一个写操作。由于缺乏额外嘚信息最简单的方法就是置换一个未被修改的页面来使用，扫描中需要记录未被修改的页面的位置如果不存在未被修改的页面，就选萣当前页面并把它写回磁盘

我们到现在已经研究了各种页面置换算法，现在我们来一个简单的总结算法的总结归纳如下

不可实现，但鈳以用作基准
NRU(最近未使用) 算法	和 LRU 算法很相似
有可能会抛弃重要的页面
比 FIFO 有较大的改善
LRU(最近最少)算法	比较优秀但是很难实现
NFU(最不经常食用)算法
近似 LRU 的高效算法

• 最优算法在当前页面中置换最后要访问的页面。不幸的是没有办法来判定哪个页面是最后一个要访问的，因此实际仩该算法不能使用然而，它可以作为衡量其他算法的标准

• NRU 算法根据 R 位和 M 位的状态将页面氛围四类。从编号最小的类别中随机选择一个頁面NRU 算法易于实现，但是性能不是很好存在更好的算法。

• FIFO 会跟踪页面加载进入内存中的顺序并把页面放入一个链表中。有可能删除存在时间最长但是还在使用的页面因此这个算法也不是一个很好的选择。

• 第二次机会算法是对 FIFO 的一个修改它会在删除页面之前检查这個页面是否仍在使用。如果页面正在使用就会进行保留。这个改进大大提高了性能

• 时钟 算法是第二次机会算法的另外一种实现形式，時钟算法和第二次算法的性能差不多但是会花费更少的时间来执行算法。

• LRU 算法是一个非常优秀的算法但是没有特殊的硬件(TLB)很难实现。洳果没有硬件就不能使用 LRU 算法。

• NFU 算法是一种近似于 LRU 的算法它的性能不是非常好。

• 老化 算法是一种更接近 LRU 算法的实现并且可以更好的實现，因此是一个很好的选择

• 最后两种算法都使用了工作集算法工作集算法提供了合理的性能开销，但是它的实现比较复杂WSClock 是另外一種变体，它不仅能够提供良好的性能而且可以高效地实现。

总之最好的算法是老化算法和WSClock算法。他们分别是基于 LRU 和工作集算法他们嘟具有良好的性能并且能够被有效的实现。还存在其他一些好的算法但实际上这两个可能是最重要的。