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


 

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

26473. Биоморфологические закономерности строения и развития организмов 27 KB
  Биоморфологические закономерности строения и развития организмов Организм – целостная живая система для которого прежде всего характерны целостность и дискретность. Общие принципы строения тела животного: биполярность билатеральность сегментарность закон трубкообразного строения большинство непарных органов расположены вдоль главной оси тела Основные законы биологического развития: Закон исторического филогенетического развития Шмальгаузен: в процессе развития постоянно происходит дифференцировка разделение функций клеток и тканей...
26474. Железы кожного покрова 45 KB
  На коже вымени: между бёдрами – молочное зеркало planum lactiferum или надвыменная область regio supramammaria Под кожей поверхностная фасция вымени беловатая пластинка из плотн. ткани соединительнотканная собственная оболочка долей вымени соединённая прослойками ткани внутри долей вымени – стромой stroma gl. mammaria между правой и левой половинами – подвешивающая связка вымени lig. suspensorium mammarium на месте связки снизу вымени – серединный жёлоб – sulcus intermammarius.
26475. Классификация костей 23.5 KB
  Классификация костей Оs longum длинные дугообразные рёбра трубчатые плечевая бедренная общий план строения: биэпифизарные дистальный эпифиз проксимальный эпифиз между эпифизами – тело кости – диафиз. Зона роста кости в длину – проксимальный и дистальный метафиз – между эпифизом и диафизом. Os longum короткие равны по длине высоте ширине состоят из компактного и губчатого вещества кости запястья и заплюсны основная функция – амортизация Os planum плоские или пластинчатые Имеют обширные...
26476. Кость как орган и её остеогенез 33.5 KB
  соли в кости меняется: Молодость: 1:1 Зрелость: 1:2 Старость: 1:7 кости твёрдые хрупкие С поверхности кость покрыта надкостницей periosteum: Наружный фиброзный слой защитная функция из плотной соединительной ткани содержит много коллагеновых волокон. продольно по отношению к главной оси кости. Костные перегородки остеоны расположены плотно что придаёт кости прочность сравнимую с прочностью гранита. Особо толстый слй компакты там где велики нагрузки кости на излом.
26477. Морфофункциональная характеристика волоса 35.5 KB
  Морфофункциональная характеристика волоса Волосы pili производные эпидермиса тонкие эластичные ороговевающие нити из ороговевшего или ороговевающего эпителия. волосы покрывают почти всё тело Фции: защита терморегуляторная орган осязания Волос состоит из: волосяная нить: стержень – scapus pili видимая часть корень – radix pili находится в толще кожного покрова корень переходит в луковицу волоса. волосяная сумка чехол в сумку открываются протоки сальных желёз Утолщение корня...
26478. Морфофункциональная характеристика кожного покрова 36.5 KB
  3 составляющих: кожа cutis слизистая оболочка tunica mycosa выстилает изнутри органы пищеварения дыхания размножения мочевыделения производные кожного покрова: железы потовые сальные молочные волосы перья чешуя мякиши роговые образования рога копыта когти СUTIS: epidermis располагается с поверхности представлен многослойным плоским ороговевающим эпителием dermis собственно кожа – дерма – соединительная ткань subcutis подкожный слой – соединительная ткань epidermis 2060мкм эктодермальное происхождение...
26479. Морфофункциональная характеристика мякиша 32 KB
  Морфофункциональная характеристика мякиша МЯКИШИ torus – упругие утолщения кожного покрова которые служат для опоры конечности о землю и обеспечивает амортизацию обладают большой чувствительностью осязание имеют хорошо развитый подкожный слой липоциты эласт. волокна располагаются на автоподиях Лошадь запястье пальмарно заплюсна плантарно каштаны пясть плюсна – шоры пальцевый мякиш стрелка внутри копыта Собака на грудной – запястные пястные пальцевые на тазовой – плюсневые пальцевые Свинья КРС...
26480. СПЛАНХНОЛОГИЯ 24.5 KB
  Внутренние органы оъединяют в 3 аппарата: пищеварительный: система органов пищеварения пищеварительный канал пищеварительные железы вспомогательный аппарат жевательные мышцы челюсти зубы мышцы брюшного пресса и т. дыхательный: система органов дыхания дыхательные пути – носовая полость глотка гортань трахея органы дыхания – лёгкие вспомогательный аппарат органы дыхыхательной распираторики – грудная клетка диафрагма мышцы брюшного пресса мочеполовой: почки мочевыводящие...
26481. МЫШЦЫ ГРУДНОЙ КЛЕТКИ 39.5 KB
  cerratus dorsalis craniflis i caudalis e поверхностная мышцы прикрывает мускулатуру позвоночного столба лежит дорсально в области холки в области поясницы закрепление различно у разных видов = инспиратор слабо развит у КРС экспираторнаиболее хорошо выражен у лошади и собаки иннервация – венральные ветви спинномозговых нервов межрёберные закрепляется широким апоневрозом на остистых отростках грудных позвонков 58 поясничных позвонков 15 закрепляются зубцами на верхней трети и теле рёбер Л – 512 КРС – 58...