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

наличия ожидающих писателей и читателей (события S 1 и S 2 ) и от значений
событий, свидетельствующих о завершении процессов записи и чтения, т.е.
имеем:
                               1                              1       2
                              S пр  f 1 ( S 1, S 2 , S чо , S pk , S pk )
                                2                             1       2
                              S пр  f 2 ( S 1, S 2 , S чо , S pk , S pk ),
где S 1pk и S 2pk - события, свидетельствующие о факте окончания процедуры
                  записи и чтения соответственно, эти события фактически
                  повторяют события S 1n и S 2n , но со сдвигом на один такт.
         В связи с тем, что события S 1пр и S пр
                                              2
                                                 зависят от событий S 1 и S 2 , то
целесообразно рассматривать формализацию условий для зарождения
событий S 1k и S 2k , состоящих из двух событий ( S 1 S 1пр ) и соответственно
        2
( S 2 S пр ), как индивидуальных событий, обозначив их символами S 1k ,0 и S 2k ,0 .
Тогда уравнения (6.25) примут вид:
                     1             1      1      1 1
                    S k (t  1)  S k ,0 S вз  S k S n 
                                                                        (6.26)
                      2             2      2      2 2
                    Sk  (t  1)              
                                  S k ,o S вз S k S n . 
     Для получения уравнений, формализующих события S 1k ,0 и S 2k ,0 с
учетом пяти исходных событий (S 1 , S 2 , S чо , S1pk , S 2pk ) , воспользуемся
построенной прямой таблицей переходов (ПТП) для событий S 1k ,0 и S 2k ,0
(табл.6.2).
      При построении такой ПТП учитывались следующие обстоятельства:
         так как события S 1pk и S 2pk не могут существовать в один и тот же
момент времени, то для комбинации их значений S 1pk  S 2pk  1 значения
событий S 1k ,0 и S 2k ,0 будут неопределенными;
         так как события S 1k и S 2k по требованию алгоритма
взаимодействия процессов должны быть несовместимыми, то в каждой
строке ПТП значения для S 1k ,0 и S 2k ,0 имеют противоположные значения;
         с целью уменьшения размерности ПТП в ней опущены строки,
для которых S 1 = S 2 =0 и S 1pk = S 2pk =1.
     С учетом указанных замечаний и в соответствии со словесной
формулировкой алгоритма взаимодействия процессов ПТП для событий S 1k ,0
и S 2k ,0 будет иметь следующий вид (табл. 6.2).




                                                                                 180