Кэширование данных: путь к повышению производительности. Что такое «Кэшированные данные» в телефонах и смартфонах Андроид

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

Компьютер, состоящий из самых разных по принципам работы и назначению устройств, можно с достаточно вескими основаниями назвать "гнездом раздора". Ну никак его подсистемы и узлы не хотят согласованно работать на общее благо. Если процессор вырывается вперед, от него отстает память, а о дисковых накопителях и говорить не приходится. И заставить всех бежать со скоростью, задаваемой лидером, чрезвычайно сложно.

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

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

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

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

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

Итак, кэширование чтения основано на предсказании следующих обращений к диску за данными (обычно расположенными непосредственно вслед за только что прочитанными) и помещении их в быстродействующую память перед тем, как они потребуются системе. Поскольку программа, отвечающая за кэширование, считывает информацию в память до того, как за ней обратятся, такой механизм часто называют буфером с упреждающим чтением (read look-ahead buffer). С точки зрения еще более существенного повышения производительности не имеет смысла размещать кэш-буфер и соответствующую программу в основной памяти компьютера, так как тогда она потребует часть вычислительных ресурсов центрального процессора. Дисковый накопитель сам способен справиться с упреждающим кэшированием, не отвлекая компьютер на хлопоты, связанные с управлением кэш-памятью.

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

Сегодня, когда большинство производителей использует от 128 до 512 килобайт кэш-памяти, компания Seagate в своих наиболее производительных накопителях Barracuda и Cheetah увеличила ее объем до полновесного мегабайта (предусмотрев возможность ее наращивания в четыре раза), а винчестеры Elite рекордной емкости (23 гигабайта) сразу оснащает 2 мегабайтами кэша. Это необходимо с учетом тех приложений, для которых предназначены указанные жесткие диски - для рабочих станций и серверов класса "хай-энд", мини- и суперкомпьютеров. В каждом из этих случаев постоянно требуется прочтение большого количества данных при максимальной скорости передачи. Настолько быстро, насколько только возможно.

Адаптивное кэширование Каждый раз, когда компьютер обращается за данными, которые уже находятся в кэше, запрос называется "попаданием в кэш". Если же запрошенных данных в кэше не оказалось и накопитель должен привести в действие свою механику и прочитать их с дисков, говорят о "промахе". О том, насколько эффективно работает программа (или алгоритм) кэширования, легче всего судить по соотношению попаданий и промахов. Сравнивая число попаданий с числом промахов, получают так называемый "рейтинг попаданий" для примененной схемы кэширования.

Применение стратегий, известных как адаптивное и сегментированное кэширование, помогает минимизировать частоту осечек.

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

Представим теперь, что кэш-память разделена на два сегмента по 400 килобайт каждый. Накопитель расценивает их как два абсолютно независимых кэш-буфера. Теперь данные для одного приложения можно записывать в первый 400-килобайтный сегмент, а для второго - во второй 400-килобайтный сегмент. Данные для обеих программ будут выдаваться из кэш-памяти, соотношение попаданий и промахов улучшится раза в два, если не больше. Именно поэтому в своих винчестерах Seagate применяет кэш-буферы, разделенные на два или четыре сегмента фиксированного размера. Наращивать их число свыше четырех инженеры из Seagate считают неоправданным, кроме исключительных случаев.

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

Предположим снова, что на винчестере установлен 800-килобайтый кэш-буфер с упреждающим чтением и этот буфер разделен на четыре сегмента по 200 килобайт. Предположим также, что запущенное на компьютере приложение запрашивает данные, которых нет ни в одном из четырех сегментов. Накопитель должен смириться с промахом и прочитать их со своих дисковых пластин, а заодно решить, куда их поместить в кэш-памяти. Чтобы принять такое решение, ему предстоит определить, какой из четырех сегментов лучше очистить. Разумеется, нежелательно помещать новые данные в сегмент, информация из которого вскоре может быть затребована, так как это приведет к повторному ее считыванию и перезагрузке кэша. Адаптивный алгоритм принимает решение о том, данные из какого сегмента скорее всего больше не понадобятся, основываясь на собственном анализе предыдущего использования данных.

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

Роман Соболенко,по материалам Seagate

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

История [ | ]

Впервые слово «cache» в компьютерном контексте было использовано в 1967 году во время подготовки статьи для публикации в журнале «». Статья касалась усовершенствования памяти в разрабатываемой модели 85 из серии IBM System/360 . Редактор журнала Лайл Джонсон попросил придумать более описательный термин, нежели «высокоскоростной буфер», но из-за отсутствия идей сам предложил слово «cache». Статья была опубликована в начале 1968 года, авторы были премированы IBM , их работа получила распространение и впоследствии была улучшена, а слово «кэш» вскоре стало использоваться в компьютерной литературе как общепринятый термин .

Функционирование [ | ]

Кэш - это память с большей скоростью доступа, предназначенная для ускорения обращения к данным, содержащимся постоянно в памяти с меньшей скоростью доступа (далее «основная память»). Кэширование применяется ЦПУ , жёсткими дисками , браузерами , веб-серверами , службами DNS и WINS .

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

Когда клиент кэша (ЦПУ, веб-браузер, операционная система) обращается к данным, прежде всего исследуется кэш. Если в кэше найдена запись с идентификатором, совпадающим с идентификатором затребованного элемента данных, то используются элементы данных в кэше. Такой случай называется попаданием кэша . Если в кэше не найдена запись, содержащая затребованный элемент данных, то он читается из основной памяти в кэш, и становится доступным для последующих обращений. Такой случай называется промахом кэша . Процент обращений к кэшу, когда в нём найден результат, называется уровнем попаданий , или коэффициентом попаданий в кэш.

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

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

При модификации элементов данных в кэше выполняется их обновление в основной памяти. Задержка во времени между модификацией данных в кэше и обновлением основной памяти управляется так называемой политикой записи .

В кэше с немедленной записью каждое изменение вызывает синхронное обновление данных в основной памяти.

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

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

Аппаратная реализация [ | ]

Кэш центрального процессора [ | ]

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

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

В неэксклюзивной кэши могут вести себя как угодно.

Уровни кэша [ | ]

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

Вторым по быстродействию является кэш второго уровня - L2 cache, который обычно, как и L1, расположен на одном кристалле с процессором. В ранних версиях процессоров L2 реализован в виде отдельного набора микросхем памяти на материнской плате. Объём L2 от 128 кбайт до 1−12 Мбайт. В современных многоядерных процессорах кэш второго уровня, находясь на том же кристалле, является памятью раздельного пользования - при общем объёме кэша в n Мбайт на каждое ядро приходится по n/c Мбайта, где c - количество ядер процессора.

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

Ассоциативность кэша [ | ]

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

При одинаковом объёме кэша схема с большей ассоциативностью будет наименее быстрой, но наиболее эффективной (после четырёхпотоковой реализации прирост «удельной эффективности» на один поток растет мало).

Кэширование внешних накопителей [ | ]

Многие периферийные устройства хранения данных используют внутренний кэш для ускорения работы, в частности, жёсткие диски используют кэш-память от 1 до 256 Мбайт (модели с поддержкой NCQ /TCQ используют её для хранения и обработки запросов), устройства чтения CD/DVD/BD-дисков также кэшируют прочитанную информацию для ускорения повторного обращения.

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

Применение кэширования внешних накопителей обусловлено следующими факторами:

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

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

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

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

Программная реализация [ | ]

Политика записи при кэшировании [ | ]

При чтении данных кэш-память даёт однозначный выигрыш в производительности. При записи данных выигрыш можно получить только ценой снижения надёжности. Поэтому в различных приложениях может быть выбрана та или иная политика записи кэш-памяти.

Существуют две основные политики записи кэш-памяти - сквозная запись (write-through) и отложенная запись (write-back):

Алгоритм работы кэша с отложенной записью [ | ]

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

Процесс читает данные в полученный буфер и освобождает его. В случае модификации процесс перед освобождением помечает буфер как «грязный». При освобождении буфер помещается в голову списка свободных буферов.

Таким образом:

если процесс прочитал некоторый блок в буфер, то велика вероятность, что другой процесс при чтении этого блока найдёт буфер в оперативной памяти;
запись данных во внешнюю память выполняется только тогда, когда не хватает «чистых» буферов, либо по запросу.

Алгоритм вытеснения [ | ]

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

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

Кэширование, выполняемое операционной системой [ | ]

Кэш оперативной памяти состоит из следующих элементов:

Кэширование интернет-страниц [ | ]

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

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

Кэширование результатов работы [ | ]

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

См. также [ | ]

Примечания [ | ]

Кэш // Большой орфографический словарь русского языка / под ред.

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

Технология кэширования в ExpressionEngine состоит из нескольких независимых систем кэширования данных, и настроек.

Кэширование запросов

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

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

Система кэширования запросов обеспечивает где-то от 30 % до 90%- сокращения общего количества запросов в зависимости от того, как созданы ваши страницы.

Эта возможность может быть вручную отключена на странице настройки базы данных в панели управления.

Кэширование тегов

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

Кэш тегов хранится в течение интервала времени, определенного пользователем. По истечении указанного интервала времени, кэш автоматически обновляется.

Для включения кэширования тега, добавьте указанные ниже два параметра для любого тега:

Cache="yes" refresh="10"

Примечание: refresh указывает время, в минутах, между обновлениями кэша.

Например, для кэширования тега в течение 30 минут, вы должны сделать следующее:

{exp:weblog:entries cache="yes" refresh="30"}

Кэширование шаблонов

Кэширование шаблонов (или кэширование динамических страниц) позволяет вам кэшировать все шаблоны, делая ваши страницы намного более легкими. Так как ExpressionEngine требует выполнение нескольких сценариев и запросов к базе данных для управления основными ресурсами, нельзя получить 100%-ых статических страниц, всегда будет немного меньше.

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

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

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

Кэширование динамических запросов раздела

Эта настройка находится на странице Admin > Глобальные настройки разделов. Эта функция увеличит скорость обработки тега {exp:weblog:entries} , кэшируя запросы, которые обычно выполняются динамически. Эта опция, однако, подходит не для всех людей.

Включайте эту функцию, только если вы не используете "будущие" или "прошедшие" записи.

Отключение запросов

Параметр disable= доступен в теге {exp:weblog:entries} . Он позволяет вам отключать функции тега, которые вы не используете, для повышения производительности. Тег weblog entries разработан так, что по умолчанию производится выборка большого количества информации: Категории, заказные поля, данные пользователя, и т.д. В зависимости от того, как вы используете тег, некоторые из этих данных могут быть не нужны. С помощью параметра "disable" вы можете отключить эти функции тега, чтобы сделать его более "легким".

Синтаксис для параметра disable следующий: disable="ЭЛЕМЕНТ, КОТОРЫЙ ВЫ ХОТИТЕ ОТКЛЮЧИТЬ" . Существует пять элементов, которые могут быть выключены:

categories
category_fields
custom_fields
member_data
pagination
trackbacks

Вы можете отключить несколько элементов, разделяя их, как показано ниже:

Disable="categories|member_data|trackbacks"

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

Например, если вы используете тег weblog entries для отображения заголовков 10 последних записей:

{exp:weblog:entries orderby="date" sort="desc" limit="10"}
{title}

{/exp:weblog:entries}

В этом примере вы отображаете только заголовки ваших записей, и нечего больше; тем не менее, тег weblog извлекает категории и другие данные автоматически. Используя параметр disable= , вы можете отключить ненужные функции для того, чтобы исключить их из запроса. В нашем случае вы не нуждаетесь ни в одной из функций, и все они могут быть отключены.

{exp:weblog:entries orderby="date" sort="desc" limit="10" disable="categories|custom_fields|member_data|pagination|trackbacks"}
{title}

{/exp:weblog:entries}

Примечание : Вы так же можете использовать параметр disable="category_fields" в тегах

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

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

Значение элемента данных;

Адрес элемента данных в основной памяти;

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

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

Эффективность кэширования и среднее время доступа к данным в системе зависят от вероятности попадания в кэш. Поэтому использование кэш-памяти эффективно только при высокой вероятности кэш-попадания. Вероятность обнаружения данных в кэше зависит от следующих факторов: от объемов кэша и кэшируемой памяти, от алгоритма замещения данных в кэше, от особенностей выполняемой программы и времени ее работы, от уровня мультипрограммирования и других особенностей вычислительного процесса. В большинстве реализаций кэш-памяти процент кэш-попаданий выше 90%, это объясняется наличием у данных объективных свойств: пространственной и временной локальности.

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

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

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

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

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

1.Сквозная запись (write through ). При каждом запросе к основной памяти и при записи в нее просматривается кэш. Если данные по запрашиваемому адресу отсутствуют, то запись выполняется только в основную память. Если же данные, к которым выполняется обращение, находятся в кэше, то запись выполняется одновременно в кэш и основную память.

2.Обратная запись (write back ). При возникновении запроса к памяти выполняется просмотр кэша. Если запрашиваемых данных отсутствуют, то запись выполняется только в основную память. В ином случае запись производится только в кэш-память, при этом в описателе данных делается специальная отметка (признак модификации), которая указывает на то, что при вытеснении этих данных из кэша необходимо переписать их в основную память.

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

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

1.Случайное отображение . Элемент оперативной памяти и его адрес размещается в произвольном месте кэш-памяти. Критерием поиска в кэше является адрес оперативной памяти из запроса. Для поиска запрошенных данных используется алгоритм ассоциативного поиска , при котором сравнения с записями кэша выполняются параллельно. Признак (адрес данных в оперативной памяти), по которому выполняется сравнение, называется тегом (tag ). Вытеснение устаревших данных происходит только в случае, полного заполнения кэш-памяти. Выбор данных на выгрузку осуществляется среди всех записей кэша и основывается на приемах, аналогичных алгоритмам замещения страниц. Электронная реализация схемы приводит к удорожанию памяти, поэтому ассоциативная кэш-память используется в случаях, когда для обеспечения высокого процента попадания достаточно небольшого объема памяти.

2.Детерминированное отображение . Элемент основной памяти всегда отображается в одно и то же место кэш-памяти. Кэш-память разделена на строки, каждая из которых имеет свой номер и предназначена для хранения одной записи об одном элементе данных. Между номерами строк кэш-памяти и адресами оперативной памяти устанавливается соответствие «один ко многим»: одному номеру строки соответствует несколько адресов оперативной памяти. Отображение осуществляется при помощи специальных функций, например, путем простого выделения нескольких разрядов из адреса оперативной памяти, которые интерпретируются как номер строки кэш-памяти.

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

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

По номеру группы, полученному из адреса оперативной памяти из запроса;

В пределах группы путем ассоциативного просмотра всех записей в группе на случай совпадения старших частей адресов оперативной памяти.

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

Диаграмма кэша памяти ЦПУ

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

Когда клиент кэша (ЦПУ, веб-браузер, операционная система) обращается к данным, прежде всего исследуется кэш. Если в кэше найдена запись с идентификатором, совпадающим с идентификатором затребованного элемента данных, то используются элементы данных в кэше. Такой случай называется попаданием кэша . Если в кэше не найдено записей, содержащих затребованный элемент данных, то он читается из основной памяти в кэш, и становятся доступным для последующих обращений. Такой случай называется промахом кэша . Процент обращений к кэшу, когда в нём найден результат, называется уровнем попаданий или коэффициентом попаданий в кэш.

В кэше с немедленной записью каждое изменение вызывает синхронное обновление данных в основной памяти.

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

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