Алгоритмы замены страниц виртуальной памяти

У меня есть проект, в котором меня попросили разработать приложение для имитации работы различных алгоритмов замены страниц (с различным размером рабочего набора и периодом стабильности). Мои результаты:

• Вертикальная ось: ошибки страницы
• Горизонтальная ось: размер рабочего набора
• Ось глубины: стабильный период

Приемлемы ли мои результаты? Я ожидал, что LRU даст лучшие результаты, чем FIFO. Здесь они примерно одинаковы.

Кажется, что для случайной выборки период стабильности и размер рабочего набора вообще не влияют на производительность? Я ожидал таких же графиков, как FIFO и LRU, просто худшая производительность? Если эталонная строка очень стабильна (маленькие ветки) и имеет небольшой размер рабочего набора, она все равно должна иметь меньше ошибок страниц, чем приложение с большим количеством ветвей и большим размером рабочего набора?

Подробнее

Мой код Python|Вопрос проекта

• Длина строки ссылки (RS): 200 000
• Размер виртуальной памяти (P): 1000
• Размер основной памяти (F): 100
• количество страниц времени, на которые ссылаются (m): 100
• Размер рабочего набора (e): 2–100
• Стабильность (t): 0–1

Размер рабочего набора (e) и период стабильности (t) влияют на то, как эталонная строка сгенерировано.

|-----------|--------|------------------------------------|
0           p        p+e                                  P-1

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

• Повторяйте до тех пор, пока не будет сгенерирована ссылочная строка.
  • выбрать mчисел в [p, p+e]. mимитирует или ссылается на количество ссылок на страницу
  • выбирает случайное число, 0
  • если r
  • сгенерировать новый p
  • else (++p)%P

ОБНОВЛЕНИЕ (в ответ на ответ @MrGomez)

Однако вспомните, как вы заполняли входные данные: используя random.random, тем самым давая вам равномерное распределение данных с вашим контролируемым уровень энтропии. Из-за этого все значения с равной вероятностью происходят, и поскольку вы построили это в пространстве с плавающей запятой, рецидивы крайне маловероятны.

Я использую random, но это тоже не полностью случайно, ссылки генерируются с некоторой локальностью, несмотря на использование параметров размера рабочего набора и количества страниц?

Я попытался увеличить относительную numPageReferencedна numFramesв надежде, что она будет больше ссылаться на страницу, находящуюся в данный момент в памяти, тем самым показывая преимущество LRU в производительности по сравнению с FIFO, но это не помогло. т дать мне четкий результат хотя. Просто к вашему сведению, я попробовал то же приложение со следующими параметрами (соотношение страниц/кадров осталось прежним, я уменьшил размер данных, чтобы ускорить работу).

--numReferences 1000 --numPages 100 --numFrames 10 --numPageReferenced 20

Результат

Всё-таки не такая уж большая разница.Правильно ли я говорю, что если я увеличу numPageReferencedпо сравнению с numFrames, LRU должен иметь лучшую производительность, поскольку он больше ссылается на страницы в памяти? А может я что-то не так понимаю?

Что касается случайности, я думаю примерно так:

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

Хм, может быть, я должен подумать об этом больше :)

ОБНОВЛЕНИЕ: Мусор менее заметен при более низкой стабильности

Здесь я пытаюсь показать, что размер рабочего набора превышает количество кадров (100) в объем памяти. Однако при более низкой стабильности (высокий t) прерывистый бросок кажется менее очевидным, почему это может быть? Объясняется ли это тем, что по мере того, как стабильность становится низкой, количество ошибок страниц приближается к максимуму, поэтому не так важно, каков размер рабочего набора?