Известия Тульского государственного университета. Технические науки, 2017, № 2

Министерство образования и науки Российской Федерации 
 
Федеральное государственное бюджетное  
образовательное учреждение высшего образования  
«Тульский государственный университет» 
 

 
 
 
16+ 
ISSN 2071-6168 
 
 
 
 
 
 
 
ИЗВЕСТИЯ  
ТУЛЬСКОГО ГОСУДАРСТВЕННОГО 
УНИВЕРСИТЕТА 
 
 
ТЕХНИЧЕСКИЕ НАУКИ 
 
 
Выпуск 2 
 
 
 
 
 
 
 
 
 
 
 
 
Тула 
Издательство ТулГУ 
2017 

УДК 621.86/87                                                                             ISSN 2071-6168 
 
 
Известия Тульского государственного университета. Технические науки.  
Вып. 2. Тула: Изд-во ТулГУ, 2017. 324 с.
 
Рассматриваются научно-технические проблемы приборов и управления, машиностроения и машиноведения, электротехники, информатики, 
вычислительной техники и обработки информации. 
Материалы предназначены для научных работников, преподавателей вузов, студентов и аспирантов, специализирующихся в проблематике 
технических наук. 
 
 
Редакционный совет 
 
М.В. ГРЯЗЕВ – председатель, В.Д. КУХАРЬ – зам. председателя, 
В.В. ПРЕЙС – главный редактор, А.А. МАЛИКОВ – отв. секретарь, 
И.А. БАТАНИНА, О.И. БОРИСКИН, М.А. БЕРЕСТНЕВ, В.Н. ЕГОРОВ, 
О.Н. ПОНАМОРЕВА, Н.М. КАЧУРИН, В.М. ПЕТРОВИЧЕВ 
 
 
 
Редакционная коллегия 
 
О.И. Борискин (отв. редактор), С.Н. Ларин (зам. отв. редактора), 
Б.С. 
Яковлев 
(отв. 
секретарь), 
И.Л. 
Волчкевич, 
Р.А. 
Ковалев,  
М.Г. Кристаль, А.Д. Маляренко (Республика Беларусь), А.А. Сычугов,  
Б.С. Баласанян (Республика Армения), А.Н. Чуков  
 
 
Подписной индекс 27851 
по Объединённому каталогу «Пресса России» 

Сборник 
зарегистрирован 
в 
Федеральной 
службе по надзору в сфере связи, информационных 
технологий и массовых коммуникаций (Роскомнадзор).  
ПИ № ФС77-61104 от 19 марта 2015 г.  

 
«Известия ТулГУ» входят в Перечень ведущих 
научных 
журналов 
и 
изданий, 
выпускаемых 
в 
Российской Федерации, в которых должны быть 
опубликованы научные результаты диссертаций на 
соискание учёной степени доктора наук 
 
 
© Авторы научных статей, 2017 
© Издательство ТулГУ, 2017 

Приборы и управление 
 

 
3

 
 
 
 
 
 
ПРИБОРЫ И УПРАВЛЕНИЕ 
 
 
 
 
УДК 004.942 
 
ПЕТРИ-МАРКОВСКАЯ МОДЕЛЬ ПРЕРЫВАНИЙ 
 
Е.В. Ларкин  
 
Исследуется время интерпретации алгоритмов на ЭВМ Фон Неймановского 
типа. С использованием фундаментального аппарата полумарковских процессов построена аналитическая математическая модель для оценки времени выполнения программы при отсутствии прерываний. Показано, что внешние прерывания представляют собой результат работы независимого случайного процесса, который развивается параллельно с интерпретацией алгоритма. Для описания взаимодействия двух 
процессов применен аппарат сетей Петри-Маркова. Построена базовая структурнопараметрическая модель функционирования ЭВМ при наличии внешних прерываний. 
Показано, что в общем случае Петри-Марковская модель является бесконечной. Разработана рекурсивная процедура блуждания по сети Петри-Маркова для данного конкретного случая. Показано, что процесс блуждания не является полумарковским. 
Предложен метод трансформации Петри-марковской модели в строго полумарковский процесс. 
Ключевые слова: ЭВМ Фон Неймановского типа, прерывание, временные характеристики, полумарковский процесс, сеть Петри-Маркова, модель, блуждание. 
 
1. Введение. Режим прерываний широко используется в системах 
цифрового управления объектами [1, 2]. В соответствии с этим режимом, 
при поступлении прерывания центральный процессор прекращает интерпретацию текущего алгоритма и переходит к интерпретации алгоритма обработки прерываний, по завершении которой возвращается к выполнению 
отложенной программы. При практической реализации алгоритмов возможны прерывания двух типов, программные и аппаратные. Программные 
прерывания приводят к обычным ветвлениям в алгоритмах [3], поэтому 
учет их влияния на общее время интерпретации является достаточно несложной инженерной задачей. Аппаратные прерывания генерируются 
внешним источником, функционирование которых не зависит от ЭВМ, поэтому в компьютерной системе с аппаратными прерываниями имеет место 

Известия ТулГУ. Технические науки. 2017. Вып. 2 
 

 
4

параллельный процесс, разворачивающийся во времени: с одной стороны, 
это ЭВМ, интерпретирующая текущий алгоритм, а с другой стороны - это 
внешний источник прерываний. Как и в любом параллельном процессе, в 
исследуемой системе между субъектами возникает «соревнование» [4, 5, 6] 
за пользование аппаратными ресурсами, в частности, процессором. Наличие «соревнования», и «победа» в «соревновании» генератора прерываний 
увеличивает время интерпретации основного алгоритма. Увеличение времени зависит от плотности потока команд на прерывание и от временных 
характеристик алгоритма обработки прерываний. Оценка времени интерпретации алгоритма в этом случае должна сводиться к анализу результатов 
«соревнования» между текущим алгоритмом и генератором прерываний. 
Модели, позволяющей производить подобную оценку, в настоящее время 
не существует, что объясняет необходимость и актуальность исследований 
в данной области. 
2. Временные характеристики алгоритма без прерываний. Рассмотрим процесс выполнения алгоритма на ЭВМ Фон Неймановского типа. Он сводится к последовательной интерпретации операторов, которая 
разворачивается во времени. После выполнения  очередного оператора переход к одному из следующих возможных операторов осуществляется для 
внешнего наблюдателя случайным образом. Время, в течение которого 
выполняется оператор, является случайным. В силу этого естественной 
моделью, описывающей интерпретацию алгоритма, является полумарковский процесс [7, 8, 9] вида 

( )
{
}
t
h
,
Β
=
µ
,                                                    (1) 
где 
{
}
M
J
J
j
β
β
β
β
β
=
Β
+
...,
,
,
...,
,
...,
,
1
1
 
- 
множество 
состояний; 

( )
( )
[
]
t
h
t
m
j,
=
h
 - полумарковская матрица, имеющая размер 
M
M ×
. 

Типовая структура алгоритма самого общего вида приведена на 
рис. 1. 
 
 

β1

E
β1 

... 

β1

βJ 

βJ+1 

βM 

 
Рис. 1. Типовая структура алгоритма 

Приборы и управление 
 

 
5

Состояния полумарковского процесса, показанного на рис. 1, имеют 
следующий физический смысл:  

1
β  - стартовое состояние, являющееся математическим аналогом 
оператора «начало» алгоритма;  

{
}
M
m
J
E
B
β
β
β
=
⊃
+
...,
,
...,
,
1
 - подмножество поглощающих состояний, являющихся математическим аналогом операторов «конец» алгоритма. 
Структура полумарковского процесса такова, что для любого 
E
j ∉
β
, 
1
≠
j
 всегда существует хотя бы один путь 
j
β
→
β1
 и хотя бы один 

путь 
E
j →
β
. В силу этого структура и параметры полумарковского про
цесса (1) таковы, что в полумарковской матрице: 
первый столбец содержит только нулевые элементы; 
поглощающими состояниями являются только состояния подмножества E, т.е.  строки с (J + 1)-й по M-ю содержат только нулевые элементы; 
для остальных строк 

( )
J
j
dt
t
h
M

m
jm
≤
≤
=
∑ ∫
=

∞

1
,1
1 0

.                                     (2) 

Таким образом, все возможные пути 
E
→
β1
 составляют полную 
группу несовместных событий. Для этого случая плотность распределения 
времени достижения одного из состояний подмножества E из состояния 1
β  
определяется по зависимости 

( )
( )
[
]
{
}








⋅
⋅
=
∑
∞

=

−

1
1
1

k
E
c
k
r
t
L
L
t
f
I
h
I
,                              (3) 

где L и L-1 - соответственно прямое и обратное преобразования Лапласа; 

I
r
 - вектор-строка, включающий M элементов, первый элемент которого 

равен единице, а остальные элементы равны нулю; 
E

cI
 - вектор-столбец, 
включающий M элементов, элементы с первого по J-й которого равны нулю, а остальные элементы равны единице. 
Плотность распределения ( )t
f
 определяет время выполнения алгоритма. По указанной плотности могут быть найдены минимальное, среднее 
и максимальное время выполнения: 

( )t
f
T
arg
min
min =
; 
( )t
f
T
arg
max
max =
;                          (4) 

( )dt
t
tf
T
∫
∞

=

0

; 
(
)
( )dt
t
f
T
t
D
∫
∞

−
=

0

2
. 

Полумарковский процесс после упрощения приведен на рис. 2 а. 

Известия ТулГУ. Технические науки. 2017. Вып. 2 
 

 
6

βEf
βf 
βg 

f(t) 
g(t) 

a
b

βEv
βv 
v(t) 

c
 
 
Рис. 2. Структура упрощенного полумарковского процесса а, 
генератора b и обработчика с прерываний 
 
Внешний генератор прерываний представлен на рис. 2 b, а на рис. 2 
с показан полумарковский процесс обработки прерываний. Естественно, 
что наличие внешних прерываний изменяет время выполнения алгоритма, 
поскольку вычислительные ресурсы ЭВМ Фон Неймановского типа в этом 
случае тратятся на интерпретацию алгоритма обработки прерывани1. 
3. Модель выполнения алгоритма при наличии прерываний. 
Рассмотрим случай, когда прерывания в ЭВМ Фон-Неймановского типа 
поступают от внешнего источника. Полумарковский процесс, описывающий интерпретацию алгоритма при наличии прерываний, является 3параллельным и имеет следующий вид: 

{
} ( )
{
}
t
Ev
Ef
v
f
g
h~
,
,
,
,
,
~
β
β
β
β
β
=
µ
,                                    (5) 

где t - время; 
E
f
g
β
β
β
,
,
 - множество состояний; 
g
β  - состояние, модели
рующее генерацию одного прерывания; 
f
β
 - состояние, моделирующее 

выполнение алгоритма; 
v
β  - состояние, моделирующее алгоритм обработки прерываний; 
Ef
β
 - поглощающее состояние полумарковской модели 

алгоритма; 
Ev
β
 - поглощающее состояние полумарковской модели обработчика прерываний; 

( )

( )

( )
( )












=
t
t
t
t

v

f

g

h
0
0
0
h
0
0
0
h
h

32
31

23
21

13
12
~
;                                       (6) 

( )
( )
[
]
t
g
t
g
=
h
; 
( )
( )





=
0
0
0
t
f
t
f
h
; 
( )
( )





=
0
0
0
t
v
t
v
h
;                   (7) 

(
)
0
,0
13
12
=
= 0
0
; 




=
=
0
0
31
21
0
0
; 




=
=
0
0
0
0
32
23
0
0
. 

Полумарковский процесс (5) является не просто 3-параллельным. 
Все три элементарных процесса находятся во взаимодействии. Взаимодействие осуществляется по следующему правилу. При старте одновременно 
запускаются процессы  
( )t
f
h
 и  
( )t
g
h
, которые вступают в «соревнование» 

[10, 11, 12]. Если «побеждает» процесс 
( )t
f
h
, to интерпретация алгоритма 

заканчивается, в противном случае запускается процесс 
( )t
v
h
, который 

Приборы и управление 
 

 
7

«соревнуется» с процессом 
( )t
g
h
. Если в этом случае «побеждает» процесс 

( )t
g
h
, то вновь запускается обработчик прерываний. В противном случае 

происходит возврат в процесс 
( )t
f
h
, который продолжается с того момен
та, на котором был прерван, при этом «соревнование происходит с продолжением ожидания срабатывания генератора прерываний. Теория графов не позволяет описать разделение процессов («fork») и слияние процессов («joint»). Поэтому далее для моделирования использован аппарат сетей 
Петри-Маркова [10, 11, 12].  
Сеть Петри-Маркова (СПМ), описывающая функционирование алгоритма с прерываниями, приведена на рис. 3.  
 

z1 

... 

0a2

1a3

1a1

1a2

2a3

2a1

2a2

... 

ka3

ka1

ka2

k+1a3

k+1a1

k+1a2

z2 

z3 

zk 

zk+1 

zk+2 

... 

A1

A2

Ak

Ak+1

k-1a2

Sf / Sg

Sv / Sg 

Sv / Sg

Sv / Sg 

 
Рис. 3. Сеть Петри-Маркова, моделирующая алгоритм с прерываниями 

Известия ТулГУ. Технические науки. 2017. Вып. 2 
 

 
8

СПМ имеет следующий вид: 

( )
{
}
Λ
Φ
,
,
,
t
Z
A
=
Π
,                                              (8) 

где 
{
}
...
,
...,
,
, 1

2

0

k

kA
A
a
A =
 - множество мест, включающее место 
2

0a , мо
делирующее 
старт 
процесса, 
и 
подмножества 
{
}
3
2
1
,
,
a
a
a
A
k
k
k
k
=
 

...
,2
,1
=
k
 мест, моделирующих процессы, участвующие в «соревновании» 

k-го уровня; 
1
a
k
 - место, моделирующее текущий алгоритм, интерпретируемый ЭВМ, которым может быть алгоритм (плотность распределения 
времени выполнения ( )t
v
) обработки прерываний, или основой алгоритм 

(плотность распределения времени выполнения 
( )t
f
); 
2
a
k
 - место, моде
лирующее функционирование генератора прерываний,  
3
a
k
 - место, моделирующее возврат на предыдущий уровень обработки прерываний;  

{
}
...
,
...,
,
1
k
z
z
Z =
 - множество переходов, определяющих уровень обработки прерываний; 
( )t
Φ
 - матрица плотностей распределения; Λ - матрица логических условий выполнения полушагов из переходов. 
Структура СПМ описывает многоуровневую. процедуру парных 
«соревнований» трех субъектов: генератора прерываний 
g
S  с основным 

алгоритмом 
f
S
 и генератора прерываний 
g
S  с обработчиком прерываний 

v
S    
Первый уровень «соревнований» представлен подсетью от места 

2

0a  до мест 
,
,
3

2

3

1
a
a
т.е. 

( )
{
}
1
1
1
1
1
,
,
,
Λ
Φ t
Z
A
=
Π
,                                         (10) 

где 
{
}
2

2

2

2

1

2

3

1

2

1

1

1

2

0

1
,
,
,
,
,
,
a
a
a
a
a
a
a
A =
 
- 
подмножество 
мест; 

{
}
3
2
1
1
,
,
z
z
z
Z =
 - подмножество переходов; 
( )
( )
[
]
t
t
ij
ϕ
=
1
Φ
 - 7×3 матрица 

плотностей распределения, задающая временные интервалы «соревнований»; 
[
]
ji
λ
=
1
Λ
 - 3×7 матрица логических условий выполнения полушагов 

из переходов; 

 
( )

( )

( )
( )

( )

( )
( )




























ϕ

ϕ

δ

ϕ

ϕ
δ

=

0
0
0

0

0

0
0
0
0
0

0
0
0

0

0

2
2
1
2

2
1
1
1

1

t

t

t

t

t
t

t
Φ
;                                     (11) 

[
]
ij
λ
=
1
Λ
;                                                     (12) 

Приборы и управление 
 

 
9

;0
36
35
34
33
32
31
27

23
22
21
17
16
14
11
=
λ
=
λ
=
λ
=
λ
=
λ
=
λ
=
λ
=

=
λ
=
λ
=
λ
=
λ
=
λ
=
λ
=
λ

(
) (
)
1
3

2

1
2

0

13
12
,
,
z
a
z
a
∨
=
λ
=
λ
; 
(
)
2
2

1

15
,z
a
=
λ
; 

(
) (
)
2
3

3

2
2

1

25
24
,
,
z
a
z
a
∨
=
λ
=
λ
; 
(
)
2
1

1

26
,z
a
=
λ
; 
(
)
2
1

2

37
,z
a
=
λ
. 

Рекурсивная процедура первого уровня «соревнований» реализует
ся следующим образом. После полушага (
)
1
2

0
,z
a
 логические условия становятся равными 
1
12 =
λ
; 
1
13 =
λ
. При этом, в соответствии с (12), разре
шается выполнение полушагов (
)
1

1

1, a
z
 и (
)
2

1

1, a
z
. После выполнения указанных полушагов запускаются процессы 
f
S
 и 
g
S , и вступают между со
бой в «соревнование», которое разворачивается в физическом времени. На 
первом шаге рекурсии  

( )
( )t
f
t =
ϕ
:
1

1
; 
( )
( )t
g
t =
ϕ
:
2

1
.                                   (13) 

Взвешенные плотности распределения времени выполнения полу
шагов (
)
2
1

1
,z
a
 и (
)
2
2

1
,z
a
 первыми определяются по зависимостям: 

( )
( )
( )
[
]

( )
( )
( )
[
]






Φ
−
⋅
ϕ
=
η

Φ
−
⋅
ϕ
=
η

t
t
t

t
t
t

1
1
2
1
2
1

2
1
1
1
1
1

1

1
,                                    (14) 

где 
( )
( )
∫
τ
τ
ϕ
=
Φ
t
d
t

0

...
...
...
...
. 

Вероятности и плотности распределения времени выполнения по
лушагов (
)
2
1

1
,z
a
 и (
)
2
2

1
,z
a
 первыми равны соответственно 

( )
( )dt
t
dt
t
∫
∫

∞
∞

η
=
π
η
=
π

0

2
1
2
1

0

1
1
1
1
,
.                              (15) 

( )
( )
( )
( ).
;

2

1
2
1

2
1

1

1
1
1

1
1
π

η
=
ψ
π

η
=
ψ
t
t
t
t
 

В том случае, если первым выполняется полушаг (
)
2
1

1
,z
a
, СПМ  

переключается в место 
3

1a , являющееся аналогом поглощающего состояния, и работа алгоритма завершается. В том случае, если первым выполня
ется полушаг (
)
2
2

1
,z
a
, СПМ переключается в места 
1

2a , 
2

2a , и по зависимости [11] 

Известия ТулГУ. Технические науки. 2017. Вып. 2 
 

 
10

( )
( )
( )
(
)

( )
( )
∫

∫

∞

∞

Φ
Φ

τ
τ
+
ϕ
τ
ϕ

=
ϕ

0

1
1
2
1

0
1
1
2
1

1
1
1

:

t
d
t

d
t
t

t
,                                (16) 

оценивается время, оставшееся до окончания пребывания в месте 
1

1a  ( ( )t
1
 
- единичная функция Хэвисайда). Время (16) подставляется в процесс 
f
S . 

После выполнения в первый раз полушагов (
)
1

2

2,
a
z
 и (
)
2

2

2,
a
z
 в 

местах 
1

2a , 
2

2a  начинается «соревнование» процесса обработки прерыва
ния и генератора прерываний, который запускается вновь (
( )
( )t
g
t =
ϕ
:
2

2
). 

Поскольку «соревнование» запускается в первый раз, то 
( )
( )t
v
t =
ϕ
:
1

2
. 
Взвешенные плотности распределения времени выполнения полушагов 
(
)
3
1

2
,z
a
 и (
)
3
2

2
,z
a
 первыми, вероятности и плотности распределения определяются по зависимостям: 
( )
( )
( )
[
]

( )
( )
( )
[
]





Φ
−
⋅
ϕ
=
η

Φ
−
⋅
ϕ
=
η

t
t
t

t
t
t

1
2
2
2
2
2

2
2
1
2
1
2

1

1
,                                    (17) 

( )
( )dt
t
dt
t
∫
∫

∞
∞

η
=
π
η
=
π

0

2
2
2
2

0

1
2
1
2
,
. 
( )
( )
( )
( ).
;

2

2
2
2

2
2

1

2
1
2

1
2
π

η
=
ψ
π

η
=
ψ
t
t
t
t
 

Если в результате «соревнования» первым выполняется полушаг 

(
)
3
1

2
,z
a
 (завершается обработка прерывания), то 
a) выполняется подстановка (подготавливается продолжение работы генератора прерываний)  

( )
( )
( )
(
)

( )
( )
∫

∫

∞

∞

Φ
Φ

τ
τ
+
ϕ
τ
ϕ

=
ϕ

0

2
2
1
2

0
2
2
1
2

2
2
1

:

t
d
t

d
t
t

t
;                                (18) 

б) выполняются полушаги, сначала (
)
3

2

3, a
z
, а затем (
)
1
3

2
, z
a
; 

в) выполняется пара полушагов (
)
1

1

1, a
z
 и (
)
2

1

1, a
z
 и запускается 

процесс «соревнования в местах 
2

1

1

1
, a
a
 с новыми значениями плотностей 

распределения 
( )
( )t
t
2

1

1

1
, ϕ
ϕ
. 
Если в результате «соревнования» первым выполняется полушаг 

(
)
3
2

2
,z
a
 (срабатывает генератор прерываний), то