Принципы работы кэш - памяти.
Рассмотрим одну из возможных схем работы кэш-памяти для понимания принципов ее работы:
В кэш памяти содержатся ЗАПИСИ обо всех загруженных в нее элементах.
Каждая запись включает:
16. Данные
17. Адрес этих данных в основной памяти
18. Дополнительная инфа (признак модификации, признак действительности данных)
Процесс обращается к основной памяти:
19. ОС просматривает содержимое КЭШа, нет ли нужных данных там.
20. КЭШ-память не адресуема, поиск идет по адресу данных в оперативной памяти
1) Если данные есть – кэш попадание, данные считываются из КЭШа и передаются запросившему.
2) Если данных нет – кэш-промах, ОС идет в основную память и добывает данные оттуда.
При оценке эффективности кэш-памяти обычно используют следующие характеристики:
• коэффициент попаданий (hit rate) — отношение числа обращений к памяти, при которых произошло попадание, к общему числу обращений к ЗУ данного уровня иерархии;
• коэффициент промахов (miss rate) — отношение числа обращений к памяти, при
которых имел место промах; к общему числу обращений к ЗУ данного уровня иерархии;
• время обращения при попадании (hit time) — время, необходимое для поиска
нужной информации в памяти верхнего уровня (включая выяснение, является ли обращение попаданием), плюс время на фактическое считывание данных;
• потери на промах (miss penalty) — время, требуемое для замены блока в памяти более высокого уровня на блок с нужными данными, расположенный в ЗУ следующего (более низкого) уровня. Потери на промах включают в себя:
a. время доступа (access time) — время обращения к первому слову блока при промахе
b. время пересылки (transfer time) — дополнительное время для пересылки оставшихся слов блока.
Время доступа обусловлено задержкой памяти более низкого уровня, в то время как время пересылки связано с полосой пропускания канала между ЗУ двух смежных уровней.
От чего зависит эффективность кэширования? От вероятности попаданий в кэш.
Использование кэш-памяти имеет смысл только при высокой вероятности кэш-попаданий, т.к. иначе это только дополнительные расходы времени на поиск в КЭШе.
Вероятность кэш-попаданий зависит от:
- объема КЭШа
- объема кэшируемой памяти
- алгоритма замещения данных в КЭШе
- особенностей выполняемой программы
- времени ее работы
- и тд
Но в большинстве реализаций процент кэш-попаданий высокий, более 90%. Круть.
Это достигается за счет того, что данные обладают свойствами пространственной и временной локальности.
21. Временная локальность – если произошло обращение к какому-то адресу, то с большой вероятностью скоро по нему снова обратятся
22. Пространственная локальность – если произошло обращение к какому-то адресу, то скоро произойдет обращение по соседним адресам.
В соответствии с принципом временной локальности, в Кэше сохраняют недавно просмотренные данные, а в соответствии с принципом пространственной локальности, в кэш считывается не один элемент информации, а целый блок данных или целый массив, если идет обработка массива.
Проблема согласования данных.
Существование двух копий данных – в КЭШе и оперативной памяти – порождает проблему согласования данных.
Вытеснение данных из КЭШа
23. Если данные не были изменены, то нужно просто сбросить бит действительности
24. Если данные были изменены, то нужно скопировать их в основную память
2) Если во время нахождения данных в КЭШе были изменены данные в основной памяти – копия в КЭШе становится недостоверной.
Есть 2 варианта решения проблемы:
25. Сквозная запись – при каждой записи в основную память просматривается кэш. Если элемент найден в КЭШе, переписываются обе копии, если нет – только то, что в основной памяти
26. Обратная запись – при каждой записи в основную память просматривается кэш. Если элемент найден в КЭШе, переписывается только копия в КЭШе, если нет – то, что в основной памяти.
В некоторых алгоритмах замещения предусмотрена первоочередная выгрузка модифицированных, грязных данных. Также модифицированные данные могут выгружаться не только, когда нужно освободить кэш, но и в фоновом режиме, когда ОС больше нечем заняться.