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. Невозможность применения этого алгоритма на практике объясняется тем, что применять его можно только для заранее известного алгоритма обращения к памяти.


 

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

37441. Виды и средства измерений. Виды эталонов. Стандартные образцы 19.55 KB
  Прямые измерения — это непосредственное сравнение физической величины с ее единицей. Например, при определении длины предмета с помощью линейки происходит сравнение искомой величины (количественного выражения значения длины) с мерой, т. е. единицей измерения.
37442. Факторы, сохраняющие качество товаров 16.91 KB
  Режим хранения - это совокупность условий, при которых товар сохраняет свое качество. Для каждого товара необходим определенный режим хранения, зависящий от его состава и свойств. При правильном режиме не только сохраняется качество, но и снижаются потери товаров.
37443. Потребительские свойства товаров. Общие понятия и номенклатура потребительских свойств 17.07 KB
  Свойства товаров, обусловливающие их пригодность удовлетворять определенные потребности населения и проявляющиеся в процессе эксплуатации или потребления, называют потребительскими. В совокупности потребительские свойства составляют качество.
37444. Оценка качества товаров. Понятие и этапы оценки качества. Градации качества. Несоответствия и дефекты товаров 18.86 KB
  Оценка уровня качества — это совокупность операций, включающая выбор номенклатуры показателей качества оцениваемой продукции, определение значений этих показателей и сопоставление их с базовыми...
37445. Химический состав и свойства товаров 17.78 KB
  Медикобиологические требования к качеству продовольственных товаров — комплекс критериев, определяющих пищевую ценность и безопасность продовольственного сырья и продовольственных товаров.
37446. Сохраняющие факторы: упаковка товаров, транспортирование, хранение 18.84 KB
  Тара в зависимости от функционального назначения подразделяется на потребительскую и транспортную. В потребительскую тару расфасовывают продукцию (банка, бутылка, ампула, туба и др.)
37447. Средства товарной информации. Виды и формы 19.27 KB
  От того, насколько качественны эти информационные услуги, зависят скорость продвижения товаров по каналам распределения, интенсивность сбыта, стимулирование продаж, создание потребительских предпочтений и в конечном счете жизненный цикл товара
37448. Мастер общения. Советы практикующего психолога 439.5 KB
  Советы практикующего психолога ДУМАЕТЕ У ВАС НЕТ ЗАКОМПЛЕКСОВАННОСТИ В ОБЩЕНИИ Думаю что нет такс усмешкой и непоколебимой самоуверенностью обычно отвечают молодые люди. Но если ответ противоположный Как только представите себя в аудитории или на сцене так сразу все внутри заполняет липкий страх ногируки становятся деревянными во рту пересыхает перед глазами плывет Да и в обычном общении немало затруднений Вот тогда поспешите преодолеть закомплексованность в общении. В результате сформировалась новая задача вначале снять у...
37449. РЕШЕНИЕ ЗАДАЧИ ПОИСКА ОПТИМАЛЬНОГО МАРШРУТА ГРУЗОПЕРЕВОЗОК. СЕТЕВЫЕ ЗАДАЧИ 1.83 MB
  Mathematica — система компьютерной алгебры разработанная компанией Wolfram Research. Содержит множество функций как для аналитических преобразований, так и для численных расчётов. Кроме того, программа поддерживает работу с графикой и звуком, включая построение дву- и трёхмерных графиков функций, рисование произвольных геометрических фигур, импорт и экспорт изображений и звука.