Пейджинг: основной, иерархический, хэшированный и инвертированный - PullRequest
Новая
       86

Пейджинг: основной, иерархический, хэшированный и инвертированный

2 голосов
/ 05 апреля 2011

Что касается операционных систем и таблиц страниц, то, по-видимому, существует 4 основных способа разбивки на страницы и таблиц страниц

Basic - таблица с одной страницей, в которой хранится номер страницы и смещение

Иерархическая - многоуровневая таблица, которая разбивает виртуальный адрес на несколько частей

Хэширование - хэшированная таблица страниц, которая часто может включать несколько хэширований, сопоставляемых одной и той же записи

Inverted - логический адрес также включает PID, номер страницы и смещение. Затем PID используется для поиска страницы в таблице, а число строк в таблице добавляется к смещению, чтобы найти физический адрес для основной памяти. (Грубое и, вероятно, ужасное определение)

Мне просто интересно, каковы плюсы и минусы каждого метода? Кажется, что основной - это более простой метод, но он также может занимать больше места в памяти для большего адресного пространства. Что еще?

1 Ответ

2 голосов
/ 23 июля 2015

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

  • Basic может занимать много памяти (для современной системы, использующей 4 ГБ памяти, это может составлять до 300 МБ только для таблицы) и поэтому нецелесообразно.

  • Hierarchical значительно уменьшает эту память, добавляя только те таблицы, которые действительно используются. Тем не менее, у каждого процесса есть таблица корневых страниц. И если объем памяти процессов разрознен, все еще может быть много ненужных записей во вторичных таблицах. Это гораздо лучшее решение в отношении памяти, чем в Basic, и вводит лишь незначительное увеличение вычислений.

  • Хеширование не работает из-за коллизий хешей

  • Инвертированное решение - это решение для работы Hashed. Использование памяти очень мало (такое же, как базовая таблица для одного процесса, плюс некоторый PID и накладные расходы цепочки). Проблема заключается в том, что в случае коллизии хеша (несколько процессов используют один и тот же виртуальный адрес), вам придется следовать информации о цепочке (как в связанном списке), пока вы не найдете запись с соответствующим PID. Это может привести к большим вычислительным затратам в дополнение к хеш-вычислениям, но при этом будет занимать как можно меньший объем памяти.

...