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


 

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

7591. Бюджет. Бюджетна система 61 KB
  ТЕМА 6. Бюджет. Бюджетна система Питання до лекції Економічна сутність та призначення бюджету, його функції. Склад доходів і видатків бюджету. Бюджетна система України та принципи її побудови. Бюджетний процес: сутність, хар...
7592. Семіотичний характер логіки. 39.5 KB
  Семіотичний характер логіки. Всю множину мов можна поділити на дві підмножини: природні і штучні мови. Природні мови виникають стихійно, в умовах практичної взаємодії між людьми. Вони використовуються насамперед з комунікативною метою як ефективний ...
7593. Логічний аналіз імен 43 KB
  Взагалі всі ознаки в логіці підрозділяються на відмінні і суттєві. Відмінна ознака відрізняє певні предмети від усіх інших. Суттєві ознаки виражають якісну специфіку предмета, його сутність. Кожна суттєва ознака є відмінною але не навпаки. У змісті імені фіксується лише суттєві ознаки.
7594. Операції з іменами 45 KB
  Поділ - це здійснення переходу від одного родового імені до множини родових імен. Це процес виявлення можливий родових імен. Ім'я, обсяг якого підлягає поділу, називається подільним. Видові імена, які отримані в результаті поділу і в яких зафіксовані результати поділу називаються членами поділу. Ознака, за якою обсяг подільного імені поділяється на обсяги видових імен, називається основою поділу
7595. Класична логіка висловлювань 56.5 KB
  Класична логіка висловлювань. Характерні ознаки класичної логіки висловлювань (=пропозиційної логіки) такі: 1) В межах пропозиційної логіки розглядаються лише такі міркування, засновки і висновки яких складаються із дескриптивних висловлювань....
7596. Моделі даних. Загальні поняття 105.5 KB
  Моделі даних Загальні поняття. Термін база данихговорить про те, що йдеться про дані, тобто про інформацію, яка характеризує певний об’єкт, та, що ці дані є базовими, основними. З погляду користувача, який екс...
7597. Проектування БД. Загальні поняття 90 KB
  Проектування БД Структура БД. Одним із найважливіших понять в теорії БД є архітектура і структура БД, які служать основою для розуміння можливостей сучасних СУБД. Розрізняють три рівні архітектури БД: внутрішній рівень найбі...
7598. Мова SQL. Загальна характеристика 116 KB
  Мова SQL Загальна характеристика. Як уже було сказано вище, обробка об’єктів БД виконуються мовою SQL, яка має певний набір команд. Команди SQL завжди починаються з дії (verb) - слова або групи слів, що описують задану операцію. Крім того,...
7599. Обмеження. Postgre SQL. 60 KB
  Обмеження Postgre SQL має декілька варіантів обмеження даних (constraint), які впливають на операції вставки і оновлення. Розглянемо один із них, який полягає в установці обмеженьдля таблиць і полів.Обмеженням є особливий атри...