Моделирование вычислительных систем

1



17



Задание 1. Разработка модели мультипрограммной вычислительной системы.



В соответствие с вариантом определить параметры средней задачи определить возможность размещения файлов на ВЗУ. Определить параметры минимальной конфигурации системы. Графически представить структуру разработанной модели.



При оперативной обработке информации ставится цель уменьшить среднее время решения задачи. Если поступившая заявка на выполнение работы немедленно принимается к исполнению, то вычислительная система функционирует в режиме оперативной обработки. Такие вычислительные системы получили специальное название – системы оперативной обработки (СОО). Процесс решения задачи Zi представляется произвольной последовательностью этапов счета (обработки в процессоре) и обращения к файлам F1,…, FN (обмена информацией между внешней и оперативной памятью системы).

Предполагается, что исследуемая СОО предназначена для решения заданного набора задач {Zi} (i=1,2,.., M). Где М – число задач, возлагаемых на систему с целью реализации определенных функций. Каждая задача Zi характеризуется интенсивностью потока запросов на ее решение, трудоемкостью i процессорных операций, трудоемкостью операций обмена с внешней памятью, которая задается средним числом обращений Nij к файлу Fj в процессе решения задачи Zi.

Множество файлов {Fj} (j=1,2,.., N), где N – число файлов, используемых в процессе решения множества задач {Zi} размещается во внешней памяти системы, состоящей из накопителей двух типов НЖМД и  НМОД. Обмен информацией между оперативной и внешней памятью системы производится на уровне записей, представляющих структурно неделимую единицу информации при обмене. Файл Fj (j=1,2,..,N) характеризуется длиной файла Gj, средней длиной записи gj.

Накопители, используемые в составе внешней памяти СОО, характеризуются такими техническими параметрами как среднее время доступа к данным, размещаемым в НЖМД – UМД и в НМОД – UМОД, скорость передачи данных при обмене через канал передачи данных – VМД и VМОД для НЖМД и НМОД соответственно, емкость накопителя – GМД и GМОД.









В данном случае условия таковы:

Задачи, решаемые системой, и интенсивности их поступления

1

2

3

4

5

Z1

1

Z2

2

Z3

3

Z4

4

Z5

5

7

2,0

14

1,8

10

0,5

19

0,5

1

2,0

Параметры задач:

№ задачи

Трудоемкость процессорных операций i

Среднее число обращений к файлам Nij





F1

F2

F3

F4

F5

F6

F7

F8

F9

F10

1

100

10

5

-

-

-

-

2

1

-

-

7

700

10

-

-

5

-

-

1

-

2

-

10

1000

-

15

-

-

22

10

3

-

4

-

14

400

5

-

15

7

-

-

2

-

3

-

19

900

-

40

-

15

-

-

4

-

-

2

Параметры файлов:

Файлы

DF1

DF2

DF3

DF4

DF5

DF6

DF7

DF8

DF9

DF10

Длина файла, Мбайт (Gi)

1

2

2

3

3

4

5

6

8

9

Средняя длина записи, Кбайт (gi)

5

8

15

6

14

18

10

15

20

25

Параметры накопителей:



Тип



Название накопителя

Емкость, Мбайт

Скорость передачи данных (VН), Кбайт/сек

Среднее время доступа (UН), сек

НЖМД

IBM UltraStar XP Wide/Fast SCSI-2

4200

6900

0,0136

НМОД

Fujitsu MEOD 130-MMac/PC

128

1100

0,0383



Исследования проводятся на сетевых моделях СОО с однородным потоком заявок. Этап обращения к файлам рассматривается как последовательность двух фаз: подготовительной и передачи информации.

В модели отображаются только те устройства СОО, которые оказывают наиболее существенное влияние на процесс решения задач пользователей в смысле задержки получения ответа во времени. Каждое из устройств участвует в реализации определенного этапа в процессе решения задачи.

Любое устройство СОО представляется в модели одноканальной СМО. Дисциплина обслуживания заявок в любой СМО предполагается простейшей бесприоритетной очередью FIFO (обслуживание в порядке поступления). Одноканальная СМО характеризуется интенсивностью i  входящего потока и средним временем U- обслуживания заявок.

Первым этапом построения сетевой модели системы оперативной обработки является усреднение параметров задач из множества задач {Zi}, возлагаемых на систему, с целью приведения неоднородного потока заявок к однородному. Параметры, получаемые в результате усреднения, описывают, так называемую, среднюю задачу. Приведение неоднородного потока заявок к однородному должно проводиться таким образом, чтобы однородный поток запросов на решение средней задачи создавал в среднем такую же нагрузку на систему, как неоднородный поток запросов на решение множества задач {Zi}. Вследствие этого параметры средней задачи определяются посредством усреднения параметров множества задач {Zi}, решаемых системой, по интенсивностям их поступления i   (i=1,2,..,M), где М – количество входных потоков заявок.

Параметры средней задачи определяются следующим образом:

		Интенсивность потока запросов на решение средней задачи:





=1+2+ 3 +4+ 5 = 2+1,8+0,5+0,5+2 = 6,8

Средняя трудоемкость процессорных операций при решении средней задачи: 



		Среднее число обращений к файлу Fj:







D1

D2

D3

D4

D5

D6

D7

D8

D9

D10



5,51

3,97

4,43

1,62

0,74

1,93

0,29



1,68

0,15



		Суммарное число обращений к файлам в процессе решения средней задачи:





D = 7,2 + 5,51 + 3,97 + 4,43 + 1,62 + 0,74 + 1,93 + 0,29 + 1,68 + 0,15 = 27,52

		Вероятность использования файла Fj:





P1

Р2

Р3

Р4

Р5

Р6

Р7

Р8

Р9

Р10

7,2 / 27,52 = 0,261

0,2

0,144

0,16

0,06

0,03

0,07

0,01

0,06

0,005



		Средняя трудоемкость этапа счета:









0  =  480,9 / 28,52 = 16,86



Следующим этапом построения является этап, на котором определяется возможность размещения файлов в накопителе внешней памяти. Этот этап построения модели СОО состоит в количественной оценке возможности размещения каждого файла из множества {Fj} в накопителях различного типа, входящих в состав внешней памяти исследуемой системы.

Вследствие того, что к различным файлам производится различное число обращений при решении задач, естественно предположить, что файлы, сравнительно редко используемые в процессе решения задач, могут располагаться как в НМОД, так и в НЖМД, в то время как файлы, частота обращений к которым велика, должны располагаться в НЖМД как устройствах внешней памяти с минимальным временем доступа.

Условие существования стационарного режима в накопителе при условии размещения в нем файла Fj имеет вид:

где j – интенсивность потока запросов к файлу

      j – среднее время доступа к файлу.

Интенсивность j потока запросов к файлу Fj можно представить в виде:

j=Dj

1

2

3

4

5

6

7

8

9

10

6,8 х 7,2 = 48,96

37,47

27

30,1

11,02

5,03

13,1

1,98

11,42

1,02



С учетом этого можно получить ограничение на среднее время доступа к файлам: 





Введем обозначение 

Величина j представляет собой максимально допустимое время доступа к файлу Fj. В связи с этим файл Fj может размещаться в накопителе, обеспечивающем время доступа к информации меньшее j. Таким образом, сравнивая значения j     (j= 1, 2, …, N) со значениями UМД и UМОД, можно оценить возможность размещения файла Fj либо только в НЖМД, либо НМОД или НЖМД. При UМДj файл может быть полностью размещен в НЖМД.



1

2

3

4

5

6

7

8

9

10

0,0204

0,0267

0,370

0,033

0,089

0,199

0,763

0,505

0,876

0,98



Таким образом, только в НЖМД могут размещаться файлы F1, F2, F3, F4 и F6, остальные могут размещаться как в НМОД, так и в НЖМД.

Третьим этапом построения сетевой модели СОО является этап определения параметров минимальной конфигурации СОО. Определение производится с учетом существования стационарного режима в каждой СМО сети. Последнее условие определяет существование стационарного режима во всей сети в целом. Для одноканальной СМО Si условие существования стационарного режима имеет вид:





где i   - интенсивность потока заявок в СМО Si;

         i – среднее время обслуживания заявок в СМО Si

Интенсивность  i  потока заявок к любой СМО Si, линейной стохастической сети связана с интенсивностью источника заявок  соотношением:

i  = i 

где i – коэффициент передачи СМО Si

Использование физического смысла коэффициента передачи, как среднего числа прохождений заявки из источника через СМО Si от момента ее поступления в сеть до момента выхода из сети, позволяет существенно упростить процедуру определения величин i.

Определение минимального быстродействия процессора сводится к следующему. Число запросов на этап счета в процессе решения одной задачи равно (D+1). Вследствие этого значение (D+1) можно рассматривать как коэффициент передачи СМО, отображающей процессор. Таким образом, интенсивность потока заявок к процессору:

пр =  (D+1)

пр = 6,8  х 28,52 = 193,94

Среднее время обслуживания заявки в процессоре (средняя продолжительность этапа счета):







где Vпр – быстродействие процессора

С учетом этих соотношений условие существования стационарного режима в СМО, отображающей в сетевой модели СОО процессор, принимает вид:





Таким образом, минимальное быстродействие процессора, обеспечивающее существование стационарного режима:



Vпрмин=



Vпрмин= 6,8 х 480,9 = 3271



При определении количества накопителей внешней памяти (НМОД и НЖМД) следует исходить из условия существования стационарного режима, так и из условия возможности размещения файлов по накопителям по объему.

Условие существования стационарного режима в многоканальной СМО или в совокупности одноканальных СМО, отображающих в модели НЖМД системы, имеет вид:





Входящая в это выражение интенсивность потока заявок к системе НЖМД равна:          МД=DPМД,

 где PМД – вероятность обращения к ленточным файлам при операции обмена с файлами. Значение PМД определяется путем суммирования вероятностей Pj обращения к файлам, размещенным в НЖМД:





Рмд = 0,261 + 0,2 +0,144 + 0, 16 + 0,03 = 0,795

С использованием соотношения для МД, условие существования стационарного режима для НЖМД приводится к виду:







откуда можно найти ограничение снизу на количество НЖМД системы:

mМД >  DPМДUМД

Для нашего случая mМД > 27,52 х 0,795 х 6,8 х 0,0136

			mМД > 2

Кроме того, необходимость размещения в НЖМД всех ленточных файлов требует выполнения условия, при котором емкость НЖМД, используемых в системе, не меньше суммарной длины ленточных файлов, т.е.









где Gi – длина ленточного файла, Gмд – емкость одного НЖМД, в данных условиях mмд  (1 + 2 + 2 + 3 + 4)/4200

 mмд  0,003

Таким образом, исходя из обоих ограничений, минимальное количество НЖМД системы определяется выражением:

Количество НМОД минимальной конфигурации определяется аналогично:









Интенсивность потока заявок кпд равна сумме интенсивностей потоков заявок к НМОД и НЖМД: кпд = мод + мд = D = 6,8 х 27,52 = 187,148

При определении среднего времени передачи через КПД учитывается различная скорость передачи данных для НМОД и НЖМД. Для этого определяется средняя длина записи для магнитооптических и дисковых файлов соответственно. Величины gмод и gмд определяются усреднением длин записей по магнитооптическим и дисковым файлам с учетом вероятностей Pj их использования при решении средней задачи, т.е. 







gмод = (0,06х14 + 0,07х10 + 0,01х15 + 0,06х20 + 0,005х25) / 0,205 = 14,7

gмд = (0,261х5 + 0,2х8 + 0,144х15 +0,16х6 + 0,03х18) / 0,795 = 8,26



	Тогда с учетом вероятностей обращения к магнитооптическим и дисковым файлам в процессе обмена информацией между внешней и оперативной памятью СОО среднее время  передачи данных через КПД :







Это выражение может быть приведено к виду:







        Uкпд = (0,06х14 + 0,07х10 + 0,01х15 + 0,06х20 + 0,005х25) / 1100 + 

+ (0,261х5 + 0,2х8 + 0,144х15 + 0,16х6 + 0,03х18) / 6900 = 0,00369

Количество КПД в СОО должно удовлетворять условию:

mкпд>DUкпд

т.е. для минимальной конфигурации:

mкпдмин = [DUкпд]

mкпдмин = [6,8 x 27,52 x 0,00369] = [0,69] = 1

Таким образом, при минимальной конфигурации должно быть 3 накопителя на жестких магнитных дисках, 2 накопителя на магнитооптических дисках и один канал передачи данных. На рисунках 1 и 2 (стр.10) представлены структура моделей М1 и М6 соответственно.





КПД1

СМО S4

КПД1

КПД1

МД1

МД2

МД3

МОД2

МОД1

ЦП

Рис. 1 . Модель М1

МД3

МД2

МД1









ПР

мод1

мод2

СМО S3

CМО S2

МД

МД3

МД2

МД1

МОД2

Омод

мод

МОД1

ЦП

СМО S1

Опр

Рис. 2 . Модель М6

КПД









ПР

Задание 2. Разработка упрощенной сетевой модели ВС.

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



Исследование характеристик функционирования СОО проводится на модели М6. Определение параметров упрощенных сетевых моделей сводится к следующему.

Определяется матрица вероятностей передач Р=|Pij|, где Pij – вероятность того, что заявка, поступающая в систему Si, поступит в систему Sj (i,j=0,…, n), где n- число каналов в системе. Очевидно, что Pii = 0 и сумма Pij =0 для любого i. 

Модели ВС удобно представлять в виде направленных графов, в которых вершины графа соответствуют различным СМО, а направленные дуги – процессам перехода заявок из одной СМО в другую. Для модели М6 вышеописанный граф будет иметь вид представленный на рисунке 3. 



S0

P01

P10

P12

P24

S2

S1

S3

S4

P13

P34

P41

Рис. 3 . Граф модели М6















В данном случае принято следущее соответствие:

		S0 – процесс поступления (прихода) заявки в сеть и процесс ее выхода из сети;

		S1 – процессор;

		S2 – накопители на магнитооптических дисках;

		S3 – накопители на жестких магнитных дисках;

		S4 – каналы передачи данных

Для сети, изображенной на рисунке 3 очевидно, что P01 = P24 = P34 = P41 = 1. Диагональные элементы матрицы З нулевые. Таким образом, осталось определить элементы Р10, Р12, Р13. Вероятность Р10 представляет собой вероятность завершения задачи на очередном этапе счета. Учитывая, что задача может завершиться на любом этапе с равной вероятностью, а общее число этапов счета, приходящихся на одну задачу равно (D+1), получим Р10 = 1 / (D+1) = 1/ (1+27,52) = 0,035 .  Вероятности P12, Р13 можно представить как произведение двух вероятностей: продолжение этапа решения задачи и обращение к соответствующему накопителю.

Вероятность первого события равна 



Вероятность второго события равна Рмод для НМОД и Рмд для НЖМД. Тогда получим:



Р12 = 27,52 х 0,205 / 28,52 = 0,198

Р13 = 27,52 х 0,795 / 28,52 = 0,767

В соответствии с вышеизложенным, матрица вероятностей передач для данной модели будет выглядеть следующим образом:

















С учетом ранее найденных значений, матрица примет видт.е. мы видим, что изменение конфигурации повлияет только на вероятности Р12 и Р13, а изменение потока заявок повлияет на изменение вероятностей Р12, Р13 и Р10.

Задание 3. Разработка сетевой модели ВС с максимальной степенью детелизации.

 Используя параметры средней задачи и минимальной конфигурации выбрать способ распределения файлов по накопителям и способ подключения ВЗУ к каналам передачи данных. Определить параметры сетевой модели ВС с максимальной степенью детализации. Отобразить граф стохастической сети для выбранной модели. Исследовать влияние структурных параметров на характеристики функционирования ВС.



Для получения более точных результатов исследования используются модели с максимальной степенью детализации М1, в которых производится учет реального распределения файлов по накопителям внешней памяти СОО и способа подключения накопителей к каналам.

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

Использование моделей с максимальной  степенью детализации предполагает такую последовательность этапов исследования:

		Выбор способа распределения файлов по накопителям внешней системы;

		Выбор способа подключения накопителей к каналам;

		Построение конфигурации стохастической сети, представляющей модель М1 исследуемой систем, и определение параметров сетевой модели.

		Исследование характеристик функционирования СОО на модели.

При выборе способа распределения файлов следует руководствоваться следующими основными положениями:

файлы, для которых выполняется условие возможности размещения в НЖМД U*j<= Uмод, размещаются в НЖМД. Согласно расчетам в задании 1 (стр.5), в НЖМД размещаются файлы F1-4, 6.

Файлы, для которых выполняется условие размещения в НМОД U*j>Uмод, как правило, размещаются в НМОД. В нашем случае в НМОД будут находиться файлы F5, 7-10. 

Файл размещается в накопителе целиком

Размещение нескольких файлов в одном накопителе производится при выполнении следующих условий:

а) Условие размещения по объему G1+…+Gn  Gн, где Gн – объем накопителя. Исходя из этого условия, вполне достаточно одного НЖМД и одного НМОД для размещения всех файлов, т.к. объемы файлов значительно меньше объемов накопителей.

б)  Условие существования стационарного режима при обслуживании потока запросов к накопителю Uн < 1/ (D1 +Dn). В случае размещения всех файлов в одном НЖМД или НМОД это условие не выполняется. Из расчетов в 1 задании (стр. 9) следует, что должно быть 3 НЖМД и 2 НМОД. Рассчитаем, какие из файлов будут в накопителях. 

Для НЖМД.   Преобразуем формулу условия существования стационарного режима (D1 +Dn) < 1/ Uн

     (D1 +Dn) < 1/ Uн 

т.е. для НЖМД сумма среднего числа обращений к файлам должна быть меньше 10,81. Исходя из этого, разместим файлы F1 и F6 на первый НЖМД, файлы F2и F3 на второй, файл F4 –на третий НЖМД.

Для НМОД.  Сумма среднего числа обращений к файлам НМОД должна быть меньше 3,84. Разместим файлы F5 и F7 в первый НМОД, файлы F8, F9 и F10 во второй.

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

При сравнении вариантов распределения, обладающих одинаковым числом накопителей одного типа и различными значениями вероятностей Рмод и Рмд обращения к магнитооптическим и дисковым файлам, (Рмд+Рмод=1), предпочтение следует отдавать варианту с максимальным значением Рмд. Это условие означает необходимость более полного использования в первую очередь НЖМД как накопителей с меньшим по сравнению с НМОД средним временем доступа к информации.

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







где Рмодi и Рмдi- вероятность использования накопителя при обращении к файлам.

Эти условия соответствуют обеспечению распределения файлов, при котором степень неравномерности загрузки накопителей одного типа стремится к минимуму.

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

К одному КПД следует подключать по возможности накопители одного вида, если это подключение не увеличивает общее число каналов в системе.

Минимальное число каналов передачи данных, обеспечивающих существование стационарного режима в системе







Вероятность передачи заявки Р1i от процессора к СМО Si определяется следующим образом:







Здесь суммирование ведется по всем файлам, подключенным к накопителю.

На рисунке 4 (стр.16) представлен граф этой модели.









	

S1

S2

S3

S4

S5

S6

S7

S0

P01

P10

P12

P13

P14

P15

P16

Р27

Р37

Р47

Р57

Р67

Р71

Рис. 4. Граф модели М1

	

	

	

	

	

	

	

	

	

	

	

	В данном случае 

	S0 – процесс поступления заявки в сеть и процесс ее выхода из сети;

	S1 – процессор;

	S2…S4 – НЖМД;

	S5, S6 – НМОД;

	S7 - КПД

Для этой сети очевидно, что Р01 = Р27 = Р37 = Р47 = Р57 = Р67 = Р71. Диагональные элементы матрицы нулевые. Вероятность Р10 представляет собой вероятность завершения задачи на очередном этапе счета. Учитывая, что задача может завершиться на любом этапе с равной вероятностью, а общее число этапов счета, приходящихся на одну задачу равно (D+1), получим Р10 = 1 / (D+1) = 1/ (1+27,52) = 0,035 .  Вероятности P12, Р13 можно представить как произведение двух вероятностей: продолжение этапа решения задачи и обращение к соответствующему накопителю.

Вероятность первого события равна 

Р10 = 0,035

Р12 = 27,52 х ((0,261+0,03) / (D+1)) = 0,281

Р13 = 27,52 х ((0,2+0,144) / (D+1)) = 0,332

Р14 = 27,52 х (0,16 / (D+1)) = 0,154

Р15 = 27,52 х ((0,06 + 0,07)/(D+1)) = 0,128

Р16 = 27,52 х ((0,01 +0,06 +0,005)/(D+1)) = 0, 07



Матрица вероятностей передач для данной модели будет иметь вид:

















При переразмещении файлов в накопителях будет меняться вероятность передачи к этим накопителям.



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