Принцип кэширования

Работа с оперативной памятью.

Принцип кэширования состоит в следующем. Пусть есть два способа получения информации: первый быстрый, а второй – медленный. Причем часто требуется информация, которая была уже выбрана ранее. Первичный источник информации – тот, доступ к которому затруднен. Очевидный способ ускорения получения информации – хранение ее в некотором буфере с высокой скоростью доступа.

Но следует учитывать два фактора: скоростной буфер может быть дорогой, информация в первичном источнике может изменяться, следовательно, требуется ее обновление в буфере.

Такой скоростной буфер называют кэш. Физически это может быть и аппаратное средство, и программный способ хранения данных.

Ускорение доступа к информации происходит за счет того, что она сначала ищется в кэш, и только если ее там нет, осуществляется более длительный поиск в первичном источнике. Очевидно, что в случае, если информация не требуется повторно, использование кэш не только не полезно, но и вредно, так как замедляет поиск. Замедление происходит потому, что сначала данные ищутся в кэш, а после этого – в первичном источнике.

Покажем, как среднее время доступа к данным зависит от вероятности попадания в кэш -P. Пусть имеется основное запоминающее устройство объемом V (количество записей) со средним временем доступа к данным tвн. Пусть есть последовательная кэш-память, реализующая время доступа к одному данному tкэш. Обозначим через Pизм –вероятность того, что вытесняемые из кэш данные были изменены и их приходится переносить в основную память. Тогда среднее время доступа к данным (по определению математического ожидания) можно рассчитать следующим образом:

t = (tкэш*V + tвн*Pизм+ tвн) *(1 – P) + ((tкэш*V)/2) *P

Из нее видно, что среднее время доступа к данным в системе с кэш-памятью линейно зависит от вероятности попадания в кэш. Очевидно также и то, что при отсутствии данных в кэш тратится лишнее время на поиск в кэш и на вытеснение не нужного данного.

В реальных системах вероятность того, что нужные данные окажутся в кэш составляет примерно 0,9. Высокое значение вероятности связано с наличием у данных объективных свойств: пространственной и временной локальности.

Пространственная локальность. Если произошло обращение по некоторому адресу, то с высокой степенью вероятности в ближайшее время произойдет обращение к соседним адресам. Пример: почти любая обработка массива данных выглядит как последовательное или почти последовательное обращение к элементам массива.

Временная локальность. Если произошло обращение по некоторому адресу, то следующее обращение по этому же адресу с большой вероятностью произойдет в ближайшее время. Пример: счетчик цикла for – к нему, как минимум один дважды происходит обращение при каждой итерации (наращивание и сравнение с границей), а часто и в теле цикла используется счетчик, например, для индексации.

Замечание: указанные два свойства данных вытекают из естественной природы практически любой информации, но далее мы увидим, что эти свойства могут (и должны!) искусственно обеспечиваться с целью ускорения работы компьютера (пример – LE (линейно выполнимые) задачи, о которых будет рассказано в теме "Виртуальная память").

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

Дата добавления: 2014-12-07