4846
правок
Подкачка страниц: различия между версиями
Материал из WEGA
м
→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Кэширование (''Caching'') == Постановка задачи == В компьютерах обычно имеется небольшой объем быстрой памяти, чтобы важные данные всегда были «под рукой». Эта память называется кэш-памятью. Рассматриваемый здесь вопрос заключае...») |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
В компьютерах обычно имеется небольшой объем быстрой памяти, чтобы важные данные всегда были «под рукой». Эта память называется кэш-памятью. Рассматриваемый здесь вопрос заключается в том, какие страницы должны храниться в кэше при запросе новой страницы. | В компьютерах обычно имеется небольшой объем быстрой памяти, чтобы важные данные всегда были «под рукой». Эта память называется ''кэш-памятью''. Рассматриваемый здесь вопрос заключается в том, какие страницы должны храниться в кэше при запросе новой страницы. | ||
Говоря формально, рассматривается двухуровневое хранилище памяти. Кэш может содержать k страниц, а медленная память – n страниц, где n обычно намного больше k. На вход подается последовательность запросов к страницам. Если запрашиваемая страница отсутствует в кэше, алгоритм выдает ошибку. Цель заключается в том, чтобы минимизировать совокупное количество ошибок страниц. | Говоря формально, рассматривается двухуровневое хранилище памяти. Кэш может содержать <math>k</math> страниц, а медленная память – <math>n</math> страниц, где <math>n</math> обычно намного больше <math>k</math>. На вход подается последовательность запросов к страницам. Если запрашиваемая страница отсутствует в кэше, алгоритм выдает ошибку. Цель заключается в том, чтобы минимизировать совокупное количество ошибок страниц. | ||
Легко предложить оптимальный алгоритм, если известна вся последовательность запросов: при каждой ошибке вытеснять из кэша ту страницу, которая в следующий раз будет запрашиваться в наиболее отдаленном будущем [2]. Однако на практике решения о подкачке приходится принимать без знания будущего. Таким образом, необходим онлайновый алгоритм, который принимает решения для каждого запроса, основываясь только на нем и на предыдущих запросах. | Легко предложить оптимальный алгоритм, если известна вся последовательность запросов: при каждой ошибке вытеснять из кэша ту страницу, которая в следующий раз будет запрашиваться в наиболее отдаленном будущем [2]. Однако на практике решения о подкачке приходится принимать без знания будущего. Таким образом, необходим ''онлайновый'' алгоритм, который принимает решения для каждого запроса, основываясь только на нем и на предыдущих запросах. | ||
== Основные результаты == | == Основные результаты == | ||
