Сетевые операционные системы

Глава 5. Управление памятью

Продолжение

Проблема согласования данных

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

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

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

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

Способы отображения основной памяти на кэш

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

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

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

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

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

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

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

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

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

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

Схемы выполнения запросов в системах с кэш-памятью

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

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

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

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

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

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

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

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

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

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

Продолжение следует...

В следующем выпуске:

• Выводы
• Задачи и упражнения