Задача

Чтобы понять принцип кэширования, рассмотрим следующую ситуацию. Вы работаете над длинной научной статьей, а жесткие правила вашей библиотеки позволяют брать не более восьми книг одновременно. Вы знаете, что восьми книг вам не хватит, но в любой момент времени вам хотелось бы иметь доступ к восьми книгам, наиболее актуальным на данный момент.
Как определить, какие книги следует заказать, когда вернуть часть из них в обмен на другие и как свести к ми- нимуму количество обменов книг в библиотеке?

Именно такая ситуация возникает при работе с иерархиями памяти: существует небольшой объем данных, к которым можно обращаться очень быстро, и большой объем данных, для обращения к которым требуется больше времени; вы должны решить, какие данные следует держать «под рукой».

Иерархии памяти повсеместно встречались на компьютерах с первых дней их истории. Для начала стоит отметить, что обращения к данным в основной памяти происходят существенно быстрее, чем обращения к данным на жестком диске; с другой стороны, диск обладает много большей емкостью. А это означает, что часто используемые данные лучше хранить в основной памяти и обращаться к диску как можно реже. Тот же принцип на качественном уровне используется встроенными кэшами современных процессоров. Обращение к содержимому осуществляется за несколько тактов, и выборка данных из кэша происходит намного быстрее, чем вы- борка из основной памяти. Так появляется еще один уровень иерархии; чтение из малого кэша осуществляется быстрее, чем чтение из основной памяти, а последняя работает быстрее диска (но имеет меньший объем). Расширения этой иерархии также встречаются во многих других ситуациях. Например, при работе в браузере диск часто выполняет функции кэша для часто посещаемых веб-страниц, так как чтение данных с диска происходит намного быстрее, чем загрузка по Интернету.

Общим термином «кэширование» называется процесс хранения малых объемов данных в быстрой памяти, чтобы уменьшить время, которое тратится на взаимо- действия с медленной памятью. В приведенных примерах встроенный кэш снижает необходимость в выборке данных из основной памяти, основная память выполняет функции кэша для диска, а диск служит кэшем для Интернета. (Подобно тому, как ваш рабочий стол служит кэшем для библиотеки, а отдельные факты, которые вам удается держать в голове без обращения к книге, образуют своего рода кэш для книг на столе.)

Чтобы кэширование было по возможности эффективным, желательно, чтобы при обращении к данным информация уже находилась в кэше. Для этого алгоритм управления кэшем определяет, какая информация должна храниться, а какую информацию следует удалить из кэша, когда в него потребуется внести новые данные.

Конечно, с возникновением проблемы кэширования в разных контекстах при- ходится учитывать различные факторы, зависящие от технологии. Впрочем, здесь будет использоваться абстрактное представление задачи, лежащее в основе боль- шинства контекстов. В нем рассматривается множество U из n фрагментов данных, хранящихся в основной памяти. Также существует более быстрая память — кэш, способная в любой момент времени хранить k < n фрагментов данных. Будем считать, что кэш изначально содержит множество из k элементов. Мы получаем последовательность элементов данных D = d1, d2, ..., dm из U — это последователь- ность обращений к памяти, которую требуется обработать; при обработке следует постоянно принимать решение о том, какие k элементов должны храниться в кэше. Запрашиваемый элемент d. очень быстро читается, если он уже находится в кэше; в противном случае его приходится копировать из основной памяти в кэш и, если кэш полон, вытеснять из него какой-то фрагмент данных, чтобы освободить место для d.. Такая ситуация называется кэш-промахом; естественно, мы стремимся к тому, чтобы количество промахов было сведено к минимуму.

Итак, для конкретной последовательности обращений к памяти алгоритм управления кэшем определяет план вытеснения (какие элементы в каких точках последовательности должны вытесняться из кэша), а последний определяет со- держимое кэша и частоту промахов. Рассмотрим пример этого процесса.

♦ Допустим, имеются три элемента {a, b, c}, размер кэша k = 2 и последователь- ность

a, b, c, b, c, а, b.

В исходном состоянии кэш содержит элементы а и b. Для третьего элемента последовательности можно вытеснить a, чтобы включить c в кэш; на шестом элементе можно вытеснить c, чтобы вернуть a; таким образом, вся последова- тельность включает два промаха. Если поразмыслить над этой последователь- ностью, становится понятно, что любой план вытеснения для этой последова- тельности должен включать как минимум два промаха.

В условиях реальных вычислений алгоритм управления кэшем должен обра- батывать обращения к памяти d1, d2, ..., не располагая информацией о том, какие обращения встретятся в будущем; но для оценки качества алгоритма системные аналитики с первых дней старались понять природу оптимального решения задачи кэширования. Если известна полная последовательность S обращений к памяти, какой план вытеснения обеспечит минимальное количество кэш-промахов?

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения