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

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

Страничная организация памяти относится к методам несмежного размещения процессов в основной памяти. Она позволяет свести к  минимуму общую фрагментацию за счет полного устранения внешней фрагментации и минимизации внутренней фрагментации.  Эта форма организации виртуальной памяти во многом похожа на сегментную. Основные различия заключаются в том, что все страницы, в отличие от сегментов, имеют одинаковые размеры, а разбиение виртуального адресного пространства процесса на страницы выполняется системой автоматически. Типичный размер страницы – несколько килобайт. Для процессоров 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, Страничная организация памяти