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

ТЕМА 3. УПРАВЛЕНИЕ ПАМЯТЬЮ

 

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

План занятия:

1. Откачка и подкачка.

2. Смежное распределение памяти.

3. Общая задача распределения памяти и стратегии ее решения.

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

5. Страничная организация.

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

7. Оценка среднего времени доступа к памяти с использованием TLB.

8. Защита памяти.

9. Структура таблицы страниц.

10. Хешированные таблицы страниц.

11. Инвертированные таблицы страниц.

12. Разделяемые страницы

 

Откачка и подкачка

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

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

Файл откачки (backing store) -область дисковой памяти, используемая операционной системой для хранения образов откачанных процессов. Файл откачки организуется максимально эффективно: обеспечивается прямой доступ ко всем образам процессов в памяти (например, через таблицу по номеру процесса).

Популярная разновидность стратегии откачки и подкачки – roll out / roll in: откачка и подкачка на базе приоритетов; более приоритетные процессы исполняются, менее приоритетные – откачиваются на диск.

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

В распространенных ОС – UNIX, Linux, Windows и др. – реализованы различные стратегии откачки и подкачки.

Схема откачки и подкачки изображена на рис. 1.

Рис. 1. Схема откачки и подкачки.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

 

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

Рис.6. Список свободных фреймов.

 

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

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

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

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

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

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

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

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

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

Защита памяти

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

Организация защиты памяти процесса с помощью бита valid - invalid иллюстрируется на рис. 8.

Рис. 8. Бит valid-invalid в таблице страниц.

 

В примере процесс имеет 6 логических страниц с номерами от 0 до 5. Таблица страниц имеет длину 8 (с элементами от 0 до 7). Элементы 6 и 7 не соответствуют логическим страницам процесса, поэтому в них биты valid - invalid установлены в значение invalid. Поэтому при попытке обращения по логическому адресу с номером страницы 6 или 7 произойдет прерывание по неверной адресации.

Структура таблицы страниц

Иерархические таблицы страниц. Таблицы страниц в операционных системах могут быть по -разному организованы, при сохранении общих принципов их использования, описанных ранее. Рассмотрим далее три основных способа организации таблиц страниц – иерархические таблицы страниц, хешированные таблицы страниц и инвертированные таблицы страниц.

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

При обычной организации таблицы страниц, логический адрес (для 32-разрядной архитектуры, при размере страницы 4 килобайта = 4096 байтов) разбивается на номер страницы (20 битов) и смещение внутри страницы (12 битов).

При двухуровневой организации таблицы страниц, таблица страниц верхнего уровня сама делится на страницы, поэтому логический адрес будет иметь вид: (p1, p2, d),где p1 – индекс во внешней таблице страниц, p2 – смещение внутри страницы для внешней таблицы страниц, d – смещение внутри страницы (адресуемой по внутренней таблице страниц). При тех же предположениях об архитектуре и размере страницы, p1 и p2 будут занимать по 10 битов.

Организация двухуровневых таблиц страниц изображена на рис. 9.

Рис. 9. Организация двухуровневых таблиц страниц.

 

Схема адресной трансляции по двухуровневой таблице страниц иллюстрируется рис. 10.

Рис. 10. Схема адресной трансляции по двухуровневой таблице страниц.

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

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

Пример использования разделяемых страниц тремя процессами приведен на рис. 13. Три процесса используют одни и те же коды трех редакторов ed1, ed2, ed3, логические страницы которых имеют для обоих процессов номера 0, 1 и 2. Кроме того, каждый процесс использует свои индивидуальные данные data1, data2, data3.

Рис. 13. Разделяемые страницы.

Ключевые термины

Roll out / roll in - откачка и подкачка на базе приоритетов; более приоритетные процессы исполняются, менее приоритетные – откачиваются на диск.

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

Бит valid-invalid – бит в элементе таблицы страниц, указывающий, принадлежит ли страница логической памяти процесса.

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

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

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

Инвертированная таблица страниц – таблица страниц, при обращении к которой выполняется поиск требуемой физической страницы по номеру процесса и логическому номеру страницы.

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

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

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

Метод первого подходящего – метод решения общей задачи распределения памяти,при котором выбирается первый по списку свободный участок подходящего размера (не меньшего, чем n).

Общая задача распределения памяти - Имеется список свободных областей памяти и список занятых областей разного размера; реализовать оптимальный алгоритм выделения свободного смежного участка памяти длины n.

Откачка (swap out) - запись образа неактивного процесса на диск.

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

Подкачка (swap in) - считывание активного процесса с диска в основную память.

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

Регистр таблицы страниц (page table base register – PTBR) – регистр, указывающий на таблицу страниц и хранящий ее длину.

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

Cмежное распределение памяти – распределение памяти для пользовательских процессов в одной смежной области основной памяти.

Среднее время доступа (Effective Access Time - EAT) – оценка математического ожидания числа обращений к памяти при страничной организации.

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

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

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

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

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

Фрейм – образ страницы в основной памяти.

Хешированная таблица страниц – таблица страниц, при обращении к которой выполняется поиск, основанный на хешировании номера логической страницы.

Краткие итоги

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

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

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

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

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

Для реализации таблицы страниц в системе имеется регистр таблицы страниц, содержащий ее адрес и длину.

Для ускорения трансляции адресов используется ассоциативная память страниц (TLB).

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

Таблицы страниц бывают различной структуры – иерархические, хешированные и инвертированные. Хешированные таблицы страниц требуют поиска нужной страницы по хеш-списку. Инвертированные таблицы страниц требуют поиска нужной физической страницы по номеру процесса и логическому номеру страницы.

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

Вопросы для самопроверки:

1. Что такое откачка и подкачка?

2. Что такое файл откачки?

3. Как организовано смежное распределение памяти?

4. Как используется регистр перемещения для адресации?

5. Какие методы решения общей задачи распределения памяти Вам известны?

6. Что такое метод первого пододящего?

7. Что такое метод наиболее подходящего?

8. Что такое метод наименее подходящего?

9. Что такое фрагментация?

10. Что такое внешняя и внутренняя фрагментация?

11. Что такое компактировка и как с ее помощью избавиться от внешней фрагментации?

12. Что такое страничная организация?

13. Что такое страница?

14. Что такое таблица страниц?

15. Что такое фрейм?

16. Как осуществлятся трансляция адресов при страничной организации?

17. Что такое список свободных фреймов?

18. Что такое регистр таблицы страниц?

19. Как используется ассоциативная память для ускорения трансляции адресов при страничной организации?

20. Что такое среднее время доступа?

21. Что такое бит valid - invalid и как он используется для защиты памяти?

22. Какие Вам известны виды структур таблицы страниц?

23. Что такое иерархическая таблица страниц?

24. Что такое хешированная таблица страниц?

25. Что такое инвертированная таблица страниц?

26. Что такое разделяемые страницы и каково их назначение?

Упражнения

1. Реализуйте смежное распределение памяти.

2. Реализуйте методы первого подходящего, наиболее подходящего и наименее подходящего.

3. Реализуйте алгоритм компактировки основной памяти.

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

5. Реализуйте ассоциативную память страниц и операции над ней.

6. Реализуйте двухуровневые таблицы страниц.

7. Реализуйте хешированные таблицы страниц.

8. Реализуйте инвертированные таблицы страниц.

ТЕМА 3. УПРАВЛЕНИЕ ПАМЯТЬЮ

 

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

План занятия:

1. Откачка и подкачка.

2. Смежное распределение памяти.

3. Общая задача распределения памяти и стратегии ее решения.

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

5. Страничная организация.

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

7. Оценка среднего времени доступа к памяти с использованием TLB.

8. Защита памяти.

9. Структура таблицы страниц.

10. Хешированные таблицы страниц.

11. Инвертированные таблицы страниц.

12. Разделяемые страницы

 

Откачка и подкачка

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

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

Файл откачки (backing store) -область дисковой памяти, используемая операционной системой для хранения образов откачанных процессов. Файл откачки организуется максимально эффективно: обеспечивается прямой доступ ко всем образам процессов в памяти (например, через таблицу по номеру процесса).

Популярная разновидность стратегии откачки и подкачки – roll out / roll in: откачка и подкачка на базе приоритетов; более приоритетные процессы исполняются, менее приоритетные – откачиваются на диск.

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

В распространенных ОС – UNIX, Linux, Windows и др. – реализованы различные стратегии откачки и подкачки.

Схема откачки и подкачки изображена на рис. 1.

Рис. 1. Схема откачки и подкачки.