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

Question

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

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

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

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

Подробнее

Мой код Python | Проектный вопрос

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

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

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

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

• Повторять до тех пор, пока не будет сгенерирована ссылочная строка
  • выбрать m чисел в [p, p + e]. m имитирует или ссылается на количество ссылок на страницу
  • выбрать случайное число, 0 <= r <1 </li>
  • если г
    • генерировать новый 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), почему это может быть? Является ли это объяснением того, что по мере того, как стабильность становится низкой, количество ошибок на странице приближается к максимальному, поэтому не имеет большого значения размер рабочего набора?

Answer 1

Эти результаты являются разумными, учитывая вашу текущую реализацию. Однако обоснование этого требует некоторого обсуждения.

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

Давайте разберем ваш вопрос по алгоритму и изучим свойства их компонентов.в контексте:

1. FIFO показывает увеличение количества ошибок страницы при увеличении размера вашего рабочего набора (ось длины).

   Это правильное поведение, соответствующее аномалии Беладия для замены FIFO.По мере увеличения размера вашего рабочего набора страниц количество ошибок страниц также должно увеличиваться.

2. FIFO показывает увеличение количества ошибок страниц по мере стабильности системы ( 1 - ось глубины ) уменьшается .

   Принимая во внимание ваш алгоритм стабильности посева (if random.random() < stability), ваши результаты становятся менее стабильными в качестве стабильности ( S ) приближается 1. По мере того, как вы резко увеличиваете энтропию в своих данных, число ошибок страниц также резко увеличивается и распространяет аномалию Беладия.

   Пока чтотак хорошо.

3. LRU показывает соответствие с FIFO .Почему?

   Обратите внимание на ваш алгоритм заполнения. Стандарт LRU наиболее оптимален при наличии запросов на пейджинг, структурированных в меньшие операционные кадры.Для упорядоченных, предсказуемых поисков улучшается FIFO за счет устаревания результатов, которых больше нет в текущем кадре выполнения, , что является очень полезным свойством для поэтапного выполнения и инкапсулированной модальной операции.Опять же, пока, все хорошо.

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

   В результате ваша LRU воспринимает, что каждый элемент встречается небольшое количество раз, а затем полностью отбрасывается при вычислении следующего значения.Таким образом, он корректно отображает каждое значение, выпадающее из окна, обеспечивая производительность, сравнимую с FIFO .Если ваша система правильно учитывает повторяемость или сжатое пространство символов, вы увидите заметно отличающиеся результаты.

4. Для случайных, периода стабильности и размера рабочего набора неткажется, влияет на производительность на всех.Почему мы видим этот набросок по всему графику вместо того, чтобы дать нам относительно гладкое многообразие ?

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

   Или так?Для каждого набора записей вы случайным образом назначаете подмножество для постраничного вывода как функцию времени.Это должно обеспечить относительно равномерную производительность подкачки, независимо от стабильности и независимо от вашего рабочего набора, если ваш профиль доступа снова является равномерно случайным.

   Таким образом, в зависимости от условий, которые вы проверяете, это абсолютно правильное поведение соответствует тому, что мы ожидали .Вы получаете равномерную производительность подкачки, которая не ухудшается с другими факторами (но, наоборот, не улучшается ими), которая подходит для высокой нагрузки и эффективной работы.Неплохо, просто не то, что вы могли бы интуитивно ожидать.

Итак, в двух словах, это разбивка, так как ваш проект в настоящее время реализуется.

В качестве упражнения для дальнейшего изучения свойств этих алгоритмов в контексте различного расположения и распределения входных данных я настоятельно рекомендую углубиться в scipy.stats, чтобы увидеть, что, например,Гауссово или логистическое распределение может подойти к каждому графику.Затем я хотел бы вернуться к документированным ожиданиям каждого алгоритма и набросать случаи, когда каждый из них уникален наиболее и наименее уместен.

В целом, я думаю, ваш учитель будет гордиться.:)