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.


 

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

72699. Дослідження транзисторів по схемі із спільним емітером 104 KB
  Зняти вхідну і вихідну статичні характеристики визначати коефіцієнт підсилення по струму і вхідний опір транзистора. Як основну схему включення біполярного транзистора застосовують схему включення із спільним емітером. Схема для зняття характеристик транзистора із спільним емітером приведена на малюнку.
72700. Электричество и магнетизм 16.86 MB
  Сила тока проходящего через организм зависит от приложенного напряжения и от сопротивления того участка тела через который проходит ток. Необходимо помнить что предел безопасной величины переменного тока с частотой 50 Гц равен 10 мА.
72701. Исследование демографической структуры популяции 263 KB
  Популяция представляет собой группу организмов одного и того же вида, занимающих определенную территорию и обладающих особыми признаками, которые поддаются статистической обработке. Эти признаки - плотность, рождаемость, смертность, биотический потенциал, расселение...
72702. Определение относительной и абсолютной влажности воздуха 277 KB
  Насыщенный пар. В закрытом сосуде жидкость и ее пар могут находиться в состоянии динамического равновесия, когда число молекул, вылетающих из жидкости, равно числу молекул, возвращающихся в жидкость из пара, т. е. когда скорости процессов испарения и конденсации одинаковы.
72703. Определение емкости батареи конденсаторов 754 KB
  Цель работы: Определить емкость батареи конденсаторов при их последовательном и параллельном соединении. Приборы, принадлежности и материалы: конденсаторы для соединения их в батарею, вольтметр, амперметр, реостат, источник переменного тока.
72704. Технологія створення та редагування таблиць 334 KB
  Мета: Познайомитися з технологією створення та редагування електронної таблиці. Навчитися настроювати зовнішній вигляд вікна процесора Excel. Отримати навички введення даних до таблиці, познайомитися з основними операціями роботи з найпростішими формулами.
72705. ИЗУЧЕНИЕ ПРИНЦИПОВ ПОСТРОЕНИЯ МНОГОКАНАЛЬНОЙ СИСТЕМЫ ПЕРЕДАЧИ С ЧАСТОТНЫМ РАЗДЕЛЕНИЕМ КАНАЛОВ 208.5 KB
  Рассчитать и построить схемы преобразования спектров в аппаратуре мультиплексирования и демультиплексирования указав границы частотных диапазонов занимаемых канальными и групповым сигналами. Разработать методику проведения и выполнить измерения помехозащищенности передаваемых...
72706. АТОМНІ ЕЛЕКТРИЧНІ СТАНЦІЇ 32.5 KB
  Особливості експлуатації АЕС обумовлені специфікою їх технологічної схеми. Однією з особливостей сучасних паротурбінних АЕС є їх робота на насиченому та слабо перегрітому парі з порівняно невисокими тисками пари перед турбіною 65 МПа.