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

    S 1,З и S 2,З - сокращенные обозначения событий, определяющих заявку
           на запись и чтение из буфера соответственно;
    S1 и S 2 - сокращенные обозначения событий, определяющих прием
             заявок на запись и чтение соответственно;
     S r1 и S r2 - сокращенные обозначения событий, символизирующих
             ожидание процессами производителя и потребителя окончания
             операции записи и чтения из буфера соответственно.
      Рассмотрим теперь вариант формализации алгоритма управления
параллельными процессами в задаче «производители-потребители», когда
процессы взаимодействуют через согласующий буфер на число слов N1.
Для этого алгоритма должно быть обеспечено:
           взаимоисключение процессов при обращении к критическому
ресурсу – согласующему буферу;
           предотвращение чтения из пустого буфера и записи в полный
буфер.
      Для определения состояния буфера используется счетчик буфера
(СчБ), в который перед операциями записи (чтения) в буфер заносится
константа N, определяющая максимальное число слов, записываемых в
буфер. При t=0/ СчБ:=N.
      Во время операций записи (чтения) в буфер в СчБ выполняются
следующие операции:
           при каждой записи одного слова из СчБ вычитается единица
(СчБ:=СчБ-1), поэтому при СчБ=0 буфер будет полон, а его состояние будем
характеризовать событием S БП (при S БП  1 буфер полон);
          при каждом чтении из буфера одного слова в СчБ посылается
единица (СчБ:=СчБ+1), поэтому при СчБ=N буфер будет пуст, а его
состояние будем характеризовать событием S БО (при S БО  1 буфер пуст).
      Введение двух событий S БП и S БО позволяет охарактеризовать
промежуточное состояние буфера, когда он может быть и не пустым и не
полным ( S БП = S БО =0). Это может иметь место, когда при очередной записи
буфер был заполнен не полностью, т.е. число слов в буфере после очередной
записи будет меньше N.
      Учитывая рассмотренные выше требования к алгоритму управления
межпроцессного взаимодействия для двух параллельных процессов через
согласующий буфер с числом слов N1, а также методику формализации
функции взаимоисключения критических участков (раздел 6.3), граф НДА,
представляющий этот алгоритм (рис.6.6) будет иметь в основном такую же
структуру, что и граф НДА (рис.6.5), представляющий алгоритм управления
процессами для варианта, когда согласующий буфер имеет объем в одно
слово.


                                                                        171