Множественно-ассоциативное отображение

Ассоциативное отображение

На рис. 8.5 показана схема гораздо более гибкого метода отображения, согласно которому блок основной памяти можно помещать в любой блок кэша. При этом для идентификации хранящегося в кэше блока памяти необходимо иметь уже не 5, а 12 бит. При выполнении программы теговые биты сгенерированного процес­сором адреса по очереди сравниваются с теговыми битами каждого блока кэша. Если совпадение найдено, значит, содержащий данное слово блок уже присутст­вует в кэше. Такая технология называется ассоциативным отображением. Она предоставляет полную свободу выбора местоположения блока в кэше, благодаря чему пространство кэша может использоваться более эффективно. Новые блоки заменяют уже хранящиеся в кэше только в том случае, если кэш заполнен, причем для этой цели необходим алгоритм выбора удаляемого блока. Подобных алгорит­мов, как станет ясно из раздела 8.3.2, довольно много. Стоимость ассоциативного кэша выше, чем кэша с прямым отображением, поскольку в нем выполняется просмотр всех 128 тегов блоков. Поиск блока в кэше называется ассоциативным поиском. Для того чтобы он выполнялся достаточно быстро, теги должны про­сматриваться параллельно.

23. Кэширование. Множественно-ассоциативное отображение

Множественно-ассоциативное отображение

Технологии прямого и ассоциативного отображения могут использоваться со­вместно. В этом случае блоки кэша объединяются в множества, и каждый блок основной памяти может располагаться в любом из блоков определенного множе­ства. Причем вероятность конфликтов, являющихся одним из недостатков пря­мого отображения, значительно снижается. Такой кэш, получивший название множественно-ассоциативного, дешевле полностью ассоциативного кэша, по­скольку в нем уменьшена область ассоциативного поиска. Рассмотрим принцип множественно-ассоциативного отображения на примере кэша с 64 множествами по два блока в каждом (рис. 8.6). Блоки памяти 0, 64, 128,..., 4032 отображаются на множество 0 и могут занимать любую из двух позиций в этом множестве. На­личие 64 множеств блоков означает, что 6-разрядное поле множества в составе адреса слова определяет, какое множество кэша может содержать это слово. Поле тега адреса ассоциативным путем сравнивается с тегами двух блоков найденного множества, и если оно совпадет с одним из тегов, значит, соответствующий блок уже находится в кэше. Реализовать такой поиск очень просто.

Количество блоков во множестве задается в соответствии с требованиями кон­кретного компьютера. В случае основной памяти и кэша, показанных на рис. 8.6, для четырех блоков в множестве потребуется 5-разрядное поле множества, для восьми блоков — 4-разрядное и т. д. Граничное значение 128 блоков в множестве не требует поля множества и соответствует полностью ассоциативному кэшу с 12 те­говыми битами. Другое граничное значение — один блок в множестве — соответ­ствует методу прямого отображения. Кэш с k блоками во множестве называется k-канальным множественно-ассоциативным кэшем.

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

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

24. Кэширование. Алгоритмы замещения

Для использования алгоритма LRUконтроллер кэша должен отслеживать об­ращения ко всем блокам кэша. Предположим, что ему нужно следить за обраще­ниями к блоку LRU из четырехблочного множества множественно-ассоциатив­ного кэша. Для каждого блока может использоваться 2-разрядный счетчик. При попадании в кэш счетчик соответствующего блока устанавливается в 0. Счетчи­ки, значения которых были больше значения данного счетчика, увеличиваются на 1. Когда в кэше не оказывается нужного блока, а в множестве еще есть место, счетчик нового блока устанавливается в 0, а значения других счетчиков увеличи­ваются на 1. Если же множество заполнено, блок, счетчик которого равен 3, уда­ляется, а на его место помещается новый блок. Значения остальных трех счетчи­ков увеличиваются на 1. Нетрудно убедиться, что при использовании такого ал­горитма значения счетчиков четырех блоков всегда будут разными.

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

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

25. Организация памяти ЭВМ, виртуальная память

Под памятью ЭВМ понимаются запоминающие устройства (ЗУ). Стоимость памяти составляет существенную часть общей стоимости ЭВМ. Память ЭВМ имеет многоуровневую организацию:

- внутренняя (сверхоперативная (СВОП), кэш-память, ПЗУ, ОП).

Кэш-память, внутренняя память ЭВМ. В настоящее время память этого типа широко используется в мини-, общего назначения и супер-ЭВМ, а также в более мощных ПК. Кэш-память выполняется на быстродействующих БИС и её быстродействие должно соответствовать скорости работы АЛУ и УУ. Кэш-память используется для ранения наиболее часто используемых программ и данных, осуществляя своего рода связующий буфер между быстрыми устройствами ЦП и более медленной ОП и позволяя получать существенный временной выигрыш.

Оперативная память (ОП) служит для хранения информации (программы, данные, промежуточные и конечные результаты), непосредственно обеспечивающие текущий вычислительный процесс в АЛУ и УУ процессора. Информация в ОП сохраняется только при наличии питания (сеть, батарея); поэтому во избежание потери информации, используемые для наиболее важных работ ЭВМ различных классов обеспечиваются автономным блоком питания (UPS), который автоматически включается при отключении основного питания (переносные ПК). В процессе обработки информации осуществляется тесное взаимодействие ЦА и ОП под управлением первого: из ОП в ЦП поступают команды и операнды, над которыми производятся операции (определяемые их кодами в командах), а из ЦП в ОП записываются промежуточные и конечные результаты обработки. В настоящее время объём ОП колеблется в широком диапазоне, от 640Кбайт (для простых ПК), до нескольких гигабайт у супер-ЭВМ; время обращения к памяти менее 0, 2мкс; в качестве элементной используется в основном полупроводниковая база (диапазоны значений времени доступа в наносекундах: СВОП-5-15, кэш-10-50, ПЗУ-30-200, ОП-50-150). Развитие элементной базы постоянно корректирует эти показатели в сторону уменьшения; при этом скорость уменьшения увеличивается.

25.1 виртуальная память

Виртуализация оперативной памяти осуществляется совокупностью программных модулей ОС и аппаратных схем процессора и включает решение следующих задач:

размещение данных в запоминающих устройствах разного типа, например часть кодов программы-в-оперативной-памяти, а-часть-на диске;

выбор образов процессов или их частей для перемещения из оперативной памяти на диск и обратно;

перемещение-по-мере-необходимости-данных-между-памятью-и- диском;

преобразование виртуальных адресов в физические.

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

Виртуализация памяти может быть осуществлена на основе двух различных подходов:

свопинг (swapping) -образы процессов выгружаются на диск и возвращаются в оперативную память целиком;

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

26. Виртуальная память, преобразование адресов.

Виртуальная память – картина памяти, формируемая операционной системой для процесса (вспомним, что одна из функций ОС – предоставление виртуальной машины; естественно предположить, что память такой машины тоже должна быть виртуальной). Деятельность ОС по созданию такой картины правомерно назвать виртуализацией памяти.

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

Виртуальная память – это возможность адресовать пространство памяти, больше чем первичная память ЭВМ. Два класса схем структуризации – схемы страничной структуризации и схемы сегментной структуризации. Страничная структуризация: в каждую группу должно входить одинаковое число адресов. Группировку проводят последовательно от начала исходного адреса пространства в порядке возрастания адресов, и каждой вновь образованной странице присваивается номер. Второй шаг: производится перенумерация адресов в пределах каждой страницы и её рассматривают как отдельное адресное пространство. Адреса в пределах каждой страницы получают значения от 0 до 2^m-1(размер страницы) в порядке возрастания от начала страницы. Адреса внутри страницы – смещение. Адрес задаётся двумя координатами: номер страницы и смещение.

26.1.

Страничная организация – это преобразование адресов виртуальной памяти в адреса ОЗУ.

Процесс обращается по виртуальному адресу V=(p, d), где р – номер страницы, d – смещение. Необходимые страницы из ВЗУ переписываются в ОЗУ. Страница в ОЗУ называется кадром. Перемещаемая страница может быть в любом страничном кадре. Формируется таблица страниц, где строка представляет собой тройку- (r, s, p’). r – бит признака присутствия страницы, s – адрес внешней памяти, если страницы в ВЗУ нет, p’ – номер страничного кадра, если страница находится в ВЗУ.

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

Процесс обращается только по виртуальному адресу и преобразование происходит только когда страница находится в ОЗУ, т.к. существует другой механизм загрузки страниц. Механизм отображения страниц ищет номер страницы p в таблице отображения и находит p’. Путем конкатенации к p’ добавляется смещение и формируется физический адрес ОЗУ. Конкатенация – объединение 2-ичных изображений с целью получения третьего.

27.

Прерывания. Источники прерываний, средства управления прерываниями.

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

В зависимости от источника возникновения сигнала прерывания делятся на:

· асинхронные, или внешние (аппаратные) — события, которые исходят от внешних источников (например, периферийных устройств) и могут произойти в любой произвольный момент: сигнал от таймера, сетевой карты или дискового накопителя, нажатие клавиш клавиатуры, движение мыши. Факт возникновения в системе такого прерывания трактуется как запрос на прерывание (англ. Interrupt request, IRQ);

· синхронные, или внутренние — события в самом процессоре как результат нарушения каких-то условий при исполнении машинного кода: деление на ноль или переполнение стека, обращение к недопустимым адресам памяти или недопустимый код операции;

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

Термин «ловушка» (англ. trap) иногда используется как синоним термина «прерывание» или «внутреннее прерывание». Как правило, словоупотребление устанавливается в документации производителя конкретной архитектуры процессора.