一、页式存储
从这个小节开始，我们会介绍虚拟存储系统，这个小结当中我们会先学习什么是页式存储器。
我们之前说过，主存和 cache 之间，它们之间的数据传送是以块为单位的。
就是如果此时我访问到了主存的某一个地址单元，这个地址单元是包含在比如 3 号主存块里。基于局部性原理，我们可以把 3 号主存块调入到 cache 的某一个位置，用这样的方式来提升系统的整体性能。
（1）分页
与主存分块息息相关的一个概念叫做分页。什么叫分页？
我们写的一些程序还有一些APP，可能一个程序一个APP，它的大小是很大的。
比如我们之前提过一个微信可能它有一个 1GB这么大，如果你要把微信1GB的数据全部放入到内存，并且是要求连续存放的话，是不是就意味着你必须在主存（内存）里边找到连续的 1GB的空闲区间，才可以把微信所有的数据给调进去。
这种必须连续存放的限制，在很多时候会导致主存的利用率不高。
所以在实际应用当中，我们写的一个程序，它可能有很多的指令代码，还有各种各样的数据，包括数组变量之类的很多的信息组成。
比如程序总共 4 个 KB，为了让主存的利用率更高，我们一般来说会把一个程序分为一个一个大小相等的页面，英文就是 page 。
每一个页面的大小和我们主存的一个物理块的大小其实是相同的，也就是 4 KB 的程序会被我们分为四个页面，并且我们可以给每一个页面进行一个编号，如下图，0 号页， 1 号、 2 号、 3 号页面，每一个页面的大小都是 1 KB。
接下来我们可以把这些页面离散地放到主存当中，比如分别放到这些个位置。
（2）页式存储系统
所以什么是页式存储系统呢，就是说，我们会把一个程序或者更准确的说应该叫一个进程。
但是在计组这门课里，可能有同学还不太理解进程这个概念，所以我们可以先简单地把它理解为一个程序，这程序里边包含了很多代码，很多数据，看起来它总共有这么大，但是我们会把它分成一个一个大小相等的页面，然后把这些页面放到一个一个的主存块里边。
这样的话，我们就可以把一个很大的程序拆分成多个页面，离散地放到主存的不同区域，这样我们就可以让主存的空间利用率更高。
所以这儿提到的，把程序分为一个的页面，这个分页更多的是逻辑层面的一个划分，而主存和 cache 进行分块，更多的是物理层面的一个划分。
（3）几个重要概念
接下来我们看一下一个程序被拆分成若干个页面，放到不同的位置之后，这个程序应该怎么执行。
我们需要引入两个很重要的概念，一个叫做逻辑地址，又可以叫做虚地址，所谓虚地址，就是程序员视角看到的地址空间。与这个概念相对应的另一个概念叫物理地址，又叫实地址，就是实际在主存里边的真实的物理地址。
来看一下什么意思。
1.逻辑地址
刚才我们说程序被拆分成了 4 个大小相同的页面，这个分页的过程其实对我们普通的应用程序员来说是不可见的。给程序分页是操作系统在背后帮我们做的事情，每一个页面的数据会被离散地放到主存的各个地方。
那对于我们普通程序员来说，我们自己写了一个程序，我们肯定是能够知道最后程序打包出来。比如这个程序是.exe 这样的一个可执行文件，我们肯定能够知道我们自己的程序总共的大小是多大，比如4KB。
所以站在我们自己的视角来看，这整个程序它应该是 2 的 12 次方这么多个字节。
如果按字节编址，我们这一整个程序，它的各个字节的地址范围应该是 12 个全零一直到 12 个全1。因为 2 的 12 次方刚好可以用 12 个比特来表示。
所以这是我们应用程序员的视角所看到的一个地址空间。
既然这个程序是我们自己写的，我们自己是不是能够知道这个程序的每个位置存放的是什么东西？
比如我们可以知道在某一个地址所对应的存储单元这儿，存了一个变量x，在后面某一个位置，我们又存了一个变量y。我们假设变量x它所存放的逻辑地址是这样一个地址，下面这个是变量 y 的地址。 
既然我们知道每一个变量存放在什么地方，我们是不是可以写一系列的指令？
比如我们可以写这样的一条机器指令--取数指令。
我们在第一章说过，想要把变量 x 取到 ACC累加寄存器里边，取数指令的操作码（绿色部分)如上，后面的这串参数指明的是我们想要取的变量的地址。
当然，这个地方我们使用的是逻辑地址。也就是在这 4KB的程序里边，变量 x 它所存放的相对位置是在什么地方，我们指明的只是一个相对地址，这是我们视角看到的东西。
我们可以来分析一下变量x的逻辑地址它应该属于哪一个页面。
注意我们这儿说每一个页面的大小是 1KB， 1KB就是 2 的 10 次方这么多个字节。
所以对于十二比特的逻辑地址来说，我们可以用后面的十个比特来表示每一个页面的页内地址。因为 10 个比特刚好可以表示 2 的 10 次方个字节。
用前边的两个比特来表示逻辑地址它应该属于哪一个页面。
所以对于变量 x 来说，它前面的两个比特位是00，就说明变量 x 它应该是被划分在 0 号页面当中。
2.物理地址
通过上图大家可以看到， 0 号页面它应该是被放到了 2 号主存块当中，所以变量 x 它实际存放的物理地址，我们可以用 0 号页面它的主存块号拼接上变量 x 的页内地址，用这样的方式把 x 的逻辑地址转换成它实际存放的物理地址。
3.页表
所以如果采用这种页式存储，我们作为程序员，写的指令肯定只能指明我们想要读写的那些数据它所存放的一个逻辑地址，我们只能给出逻辑地址。
操作系统会负责把逻辑地址映射为与之对应的物理地址。这个地址转换的过程最重要的就是把逻辑页号映射为与之相对应的主存块号。
因为每一个逻辑页都是存放在一个对应的主存块里的，它们大小都是相同的。
为了记录这种逻辑页号到主存块号的映射关系，操作系统会建立一张所谓的页表，就是一个数据结构。
页表当中就记录了每一个逻辑页它存放在了哪一个主存块当中。
比如刚才我们访问的变量x，它的逻辑页号就是 0 号页。通过查页表就可以知道，逻辑页号应该是存放在主存块号为 2 这个位置。
我们再把主存块号和页内地址进行一个拼接，就可以得到 x 变量的一个最终的物理地址。 
所以页表是一个对于操作系统来说很重要的数据结构。
因为CPU在执行任何一条机器指令的时候，所有的机器指令所指明的这些变量存放的地址，只是指明了一个逻辑地址。在这条指令运行的过程当中，必须把逻辑地址映射为与之相对应的物理地址。
这就需要用到页表，通过查询页表就可以知道每一个逻辑页面存放在哪一个主存块当中。
这儿值得一提的是，页表相关的这些数据是存放在主存里边的，所以CPU在进行地址转换的时候，需要查询页表，就意味着CPU 需要进行一次访存操作。
另一点需要补充的是，我们的页表是一行一行的信息组成的，页表当中的一行，可以称为一个页表项。每一个页表项就对应了某一个逻辑页号和主存块号之间的一对映射关系。
二、地址变换过程
如果操作系统采用的是这种页式存储的策略，当CPU 执行一些指令的时候，这些指令里边肯定会指明当前要访问的是哪一个逻辑地址。
逻辑地址可以被拆分为逻辑页号，还有页内地址这样的两个部分。
页内地址总共占多少个比特位，这一点主要是看每一个页面是多大。
比如刚才那个例子当中，每一个页面的大小是 1 KB，也就是 2 的 10 次方个字节，那么页内地址就需要用 10 个比特来表示。
而如果一个页面的大小，比如是 4KB，也就是 2 的 12 次方这么多个字节，在这种情况下，页内地址应该用 12 个比特来表示。
对于刚才我们这个例子来说，页内地址只有 10 个比特。
<1> 第一步 CPU 会把指令里边指明的逻辑地址（00 1000000011）把它拆分为逻辑页号（00）和页内地址（1000000011）这样的两个部分。
<2>接下来， CPU 里边还会有一个很重要的寄存器，叫做页表基址寄存器。
该寄存器指明了页表被存放在了主存的哪一个地址。
比如这个页表基地址，假如是1058这样的一个值。这就意味着我们当前正在运行的程序，它所对应的页表是从 1058 号主存单元开始存储的。
每一个页表项，也这儿的一行大小都是相同的，比如每一行占 4 个字节。
这就意味着从 1058 号主存单元开始，往后取 4 个字节的数据就是我们的第一个页表项，也指明了 0 号逻辑页面它存储在什么位置。
如果从这个地址再往后找 4 个字节，是不是就到了下一个页表项？也就是 1 号逻辑页面存放在什么位置。
所以，由于我们每一个页表项的大小都是相同的，因此只要指明了页表它存放的起始地址，CPU就可以根据逻辑页号，再结合基地址，可以立即找到任何一个逻辑页号所对应的页表项是在什么地方，然后直接读出想要找的页表项就可以。
对于刚才我们所说的这个例子，我们要找的是 0 号逻辑页， 0 号逻辑页是存放在主存块号为 2 的位置，也就是说，最终我们查找到的是第一个页表项。
<3> 接下来CPU会把主存块号 2 拼接上刚才拆出来的页内地址，把这两段进行一个拼接，就可以得到最终的物理地址，也就是变量 x 它所存放的物理地址。
<4> 得到物理地址之后，接下来是不是只需要访问主存的这个物理地址就可以了？
结合我们之前的学习，当要访问主存的某一个地址的时候，无论是读操作还是写操作，CPU 都会优先去 cache 里边去查找， cache 当中此时有没有保存我们想要访问的这个主存块的副本数据。
如果在 cache 当中能够找到，会直接从 cache 里边读取或者写入相应的数据。而如果 cache 未命中就是没有找到，CPU 才会去主存里边访问相应的地址单元。
所以主存里边各个块的内容，它在 cache 里边有可能是会有一个副本数据的，因为这样可以保证我们在最终访问物理地址的时候速度会更快。
三、优化
（1）分析
现在我们把刚才的思想给它发扬光大一下。
刚才我们说过，页表的这些数据是存放在主存里边的。也就是当 CPU要查页表的时候，其实是需要进行一次访存操作。
之前我们说过，程序的运行是有很强的局部性的，也就是此时我们访问的变量x，它属于 0 号逻辑页面。
那么根据局部性原理，我们可以知道，接下来的一段时间内，我们也很有可能会继续访问 0 号逻辑页面。这是不是意味着接下来在执行其他指令的时候，如果其他的指令也需要访问 0 号逻辑页面。那么CPU 在进行地址转换的时候，它每一次都会去主存里边查找页表，这显然是很低效的。
所以这个问题我们可以利用之前的思路把它进行一个优化。
如果此时我们访问了 0 号逻辑页面，这也就意味着我们在地址转换的时候，我们会使用到 0 号逻辑页面所对应的页表项。
而根据局部性原理可以知道，在接下来一段时间内，我们很有可能会频繁地访问到 0 号逻辑页面。
我们是不是可以把 0 号逻辑页面所对应的页表项，把它复制一份放到一个更高速的存储器当中？
就有点类似于把某一个主存块放到一个更高速的 cache 当中，我们这也可以把某一个页表项把它放到一个更高速的存储器里边。
这样当我们接下来再进行逻辑页号到主存块号的转换过程当中，就可以使地址转换的速度更快，所以基于思想，我们引入一个类似于 cache 的硬件机构，叫做快表，缩写叫TLB。
（2）快表
CPU 对快表的查询速度是非常快的。
引入了快表之后，我们在主存里边存储的完整的页表信息，可以把它称为慢表。
慢和快是一个相对的概念。
来看一下引入快表机构之后，地址变换的过程是什么样的。
<1> 首先，CPU要执行一条指令，指令当中会指明此次要访问的逻辑地址是什么。
逻辑地址可以被拆分成逻辑页号还有页内地址这样的两个部分。
<2> 引入了快表之后， CPU 做的事情是，首先会在快表当中尝试着找到逻辑页号所对应的页表项的副本。
如果能在快表当中找到，是不是花的时间可以更少？
但是刚开始块表是空的，所以查块表的操作是没有命中的。
如果在快表当中找不到00所对应的页表项，就是快表没有命中， CPU 才会去主存里边查询慢表。
现在查询慢表虽然耗费了一些时间，但是终归我们能够找到 0 号逻辑页面它所存储的主存块号是多少。
把主存块号拼上页内地址，就可以得到最终的物理地址。
基于局部性原理，我们现在访问了 0 号逻辑页之后，接下来也很有可能会频繁地访问到 0 号逻辑页。
为了加快地址转换的速度，所以我们可以把这个页表项的数据放到更快的快表当中。
接下来的指令当中，如果我们还继续访问了 0 号逻辑页面， CPU 可以直接在快表里边找到 0 号逻辑页它所存储的主存块号。
这样的话， CPU 就可以用很快的速度直接确定 0 号逻辑页面它的主存块号是多少。然后直接用主存块号拼接上页内地址，就可以得到最终的物理地址。
所以这就是快表的作用。 
（3）补充
1.快表和Cache
第一次学习的同学很容易把快表和 cache 相混淆，但其实它们俩的作用是很不一样的。
cache 里边存储的其实是某一些主存块的数据的副本，是一整块往 cache 里边调的。
而快表里边存储的是慢表的某一些页表项的副本，每个页表项很小，有可能一个页表项只有 4 个字节。而之前我们说过，每一个主存块，它的大小还是比较大的，有可能有 1KB。
引入块表是为了让我们从逻辑地址到物理地址的转变速度更快，可以减少一次访存。这是块表的作用，加快地址变换的速度；而 cache 的作用是，当我们确定了最终想要访问的物理地址之后，对物理地址的访问有可能会更快。
只要 cache 里边存在物理地址所对应的主存块的一个数据副本，我们就可以直接访问 cache 里的数据，而不需要去访问主存。
快表和 cache 它们起作用的阶段也不一样。
快表是在地址变换的过程当中起到了加速的作用，而 cache 是在最终得到的地址，访问这些地址的时候起到了加速的作用。
2.快表
🤔为什么 CPU查快表比查询慢表要快得多？
①首先第一个原因，快表采用了 SRAM，主存采用了 DRAM， SRAM 的读写速度要比 DRAM 更快。
②另外，在电路设计方面，快表是一种典型的相联存储器。
不知道大家对这个概念还有没有印象，应该是我们在第三章的第一个小节里边提到的概念，所谓的相联存储器就是CPU可以根据内容来寻访。
对于普通的主存来说， CPU 寻访某一个数据是根据地址信息去寻访的。而对于相联存储器来说， CPU 可以根据标记的实际内容，快速地通过硬件电路去找到在快表当中有没有与标记相对应的数据。
所以这些特性导致了快表的查找速度非常快。
按照之前的经验，快表它的速度很快，是不是意味着它成本很高，设计起来很复杂？这也就意味着快表当中不可能保存程序的整个页表的信息，它只可能保存页表的某一小部分的信息。
这一点和 cache 与主存的关系是很类似的。
所以在实际应用当中，快表很容易被存满。 快表的所有这些表象都被存满之后，是不是也会遇到所谓的替换问题。
就有点类似于cache 里边只能存储几个块的数据， cache 存满了之后，是不是我们要选择把哪些块替换出去，把哪些新的块给替换进来？对于快表来说也是一样。只不过快表它替换的对象是一个一个的表项，而不是一块一块的数据。
所有的这些东西都是可以串起来的。
四、总结回顾
接下来，我们对小节的内容进行一个总结与回顾。
对于 CPU 来说， CPU 的作用就是执行一条一条的指令，这些机器指令里边会指明此次 CPU 需要访问的是哪一个主存单元，哪一个主存地址。
指令里边所携带的地址其实都是逻辑地址。
如果采用页式存储管理，一个逻辑地址可以被拆分为页号和页内地址这样的两个部分。
在引入了快表机构之后， CPU 会优先地使用页号去快表当中查找有没有和页号相对应的表项。如果快表能够命中，就可以直接根据快表当中保存的表项的信息，知道逻辑页号它被存放在了哪个主存块。
接下来， CPU 只需要把主存块和最初的页内地址进行一个拼接，就可以得到最终需要访问的物理地址。
这是块表命中的情况。
如果快表没有命中，那么就意味着 CPU 必须进行一次访存操作。
去主存里边查慢表，根据逻辑页号就可以找到与之相对应的页表项。通过慢表里边保存的页表项，就可以知道这个逻辑页面它存放在了哪个主存块。
接下来同样的，我们只需要用主存块和页内地址进行一个拼接，就可以得到最终要访问的物理地址是哪。
除了得到要访问的物理地址之外， CPU 还会把此次查找的页表项的内容把它复制一份到快表当中。这样就可以保证接下来如果继续访问逻辑页号，下一次进行地址转换的时候， TLB 快表就可以命中，这样就可以加快我们地址转换的速度。
这就是地址转换的过程。
在得到了我们最终想要访问的物理地址之后， CPU 并不会直接去访问主存的物理地址，而是会优先去 cache 当中尝试着找一找能不能找到所对应的主存块的一个副本数据。
如果能够找到，也就是 cache 命中， CPU就可以直接从 cache 当中访问想要访问的数据。无论是读还是写。访问 cache 就意味着速度会很快。
而如果 cache 没有命中，就意味着此时我们要访问的物理地址，它所对应的主存块是没有被放到 cache 里边的。这种情况下， CPU 就不得不去主存里边去访问想要找的地址数据。
除了访问这些地址之外，还会把这个地址它所对应的主存块给调入cache，这样如果接下来我们继续访问这个主存块，就可以保证 cache 是能够命中的，能够使得我们访存的速度加快。
所以这就是访问一个逻辑地址的整个过程。
引入了快表之后，快表能够加快我们从逻辑地址到物理地址的转换速度。
得到了最终想要访问的物理地址之后， cache 又加快了CPU对物理地址的访问速度。
所以大家再体会一下快表和 cache 的作用。
再次强调，快表里边存储的是某些页表项的副本，而 cache 里边存储的是某一些主存块的副本。
另外，第一次接触页式存储的同学，还需要把逻辑地址还有什么页号、页内地址、虚地址、实地址这些个概念把它给过一遍。
