Пейджинг: базовый, иерархический, хэшированный и инвертированный
Что касается операционных систем и таблиц страниц, то, по-видимому, существует 4 основных метода для страниц и таблиц страниц.
Basic - таблица с одной страницей, в которой хранится номер страницы и смещение
Иерархическая - многоуровневая таблица, которая разбивает виртуальный адрес на несколько частей
Хэшированный - хэшированная таблица страниц, которая часто может включать несколько хэширований, сопоставляемых одной и той же записи.
Перевернутый - логический адрес также включает PID, номер страницы и смещение. Затем PID используется для поиска страницы в таблице, а число строк в таблице добавляется к смещению, чтобы найти физический адрес для основной памяти. (Грубое и, вероятно, ужасное определение)
Мне просто интересно, каковы плюсы и минусы каждого метода? Кажется, что основной - это более простой метод, но он также может занимать больше места в памяти для большего адресного пространства. Что-то еще?
1 ответ
Ключом к созданию пригодной для использования модели страницы является минимизация неиспользуемого пространства для ненужных записей. Вы хотите минимизировать объем необходимой памяти, сохраняя при этом низкую стоимость вычислений при поиске памяти.
Basic может занимать много памяти (для современной системы, использующей 4 ГБ памяти, что может составлять до 300 МБ только для таблицы), и поэтому нецелесообразно.
Hierarchical значительно уменьшает эту память, добавляя только те таблицы, которые действительно используются. Тем не менее, у каждого процесса есть таблица корневых страниц. И если объем памяти процессов разбросан, все еще может быть много ненужных записей во вторичных таблицах. Это гораздо лучшее решение в отношении памяти, чем в Basic, и вносит лишь незначительное увеличение вычислений.
Хеширование не работает из-за коллизий хешей
Inverted - это решение, которое заставит работать Hashed. Использование памяти очень мало (такое же, как базовая таблица для одного процесса, плюс некоторый PID и накладные расходы цепочки). Проблема заключается в том, что в случае коллизии хеша (несколько процессов используют один и тот же виртуальный адрес), вам придется следовать информации о цепочке (как в связанном списке), пока не найдете запись с совпадающим PID. Это может привести к большим вычислительным затратам в дополнение к хеш-вычислениям, но при этом будет занимать как можно меньший объем памяти.