|
对于多线程系统的程序员来说，虚拟内存和缓存接口的话题是很重要的。硬件实现虚拟内存寻址的方式对代码的性能有非常大的影响。
本文是关于硬件结构对软件性能产生的影响讨论系列专栏的第二篇。上个月，我们考察了两种关于缓存结构的协定：写贯穿与写回相对比，以及直接映像和相联映像对比。
虚拟内存允许程序使用比处理器地址总线实际位数更大的寻址空间。一种处理器有16位地址总线（例如，z80），可以直接寻址两个16位的内存地址空间。典型的应用是相同的处理器可以通过虚拟内存系统访问更大的地址空间，比如232M或者2000M比特。
很明显，此寻址空间比大部分应用的需要要大得多。尽管如此，使用这个更大虚拟寻址空间可以得到一些很好的应用。通常实现大的寻址空间的方法是分段，它通过将逻辑地址转换为线性地址加上一个段偏移量的方式来实现。这里，我们将介绍一种更成熟的虚拟内存管理机制——分页。
分页的作用是将线性地址空间转换到物理地址空间。某些系统不使用分页但是使用分段，在分段的机制下线性地址通过把段的偏移量和逻辑地址相加得到了实际的物理地址。还有一些系统使用分页而不使用分段，在这种情况下线性地址与程序产生逻辑地址的原理是相同的。
无论是使用分段还是线性寻址，其原理和逻辑寻址是相同的，分页通过线性地址和偏移量相加将线性地址转化为物理地址。偏移量可以在页表入口中查到，而页表入口可以通过索引偏移量从页表目录中查到。同时，页表目录的基地址可以通过一个片内的控制寄存器直接寻址，我们称之为根寄存器。
偏移的层次个看起来似乎让人看不明白，所以我们从另一个角度来分析一下。图1显示了一个典型的分页系统（80386使用这样的偏移）
在分页模式下８０３８６产生地址的步骤
程序产生32位的线性地址可以分为三部分：页目录索引，页表索引和页偏移量。32位线性地址的最高10位为页目录索引，其与根寄存器的页目录项索引的基址相加。页表目录项包含页表的地址。然后线性地址的下10位和页表地址相加，可以在表中找到需要的页索引。最后，线性地址的后12位和页表相加即可得到实际的物理空间。
使用三层的分层机制（根寄存器、页表目录以及页表）保证了编程时的灵活性。多线程系统为不同的进程在根寄存器加载不同的值，以提供不同的任务之间的隔离。同时，因为页表目录可以指向不同的页表，几个进程可以为了实现保护功能共同使用公共空间的页表，譬如ROM。页表本身允许程序在不同物理地址空间存储和访问连续的数据和指令。
可是这种过程是很复杂的，它涉及目录中独立的查表以及在页表中找到正确的物理地址。如果页目录和所有的页表都保存在主存储中，处理时需要使用两个独立的内存读取以找到一个字节。为了减少频繁的目录和页表查表，一些处理器使用了转换旁视缓冲存储器（TLB）。一个TLB是一个缓存，它通常是完全相关联的，用于保存当前激活的页表目录。例如，80386使用一个32位的字完全相关联的TLB。
当在片上TLB中被发现一个页表入口（TLB命中），页表查询就不需要以前的转换时间。当TLB丢失发生时，处理器必须在页表目录中再进行一次查询，计算索引页表的偏移量，查询页表的入口，并通过线性地址和页表入口相加得到物理地址。
然后，这个处理器用新的页表入口地址替换旧的，假设这个页很快的又被访问，再继续持续这样的工作方式。所有的处理（三次加法操作和两次存储器访问以找到物理地址）明显地导致某些性能的退化。
在通常的操作中，TLB可以有98%的命中率。命中率在执行深度嵌套的任务时会有明显的降低。这是因为处理器在判断从TLB中丢弃某个页表入口地址时会有丢失。
缓存机制
两个主要的缓存替代机制，包括最少使用频率算法(LFU)和最近最少使用算法（LRU）。从程序员的角度来看，采用LFU算法是更加合理的。例如，对在一些很少使用的页中的偶然出现系统变量，使用LFU替代算法中，其缓存保存的时间是比较短暂的。
然而很不幸的是，LFU算法很难使用硬件实现。所有在小型超级计算机等级以下的计算机存储系统目前都使用LRU替代算法，对指令缓存、数据缓存和TLB进行替换，这对存储系统的容量提出了一些严格的限制。
ｔｒａｓｈｉｎｇ的出现
让我们考察已有32个访问入口地址时的情况，它是全相关的基于LRU替换算法的TLB，当第33次访问需要寻址不同的页时，将导致第一次访问的页从缓存中丢失。这种情况看起来像是一个低TLB丢失频率，但是考虑一下基于时间片的多线程系统，当其正在运行六个进程时，每个进程都使用不同的页面用于指令和数据保存（一个明智的编程方法）。在这种情况下，在任何给定的时间内最少12个页面都是激活的。如果每个进程在每个时间片内都使用双倍嵌套处理方法（或者在三个页中跳转），这样就会有36个激活的页，比在TLB中允许的存在页数还要多四个。
现在观察操作系统通过依次的6个时间片进行循环时会发生什么情况。当处理器到达第6个时间片的时候，将依次访问30个不同的页。在第6个时间片截止的时候，操作系统将访问36个不同的页，并且缓存管理机制将从TLB中丢弃此循环最开始进入的4个页的访问地址。这4个页是最近最少使用的（它们是在6个时间片的第1个）。
当操作系统循环再次到第1个时间片的时候，TLB需要重新使用刚才丢弃的页表。在装载完丢弃页的访问地址的时候，操作系统又丢弃下6个页的访问地址，我们可以考虑一下，这次丢弃的地址是第2个时间片所需要的地址。当处理器继续其畅快的工作时，它将继续丢失后面的时间片的页表入口地址。
这种情况叫做页表trashing， 对TLB原应提供的性能的提高具有很强的破坏性。随着持续的破坏，整个程序的速度看起来是比优化的后的程序最少67%，因为处理器需要在每一个循环中查表得到3个存储地址而不是一个。这样在性能上大幅度地的降低足以引起大家的关注。
数据缓存的复杂性
如果系统中还存在一个数据cache时，Trashing会对计算机的性能产生更大的破坏。这是因为数据cache的处理机制无法区分两个数据页表的不同。结果是，无论当数据页表何时出现在TLB，将被载入数据缓存。当每一个页表和页表目录出现的时候，旧的数据cache存储的数据将会丢失，并通过查表得到并装载新的数据。因为数据cache通常采用LRU替换算法，所以数据缓存中共享的数据页表是不能被保存的，除非缓存是组相关的。这种情况很少发生，因为大部分的数据缓存系统都有两种组相关的方式。
另外，数据缓存中页表的丢失也不总会造成问题。当操作系统开始一个新的任务事发生TLB丢失，数据缓存丢失的数据属于旧的任务，此时缓存的更新不会对性能有任何影响。
页表trashing同样也可以引起数据trashing。例如，当处理一块连续的数据时引发了一个很少使用的进程。一组缓存装载页表目录；另一组缓存装载页表索引。如果还有另外一组缓存用于装载当前的数据，它只能在下一步进行（而不是保存页表目录或者页表）因为它是最近最少使用的。所有这些将导致数据缓存性能的降低，即使此进程并不访问任何数据。
硬件结构对代码性能的影响是不能忽视的，特别是在分页虚拟存储系统中。指令缓存、数据缓存和TLB的类型和大小对一个看起来似乎很简单的应用程序的影响有着极大的不同，特别是在对任务的环境下。
按照一些简单的规则可以帮助避免一些不必要trashing。例如可以通过TLB丢失使数据缓存性能降低减到最小，甚至当没有上下文切换时页表查询的失败。经常使用宏，长时间不使用的数据应该声明为绝对的而不是相对的。
还有一些其他的避免trashing的方法：尽可能避免程序中的嵌套调用，使同时进行的任务数目最小化，除非万不得已不要使用超过页的大小的跳转。
下次我们将讨论一些特殊的技术譬如流水线指令和数据来避免trashing。我们还将解释为什么使用交叉存储块会导致不同数据和代码结构在性能上的不同。
|
