Лекции по "Криптология "

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

 Сквозная запись (write through).

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

Оглавление

Лекция 16. Структура системы ввода-вывода. Функции базовой подсистемы ввода-вывода. 1

Логические принципы организации ввода-вывода 1

Структура системы ввода-вывода 1

Функции базовой подсистемы ввода-вывода 4

Буферизация и кэширование 5

Spooling и захват устройств. 6

Обработка прерываний и ошибок 6

Планирование запросов 7

Лекция 15. Система управления вводом-выводом. Физические принципы организации ввода-вывода. Общие сведения об архитектуре компьютера. Структура контроллера устройства. Опрос устройств и прерывания. 8

Физические принципы организации ввода-вывода 8

Общие сведения об архитектуре компьютера 8

Структура контроллера устройства 10

Опрос устройств и прерывания. Исключительные ситуации и системные вызовы 11

Для внешних прерываний характерны следующие особенности: 13

Прямой доступ к памяти (Direct Memory Access – DMA) 14

Лекция 14. Загрузка программ. Абсолютная загрузка. Относительная загрузка. Позиционно-независимый код. Загрузка ОС. Сборка программ. 15

Загрузка программ 15

Абсолютная загрузка 15

Абсолютная загрузка используется, например, в системе UNIX на 32-разрядных машинах. 16

Относительная загрузка 16

Позиционно-независимый код 17

Загрузка ОС 17

Пример: Загрузка системы MS-DOS. 20

Сборка программ 21

Объектный модуль 21