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


 

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

3830. Внутренний фотоэффект в полупроводниках 95 KB
  Внутренний фотоэффект в полупроводниках. Цель работы. Определение опытным путем влияния освещенности на проводимость полупроводника и установление закона рекомбинации неосновных носителей заряда. Указания по организации самостоятельной работы....
3831. Определение удельной теплоемкости жидкости с помощью элекnрокалориметра 119.5 KB
  Определение удельной теплоемкости жидкости с помощью электрокалориметра Приборы и принадлежности Два электрокалориметра, два термометра, технические весы с разновесами, исследуемая жидкость, сосуд с водой. Теория работы и описание прибора Удельной т...
3832. Определение скорости монтажного патрона с помощью баллистического крутильного маятника 81 KB
  Определение скорости монтажного патрона с помощью баллистического крутильного маятника Цель работы - изучение законов сохранения на примере баллистического маятника. Приборы и принадлежности: баллистический крутильный маятник комплект монтажных пат...
3833. Дослідне вивчення властивостей математичного маятника. 96.5 KB
  Дослідне вивчення властивостей математичного маятника. Мета роботи: Перевірити справедливість формули періоду коливань математичного маятника для різних довжин маятника і різних кутів відхилення від положення рівноваги. Прилади і матеріали: Штатив...
3834. Исследование температурной зависимости электропроводности твердых тел 132 KB
  Исследование температурной зависимости электропроводности твердых тел/ Цель работы: Установление опытным путем законов изменения электропроводности твердых тел при их нагревании и определение энергии активации полупроводника. Теоретические исслед...
3835. Определение влажности воздуха 98.5 KB
  Определение влажности воздуха Приборы и принадлежности: Психрометр, барометр, пипетка и сосуд с водой. Теория работы и описание прибора Такие явления, как быстрота испарения, высыхание различных веществ, тканей, увядание растений, состояние организм...
3836. Определение удельной теплоты парообразования 135 KB
  Определение удельной теплоты парообразования Приборы и принадлежности: Кипятильник, сухопарник, термометр, штатив, технические весы, разновес, барометр-анероид, калориметр, сосуд с водой, стакан. Рис. 12 Теория работы и описание приборов Парообразов...
3837. Физический маятник 88 KB
  Цель работы: Экспериментальное определение физических характеристик колебаний физического и математического маятников. Имеется в виду сравнить экспериментальное и расчётное значение периода колебаний физического маятника и период колебаний математич...
3838. Определение ускорения свободного падения 146.5 KB
  Определение ускорения свободного падения Цель: Изучение динамики движения тел в поле гравитационного притяжения. Задача: измерение ускорения свободного падения с помощью математического и физического маятников Оборудование: универс...