50527

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

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

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

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

Русский

2014-01-25

37 KB

6 чел.

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

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

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


 

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

7380. Изучение модуля процессора событий TIM08, и модуля таймера базового времени TMB08 251.5 KB
  Изучение модуля процессора событий TIM08, и модуля таймера базового времени TMB08 Цель работы: Изучить подсистему реального времени микропроцессора. Освоить методику выбора тактирующей последовательности и порядок программирования синт...
7381. Ведение бухгалтерского учета на практике в программе 1С: Бухгалтерия 226.5 KB
  Учетная политика предприятия - это совокупность способов ведения бухгалтерского и налогового учета, выбранная предприятием из различных вариантов, допускаемых законодательством. Поскольку существует некоторая свобода выбора, то, очевидно
7382. Выбор диодов СВЧ для конкретного применения. КР 795.5 KB
  Диоды арсенидогаллиевые, планарно-эпитаксиальные, параметрические. Предназначены для применения в параметрических усилителях сантиметрового диапазона длин волн. Выпускаются в металлическом корпусе с жесткими выводами.
7383. Эластичность спроса по ценам, доходам, перекрестная эластичность 204.08 KB
  Введение. Экономическая наука призвана определять, как максимально эффективно использовать ограниченные ресурсы - природные запасы, капиталы, трудовые резервы. Подробно всем другим отраслям знаний, экономика включает набор аксиом и доказательств, пр...
7384. Линейная алгебра и аналитическая геометрия 528 KB
  Линейная алгебра и аналитическая геометрия Задача 1. Дана система трех линейных уравнений. Найти решение ее двумя способами: методом Крамера и методом Гаусса. Решение методом Крамера. Запишем формулы Крамера...
7385. Космические и наземные системы радиосвязи и сети телерадиовещания. Проект цифровой радиорелейной линии 905 KB
  Космические и наземные системы радиосвязи и сети телерадиовещания Проект цифровой радиорелейной линии Введение Технология цифровых радиорелейных линий в настоящее время достигла высокого качественного и количественного развития. Сегодня радиорелейны...
7386. Моделирование мобильного телефона Google Nexus One в среде 3ds Studio Max 609.54 KB
  Содержание Введение 1. Техническое задание 1.1 Основание для разработки 2. Рабочий проект 2.1 Моделирование объектов 2.2 Построение корпуса 2.3 Построение нижней крышки корпуса 2.4 Построение верхней крышки корпуса 2.5 Добавление деталей 2.6 Примене...
7387. Проектирование дополнительных рабочих органов для плуга-лущильника ППЛ-10-25 131.86 KB
  В почвенно-климатических регионах Европейской части России с выпадением осадков более 500 мм в год, вспашка с оборотом пласта является наиболее эффективным приёмом основной обработки почвы. В сложившихся условиях дефицита минера...
7388. Визуальный контроль резервуара вертикального стального РВС-5000 32.27 MB
  Визуальный контроль резервуара вертикального стального РВС-5000 1. Эскиз резервуара Технические характеристики РВС 5000 м...