1) Cтратегия fifo, в соответствии с которой из основной памяти
удаляются страницы, раньше других занесенные в нее.
2) Cтратегия lru, при использовании которой удаляется та страница, обращение к которой имело место раньше, чем к другим.
3) cтратегия WS (Working Set - рабочее множество), в соответствии с которой удаляются страницы, не содержащиеся в так называемом рабочем множестве, т. е. наборе страниц, к которым за определенный истекший интервал времени зафиксировано обращение. Две из этих стратегий замены страниц - LRU и WS - основаны на предположении, что страницы, использовавшиеся в последний период, будут часто использоваться и впредь. По сравнению с ними реализация стратегии FIFO проще, но эффективность ее относительно ниже. На практике обычно используются стратегии LRU и WS, а также их сочетание и модификации.
Управление распределением основной памяти. Одна из проблем параллельной обработки состоит в том, каким образом распределить блоки основной памяти между всеми программами, участвующими в этой обработке, В общем случае чем больше объем распределяемой основной памяти, тем реже приходится производить ее перераспределение. Для повышения эффективности выполнения каждой из параллельно обрабатываемых программ необходимо обеспечить их определенным объемом основной памяти. При чрезмерном увеличении уровня мультиплексирования программ уменьшается объем памяти, отводимой каждой из них, повышается частота обмена страниц, что приводит к резкому снижению эффективности всей системы мультипрограммной обработки.
стр.8
Возникает так называемое дробление памяти. Для устранения этого явления управление обменом страниц осуществляется с учетом
обеспечения наибольшей эффективности использования центрального
процессора. Хотя реализация этого управления занимает время, ситуация в целом улучшается благодаря своевременному сокращению степени мультиплексирования.
Расслоение памяти. При обращении к основной памяти с целью
ускорения этого процесса запись и считывание нескольких байтов могут осуществляться за один раз. В большинстве современных ЭВМ основная память подразделяется на несколько независимых модулей (блоков). Это разбиение способствует повышению эквивалентного
быстродействия основной памяти. При неисправностях или повреждениях соответствующие блоки памяти исключаются из основной памяти с последующим ее перегруппированием, в результате чего работоспособность памяти сохраняется, хотя с некоторым ухудшением ее параметров.
Для повышения эффективности многоблочной структуры в ее
системе адресации применяется процедура расслоения. Суть этой
процедуры состоит в том, что при числе блоков п поступающий адрес а
относится к блоку с номером (a) mod п. Например, при четырех блоках
памяти адресация выполняется в соответствии со структурой, показанной на рис. 1.7.
стр.9 При обращениях к последовательным соседним адресам можно добиться n-кратного увеличения скорости обращения за счет
параллельного действия всех блоков. Подобная процедура распределения адресов по блокам называется n-расслоением обращений к памяти.
Схема управления вводом-выводом информации является общей для всех блоков и работает с разделением времени, т. е. практически блоки действуют с некоторым временным смещением, как показано на рис.1.8. Обычно п равно 2—16, но в некоторых случаях число блоков памяти достигает 64.
Рис. 1.8 Временная диаграмма памяти с расслоением Кэш-память. Кэш-память предназначена для повышениябыстродействия процесса обращения к основной памяти. В ее структуру, как показано на рис.1.9, входят массив данных и справочник. В массив данных копируются соответствующие блоки основной памяти, а их адреса заносятся в справочник. Блок обработки команд процессора обычно обращается к буферной памяти. При отсутствии в ней требуемых блоков они переписываются в нее из основной памяти. При этом эквивалентное время обращения к памяти ta, определенное по формуле (1.1), равно ta = tb + α* tm (1.2)
где tb— время обращения к буферной памяти, tm— время обращения
к основной памяти, α - вероятность отсутствия требуемой информации в буферной памяти (вероятность неудачного обращения). Обычно tb меньше tm на порядок и при достаточном уменьшении α можно достичь ta приблизительно равным tb.
По мере повышения быстродействия элементов вычислительной
техники повышается быстродействие и процессора. При этом сокращается и время обращения к буферной памяти. Однако в силу постоянно растущих требований к увеличению объема памяти время обращения к основной памяти существенно уменьшить трудно, и разница между tb и tm увеличивается, что приводит к снижению эффективности буферной памяти. Преодолевается эта тенденция за счет увеличения емкости кэш-памяти или применения многоуровневой структуры кэш.
Стр.10
Система буферизации может быть применена и для обмена данными между основной памятью и памятью на дисках. Используя кэш- память емкостью несколько десятков мегабайт, реализованную на запоминающих элементах СБИС или выделенную в специальной области оперативной памяти, можно увеличить эквивалентную скорость обращения к дискам и флэш-картам примерно в 2—10 раз.
Таким образом кэширование — это универсальный метод, пригодный для ускорения доступа к оперативной памяти, к диску и к другим видам запоминающих устройств.
Виртуальную память также можно считать одним из вариантов реализации принципа кэширования данных, при котором оперативная память выступает в роли кэш по отношению к внешней памяти — жесткому диску. И в этом случае кэширование используется не только для того, чтобы уменьшить время доступа к информации, но и для того, чтобы использовать диск для временного хранения неиспользуемых некоторое время программ и данных с целью освобождения места для активных процессов. В результате наиболее интенсивно используемые программы и данные находятся в оперативной памяти, остальная же информация хранится в более
объемной и менее дорогостоящей внешней памяти.
Рассмотрим одну из возможных схем кэширования (рис.1.10).
Содержимое кэш-памяти представляет собой совокупность записей обо всех загруженных в нее элементах данных из основной памяти. Каждая запись об элементе данных включает в себя три поля:
- адрес, который этот элемент данных имеет в основной памяти;
- дополнительную информацию, которая используется для
реализации алгоритма замещения данных в кэш и обычно включает признак модификации и признак действительности данных;
- значение элемента данных.
Первое поле зачастую называют полем тегов, второе – полем
стр.11
достоверности, третье - полем данных. При каждом обращении к основной памяти по физическому адресу просматривается содержимое кэш-памяти с целью определения, не находятся ли там нужные данные. Кэш-память не является адресуемой, поэтому поиск нужных данных осуществляется по содержимому – по взятому из запроса значению поля адреса в оперативной памяти. Далее возможен один из двух вариантов развития событий:
- если данные обнаруживаются в кэш-памяти, то есть произошло
кэш- попадание (cache-hit), они считываются из нее и результат передается источнику запроса;
- если нужные данные отсутствуют в кэш-памяти, то есть
произошел кэш-промах (cache-miss), они считываются из основной памяти, передаются источнику запроса и одновременно с этим копируются в кэш- память.
Среднее время доступа к данным в системе с кэш-памятью линейно
зависит от вероятности попадания в кэш. Очевидно, что использование кэш- памяти имеет смысл только при высокой вероятности кэш-попадания.
Вероятность обнаружения данных в кэш зависит от разных факторов, таких, например, как объем кэш, объем кэшируемой памяти, алгоритм замещения данных в кэш, особенности выполняемой
стр.12
программы, время ее работы, уровень мультипрограммирования и других особенностей вычислительного процесса. Тем не менее в большинстве реализаций кэш- памяти процент кэш-попадании оказывается весьма высоким — свыше 90 %. Такое высокое значение вероятности нахождения данных в кэш- памяти объясняется наличием у программ и данных объективных свойств, называемых пространственной и временной локальностью. Временная локальность заключается в том, что если произошло обращение по некоторому адресу, то следующее обращение по тому же адресу с большой вероятностью произойдет в ближайшее время.
Пространственная локальность заключается в том, что если произошло обращение по некоторому адресу, то с высокой степенью вероятности в ближайшее время произойдет обращение к соседним адресам. Основываясь на свойстве временной локальности, программы и данные, только что считанные из основной памяти, размещают в запоминающем устройстве быстрого доступа, предполагая, что скоро они опять понадобятся. В начале работы системы, когда кэш-память еще пуста, происходит процедура её заполнения. В этот промежуток времени практически каждый запрос к основной памяти выполняется по следующей схеме: просмотр кэш, констатация промаха, чтение данных из основной памяти, передача результата источнику запроса с одновременным копированием данных в кэш. Затем, по мере заполнения кэш, в полном соответствии со свойством временной локальности возрастает вероятность
обращения к данным, которые уже были использованы на предыдущем
этапе работы системы, то есть к данным, которые содержатся в кэш и могут быть считаны значительно быстрее, чем из основной памяти.
Свойство пространственной локальности также используется для
увеличения вероятности кэш-попадания: как правило, в кэш-память
считывается не один информационный элемент, к которому произошло
обращение, а целый блок данных, расположенных в основной памяти в
непосредственной близости с данным элементом. Поскольку при
выполнении программы очень высока вероятность, что команды
выбираются из памяти последовательно одна за другой из соседних ячеек, то имеет смысл загружать в кэш-память целый фрагмент программы.
Аналогично если программа ведет обработку некоторого массива данных, то ее работу можно ускорить, загрузив в кэш часть или даже весь массив данных. При этом учитывается высокая вероятность того, что значительное число обращений к памяти будет выполняться к адресам массива данных.
Проблема согласования данных. В процессе функционирования
вычислительной системы содержимое кэш-памяти постоянно обновляется. Время от времени устаревшие данные из нее вытесняются для освобождения места под новые данные. Реально вытеснение означает либо простое объявление свободной соответствующей области кэш-памяти (сброс бита действительности), если вытесняемые данные за время нахождения в кэш не были изменены, либо в дополнение к этому копирование данных в
основную память, если они были модифицированы. Алгоритм замены
стр.13
данных в кэш-памяти существенно влияет на ее эффективность. Алгоритм должен, во-первых, быть максимально быстрым, чтобы не замедлять работу кэш-памяти, а во-вторых, обеспечивать максимально возможную вероятность кэш-попаданий. Поскольку из-за непредсказуемости вычислительного процесса ни один алгоритм замещения данных в кэш- памяти не может гарантировать идеальный результат, разработчики ограничиваются рациональными решениями, которые по крайней мере, не сильно замедляют работу кэш.
Наличие в МПС двух копий данных - в основной памяти и в кэш -
порождает проблему согласования данных. Если происходит запись в
основную память по некоторому адресу, а содержимое этой ячейки
находится в кэш, то в результате соответствующая запись в кэш становится недостоверной.
Рассмотрим два подхода к решению этой проблемы.
Сквозная запись (write through). При каждом запросе к основной памяти, в том числе и при записи, просматривается кэш. Если строка с
запрашиваемым адресом отсутствует в кэш (для этого просматривают поле тегов), то запись выполняется только в основную память. Если же адрес, по которому выполняется обращение, находится и в КЭШе, то запись производится одновременно в кэш и основную память. Такая операция по времени равносильна обращению в основную (оперативную) память и не дает большого выигрыша от применения кэш-памяти.
Обратная запись (write back). Аналогично при возникновении запроса к памяти выполняется просмотр кэш, и если строка с запрашиваемым адресом там отсутствует, то запись выполняется только в основную память. В противном же случае запись производится только в
кэш-память, при этом в поле управления делается специальная отметка
(признак модификации), которая указывает на то, что при вытеснении этих данных из кэш необходимо переписать их в подходящий момент в основную память, чтобы обновить устаревшее содержимое основной памяти.
Очевидно, что в этом случае в соответствии с принципами временной и пространственной локальности, обращения будут происходить преимущественно к кэш-памяти, а малая их доля упадёт на основную память. Поэтому временная эффективность метода обратной записи высокая, хотя требует применения более сложных алгоритмов согласования данных.
Контроллер кэш-памяти осуществляет копирование модифицированной строки при любых замещениях строки. Модифицированные данные могут выгружаться не только при освобождении места в кэш-памяти для новых данных, но и в «фоновом режиме», то есть в промежутках, когда шинный интерфейс не занят процессором или другими устройствами.
В некоторых алгоритмах замещения предусматривается первоочередная выгрузка модифицированных, или, как еще говорят, «грязных» данных.
Способы отображения основной памяти на кэш. Алгоритм поиска и алгоритм замещения данных в кэш непосредственно зависят от того,
каким образом основная память отображается на кэш-память. Принцип
прозрачности требует, чтобы правило отображения основной памяти на
стр.14
кэш-память не зависело от работы программ и пользователей. При
кэшировании данных из оперативной памяти широко используются две
основные схемы отображения: случайное отображение и
детерминированное отображение.
При случайном отображении элемент оперативной памяти в общем
случае может быть размещен в произвольном месте кэш-памяти. Для того чтобы в дальнейшем можно было найти нужные данные в кэш, они помещаются туда вместе со своим адресом, то есть тем адресом, который данные имеют в оперативной памяти. При каждом запросе к оперативной памяти выполняется поиск в кэш, причём критерием поиска выступает адрес оперативной памяти из запроса. Очевидная схема простого перебора для поиска нужных данных в случае кэш оказывается непригодной из-за недопустимо больших временных затрат.
Для кэш со случайным отображением используется так называемый
полный ассоциативный поиск, при котором сравнение выполняется не
последовательно с каждой записью кэш, а параллельно со всеми его записями (рис.1.11). Признак, по которому выполняется сравнение, называется тегом (tag). В данном случае тегом является адрес данных в оперативной памяти. Электронная реализация такой схемы приводит к удорожанию памяти, причем стоимость существенно возрастает с увеличением объема запоминающего устройства. Поэтому полностью ассоциативная кэш-память используется в тех случаях, когда для обеспечения высокого процента попадания достаточно небольшого объема памяти.
В кэш, построенных на основе случайного отображения, вытеснение старых данных происходит только в том случае, когда вся кэш-память заполнена и в ней не осталось свободного места. Выбор данных на выгрузку осуществляется среди всех записей кэш. Обычно этот выбор основывается на тех же приемах, что и в алгоритмах
стр.15
замещения станиц, например выгрузка данных, к которым дольше всего не было обращений, или данных, к которым было меньше всего обращений.
Второй, детерминированный способ отображения предполагает, что любой элемент основной памяти всегда отображается в одно и то же место кэш-памяти. В этом случае кэш-память разделена на строки, каждая из которых предназначена для хранения одной записи об одном элементе данных и имеет свой номер. Между номерами строк кэш-памяти и адресами оперативной памяти устанавливается соответствие «один ко многим»:
-одному номеру строки соответствует несколько (обычно достаточно много) адресов оперативной памяти.
В качестве отображающей функции может использоваться простое
выделение нескольких разрядов из адреса оперативной памяти, которые интерпретируются как номер строки кэш-памяти (такое отображение называется прямым). Например, рассмотрим принцип построения кэш- памяти (рис. 1.12) объёмом 256 Кбайт с размером строки 32 байта и объёмом кэшируемой основной памяти 64 Мбайт. Кэшируемая основная память при этом разбивается на блоки, размер которых равен размеру кэш-памяти. Для рассматриваемого случая количество блоков равно 256. В свою очередь кэш- память делится на строки, длина которых равна количеству байт, передаваемых процессором в одном пакете ( 4 х 8 байт = 32 байта для процессоров Pentium). Тогда в кэш-памяти будет храниться 8192 записей, то
есть кэш имеет 8К строк, пронумерованных от 0 до 8К-1. Любой адрес
оперативной памяти может быть отображен на адрес кэш-памяти простым отделением 13 двоичных разрядов(2**13=8192).
При поиске данных в КЭШе используется быстрый прямой доступ к
записи по номеру строки, полученному путем обработки адреса из
запроса. Однако поскольку в найденной строке могут находиться данные ячейки оперативной памяти, младшие разряды адреса которой совпадают с номером строки, необходимо выполнить дополнительную проверку. Для этих целей каждая строка кэш-памяти дополняется тегом, содержащим старшую часть адреса данных в оперативной памяти. Для сравнения с тегом используются 8 старших разрядов(2**8=256) адреса из запроса. При совпадении тега с соответствующей частью адреса оперативной памяти из запроса констатируется кэш-попадание. Для адресации байт внутри строки необходимо выделить 5 разрядов( 2**5=32) из адреса запроса.
стр.16
Если же произошел кэш-промах, то данные считываются из
оперативной памяти и копируются в кэш. Если строка кэш-памяти, в
которую должен быть скопирован элемент данных из оперативной памяти, содержит другие данные, то последние вытесняются из кэш. Заметим, что процесс замещения данных в кэш-памяти на основе прямого отображения существенно отличается от процесса замещения данных в кэш-памяти со случайным отображением. Во-первых, вытеснение данных происходит не только в случае отсутствия свободного места в кэш, во-вторых, никакого выбора данных на замещение не существует.
Во многих современных процессорах кэш-память строится на основе сочетания этих двух подходов, что позволяет найти компромисс между сравнительно низкой стоимостью кэш с прямым отображением и
интеллектуальностью алгоритмов замещения в кэш со случайным
отображением. При смешанном подходе произвольный адрес
оперативной памяти отображается не на один адрес кэш – памяти (как это характерно для прямого отображения) и не на любой адрес кэш памяти (как это делается при случайном отображении), а на некоторый набор адресов. Все наборы пронумерованы. Поиск в кэш осуществляется вначале по номеру набора, полученному из адреса оперативной памяти из запроса, а затем в пределах набора путем ассоциативного просмотра всех записей в наборе на предмет совпадения старших частей адресов оперативной памяти(Рис.1.13)
стр.17
При промахе данные копируются по любому свободному адресу из
однозначно заданного набора. Если свободных адресов в наборе нет, то выполняется вытеснение данных. Поскольку кандидатов на выгрузку несколько (все записи из данного набора), алгоритм замещения может учесть интенсивность обращений к данным и тем самым повысить вероятность попаданий в будущем. Таким образом в данном способе комбинируется прямое отображение на набор и случайное отображение в пределах набора.
Кэш-память, какого типа называют наборно-ассоциативной (множественно- ассоциативной, частично - ассоциативной).
Схемы алгоритмов выполнения запросов в системах с кэш-памятью
На рис.1.14 приведен обобщенный алгоритм работы кэш-памяти.
Большая часть ветвей этой схемы уже была подробно рассмотрена выше, поэтому остановимся здесь только на некоторых особых случаях.
стр.18
Из схемы алгоритма видно, что когда выполняется запись, кэш
просматривается только с целью согласования его содержимого и
содержимого основной памяти. Если происходит промах, то запросы на
запись не вызывают никаких изменений в содержимом кэш. В некоторых же реализациях кэш-памяти при отсутствии данных в кэш они копируются туда из основной памяти независимо от того, выполняется запрос на чтение или на запись.
В соответствии с описанной логикой работы кэш-памяти следует, что при возникновении запроса сначала просматривается кэш, а затем, если произошел промах, выполняется обращение к основной памяти. Однако часто реализуется и другая схема работы кэш: поиск в кэш и в основной памяти начинается одновременно, а затем, в зависимости от результата просмотра кэш, операция в основной памяти либо продолжается, либо прерывается.
При выполнении запросов к оперативной памяти во многих
стр.19
вычислительных системах используется двухуровневое кэширование
(рис.1.15). Кэш первого уровня имеет меньший объем и более высокое
быстродействие, чем кэш второго уровня. Кэш второго уровня играет роль основной памяти по отношению к кэш первого уровня.
На рис. 1.16 показана схема алгоритма выполнения запроса на чтение в системе памяти с двухуровневым кэш. Сначала делается попытка обнаружить данные в кэш первого уровня. Если произошел промах, поиск продолжается в кэш второго уровня. Если же нужные данные отсутствуют и здесь, тогда происходит считывание данных из основной памяти. Очевидно,что время доступа к данным оказывается минимальным, когда кэш- попадание происходит уже на первом уровне, несколько большим - приобнаружении данных на втором уровне. И самое большое время доступа составляет обращение к оперативной памяти, если нужных данных нет ни в том, ни в другом кэш. При считывании данных из оперативной памяти происходит их копирование в кэш второго уровня, а если данные считываются из кэш второго уровня, то они копируются в кэш первого уровня.
При работе такой иерархической организованной памяти необходимо обеспечить непротиворечивость данных на всех уровнях. Кэш разных уровней могут согласовывать данные разными способами. Пусть, например, кэш первого уровня использует сквозную запись, а кэш второго уровня - обратную запись. (Именно такая комбинация алгоритмов согласования применена в процессоре Pentium при одном из возможных вариантов его работы.
стр.20
На рис. 1.17 приведена схема выполнения запроса на запись в такой
системе. При модификации данных необходимо убедиться, что они отсутствуют в кэш. В этом случае выполняется запись только в оперативную память.
стр.21
Если данные обнаружены в кэш первого уровня, то вступает в силу алгоритм сквозной записи: выполняется запись в кэш первого уровня и передается запрос на запись в кэш второго уровня, играющий в данном случае роль основной памяти. Запись в кэш второго уровня в соответствии с алгоритмом обратной записи, принятом на данном уровне, сопровождается установкой признака модификации, при этом никакой записи в оперативную память не производится.
Если данные найдены в кэш второго уровня, то, так же как и в
предыдущем случае, выполняется запись в этот кэш и устанавливается
признак модификации.
Рассмотренные в данном разделе проблемы кэширования охватывают только такой класс систем организации памяти, в котором на каждом уровне имеется одно кэширующее устройство. Существует и другой класс систем памяти, главной отличительной особенностью которого является наличие нескольких кэш одного уровня. Этот вариант характерен для распределенных систем обработки информации – мультипроцессорных системах и компьютерных сетях.
Одна из существенных проблем, возникающих при управлении кэш-
памятью, связана с коллективным использованием основной памяти.
Когда, как показано на рис. 1.18, основная память совместно используется несколькими процессорами, каналами обмена с ВЗУ и т. д., возможно возникновение конфликтов между кэш-памятями, между
стр.22
кэш-памятью и основной памятью, поэтому необходимы меры, обеспечивающие их согласованную работу (кэш когерентность).
Если в мультипроцессорной системе применяется сквозная запись в память, то при записи информации в какую-либо строку её адрес сообщается всем другим процессорам (а не только тому, в кэш которого выполняются изменения данных). В этих других процессорах проверяется, нет ли данной строки в их кэш и, если есть, то в дальнейшем информация этой строки во всех кэш считается недостоверной. При использовании сквозной записи управление производится таким образом, что обновление строки происходит только в кэш одного процессора, а в остальных процессорах эта строка считается недостоверной. При обращении для считывания информации к строке, содержимое которой обновлялось в кэш другого процессора, это обновленное содержимое передается в основную память, затем строка переносится в кэш, к которому имело место обращение для считывания, после чего происходит считывание.
Лекция №2