close

Вход

Забыли?

вход по аккаунту

?

Параметры потока транзакций генерируемых по принципу поллинга..pdf

код для вставкиСкачать
Известия ТулГУ. Технические науки. 2016. Вып. 2
УДК 681.5 (519.95)
ПАРАМЕТРЫ ПОТОКА ТРАНЗАКЦИЙ, ГЕНЕРИРУЕМЫХ
ПО ПРИНЦИПУ ПОЛЛИНГА
А.А. Аршакян, Е.В. Ларкин
Исследуется поллинг как способ опроса периферийных устройств. Определен
типовой вид функции распределения времени между двумя транзакциями при поллинге.
Показано, что типовую функцию распределения целесообразно аппроксимировать
функцией, имеющей более компактный вид. С использованием метода неопределенных
множителей Лагранжа получена система уравнений для расчета параметров аппроксимирующей функции. Показано, что если в структуре алгоритма имеется хотя бы
один цикл, то функция распределения может быть аппроксимирована композицией
экспоненциальных законов. С помощью компьютерного эксперимента, проведенного по
методу Монте-Карло, показано, что в этом случае аппроксимирующей функцией может быть Гамма-распределение.
Ключевые слова: алгоритм, поллинг, поток транзакций, функция распределения, аппроксимация, гамма-распределение.
Поллинг как способ опроса периферийных устройств достаточно
часто встречается в системах цифрового управления объектами и в информационных системах [1, 2, 3]. Алгоритмы, реализующие опрос периферийных устройств, обладают целым рядом особенностей, которые достаточно
полно отражены в известных работах [4, 5, 6, 7]:
алгоритмы являются циклическими, т.е. они имеют оператор начала, но не имеют оператора окончания, окончание вычислительного процесса производится через внешнее прерывание;
опрос периферийных устройств производится за счет включения в
алгоритм специальных операторов управления транзакциями, количество
которых в алгоритме может быть произвольным;
выбор ветви продолжения вычислительного процесса в местах
ветвления алгоритма является случайным и определяется условиями,
включенными в операторы принятия решения и законами распределения
обрабатываемых данных;
время выполнения операторов алгоритма является случайным,
функции распределения времени выполнения операторов также определяются законами распределения обрабатываемых данных.
В подобном аспекте алгоритмы информационно-управляющих систем рассматривались в [8], где процесс интерпретации детерминированного алгоритма для внешнего, по отношению к системе, наблюдателя рассматривался как полумарковский процесс с непрерывным временем. Операторы алгоритма рассматривается как состояния процесса, а интерпрета40
Информатика, вычислительная техника и обработка информации
ции алгоритма в целом рассматривается как блуждание по состояниям.
Поток транзакций формируется когда полумарковский процесс через случайные моменты времени попадает в состояния, моделирующие обращения к периферийному устройству.
В [9, 10] показано, как можно определить время между двумя транзакциями при поллинге и получены зависимости для оценки названных
временных интервалов, которые в общем случае имеют вид
J
f (t ) = ∑
j =1
p j f j (t ) ,
(1)
где p j - вероятность того, что реализацией блужданий по полумарковской
цепи между двумя состояниями, моделирующими один и тот же, или пару
операторов транзакций будет j-я конкретная траектория; f j (t ) - плотность
распределения времени блуждания по j-й конкретной траектории.
Использование f (t ) в виде (1) для анализа информационноуправляющих систем вызывает известные трудности, и поэтому целесообразно аппроксимировать указанное выражение законом, часто используемым при анализе, например систем массового обслуживания [11].
Представим (1) в виде функции распределения
t J
J
F (t ) = ∫ ∑ p j f j (τ )dτ = ∑ p j F j (t ) ,
0 j =1
(2)
j =1
t
где F j (t ) = ∫ f j (τ )dτ - функция распределения времени до наступления j-го
0
события.
Очевидно, что F (t ) - функция неубывающая, так как является линейной композицией неубывающих функций F j (t ) , F (0 ) = 0 ; lim F (t ) = 1 ,
t →∞
J
т.к. ∑ p j = 1 и lim F j (t ) = 1 .
t →∞
j =1
Аппроксимируем функцию F (t ) законом распределения g (t , A) , где
A = (a1 , ..., an , ..., a N ) - вектор параметров. В общем случае ошибка аппроксимации определяется выражением
2
∞ J

ε = ∫  ∑ p j F j (t ) − G (t , A) dt ,

0  j =1
t
где G (t , A) = ∫ g (τ, A)dτ .
0
41
(3)
Известия ТулГУ. Технические науки. 2016. Вып. 2
Отметим, что критерий (3) имеет вид суммы квадратов разности, а
не взвешенной суммы квадратов разности, которая используется в задачах
выравнивания статистических рядов [12]. Это происходит вследствие того,
что плотность распределения вида (1) уже отражает только существенные
особенности статистического материала, по которому были получены
плотности f j (t ) и вероятности p j . Случайности, вызывающие отклонение
статистик, связанные с недостаточным объемом экспериментальных данных, были учтены при получении казанных плотностей и вероятностей [3,
5, 7, 8].
Для аппроксимирующего закона g (t , A) должны выполняться ограничения:
∞
∫ dG (t , A) = 1 ;
t =0
∞
∫ tdG (t , A) = T ;
(4)
t =0
∞
k
∫ (t − T ) dG (t , A) = µ k , 2 ≤ k ≤ K ,
t =0
∞ J
где T = ∫ t ∑ p j dF j (t ) – математическое ожидание времени между двумя
0 j =1
∞
J
0
j =1
транзакциями при поллинге; µ k = ∫ (t − T )2 ∑ p j dF j (t ) - k-й центральный
момент плотности распределения (1), в частности, при k = 2 - это дисперсия плотности распределения времени между двумя транзакциями.
Для поиска оптимальных значений параметров можно воспользоваться методом неопределенных множителей Лагранжа. Функция Лагранжа будет иметь вид [13]
2
∞ J

Φ ( A, B) = ∫  ∑ p j F j (t ) − G (t , A ) dt +

0  j =1
∞
∞
 ∞


 K


+ b0 1 − ∫ dG (t , A ) + b1 T − ∫ tdG (t , A ) + ∑ bk µ k − ∫ (t − T )k dG (t , A ), (5)
 0


 k = 2 

0
0
где B = (b0 , b1, b2 , ..., bK ) – вектор неопределенных множителей Лагранжа.
В соответствии с методом неопределенных множителей Лагранжа
необходимые условия существования экстремума будут иметь вид:
42
Информатика, вычислительная техника и обработка информации
Математическое ожидание и дисперсия плотности распределения
f(t) равны, соответственно Tm,n = 1 с, Dm,n = 0,03 с 2 , 1 ≤ m, n ≤ 3 . Возврат
генератора в состояние 1 означает генерацию транзакции. Компьютерный
эксперимент будем проводить по следующей методике [15, 16]:
1) обнуление счетчика числа реализаций, l = 0.
2) присвоение статуса текущего первому состоянию ñl = 1 .
3) обнуление счетчика времени, t l = 0 .
4) запуск генератора случайных чисел и получение случайного числа 1 ≤ π ≤ 1 с равновероятным распределением.
5) если 0 ≤ π ≤ 0,333 , то a l = 1 ; если 0,333 < π ≤ 0,666 , то al = 2 ; если 0,666 < π ≤ 1 , то al = 3 .
6) запуск генератора случайных чисел и получение числа π.
приращения
времени
по
зависимости:
7) Определение
∆ t = 0,6π + 0,7 s
8) t l := t l + ∆ t ;
9) если ñl ≠ 1 , то 4).
10) разгрузка tl в массив результатов.
11) l := l + 1 . Если l < L , то 3).
12) конец эксперимента.
В результате формируется гистограмма, показанная на рис. 4 штрихами.
Оценка математического ожидания и дисперсии плотности распределения времени между транзакциями по гистограмме дают 1T1,1 = 3 c ;
1
D1,1 = 6,123 c 2 .
Гистограмму рекомендуется
Г-распределения, имеющего вид
аппроксимировать
 0 при t < 0,

f (t ) =  λα α −1
exp(−λt ) при t < 0,
 Γ (α ) t

с
помощью
(8)
где α > 0 - параметр формы; λ > 0 - параметр масштаба;
∞
Γ(α) = ∫ x α −1 exp( −λx ) dx .
0
Параметры λ и α распределения (8) определяются по зависимостям
1
λ=
T1,1
1
D1,1
45
;
(9)
Информатика, вычислительная техника и обработка информации
5. Ивутин А.Н., Ларкин Е.В. Временные и вероятностные характеристики транзакций в цифровых системах управления // Известия Тульского государственного университета. Технические науки. Вып. 1. Тула: Издво ТулГУ, 2013. С. 252 - 258.
6. Ивутин А.Н., Ларкин Е.В. Прогнозирование времени выполнения
алгоритма // Известия Тульского государственного университета. Технические науки. Вып. 3. Тула: Изд-во ТулГУ, 2013. С. 301 - 315.
7. Ларкин Е.В., Котов В.В., Котова Н.А. Оценка эффективности
программного обеспечения робота с использованием сетей Петри-Маркова
// Известия Тульского государственного университета. Технические науки.
Вып. 9. Ч. 2. Тула: Изд-во ТулГУ, 2013. С. 156 - 163.
8. Клинцов Г.Н., Ларкин Е.В. Полумарковое моделирование алгоритмов выполнения программы на ЭВМ // Известия Тульского государственного университета. Технические науки. Вып. 9. Ч. 1. Тула: Изд-во ТулГУ, 2015. С. 143 - 149.
9. Ларкин Е.В., Привалов А.Н., Клепиков А.К. Алгоритм последовательных упрощений при оценке временной сложности алгоритмов с применением полумарковских моделей // Известия Тульского государственного университета. Технические науки. Вып. 9. Ч. 2. Тула: Изд-во ТулГУ,
2014. С. 83 - 98.
10. Larkin E.V., Lutskov Yu.I., Ivutin A.N., Novikov A.S. Simulation of
concurrent process with Petri-Markov nets // Life Science Journal. 2014. N. 11.
P. 506 - 511.
11. Ларкин Е.В., Котов В.В., Титов С.В. Аппроксимация взвешенной суммы плотностей распределения вероятностным законом // Известия
ТулГУ. Серия: Проблемы специального машиностроения. Вып. 3. Ч. 1. Тула: ТулГУ, 2000. С. 389 - 393.
12. Румшинский Л.З. Математическая обработка результатов эксперимента: Справочное руководство. М.: Наука, 1971. 192 с.
13. Аоки М. Введение в методы оптимизации. М.: Наука, 1977.
314 с.
14. Хастингс Н., Пиккок Дж. Справочник по статистическим распределениям. М.: Статистика, 1980. 96 с.
15. Ivutin A.N, Larkin E.V. Simulation of Concurrent Games // Bulletin
of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software. Chelyabinsk. 2015. Vol. 8. № 2. P. 43 - 54.
16. Котов В.В., Котова Н.А., Ларкин Е.В. Метод имитационного
моделирования систем с использованием сетей Петри-Маркова // Известия
Тульского государственного университета. Технические науки. Вып. 9.
2015. С. 164 - 170.
Аршакян Александр Агабегович, канд. техн. наук, докторант, elarkin@mail.ru,
Россия, Тула, Тульский государственный университет,
47
Известия ТулГУ. Технические науки. 2016. Вып. 2
Ларкин Евгений Васильевич, зав. кафедрой, докт. техн. наук, проф.,
elarkin@mail.ru, Россия, Тула, Тульский государственный университет
PARAMETERS OF FLOW OF TRANSACTIONS,
WHICH ARE GENERATED ON POLLING PRINCIPLE
A,A. Arshakyan, E.V. Larkin
Polling as the technique of scanning of peripherals is investigated. Typical form of
distribution function of time between neighbor transactions, when polling process, is defined.
It is shown that the typical distribution function it is expediently to approximate with a compact function. With use Lagrange multipliers method the system of equations for calculation
of parameters of approximated function is obtained. It is shown that when in a structure of
algorithm there is at least one cycle, distribution function may be the exponential one. With
use of Monte-Carlo method it is shown that in this case as the approximated function may be
choose Gamma-function
Key words: algorithm, polling, flow of transactions, distribution function, approximation, Gamma-function.
Arshakyan Alexander Agabegovich, candidate of technical science, postgraduate,
elarkin@mail.ru, Russia, Tula, Tula State University,
Larkin Eugene Vasilyevich, head of chair, doctor of technical science, professor,
elarkin@mail.ru, Russia, Tula, Tula State University
УДК 623.320
АЛГОРИТМ УСТРАНЕНИЯ ИНТЕРФЕРЕНЦИИ ПОСЛЕ
ЛИНЕЙНОГО СИНТЕЗА АПЕРТУРЫ АНТЕННЫ
РАДИОЛОКАЦИОННОГО ДАТЧИКА
Ю.И. Вареница, Ю.И. Мамон, К.А. Хомяков
Предложен алгоритм устранения интерференции сигнала радиолокационного
датчика без отказа от использования монохроматического зондирующего сигнала.
Показано, что для уменьшения интерференции в лепестках восьмёрки передаточных
функций точек траектории объекта, нужно просуммировать или перемножить значения
взаимно корреляционных функций в точках пересечения корреляционных лучей. По наборам параллельных корреляционных лучей под разными углами можно восстановить приемлемое изображение объекта.
Ключевые слова: радиолокационный датчик, опорный траекторный сигнал,
интерференция, синтезированная апертура, антенна, передаточная функция, корреляционная функция, матрица изображения.
Известен теоретический аппарат синтеза апертуры антенны радиолокационного датчика на базе применения взаимных корреляционных функций
объектного траекторного сигнала с набором опорных траекторных сигналов
48
Документ
Категория
Без категории
Просмотров
4
Размер файла
552 Кб
Теги
генерируемых, транзакций, поллинга, pdf, принципы, поток, параметры
1/--страниц
Пожаловаться на содержимое документа