Портал GPSS.RU

В. Н. Задорожный

МЕТОДЫ УСКОРЕННОЙ ИМИТАЦИИ ПРОЦЕССОВ С ИНТЕНСИВНЫМИ ПРЕРЫВАНИЯМИ


 

 

1.         Проблема моделирования интенсивных прерываний

При непосредственном имитационном моделировании таких систем массового обслуживания (СМО), в которых интенсивность λ потока приоритетных заявок на несколько порядков превосходит интенсивность λ' потока неприоритетных (рядовых) заявок, затраты компьютерного времени могут возрастать также на несколько порядков. Это связано с тем, что для получения представительной статистической выборки по обслуживанию N рядовых заявок приходится воспроизводить прохождение приблизительно (λ/λ')N приоритетных заявок, т. е. общее число имитируемых событий оказывается на несколько порядков выше, чем число событий наблюдаемых.
Подобная проблема возникает, например, при имитации вычислительных сис-тем, в которых управляющие программы ненадолго, но часто прерывают выполнение прикладных программ, создавая некоторую дополнительную загрузку r центрального процессора. Обычно при имитации ВС проблему обходят путем исключения из модели потока приоритетных заявок и учета их влияния «в среднем». Например, в [1] предла-гается исключаемый поток прерываний компенсировать занижением быстродействия моделируемого процессора на долю, равную r. Однако при таком учете времени пре-рываний теряется его дисперсия, вклад которой в среднее время ожидания рядовых заявок может быть существенным, когда показатель α = λ/λ' составляет 101 ÷103.
Исследование интенсивно прерываемых процессов обслуживания в СМО типа G2|G2|1 с абсолютными приоритетами позволило установить ряд общих аналитических результатов. В частности, найден достаточно простой и эффективный метод такого исключения из СМО потока приоритетных заявок, при котором время прерываний учитывается с точностью до распределения. Точная аналитическая форма полученных результатов достигается с помощью асимптотического анализа свойств системы G2|G2|1 при α → ∞. Увеличение α интерпретируется здесь как масштабное преобразование кумулятивных распределений A(t) и B(t), задающих время поступления и обслуживания приоритетных заявок в исходной системе. Эти распределения рассматриваются как заданные параметрически через базовые распределения A*(t) и B*(t):
A(t) = A*(αt), B(t) = B*(αt). (1)
Характеристики СМО, которые определяются только функциями A(t) и B(t) и имеют размерность времени, изменяются при увеличении α пропорционально α–1.


 

 

2.         Основные соотношения

Обозначим t время между приходами смежных приоритетных заявок, x – время обслуживания приоритетной заявки, t' – время между приходами рядовых заявок и x' – время обслуживания рядовой заявки. Средние значения этих случайных величин (сл. в.) будут обозначаться, соответственно, в виде В дальнейшем в качестве символа среднего любой сл. в. будем использовать ее надчеркнутое обозначение.
Интенсивности l, l' приоритетного и неприоритетного потоков выражаются че-рез средние интервалы поступления заявок: . Коэффициент загрузки системы r Σ положим меньшим единицы:
r Σ = ρ + ρ' < 1,
где ρ – коэффициент загрузки СМО приоритетными заявками,
ρ' – коэффи-циент ее загрузки рядовыми заявками.
Приоритетные заявки в системе «не ощущают» рядовых заявок, поэтому с их точки зрения рассматриваемая СМО является системой G|G|1 с одним входным потоком заявок. Систему, получаемую из исходной СМО удалением потока рядовых заявок, назовем системой S. Обозначим через π длину периода занятости в этой системе, через ψ – длину периода незанятости. Период занятости и следующий за ним период незанятости образуют период регенерации [2]. Процессы, которые по определению принадлежат разным периодам регенерации, статистически независимы.
При больших α чистое время обслуживания x' рядовой заявки с высокой вероятностью многократно превышает среднюю длину периода незанятости СМО приоритетными заявками. Поскольку рядовая заявка обслуживается только во время этих периодов незанятости, то ее обслуживание завершается, когда их сумма перекрывает заданное значение величины x' = T. Независимость и одинаковое распределение всех периодов ψi, покрывающих в сумме заданное время обслуживания T, позволяют рассматривать их как поток восстановлений и применять к ним соответствующую хорошо разработанную теорию [3].
Последовательные периоды pi занятости СМО приоритетными заявками представляют собой приращения суммарного времени ZT прерываний рядовой заявки в процессе ее обслуживания. Между собой приращения pi независимы, как и периоды незанятости ψi. Однако любые два периода pi и ψi , составляющие вместе один период регенерации (в системе S), в общем случае зависимы. В [3] с точностью до обозначений рассматриваются асимптотические свойства именно такой последовательности интервалов восстановления (у нас это ψi) с независимыми приращениями (pi), в котором допускается зависимость внутри соответствующих пар сл. в. (pi и ψi). Известны характеристики суммы приращений ZT, которая накапливается в процессе покрытия интервалами восстановления большого (относительно них) отрезка времени T. Поскольку в нашей системе G2|G2|1 сл. в. ZT представляет собой суммарное время прерываний рядовой заявки при фиксированном времени ее обслуживания x' = T, то эти известные характеристики являются ее условными вероятностными характеристиками.
Общий подход к имитации системы G2|G2|1 при больших α будет состоять в том, чтобы перейти от нее к моделированию системы S' класса G|G|1, которая получается удалением (так или иначе скомпенсированным) из исходной системы потока приоритетных заявок. В системе S' присутствует только поток рядовых заявок, и их скорректированное время обслуживания определяется как сумма чистого времени обслуживания и времени прерываний, вычисляемого по его условным характеристикам. Задержкой начала обслуживания рядовой заявки, которая может возникать из-за ее прихода во время незавершенного периода занятости p, пренебрежем, т. к. при α → ∞ она в среднем сводится к нулю.


 

 

3.         Метод усреднения времени прерываний


Из свойств восстановлений с приращениями [3] вытекает, что время ZT прерываний обслуживания рядовой заявки при больших значениях α в среднем пропорционально ее чистому времени обслуживания T:
Суммируя чистое время обслуживания рядовой заявки T со средним временем прерываний , получаем общее время обслуживания hT = T + = T/(1–r). Таким образом, скомпенсировать удаление приоритетного потока при моделировании системы S' можно увеличением времени обслуживания рядовой заявки в (1–r)–1 раз. Именно это и реализуется известным практическим приемом, упомянутым в [1].
Однако такой метод компенсации, пренебрегающий дисперсией времени прерываний ZT, занижает и дисперсию скорректированного времени обслуживания, и вместе с нею занижает среднее время ожидания рядовых заявок.


 

 

4.         Метод суммы периодов занятости


Используя результаты теории восстановлений [3], второй момент времени ZT прерываний можно выразить в форме коэффициента вариации следующим образом:
Время прерываний ZT сходится по распределению к нормальной сл. в., имеющей коэффициент вариации (4) и среднее значение (3).
В формуле (4) величина пропорциональна α–1. Следовательно, коэффициент вариации , а вместе с ним и погрешности известного метода усреднения, пропорциональны α–1/2, т. е. уменьшаются достаточно медленно.
Для того, чтобы при компенсации времени прерываний ZT учитывать его второй момент (4), необходимо определить соответствующие характеристики системы S, в ко-торой присутствует только приоритетный поток заявок. Это можно сделать с помощью моделирования системы S, которое имеет «обычную» трудоемкость. Поэтому в целом моделирование системы G2|G2|1 получается двухэтапным. На втором этапе моделирует-ся система S' (только с рядовыми заявками). В системе S' перед обслуживанием рядо-вой заявки сначала определяется ее чистое время обслуживания x' = T, а затем к нему добавляется суммарное время прерываний, которое имеет среднее и коэффициент вариации , вычисляемые через T по формулам (3) и (4).
Асимптотические свойства рассмотренных процессов восстановления позволяют также определить два момента числа  T прерываний обслуживания

Сл. в.  T и ZT при больших α распределены по двухмерному нормальному зако-ну, и коэффициент корреляции между ними не зависит от α.
Метод суммы периодов занятости исследован аналитическими средствами и экспериментально. В качестве критерия точности метода использовалась ошибка , вносимая компенсацией в среднее время ожидания рядовых заявок.
Аналитическая проверка метода на системах класса M2|G2|1, выполненная с помощью имеющихся для этого класса СМО точных решений [4], показала, что при их имитации ошибка метода при любом α.
Экспериментальная проверка, выполненная с моделями на языке GPSS, подтвердила высокую точность метода в классе систем G2|G2|1. Коэффициенты вариации интервала поступления и времени обслуживания заявок варьировались в пределах от 0 до 3. На практике, в широком диапазоне параметров СМО, уже при α = 10 ÷ 20 условное время прерываний ZT с высокой точностью отвечает нормальному распределению с параметрами (3), (4).
Недостатком метода, усложняющим планирование имитационного эксперимента, является необходимость предварительной имитации системы S для оценки величин r, , и , используемых на основном этапе моделирования.
Заметим, что в случае, если система S относится к классу M|G|1, эти величины известны:


 

 

5.         Метод суммы периодов обслуживания


Формирование времени прерываний ZT можно представить и в виде другого механизма восстановлений и накоплений, определяемого прямо через сл. в. t и x, которые имеют заданные распределения вероятностей A(t) и B(t). Сл.в. ZT может быть представлена как сумма длительностей обслуживания всех прерывающих заявок:
ZT = x1 + x2 + … +xnT, (8)
где nT – число прерывающих заявок. При этом nT определяется как такое число незави-симых слагаемых вида (τi – xi) в сумме (τ1 – x1) + (τ2 – x2) + … + (τnT – xnT), при котором добавление еще одного слагаемого (τnT+1 – xnT+1) приводит к превышению заданного чис-того времени T обслуживания рядовой заявки. Система сл. в. {xi, (τi–xi)},
(i = 0, 1, 2, …, nT) имеет, с точностью до обозначений, те же свойства, которые установ-лены выше для системы сл.в. {pi ,yi}, (i = 0, 1, 2, …, gT), за тем несущественным при больших α исключением, что слагаемые (τi – xi) могут быть отрицательными. Следова-тельно, в соотношениях (3) – (7) все параметры сл.в. p и y можно просто заменить со-ответствующими им параметрами сл.в. x и (τ – x). Этот способ применения теории вос-становлений менее очевиден, но приводит к более простым и хорошо интерпретируе-мым формулам. В роли интервала восстановления здесь выступает сл. в. (τ – x).
Выполняя в формулах (3) – (7) после оговоренной замены переменных алгебраические преобразования, учитывающие простые связи между разными представлениями моментов сл. в., получаем следующие результаты.
Во-первых, из (3) и (4) после соответствующих замен и упрощений находим:

Формулы (9) и (10) выражают моменты сл. в. ZT непосредственно через характеристики интервала поступления τ и времени обслуживания x приоритетных заявок, вследствие чего отпадает необходимость этапа предварительной имитации системы S перед моделированием системы S'.
Во-вторых, преобразуя таким же способом соотношения (5) и (6), находим два первых момента числа прерывающих заявок nT:

которое обязано быть точным при α → ∞ и, следовательно, является точным при любом значении α, т. к. не зависит от него. Соотношение (14), таким образом, представляет собой инвариант, выполняющийся точно в любой системе G|G|1.
Метод суммы периодов обслуживания эквивалентен по точности методу суммы периодов занятости, но значительно проще в практическом применении. Однако он несколько уступает в плане универсальности; он не позволяет, например, имитировать число gT прерывающих периодов занятости.
С учетом (9), (10) и формулы Кингмана [5] для ρΣ → 1, теперь можно оценить погрешность известного метода усреднений. При больших ρΣ оценка величины методом усреднений удовлетворяет приближенному равенству:

где C – коэффициент вариации времени обслуживания рядовой заявки. При фиксированных α и ρ относительное занижение времени ожидания (15) сверху не ограничено.
Разработанные методы суммирования, напротив, практически не вносят погрешности, т. к. уже при α > 10 ¸ 20 учитывают время прерываний с точностью до распределения. При значениях α порядка 10n, когда обычное усреднение прерываний из-за существенных ошибок может оказаться неприемлемым, эти методы позволяют без потери точности ускорить имитацию, соответственно, примерно в 10n раз.


 

 

6.         Литература


1. Максимей И. В. Функционирование вычислительных систем (Измерения и анализ). – М.:Советское радио, 1979. – 272 с.
2. Iglehart D. L. The regenerative method for simulation analysis//In Current Trends in Programming Methodology. Vol. III: Software Modelling, K.M. Chandy and R.T. Yen, Eds., Prentice-Hall, Englewood, Cliffs N.J., 1978. P. 52–71.
3. Кокс Д. Р. Теория восстановления /Кокс Д.Р, Смит В. Л.: Пер. с англ./Под ред. Ю. К Беляева. – М.: Сов. радио, 1967 г. – 312 с.
4. Гнеденко Б. В. Приоритетные системы обслуживания/ Б. В. Гнеденко , Э. А. Даниэлян , Б. Н. Димитров и др. – М.: Изд-во Московского университета, 1973. – 447 с.
5. Клейнрок Л. Вычислительные системы с очередями: Пер. с англ./Под ред. Б. С. Цыбакова. – М.: Мир, 1979. – 600 с.

 


Распечатано с портала GPSS.RU (c) В. Н. Задорожный , 2005 г.