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


 

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

84450. Правильна вимова слів із глухими приголосними. Складання казки за серією малюнків 72.5 KB
  Мета: працювати над засвоєнням правил вимови слів із глухими приголосними; розвивати вміння спостерігати аналізуватибудувати текст за малюнками розвивати мовлення; виховувати повагу до народних традицій. Обладнання: картки із словами та віршами прислів’я сюжетні малюнки.
84451. Весна прийшла 52 KB
  Мета. Розвивати у дітей мислення, вміння передавати свої думки зв’язним мовленням (усним та писемним), робити узагальнення, висновки, розвивати фантазію. Виховувати любов до природи, бережливе ставлення до неї.
84452. Закріплення й узагальнення знань про прикметник 49.5 KB
  Мета: закріпити і узагальнити знання з теми, збагачувати словниковий запас учнів; розвивати творче мислення; виховувати бережне ставлення до природи. Обладнання: малюнок «Весна», квіти, ребуси, ілюстрації, індивідуальні картки, ігри, телеграма.
84453. Загальне поняття про іменник. Іменники,що означають назви істот та назви неістот 42.5 KB
  Мета: розширити знання про іменник;вдосконалювати вміння виділяти його серед інших частин мови через правильно поставлене запитання; ознайомити з термінами назви істот і назви неістот; розвивати словниковий запас учніввиховувати навички грамотного письма.
84454. Узагальнення вивченого про частини мови 33.5 KB
  Розвивати навички відрізняти частини мови за їх лексичним значенням. Сьогодні на аукціоні незвичайний товар На моєму столі лежать картки з написаними назвами частин мови. Довірена особа від кожної групи розповідає про частину мови іменник.
84455. Складання розповіді за власним спостереженням «Жовте листячко летить, під ногами шелестить» 49.5 KB
  В жовтий лист пофарбувала Урожай з полів зібрала Золотила вербам коси Чарівна цариця Осінь Такце осінь вхід під музику дівчинки-осені Читання вірша: А я ішла по жовтим килимам По золотим червоним і багряним. Я - осінь. Я - осінь золота з легким туманом. Таке високе Як не милуватись...
84456. Слова з прямим і переносним значенням 38 KB
  Мета: формувати в учнів поняття про пряме і переносне значення слів; виробляти вміння визначати значення слова в тексті самостійно вживати слова в переносному значенні; розвивати мовне чуття навчити учнів звязно висловлювати свої думки.
84457. Зміна прикметників за зразком «один-багато» 147.5 KB
  Мета: активізувати знання учнів про прикметник. Формувати поняття про прикметник на основі істотних ознак (питання, значення, роль у реченні). Розвивати фонематичний слух, орфографічну грамотність. Виховувати любов до рідного краю, спадщини предків, пошани до народних традицій.
84458. Перевірка мовних знань і вмінь з теми «Іменник» 71 KB
  Послухайте вірш і зловіть зимові іменники хлопками. Чим цікаві виписані іменники повязані з зимовою порою Як вони називаються близькі за значенням 2 вручення сніжинки з буквою о Наступне завдання яке пропонує сніговичок це Робота в групах Гра Проціди крізь сито Розписати слова у 3 колонки.