Недетерминированные автоматы в проектировании систем параллельной обработки. Вашкевич Н.П. - 186 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

186
S
1
S
2
1
S
2
1
S
2
1
S
2
1
S
2
1
S
2
1
S
3
1
S
3
1
S
4
1
S
4
1
S
2
S
3
2
S
4
2
S
4
2
S
ЧО
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
)(
21
SS
kk
S
k
2
S
k
2
S
k
2
S
k
2
S
k
1
S
k
1
S
k
1
S
k
1
S
k
1
S
k
1
S
k
1
S
k
1
S
k
2
S
m
S
m
S
m
S
m
)(
21
SS
pp
S
p
2
S
p
1
S
p
1
)(
21
SS
nn
S
n
2
S
n
1
S
n
1
)(
21
SS
pkpk
S
pk
2
S
pk
1
S
pk
1
Такты
17 18
19 20 21 22 23 24 25 26 27 28 29 30 31 32
Рис.6.10. Временные диаграммы работы алгоритма управления
взаимодействующими параллельными процессами
в задаче «читатели-писатели» (такты 17-32)
Проследим работу управляющего алгоритма по временным
диаграммам для некоторых частных случаев задания заявок на запись и
чтение в процессе работы алгоритма по тактам:
В 1-м такте фиксируются первые ожидающий писатель (
1
1
1
S
) и
ожидающий читатель (
1
1
2
S
).
П р и м е ч а н и е: верхним индексом у событий
S
1
и
S
2
будем определять
порядковые номера писателей и читателей соответственно.
Во 2-м такте зарождается событие
S
k
1
, т.к.
1
21
SS
pkpk
и
ожидающий писатель переходит в следующем такте в ранг работающих
писателей (открытый вход в критический участок писателей -
1
1
S
k
.
С 3-его такта начинается процедура обращения к РР (
1
S
m
) и
запрещается восприятие возможной повторной заявки на обращение к РР для
записи (
0
2
1
S
).
В 4-м и 5-м тактах выполняется запись в РР.
В 6-м такте подтверждается факт окончания записи в РР (
1
1
S
pk
)
и осуществляется выход первого писателя из своего критического участка
(
0
1
S
k
).
В 7-м такте зарождается событие
S
k
2
, т.к. 1
1
ЧО
SS
pk
и первый
ожидающий читатель (
S
1
2
) переходит в ранг работающих читателей, если
даже был бы в наличии второй ожидающий писатель (т.е. при
1
2
1
S
). 
      S1              S 12   S 12   S 12   S 12   S 12    S 12                        S 13    S 13                        S 14    S 14

      S2              S 32                                                                                                S 42    S 42

      S ЧО            0      0       0      0      0       0      0      0      0      1       1      1      1      1      1       1
S 1k ( S 2k )         S 2k   S 2k   S 2k   S 2k           S 1k   S 1k   S 1k   S 1k           S 1k   S 1k   S 1k   S 1k           S 2k

      Sm                     Sm                                  Sm                                  Sm

  1      2                            2                                   1                                   1
S p (S p)                           Sp                                  Sp                                  Sp
S 1n ( S 2n )                              S 2n                                S 1n                                S 1n
S 1pk ( S 2pk )                                   S 2pk                               S 1pk                               S 1pk

 Такты            17         18     19     20     21      22     23     24     25     26      27     28     29     30     31      32

         Рис.6.10. Временные диаграммы работы алгоритма управления
               взаимодействующими параллельными процессами
                   в задаче «читатели-писатели» (такты 17-32)
       Проследим работу управляющего алгоритма по временным
  диаграммам для некоторых частных случаев задания заявок на запись и
  чтение в процессе работы алгоритма по тактам:
          В 1-м такте фиксируются первые ожидающий писатель ( S 11  1 ) и
  ожидающий читатель ( S 12  1 ).
        П р и м е ч а н и е: верхним индексом у событий S 1 и S 2 будем определять
  порядковые номера писателей и читателей соответственно.
            Во 2-м такте зарождается событие S 1k , т.к. S 1pk  S 2pk  1 и
  ожидающий писатель переходит в следующем такте в ранг работающих
  писателей (открытый вход в критический участок писателей - S 1k  1 .
                С 3-его такта начинается процедура обращения к РР ( S m  1 ) и
  запрещается восприятие возможной повторной заявки на обращение к РР для
  записи ( S 12  0 ).
                В 4-м и 5-м тактах выполняется запись в РР.
               В 6-м такте подтверждается факт окончания записи в РР ( S1pk  1 )
  и осуществляется выход первого писателя из своего критического участка
  ( S 1k  0 ).
            В 7-м такте зарождается событие S 2k , т.к. S ЧО S1pk  1 и первый
                  
  ожидающий читатель ( S 12 ) переходит в ранг работающих читателей, если
  даже был бы в наличии второй ожидающий писатель (т.е. при S 12  1 ).

                                                                                                                                         186

Страницы