Структура таблицы страниц, описанная в данном разделе, базируется на понятии хеш-функции (hash function) - целочисленной функции hash, определенной на элементах s некоторого пространства поиска S(строках, больших числах и др.) и принимающей значения из отрезка [0, H-1] где H – натуральное число. Общая идея поиска с помощью хеш-функций заключается в следующем: пространство поиска разбивается наH непересекающихся подмножеств (списков) Sh, в каждом из которых хранятся элементы, имеющие одинаковое значение хеш-функции, равное h. Таким образом, применение хеш-функции позволяет сократить поиск в среднем в H раз: при поиске элемента s сначала вычисляем hash(s),а затем выполняем поиск только в списке Shash(s) Для облегчения доступа к хеш-спискам хранится также хеш-оглавление – таблица, индексируемая значением хеш-функции, каждый элемент которой содержит ссылку на начало соответствующего списка.
Хешированные таблицы страниц используются, если адресное пространство 64-битное или большей разрядности. Очевидно, что в этом случае, при прямолинейном подходе, размеры таблиц страниц оказались бы слишком велики. Поэтому используется другой метод. Логический номер страницы хешируется (т.е. для него вычисляется хеш- функция). Полученное число (реальный номер страницы) используется как индекс в хеш-оглавлении, ссылающемся на список страниц, хешируемых в один и тот же номер. В найденном таким образом списке и выполняется поиск нужной страницы. Данный способ организации таблицы страниц и схема адресации иллюстрируются рис. 11.
Рис. 11. Хешированные таблицы страниц.
Инвертированные таблицы страниц
Данный способ организации таблиц страниц предназначен для сокращения размеров таблиц страниц. В таблице страниц хранится один элемент для каждой реальной страницы, находящейся в памяти. К логическому адресу добавляется номер процесса (pid) владеющего данной страницей. По паре (номер процесса = pid, номер страницы = p) выполняется ассоциативный поиск в таблице страниц. Индекс найденного элемента таблицы i конкатенируется со смещением d внутри страницы, в результате получается физический адрес. Инвертированные таблицы страниц иллюстрируются рис. 12.
Рис.12. Инвертированные таблицы страниц.
Разделяемые страницы
Разделяемые (совместно используемые) страницы – логические страницы, используемые несколькими процессами и имеющие один и тот же номер в таблице страниц каждого из процессов. Данный механизм полезен для экономии памяти, так как позволяет загружать в память в единственном экземпляре не изменяемую информацию, необходимую нескольким процессам – например, код и массивы констант.
Пример использования разделяемых страниц тремя процессами приведен на рис. 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. Реализуйте инвертированные таблицы страниц.