автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Разработка математических моделей определения объема памяти стохастических систем

1 3 4 9''"

\) о

ЙлЬРУССКИИ ОРДЕНА ПУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ' УНИВЕРСИТЕТ ИМЕНИ В. И ЛЕНИНА

На правах рукописи

ПОЗНЯК РЕГИНА ИОСИФОВНА

РАЗРАБОТКА МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ОПРЕДЕЛЕНИЯ ОБЪЕМА ПАМЯТИ СТОХАСТИЧЕСКИХ СИСТЕМ

Специальность 05.13.16 - применение вычислительной техники,

математического моделирования и математических методов в научных исследованиях

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Минск - 1991

.'/У/!

Работа выполнена в Белорусском ордена Трудового Красного Знамени государственном университете имени В.И.Ленина

Научный руководитель - кандидат технических наук,

старший научный сотрудник ТИХОНЕНКО О.М.

Официальные оппоненты: доктор физико-математических наук

' Рыков В.В.,

кандидат физико-математических наук старший научный сотрудник

Дудин А.Н.

Ведущая организация- - НИИ ЭВМ, г.Минск

Защита состоится 26 июня 1991 года в 10 часов

на заседании специализированного совета К 056.03.14 при Белгосуниверситете им. В.И.Ленина ( 220060, г.Минск, Ленинский проспект, 4, Университетский городок ).

С диссертацией можно ознакомиться в библиотеке Белгосуниверсигета им. В.ИЛенина.

Автореферат разослан 26 мая 1991 года

Ученый секретарь специализированного соврта

'ГШ / ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ ■rml

-."Актуальность проблемы. При проектировании стохастических

^¿ЙЙяем, таких как системы коммутации каналов и сообщений, системы обработки данных научного эксперимента, вычислительные, транспортные и экономические системы, в силу их естественной адекватности в настоящее время широко используются методы, основанные на представлении исследуемых объектов и процессов моделями массового обслуживания. Анализ получаемых моделей позволяет решить ряд задач, связанных с определением параметров и характеристик систем обработки информации со случайным потоком сообщений на входе. Однако попытка рассчитать величину объема памяти проектируемой системы известными средствами теории массового обслуживания ( ТМО ) с использованием характеристик

-числа сообщений, находящихся в системе, приводит к серьезным ошибкам, поскольку классические методы ТМО предполагают однородность поступающих в систему сообщений. В реальных же технических системах каждое сообщение несет некоторый количественный признак - длину, от которого в общем случае о^исит время обслуживания сообщения. Физический смысл длины определяется конкретным типом анализируемой системы. При решении задачи определения объема памяти под длиной следует понимать ту величин,'' объема ( выраженную, например, в битах ), которую занимает сообщение в памяти в период его нахождения в системе. Тогда, очевидно, для выбора объема памяти необходимо получить статистические характеристики полной суммы длин сообщений ( суммарного объема ), находящихся в системе в произвольный момент времени. Наличие зависимости времени обслуживания от длины сообщения, а также возможные ограничения суммарного объема делают эту задачу нетривиальной в математическом смысле. Работы Александрова A.M., Капа Б.А., Апанасовича В.В., Тихоненко О.М. дают ее решение для систем массового обслуживания ( СМО ) типа М /&/п/0 , M/G-/o° и li/G-/t/<*> с неограниченным суммарным объемом и временем обслуживания сообщения,

зависящим от длины, включая однолинейные приоритетные системы, а также для СМО типа М/М/а//п. с Независимым от длины временем обслуживания и ограниченным суммарным объемом.

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

Целью настоящей работы является разработка математических моделей определения характеристик суммарного объема сообщений в однолинейных и многолинейных системах обслуживания при различных предположениях относительно характера зависимости времени обслуживания сообщения от его длины, а также разработка и программная реализация диалоговой системы расчета характеристик ( вгслючая характеристики суммарного объема ) стационарных СМО сообщений случайной длины с простейшим входным потоком.

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

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

- формулы для определения преобразования Лапласа-Стилтьеса функции распределения суммарного объема сообщений и вычисления его первых двух моментов в предположении произвольного распределения длин сообщений и произвольной зависимости времени обслуживания от длины;

- явный вид функции распределения суммарного объема сообщений в предположении экспоненциального распределения длин сообщений и прямопропорциональной зависимости времени обслуживания от длины. .

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

3. Для однофазных стационарных СМО с п, идентичными обслуживающими приборами и неограниченной памятью при условии, что входной поток сообщений является простейшим, получены выражения для определения преобразования Лапласа-Стилтьеса функции распределения и вычисления первых двух моментов суммарного объема сообщений, а также явный вид функции распределения суммарного объема в предположении, что время обслуживания распределено экспоненциально и не зависит от длины обслуживаемого сообщения ( характер распределения д-.::?1 сообщений произволен ), либо время обслуживания пропорционально экспоненциально распределенной длине обслуживаемого сообщения.

Практическая ценность и реализация. Практическую ценность представляют

- формулы для расчета статистических характеристик суммарного объема сообщений стационарных СМО Мт- , М/М/а/т, , М/М/п./*«» с неограниченной памятью;

- вывод о допустимости пренебрегать при грубых расчетах параметров системы влиянием зависимости времени обслуживания от длины сообщения для СМО М/Сг//с ограниченной памятью;

- диалоговая система расчета статистических характеристик стационарных СМО сообщений случайной длины с простейшим входным потоком.

Разработанная диалоговая система расчета статистических характеристик стационарных СМО реализована в виде

программного комплекса для мини-ЭВМ типа "Электроника" ( операционная система РАФОС любой версии ) и функционирует в составе целевых комплексов программного обеспечения, внедренных в ГОИ имени С.И.Вавилова ( г. Ленинград ) и ЦКБ УП АН СССР ( г. Москва ).

Апробация работы. Результаты работы докладывались и обсуждались на 5-ой Всесоюзной школе-семинаре по распределенным автоматизированным системам массового обслуживания ( Рига, 1988 ); 5-ой Белорусской зимней школе-семинаре по теории массового обслуживания "Методы исследования информационно-вычислительных систем" ( Гродно, 1969 ); республиканском научно-техническом семинаре "Соверленствование методов исследования потоков событий и систем массового обслуживания" ( Киев, 1969 ); научно-технических семинарах лаборатории специализированных вычислительных систем и заседании проблемного Совета по научному приборостроению НИИ прикладных физических проблем имени А.Н.Севченко Белорусского государственного университета имени В.И.Ленина; научно-технических семинарах кафедры теории вероятностей и математической статистики Белорусского государственного университета имени В.И.Ленина.

Публикации. По теме диссертации опубликовано 6 печатных работ.

Структура, и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы, содержащего 59 наименований, из них 3 на иностранных языках. Объем работы - 96 страниц основного текста, 31 страница рисунков и таблиц. В приложении I приведены формулы, использованные при разработке и программной реализации диалоговой системы расчета статистических характеристик стационарных СМО сообщений случайной длины, тексты модулей которой приведены в приложении 2. В приложении 3 приведены документы о внедрении результатов диссертационной работы.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

1. Модели с ограниченным суммарным объемом ) и временем обслуживания, не зависящим от длины сообщения.

2. Модели с неограниченным суммарным объемом ( V- ) и временем обслуживания ^ . , зависящим от длины сообщения £ . Ui„,:! случайных величин ^ и ^ задается совместной функцией распределения

Модели класса I, адекватно описывающие функционирование достаточно широкого круга реальных систем, в частности, функционирование узла системы коммутации, исследовались в работах Александрова A.M., Каца Б.А., Ромма Э.Л., Скитовича В.В. и др., обзор которых дается в разделе 1.2 диссертации. В разделе 1.3 приведены основные результаты, полученные в работах Аланасовича В.В., Тихоненко О.М., посвященных анализу моделей класса 2 для СМО типа ,

Л/£/*./О , Щ&1И°° '.

Во второй главе диссертационной работы рассматриваются однолинейные однофазные СМО с двумя типами ограничений: ограничением на число мест ожидания в очереди на об-

елужиЕание при неограниченном суммарном объеме (М¡G-fllm., V * сх» ) и с ограничением суммарного объема при допустимости нахождения в системе любого числа сообщений (И/<г/1/°° V< ).

Постановка задачи дана в 2.1. Пусть на вход однолинейной однофазной СМО поступают сообщения, моменты прихода которых образуют простейший поток интенсивности Л . Каждое сообщение характеризуется случайной длиной 5 , • независимой от длин других сообщений. Время обслуживания ^ зависит только от длины сообщения, задана совместная функция распределения F(x, i) случайных величин 5 и Ц . Все сообщения, поступающие в систему, мгновенно записываются в память объема V ( возможно Y ' °° ) и мгновенно исключаются из нее в момент окончания обслуживания. В случае, если сообщение поступает в систему, когда обслуживающий прибор занят, оно заносится в общую очередь с числом мест ожидания т. ( возможно т. ). Если »п. конечно и в системе в этот момент уже находится м. + I сообщение, вновь поступившее сообщение теряется. Поступившее сообщение теряется также, если его длина ^ такова, что в памяти нет места для размещения информации о нем ( в случае V < <» ). Порядок обслуживания сообщений не зависит от их длины.

В разделе 2.2 построена математическая модель, позволяющая для СМО M/6/l ¡т. 00 с неограниченным суммарным объемом, функционирующей в стационарном режиме, получить статистические характеристики суммарного объема сообщений сг . Введем обозначения:

LM* 00 ) , £6+) = - функции распре-

деления ( ф.р. ) случайных величин ( сл.в. ) ^ и ^ соответственно;

о о

QW

Y>6sb ]VSJCoiL6t) = oifs, 0) ,

О

p(s) -- j e'St db(t) = Ы. (a, s) 0

преобразования Лапласа-Стилтьеса ( ПЛС ) ф.р. F(cc,i)t L(x), b(i) соответственно; , f£>; - моменты

i -го порядка сл.в. ^ и Ц ( i = 1,2,... )^,oí¿</' -мешанный момент порядка iф.р. F(x.,+) (J = 1,2,...).

Тогда выражение для ГШС стационарной ф.р. уммарного объема имеет вид

сю

$(S) = jVSJL<W*.J = р0 - (?(5))т~ *

о

« т f

'«■(s.^) ro Zr.C0) <Х ¿М-( П

-- /? u - О

в■ Г., ») - ±

d d1

О О

р; - стационарная вероятность нахождения в системе ' сообщений ( г =0,1,..., т. +1 ); р4(0) * Л Сг ) ; р.("о)= Лр; , £ = 2,3,..., /и-. ; вероятность рр гого, что система пуста, может быть найдена из условия

тормировки

m * i

Zp, -<■

г -О

Формула ( I ) позволяет определить моменты любого по-

рядка стационарного суммарного объема. Выражения для вычисления первых двух моментов имеют вид: <

I ■- !

С ' I

<*0

- * + щ у^ Д * Z Л' (0)

J I' = *

4 -/

к • О

- Л

д

Г1

< -1

1=1 к* О

- 2

к-о ¿--О

1-1 К

а

<-о

¿•о

где

й. (о А) = -4-

В разделе 2.3 получен явный вид ф.р. в случае

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

опально его длине. При р ^ I имеем %(*) = / | - (ос) -

5- 3<(>пЧ, х)] ,

Г

\/п »■ I

и -рУ

Рор е

г'де

т-1 тч-1 £ I

с -О ('О с. ■, 0 Г /

"i +1 . т-1'1 / .

1-1 -г

го-рУ г „

с - о е• о с ■

1*0 е-о с:

* 7 У 2_ ' ^

е-о г!

+ {

т-1 л,-/-/ , (

Г* 1(-0Т 1 (и)

I -О

С'

е-о

ГО ГО^-ЬРП4'1

* а -I - 1

п

При ^ = I

Ч

где

т*л/1 V

¿*о г. л } £0 (»-¡>!

4 з * К~* /г

тг1 у С„,:-, у Т)

л, \ / лт,1гк У Т Г)

-т.

¿.О 4< г о '

Раздел 2.4 посвящен анализу СМО М/&/1 с ог-

раниченным объемом памяти V в предположении, что зависимость времени обслуживания от длины сообщения предста-вима в виде § 3 с^ ■+ , где с ^ 0, [и 5 - независимые случайные.величины. Поскольку аналитические методы определения характеристик потерь сообщений в этом случае не дают результатов, описанная система исследуется с помощью имитационной регенеративной модели, позволяющей оценить вероятности потери сообщения и единицы его длины для различных типов распределений длин сообщений и времени их обслуживания. Результаты моделирования показывают, что в данном случае зависимость времени обслуживания от длины н? оказывает существенного влияния на исследуемые

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

В третьей главе рассматриваются многолинейные однофазные системы массового обслуживания с простейшим входным потоком и неограниченным объемом памяти. Задача определения статистических характеристик суммарного объема для таких СМО разрешима аналитически в случае, когда время обслуживания сообщения распределено экспоненциально, т.е. в СМО типа M/M/rt/m. и М/Л/W"0 . В разделе ЗЛ получены выражения для определения ПЛС ф.р. и вычисления моментов первого и второго порядков стационарного суммарного объема этих систем в предположении, что длины поступающих сообщений распределены произвольно, а время обслуживания сообщения не зависит от длины и распределено по экспоненциальному закону.

В разделе 3.2 построена математическая модель, позволяющая определить стационарные характеристики суммарного объема СМО M/M/n/m. и М/М/*/«> , для которых длины поступающих в систему сообщений распределены экспоненциально, а время обслуживания сообщения пропорционально его длине Ц = с ^ , где с > 0. Так, ПЛС стационарной ф.р. суммарного объема для СМО ti/M/n/m. имеет вид

n-l . ! fjii П. С2/Ь

I п-1 . / fjt

Sr^Cs + ftps)

J>

п. fj/l+»l n-f/n*/

, , , r m + i Л.

(s>{)s «■ / p { s

( 3 )

где | - параметр экспоненциального распределения длин

сообщений; - загрузка системы. Дифференци-

рованием ( 3 ) получены формулы для расчета первого и второго моментов стационарного суммарного объема су

Ч-* / \« а п + 1

7 (пР) + * -Р

/'.-.Л! ,!/(

' { О'-*)1-

а/•]-«■/

<$> - л±0 Г »У** + У сх*0(*рУ ,

х 4Л ¡Гх ('-О!

г

(пр) ч!(1-р)

* - Р

( 4 )

т* I

а -Р)*

т > I , >

р-р*1-*. л(Лл-1)- 2 р^С*" * т.)(Лл*т * О | ,

если р ^ I;

-1

/ п 1 Л /

ц1 Пи А , у * ,) ? А , ^

с? / -2—г + -г ( т * *1) / г, * —г

(¡-О! Л*.' . .77о1!

С I

4-

Л-1 , 1 <

-I

' I

I 1

т п.

1*0

! А

если = I.

Величина р0 в ( 3 ), ( 4 ) определяется соотношением

л

к! (/-р)

Переходя в ( 4 ) к пределу при т в случае

р < I, легко получить формулы для расчета первого и второго стационарных моментов суммарного объема СМО М/(1/п/<*\ Формула ( 3 ) позволяет определить явный вид ф.р. Я(х) суммарного объема сообщений СМО М/М/«./т. с пропорциональным длине временем обслуживания, однако полученное выражение оказывается очень громоздким. Аналогичное выражение для СМО М/М/и-/«*" ( ^ I ) имеет вид

¿п-1

к е

-о-рН*-

(V)

[Мс^+А^)]-^

_ * Р Ь'РК + л Р 5

к:

л

/ л

( 5 )

где

Я (с)

- (л + с)1*. /Л

СЛп'Л(с +Ар)(с-?)(с + А)

о _ Т ^

ч ~ А ~7"Г ~;¡гг ' .

£ • I 1 ■ К-0 К ■

I

г- Рты ¿<-У№ г(г) •

если £ ¿0.5;

с * .,

¡>0 ~~(5^

+ е

~'т±_ у (+х) п е

7 Сс г ^^ - 9- 7 ^_

4*0

Лп-Ь ч

д.

п е 9ь! Лл'л

( б )

если ^э = 0.5.

Величина ра в ( 5), ( б ) определяется соотношением

7 * л Р

а ы с-р)

Го

I 4*0

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

, Н/&/п./.0 и М/М/л/т. . Для них вы-

числяются значения функции распределения ( если для заданной системы это возможно ) в указанных точках, первые два момента и дисперсия.

Описание разработанной диалоговой системы дается в главе 4.

Данная реализация ДС в общем случае предполагает, что сл.в. % и 5 связаны следующей зависимостью: 5 = с 5 + Г , с ^ О, сл.в. и Г независимы.

Если с = 0, очевидно, время обслуживания сообщения не зависит от его длины, и ДС вычисляет характеристики классической модели СМО. Распределение времени обслуживания подчиняется одному из следующих законов: экспоненциальному, Эрланга, равномерному, гиперэкспоненциальному, Р\элея, логнормальному, £ -распределению, -распределению, /А -распределению. Длины поступающих в систему сообщений также подчиняются одному из указанных типов распределений ( в случае, если ДС функционирует в режиме "с учетом длин сообщений" ). Такая организация работы ДС позволяет проводить сравнительный анализ и оценивать влияние длин сообщений, циркулирующих в системе, на ее эксплуатационные характеристики.

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

Расчеты, проведенные с помощью ДС, показывают, что зависимость времени обслуживания от длины сообщения существенным образом влияет на- характеристики суммарного объема для всех типов исследованных систем и, следовательно, должна быть учтена при выборе объема памяти проектируемой технической системы.

Приложение I содержит формулы, использованные при разработке и программной реализации диалоговой системы расчета статистических характеристик стационарных СМО сообщений случайной длины. Тексты модулей ДС приведены в приложении 2. Приложение 3 содержит документы о внедре-

нии результатов диссертационной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТА РАБОТЫ

1. Разработана аналитическая модель, позволяющая определить характеристики суммарного объема сообщений в стационарной системе M/G/1/лг < 00 с неограниченной памятью и произвольной совместной функцией распределения длины сообщения и времени его обслуживания.

2. Для стационарной системы с неограниченной памятью t\ /t\/l / т. * 00 , в которой время обслуживания сообщения пропорционально его длине, рассчитан явный вид функции распределения суммарного объема.

3. Разработана имитационная модель, позволяющая исследовать характеристики потерь сообщений в стационарной системе с ограниченной памятью М/бУ*/0"0 , для которой зависимость времени обслуживания ц от длины сообщения

5 дается соотношением £, - * jf t где с > 0, 5 и )[" независимые случайные величины.

4. Разработана аналитическая модель определения характеристик суммарного объема для стационарной системы М/^/и-Дя. ^ 00 , в которой время обслуживания пропорци- ■ онально длине сообщения.

5. Для стационарной системы М/Н/п/о° с пропорциональным длине временем обслуживания сообщения получен явный вид функции распределения суммарного объема сообщений.

6. Разработана и программно реализована диалоговая система расчета характеристик стационарных СМО сообщений случайной длины типа , М/&/п/о .fl/i/",

H/h/h./fK , П/М .

Основные положения диссертации отражены в следующих публикациях.

I. Позняк-Р.И., Ревинский В.В., Старовойтов A.M., Ти-хоненко О.М. Имитационная модель однолинейной СМО с ограниченной памятью // У Всесоюзн. шк.-семинар по распределенным автоматизированным СМО. Тез. докл. М., 1988. С. 214-215.

2. Позняк Р.И., Тихоненко О.М. Расчет характеристик суммарного объема требований в многолинейной СМО // У Всесоюзн. шк.-семинар по распределенным автоматизированным СМО. Тез. докл. М., 1968. С. 336-337.

3. Позняк Р.И., Старовойтов A.M., Тихоненко О.М. Пакет программ для расчета характеристик систем обслуживания требований случайной длины // Совершенствование методов исследования потоков событий и систем массового обслуживания. Тез. докл. Томск, 1989. С.125.

4. Позняк Р.И., Тихоненко О.М. Распределение суммарного объема требований в однолинейной СМО с ограниченной очередью // Методы исследования информационно-вычисли-_ тельных систем. Тез. докл. У Белорусской зимней шк.-семинара. Мн., 1989. С. 97-98.

5. Позняк Р.И., Ревинский В.В., Старовойтов A.M., Тихоненко О.М. Диалоговая система расчета характеристик стационарных СМО с учетом длин требований // Методы исследования информационно-вычислительных систем. Тез. докл. У Белорусской зимней шк.-семинара. Мн., 1989. С.96.

6. Тихоненко О.М., Завгороднев С.М., Позняк Р.И. Распределение суммарного объема требований в многолинейных системах массового обслуживания // J. Jafpzm. Procas.

Cyétinti. EÍK , 25(1989)4, 173-183.

7. Позняк Р.И., Ревинский В.В., Старовойтов A.M., Тихоненко О.М. Диалоговая система определения объема потребляемой памяти АСУ Til на базе персональной ЭВМ // Перспективы и опыт внедрения статистических методов в АСУ ТП. Тез. докл. 1У Всесоюзн. конф. Ч. 2. Гула, 1990. С. 106-107.

6. Позняк Р.И., Ревинский'В.В., Старовойтов A.M., Тихоненко О.М. Определение характеристик суммарного объема требований в однолинейных системах обслуживания с ограничениями // Автоматика и телемеханика. 1990. № II.