интересно
Предыдущая | Содержание | Следующая

Нетрадиционные сетевые модели и временные диаграммы интервалов активности

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

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

Идею предлагаемой концепции рассмотрим на примере из конкретного проекта Открытое образование (е-образование), реализуемого под патронажем Международной академии открытого образования (МАОО).

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

В открытом образовании работают специалисты, имеющие квалификацию не ниже, чем в классическом университете. Единственное, что их отличает, - это различные образовательные технологии (классическая и комплексная).

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

В системе открытого образования ресурсы используются в распределенном режиме. Ресурсы распределенного института можно поделить на два типа: интеллектуальный ресурс (учитель) и учебный ресурс (далее - просто ресурс).

Учителя - это преподаватели кафедр, тренеры учебно-тренировочных фирм, тьюторы-консультанты. Учителя предметно относятся к разным распределенным кафедрам через механизм аттестации.

Ресурсы - это комплекты учебно-практических пособий, студии (если есть дистанционная фаза типа телеконференции), режимы Интернет-доступа, аудитории (если есть очная фаза) и другие, без которых обучение студента может не состояться.

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

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

При реализации обучения по специальности процессы могут иметь причинно-следственные связи. Поэтому можно говорить о том, что они образуют направленный граф (рис. 1.7). Применение методов сетевого планирования и управления невозможно; основная трудность - это циклы. Циклы возникают по двум причинам: студенты обучаются не по жесткому учебному плану (возможны различные индивидуальные планы), для отстающих студентов организуется повторное обучение (возврат к пройденной ранее, но не защищенной дисциплине для ее более глубокого изучения). Относительно пути студента по графу в каждый момент времени он находится в определенном текущем процессе - в узле графа. Процесс, который передал студента в текущий процесс, назовем производителем, а процесс, который примет студента после завершения текущего, назовем потребителем.

Рассмотрим возможные диаграммы состояний процесса (рис. 1.8). Если мощности ресурсов бесконечны либо каждый процесс используется вместе с постоянно закрепленными за ним ресурсами, то возможны два состояния (рис.1.8,а): ожидание студентов (ЖС) и выполнение процесса изучения дисциплины (ПУ). В таких ситуациях не возникает необходимости в незапланированных ресурсах: у студента есть учебный план. В состояние ПУ процесс попадает, получив студента от процесса-производителя. После изучения дисциплины студент переходит к процессу-потребителю и попадает в состояние ЖС, если какой-либо производитель не подготовил следующего студента.

В более реальном случае (рис. 1.8,6) при конечных мощностях глобальных ресурсов появляется состояние ожидания ресурса, когда процессу (точнее, студенту в процессе изучения дисциплины) нужны ресурсы (HP).

В условиях реального университета, когда обучение контролируется, а выделение ресурсов и их возвращение осуществляется с помощью процессов планирования и распределения ресурсов, вводятся еще два состояния (рис.1.8,в): подготовка к выполнению (ТВ) и завершение выполнения - контрольные мероприятия, экзамены, зачеты (ЭЗ).

Когда возникает потребность в незапланированных ресурсах, то возможны обратные переходы типа ПУ->НР (рис. 1.8,6,1.8,в). Такие переходы могут привести к блокировкам, которые можно разрешить с помощью известных решений задачи взаимного исключения.

Во время подготовки к выполнению (ТВ) осуществляется планирование ресурсов, а после завершения (ЭЗ) - возврат ресурсов в распоряжение планирующих и распределяющих процессов.

Организация и взаимосвязь различных компонентов системы открытого образования может быть рассмотрена относительно управления процессами в следующих подразделениях университета (рис. 1.9):

управления учебной и учебно-методической работой (УУМР), которое ведает всеми ресурсами, относящимися к учебному процессу;

дирекции распределенного университета, которая совместно с территориально-распределенными филиалами университета (партнерами) отвечает за реализацию учебного плана;

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

кафедр (распределенных кафедр открытого образования). Кафедры - это обладатели интеллектуального ресурса (профессорско-преподавательского состава, тренеров (тьюторов-консультантов), аспирантов, докторантов и других преподавателей).

Далее перейдем к оценке времени изучения студентами дисциплин учебного плана. Время прохождения всех дисциплин учебного плана студентом - это время пребывания заявки в стохастической сети {см. рис. 1.7). Заявки в такой сети будем называть транзактами, чтобы отличать от других элементарных заявок.

Транзакт, попадая из одного узла сети (процесс-производитель) в другой узел (процесс-потребитель), свидетельствует о необходимости изучения студентом следующей дисциплины учебного плана. После этого процесс-потребитель выводится из состояния ЖС и попадает в состояние ГВ. После выделения ресуроов (HP), выполнения функции (ПУ) и завершения выполнения контрольных мероприятий (ЭЗ) транзакт появляется на выходе узла-производителя, а процесс возвращается в состояние ЖС. Случайный интервал времени, ограниченный моментом выхода процесса из состояния ЖС в начале изучения дисциплины и ближайшим моментом попадания в это состояние, назовем интервалом активности процесса. Длительность пребывания транзакта в соответствующем узле - это интервал активности. Для оценки времени реакции системы открытого образования, реализуемой в рамках распределенного института по учебному плану, необходимо уметь рассчитывать значения интервалов активности всех процессов, входящих в состав сети.

Оценка интервала активности процесса. Далее построим итерационную процедуру, позволяющую провести соответствующие оценки. Обозначим А - начало очередной итерации; Б - конец очередной итерации.

А. Начало итерации. Пронумеруем N узлов стохастической сети, характеризующих конкретный план, индексами у и предположим справедливость допущений:

..., N (только в каком-то приближении, так как их необходимо рассчитать);

известны вероятности поступления транзакта из каждого процесса-производителя в любой процесс-потребитель %jn , j, n = 1, 2,..., N; эти вероятности определяются исходя из параметров набора учебных планов, индивидуальных схем обучения и числа студентов, проходящих через систему открытого образования;

Такие допущения могут быть в какой-то степени справедливы, если учебный процесс находится в стационарном режиме (если переходные процессы и были, то они завершились). Поэтому при их выполнении можно получить среднее время изучения всех дисциплин учебного плана по формуле для замкнутых сетей:

- средняя длительность интервала активности;

- интенсивность запросов на курс с номером/;

- интенсивность поступления потока студентов, желающих обучаться по данному учебному плану.

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

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

- процесс ждет студентов (состояние ЖС);

- готовится к выполнению (состояние ГВ);

- процессу нужны ресурсы (состояние HP);

- длительность пребывания в состоянии ПУ;

- индекс, показывающий случайный характер индексируемой величины.

за-

можно определять с помощью одного из трех возможных способов:

исходя из характеристик распределенного института (головного университета, осуществляющего открытое образование);

с помощью хронометрирования;

- это цикл обслуживания;

методика определения цикла обслуживания для потоков типа пуас-соновского или группового и формулы для расчетов приведены в работе.

Предположим, что в распоряжении института имеется М глобальных ресурсов, используемых при обучении. Мощность каждого ресурса - S, элементов, а для выполнения процесса (изучения курса) у предварительно необходимо выделить RtJ элементов каждого ресурса. Причем 0 <RtJ <S,,i=l,2, — , M,j=,2, ...,N.

- это интервал времени, начинающийся в

момент выделения процессу первого элемента ресурса / из набора свободных ресурсов и заканчивающийся моментом возвращения всех Ry элементов в этот набор (каждому ресурсу соответствует свой менеджер обслуживания, контролирующий очередь). Через какой-то интервал времени

на входе счетчика появится первая удовлетворенная заявка очереди /-го ресурса. После этого проходит еще Ry-l случайных интервалов, пока не появятся остальные заявки (каждая соответствует одному выделенному элементу). Если считать, что интенсивность освобождения процессами элементов стационарна, то каждый из

Через время

) и завершается контрольными мероприятиями (за время ty). Поток заявок, поступающий на вход рассматриваемой модели, - неординарный с интенсивностью Xj. Мы не рассматриваем классический учебный процесс классического университета, строящийся по принципу объединения: специальностьо учебный планоучебное расписаниеоконтингент (группы студентов).

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

один студент может привести несколько студентов (а в модели один транзакт может породить группу других транзактов);

в учебном плане могут быть циклы.

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

Одно из свойств групповых потоков заключается в том, что а превосходит математическое ожидание интервала между заявками, поэтому коэффициент вариации с>. Формула для оценки среднего размера группы заявок при обобщенном распределении Эрланга имеет вид

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

связан с коэффициентом вариации

соотношениями:

Определим интенсивность потока, поступающего к одному из- St элементов i-ro ресурса

Далее введем вероятность того, что запрос на вьщеление элемента *-го ресурса поступил от j-ro процесса:

Размер группы заявок к ресурсу i от модуля,/ равен п }. = п. Rr. Средний размер группы, поступающей в одну очередь, равен:

откуда можно получить квадрат коэффициента вариации для потока транзактов, поступающих в /-ю очередь:

и интервал времени

. По правилу расчетов для объединения про-

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

Допустим, что известна средняя задержка в очереди к ресурсу tqi. Тогда можно аппроксимировать функцию распределения времени пребывания в очереди hq,{t) выражением

с погрешностью, находящейся в пределах 15 % даже при эрланговских потоках и постоянных временах обслуживания. Однако при перегрузках (при значениях р(, существенно больших 0 и близких к 1) это выражение становится практически точным, и можно показать, что распределение числа заявок в очереди при перегрузке - экспоненциальное. Поэтому дисперсия времени пребывания в очереди равна

а средняя длительность задержки в очереди определяется из соотношения, получаемого при аппроксимации процесса изменения длины очереди при перегрузках процессом диффузии,

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

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

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

,

- квадрат коэффициента вариации длительности обслуживания, т.е. эти формулы дают результаты с удовлетворительной погрешностью. Формула для оценки р,, характерная для больших значений р, (обычно при 0,5 й р, < 1), имеет следующий вид:

запрошенных элементов

отлична от нуля, равна

Функцию распределения времени ожидания выделения всех элементов /-го ресурсау-му процессу представим в виде

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

задержки процесса:

Тогда справедливы следующие соотношения.

1. При М=1 и индексе /=1 имеет место формула

Далее используем определение функции распределения для Л4И,2 /.

2. При М=2 и индексах /=1,2 справедливо равенство

4. При произвольном М используем метод полной математической индукции и получаем следующее выражение Щ/) для любых

Причем существуют М ограничений на вспомогательные переменные /„:

в фигурных скобках.

:

Б. Конец итерации. Из временной диаграммы на рис. 1.10,6 следует:

Уточнив значения, известные в начале итерации с какой-то погрешностью, итерацию можно повторить, пока процесс не сойдется к результатам с приемлемой точностью. Таким образом, методом последовательных приближений можно получить интересующие нас параметры интервала активности. Расчеты выполняются методом последовательных приближений с использованием рекурсивной функции, написанной на языке C++.

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

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

Выводы

Основные составляющие технологии имитационного моделирования:

структурный анализ сложного процесса;

формализованное описание модели;

построение модели;

проведение экстремального эксперимента.

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

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

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