50527

Моделирование работы программ в виртуальной памяти и исследование эффективности их выполнения

Лабораторная работа

Информатика, кибернетика и программирование

Задание Собирать статистику работы по каждому исследуемому алгоритму для заданного ряда процентного объема физической памяти например 2510153550759095100 и всех алгоритмов вытеснения LRU FIFO OPT FRU. Выводы Сортировка выбором: трудоёмкость N2 2 алгоритм неадаптивный показатели эффективности алгоритмов LRU и FIFO практически одинаковы аномальный алгоритм замещения FRU превосходит по эффективности LRU и FIFO реально применимые алгоритмы LRU и FIFO уступают теоретическому максимуму в 23 раза что говорит об их...

Русский

2014-01-25

37 KB

7 чел.

Министерство Образования и Науки РФ

Новосибирский Государственный Технический Университет

Лабораторная работа №2

Тема: Моделирование работы программ в виртуальной памяти и исследование эффективности их выполнения

Выполнили:

Горбунов А.Ю.,

Туркин А.С.,

Бикбулатов Д.В.

Проверил:

Романов Е.Л.

2008


Цель работы

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

Задание

  •  Собирать статистику работы по каждому исследуемому алгоритму для заданного ряда процентного объема физической памяти (например, 2,5,10,15,35,50,75,90,95,100) и всех алгоритмов вытеснения (LRU, FIFO, OPT, FRU). Размерности массивов должны быть подобраны таким образом, чтобы была набрана достаточная статистика обращений (в диапазоне 1000 - 5000);
  •  Алгоритмы сортировки должны работать с массивами, заполненными случайными числами. Для одного выбранного значения процентного объема необходимо выполнить несколько (в пределах 10-20) прогонов модели, чтобы оценить диапазон изменений статистики (среднее и дисперсию). То же самое касается модели рабочего набора;
  •  Все полученные значения необходимо перенести в Excel и построить графики зависимости процента страничных прерываний от процентного объема физической памяти;
  •  Для моделей «рабочего набора» определить объем физической памяти, соответствующий рабочему набору программы на основе анализа результатов измерений (по изменению процента страничных прерываний);
  •  Для алгоритмов сортировки сделать выводы о сравнительной эффективности алгоритмов как с точки зрения трудоемкости (используя материалы курса СиАОД), но и с точки зрения эффективности их выполнения в виртуальной памяти. Необходимо также обосновать полученные результаты, проанализировав алгоритм (прежде всего с точки зрения свойства локальности);
  •  Сделать выводы об эффективности различных алгоритмов замещения. Обосновать полученные различия и «аномалии» (если такие наблюдаются) свойствами исследуемых алгоритмов.

Вариант

Алгоритмы сортировки: выбором, быстрая, рекурсивным слиянием.

Выводы

Сортировка выбором:

  •  трудоёмкость N2/2, алгоритм неадаптивный
  •  показатели эффективности алгоритмов LRU и FIFO практически одинаковы
  •  аномальный алгоритм замещения FRU превосходит по эффективности LRU и FIFO
  •  реально-применимые алгоритмы LRU и FIFO уступают теоретическому максимуму в 2-3 раза, что говорит об их непригодности
  •  увеличение объёма физической памяти мало улучшает эффективность работы
  •  сортировка выбором плоха как в плане использования процессорного времени, так и в плане работы с памятью и непригодна для работы с виртуальной памятью

Быстрая сортировка:

  •  линеарифмическая (n*log2n) трудоёмкость, алгоритм адаптивный
  •  алгоритмы замещёния LRU и FIFO в условиях малого объёма физической памяти уступают оптимальному алгоритму на 20…30%
  •  при большем объёме памяти LRU и FIFO проигрывают оптимальному алгоритму в 5 раз
  •  увеличение VФП в диапазоне до 0.8 VВП хорошо сказывается на быстродействии
  •  в рабочем диапазоне %ФП FIFO немного отстаёт от LRU
  •  аномальный алгоритм FRU в 8-10 раз хуже реально-применимых
  •  результаты для этой [адаптивной] сортировки на псевдослучайных данных нестабильны

Сортировка рекурсивным слиянием:

  •  линеарифмическая (n*log2n) трудоёмкость, алгоритм неадаптивный
  •  на малых объёмах ФП LRU и FIFO уступают оптимальному алгоритму на ~30%, при %ФП=35 и выше - вдвое
  •  на всём диапазоне FIFO немного превосходит по эффективности LRU
  •  увеличение VФП в диапазоне до 0.6 VВП очень хорошо сказывается на быстродействии
  •  аномальный алгоритм FRU в 8-10 раз хуже реально-применимых

Сравнение алгоритмов:

  •  эффективности работы с ВП у быстрой сортировки и сортировки рекурсивным слиянием немного отличаются только при %ФП < 20, далее – одинаковы
  •  оптимальными сочетаниями являются: при %ФП<40 – быстрая сортировка с замещением страниц по алгоритму FIFO; при %ФП>40 – рекурсивное слияние с замещением страниц по алгоритму FIFO.
  •  для алгоритма FRU сделать однозначный вывод невозможно. Эффективность его применения на некоторых алгоритмах сортировки (например, сортировка выбором) превосходит эффективность реально-применимых алгоритмов: LRU и FIFO. Невозможность применения этого алгоритма на практике объясняется тем, что применять его можно только для заранее известного алгоритма обращения к памяти.


 

А также другие работы, которые могут Вас заинтересовать

41714. Таблицы, сортировка таблиц, вычисление в таблицах в редакторе Word 54.82 KB
  С помощью Microsoft Grph можно создавать высококачественные информативные диаграммы и включать их в документы Word. Создание диаграммы Диаграммы строятся на основе данных содержащихся в таблице данных также внедряемой в документ Word. Можно создавать диаграммы четырнадцати основных и двадцати дополнительных типов. Тип диаграмм Правильный выбор типа диаграммы позволяет представить данные самым выигрышным образом.
41715. Ввод-вывод. Ветвления 168.52 KB
  Цель работы: Разработать алгоритм и написать программу на языке С++ для выполнения задания согласно номера бригады. Программа должна обеспечивать обмен с оператором, выдавая необходимые сообщения и позволяя вводить исходные данные и просмотреть результат выполнения программы.
41717. Снятие ВАХ стабилитрона 95.61 KB
  Стабилитроном-это диод, предназначенный для стабилизации уровня постоянного напряжения. По конструкции стабилитроны всегда плоскостные и кремниевые. Принцип действия стабилитрона основан на том, что на его вольт-амперной характеристике имеется участок, на котором напряжение практически не зависит от величины протекающего тока.
41718. Технология разборки автомобильных генераторов переменного тока 512.4 KB
  Оценка технического состояния отдельных деталей генератора и его работы в целом. До введення цієї системи позначення генератора містило букву Г Г250 і тому подібне а регулятора напруги – букви РР РР24 і тому подібне.5 Технологія розбирання генератора: Отримати набір інструментів необхідних для розбирання і збирання генератора типу Г–221.
41719. АНАЛИЗ ЧАСТОТНЫХ ХАРАКТЕРИСТИК ЗВЕНЬЕВ 52.99 KB
  Определить влияние коэффициентов входящих в описание каждого звена на характеристики ЧХ. Использование пакета MtLb Построение частотных характеристик звеньев с помощью программы MtLb Построение частотных характеристик в программе MtLb 7.0 1 выполняется аналогично построению временных характеристик в той же программе.
41721. ДИОДНЫЕ ОГРАНИЧИТЕЛИ И ФИКСАТОРЫ УРОВНЯ 340.36 KB
  В зависимости от схемы включения и режима работы нелинейного элемента ограничителя различают 3 вида ограничения: по максимуму ограничение сверху –рис.5 Диод ограничителя включается между входом и выходом схемы последовательно с нагрузкой. Если напряжение входного сигнала Uвх меньше напряжения смещения Е диод работает на обратной ветви характеристики где его внутреннее сопротивление велико и разделяет вход схемы от выхода. Форма напряжений на входе и выходе схемы иллюстрируется на рис.
41722. Подготовка и проведение измерений с помощью электронного мультиметра 200.19 KB
  Испытание однофазного трансформатора при работе под нагрузкой Методическое указание Самара Самарский государственный технический университет 2008 Печатается по решению Редакционно-издательского совета СамГТУ УДК621. 313 Испытание однофазного трансформатора при работе под нагрузкой: метод. Содержат практические рекомендации по экспериментальным методам определения основных характеристик однофазного трансформатора по обработке опытных данных и оформлению отчетов а также контрольные вопросы. Этот процесс...