Структура таблицы страниц
Организация таблицы страниц – один из ключевых элементов отображения адресов в страничной и сегментно-страничной схемах. Рассмотрим структуру таблицы страниц для случая страничной организации более подробно.
Итак, виртуальный адрес состоит из виртуального номера страницы и смещения. Номер записи в таблице страниц соответствует номеру виртуальной страницы. Размер записи колеблется от системы к системе, но чаще всего он составляет 32 бита. Из этой записи в таблице страниц находится номер кадра для данной виртуальной страницы, затем прибавляется смещение и формируется физический адрес. Помимо этого запись в таблице страниц содержит информацию об атрибутах страницы.
Формат конкретной записи в значительной мере зависит от машины, но виды представленной информации примерно одни и те же. На рис. 29 приведен образец записи таблицы страниц. Ее длина варьируется от компьютера к компьютеру, но 32 бита – это наиболее распространенный размер. Самым важным полем является поле номера страничного блока. При отображении страниц основной задачей является определение данной величины. За этим полем следует бит присутствия/отсутствия. Если этот бит равен 1, запись имеет силу и может использоваться. Если он равен 0, виртуальная страница, которой соответствует эта запись, в данный момент отсутствует в памяти. Обращение к записи в таблице страниц, где биту присутствия/отсутствия присвоено нулевое значение, приводит к ошибке отсутствия страницы.
Биты защиты говорят о том, какие виды доступа разрешены к этой странице. В простейшей форме это поле содержит один бит, равный 1 для чтения/записи и 0 только для чтения. Более сложные схемы имеют три бита, по одному для допуска каждой из операций чтения, записи и выполнения страницы.
Рис.29. Типичная запись таблицы страниц
Биты изменения и обращения отслеживают использование страницы. Когда страница записывается, аппаратура автоматически устанавливает бит изменения. Этот бит учитывается, когда операционная система решает освободить страничный блок. Если страница в нем была изменена (то есть она «грязная»), ее новая версия должна быть переписана на диск. Если она не была модифицирована (то есть страница «чистая»), ее можно просто удалить из памяти, так как все еще действительна копия на диске. Этот бит иногда называют грязным битом, так как он отражает состояние страницы.
Бит обращения устанавливается всякий раз, когда происходит обращение к странице для чтения или записи. Его значение помогает операционной системе при выборе страницы для удаления из памяти, когда случается ошибка отсутствия страницы. Страницы, не использующиеся в данный момент, являются лучшими кандидатами, чем находящиеся в работе. Этот бит играет важную роль в нескольких алгоритмах перемещения страниц. Наконец, последний бит позволяет запретить кэширование страницы. Данное свойство важно для страниц, отображающихся не на память, а на регистры устройств.
Адрес места на диске, где хранится страница тогда, когда она не находится в памяти, не является частью таблицы страниц. Причина очень проста. Таблица страниц содержит только ту информацию, которая нужна аппаратуре для преобразования виртуального адреса в физический. Информация, необходимая операционной системе для обработки ошибок отсутствия страниц, хранится в программных таблицах внутри самой ОС. Аппаратуре она не нужна.
Основную проблему для эффективной реализации таблицы страниц создают большие размеры виртуальных адресных пространств современных компьютеров, которые обычно определяются разрядностью архитектуры процессора. Самыми распространенными на сегодня являются 32-разрядные процессоры, позволяющие создавать виртуальные адресные пространства размером 4 Гбайт (для 64-разрядных компьютеров эта величина равна 264 байт). Кроме того, существует проблема скорости отображения, которая решается за счет использования так называемой ассоциативной памяти.0
Перемещение страниц по запросу (demand paging). Виртуальная память чаще всего реализуется на базе страничной организации памяти, совмещенной со свопингом (подкачкой) страниц.
Свопингу подвергаются только те страницы, которые необходимы процессору. Таким образом, перемещение страниц по запросу означает:
· программа может выполняться CPU, когда часть страниц находится в основной памяти, а часть – во внешней;
· в процессе выполнения новая страница не перемещается в основную память до тех пор, пока в ней не возникла необходимость.
Для учета распределения страниц между внешней и основной памятью каждая строка таблицы страниц дополняется битом местонахождения страницы (valid/invalid bit).
В том случае, если процессор пытается использовать страницу, помеченную значением invalid, возникает событие, называемое страничная недостаточность (paging fault).
Страничная недостаточность вызывает прерывание выполнения программы и передачу управления операционной системе. Реакция операционной системы на страничную недостаточность заключается в том, что необходимая страница загружается в основную память.
Основные этапы обработки страничной недостаточности (рис. 30.):
Рис. 30. Обработка страничной недостаточности
1) Процессор, прежде чем осуществлять преобразование логического адреса в физический, проверяет значение бита местонахождения необходимой страницы.
2) Если значение бита invalid, то процесс прерывается и управление передается операционной системе для обработки события страничная недостаточность.
3) Отыскивается необходимая страница во вторичной памяти и свободная страничная рамка в основной.
4) Требуемая страница загружается в выбранную страничную рамку.
5) После завершения операции загрузки редактируется соответствующая строка таблицы страниц, в которую вносится базовый адрес и значение бита местонахождения– valid.
6) Управление передается прерванному процессу.
Метод обмена страниц по запросу позволяет начать выполнение процесса даже в том случае, когда ни одна страница этого процесса не загружена в основную память.
Вторичная память, используемая при обмене страниц по запросу, – это высокоскоростное дисковое устройство, часто называемое оборудованием свопинга (swap device), а часть используемого дискового пространства – пространство свопинга (swap space).
Замещение страниц. В процессе обработки страничной недостаточности операционная система может обнаружить, что все страничные рамки основной памяти заняты и, следовательно, невозможно загрузить требуемую страницу. В этом случае возможны следующие режимы: приостановка прерванного процесса, уменьшение на единицу количества процессов мультипрограммной смеси для освобождения всех ею занимаемых страничных рамок, использование метода замещения страниц.
Метод замещения страниц состоит в том, что в основной памяти выбирается наименее важная/используемая страница, называется страница-жертва (victim page), которая временно перемещается в пространство свопинга, а на ее место загружается страница, вызываемая страничной недостаточностью.
Обработка страничной недостаточности с учетом замещения осуществляется по следующему алгоритму:
- определяется местонахождение страницы путем анализа бита местонахождения;
- если значение бита invalid, то разыскивается свободная страничная рамка;
- если имеется свободная страничная рамка, то она используется;
- если свободной страничной рамки нет, то используется алгоритм замещения, который выбирает страницу-жертву;
- страница-жертва перемещается в пространство свопинга и таблица страниц редактируется;
- требуемая страница загружается на место страницы-жертвы и соответствующим образом редактируется таблица страниц.
Управление передается прерванному процессу. Приведенный алгоритм замещения требует двухстраничных перемещений:
- страница-жертва перемещается в пространство свопинга;
- требуемая страница перемещается в освободившуюся страничную рамку.
Страницу-жертву можно не копировать в пространство свопинга в том случае, если за время, прошедшее от последнего перемещения, ее содержимое не модифицировалось. В этом случае время замещения уменьшается примерно вдвое.
Для учета факта модификации страницы в таблицу страниц вводится дополнительный бит, который меняет свое значение на противоположное в том случае, если содержимое страницы изменилось.
Для практического использования метода обмена страниц по запросу необходимы два алгоритма:
- алгоритм распределения страничных рамок (frame allocation algorithm);
- алгоритм замещения страниц (page replacement algorithm).