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

Структура таблицы страничек, описанная в данном разделе, базируется на понятии хеш-функции (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.Инвертированные таблицы страничек.

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

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

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

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

Главные определения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для ускорения трансляции адресов употребляется ассоциативная память страничек (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. Реализуйте инвертированные таблицы страничек.


himicheskaya-klassifikaciya-mineralov-shpargalka.html
himicheskaya-promishlennost-bezopasnost-zhiznedeyatelnosti-tehnika-bezopasnosti-normativnaya-literatura.html
himicheskaya-promishlennost-v-f-voskoboev-akademiya-grazhdanskoj-zashiti-kafedra-ustojchivosti-ekonomiki-i-zhizneobespecheniya.html