В.А. Фисун - Прикладное программирование в задачах математической физики. Архитектурные принципы построения ЭВМ (doc) (1127760), страница 6
Текст из файла (страница 6)
Трансляция адресов может производиться при помощи служебной таблицы страниц. Каждой странице виртуальной памяти соответствует строка в таблице страниц. В i строке таблицы для страниц, отображенных на физическую память, хранятся: N страницы физической памяти, которая соответствует данной виртуальной, статус доступа (чтение, запись), признак записи.
Такая схема организации таблицы соответствия виртуальных и физических адресов носит модельный характер и не используется на практике из-за большого объема таблицы, число строк в которой – миллион, большая часть которых хранит признак “отсутствует в ОЗУ”. Так как при мультипрограммном режиме работы на ЭВМ одновременно выполняются несколько программ, то общий размер таких служебных таблиц превысил бы разумные пределы.
Реальные схемы трансляции адресов используют двухуровневую систему таблиц, при которой виртуальный адрес страницы рассматривается как два десятиразрядных поля. Первое поле указывает на строку каталога разделов, служебную страницу оперативной памяти, приданной каждой задаче. Строка каталога, в свою очередь, хранит ссылку на таблицу страниц, индексация которой вторым полем виртуального адреса страницы и дает искомый адрес физической страницы. Таким образом, для выборки заданного байта, в общем случае, необходимо три обращения к оперативной памяти (без использования аппарата кэш-памяти).
Каталог раздела и таблицы страниц также имеют размер страницы, причем таблицы страниц формируются динамически, при обращении к очередному фрагменту виртуального пространства, который еще не представлен в ОЗУ. Формирование новой таблицы страниц производится при инициализации новой строки каталога, число служебных страниц возрастает только при большом разбросе значений виртуального адреса. Такая схема позволяет экономить память для служебных таблиц, плата – дополнительные обращения к памяти.
Механизм трансляции виртуальных адресов оптимизируется также с учетом принципа существования точек сгущения в исполняемых программах. Факт обращения к текущей странице и нескольким предшествующим виртуальным страницам фиксируется в буфере TLB (Translation Localside Buffer). В буфере сохраняются также адреса соответствующих физических страниц, найденных по предыдущей схеме. Процесс трансляции виртуального адреса начинается с обращения к этому буферу. Механизм TLB за один такт обращения к буферу выдает физический адрес страницы, если информация о запрашиваемой виртуальной странице находится в буфере. Время работы TLB совмещается с выборкой заказанной информации из кэш-памяти, обращение к которой производится по содержимому поля смещения.
При обращении к виртуальной странице, которой нет в оперативной памяти, она переписывается в физическую, возможно, предварительно отправив неиспользуемую в данный момент страницу на диск процедурой “своппинг”. Вопрос выбора страницы оперативной памяти для вытеснения из пула рабочих страниц определяется выбранной стратегией подкачки страниц.
Наиболее часто реализуется механизм LRU (Least Recently Used), по которому вытесняется страница с самым “старым” обращением к ней из последних зафиксированных. Модельная реализация этого механизма такова. С каждой страницей пула физических страниц задачи связывается счетчик; все счетчики увеличиваются на единицу через каждую фиксированную единицу времени. При обращении к странице её счетчик обнуляется. При данной стратегии вытесняется страница с максимальным значением счетчика. Следующий вариант реализации данного механизма основан на списковых структурах. Можно устроить очередь из ссылок на страницы пула, перемещая в хвост очереди ссылку на страницу при каждом обращении к ней (к странице). Тогда в голове очереди будет ссылка на страницу с самым “древним” обращением – кандидат на вытеснение.
Алгоритм замещения страниц “первый вошел, первый вышел” FIFO (First In First Out) обеспечивается вытеснение страницы, находящейся в пуле дольше всех. Реализуется на списковых структурах по аналогии с предыдущей схемой, однако здесь положение страницы в очереди не изменяется при последующих обращениях к странице.
Алгоритм LFU (Least Frequently Used) обеспечивает вытеснение наименее часто используемой страницы, страницы с минимальным числом обращений. Каждая страница имеет счетчик, увеличивающий на единицу свое значение при каждом обращении к странице.
Наконец можно вытеснять страницы произвольным образом, по содержимому датчика случайных чисел.
Некоторые особенности перечисленных стратегий подкачек страниц.
Для наиболее часто реализуемого механизма LRU Э.Таненбаум приводит пример ”патологической ” ситуации. Пусть задача, использующая пять страниц, есть большой цикл, последовательно перебирающий виртуальные страницы: 1,2,3,4,5,1,2,3,4,5,1,.Если такой задаче дать пул из четырех физических страниц, то очередь первых четырех страниц в начале работы задачи имеет вид: <хвост списка> 4-3-2-1< голова списка> страниц. При переходе на пятую страницу вытесним первую страницу (подкачка пятой страницы на поле первой) из головы и очередь страниц будет иметь вид: 5-4-3-2. Переход в начало цикла, на первую страницу, также вызовет подкачку и очередь страниц будет иметь вид: 1-5-4-3. Далее везде, переход программы на новую страницу, всегда вызывает подкачку страницы.
Для алгоритма FIFO: “первый пришёл – первым ушёл” известен пример неэффективного использования ресурсов (аномалия Биледи). Если задача использует пять страниц и обращается к ним в таком порядке: 1-2-3-4-1-2-5-1-2-3-4-5, то в случае выделения ей четырех физических страниц в процессе выполнения задачи произойдет 10 подкачек, а на трех физических страницах памяти задаче потребуется для работы даже на одну подкачку меньше, только девять подкачек.
Алгоритм LFU (Least Frequently Used) может обеспечить сохранение в оперативной памяти страницы с интенсивно используемым кодом – с циклом. Однако, накопленные значения счетчиков будут грузом и при выходе из цикла будут блокировать вытеснение этих страниц. Модификация данной стратегии заключается в одновременном сдвиге всех счетчиков на один разряд в сторону младших разрядов через заданные промежутки времени. Данная схема может несколько скомпенсировать вес счетчиков мертвых страниц.
Описанные механизмы управления физической памятью реализуется средствами операционных систем процессора автоматически, они ”прозрачны”, не “видимы” для прикладного программиста.
3.4. Иерархическая структура оперативной памяти
Структуру памяти ЭВМ принято представлять в виде пирамиды, на гранях которой записана вся номенклатура памяти сообразно ее быстродействию и емкости. Ближе к вершине расположены наиболее быстрые компоненты, в основании пирамиды самые медленные, но зато самые емкие. Вот этот перечень:
1. Регистровая память.
2. Процессорный кэш (кэш первого уровня).
3. Кэши 2, 3 уровней.
4. ОЗУ.
5. Массовая память.
Память 1-4 уровней служит для кратковременного хранения информации, она есть память с произвольным доступом (Random Access Memory - RAM), которая допускает обращение к любому ее элементу в произвольном порядке. Ее реализация основана на электронике, то есть на управлении процессами записи и хранения информации электронными схемами. Для массовой памяти используются внешние запоминающие устройства.
Для ускорения доступа к оперативной памяти используется буферизация данных и объектного кода в специальной сверхоперативной памяти, скорость которой значительно выше основной оперативной памяти. Исходной посылкой для буферизации служит гипотеза о наличии в вычислительном процессе объективных свойств: пространственной и временной локальности (точек сгущения). Процессы стремятся исполнять команды небольшими порциями, которые именуются программными циклами или подпрограммами, используемые ими указатели группируются в информационном пространстве процесса. В этом состоит суть так называемого принципа "локальности" Деннинга [Denning]. Модель локальности состоит в том, что, когда процесс выполняется, он двигается от одной локальности к другой. Локальность в терминах виртуального пространства - набор страниц, которые активно используются вместе. Программа обычно состоит из нескольких различных локальностей, которые могут перекрываться.
Например, когда вызвана процедура, она определяет новую локальность, состоящую из инструкций процедуры, ее локальных переменных и множества глобальных переменных. После ее завершения процесс оставляет эту локальность, но может вернуться к ней вновь. Таким образом, локальность определяется кодом и данными программы. Итак, модель локальности - принцип, положенный в основу работы буферов. Если бы доступ к любым типам данных был случайным, то буферизация была бы бесполезной. Эффект от буферизации можно определить по среднему времени выборки: t = t2*p+ t1*(1-p), где t1 - среднее время доступа к данным основной памяти, t2 - среднее время доступа к данным из буфера (t2<t1), p - вероятность наличия данного в буфере. Очевидно, что среднее время зависит от вероятности р и изменяется от среднего времени доступа к основной памяти (при p=0) до среднего времени доступа непосредственно в буфер (при p=1). В качестве буфера используются регистровая память и кэш-память. Размер регистровой памяти может достигать нескольких Кбайт, кэш – более медленная память, но ее размер может измеряться Мегабайтами. Если регистровой памятью управляет программист в явном виде, то кэш-память "прозрачна" (невидима) для программиста, кэширование производится автоматически.
Прозрачностью кэш-памяти и обязана интерпретация слова кэш (cache), как тайник, тайный склад. По определению, эффект кэширования основан на предположении о многократном использовании данных (Data reuse) из кэш-памяти. Принято различать две формы многократного использования данных кэша: временное использование (temporal reuse) и пространственное использование (spatial reuse). Временное использование означает, что некоторое данное, загруженное в кэш, может использоваться, по крайней мере, более двух раз. Пространственное использование кэша предполагает возможность использовать некоторый пространственный набор данных, загруженных в кэш.
3.5. Кэш-память.
Механизм кэширования обеспечивает ускорение работы оперативного запоминающего устройства путем иерархического сочетания различных по быстродействию видов памяти и использования алгоритма кэширования для размещения данных. Кэш-память (cache, cache memory) – это память, как правило, на порядок более быстрая, чем основная, размещается в качестве буферной, между процессором и основной памятью - ОЗУ, и служит для временного хранения (в рамках своего объема) всех данных, потребляемых или генерируемых процессором. В многоуровневых кэшах элементами связки "процессор - основная память" могут выступать сами кэши. Считается, что технология кэш-памяти предложена Морисом Уилксом на основе идеи Гордона Скеротта в 1965 г.
Алгоритм кэширования состоит в следующем:
1. По каждому запросу процессора на чтение из ОЗУ команды или данного (числа, текстовой информации) происходит поиск требуемого данного в кэш- памяти (или места в кэше для записи генерируемого данного).
2. Если данное (место для записи) есть в кэше – кэш-попадание (cache hit) - то оно передается в процессор из кэша (записывается в кэш).
3. Если нужного данного нет в кэше – кэш-промах (cache miss) – то данное выбирается из основной памяти и пересылается в кэш память, а затем передается процессору. При переполнении кэша (нет места для записи) из него удаляется (модифицированные данные сохраняются в основной памяти) часть данных, обычно наименее востребованных.
Любой микропроцессор имеет "процессорный" кэш или кэш первого уровня (L1 Cache). Это буферная память объемом от 4 Кбайт до 16 Мбайт, в которой размещаются все данные и команды программы, адресуемые процессором, и из которой данные (команды) поставляются процессору. Эта память значительно быстрее основной памяти - ОЗУ, но меньшего объема, поэтому механизм кэширования обеспечивает обновление кэша, обычно сохраняя в нем только наиболее часто употребляемые данные. Обмен между основной и кэш памятями производится квантами, объемами 4 - 120 Кбайт. Копируются целиком "строки кэша" (cache line), содержащие данные (команды), адресуемое процессором.
Все адресуемые данные процессора, включая агрегатированные (двойные слова, вещественные числа одинарной и двойной точности), размещаются в строке кэша целиком (для режима с выравниванием данных в строках); в свою очередь, строка кэша может содержать несколько данных. Сегменты программного кода, на которые возможна передача управления, размещаются в начале строки кэша. Такое размещение информации по строкам кэша производится системами программирования автоматически, этот процесс называется “выравниванием данных”, он может быть заблокирован. Обычно программный код помещается в особый кэш, I-кэш – кэш-память, которая отделена от кэша данных - D-кэша. Выборка данных из кэша (hit time) производится обычно за один такт синхронизации (оценки: 1 - 4 такта), потери при кэш-промахе оцениваются в 8 - 32 такта, доля промахов (miss rate) в 1% -20%.
Кэш-память можно рассматривать как таблицу, содержащую копии последовательности байтов из оперативной памяти, причем с каждой строкой кэша при её заполнении ассоциируется адрес строки оперативной памяти. Оперативная память при этом также будет рассматриваться как двумерная таблица, состоящая из строк, каждая строка имеет свой номер – тег. Тег для процессоров архитектуры IА32 состоит из 25 битов, а размер строки кэша равен 32 байтам. Соответственно, адрес ОЗУ состоит из поля тега, содержимое которого задает номер строки кэша в памяти и поля сдвига, которое содержит указатель на заданный байт в этой строке. В заполненном кэше с каждой его строкой должен быть связан тег - номер соответствующей строки кэша в ОЗУ.
Типы связи определяют архитектуру кэша, которая разделяется на схемы: полностью ассоциативная, частично ассоциативная и кэш-память с прямым отображением.
Полностью ассоциативная кэш память (fully associative) реализуется механизмами ассоциативной памяти - АОУ. Кэш можно рассматривать как таблицу, состоящую из элементов вида: <тег><строка кэша>, где тег есть поле ключа, а строка кэши – данные, которые механизм ассоциативной памяти выдает при совпадении значения поля тега с запрашиваемым ключом – адресом строки кэша оперативной памяти. Каждая новая строка оперативной памяти будет размещаться в кэше до тех пор, пока не произойдет полного заполнения кэш-памяти. В этом случае, для размещения очередной строки будет вытеснена одна из занятых строк, алгоритмы вытеснения аналогичны алгоритмам подкачки страниц. Данный механизм по сравнению с другими наиболее полно использует кэш-память, но имеет громадный недостаток – объем ассоциативной памяти не может быть большим. Остальные схемы кэша моделируют ассоциативную память на адресной памяти, то есть реализуют хэш-функцию в той или иной форме.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
