1700495281
算法之美：指导工作与生活的算法 分级存储器体系
1700495282
1700495283
莉迪娅·戴维斯
1700495284
1700495285
有一位女性，她的感觉十分敏锐，但是记忆力极差……她忘不了工作，而且工作起来特别勤奋。
1700495286
1700495287
大约从2008年开始，我们在市场上为新购置的电脑选择存储器时，都会面临一个非常棘手的问题——必须在大小和速度之间做出权衡。计算机行业目前正处于从硬盘驱动器向固态硬盘过渡的阶段。同样的价位，硬盘的容量要比固态硬盘大得多，但是固态硬盘的性能则远胜对手。对于这点，大多数消费者现在已有体会，或者在换用固态硬盘后很快就会有所体会。
1700495288
1700495289
漫不经心的消费者可能不知道，计算机内部经常需要做出这种权衡，而且因为这种权衡太频繁了，以至于人们认为这是计算的基本原理之一。
1700495290
1700495291
1946年，亚瑟·伯克斯、赫尔曼·戈德斯坦和约翰·冯·诺依曼在普林斯顿高级研究所展开合作，为他们所谓的“电子记忆器官”起草了一个设计方案。他们写道，在一个理想的世界里，机器当然可以有无限量的快速储存能力，但在实践中这是不可能的。（现在仍然不可能。）于是，这三个人退而求其次，提出了“分级存储器体系，每一级的存储能力都超过以前，但是读取速度有所减慢”。事实上，通过各种各样的存储器，有的体积小、速度快，还有的体积大、速度慢，或许我们可以制造出兼具这两个优点的存储器。
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），即将闲置不用时间最长的内容清理掉（与之相对应的斯图尔特的问题是“上次穿它或使用它是什么时候的事”）。
[
上一页 ]
[ :1.70049528e+09 ]
[
下一页 ]