50500

Моделирование работы программ в виртуальной памяти и исследование эффективности их выполнения

Лабораторная работа

Информатика, кибернетика и программирование

Имитационная модель страничных прерываний Программа моделирует процесс обработки страничных прерываний и выполнение алгоритмов замещения страниц при их отсутствии в физической памяти. Модель реализована в классе VM который сохраняет последовательность обращений к памяти исследуемого алгоритма трассировка и моделирует по ней страничные прерывания и алгоритмы замещения собирая при этом статистику. Для моделирования обращения к памяти используется метод VM::ccessint ddr int write который получает адрес обращения обычно это индекс в...

Русский

2014-01-24

86.5 KB

13 чел.

Операционные системы

Лабораторная работа «Моделирование работы программ в виртуальной памяти и исследование эффективности их выполнения»

Цель работы

Целью работы является изучение принципов организации виртуальной памяти, механизма страничных прерываний и алгоритмов замещения страниц, а также исследование эффективности работы различных алгоритмов в системе виртуальной памяти.

Имитационная модель страничных прерываний

Программа моделирует процесс обработки страничных прерываний и выполнение алгоритмов замещения страниц при их отсутствии в физической памяти. Модель реализована в классе VM, который сохраняет последовательность обращений к памяти исследуемого алгоритма (трассировка) и моделирует по ней страничные прерывания и алгоритмы замещения, собирая при этом статистику. В данной лабораторной работе исследуются свойства программ, работающих с массивами, в частности, алгоритмов сортировки, и собирается статистика по обращению программы к одному (или нескольким) массивам. Обращения к сегменту команд за программным кодом и к сегменту стека за локальными переменными в данном случае происходят в ограниченном пространстве адресов и при моделировании не учитываются.

Для моделирования обращения к памяти используется метод VM::access(int addr, int write), который получает адрес обращения  (обычно это индекс в массиве) и признак обращения по записи. Эти данные дописываются в динамический массив trace. По окончании моделирования вызывается метод VM::show(), который вызывает метод VM::proc() для обработки полученной трассы.

Для работы с моделью в исследуемой программе необходимо определить объект класса VM, конструктор которого содержит параметры модели:

- int per_pg – количество элементов массива на одной странице. Реальный размер физической страницы – 4Кб, поэтому на практике на одной странице размещаются 1024 целых 32-разрядных числа. В модели достаточно использовать грубое приближение (5-10 элементов на страницу). Это позволяет сохранить свойства моделируемого процесса, представляя его с некоторым «огрублением» (при 5 элементах один элемент массива соответствует 20 элементам реального). Соответственно, в 20 раз будет больше размерность реального массива в отличие от моделируемого;

- int sz0 – размерность массива, с которым работает программа (объем виртуальной памяти);

- int procent объем физической памяти (или рабочего набора физических страниц) в процентах к размерности массива (целое число 1..100);

- int mode0 – алгоритм замещения (0 – LRU, 1-FIFO, 2-OPT)

В текст моделируемого алгоритма необходимо внести соответствующие добавления (обратите внимание, что повторное чтение того же элемента массива не учитывается, предполагается, что алгоритм оптимизирован и читает необходимые данные в локальную память):


//-----------Пример сортировки выбором------------------------------------------

void sort2(int A[], int n, VM &T){

for (int i=0;i<n;i++){

T.VM_access(i,0);          // Чтение i-го элемента

int c=A[i];

for (int k=i,j=i+1;j<n;j++){   

 T.VM_access(j,0);        // Чтение j-го элемента

 if (A[j]<c) c=A[j],k=j;

 }

A[k]=A[i]; A[i]=c;

 T.VM_access(k,1);        // Запись элементов (обмен)

 T.VM_access(i,1);       

 }

 T.show();

 }

void main(){

#define N 1000

VM T(5,N,10,LRU); // На странице 5 элементов, Процент объема ФП от ВП   - 10

int B[N];

sort(B,N,T);

}

Обработка полученной трассы происходит следующим образом. Класс VM содержит таблицу физических страниц (динамический массив pt размерностью np). Элемент массива – структура page содержит номер виртуальной страницы nv, которая в нее загружена, признак изменения wr, номер последнего обращения access и номер обращения, при котором произошла ее загрузка – load («время» загрузки). Все обращения в модели нумеруются счетчиком cnt, который и является аналогом «системного времени». Кроме того, имеется массив виртуальных страниц pv, содержащий индексы физических страниц или –1, если соответствующая страница не загружена.

При обработке обращения к виртуальной странице вычисляется номер виртуальной страницы, на которой находится очередной «адрес». Затем из таблицы виртуальных страниц берется индекс (номер) физической страницы. Если эта виртуальная страница загружена, то для соответствующей физической страницы корректируется время обращения (access) и признак изменения (если это обращение по записи).

В противном случае выбирается страница, которая будет вытеснена:

- для алгоритма LRU ищется физическая страница с минимальным значением access. Алгоритм удаляет страницу, к которой наиболее долго не было обращений. В реальности для работы такого алгоритма необходимо собирать статистику по обращению программы к своим виртуальным страницам, что и делается аппаратурой преобразования адресов (в описателе каждой страницы есть специальный бит обращения);

- для алгоритма FIFO ищется физическая страница с минимальным значением load – наиболее долго находящаяся в памяти. В реальности для реализации этого алгоритма операционная систем должна только фиксировать последовательность загрузки страниц;

- гипотетический оптимальный алгоритм OPT просматривает трассу вперед и для каждой страницы определяет момент следующего к ней обращения. Затем выбирается страница с максимальным моментом обращения в будущем. В реальности такой алгоритм нереализуем, однако в теории он дает границу эффективности системы виртуальной памяти.

В процессе моделирования собирается и выводится следующая статистика:

  •  nreadобщее количество обращений к памяти;
  •  nwrite количество обращений по записи;
  •  page_int процент страничных прерываний к общему количеству обращений;
  •  update -  процент страничных прерываний, сопровождающихся записью измененной страницы на диск.

Параметры модели и варианты заданий

Эффективность механизма виртуальной памяти рассматривается на нескольких моделях программ:

  1.  Модель линейного обращения к памяти (Sort_Test) – представляет собой двойной цикл по массиву с перебором всех пар элементов.
  2.  Модель «рабочего набора» (Work_Set), используемая для моделирования обращений к памяти, основанном на идее рабочего набора (РН) виртуальных страниц, к которым она обращается в течение достаточно продолжительного периода времени. Идея рабочего набора базируется на свойстве локальности программы, т.е. ее свойстве работать в течение длительного периода времени в ограниченном диапазоне адресов. Программа моделирует случайные обращения к памяти по следующим образом:
  •  в течение заданного интервала времени (количества обращений d1) программа работает со случайным диапазоном адресов шириной d2 элементов (рабочий набор), после чего случайным образом выбирает новый интервал;
  •  имеются две модели рабочего набора. В модели WorkSet моделируется равномерное распределение адресов обращений к памяти в интервале d2. Модель WorkSet_exp моделирует неравномерное (экспоненциальное) распределение обращений в памяти с плотностью вероятности выбора адреса a

  P(a) = K0 exp( - Kmem(a/d2)),

где Kmem – коэффициент неравномерности (при Kmem=1 распределение предельно равномерное, при уменьшении коэффициента неравномерность увеличивается). Коэффициент K0 устанавливает сумму вероятностей в 1 и определяется программой. При моделировании подсчитывается и выводится среднее значение (и стандартное отклонение от среднего) для адреса обращения внутри  диапазона d2. Функция WorkSet_exp имеет следующие параметры:

  •  int n – 
  •  int mколичество обращений к памяти;
  •  int d1 – интервал смены рабочего набора;
  •  int d2 – размерность рабочего набора адресов;
  •  VM &Tссылка на объект – модель;
  •  double Kmem  –коэффициент неравномерности обращений (отсутствует у WorkSet).
  1.  Программы сортировки. Необходимо включить сбор статистики обращений в сортировки двух видов из следующего списка:
  •  сортировка выбором;
  •  обменная сортировка (или однонаправленная шейкер-сортировка);
  •  вставка погружением;
  •  рекурсивное разделение («быстрая» сортировка);
  •  однократное слияние;
  •  циклическое слияние.

При выполнении лабораторной работы необходимо:

  •  собирать статистику работы по каждому исследуемому алгоритму для заданного ряда процентного объема физической памяти (например, 2,5,10,15,50,75,90,95,100) и всех алгоритмов вытеснения (LRU, FIFO, OPT). Размерности массивов должны быть подобраны таким образом, чтобы была набрана достаточная статистика обращений (в диапазоне 1000 - 5000);
  •  алгоритмы сортировки должны работать с массивами, заполненными случайными числами. Для одного выбранного значения процентного объема необходимо выполнить несколько (в пределах 10-20) прогонов модели, чтобы оценить диапазон изменений статистики (среднее и дисперсию). То же самое касается модели рабочего набора;
  •  все полученные значения необходимо перенести в Excel и построить графики зависимости процента страничных прерываний от процентного объема физической памяти;
  •  для моделей «рабочего набора» определить объем физической памяти, соответствующий рабочему набору программы на основе анализа результатов измерений (по изменению процента страничных прерываний);
  •  для алгоритмов сортировки сделать выводы о сравнительной эффективности алгоритмов как с точки зрения трудоемкости (используя материалы курса СиАОД), но и с точки зрения эффективности их выполнения в виртуальной памяти. Необходимо также обосновать полученные результаты, проанализировав алгоритм (прежде всего с точки зрения свойства локальности);
  •  сделать выводы об эффективности различных алгоритмов замещения. Обосновать полученные различия и «аномалии» (если такие наблюдаются) свойствами исследуемых алгоритмов.

Пример оформления результатов моделирования. 

read

 

 

write

 

 

%

LRU

FIFO

OPT

LRU

FIFO

OPT

2

6,15

7,01

5,65

72,6

74,5

73,5

5

4,84

5,1

4,19

74,9

75

79,8

10

3,57

4,14

3,2

76,7

75,6

84,2

15

3,01

3,58

2,56

76,2

74,6

83,8

50

1,44

1,79

1,02

70

61

80,3

75

0,98

1,22

0,34

55,4

55,7

88,1

90

0,74

0,7

0,15

47,2

31,4

70,8

95

0,64

0,78

0,08

41,9

31,2

81

100

0

0

0

100

100

100

 6.


 

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

24652. Аналіз динаміки та структури основних фондів 35 KB
  Характеристику руху о з дають коефіцієнти оновлення і вибуття Коефіцієнт оновлення=вартість прибулих о з за звітний період розділити на первісну вартість о з на кінець звітного періоду Показує яку частку від наявності на кінець звітного періоду складають нові о з Коеф вибуття= вартість вибулих о з за звітний період розділити на первісну вартість о з на початок звітного періоду Показує яка частина о з з якими підприємство починало свою діяльність у звітному році вибула через зношеність та інші причини. Технічний стан о з характеризується: Коеф...
24653. Аналіз ефективності використання основних фондів 26.5 KB
  Аналіз ефективності використання основних фондів. Під раціональним та найповнішим використанням діяючих промисловиробничих основних засобів розуміють той максимальний економічний ефект який отримує суспільство за певний період у вигляді відповідного обсягу та якості продукції. Економічна ефективність використання основних засобів визначається відношенням економічного ефекту одержаного на підприємстві за відповідний період до витрат необхідних для створення основних засобів. Для характеристики ефективності використання основних засобів...
24654. Оцінка забезпеченості підприємства трудовими ресурсами 31.5 KB
  Аналізуючи питання забезпеченості робочою силою потрібно пам'ятати що в сучасних умовах внаслідок помітних скорочень обсягів виробництва підприємства більше стикаються не з проблемою недостачі а з наявністю зайвої робочої сили необхідністю скорочення робочих місць і водночас збереження кваліфікованих кадрів на майбутнє. Із питанням забезпечення робочою силою тісно пов'язане питання закріплення кадрів на підприємстві. При цьому вивчають загальні показники прийняття та звільнення робітників і службовців розраховують коефіцієнти обороту...
24655. Аналіз ефективності використання робочої сили 24.5 KB
  прийому = Чпр сер Ч Коеф вибуття = Чвир сер Ч Коеф заг обор = Чпр Чвир сер Ч Коеф пот кадрів = Ч виб за власним бажанням сер Ч.
24656. Аналіз продуктивності праці 29.5 KB
  Розрахунок продуктивності праці: ПП = V серЧ V обсяг виробництва продукції сер Ч середньооблікова чисельність персоналу для окремих цехів: ПП = Vнат сер Ц сер Ч Vнат обсяг в натуральних одиницях сер Ц середньооблікова ціна Оцінка впливу обсягу виробництва продукції дельта ППв дельта ППв = Vф сер Цпл сер Чпл Пл. сер Цпл сер Чпл Оцінка впливу середньооблікової чисельності робітників дельта ППч = Vф чер Цпл сер ЧФ Vф сер Цпл сер Чпл Оцінка впливу середньої оптової ціни дельта ППсер ц = Vф сер Цф сер Чф Vф сер Цпл...
24657. Аналіз ефективності використання матеріальних ресурсів 25.5 KB
  Аналіз використання матеріалів здійснюється за наступними узагальнюючими показниками: матеріаловіддача зняття продукції із гривні витрат на матеріали це відношення обсягу випущеної продукції до загальної суми матеріальних витрат; матеріалоємність сума матеріальних витрат на випуск однієї гривні продукції це відношення загальної суми матеріальних витрат на обсяг виготовленої продукції. У процесі аналізу можна використати також допоміжні показники рівня використання матеріальних ресурсів: коефіцієнт використання матеріалів рівень...
24658. Аналіз витрат на виробництво за елементами та статтями витрат 26.5 KB
  Аналіз витрат на виробництво за елементами та статтями витрат. Найбільш корисним для вивчення змін у структурі витрат на виробництво є аналіз собівартості за елементами витрат. Елементні витрати це однорідні за складом витрати підприємства. До них належать матеріальні витрати оплата праці відрахування на соціальні потреби амортизаційні відрахування інші грошові витрати.
24659. Аналіз витрат на одну гривню товарної продукції 25 KB
  Аналіз витрат на одну гривню товарної продукції.товарної продукції є основним показником який харзує рівень і динаміку витрат на підво які розробляють різновидну продукцію. товварної продукції є загальним показником рівня витрат він може бути розрахованим для будь якого підващо дуже важливо до порівняння аналізу між підвами їх оцінки конкурентно спроможності. товарної продукції харзує успішність роботи підвапо впровадженя нової технікипідвищення продукції праці раціонально викорастаних ресурсів.
24660. Методика аналізу фінансових результатів підприємства 32 KB
  Кінцевим позитивним результатом господарської діяльності підприємства є прибуток. Прибуток це грошовий дохід утворений в результаті виробничогосподарської діяльності. Прибуток виконує такі основні функції: оцінки підсумків діяльності підприємства; розподілу розподілу доходу між підприємством і державою підприємством і його робітниками між сферою виробництва і невиробничою сферою; джерела утворення фондів економічного стимулювання і соціальних фондів. Джерелами аналітичної інформації є плани економічного та соціального...