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.


 

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

57666. Music styles 114 KB
  Today we’ll have an unusual beginning of the lesson. Look at the blackboard and read the dialogue with roles of your groups. (Using jazz dialogues by roles of two groups)
57667. Teenagers. Their problems and activities 95.5 KB
  Good morning to everyone. Welcome to our English class. Today we will speak about the problems of teenagers. Youth is a very important period in the life of a man. This is a time when a person discovers the world and tries to determine their place in the universe.
57668. Моє рідне місто 100 років тому 61.5 KB
  One representative from each group will come here and assist me in finding the correct name a)turn left: b) go as far as; c) cross the bridge; d) take the first turning right; e) take the second turning left...
57669. Transportation and Public Transit 547 KB
  Pupils, today we take cars, trains, airplanes and power boats for granted. But we haven’t always had them. People have lived on earth for millions of years. But until a few hundred years ago, there weren’t that many ways to get aroun
57670. The More We Travel The More We Know 168.5 KB
  We shall learn a lot of interesting information about history, sights, customs and leisure. We’ll speak, work with presentations, listen to the text, read, make up a dialogue. At the end of the lesson you must give the answers to the question “Why do the people travel?”
57671. Жизнь общества. Повторение грамматики 1.33 MB
  Цели урока (разрабатываются совместно с учениками): Повторить грамматический материал The Present Simple (Indefinite) Tense; Изучить и первично закрепить грамматический материал The Present Simple (Indefinite) Passive Voice...
57672. Свята і традиції. Національні свята України та Великої Британії 135 KB
  Today the topic of our lesson is “Holidays in Great Britain”. We shall talk about different English traditions and customs, learn new things about the traditions of celebration of different English holidays.
57673. Образ жінки в мистецтві 162 KB
  These words are of the same meaning. A woman is the beginning of every starting. She is a source of happiness, joy and attraction. She is beautifull in her appearance, behaviuor and as a person as well.
57674. Великобританія та Україна 62.5 KB
  Yes, you’re right. But today I propose you to watch a TV programme about another one British park. Be ready to discuss the programme and we’ll practice the dialogues to improve your communicative skills.