научная статья по теме СЕМАНТИЧЕСКИЕ ОБЛАСТИ ВРЕМЕННЫХ СТРУКТУР СОБЫТИЙ Математика

Текст научной статьи на тему «СЕМАНТИЧЕСКИЕ ОБЛАСТИ ВРЕМЕННЫХ СТРУКТУР СОБЫТИЙ»

ТЕОРЕТИЧЕСКИЕ ВОПРОСЫ ПРОГРАММИРОВАНИЯ ~

УДК 21.22

СЕМАНТИЧЕСКИЕ ОБЛАСТИ ВРЕМЕННЫХ СТРУКТУР СОБЫТИЙ*

© 2008 г. И. Б. Вирбицкайте1'2, Р. С. Дубцов1

1 Институт систем информатики им. А.П. Ершова СО РАН 630090 Новосибирск, просп. Академика Лаврентьева, 6 2Новосибирский государственный университет 630090 Новосибирск, ул. Нирогова, 2 E-mail: virb@iis.nsk.su, dubtsov@iis.nsk.su Поступила в редакцию 11.07.2007 г.

В работе вводятся и исследуются временные расширения различных классов структур событий и помеченные области Скотта, а также строятся категории данных моделей и изучаются их свойства. Кроме того, на основе теоретико-категорных методов устанавливаются взаимосвязи между временными структурами и помеченными областями Скотта.

1. ВВЕДЕНИЕ

К настоящему времени в теории параллельных систем и процессов известно большое многообразие абстрактных семантических моделей: сети-процессы, трассы Хоара, трассы Мазурке-вича, частично упорядоченные множества, причинные деревья, структуры событий и т.д. С помощью этих моделей исследуется поведение параллельных/распределенных систем, определяются различные семантические представления параллельных процессов, устанавливаются взаимосвязи между существующими подходами к изучению семантики параллельных программ. Такое многообразие моделей требует их систематизации и унификации. Изучением глубоких взаимосвязей между различными семантическими моделями занимается специальный раздел теории параллелизма - компаративная семантика (comparative semantics).

Одной из центральных моделей параллельных недетерминированных процессов являются структуры событий, которые впервые были введены и исследованы в диссертационной работе Винскеля [1]. Основное достоинство этих моделей состоит в том, что в них явным образом задаются базовые отношения - причинной зависи-

"Данная работа частично финансировалась РФФИ (грант №07-01-00543).

мости, параллелизма и недетерминированного выбора (конфликта) - между событиями параллельных систем. Структуры событий используются для установления взаимосвязей между различными моделями параллельных процессов [1-3] и определения денотационной и операционной семантик формальных и программных языков параллельных процессов [1, 4-7]. В литературе известны различные классы моделей структур событий: первичные [1], общие [1], стабильные [4], потоковые [5], свободные [6], расслоенные [7], с приоритетами [8], автоматные [9], локальные [10], с разрешаемым конфликтом [11] и т.д. Сравнительный анализ некоторых классов структур событий можно найти в работах [12-14].

Последнее десятилетие методы теории категорий [15] стали активно применяться в компаративной семантике. Основная идея данного подхода заключается в следующем. Объекты категорий представляют процессы, а морфизмы соответствуют взаимосвязям между поведениями процессов (т.е. показывают, как один процесс моделирует другой). Одна модель считается более выразительной, чем другая, в терминах вложений (или прообразов). В работах [16, 17] на основе теоретико-категорных методов были исследованы взаимосвязи между различными параллельными моделями: деревьями синхронизации, структурами событий,система-

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

Известно, что денотационная семантика и теория областей Скотта активно используются как математический базис для описания семантики последовательных программ, установления взаимосвязей между языками программирования, исследования типов данных языков программирования. Применение таких абстрактных методов к моделям параллельных систем и процессов всегда вызывало некоторую долю скептицизма (например, см. [18]). Однако в работе [1] было показано, что с помощью теоретико-категорных методов можно установить классы областей Скотта, которые соответствуют семантике структур событий, а через построение сопряжений - и семантике сетей Петри (другими словами, определить семантические области моделей). Кроме того, в статье [19] с использованием теоретико-категорных методов была проведена унификация таких семантических моделей, как сети-процессы, "развертка" (unfolding), структуры событий, области Скотта. Также семантические области были разработаны для первичных структур событий с приоритетами [8] и вероятностных структур событий [20].

Особое место среди параллельных систем занимают системы реального времени, поведение которых в значительной степени зависит от количественных временных характеристик. Для систем реального времени важны как модели вычислений, так и модели времени. В литературе такие системы часто представляются временными автоматами [21], временными системами переходов [22] и алгебрами временных процессов (см., например, [23]). Однако все эти формализмы базируются на интерливинговой семантике и не позволяют моделировать параллелизм естественным образом (напрямую). К временным моделям с семантикой "истинного параллелизма" относятся временные расширения моделей структур событий [24-28], сетей-процессов [29, 30], сетей Петри [31-33], причинных деревьев [34], частично-упорядоченных множеств [35, 36], систем конфигураций [37], асинхронных систем переходов [38]. Перечисленные выше временные модели могут быть классифицированы относительно семи дихотомий:

• дискретное/непрерывное время. В дискретных моделях (см., например, [30, 33]) время задается целыми числами. Такой подход обычно используется для описания систем с общим глобальным счетчиком времени. Время делится на счетное количество тактов: п + 1-ый такт начинается в га-ый момент времени и заканчивается в п + 1-ый. Дальнейшее разбиение времени внутри тактов не предусматривается. В непрерывных моделях [24, 26, 32, 34, 37] время измеряется по непрерывной временной шкале, и возможно неограниченное число событий при переходе системы из одного состояния в другое;

• абсолютное/относительное время. В процессе функционирования системы временные характеристики связываются либо с началом ее функционирования (абсолютное время) [24, 27], либо отсчитываются от конца предыдущего действия системы (относительное время) [32];

• явное/неявное понятие прохождения времени. Известно, что временная система функционирует двумя способами: посредством выполнения действия и посредством прохождения некоторого времени. Эти два понятия становятся ортогональными при явном введении понятия прохождения времени. Такой подход рассмотрен в [37], а альтернативный - в [24, 26, 32, 38];

• задержанные/мгновенные действия. В моделях, описанных в [26, 33, 36, 38], задержка действия смоделирована как временной промежуток между началом выполнения действия и его окончанием. При втором подходе выполнение действия само не требует времени, но, как правило, может быть отложено на определенный срок [24, 32, 34, 37];

• с локальными часами/без них. Использование локальных часов [29, 32, 38] позволяет описывать эволюцию различных частей распределенных систем. Иначе говоря, каждое событие имеет свой таймер задержки, который начинает отсчитывать время с того момента, когда событие становится активным, и останавливается, когда событие становится пассивным. Такой подход позволяет достаточно легко изучать поведе-

ние системы локально. С другой стороны, как было продемонстрировано в [24], операционная семантика алгебр временных процессов может быть описана проще, если не использовать локальные часы;

• несогласованные/согласованные по времени трассы. В несогласованных по времени трассах предшествование событий не отражает их временного порядка, поэтому во многих работах такой подход не используется (см., например, [30, 32]). Однако, как сообщалось в статьях [24, 38], несогласованные по времени трассы позволяют построить семантику "истинного параллелизма" для временных интерливинговых алгебр процессов, т.е. установить связи между "истинным параллелизмом" и интерливингом;

• " срочные" / " несрочные" действия. Понятие "срочного" действия подразумевает, что действие должно быть выполнено сразу, как только оно готово, т.е. все его предшественники выполнились и его временные ограничения также выполнены (см. [32, 37, 38]). Однако иногда требование "срочного" выполнения временных действия является слишком жестким. Один из способов решения этой проблемы - добавление "несрочных" действий. Например, в работе [24] были использованы оба вида действий.

Цель данной работы состоит в том, чтобы разработать временные расширения наиболее популярных и изученных классов структур событий - первичных, расслоенных, стабильных, и на основе теоретико-категорных методов установить строгие взаимосвязи как между данными моделями, так и данных моделей с областями Скотта. Следует отметить, что такой подход, насколько нам известно, пока не исследовался в литературе по параллельным моделям с реальным временем.

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

а

в

с\

гед

С сп/ И-гед

&тс{

Есп!

С 1п(1 с

^гэр

1)Гед

ЕГШ.{

Рис. 1.

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

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком