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.


 

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

21869. Качество и эффективность управленческих решений 54 KB
  Качество и эффективность управленческих решений.1 – Понятие управленческого решения и управленческого действия В теории принятия решений выделяют понятия управленческие решения и управленческие действия.2 Качественная оценка эффективности управленческого решения В состав качественных показателей эффективности разработки управленческих решений могут быть включены: своевременность представления проекта решения степень научной обоснованности решений использование научных методов разработки современных подходов ...
21870. Контроль реализации управленческих решений 72 KB
  Понятие содержание цель и функции контроля; 11. Виды контроля и их классификация; 11. Основные принципы и критерии организации контроля; 11. Основные принципы и критерии организации контроля.
21871. Управленческие решения и ответственность 53 KB
  Управленческие решения и ответственность. Ответственность руководителя как элемент процесса принятия и реализации решения; 12. – Ответственности и ее формы в зависимости от сферы деятельности Ответственность категория этики и права выражает особое социальное и моральноправовое отношение личности к обществу. В зависимости от сфер жизнедеятельности людей ответственность имеет ряд форм.
21872. Функции решения в методологии и организации процесса управления 253 KB
  Функции решения в методологии и организации процесса управления.1 Функции решения в методологии и организации процесса управления; 1.2 Понятие управленческого решения и сферы его применения; 1.
21873. Типология управленческих решений 155.5 KB
  Классификация управленческих решений Для разработки и принятия адекватного рассматриваемой проблеме управленческого решения эта работа должна строиться на основе научной классификации управленческих решений. Наиболее широко распространена их классификация по следующим основаниям: сфера деятельности; сроки действия; цели; вид лица принимающего решение ЛПР; уникальность управленческого решения; полнота исходной информации; степень обоснованности решения; ранг управления; масштабность решения; объект...
21874. Условия и факторы качества управленческих решений 47 KB
  Условия и факторы качества управленческих решений. Свойства качественных решений 3. Условия и факторы качества решений 3. Существует показатель косвенно оценивающий качество принятых управленческих решений через количество выполненных решений: Кк = Рв Рн Рп 100 где Кк коэффициент качества управленческих решений; Рп количество принятых управленческих решений; Рв количество выполненных управленческих решений; Рн количество выполненных некачественных решений.
21875. Модели и методология разработки управленческого решения 143.5 KB
  Модель менее сложна чем моделируемый объект и позволяет руководителю лучше разобраться в конкретной ситуации и принять правильное решение. В этой модели основное внимание уделяется роли ожиданий и системы ценностей членов организации их представлениям о ситуации взаимодействию между членами организации.Качество индуктивной модели определяется тем насколько с одной стороны удается упростить описание ситуации принятия решения а с другой насколько верно удается отразить основные свойства моделируемой ситуации. Здесь путь создания...
21876. Гражданский иск как способ восстановления нарушенных прав 339.5 KB
  Объектом работы являются правоотношения, возникающие между государством в лице органов и должностных лиц, осуществляющих производство по уголовному делу и гражданином, в связи с реализацией им права на восстановление нарушенных прав, в том числе и входящего в его структуру права на возмещение имущественного вреда и устранение последствий морального вреда.
21877. Роль автоматизации в процессе производства нефтяного кокса 405.5 KB
  Целью данной курсовой работы является изучение роли автоматизации в процессе производства нефтяного кокса. Актуальность избранной темы вызвана тем, что внедрение специальных автоматических устройств приводит к увеличению количества продукции и улучшению его качества, росту производительности труда, снижению себестоимости продукции, улучшению условий работы, удлинению сроков эксплуатации оборудования и т. д.