1700495292
1700495293
任何曾经使用过图书馆的人都可以清楚地了解分级存储器体系背后的基本思想。例如，如果你正在为写论文收集资料，就有可能需要多次参考一些图书。你不可能每次都跑到图书馆，而是把相关书籍借回家，放到你的书桌上。这样，查询起来就方便得多。
1700495294
1700495295
在1962年超级计算机阿特拉斯在英国曼彻斯特问世以前，计算领域的这种“分级存储”概念一直停留在理论层面。从外形看，阿特拉斯的主存储器并不像蜡筒留声机，而像一个很大的鼓，它通过旋转来读写信息。但是，阿特拉斯还有一个用极化磁体制成的体积较小、速度更快的“工作”存储器。数据可以从鼓中读取到磁体上，然后在那里轻松地加以处理，最后处理结果将被写回到主存储器的大鼓上。
1700495296
1700495297
阿特拉斯问世之后不久，剑桥大学数学家莫里斯·威尔克斯意识到，这种体积较小、速度较快的存储器不仅可以为我们处理数据、将处理好的数据存回主存储器提供了一个非常方便的场所，还可以用来有意地保留稍后可能需要使用的信息片段，为后期类似的需要做好准备，从而极大地加速机器的操作。如果所需要的数据仍然保留在工作存储器中，就不必再到主存储器中装载这些数据了。威尔克斯认为，这种体积较小的存储器“可以自动收集并保存来自速度较慢的主内存的数据，为后期使用做好准备，从而免除了再次访问主存储器带来的麻烦”。
1700495298
1700495299
当然，关键是要管理好那个体积小、速度快、价值大的存储器，以保证我们可以在里面找到需要的数据。我们继续以图书馆来打比方。如果你去一次图书馆就可以找到所有需要的图书，然后在家里埋头钻研，其效果可以与你把图书馆中所有的图书都搬到案头的做法相媲美。去图书馆的次数越多，效率就越低下，而办公桌的实际利用价值就越小。
1700495300
1700495301
20世纪60年代末，威尔克斯的提议在IBM 360/85超级计算机中得以实现，人们称之为“缓存”。从那以后，计算机科学中到处都有了缓存的身影。将频繁调用的信息片段保存以备后用的效果非常好，因此这个做法在计算的各个方面都得到了应用。处理器有缓存，硬盘有缓存，操作系统有缓存，Web浏览器有缓存，连向这些浏览器提供内容的服务器也有缓存，因此我们可以立刻看到数百万人观看的猫骑真空吸尘器的视频……但是，我们的步子迈得有点儿超前了。
1700495302
1700495303
根据人们的描述，计算机在过去50多年里逐年呈指数增长，这为“摩尔定律”精准的预测了下一个注脚。1975年，英特尔的戈登·摩尔提出“摩尔定律”，称中央处理器的晶体管数量每两年翻一番。但是，存储器的性能没有按这个速度提升，这意味着访问存储器时的时间成本也在呈指数增长。例如，你写论文的速度越快，每次去图书馆带给效率的负面影响就越大。同样，如果工厂每年将制造速度提升一倍，但是零部件从海外运送到工厂的速度仍然那么慢，总数也没变，这只能意味着该工厂停工的时间将增加一倍。在一段时间内，摩尔定律似乎没有任何实际意义，它只不过预测出处理器的速度将越来越快，闲置的时间会越来越多。在20世纪90年代，人们开始把这种现象称作“内存墙”。
1700495304
1700495305
为了避免一头撞上这堵墙，计算机科学至今为止采取的最有效措施就是缓存、缓存的缓存以及缓存的缓存的缓存，如此而已。现代消费者购买的笔记本电脑、平板电脑和智能手机都有一个6层的分级存储器体系。今天，存储器的智能管理对计算机科学的重要性已经达到了史无前例的高度。
1700495306
1700495307
一提到缓存（或者具有类似功能的壁橱），我们大脑中闪现的第一个问题就是：如果它们装满了东西，我们该怎么办？下面，我们就从这个问题开始谈起。
1700495308
1700495309
1700495310
1700495311
1700495313
算法之美：指导工作与生活的算法 缓存清理与未卜先知
1700495314
1700495315
夏洛克·福尔摩斯
1700495316
1700495317
相信我，总有一天，当你增加新知识的时候，就会把以前熟知的东西忘了。所以最要紧的是，不要让一些无用的知识把有用的挤出去。
1700495318
1700495319
缓存满了后，如果你想继续在缓存中存储其他东西，就必然需要腾出一些空间。在计算机科学中，在缓存中腾出空间的过程被称为“缓存替换”或“缓存清理”。威尔克斯指出：“由于缓存的容量比主存小好几倍，不能无限度地把数据保存在其中，因此我们必须在系统中植入一个算法，逐步覆盖缓存中的数据。”这些算法被称为“替换策略”或“清理策略”，或者简单地称为缓存算法。
1700495320
1700495321
我们知道，IBM在20世纪60年代率先推动缓存系统的部署应用。不出意料，它也是早期缓存算法开创性研究的发源地，也许他们取得的任何一项成果都没有拉斯洛·贝莱迪的算法重要。1928年，贝莱迪出生于匈牙利，大学期间学的是机械工程专业。在1956年匈牙利革命期间，身无分文的他逃到了德国，随身携带的书包里只装有“一件内衣和毕业论文”。后来，他又离开德国，来到法国，并于1961年移民到美国。这一次，他带着妻子，“襁褓中的孩子，口袋里装着1000美元。除此以外，就别无他物了”。似乎在他进入IBM研究缓存清理之前，他就已经深谙此道，知道哪些东西该留下来，哪些东西可以抛弃。
1700495322
1700495323
贝莱迪于1966年发表的那篇缓存算法论文是随后15年里被引用最多的计算机科学研究成果。这篇论文解释道，缓存管理的目标是尽可能减少“页面错误”或“缓存缺失”。所谓缓存缺失，是指无法在缓存中找到所需数据，因此只能到较慢的主存中查找的现象。贝莱迪在文中写道，从本质上讲，最优缓存清理策略就是在缓存已满时，将未来最长时间内不会再次使用的数据从缓存中清理出去。
1700495324
1700495325
当然，要确切地知道什么时候会再次需要某些数据，并不像说起来那么容易。
1700495326
1700495327
今天，为了表示敬意，人们把那个无所不知、有先见之明，而且可以在分析未来情况基础上执行最优缓存策略的那个假想算法称作贝莱迪算法。该算法是被计算机科学家称为“千里眼”算法的一个实例，一个可以从未来数据中获取信息的算法。这个概念其实并不像听起来那么疯狂（在某些情况下，系统可能会对未来产生一种期望），但是一般来说，未卜先知是很难实现的，因此软件工程师在实践中试图使用贝莱迪算法时，就会开玩笑说他们遭遇了“实施难题”。因此，我们面临的挑战是找到一种接近于未卜先知的算法，当我们被当前现状遮住双眼的时候，可以借助这种算法看清楚未来的情况。
1700495328
1700495329
我们可以尝试随机清理算法，将新数据添加到缓存中，并随机覆盖旧数据。随机清理是早期高速缓存理论得出的一个令人吃惊的结果，虽然远非完美，但是效果也还不错。这也可能是一种巧合，因为只要有一个缓存，无论你如何维护，都可以提升系统的效率。不管怎么说，你经常使用的内容通常还会很快回到缓存中。另一种简单的策略叫作先进先出（FIFO）。这种算法总是清理或覆盖在缓存中保存时间最久的内容（与玛莎·斯图尔特问的“我已拥有它多长时间了”这个问题有异曲同工之妙）。第三种方法是最近最少使用（LRU），即将闲置不用时间最长的内容清理掉（与之相对应的斯图尔特的问题是“上次穿它或使用它是什么时候的事”）。
1700495330
1700495331
事实证明，斯图尔特强调的这两点暗示了两种截然不同的策略，而且她的一条建议显然比另一条更有效果。贝莱迪在若干情形下对随机清理、先进先出和最近最少使用的几个变体进行了比较，结果发现最近最少使用法始终表现出最接近未卜先知的效果。最近最少使用法的高效性得益于计算机科学家所谓的“时间局部性”：如果一个程序曾经调用过某个信息，那么在不久的将来它可能会再次调用这个信息。计算机解决问题的方式（例如，执行一个循环，使一系列相关的读和写可以快速完成）是造成时间局部性的一个原因，而人解决问题的方式是另外一个原因。在使用电脑时，你可能会在电子邮件、网页浏览器和文字处理器之间来回切换。你最近访问过这些程序的这个事实就是一个线索，表明你可能会再次访问该程序。在同等条件下，如果某个程序处于闲置状态的时间较长，就表明你在未来一段时间内应该也不会调用该程序。
1700495332
1700495333
事实上，这一原则甚至隐含于计算机向用户展示的界面中。电脑屏幕上的窗口有所谓的“Z轴顺序”，即决定程序相互叠加次序的模拟深度。最近最少使用的程序处于底部。前火狐浏览器的创意主管阿扎·拉斯金说：“使用现代浏览器（电脑）在很多时候就相当于从事数字版的文书工作。”与“文书工作”的相似性淋漓尽致地体现在微软系统Windows和苹果系统Mac OS任务切换界面中：当你按下Alt+Tab或Command+Tab组合键时，就会看到，你最近使用过的程序按你使用的时间先后逆向排列。
1700495334
1700495335
研究缓存清理策略的相关文献已经达到了令人难以想象的深度，各种算法应有尽有，不一而足，有的可以计算使用频率和最后一次使用时间，有的可以追踪倒数第二次访问的时间，而不关心最后一次访问的情况。不过，尽管创新性高速缓存方案品种繁多，其中一些在适当的条件下甚至可以击败最近最少使用法，但是最近最少使用法（以及在该策略基础上做出的一些细微调整）仍然深受计算机科学家们的喜爱，并且在开发各种应用程序时得到不同程度的应用。最近最少使用法告诉我们，我们需要的下一个程序可能就是之前我们需要的最后一个程序，接下来我们可能还需要之前需要的倒数第二个程序。我们最不需要的可能就是我们弃用时间最长的那个程序。
1700495336
1700495337
除非有充分的反对理由，否则我们可以认为对未来最有借鉴意义的就是历史的镜像。最接近于未卜先知的做法就是假定历史会重演，不过是按照相反的顺序重新上演。
1700495338
1700495339
1700495340
1700495341
[
上一页 ]
[ :1.700495292e+09 ]
[
下一页 ]