Шерлок Холмс
Когда кеш заполнится, вам, очевидно, понадобится освободить место для хранения дополнительной информации. В компьютерной науке процесс освобождения места называется «замещение кеша». Как писал Вилкес, «поскольку кеш – это всего лишь малая часть объема основной памяти, слова не могут сохраняться в ней в течение неопределенного периода времени, поэтому в систему должен быть встроен алгоритм, согласно которому слова будут постепенно перезаписываться». Эти алгоритмы известны как алгоритмы замены или замещения или просто алгоритмы кеширования.
Как мы видим, роль IBM в части внедрения систем кеширования в 60-е годы была одной из основных. Неудивительно, что IBM стала первой проводить фундаментальные исследования алгоритмов кеширования. И, пожалуй, пальму первенства среди них нужно отдать алгоритму Ласло Белади. Белади родился в 1928 году в Венгрии, учился на инженера-механика, а во время Венгерской революции 1956 года бежал в Германию с одним рюкзаком, «в котором лежали только белье и диплом». Из Германии он переехал во Францию, затем в 1961 году эмигрировал в США вместе с женой, «маленьким сыном и тысячей долларов в кармане». Казалось, что он обладал отличным чувством меры и понимал, что нужно хранить, а с чем можно легко распрощаться, еще до начала своей работы над замещением кеша в IBM.
Работа Белади по алгоритмам кеширования, которую он написал в 1966 году, оставалась наиболее цитируемым исследованием в компьютерной науке в течение 15 лет. Согласно ей, цель использования кеша состоит в минимизации обращений к более медленной основной памяти в тех случаях, когда пользователь не может найти нужную информацию в кеше. Такие случаи называют «ошибка отсутствия страницы» или «число непопаданий в кеш». Оптимальная политика замещения кеша, как становится очевидно из определения, писал Белади, заключается в том, чтобы, когда кеш полностью заполнен, вытеснить любой его элемент, который максимально нескоро нам понадобится.
Разумеется, определить, когда нам понадобится та или иная информация, – задача трудновыполнимая.
Гипотетически всезнающий и предвидящий алгоритм, способный выбрать оптимальную политику, сегодня известен как алгоритм Белади. Это пример так называемого ясновидящего алгоритма, который использует информацию из будущего. На самом деле не все так безумно, как кажется, ведь существуют случаи, когда система может знать, чего ждать. Но в целом с ясновидением работать сложно, и специалисты по программному обеспечению часто шутят о «трудностях внедрения», которые возникают при попытках применить алгоритм Белади на практике. Таким образом, задача состоит в том, чтобы найти такой алгоритм, решение которого будет максимально дальновидным и точным в тех случаях, когда мы крепко завязли в настоящем и можем лишь гадать, что ждет нас впереди.