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

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

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

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

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

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

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

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

СПЕЦИАЛЬНАЯ ЧАСТЬ

Назначение и функции программной системы

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

Основные объекты:

1) пациенты;

2.2. Системные требования

Для работы базы данных необходимы следующие ресурсы:

· процессор Pentium 133 или выше;

· минимальный объем оперативной памяти - 32 Мбайт;

· жесткий диск с объемом свободного пространства не менее 100 Мбайт;

· CD-ROM, клавиатура, мышь.

Для запуска данной базы данных требуется Visual Fox Fox Pro 6 и операционную систему: Windows 98/ME/NT 4.0/2000/XP.

Основные объекты данной информационной системы:

· «Сведения о врачах» - содержит данные о врачах;

· «Сведения о пациенте» - содержит личные данные пациента;

· «Учет поступления, выписок» - содержит информацию о диагнозе и времени пребывания пациентов в больнице.

Связывание таблиц

Access 2007 позволяет строить реляционные базы данных, отдельные таблицы которых могут быть связаны между собой.

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

Гораздо чаще встречается связь «один ко многим», при которой для каждой записи в одной таблице существует одна, несколько или ни одной записи в другой таблице.

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

С базе данных «Поликлиника» таблицы связаны друг с другом двумя связями «один ко многим».

Запросы

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

Таблица 3 «Функции и выполняемые операции»

Перечень запросов, применявшихся в данной базе данных приведен ниже.

Запрос «Врачи и их пациенты»

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

Запрос «Время пребывания в больнице»

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

Запрос «Пациенты-женщины»

Запрос «Пациенты-женщины» отображает пациентов женского пола

Запрос «Пациенты, лежавшие неоднократно»

Запрос «Пациенты, лежавшие неоднократно» выводит пациентов, которые лежали в больнице более одного раза.

Запрос «Пациенты-пенсионеры»

Запрос «Пациенты-пенсионеры» отображает всех пациентов, достигших пенсионного возраста.

Запрос «Подбор специальности врача по диагнозу»

Запрос «Подбор специальности врача по диагнозу» позволяет, путем ввода диагноза при запуске запроса определить специализирующегося на данной болезни врача.

Формы

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

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

Любая форма строится на основе Access-таблицы или запроса. Имена полей извлекаются из спецификации таблицы, а поля в форме можно расположить по своему усмотрению. На основе одной таблицы можно построить несколько форм.

В Access 2007 существует несколько способов создания форм:

Таблица 4 Способы создания форм

Существует несколько разновидностей автоформ:

Форма - создание формы для ввода данных по одной записи за раз

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

Несколько элементов - создание формы, в которой записи отображаются в виде таблицы, при этом каждая запись занимает отдельную строку

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

Перечень форм, применявшихся в данной работе приведен ниже:

Форма «История болезни»

Форма «История болезни» показывает данные больного, диагноз и дату поступления с данным диагнозом в больницу.

Главная кнопочная форма

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

Форма «Сведения о врачах»

Форма «Сведения о врачах» представлена в ленточном виде и показывает ФИО врача и его специальность.

Форма «Сведения о пациенте»

Форма «Сведения о пациенте» представляет собой ленточный тип формы, показывающей данные о пациенте.

Отчеты

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

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

Использование отчетов имеет следующие достоинства:

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

· отчет позволяет включать и печатать графические объекты (например, диаграммы);

· обеспечивается возможность работы с материалом, напечатанным на бумаге.

Отчеты можно создавать двумя способами:

1) при помощи мастеров отчетов/автоотчетов;

2) «вручную».

Отчет «Врачи по специальности»

Отчет «Врачи по специальности» построен в виде макета «структура» с уровнем группировки по специальности врача и отображает всех врачей поликлиники по конкретной сепциальности.

Отчет «Пациенты-пенсионеры»

Отчет «Пациенты-пенсионеры» показывает всех пациентов пенсионного возраста.

Отчет «Учет поступления, выписок»

Отчет «Учет поступления, выписок» выполнен с уровнем группировки представления данных по ФИО пациента и позволяет просмотреть данные о диагнозах, поступлениях и выписках пациентов

Макросы

Удобно разрабатывать макросы для автоматизации несложных процессов, таких как открытие и закрытие форм и отчетов, вывод на экран или печать документов и т.д. Окно макросов включает четыре столбца: Имя макроса, Условие, Макрокоманда, Аргументы, Примечание.

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

ЗАКЛЮЧЕНИЕ

Таким образом, в процессе проектирования базы данных, можно прийти к выводу, что правильная организация хранения и представления данных является неотъемлемой частью для успешного функционирования базы данных. Огромную роль в построении базы данных в MS Access играют такие полезные функции, как создание запросов, которые позволяют делать выборку необходимых полей из большой совокупности данных, а также производить арифметические и логические операции над этими полями.

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Дейт К. Дж. Введение в системы баз данных / Пер. с англ. 6-е изд. К.:Диалектика, 1999.

2. Замулин А. В. Системы программирования баз данных и знаний. Новосибирск.: Наука. Сиб. Отд., 2002.

3. Мартин Дж. Организация баз данных в вычислительных системах. / Пер. с англ. М.: Мир, 2000.

4. Романов Б. Л., Кушниренко А. С. dBase IV. Назначение, функции, применение. М.: Радио и баз данных, 1999.

5. Ульман Дж. Основы систем баз данных. М.: Финансы и статистика, 2003.

6. Бородаев В. А., Кустов В. Н. Банки и базы данных. Уч. пособие. Л.: ВИКИ, 2000.

7. Кузнецов С. Д. Введение в СУБД: часть 4.// Системы Управления Базами Данных, №4, 1999. - С. 114-122.

Страничная организация памяти применяется только в защищенном режиме , если в регистре управления CR0 бит PG = 1.

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

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

Для 32-разрядного микропроцессора:

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

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

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

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

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

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

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

Рис. 3.12. Принцип преобразования виртуального страничного адреса в физический

Рассмотрим пример преобразования адреса виртуальной страницы в адрес физической страницы. Пусть компьютер использует адресное пространство, предполагающее разбиение на страницы объемом V стр = 1I, и имеет оперативную память V ОЗУ = 3 страницы. Пусть на компьютере одновременно выполняются четыре программы, имеющие следующее количество страниц: V A = 2, V B = 1, V C = 3, V D = 2. Переключение между программами происходит через время кванта t k = 1. Время выполнения каждой страницы любой программы составляет t = 2t k . Полагаем, что страницы программ загружаются в оперативную память по мере необходимости и по возможности в свободные области ОЗУ. Если вся память занята, то новая страница замещает ту, к которой дольше всего не было обращений.

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

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

Таблица 3.2. Пример страничного распределения памяти в мультипрограммной ЭВМ

Страница

Такты

Динамическое распределение оперативной памяти

ОЗУ 0

АО

Таблица страничного преобразования для программы А

A 0

Таблица страничного преобразования для программы В

B 0

Таблица страничного преобразования для программы С

С 0

Таблица страничного преобразования для программы D

D 0

Если каждая страница имеет объем 1000 адресуемых ячеек, то, например, в такте 9 обращение по виртуальному адресу 1100 программы A (виртуальная страница 1, смещение в странице равно 100) приведет к обращению по физическому адресу 2100 (физическая страница 2, смещение в физической странице такое же, как и в виртуальной, то есть 100).

Рассмотрим теперь применение этих общих принципов страничного преобразования адреса в микропроцессоре с архитектурой IA-32 при объеме страницы в 4 Кбайт.

Основой страничного преобразования служит 32-разрядныйлинейный адрес , полученный на этапе сегментного преобразования логического адреса . Страничное преобразование выполняется при значении бита PG = 1 в управляющем регистре CR0.

В этом случае старшие 20 разрядов линейного адреса фактически представляют собой номер виртуальной страницы. Однако при прямом одноступенчатом преобразовании этого номера в номер физической страницы необходима таблица из 2 20 элементов длиной 4 байта каждый (20-разрядный номер страницы плюс некоторая дополнительная информация), т. е. 4 Мбайт. В мультипрограммной среде такая таблица может потребоваться для каждой задачи. Эта таблица должна постоянно храниться в оперативной памяти, чтобы существенно не увеличивать время формирования физического адреса. Для этих целей потребуется постоянное резервирование существенной части емкости ОЗУ, что на этапе появления первых ЭВМ на основе МП с архитектурой IA-32 было практически невозможно.

Вместо этого микропроцессор использует двухступенчатое страничное преобразование адреса. Корневая страница, называемая каталогом таблиц страниц (КТС), содержит 1024 32-разрядных элемента каталога таблиц страниц (ЭКТС - PDE page directory entry). Каждый из них адресует подчиненную таблицу страниц (ТС), то есть всего допускается до 1024 подчиненных таблиц страниц. Каждая из таблиц страниц содержит 1024 32-разрядных элемента таблицы страниц (ЭТС - PTE page table entry), каждый из которых и адресует физическую страницу. Таким образом, общее количество адресуемых физических страниц равно 2 20 , то есть все виртуальное адресное пространство (4 Кбайт * 220 элементов = 2 32 байт). Каждая таблица занимает 1024 4 = 4 Кбайт, то есть ровно 1 страницу. Общий объем таблиц, используемых для страничного преобразования, не уменьшился, а даже несколько возрос за счет использования каталога таблиц страниц. Однако, вопервых, практически всегда в системе этот размер можно существенно уменьшить за счет того, что некоторые линейные адреса никогда не будут сформированы (а эту информацию дают таблицы дескрипторов сегментов), и для них не нужно создавать таблицу страниц. А во-вторых, в оперативной памяти должны постоянно находиться лишь каталог таблиц страниц и таблица страниц выполняемой в настоящее время программы. Остальные таблицы страниц могут временно храниться во внешней памяти.

Рис. 3.13. Страничное преобразование линейного адреса в физический

Таким образом, преобразование линейного адреса в физический имеет вид, представленный на рис. 3.13.

Старшие 20 разрядов линейного адреса разбиваются на два 10-разрядных поля: поле номера элемента каталога таблиц страниц и поле номера элемента таблицы страниц . Так как и каталог таблиц страниц , и каждая таблица страниц занимают ровно 1 страницу и выровнены по границе страницы, то младшие 12 разрядов их базового адреса равны нулю, и для определения их физического адреса достаточно 20-разрядного поля.

Для каталога таблиц страниц его 20-разрядный адрес находится в регистре управления CR3. КТС постоянно находится в памяти и не участвует в свопинге.

Старшие 20 разрядов физического адреса таблицы страниц извлекаются из ЭТС. Структуры элемента КТС и элемента ТС схожи (рис. 3.14).

Рис. 3.14. Структура элементов каталога таблиц страниц и таблицы страниц

Старшие 20 разрядов элемента дают базовый адрес таблицы страниц (в ЭКТС) или физической страницы (в ЭТС). Биты P, A, R/W и U/S имеют определенное сходство с аналогичными атрибутами дескриптора сегмента, другие биты имеют специфическое назначение.

Бит присутствия P показывает, отображается ли адрес страничного кадра (таблицы страниц или страницы памяти) на страницу в физической памяти. При P = 1 страница присутствует в ОЗУ. При P = 0 страницы в памяти нет, и обращение к этой странице вызывает прерывание типа "страничное нарушение".

Бит доступа А устанавливается микропроцессором в состояние А = 1 при обращении к данному страничному кадру для записи или чтения информации.

Бит модификации D (Dirty - "грязный") устанавливается процессором равным 1 в элементе ЭТС при записи на данную страницу. Для элементов каталога таблиц страниц значение бита D является неопределенным. При загрузке страницы в память операционная система сбрасывает бит D. Если при необходимости выгрузки страницы во внешнюю память оказывается, что для нее D = 0, это означает, что к странице в памяти не было обращений на запись, во внешней памяти есть ее точная копия, и реально передавать страницу из памяти на диск не нужно. Тем самым экономится время при свопинге.

Бит чтения-записи R/W и бит U/S (user/supervisor - пользователь/супервизор) определяют права доступа к таблице страниц или к странице для программ с различными уровнями привилегий. Для страниц существует только 2 уровня привилегий: уровень супервизора (U/S = 0), соответствующий значению DPL сегмента 0, 1, 2, и уровень пользователя (U/S = 1), соответствующий DPL = 3. Если к странице осуществляется запрос с уровнем привилегий 3 (программы пользователя), то при значении U/S = 0 ему запрещается доступ к соответствующей таблице или странице. Если U/S = 1, то при значении R/W = 0 разрешается только чтение таблицы или страницы, а при R/W = 1 - и чтение, и запись.

При запросах с большими привилегиями (системные программные уровни 0, 1, 2) допускается з0апись и чтение таблиц и страниц при любых значениях U/S, R/W (табл. 3.3).

Биты PWT и PCD используются для управления работой кэш-памяти при страничной адресации. Бит PCD - запрещение кэширования страницы. При PCD = 1 кэширование запрещено. Бит PWT - бит обратной записи страниц. Определяет метод обновления внешней кэш-памяти (кэш 2-го уровня). При PWT= 1 - обновление проводится методом сквозной записи (как для внутреннего кэша), при PWT = 0 - методом обратной записи.

Биты 9…11 в ЭКТС и ЭТС зарезервированы за операционной системой. Процессор никогда не использует и не изменяет эти биты. Разработчики ОС могут привлечь эти биты для хранения информации о "старении" страниц, чтобы определять страницы, подлежащие замене из внешней памяти, и для других целей.

Старшие 10 разрядов линейного адреса совместно с содержимым регистра управления CR3 определяют необходимый элемент каталога таблиц страниц . Следующие 10 разрядов линейного адреса содержат номер элемента в выбранной таблице страниц.

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

Последние 12 разрядов линейного адреса содержат смещение в странице. Таким образом, сумма смещения в странице и базового адреса страницы, извлеченного из ЭТС, дает физический адрес искомого байта.

- 52.00 Кб

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подход на основе логических часов – ассоциирует с каждой строкой таблицы поле «время использования», а в ЦП добавляются логические часы. Логические часы увеличивают значение при каждом обращении к памяти. Каждый раз когда осуществляется ссылка на страницу, значение регистра логических часов копируется в поле «время использования». Заменяется страница с наименьшим значением в отмеченном поле путем сканирования всей таблицы станиц.
Подход на основе стека номеров страниц – стек номеров страниц хранит номера страниц, упорядоченных в соответствии с историей их использования, на «вершине» стека располагается только что использованная страница, а на «дне» дольше всех не используемая страница. Как только осуществляется ссылка на страницу, она перемещается на вершину стека, а номера всех страниц сдвигаются вниз.

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

Фрагментация

Фрагментация – это дробление памяти на мелкие не смежные свободные области маленького размера. Фрагментация возникает после выполнения системой большого числа запросов на память, таких, что размеры подходящих свободных участков памяти оказываются немного больше, чем требуемые. Например, если имеется 100 смежных свободных областей памяти по 1000 слов, то после выполнения 100 запросов на память по 999 слов каждый в списке свободной памяти останутся 1000 областей по одному слову.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Использования списка свободных фреймов иллюстрируется на рис. 16.6.

увеличить изображение
Рис. 16.6. Список свободных фреймов.

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

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

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

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

В системах с теговой архитектурой, например, "Эльбрус", регистр таблицы страниц (регистр таблицы страниц пользователя – РТСП) содержит дескриптор таблицы страниц, который, кроме ее адреса, содержит также ее длину.

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

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

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

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

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

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

Еще на эту тему:

Другие статьи: