- 52.00 Кб

Страничная организация памяти

Страничная организация памяти относится к методам несмежного размещения процессов в основной памяти. Она позволяет свести к минимуму общую фрагментацию за счет полного устранения внешней фрагментации и минимизации внутренней фрагментации. Эта форма организации виртуальной памяти во многом похожа на сегментную. Основные различия заключаются в том, что все страницы, в отличие от сегментов, имеют одинаковые размеры, а разбиение виртуального адресного пространства процесса на страницы выполняется системой автоматически. Типичный размер страницы – несколько килобайт. Для процессоров Pentium, например, страница равна 4 Кб.

Все виртуальные адреса одного процесса относятся к единому линейному пространству, проще сказать, виртуальный адрес выражается одним числом, от 0 до некоторого максимума. Старшие разряды двоичного представления этого адреса определяют номер виртуальной страницы, а младшие разряды – смещение от начала страницы. Например, для страниц по 4 Кб смещение занимает 12 младших разрядов адреса.

Физическая память также считается разбитой на части, размеры которых совпадают с размером виртуальной страницы. Эти части называются физическими страницами или страничными кадрами (page frames). Таблица страниц процесса по структуре похожа на таблицу сегментов. Для каждой виртуальной страницы она содержит: режим доступа, флаг присутствия страницы в памяти, номер страничного кадра, флаг чистоты. Если страница отсутствует в памяти, ее данные сохраняются в файле подкачки, который в этом случае чаще называют страничным файлом (page file).

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

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

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

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

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

Перемещение страниц по запросу

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

1. Программа может выполняться на ЦП, когда часть страниц находится в основной памяти, а часть во внешней;
2. В процессе выполнения новая страница не перемещается в основную память до тех пор, пока в ней не возникла необходимость.

Для учета распределения страниц между внешней и основной памятью каждая строка таблицы страниц дополняется битом местонахождения страницы (valid/invalid bit). В том случае если ЦП пытается использовать страницу, помеченную значением invalid, возникает событие, называемое страничной недостаточностью. Страничная недостаточность вызывает прерывание выполнения программы и передачу управления ОС. Реакция ОС на страничную недостаточность заключается в том, что необходимая страница загружается в основную память.

Основные этапы обработки страничной недостаточности:

1. ЦП, прежде чем осуществлять преобразование логического адреса в физический, проверяет значение бита местонахождения необходимой страницы.
2. Если значение бита invalid, то процесс прерывается и управление передается ОС для обработки события страничная недостаточность.
3. Отыскивается необходимая страница во вторичной памяти и свободная страничная рамка в основной.
4. Требуемая страница загружается в выбранную страничную рамку.
5. После завершения операции загрузки редактируется соответствующая строка таблицы страниц, в которую вносится базовый адрес и значение бита местонахождения – valid.
6. Управление передается прерванному процессу.

Метод замещения страниц

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

Обработка страничной недостаточности с учетом замещения:

1. Определяется местонахождение страницы путем анализа бита нахождения.
2. Если значение бита invalid, то разыскивается свободная страничная рамка.
3. Если имеется свободная страничная рамка, то она используется.
4. Если свободной страничной рамки нет, то используется алгоритм замещения, который выбирает страницу – жертву.
5. Страница – жертва перемещается в пространство свопинга и таблица страниц редактируется.
6. Требуемая страница загружается на место страницы – жертвы и соответствующим образом редактируется таблица страниц.

Для учета факта модификации страницы в таблицу страниц вводится дополнительный бит, который меняет свое значение на противоположное в том случае, если содержимое страницы изменилось.

Алгоритм распределения страничных рамок

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

1. FIFO (first in first out). Этот алгоритм ассоциирует с каждой страницей время, когда эта страница была помещена в память. Для замещения выбирается наиболее старая страница. Алгоритм учитывает только время нахождения страниц в памяти, но не учитывает используемость страницы.
2. Алгоритм LRU (least recently used). Он выбирает для замещения ту страницу, на которую не было ссылок на протяжении длительного периода времени. Он ассоциирует с каждой страницей время последнего использования этой страницы. Замещается та страница, которая дольше всех не использовалась. Применяется два подхода при внедрении этого алгоритма:
1. Подход на основе логических часов – ассоциирует с каждой строкой таблицы поле «время использования», а в ЦП добавляются логические часы. Логические часы увеличивают значение при каждом обращении к памяти. Каждый раз когда осуществляется ссылка на страницу, значение регистра логических часов копируется в поле «время использования». Заменяется страница с наименьшим значением в отмеченном поле путем сканирования всей таблицы станиц.
2. Подход на основе стека номеров страниц – стек номеров страниц хранит номера страниц, упорядоченных в соответствии с историей их использования, на «вершине» стека располагается только что использованная страница, а на «дне» дольше всех не используемая страница. Как только осуществляется ссылка на страницу, она перемещается на вершину стека, а номера всех страниц сдвигаются вниз.

Лекция 13, Страничная организация памяти

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

· сегментная;

· сегментно-страничная.

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

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

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

Каждый сегмент - линейная последовательность адресов от 0 до максимума. Различные сегменты могут иметь различные длины, которые могут меняться динамически (например, сегмент стека). В элементе таблицы сегментов помимо физического адреса начала сегмента (если виртуальный сегмент содержится в основной памяти) содержится длина сегмента. Если размер смещения в виртуальном адресе выходит за пределы размера сегмента, возникает прерывание.

Логический адрес - упорядоченная пара v=(s,d), номер сегмента и смещение внутри сегмента.

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

Рис. 11.2 Преобразование логического адреса при сегментной организации памяти.

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

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

Рис. 11.3 Формирование физического адреса при сегментно-страничной организации памяти.

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

Ассоциативная память.

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

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

Естественное решение - снабдить компьютер аппаратным устройством для отображения виртуальных страниц в физические без обращения к таблице страниц, то есть иметь небольшую, быструю кэш-память, хранящую необходимую на данный момент часть таблицы страниц. Это устройство называется ассоциативная память , иногда также употребляют термин ассоциативные регистры (иногда translation lookaside buffer (TLB)).

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

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

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

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

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

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

Например, предположим, что для доступа к таблице страниц необходимо 100 нс, а для доступа к ассоциативной памяти 20 нс. С 90% hit ratio среднее время доступа - 0.9*20+0.1*100 = 28 нс.

Вполне приемлемая производительность современных ОС доказывает эффективность использования ассоциативной памяти. Высокое значение вероятности нахождения данных в ассоциативной памяти связано с наличием у данных объективных свойств: пространственной и временной локальности.

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

Иерархия памяти.

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

Рассмотренная нами схема трехуровневой памяти (ассоциативная, основная, вторичная) является частным случаем многоуровневой памяти. На пример, как показано на рис. 11.5, разновидности памяти могут быть организованы в иерархию по убыванию скорости доступа и возрастанию цены.

.

Рис. 11.5 Иерархия памяти компьютера

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

Размер страницы

Дизайнеры ОС для существующих машин редко имеют возможность влиять на размер страницы. Однако для вновь создаваемых компьютеров решение относительно оптимального размера страницы является актуальным. Как и можно было ожидать нет одного наилучшего размера. Скорее есть набор факторов, влияющих на размер. Обычно размер страницы это степень двойки от 2**9 до 2**14 байт.

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

Как следует выбирать размер страницы? Во-первых, нужно учитывать размер таблицы страниц, здесь желателен большой размер страницы (страниц меньше, соответственно и таблица страниц меньше). С другой стороны память лучше утилизируется с маленьким размером страницы. В среднем половина последней страницы процесса пропадает. Необходимо также учитывать объем ввода-вывода для взаимодействия с внешней памятью и другие факторы. Проблема не имеет хорошего ответа. Историческая тенденция состоит в увеличении размера страницы. Как правило, размер страниц задается аппаратно, например, на Intel - это 4096 байт (или 4 Кбайт), на DEC PDP-11 - 8 Кбайт, на DEC VAX - 512 байт, на других архитектурах, таких как Motorola 68030, размер страниц может быть задан программно.

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

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

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

Для увеличения эффективности такого типа схем в процессорах используется специальная полностью ассоциативная кэш-память, которая также называется буфером преобразования адресов (TLB traнсlation-lookaside buffer). Хотя наличие TLB не меняет принципа построения схемы страничной организации, с точки зрения защиты памяти, необходимо предусмотреть возможность очистки его при переключении с одной программы на другую.

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

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

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

Сегментация памяти

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

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

Для реализации сегментации было предложено несколько схем, которые отличаются деталями реализации, но основаны на одних и тех же принципах.

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

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

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

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

Страничная организация виртуальной памяти

В большинстве современных операционных систем виртуальная память организуется с помощью страничной адресации. Оперативная память делится на страницы: области памяти фиксированной длины (например, 4096 байт), которые являются минимальной единицей выделяемой памяти (то есть даже запрос на 1 байт от приложения приведёт к выделению ему страницы памяти). Процесс обращается к памяти с помощью адреса виртуальной памяти, который содержит в себе номер страницы и смещение внутри страницы. Процессор преобразует номер виртуальной страницы в адрес соответствующей ей физической страницы при помощи буфера ассоциативной трансляции. Если ему не удалось это сделать, то требуется обращение к таблице страниц (так называемый Page Walk), что может сделать либо сам процессор, либо операционная система (в зависимости от архитектуры).

(слайд №12)

Рис. 16.4. Пример страничной организации.

Страничная организация (paging) – стратегия управления памятью, при которой:

· логическая память делится на страницы – смежные области одинаковой длины, обычно – степень 2 (например, 512 слов);

· физическая память, соответственно, делится на фреймы такого же размера;

· распределение логической памяти происходит с точностью до страницы;

· физическая память процесса может не быть непрерывной;

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

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

Цели страничной организации – обеспечить возможность не смежного распределения физической памяти для процессов, а также расширить пространство логической памяти.

На рис. 16.4 приведен пример страничной организации, который демонстрирует, что, в отличие от непрерывной логической памяти процесса, соответствующие фреймы страниц в основной памяти могут быть расположены не смежно: логической странице 0 соответствует фрейм 1, странице 1 – фрейм 4, странице 2 – фрейм 3, странице 3 – фрейм 7.

(слайд №13)

Рис. 16.5. Пример страничной организации блоками по 4 страницы.

На рис. 16.5 приведен другой возможный пример страничной организации: логическая и физическая память разбита на блоки по 4 страницы подряд; в таблице страниц хранится не номер страницы, а номер блока страниц. Например, в элементе 0 таблицы страниц хранится номер блока 5, по которому адрес начала блока вычисляется домножением содержимого элемента таблицы страниц на размер блока, равный 4 (результат – 20).

Реализация таблицы страниц

Использование ассоциативной памяти. Таблица страниц – непрерывная область физической памяти. В системе имеется базовый регистр таблицы страниц (page table base register – PTBR), указывающий на таблицу страниц и хранящий ее длину.

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

(слайд №14)

Рис. 16.3. Архитектура трансляции адресов при страничной организации.

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

(слайд №15)

Рис. 16.7. Схема трансляции адресов с использованием ассоциативной памяти.

Проблема двух обращений решается введением ассоциативной памяти (cache) страниц, называемой также буфер трансляции адресов (translation lookaside buffer – TLB). Ассоциативная память, по существу, является ассоциативным списком пар вида: (номер страницы, номер фрейма). Ее быстродействие значительно выше, чем у основной памяти и у регистров.

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

Модифицированная схема трансляции адресов с использованием TLB иллюстрируется рис. 16.7 .

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

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

Такой способ одно уровней адресации только для больших страниц 4мб используется только Ос, пользовательские приложения в такой в режиме не работают

Двухуровнивая адрессация. Для каждого приложения используется каталог страниц(Page Directory) и таблица страниц. В каталоге задаются адреса таблиц страниц. Весь адрес разделяется на 3 составляющие

А0 определяет смещения внутри страницы

А1 определяет номер строки в таблице строки(не более 1024 строк). Каждая такая строка должна содержать адрес начало страницы. Размер страниц также составляет 4кб, то есть одной странице.

В резульате такая таблица может задавать пространство 1024 страницы или 4мб. Если для како-го приложения известное памяти, можно определить количесвто страниц.

А2 определяет номер строки в каталоге страниц,(не болие 1024) размер тоже 4кб. В памяти обезательно должен присуствовать каталог, причем ардес его управляещго храниться в регистре CR2.При объедение А0 и А2 можно получить значения смещения внутри страницы, но большего размера.

Трехуровневая страничная адресация. Адрес разделяется на 4 компонента

А3	А2	А1	А0

Размер самой таблицы остается по 4кб но размер строки увеличивается в 2 раза.

А3 определяет одной из 4 таблицы каталога. При 3уровней страничной адрессаци можно использовать большие страницы 2 мб обеднив А1 А0 . наличия или отсутствие конкретной памяти отслеживает сам процесс с помощью механизма прерывания. Памятть для кодов программа, данных выделяться по страничной адрес начала страницы кратен его длине, если какой-то участок данных находиться в конце страницы создаеться новая страниц. При разработке критичных по памяти, нужно знать размер страницы и выравнивать, адрес начала страницы в том числе страницы и каталога всегда кратны размеру страницы, и по этму в любой из расмотреном варианте младший 12 бит адреса страницы свободны. В таблице используют для хранения дополнительной информации о страницы. Дополнительная информация о странице позволяет задать: признак тирпа страницы для записи или чтения, признак присутствия страницы в памяти, уровень привилегий страницы, признак были изменения в данной страницы(необходимо для анализа целостобрастности в случае ее сброса записать на диск, устанавливаеться просором при доступае тсрнице в режиме записи а сбрасывается программным анализом) признак, имел ли место доступ к данной страницы, режимы использования кеша. При использовании больших таблиц и страниц, в строке каталога указываеться что он соответствует на таблице а большой таблице. На паратном уровне процессор позволяет коретно использовать страницы трьох размеров, задавать режими доступа и уровень привелегий. Если страница осуствует в памяти процесор генерирует исключения которое обрабатывает ОС.

Действия обработчика исключений:

1) Найти свободную страницу или осводить занятую если свободных нет

2) Загрузить страницу в память

3) Записать адрес в Page Table при необходимости выполнить необходимости …

4) Обновить страницы кэш-страниц

5) Возвратиться к команде обращения памяти которая вызвала обрабатываемо исключения.

Задание страничной адресации (5 шагов+управляушие регистры)

Стратегия загрузки и выгрузки страниц

При использования регулярно надо решать такие вопрсы:

1) Определять какие именно нужно удалить из памяти

2) определить какие страницы загружены

3) определить методы загрузки выгрузки страницы

Страницы удаляться из памяти если для них не хватает объёма реальной памяти. Страницы занятые ядром ОС не выгружаются. Для решения вопрос по выгрузке страницы используеться такие подходы:

1) Оптимальный алгоритм – для выгрузки страницы выбирается страницы в которой не было не одного обращения. Недосток 6 необходими хнать историю работы с каждой таблицы.

2) Алгоритм с предварительным анализом, анализируется страницы, которые должны вызываться в очередных командах активных процессов. Страницы которые должны использоваться далее из памяти не выгружаются. Недостатки: нужен анализ процесов для определения необходимых им страниц.

3) Случайный – выгружаемая таблица определяется случайно, при этом информация для использования их или далие, но не исключено что информация может далие использоваться

4) Хронологический – выгружаются из памяти именно в том порядке в котором они были загружены. Недостакти: таблица может понадобиться.

5) Хронологический порядок с учетом использования(List R..Using)1 – выгражеться страница которая не использовалась большое времяю для определния таких страниц формируеться не очередь а список использованых таблиц. Использована записываеться в конец такого сиска, для выгрузки выбераються страницы первые в этом списке. Недостаток: может выгружена страница необходимая на следушим шаге выполнения. Он найболие часто используется в современных ОС.

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

Локальный мето допускает что для каждого процесса выделяються в соотвестви их рабочим множеством, алгоритм управлении страницами применяетьсядля каждой программы в пределах ее рабочего множества

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

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

1) Увеличения объема физической памяти

2) Ограничения количества активных процессов

3) Сокращения необходимого объёма памяти выделяемого для процесса

4) Специальный алгоритмы выделения страниц.

Механизмы управление памяти

Для работы с памяти используется 3 основных механизмов

1. Виртуальная память для работы с большими объемами

2. Отображения файлов на памяти(нужна быстра обработка или произвольна я обработки а также создния памяти разделяемой между процессами)

3. «Кучи» - механизм выделения небольших объемов памяти для приложения

Использования виртуальной памяти – для выделения регоина памяти(большого объема памяти) служит функция

LPVOID VirtualAlloc(

LPVOID lpAdress,//начальный адрес выделяемого участка(выравнивается на границу 64кб, если памяти выравнивается то адрес должен выровнены на начало страницу, при первом выделения памяти имеет значени NULL)

DWORD lpSize,//размер выделяемого памяти в кб (регион), если первый параметр NULLто ббудет увеличин до границы страницы

DWORD flAllcocationType,//тип операции выделения(либо одиночный или комбинаций флагов) таблица бондаренко 6,1 атрибуты ехе не поддерживается

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

Сиситаема инициализировать и разервирует,при попытке доступа к таклой памяти, после завершения процеса ОС освобождает все закрепленые за ним страницы. Функция VirtualAllocможет заново связать. Физическую памяти связаную с конткретнвми страницами можно освободить с помощью функции vitualFree. Для долговреной ного хранения памяти лучше выделать в страницах адресах. В этом случае в адресе передаться NULL и устанавливается флаги MEM_RESERVE, MEM_TOP_DOWN/ для резервирования под регион рекомендубъю задавать атрибут защиты наиболее общий. Выделяя виртуальной память можно задавать все атрибуты защиты кроме тех которые предназначены связаны с физической памяти: PAGE_WRITECOPY, PAGE_EXECUTE_WRITECOPY, PAGE_GUARD, PAGE_NOCAСHE.

Можно выделить не весь участка физической памяти только часть. Если размер выделяемой памяти совппадет с размеор связаной памяти то можно не 2 раза вызывать функцию а задавать флаги MEM_COMMIT|MEM_RESERVE. ДЛЯ возвращения физической памяти используеться фугкци мшкгфдаккус параметром адрес начала памяти, размер участка и MEM_DECOMMIT, если размер указать размер 0 то освобождается вся память, если в памяти происходить обращния то происходить ошибка. Для освобождения траниц существует 3 варианта

1. Предполагает что одной записи соответствует одной страницы, удаления такой записи освобождает страницу

2. Создаться битовая карта занятых записи

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

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

BOOL virtualProtect(

LPVOID lpAdress,//

DWORD flNewProtect,//новый атрибут защиты

DWORD lpflOldProtect//

Как правило вытеснения страниц вытесняется та которая долго не использовалась. Для блакирования траниц ыиспользуеться функция

LPVOID lpAdress,//

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

Бондаренко кучи(создании определения выделенной, полученияинобедения свобоныз блоков)