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.


 

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

22221. Дощатые и клеефанерные настилы покрытий 2.93 MB
  Клеефанерные панели выполняют функции настила прогонов водо и пароизоляции. По форме поперечного сечения клеефанерные панели могут быть следующих видов: 1 коробчатые; 2 ребристые обшивкой вверх; 3 ребристые обшивкой вниз Коробчатую клеефанерную панель применяют в утепленных покрытиях с рулонной кровлей и гладким потолком Она имеет двухсторонние обшивки образующие вместе с ребрами ряд полостей в которые по слою пароизоляции укладывают утеплитель. Наиболее распространенными являются коробчатые клеефанерные панели которые используют не...
22222. Балки и прогоны цельного сечения. Составные балки на податливых связях 3.02 MB
  Балки и прогоны цельного сечения Основное функциональное назначение балок и прогонов в том что они служат несущими конструкциями покрытий. Балки и прогоны цельного сечения выполняются из досок на ребро брусьев и бревен чаще окантованных с двух сторон. Ввиду ограниченности размеров сечений и длины лесоматериалов такие балки применяют при пролетах до 6 м.
22223. Государство и право в период нэпа 22.6 KB
  Еще в годы гражданской войны Зиновьев Каменев Бухарин говорили о диктатуре уже не пролетариата а о диктатуре партии. Троцкий диктатура партии при содействии красной армии национализация средств производства монополия внешней торговли. С одной стороны речь идет о диктатуре партии. Большинство соратников Ленина придерживались позиции диктатуры партии.
22224. Право в периода новой экономической политики 21.33 KB
  Как поднять доходы налоги. Налоги. Мы говорили что государство может существовать без каких то отношений но сказать то мы можем не собирать налоги невозможно Первым декретов в 1918 г. Эти налоги падали на в прошлом господствующие классы.
22225. Гражданское право. Семейное право 20.13 KB
  Государство ограничивает субъекта правоотношений какими-то рамками. С самого начала был поставлен первый принцип что у нас не должно быть ничего частного государство может вмешаться в любые имущественные отношения. Первый советский гражданский кодекс первый момент государство может вмешаться в любые правоотношения. Государство вводило нэп чтобы поднять экономику.
22226. Советская государственная система в 30х годах ХХ столетия 21.98 KB
  МИЛИЦИЯ УЖЕ ОФИЦИАЛЬНО ВХОДИТ в состав угпу до этого было секретное постановление. Постановление ЦИК СССР. 17 ноября снк СССР принимает постановление где констатируется что при упрошенном ведение дела в 1937 1938г. Этим постановление осуждалась практика массовых арестов.
22227. Государство диктатуры пролетариата 22.61 KB
  советские нпа б. дооктябрьские нпа в. Нпа советского государства основной источник Нормы дооктябрьского права Правосознание Именно нпа советского госва будет постоянно расширяться. Советы всех уровней принимали нпа.
22229. Создание советского государственного аппарата 20.28 KB
  В связи с этим большевики стали проводить национализацию. Но что теперь делать Большевики думали что учредительное собрание передаст власть Советам. Большевики знали. Большевики обещали демократизацию.