БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

НАУЧНО-ПРАКТИЧЕСКИЕ КОНФЕРЕНЦИИ

<< ГЛАВНАЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     || 2 | 3 | 4 | 5 |   ...   | 24 |

«НОВЫЕ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ И СИСТЕМЫ ТРУДЫ IX Международной научно-технической конференции Часть 1 Proceedings of the Ninth International Conference of Science and Technology ...»

-- [ Страница 1 ] --

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ГОСУДАРСТВЕННЫЙ НАУЧНО-ИССЛЕДОВАТЕЛЬСКИЙ ИНСТИТУТ

ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И ТЕЛЕКОММУНИКАЦИЙ

МЕЖДУНАРОДНАЯ АКАДЕМИЯ ИНФОРМАТИЗАЦИИ

АКАДЕМИЯ ИНФОРМАТИЗАЦИИ ОБРАЗОВАНИЯ

ФОНД СОДЕЙСТВИЯ РАЗВИТИЮ МАЛЫХ ФОРМ ПРЕДПРИЯТИЙ

В НАУЧНО-ТЕХНИЧЕСКОЙ СФЕРЕ

НАУЧНО-ТЕХНИЧЕСКОЕ ПРЕДПРИЯТИЕ «КРИПТОСОФТ»

ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

НОВЫЕ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ И СИСТЕМЫ ТРУДЫ IX Международной научно-технической конференции Часть 1 Proceedings of the Ninth International Conference of Science and Technology

NEW INFORMATION TECHNOLOGIES

AND SYSTEMS

Penza, Russia, November 9–10, Volume Пенза Издательство ПГУ УДК 004. Н Новые информационные технологии и системы : труды Н72 IX Международной научно-технической конференции (г. Пенза, 9–10 ноября 2010 г.) : в 2 ч. – Пенза : Изд-во ПГУ, 2010. – Ч. 1. – 264 с.

Представлены материалы докладов, сделанных на IX Международной научнотехнической конференции «Новые информационные технологии и системы»

(«НИТиС-2010»), проводимой Международной академией информатизации, Академией информатизации образования, научно-техническим предприятием «Криптософт» и Пензенским государственным университетом.

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

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

УДК 004. Редакционная коллегия:

В. И. Волчихин, Н. П. Вашкевич, В. Ю. Егоров, М. М. Бутаев, П. П. Макарычев, Х.-М. Ханиш © ГОУ ВПО «Пензенский государственный университет», «НИТиС-2010»

ОПЕРАЦИОННЫЕ СИСТЕМЫ И СИСТЕМНОЕ ПРОГРАММНОЕ

ОБЕСПЕЧЕНИЕ

Н.П. Вашкевич, Р.А. Бикташев Россия, Пенза, Пензенский государственный университет

ФОРМАЛИЗАЦИЯ АЛГОРИТМОВ УПРАВЛЕНИЯ

СИНХРОНИЗАЦИЕЙ ПАРАЛЛЕЛЬНЫМИ ПРОЦЕССАМИ

В ЗАДАЧЕ «ПИСАТЕЛИ-ЧИТАТЕЛИ» НА ОСНОВЕ

КОНЦЕПЦИИ НЕДЕТЕРМИНИЗМА И МЕХАНИЗМА

МОНИТОРА

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

Введение Формальным методом описания алгоритмов управления параллельными процессами в системах обработки информации придаётся большое значение, т.к. они могут обеспечить, как это отмечено в работе Хоара [1], комплексное решение задачи:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

IX Международная научно-техническая конференция 3) Постоянные переменные, характеризующие состояние ресурса, инициируются до вызова его процедур.

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

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

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

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

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

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

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

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

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

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

Общий вид описания таких событий имеет вид:

М М ВП ММ

где S МЗ и S МЗ – комбинационные события, определяющие условие зарождения событий S М и S М соответственно;

S 1 и S 2 – комбинационные события, определяющие условия сохранения событий S М и S М соответственно;

S1 и S 2 – события, определяющие приём заявок процессов писателей и читателей на запись и чтение из БД соответственно.

Эти события являются событиями непосредственно предшествующими событиям S М и S М.

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

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

где S MП и S MП – события, обеспечивающие повторный вход в IX Международная научно-техническая конференция монитор процессов писателей и читателей соответственно;

S 1 и S 2 – комбинационные события, определяющие приоритеты процессов писателей и читателей соответственно. Структура этих событий определится в дальнейшем при рассмотрении других вспомогательных частных событий от значений которых они зависят.

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

где S1 и S 2 – события, свидетельствующие об окончании операций в БД процессами писатели и читатели соответственно;

S1 C и S 2 C – события, свидетельствующие о том, что процесс «писатель» и процесс «читатель» соответственно вышли из монитора не обслуженными и «спят» до повторного входа в монитор.

Эти события можно представить таким образом:

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

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

ВП ВП М МП

ВП ВП М МП

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

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

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

от наличия ждущих писателей ( S ВП ) и читателей ( S ВП ), поступающих из начальной очереди;

от выполняемой операции в БД в предшествующий момент времени (была запись – событие Snn=1 или чтение - событие Snn=1). Кроме того необходимо иметь ввиду, что в соответствии с четвёртым требованием к монитору, ждущие процессы, которые вышли из монитора не обслуженными ( S М C и S М C ), имеют более высокий приоритет по сравнению с процессами, находящимися в начальной очереди. Поэтому события, определяющие приоритет процессов, поступающих из начальной очереди, можно представить так:

IX Международная научно-техническая конференция где S1 ( 0 ) и S 2 ( 0 ) – условная сокращённая запись событий, определяющих приоритет процессов «писатели» и «читатели» без учёта зависимости их от событий S1 C и S 2 C соответственно.

Для получения уравнений, формализующих комбинационные события S ПР ( 0 ) и S ПР ( 0 ) с учётом значений пяти исходных событий ( S ВП, S ВП, S сч, S nn, S nn ) можно воспользоваться таблицей определения истинности булевых функций S ПР ( 0 ) и S ПР ( 0 ). При построении этой таблицы учитывались следующие обстоятельства:

а) Так как события типа S nn и S nn не могут существовать в один и тот же момент времени, то для их значений S nn = S nn = значения событий S ПР ( 0 ) и S ПР ( 0 ) будут неопределёнными.

б) С целью уменьшения размерности таблицы в ней опущены строки, для которых S nn = S nn = 1 и S ВП = S ВП = 0, в последнем случае события S ПР ( 0 ) и S ПР ( 0 ) равны нулю.

Таблица 1. Таблица для определения событий S1 ( 0 ) и S 2 ( 0 )

ВП ВП ПР ПР

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

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

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

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

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

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

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

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

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

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

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

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

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

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

б) Если в предшествующий момент времени было чтение в) Если в предшествующий момент времени была запись запрещается S ПР ( 0 ) = 0, т.к. не допускается бесконечная запись.



Pages:     || 2 | 3 | 4 | 5 |   ...   | 24 |
 


Похожие материалы:

«ИНФОРМАТИКА, МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ, ЭКОНОМИКА Том 1 Сборник научных статей по итогам Международной научно-практической конференции г. Смоленск, 22 апреля 2011 г. Смоленск 2011 УДК 32.81+65.050+65 ББК 004+330.4+330 И 74 Организационный комитет конференции: председатель – д.т.н. профессор Усков А. А.; заместитель председателя – д.т.н. профессор Михаль О. Ф.; члены оргкомитета: д.с.-х.н. профессор Бедило Н. М., д.э.н. профессор Белокопытов А. В., д.т.н. профессор Вашкевич С. А., д.э.н. ...»

«8-9 июля 2003 года, Новосибирск, Академгородок, Россия Рабочее совещание Интервальная математика и методы распространения ограничений Доклады и тезисы Настоящий сборник трудов составлен из кратких аннотаций и полных текстов докладов, представленных на международное рабочее совещание Интервальная математика и методы распространения ограничений (ИМРО'03) проходившее в Новосибирском Академгородке 8–9 июля 2003 года под крышей Новосибирского Центра Информационных Технологий УниПро. Совещание ...»

«Международная научно-практическая конференция Ценности и интересы современного общества Материалы конференции (Часть 2) Москва, 2013 УДК 316.3 C 232 Материалы конференции. Международная научно- С 232 практическая конференция Ценности и интересы современно- го общества. Часть 2 // Московский государственный универ- ситет экономики, статистики и информатики – М., 2013. – 322 c. ISBN 978-5-7764-0817-5 В сборнике научных трудов конференции представлены доклады ученых государственных ...»

«За достоверность сведений, изложенных в статьях, ответственность несут авторы. Мнение редакции может не совпадать с мнением авторов материалов. При перепечатке ссылка на сборник обязательна. Материалы публикуются в авторской редакции. ~1~






 

© 2013 www.kon.libed.ru - «Бесплатная библиотека научно-практических конференций»