Автоматное представление алгоритмов управления параллельными процессами в задаче «Писатели - читатели» на основе концепции недетерминизма и механизма монитора

№ 3 (35), 2015 Технические науки. Информатика, вычислительная техника

УДК 681.3.012

Н. П. Вашкевич, В. И. Волчихин, Р. А. Бикташев

АВТОМАТНОЕ ПРЕДСТАВЛЕНИЕ АЛГОРИТМОВ УПРАВЛЕНИЯ ПАРАЛЛЕЛЬНЫМИ ПРОЦЕССАМИ В ЗАДАЧЕ «ПИСАТЕЛИ - ЧИТАТЕЛИ» НА ОСНОВЕ КОНЦЕПЦИИ НЕДЕТЕРМИНИЗМА И МЕХАНИЗМА МОНИТОРА1

Аннотация.

Актуальность и цели. Объектом исследования являются системы управления процессами и ресурсами в параллельных системах обработки информации. Предметом исследования являются алгоритмы синхронизации параллельных процессов в задаче «писатели - читатели», основанные на механизме монитора. Цель работы - получение формальной модели алгоритма синхронизации с возможностью преобразования ее в модель функционального описания аппаратуры, например на языке VHDL, с дальнейшей реализацией на программируемых логических интегральных схемах.

Материалы и методы. Формализация алгоритма синхронизации параллельных процессов в задаче «писатели - читатели» выполнена с использованием метода, основанного на логике недетерминированных автоматов.

Результаты. Получено формальное описание алгоритма управления синхронизацией процессами в задаче «писатели - читатели» на основе использования механизма монитора в виде стандартной системы канонических рекуррентных уравнений, реализующих все частные события в управляющем алгоритме. Оно будет использовано для создания средств аппаратной поддержки ряда функций многопроцессорных операционных систем, к которым относятся каналы межпроцессного обмена, очереди сообщений и др., что обеспечит уменьшение латентности и повышение пропускной способности средств коммуникаций, а также их надежность и живучесть за счет тщательной отладки оборудования.

Выводы. Полученное формальное описание позволяет в дальнейшем просто решать задачи структурной реализации алгоритмов управления процессами и ресурсами и их верификации на моделях, представляющих основные характеристики свойств алгоритма, к числу которых обычно относятся безопасность и живость, справедливость, наличие взаимоисключения взаимодействующих процессов и др.

Ключевые слова: системы управления процессами и ресурсами, взаимодействие параллельных процессов, механизмы синхронизации процессов, событийные недетерминированные автоматы, частные события, формальное описание алгоритмов.

N. P. Vashkevich, V. I. Volchihin, R. A. Biktashev

AUTOMATA-BASED DEFINITION OF CONTROL ALGORITHMS FOR PARALLEL PROCESSES IN THE READERS-WRITERS PROBLEM BASED ON THE CONCEPT OF NON-DETERMINISM AND MONITOR MECHANISM

1 Работа выполнена в рамках Федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технического комплекса России на 2014-2020 годы» (Соглашение №14.574.21.0045 от19.06.14, UIN: RFMEFI57414X0045).

Engineering sciences. Computer science, computer engineering and control

65

Известия высших учебных заведений. Поволжский регион

Abstract.

Background. The object of the study is processes and resources of control systems for parallel processing. The research subject is synchronization algorithms of concurrent processes in the readers-writers problem, based on the monitor mechanism. The aim of the study is to obtain a formal model of a synchronization algorithm that can be converted into a model of functional description of equipment, for example, using the VHDL language, with further implementation on FPGAs.

Materials and methods. Formalization of an algorithm of synchronization of parallel processes in the readers-writers problem was performed using a method based on the logic of nondeterministic automatons.

Results. The authors obtained formal description of an algorithm of process synchronization control in the readers-writers problem on the basis of using the monitor mechanism as a standard canonical system of recurrent equations, realizing all private events in the control algorithm. The description will be used for development of means of hardware support of a number of functions of multiprocessor operating systems, which include channels of interprocess sharing, message queues, etc. It will reducte latency and increase bandwidth means of communication, as well as their reliability and survivability due to thorough equipment debugging.

Conclusions. The obtained formal description allows, subsequently, simply to solve problems of structural implementation of control algorithms for processes and resources and verification of models, representing the main characteristics of the algorithm’s properties, which typically include security and liveliness, justice, presence of mutual exclusions and other interacting processes.

Key words: control systems for processes and resources, interaction of parallel processes, process synchronization mechanisms, event non-deterministic machines, private event, formal description of an algorithm.

Введение

Формальным методам описания алгоритмов управления параллельными процессами в системах обработки информации придается большое значение, так как они могут обеспечить, как это отмечено в работе Хоара [1], комплексное решение задачи спецификации, разработки, реализации, верификации и анализа сложных систем управления, в том числе задач управления асинхронными процессами и ресурсами в вычислительных системах и сетях. Особенно важно применение формальных методов описания алгоритмов управления сложных систем реального времени для их верификации на моделях [2] и реализации в виде аппаратной поддержки операционных систем [3-5]. Такой подход к использованию формальных методов при создании компьютерных систем реального времени позволил бы повысить их надежность и производительность [5, 6].

Для решения задач управления взаимодействием параллельными процессами используют различные механизмы синхронизации, в том числе и механизм монитора [3], который впервые был предложен в 1974 г. в качестве высокоуровневого механизма организации синхронизации процессов при обращении к общим ресурсам Хоаром [7] и Бринген Хансеном [8]. Применение такого механизма синхронизации по сравнению с низкоуровневыми механизмами (семафоры, критические участки) позволяет повысить надежность и компактность систем управления [3, 9, 10].

Методика формального описания алгоритмов управления взаимодействующими процессами писателей и читателей основана на использовании

66

University proceedings. Volga region

№ 3 (35), 2015 Технические науки. Информатика, вычислительная техника

языка логики событийных недетерминированных автоматов (НДА), с помощью которого описываются все реализуемые в алгоритме частные события [11]. Под частными событиями здесь понимаются события, определяющие логические условия выполнения некоторых операций и события непосредственного выполнения этих операций.

1. Общие сведения об алгоритме взаимодействия процессами в задаче «писатели - читатели»

В данной задаче имеет место два класса процессов, которым требуется доступ к базе данных (БД) (общему ресурсу). Процессы первого класса (писатели) записывают данные, а второго класса (читатели) читают данные. Процессы «читатели» не меняют содержимого базы данных, а процессы «писатели» могут изменять данные. Для того чтобы выполнить операцию записи или чтения из базы данных, процесс должен войти в монитор. При этом в любой момент времени в мониторе может находиться только один писатель или один читатель [3, 9]. Будем рассматривать вариант синхронизации процессами, когда для процессов писателей и читателей имеется по две очереди: одна -основная, а другая - для процессов, ждущих повторного входа в монитор, вышедших из монитора необслуженными из-за неготовности базы данных к выполнению операции записи или чтения.

Для того чтобы не монополизировать доступ к БД читателей, когда их будет слишком много и они могли бы заблокировать запись, должен быть предусмотрен счетчик читателей (СчЧ), в который заносится константа Е. Занесение этой константы в СчЧ должно выполняться при пустом счетчике после окончания работы читателя [3, 9].

Читатель получает доступ к БД только в том случае, если в настоящий момент нет работающего писателя и нет ожидающего писателя. Первое условие должно обеспечиваться взаимоисключением событий, определяющих входы процессов писателей и читателей к БД. Второе условие предотвращает бесконечное откладывание реализации процессов писателей из-за наплыва читателей. После окончания работы читателя СчЧ уменьшается на единицу, и если он будет не пустой, то работа читателей может быть продолжена до тех пор, пока СчЧ не будет пустым.

Писатель получает доступ к БД только в том случае, если в настоящий момент времени нет работающего читателя и СчЧ пуст или когда независимо от состояния СчЧ нет как ожидающего, так и работающего читателя. Когда писатель заканчивает работу, предпочтение отдается ожидающим читателям, а не ожидающим писателям, что предотвращает бесконечное откладывание процессов читателей из-за наплыва писателей.

2. Основные свойства и требования к монитору

Монитор, по определению в [10], - это программный модуль, который содержит переменные, определяющие состояние ресурсов и процедуры, реализующие операции над ними.

Чтобы выполнить формальное описание всех основных событий алгоритма управления в решаемой задаче взаимодействия процессов при обращении к БД (общему ресурсу), сформулируем основные свойства монитора и требования к нему, обеспечивающие реализацию следующих главных двух

Engineering sciences. Computer science, computer engineering and control

67

Известия высших учебных заведений. Поволжский регион

свойств системы управления процессами: бесконфликтность взаимодействия процессов и «справедливость» при обслуживании процессов двух разных классов.

Монитор должен обладать следующими тремя свойствами [9]:

1. Чтобы изменить состояние общего ресурса, процесс должен войти в монитор. При этом вне монитора известны только имена процедур, которые могут изменить состояние ресурса, и неизвестно состояние общего ресурса (постоянные переменные, характеризующие состояние ресурса).

2. Внутри монитора процесс не может обращаться к переменным, объявленным вне монитора.

3. Постоянные переменные, характеризующие состояние ресурса, инициируются до вызова его процедур.

Учитывая эти свойства, можно сформулировать основные требования к механизму монитора, обеспечивающие реализацию двух главных свойств системы управления процессами, отмеченные выше.

Эти требования в принципе идентичны трем требованиям к критическим интервалам при организации доступа к разделяемому ресурсу, которые были определены Деккером и Дейкстра [3, 12], а для механизма монитора добавляется еще одно - четвертое - требование. В результате такие требования к монитору можно сформулировать следующим образом:

1. В любой момент времени только один процесс может находиться внутри монитора.

2. Ни один процесс не может бесконечно долго оставаться внутри монитора.

3. Ни один процесс не должен бесконечно ждать входа в монитор.

4. Процесс, вышедший из монитора необслуженным, имеет преимущественное право на повторный вход в монитор по сравнению с процессами, находящимися в начальной очереди и требующими выполнить такую же процедуру над общим ресурсом.

3. Формализация основных событий, определяющих алгоритм управления взаимодействующими процессами в решаемой задаче

Анализируя указанные свойства и требования к монитору, можно определить как состав необходимых событий, реализующих эти требования, так и условия их зарождения и сохранения. Для аналитического описания таких событий будем базироваться на работах авторов, в том числе [11], в которых была представлена обобщенная каноническая форма описания любого частного события алгоритма логического управления на основе использования моделей НДА. Такое описание состоит из двух частей: первая обеспечивает условия зарождения частного события, а вторая - условия его сохранения.

В рассматриваемой задаче главными событиями алгоритма управления процессами «писатели - читатели» при использовании механизма мониторов

являются события sM и SM , определяющие вход процессов писателей и читателей в монитор соответственно. Общий вид описания таких событий имеет вид

SM(^ + 1) - ^МЗ^ВП v sмх ,

68

University proceedings. Volga region

№ 3 (35), 2015 Технические науки. Информатика, вычислительная техника

SM(t + !) - SM3SBП v SMSMX,

где Sm3 и Sj3 - комбинационные события, определяющие условие зарождения событий SlM и Sm соответственно; Smx и Smx - комбинационные события, определяющие условия сохранения событий Sm и Sm соответственно; sBп и S;g п - события, определяющие прием заявок процессов писателей и читателей на запись и чтение из БД соответственно. Эти события являются событиями непосредственно предшествующими событиям Sm и Sm .

В соответствии с первым требованием к мониторам события Sj3 и

2

SM3, определяющие зарождение событий входа процессов в монитор, формулируются так:

SM3(t+1)=SB

S

ВЗ°ПР>

SMЗ (t +1) - SВ З Snp,

где SB3 и Sb з - комбинационные события, обеспечивающие функции взаимоисключения процессов писателей и читателей соответственно, так как в монитор может войти и находиться в нем только один процесс, то эти события представляются таким образом:

SB3 - SM v SMn,

SB З - SM v SMn,

где Sjn и Sjn - события, обеспечивающие повторный вход в монитор

процессов писателей и читателей соответственно; Snp и Sj^p - комбинационные события, определяющие приоритеты процессов писателей и читателей соответственно. Структура этих событий определится в дальнейшем при рассмотрении других вспомогательных частных событий, от значений которых они зависят.

В соответствии со вторым требованием к мониторам события типа Smx и Smx , определяющие сохранение событий входа процессов в монитор, будут иметь следующий вид:

о1 о1 о1 о2 о2 о2

SMX - SnSMC, SMX - SnSМС,

где Sn1 и Sn2 - события, свидетельствующие об окончании операций в БД

процессов «писатели» и «читатели» соответственно; Sjc и Smc - события, свидетельствующие о том, что процесс «писатель» и процесс «читатель» соответственно вышли из монитора необслуженными и сняты до повторного входа в монитор. Эти события можно представить таким образом:

SMC (t + 1) - SM ^БД v SMC SMn, SMC (t +1) - sm ^д v SMC SMn, где sБд и S^д - события, свидетельствующие о том, что писать и читать из

БД разрешается соответственно.

Engineering sciences. Computer science, computer engineering and control

69

Известия высших учебных заведений. Поволжский регион

События «Sgn и iSgn, определяющие прием заявок процессов писателей и читателей на запись и чтение из БД, должны быть формализованы таким образом, чтобы удовлетворялось третье требование к мониторам. Для этого необходимо, чтобы заявка процессов писателей и читателей на обслуживание воспринималась и сохранялась воспринятой лишь в том случае, когда данные процессы не находятся в мониторе. Тогда эти события определятся таким образом:

°ВП

о 2

S ВП

(t + 3) -(°З v оВП

SM v SМП

где S3 и S3 - события, свидетельствующие о поступлении заявок процессов писателей и читателей на обращение к БД.

События Омп и Омп , определяющие повторный вход процессов в монитор, в соответствии с четвертым требованием к монитору должны учитывать как наличие ждущих процессов, вышедших из монитора необслуженными, так и наличие событий, определяющих разрешение писать и читать из БД, а также взаимоисключение процессов. В соответствии с этим описание таких событий будет иметь вид

ОМП (t + 3) — SMC °ВЗ ОБД v ОМП Sli, ОМП (t + 3) — SMC ОВЗ °БД v ОМП Sl.

Для формального описания функций приоритетов процессов писателей и читателей необходимо иметь в виду, что их приоритет при обращении к БД зависит от значений многих условий, в том числе: от состояния счетчика чи-

1 2

тателей (СчЧ); от наличия ждущих писателей (ОДп) и читателей (ОДп), поступающих из начальной очереди; от выполняемой операции в БД в предшествующий момент времени (была запись - событие S^n — 1 или чтение событие Snn — 1). Кроме того, необходимо иметь в виду, что в соответствии с четвертым требованием к монитору ждущие процессы, которые вышли из монитора необслуженными (SMC и SMC), имеют более высокий приоритет по сравнению с процессами, находящимися в начальной очереди. Поэтому события, определяющие приоритет процессов, поступающих из начальной очереди, можно представить так:

°пр—°Пр (0 )SMc, °пр—°пр (0 )SMc,

12

где Snp(0) и Snp (0) - условная сокращенная запись событий, определяющих приоритет процессов «писатели» и «читатели» без учета зависимости их от событий Smc и Smc соответственно.

70

University proceedings. Volga region

№ 3 (35), 2015 Технические науки. Информатика, вычислительная техника

Для получения уравнений, формализующих комбинационные события ^ПР (0) и Snp(0) с учетом значений пяти исходных событий (^Ви , П ,

SGH, S^n , S%n), можно воспользоваться таблицей определения истинности 1 2

булевых функций Snp (0) и Snp (0) (табл. 1). При построении этой таблицы учитывались следующие обстоятельства:

а) так как события типа S]in и S^j не могут существовать в один и тот

же момент времени, то для их значений Sjn = sJj = 1 значения событий 12

Snp (0) и Snp (0) будут неопределенными;

б) с целью уменьшения размерности таблицы в ней опущены строки,

для которых бПп = S2n = 1 и SВп = SВп = 0, в последнем случае события 12

Snp(0) и Snp(0) равны нулю.

Таблица 1

Таблица для определения событий Snp

№ S^^ Sm S 2 ЙВП S1 unn S 2 unn Snp

1 0 0 1 0 0 0 1

2 0 0 1 0 1 0 1

3 0 0 1 1 0 0 1

4 0 1 0 0 0 1 0

5 0 1 0 0 1 1 0

6 0 1 0 1 0 1 0

7 0 1 1 0 0 1 0

8 0 1 1 0 1 1 0

9 0 1 1 1 0 1 0

10 1 0 1 0 0 0 1

11 1 0 1 0 1 0 1

12 1 0 1 1 0 0 1

13 1 1 0 0 0 1 0

14 1 1 0 0 1 1 0

15 1 1 0 1 0 1 0

16 1 1 1 0 0 1 0

17 1 1 1 0 1 0 1

18 1 1 1 1 0 0 1

Комментарии для заполнения табл. 1.

1. Для строк 1-3:

СчЧ пустой, есть ожидающий читатель (SВи = 1) и нет ожидающего писателя (sВп = 0), поэтому Snp(0) = 0, S2Пр(0) = 1. Перед операцией чтения должна быть выполнена загрузка СчЧ.

2. Для строк 4-6:

СчЧ пустой, есть ожидающий писатель (sВп = 1) и нет ожидающего читателя (SВП = 0), поэтому Snp(0)= 1, S2IP(0)= 0 .

Engineering sciences. Computer science, computer engineering and control

71

Известия высших учебных заведений. Поволжский регион

3. Для строк 7-9:

СчЧ пустой, есть ожидающий писатель (^ВП = 1) и ожидающий читатель

(S Вп = 1), поэтому 5др (0 )= 1 (монопольный режим писателя), ^др (0) = 0.

4. Для строк 10-12:

СчЧ не пустой, есть ожидающий читатель (SВп = 1) и нет ожидающего писателя (sBn = 0), поэтому SnP(0)=0, SПр(0)=1.

5. Для строк 13-15:

СчЧ не пустой, есть ожидающий писатель (SBn = 1) и нет ожидающего читателя (SBn = 0), поэтомуSnP(0)= 1, SДР(0) = 0 .

6. Для строк 16-18:

СчЧ не пустой, есть ожидающий писатель (SBn = 1) и ожидающий читатель (S Bn = 1). Для этого варианта приоритет писателей и читателей будет зависеть от характера операции над БД, которая выполнялась в предшествующий момент времени. В этом случае будут иметь место три варианта:

1. Если в предшествующий момент времени не было ни записи

(пп = 0), ни чтения = 0), то S^(0)= 1, SnP(0)= 0, т.е. будет запись.

2. Если в предшествующий момент времени было чтение (Пп = 1), а не запись (Пп = 0), то чтение продолжается, т.е. s}jp(0)=0, Snp(0) = 1.

3. Если в предшествующий момент времени была запись (Пп = 1), а не

чтение ((п = 0), то будет чтение Snp(0)= 1, т.е. запись запрещается

Snp(0)=0 , так как не допускается бесконечная запись.

На основании построенной таблицы определения истинности событий Snp(0) и SПр(0) несложно получить для них минимальные выражения,

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

Snp(0)= SBп( Sсч v SВп v Sim 'S

sПр(0)=sВп sСч(sп

После определения всех частных событий, связанных с организацией входа процессов в монитор, можно формально представить события, непосредственно реализующие операции записи или чтения в БД. Эти события определятся так:

Sрз(t + 1) = Sm ( v SMn) v SрзSк

Sрч(t + 1) = Sm (SM v SМП) v SрчSк

72

University proceedings. Volga region

№ 3 (35), 2015 Технические науки. Информатика, вычислительная техника

где S р3 и S рЧ - события, непосредственно реализующие операции записи и чтения в БД соответственно; S кз и S кч - события, определяющие продолжительность выполнения операции записи и чтения в БД соответственно; Sm -событие, определяющее начало операции как записи, так и чтения в БД:

S,

.(' + !) = (

MSБД V S

1

МП

V

2 о2

MS

БД

V S Мп

Окончание процедур записи и чтения в БД определят события s\ и S; а также события Sm и Sm :

Sn S + 1) = SрзSкз, s'2 {t + 1) = Sрч Sкч;

Srn (t + 1) = ts1 V Sm)^ПР, SПп (t + 1) = tSn V SПп) SПp •

n

Используя описания всех частных событий, реализуемых в управляющем алгоритме синхронизации параллельных процессов в решаемой задаче, можно для наглядного представления изобразить его в виде графа НДА (рис. 1).

Рис. 1. Граф НДА алгоритма управления синхронизацией процессов в задаче «писатели - читатели»

На рис. 1 представлен граф НДА только для одной ветви - процесса «писатель», так как для процесса «читатель» он будет идентичен. Кроме того,

на рис. 1 добавлено еще одно вспомогательное событие S^, символизирующее ожидание процессом, пославшим заявку на обращение к БД, окончания процедуры записи, чтобы продолжить свою работу.

Заключение

Полученное формальное описание алгоритма управления процессами в задаче «писатели - читатели» на основе использования механизма монитора в виде стандартной системы канонических рекуррентных уравнений, реали-

Engineering sciences. Computer science, computer engineering and control

73

Известия высших учебных заведений. Поволжский регион

зующих все частные события в управляющем алгоритме, позволяет в дальнейшем просто решать задачи структурной реализации такого алгоритма и его верификации [6]. Для этой цели описание такого алгоритма просто трансформируется в код языка программирования, например, в описание на языке VHDL для аппаратной реализации алгоритма на основе ПЛИС [13], а также позволяет выполнить его верификацию на моделях, представляющих основные характеристики свойств алгоритма. К числу таких свойств обычно относятся: свойство безопасности и живости, свойства справедливости, наличие взаимоисключения взаимодействующих процессов и др.

Метод формализации, основанный на недетерминированных автоматах, а также формальное описание алгоритма управления процессами в задаче «писатели - читатели» могут быть использованы для аппаратной реализации ряда коммуникационных функций многопроцессорных операционных систем, к которым относятся каналы межпроцессного обмена, очереди сообщений и т.п. Такая реализация позволит значительно уменьшить латентность и повысить пропускную способность обменных операций между процессами, выполняющимися на разных процессорах.

Список литературы

1. Хоар, Ч. Взаимодействующие последовательные процессы : пер. с англ. /

Ч. Хоар. - М. : Мир, 1989. - 264 с.

2. Кларк, Э. М. Верификация моделей программ: Model Checking : пер. с англ. /

Э. М. Кларк, О. Граммберг, Д. Пелед. - М. : МЦНМО, 2002. - 416 с.

3. Дейтел, Х. М. Операционные системы. Основы и принципы : в 2 т. : пер. с англ. / Х. М. Дейтел, П. Дж. Дейтел, Д. Р. Чофнес. - М. : Бином-Пресс, 2011. -Т. 1. - 1024 с.

4. Akgul, B. E. S. System-on-a-chip processor synchronization support in hardware /

B. E. S. Akgul and V. J. Mooney // Design Automation and Test in Europe (DATE’01). -2001, March. - P. 633-639.

5. Бикташев, Р. А. Разработка аппаратно-ориентированного ядра многопроцессорных операционных систем реального времени / Р. А. Бикташев, Н. П. Вашкевич // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации. - Курск, 2015. -

C. 42-44.

6. Вашкевич, Н. П. Достоинство формального языка, основанного на концепции недетерминизма, при структурной реализации параллельных систем логического управления процессами и ресурсами / Н. П. Вашкевич, Р. А. Бикташев // Известия высших учебных заведений. Поволжский регион. Технические науки. - 2011. -№ 1 (7). - С. 3-11.

7. Ho are, C. A. R. Monitors, An Operating System Structuring Concept /

C. A. R. Hoare // Commun. Of the ACM. - 1974, oct. - Vol. 17. - P. 549-557.

8. Brinch Hansen, P. The Programming Language Concurrent Pascal / P. Brinch Hansen // IEEE Trans. On Software Engineering. - 1975, june. - Vol. SE-1. - P. 199207.

9. Эндрюс, Г. Р. Основы многопоточного параллельного и распределенного программирования : пер. с англ. / Г. Р. Эндрюс. - М. : Вильямс, 2003. - 512 с.

10. Таненбаум, Э. Современные операционные системы / Э. Таненбаум. - 4-е изд. -СПб. : Питер, 2015. - 1120 с.

11. Вашкевич, Н. П. Недетерминированные автоматы в проектировании систем параллельной обработки : учеб. пособие / Н. П. Вашкевич. - Пенза : Изд-во ПензГУ, 2004. - 280 с.

74

University proceedings. Volga region

№ 3 (35), 2015 Технические науки. Информатика, вычислительная техника

12. Кейлингерт, П. Элементы операционных систем : пер. с англ. / П. Кейлин-герт. - М. : Мир, 1985. - 296 с.

13. Вашкевич, Н. П. Аппаратная реализация функций синхронизации параллельных процессов при обращении к разделяемому ресурсу на основе ПЛИС / Н. П. Вашкевич, Р. А. Бикташев, Е. И. Гурин // Известия высших учебных заведений. Поволжский регион. Сер. Технические науки. - 2007. - № 2. - С. 3-12.

References

1. Khoar Ch. Vzaimodeystvuyushchie posledovatel'nye protsessy: per. s angl. [Communicating sequential processes: translation from English]. Moscow: Mir, 1989, 264 p.

2. Klark E. M., Grammberg O., Peled D. Verifikatsiya modeley programm: Model Checking: per. s angl. [Verification of program models: Model checking: translation from English]. Moscow: MTsNMO, 2002, 416 p.

3. Deytel Kh. M., Deytel P. Dzh., Chofnes D. R. Operatsionnye sistemy. Osnovy i printsipy: v 2 t.: per. s angl. [Operating systems. Basics and concepts: in 2 volumes: translation from English]. Moscow: Binom-Press, 2011, vol. 1, 1024 p.

4. Akgul B. E. S. and Mooney V. J. Design Automation and Test in Europe (DATE’01). 2001, March, pp. 633-639.

5. Biktashev R. A., Vashkevich N. P. Optiko-elektronnye pribory i ustroystva v sistemakh raspoznavaniya obrazov, obrabotki izobrazheniy i simvol'noy informatsii [Optoelectronic devices in systems of pattern recognition, image processing and symbolic information]. Kursk, 2015, pp. 42-44.

6. Vashkevich N. P., Biktashev R. A. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Tekhnicheskie nauki [University proceedings. Volga region. Engineering sciences]. 2011, no. 1 (7), pp. 3-11.

7. Hoare C. A. R. Commun. Of the ACM. 1974, Oct., vol. 17, pp. 549-557.

8. Brinch Hansen P. IEEE Trans. On Software Engineering. 1975, June, vol. SE-1, pp. 199-207.

9. Endryus G. R. Osnovy mnogopotochnogo parallel'nogo i raspredelennogo programmi-rovaniya: per. s angl. [Foundations of multithreaded, parallel and distributed programming: translation from English]. Moscow: Vil'yams, 2003, 512 p.

10. Tanenbaum E. Sovremennye operatsionnye sistemy [Modern operational systems]. 4th ed. Saint-Petersburg: Piter, 2015, 1120 p.

11. Vashkevich N. P. Nedeterminirovannye avtomaty v proektirovanii sistem parallel'noy obrabotki: ucheb. posobie [Non-deterministic automatons in parallel processing system design: tutorial]. Penza: Izd-vo PenzGU, 2004, 280 p.

12. Keylingert P. Elementy operatsionnykh sistem: per. s angl. [Operating system elements: translation from English]. Moscow: Mir, 1985, 296 p.

13. Vashkevich N. P., Biktashev R. A., Gurin E. I. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Ser. Tekhnicheskie nauki [University proceedings. Volga region. Engineering sciences]. 2007, no. 2, pp. 3-12.

Вашкевич Николай Петрович

доктор технических наук, профессор, кафедра вычислительной техники, Пензенский государственный университет

E-mail: vt@alice.pnzgu.ru

Vashkevich Nikolay Petrovich Doctor of engineering sciences, professor, sub-department of computer engineering, Penza State University

Engineering sciences. Computer science, computer engineering and control

75

Известия высших учебных заведений. Поволжский регион

Волчихин Владимир Иванович доктор технических наук, профессор, президент Пензенского государственного университета

E-mail: cnit@pnzgu.ru

Бикташев Равиль Айнулович

кандидат технических наук, профессор, кафедра вычислительных машин и систем, Пензенский государственный технологический университет

E-mail: bra559620@sura.ru

Volchikhin Vladimir Ivanovich Doctor of engineering sciences, professor, President of Penza State University

Biktashev Ravil' Aynulovich Candidate of engineering sciences, professor, sub-department of computing machines and systems, Penza State Technological University

УДК 681.3.012 Вашкевич, Н. П.

Автоматное представление алгоритмов управления параллельными процессами в задаче «писатели - читатели» на основе концепции недетерминизма и механизма монитора / Н. П. Вашкевич, В. И. Волчихин, Р. А. Бикташев // Известия высших учебных заведений. Поволжский регион. Технические науки. - 2015. - № 3 (35). - С. 65-76.

76

University proceedings. Volga region