В.А. Фисун - Прикладное программирование в задачах математической физики. Архитектурные принципы построения ЭВМ (pdf) (1127762), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

Фрагментация виртуальной памяти программы может производиться путем разделения её на блоки фиксированной длины, называемые страницами, или наблоки переменной длины, на сегменты. Размер сегментов определяетсяПособие 17.09.0929структурой задачи, каждый сегмент представляет собой отдельную логическую единицу информации, содержащую совокупность данных или программ. К сегментам можно обращаться по именам, в каждом из них устанавливается собственная нумерация слов, начиная с нуля.

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

В каждый момент выполнения программы на физическую память в ОЗУ отображаются только те виртуальныестраницы, которые используются программой в текущий момент.Остальные страницы виртуальной памяти хранятся во внешней памятив накопителях на жестких магнитных дисках. Управление оперативной памятью реализуется путем разбиения виртуальной и физической памяти наодинаковые страницы размером в 4 Кбайта (здесь и далее используются параметры микропроцессоров архитектуры IA32) и такими квантами производится перепись фрагментов виртуального пространства задачи с диска воперативную память процессора.

Такими же квантами производится перепись на диск результатов счета. После переписи фрагмента программ с магнитного диска в ОЗУ возникает проблема соответствия адресов виртуального пространства задачи - виртуальных адресов - адресам реального физического пространства микропроцессора - физическим адресам ОЗУ.Необходимое при этом отображение виртуальных адресов в физическиеадреса оперативной памяти обеспечивается специальным механизмомтрансляции адресов. При страничной организации памяти виртуальное пространство 4 Гбайт разделяется на блоки – страницы (page) размером в 4Кбайт, т.е.

на миллион виртуальных страниц. Виртуальный 32-разрядныйадрес байта представляется в виде двух полей: 20 старших разрядов определяют номер страницы, а 12 младших разрядов - сдвиг, смещение задают номер байта внутри этой страницы. Трансляция адресов заключается в замененомера виртуальной страницы на соответствующий номер страницы оперативной памяти – физической страницы.Трансляция адресов может производиться при помощи служебной таблицы страниц. Каждой странице виртуальной памяти соответствует строка втаблице страниц. В i строке таблицы для страниц, отображенных на физическую память, хранятся: N страницы физической памяти, которая соответствует данной виртуальной, статус доступа (чтение, запись), признак записи.Такая схема организации таблицы соответствия виртуальных и физических адресов носит модельный характер и не используется на практике из-забольшого объема таблицы, число строк в которой – миллион, большая частькоторых хранит признак “отсутствует в ОЗУ”.

Так как при мультипрограммном режиме работы на ЭВМ одновременно выполняются несколько программ, то общий размер таких служебных таблиц превысил бы разумныепределы.Пособие 17.09.0930Реальные схемы трансляции адресов используют двухуровневую систему таблиц, при которой виртуальный адрес страницы рассматривается какдва десятиразрядных поля. Первое поле указывает на строку каталога разделов, служебную страницу оперативной памяти, приданной каждой задаче.Строка каталога, в свою очередь, хранит ссылку на таблицу страниц, индексация которой вторым полем виртуального адреса страницы и дает искомыйадрес физической страницы. Таким образом, для выборки заданного байта, вобщем случае, необходимо три обращения к оперативной памяти (без использования аппарата кэш-памяти).Каталог раздела и таблицы страниц также имеют размер страницы, причем таблицы страниц формируются динамически, при обращении к очередному фрагменту виртуального пространства, который еще не представлен вОЗУ.

Формирование новой таблицы страниц производится при инициализации новой строки каталога, число служебных страниц возрастает только прибольшом разбросе значений виртуального адреса. Такая схема позволяетэкономить память для служебных таблиц, плата – дополнительные обращения к памяти.Механизм трансляции виртуальных адресов оптимизируется также сучетом принципа существования точек сгущения в исполняемых программах. Факт обращения к текущей странице и нескольким предшествующимвиртуальным страницам фиксируется в буфере TLB (Translation LocalsideBuffer). В буфере сохраняются также адреса соответствующих физическихстраниц, найденных по предыдущей схеме. Процесс трансляции виртуального адреса начинается с обращения к этому буферу.

Механизм TLB за одинтакт обращения к буферу выдает физический адрес страницы, если информация о запрашиваемой виртуальной странице находится в буфере. Времяработы TLB совмещается с выборкой заказанной информации из кэшпамяти, обращение к которой производится по содержимому поля смещения.При обращении к виртуальной странице, которой нет в оперативнойпамяти, она переписывается в физическую, возможно, предварительно отправив неиспользуемую в данный момент страницу на диск процедурой“своппинг”. Вопрос выбора страницы оперативной памяти для вытесненияиз пула рабочих страниц определяется выбранной стратегией подкачкистраниц.Наиболее часто реализуется механизм LRU (Least Recently Used), по которому вытесняется страница с самым “старым” обращением к ней из последних зафиксированных.

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

Тогда в голове очереди будет ссылка на страницу с самым“древним” обращением – кандидат на вытеснение.Алгоритм замещения страниц “первый вошел, первый вышел” 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-51-2-3-4-5, то в случае выделения ей четырех физических страниц в процессевыполнения задачи произойдет 10 подкачек, а на трех физических страницахпамяти задаче потребуется для работы даже на одну подкачку меньше, только девять подкачек.Алгоритм LFU (Least Frequently Used) может обеспечить сохранение воперативной памяти страницы с интенсивно используемым кодом – с циклом.

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

Характеристики

Список файлов книги