Paging and the Address-Translation Problem
Paging and the Address-Translation Problem
复制标题
DOI：
10.1145/3409964.3461814
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
M. A. Bender;A. Bhattacharjee;Alex Conway;Martín Farach-Colton;Rob Johnson;Sudarsun Kannan;William Kuszmaul;Nirjhar Mukherjee;Donald E. Porter;Guido Tagliavini;Janet Vorobyeva;Evan West
中科院分区：
文献类型：
--
作者：
M. A. Bender;A. Bhattacharjee;Alex Conway;Martín Farach-Colton;Rob Johnson;Sudarsun Kannan;William Kuszmaul;Nirjhar Mukherjee;Donald E. Porter;Guido Tagliavini;Janet Vorobyeva;Evan West
1985年由斯莱特（Sleator）和塔扬（Tarjan）提出的经典分页问题，将在随机存取存储器（RAM）中缓存页面以最小化输入输出（IO）的问题形式化。他们的在线表述忽略了地址转换的成本：程序通过虚拟地址引用数据，并且这些虚拟地址必须转换为RAM中的物理位置。尽管单个地址转换的成本比一次输入输出的成本要小得多，但每次内存访问都涉及地址转换，而输入输出可能并不频繁。在实际中，可以通过过度配置RAM来花钱避免分页；相比之下，地址转换实际上是不可避免的。因此，地址转换成本有时可能会超过分页成本，并且系统必须同时对两者进行优化。为了降低地址转换成本，所有现代中央处理器（CPU）都有转换后备缓冲器（TLB），它是常见地址转换的硬件缓存。使转换后备缓冲器有趣的是，单个转换后备缓冲器条目可能潜在地为许多地址编码地址转换。这通常是通过使用大页面来实现的，大页面将连续的虚拟地址范围转换为连续的物理地址范围。大页面以增加在RAM中保持连续性所需的输入输出为代价减少了转换后备缓冲器缺失。转换后备缓冲器缺失和输入输出之间的这种权衡表明经典分页问题并没有涵盖全部情况。本文介绍了地址转换问题，它将维护转换后备缓冲器、页表和随机存取存储器以最小化转换后备缓冲器缺失和输入输出的总成本的问题形式化。我们提出了一种算法，该算法在转换后备缓冲器缺失方面实现了大页面的优势，而在输入输出方面没有大页面的缺点。
The classical paging problem, introduced by Sleator and Tarjan in 1985, formalizes the problem of caching pages in RAM in order to minimize IOs. Their online formulation ignores the cost of address translation: programs refer to data via virtual addresses, and these must be translated into physical locations in RAM. Although the cost of an individual address translation is much smaller than that of an IO, every memory access involves an address translation, whereas IOs can be infrequent. In practice, one can spend money to avoid paging by over-provisioning RAM; in contrast, address translation is effectively unavoidable. Thus address-translation costs can sometimes dominate paging costs, and systems must simultaneously optimize both. To mitigate the cost of address translation, all modern CPUs have translation lookaside buffers (TLBs), which are hardware caches of common address translations. What makes TLBs interesting is that a single TLB entry can potentially encode the address translation for many addresses. This is typically achieved via the use of huge pages, which translate runs of contiguous virtual addresses to runs of contiguous physical addresses. Huge pages reduce TLB misses at the cost of increasing the IOs needed to maintain contiguity in RAM. This tradeoff between TLB misses and IOs suggests that the classical paging problem does not tell the full story. This paper introduces the Address-Translation Problem, which formalizes the problem of maintaining a TLB, a page table, and RAM in order to minimize the total cost of both TLB misses and IOs. We present an algorithm that achieves the benefits of huge pages for TLB misses without the downsides of huge pages for IOs.