Память современных ЭВМ представляет собой многоуровневую структуру запоминающих устройств нескольких типов, которые отличаются по своим характеристикам. Основными из них являются информационный объем, время доступа и стоимость хранения одного бита информации.
Данная схема отражает известную закономерность. Чем больше носитель, тем медленнее доступ. Стоимость хранения бита возрастает с увеличением быстродействия устройства. Устройства памяти, которое было бы недорогим, быстродействующим, и отвечало бы требованиям по объему, в настоящее время не существует.
Получение такой памяти реализуется применением особого вида памяти, называемого кэш-памятью.
· Кэш-память – это способ совместного использования двух типов запоминающих устройств, отличающихся по приведенным характеристикам. Одно из этих устройств, обладающее меньшим временем доступа, и как правило, более высокой стоимостью, условно называется быстрым, а другое устройство, обладающее большим временем доступа, меньшей стоимостью и большим объемом, условно называется медленным.
Кэшем называется не только способ взаимодействия двух типов запоминающих устройств, но и просто одно из этих устройств – быстрое из них.
Работа кэш-памяти основана на том, что за счет периодического динамического копирования в быстрое ЗУ наиболее часто используемой информации из медленного ЗУ оказывается возможным:
1. Уменьшить среднее время доступа к данным;
2. Сэкономить дорогостоящую быструю память.
Важным свойством кэш-памяти называется её «прозрачность» для программ и пользователей. Это означает, что ни пользователи, ни их программы никоем образом не участвуют в перемещении данных из ЗУ одного типа в ЗУ другого типа. Все операции выполняются автоматически системными средствами.
Если кэширование используется для уменьшения времени доступа к ОП, то в качестве кэша на практике используется быстродействующая полупроводниковая память статического типа.
Если кэширование применяется в системах ввода/вывода ЭВМ для ускорения доступа к данным во внешней памяти, то функции кэш-памяти возлагаются на ОП, в которой создаются специальные буферные области ввода/вывода, куда записываются наиболее часто используемые данные.
Виртуальную память также можно рассматривать как один из вариантов реализации принципа кэширования, при котором ОП выступает в роли быстродействующей кэш-памяти по отношению к кэш-памяти.
Обобщенную схему кэширования и структуру кэш-памяти можно представить следующей схемой:
| Ячейки кэш-памяти | Адрес данных в основной памяти | Данные | Управляющая информация |
| … | … | … | |
Под основной памятью понимается любое конкретное устройство памяти, обладающее меньшим быстродействием по сравнению с устройством кэш-памяти. Содержимое кэш-памяти представляет собой совокупность записей о загруженных в эту память элементах данных из основной памяти.
Каждая запись об элементе данных включает в себя:
1. Адрес элемента данных в основной памяти;
2. Содержание элемента данных;
3. Дополнительную управляющую информацию, которая используется для реализации алгоритма замещения данных в кэше. Обычно эта информация включает признак модификации и признак действительности данных.
Обращение к основной памяти вырабатывается в источнике запросов, которым в большинстве случаев является выполняющийся процесс. При исполнении каждого запроса с использованием физического адреса основной памяти в кэше просматривается содержимое всех ячеек с целью нахождения нужных данных. При этом просмотре используется берущийся из запроса адрес данных в основной памяти. В ходе выполнения запроса к памяти возможны два варианта:
1. Данные обнаруживаются в кэш-памяти. Это означает, что произошло кэш-попадание. Данные считываются из кэш-памяти и передаются источнику запросов (быстрый ответ).
2. Данные в кэше не обнаруживаются. В этом случае происходит кэш-промах. Данные считываются из основной памяти (медленный ответ), передаются источнику запроса и одновременно копируются в кэш-память.
Очевидно, что эффективность кэширования зависит от вероятности попадания данных в кэш. Это можно проиллюстрировать, если оценить зависимость среднего времени tср доступа к данным от вероятности P кэш-попаданий. Будем считать, что t1 – это среднее время доступа к основной памяти, t2 – среднее время доступа к кэш-памяти. Очевидно, что t2<t1. Тогда среднее время tср доступа к системе памяти, состоящей из основной и кэш-памяти, может быть оценено по соотношению tср=t2*p + t1*(1-p)= (t2-t1)*p + t1 – формуле полной вероятности.
Среднее время линейно зависит от вероятности p и от t1 при p=0 до t2 при p=1. Это означает, что смысл использования кэш-памяти существует только при достаточно высокой вероятности кэш-попаданий. Вероятность кэш-попаданий зависит от разных факторов: объема кэш-памяти, объема основной памяти, способа замещения данных в кэше при записи туда новой информации, алгоритма работы программы, в которой формируется запрос и других характеристик вычислительного процесса. Тем не менее, на практике, в большинстве систем с кэш-памятью вероятность кэш-попадания оказывается достаточно высокой. Pср=90%.
Это объясняется наличием у данных двух объективных данных:
1. Свойства временной локальности;
2. Свойства пространственной локальности.
Основываясь на свойстве временной локальности, данные, только что считанные из основной памяти, записываются в кэш-память в предположении, что они снова потребуются в ближайшие интервалы времени. В самом начале работы системы памяти, когда кэш-память пуста, каждый запрос к основной памяти выполняется полностью.
1. Просмотр кэш-памяти;
2. Фиксация кэш-промаха;
3. Чтение данных из основной памяти;
4. Передача данных источнику запроса;
5. Копирование прочитанных данных, то есть их запись в кэш-память.
По мере работы системы, кэш-память заполняется данными, и в соответствии со свойством временной локальности, возрастает вероятность обращения к данным, которые уже были использованы в предшествующие моменты времени. Эти данные содержатся в кэше, и могут быть считаны быстрее, чем из основной памяти.
Свойство пространственной локальности также оказывает влияние на увеличение вероятности кэш-попадания. Чаще всего из кэш-памяти считывается не отдельный информационный элемент, а группа (блок) элементов, расположенных в непосредственной близости друг от друга. Это увеличивает вероятность присутствия в кэш-памяти данных, к которым будет происходить обращение в ближайшие моменты времени, например, к элементам массивов, которые расположены в непосредственной близости от прочитанного текущего элемента, или к команде программы, которая будет выполняться после текущей команды. В первом случае, в кэш считывается несколько элементов массива с последовательными номерами, или даже весь массив. Во втором случае считывается группа команд программы с последовательными адресами.
В процессе работы системы с кэш-памятью, содержимое кэш-памяти постоянно обновляется. Это означает, что периодически вследствие ограниченности объема кэш-памяти, некоторые данные из неё должны вытесняться. Вытеснение означает либо простое объявление кэш-памяти как свободной, если данные, хранившиеся в этой области не были изменены, либо в дополнение к этому – копирование данных в основную память, если за время нахождения в кэше данные изменились.
Алгоритм замещения данных, вытесняемых из кэша, оказывает заметное влияние на эффективность работы кэш-памяти. Такой алгоритм, во-первых, должен быть максимально быстродействующим, и во-вторых, должен обеспечивать максимально возможную вероятность кэш-попадания. Вследствие непредсказуемости развития вычислительного процесса во времени, ни один алгоритм замещения данных в кэш-памяти не может гарантировать абсолютно оптимального результата, поэтому на практике, при разработке систем с кэш-памятью, выбирается компромиссный алгоритм, который, прежде всего, не сильно замедляет работу кэш-памяти, и во-вторых, обеспечивает приемлемую вероятность кэш-попадания.
В используемых алгоритмах замещения используются подходы, аналогичные принципу LRU в системах виртуальной памяти. Наличие в системе с основной кэш-памятью двух копий данных ведет к возникновению проблемы согласования данных. Она состоит в том, что если происходит запись в основную память по некоторому адресу, и содержимое этой ячейки еще присутствует в кэш-памяти, то эта информация в кэш-памяти становится недостоверной, то есть с течением времени устаревает, и её необходимо обновлять. Проблема согласования данных может решаться двумя способами:
1. Сквозная запись. При каждом запросе к основной памяти, в том числе и при выполнении операции записи данных в неё, просматривается содержимое кэш-памяти. Если данные по сформированному в запросе адресу в кэш-памяти отсутствуют, то запись осуществляется только в основную память, и в кэш не заносятся. Если же эти данные находятся в кэше, то запись осуществляется одновременно и в кэш-память, и в основную память.
2. Способ обратной записи. При появлении запроса к памяти просматривается кэш-память. Если запрашиваемых данных в ней нет, то запись выполняется только в основную память. В противном случае, когда данные в кэше имеются, запись осуществляется только в кэш-память, и записываемые данные сопровождаются специальным дескриптором, в котором делается отметка, называемая признаком модификации. Он указывает на то, что при вытеснении этих данных из кэша их необходимо переписать в основную память, чтобы модифицировать устаревшее содержимое, и не потерять внесенные изменения.
Существуют разновидности этих способов, в которых предусматривается первоочередная выгрузка из кэша модифицированных данных. Она может выполняться не только в момент освобождения места в кэш-памяти, но и в любой другой момент работы системы, когда интенсивность обращений к памяти не столь высока.
