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


 

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

7910. Стереотипи та їх роль у житті людини і суспільства. Толерантність. Ксенофобія. Расизм 26.28 KB
  Стереотипи та їх роль у житті людини і суспільства. Толерантність. Ксенофобія. Расизм. Мета: розвивати готовність і потребу учнів до самопізнання і самореалізації своєї особистості визначити сутність понять стереотипи, толерантність формувати ...
7911. Засоби масової інформації та їх роль у суспільному житті 28.66 KB
  Засоби масової інформації та їх роль у суспільному житті Мета: дати знання про сутність понять інформація, ЗМІ, Інформаційна революція визначити основні види і функції ЗМІ розкрити роль ЗМІ у сучасному суспільному житті продовжити формування вмін...
7912. Особливості розвитку української культури. Освіта. Недільні школи в наддніпрянській Україні. Вищі навчальні заклади. Новоросійський університет 25.19 KB
  Особливості розвитку української культури. Освіта. Недільні школи в наддніпрянській Україні. Вищі навчальні заклади. Новоросійський університет Освіта в другій половині XIX ст.Чому освіту називають світлом життя? МЕТА:формувати вміння аналізув...
7913. Османська імперія та її зовнішня політика. Ослаблення Османської імперії. Перське царство. Правління Надир-шаха 24.12 KB
  Османська імперія та її зовнішня політика. Ослаблення Османської імперії. Перське царство. Правління Надир-шаха. Османська імперія і відсіч Європи. На початку XVI ст. Османська імперія перетворилася на могутню державу з великою територією. Піс...
7914. Утворення та зміцнення Московської держави 22.5 KB
  Утворення та зміцнення Московської держави МЕТА: створити умови для всебічного розуміння учнями всіх політичних та економічних процесів розвитку земель Північно - Східної Русі. розвивати вміння зіставляти та порівнювати інформацію з різни...
7915. Наука. Наукові товариства. М. Грушевський 22.56 KB
  Наука. Наукові товариства. М. Грушевський Мета: Створити умови для всебічного розуміння учнями всіх особливостей розвитку української науки розвивати вміння зіставляти та порівнювати інформацію з різних джерел, формулювати нескладні висновки та уза...
7916. Література. Драматургія. Архітектура та містобудування. Живопис. Музика. Музеї. Українські підприємці-благодійники. Родини Терещенків та Харитоненків 34.55 KB
  Література. Драматургія. Архітектура та містобудування. Живопис. Музика. Музеї. Українські підприємці-благодійники. Родини Терещенків та Харитоненків Мета: Створити умови для всебічного розуміння учнями всіх особливостей розвитку української культур...
7917. Фольклор та декоративно-ужиткове мистецтво. Повсякденне життя: звичаї, традиції, побут. Зміни у житті українських жінок. Особливості релігійного життя 26.35 KB
  Фольклор та декоративно-ужиткове мистецтво. Повсякденне життя: звичаї, традиції, побут. Зміни у житті українських жінок. Особливості релігійного життя МЕТА: розуміння учнями всіх особливостей розвитку народного мистецтва. пов...
7918. Поняття людини як біосоціальної істоти 22.26 KB
  Поняття людини як біосоціальної істоти Людина... Хто вона така? На перший погляд це питання зовсім просте. Хто ж не знає, хто така людина? Адже на рівні здорового глузду кожен з нас впевнено виділяє людину з оточуючого середовища, її відмінність від...