О синтезе программ на языке Java по алгеброалгоритмическим спецификациям
Рассмотрены средства алгоритмических описаний для представления последовательных и асинхронных алгоритмов для их формализованного проектирования. Предложены алгоритмы диалогового конструирования алгоритмов и генерации программ на целевых языках программирования. Описан метод синтеза многопоточных п...
Gespeichert in:
| Datum: | 2006 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут програмних систем НАН України
2006
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/2334 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | О синтезе программ на языке Java по алгеброалгоритмическим спецификациям / А.Е. Дорошенко, Е.А. Яценко // Проблеми програмування. — 2006. — N 4. — С. 58-70. — Бібліогр.: 15 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859624157481795584 |
|---|---|
| author | Дорошенко, А.Е. Яценко, Е.А. |
| author_facet | Дорошенко, А.Е. Яценко, Е.А. |
| citation_txt | О синтезе программ на языке Java по алгеброалгоритмическим спецификациям / А.Е. Дорошенко, Е.А. Яценко // Проблеми програмування. — 2006. — N 4. — С. 58-70. — Бібліогр.: 15 назв. — рос. |
| collection | DSpace DC |
| description | Рассмотрены средства алгоритмических описаний для представления последовательных и асинхронных алгоритмов для их формализованного проектирования. Предложены алгоритмы диалогового конструирования алгоритмов и генерации программ на целевых языках программирования. Описан метод
синтеза многопоточных программ на языке Java по схемам асинхронных алгоритмов.
Розглянуто засоби алгоритмічних описів для подання послідовних і асинхронних алгоритмів для їх формалізованого проектування. Запропоновано алгоритми діалогового конструювання алгоритмів та генерації програм в цільових мовах програмування. Описано метод синтезу багатопоточних програм мовою Java за схемами асинхронних алгоритмів.
The means of algorithmic descriptions for representation of sequential and asynchronous algorithms for their formalized designing are considered. The algorithms of dialogue constructing of algorithms and generating of programs in target programming languages are offered. The method of synthesis of multithreaded programs in Java corresponding to the schemes of asynchronous algorithms is described.
|
| first_indexed | 2025-11-29T09:56:48Z |
| format | Article |
| fulltext |
Інструментальні засоби і середовища програмування
© А.Е. Дорошенко, Е.А. Яценко, 2006
58 ISSN 1727-4907. Проблеми програмування. 2006. № 4
УДК 681.3
А.Е. Дорошенко, Е.А. Яценко
О СИНТЕЗЕ ПРОГРАММ НА ЯЗЫКЕ JAVA
ПО АЛГЕБРОАЛГОРИТМИЧЕСКИМ СПЕЦИФИКАЦИЯМ
Рассмотрены средства алгоритмических описаний для представления последовательных и асинхрон-
ных алгоритмов для их формализованного проектирования. Предложены алгоритмы диалогового кон-
струирования алгоритмов и генерации программ на целевых языках программирования. Описан метод
синтеза многопоточных программ на языке Java по схемам асинхронных алгоритмов.
Введение
Важной проблемой современного
программирования является его математи-
зация, разработка формализованных языков
проектирования алгоритмов и программ, а
также их абстрактных моделей. К средст-
вам, ориентированным на решение проблем
формализации, обоснования правильности,
улучшения алгоритмов (по выбранным кри-
териям) принадлежат алгебры алгоритмов.
Украинской кибернетической школой вне-
сен значительный вклад в разработку алгебр
алгоритмов фундаментальными работами
В.М. Глушкова, в русле которых была по-
строена теория систем алгоритмических ал-
гебр (САА) и их модификаций [1]. Аппарат
САА стал основой метода многоуровневого
структурного проектирования программ
(МСПП). Начало инструментальным сред-
ствам метода МСПП в свое время было по-
ложено созданием системы МУЛЬТИПРО-
ЦЕСИСТ, ориентированной на структурный
синтез программ (на языках ПЛ/1, Фортран,
Паскаль и др.) по их многоуровневым про-
ектам, оформленным на входном языке про-
ектирования САА/1 [2]. Развитие объектно-
ориентированных технологий требует но-
вых подходов к инструментальным средст-
вам программирования, появились эффек-
тивные языки проектирования и средства
генерации программ в объектно-ориентиро-
ванных средах (например, язык UML и его
инструментарий [3]). С развитием Интер-
нет-технологий возникли языки, ориентиро-
ванные на разработку Web-приложений.
Отметим также, что разработка современ-
ного программного обеспечения тесно свя-
зана с развитием и использованием моделей
параллельных вычислений, которые прони-
зывают большинство аспектов архитектуры
и средств программирования современных
компьютерных систем [4–6].
В данной работе описан разработан-
ный интегрированный инструментарий,
ориентированный на формализованное про-
ектирование алгоритмов и синтез последо-
вательных и параллельных программ в объ-
ектно-ориентированных средах программи-
рования (Java, С++ и др.). Рассмотрены
средства распараллеливания и синхрониза-
ции параллельных процессов в модифици-
рованных САА. Описана реализация асин-
хронных алгеброалгоритмических моделей
вычислений с общей памятью средствами
языка программирования Java с использова-
нием интегрированного инструментария.
1. Средства формализованного проекти-
рования программ в системах алгорит-
мических алгебр
В основу предлагаемых интегриро-
ванных инструментальных средств проек-
тирования и генерации программ положен
аппарат САА и их модификаций [1]. Моди-
фицированные САА (САА-М) предназна-
чены для формализации процессов мульти-
обработки, возникающих, в частности, при
конструировании программного обеспече-
ния в мультипроцессорных системах.
САА являются двухосновной алгеб-
рой < U, B; Ω >, где U – множество опера-
торов, B – множество логических условий
[1]. Операторы представляют собой ото-
бражения информационного множества
(ИМ) в себя, логические условия являются
отображениями множества ИМ в множество
значений 3-значной логики E3 = {0, 1, µ,},
где 0 – ложь; 1 – истина; µ – неопределен-
ность. Сигнатура операций САА
Ω = Ω1 ∪ Ω2 состоит из системы Ω1 логиче-
Інструментальні засоби і середовища програмування
59
ских операций, принимающих значения в
множестве B, и системы Ω2 операций, при-
нимающих значения в множестве операто-
ров U. В САА < U, B; Ω > фиксируется сис-
тема образующих Σ, представляющая собой
конечную функционально полную совокуп-
ность операторов и логических условий. С
помощью этой совокупности посредством
суперпозиции операций, входящих в Ω, по-
рождаются произвольные операторы и ло-
гические условия из множеств U и B. К ло-
гическим операциям системы Ω1 относятся
обобщенные булевы операции: дизъюнкция
(α ∨ β), конъюнкция (α ∧ β), отрицание ( α ),
а также операция β = Aα левого умножения
условия на оператор. К основным оператор-
ным операциям системы Ω2 относятся: ком-
позиция A * B, альтернатива (α-дизъюнк-
ция) ([α] A, B), цикл (α-итерация) {[α] A}.
Представления в САА < U, B; Ω > операто-
ров из U посредством суперпозиций, вхо-
дящих в сигнатуру Ω, получили название
регулярных схем (РС) [1].
Сигнатура Ω' модифицированных
САА, кроме перечисленных конструкций,
входящих в Ω, содержит операции, предна-
значенные для представления параллельных
вычислений. К этим операциям относится, в
частности, асинхронная дизъюнкция A ∨& B
– бинарная операция на множестве U, со-
стоящая в асинхронном применении опера-
торов A и B. Суперпозиция бинарных опе-
раций асинхронной дизъюнкции приводит к
производной операции m-местной асин-
хронной дизъюнкции A
m
i =
∨&
1
, состоящей в
параллельном выполнении m ветвей вычис-
лений. Для синхронизации параллельных
ветвей в САА-М используются контрольные
точки и синхронизаторы.
Контрольные точки представляют
собой фиксированные позиции между опе-
раторами в схеме [1]. С каждой контроль-
ной точкой T ассоциировано условие u,
ложное до тех пор, пока процесс вычисле-
ний не достиг точки T, истинное с момента
достижения данной точки и неопределенное
при наличии аварийных остановок на пути,
ведущем к точке T данной схемы. Условие u
называется условием синхронизации, ассо-
циированным с точкой T, которая далее
обозначается T(u).
Под синхронизатором понимается
цикл S(u) = {[u] E}, где u – логическая
функция, зависящая от условий синхрони-
зации, ассоциированных с некоторыми кон-
трольными точками схемы [1]. Синхрониза-
тор, установленный в некотором месте схе-
мы, осуществляет задержку вычислений в
данном месте схемы вплоть до момента, ко-
гда его условие синхронизации u (сопря-
женное с прохождением соответствующих
контрольных точек) станет истинным.
С помощью рассмотренных операций
формализуется асинхронная мультиобра-
ботка [1], состоящая в совместном функ-
ционировании нескольких ветвей вычисле-
ний, снабженных специальными каналами,
реализующими, в случае необходимости,
ожидания и обменные взаимодействия ме-
жду параллельными ветвями. Представле-
ния алгоритмов в САА-М, специфицирую-
щие асинхронные операторные взаимодей-
ствия, называются параллельными регуляр-
ными схемами (ПРС). Отметим, что САА-М
также содержит средства, необходимые для
описания синхронных вычислений. В рабо-
тах [1, 5, 7 - 10] аппарат САА-М применен
при решении задач символьной мультиоб-
работки: последовательных и параллельных
сортировок, поиска, языкового процессиро-
вания и др. Проиллюстрируем рассмотрен-
ные понятия на примере параллельной ад-
ресной сортировки массива.
Пример 1. Суть адресной сорти-
ровки состоит в вычислении для каждого из
элементов входного (сортируемого) массива
M0 его индекса (адреса) в выходном массиве
M. При этом вычисление индекса для каж-
дого элемента входного массива является
независимым. В рассматриваемом алго-
ритме массив M0 длины n разбивается на m
подмассивов )(0 iМ (i = 1, ..., m), которые
обрабатываются m параллельными ветвями
(m ≥ 1). Ветвь с номером i осуществляет вы-
числение выходных индексов элементов
подмассива )(0 iМ и их вставку в массив M.
ПРС ) , ,П(-АДРСОРТ 0 mMM адресной
сортировки имеет следующий вид:
Інструментальні засоби і середовища програмування
60
где СТАРТ – оператор инициализации
данных (ввод сортируемого массива);
АДР_ВЕТВЬ(i) – ветвь, осуществляющая
вставку элементов подмассива )(0 iМ в
выходной массив М; ВЫЧ_ГР(i, m1, m2) –
вычисление границ (m1, m2) подмассива
)(0 iМ ; АДР_ВСТАВ(j) – составной
оператор, вычисляющий индекс j-го
элемента массива 0М (j = 1, ..., m) в
выходном массиве М, и выполняющий
вставку этого элемента в массив М;
))(( iТ ОБР_ЗАК – контрольная точка для
фиксации момента завершения обработки в
i -й ветви; )(ОБР_ЗАКS – синхронизатор по
условию достижения контрольных точек во
всех m параллельных ветвях; ФИН –
заключительный оператор (вывод отсорти-
рованного массива).
Смысл приведенного алгоритма
состоит в параллельном функционировании
m ветвей вычислений )iАДР_ВЕТВЬ( ,
каждая из которых осуществляет вставку
элементов подмассива )(0 iМ в массив М с
помощью оператора АДР_ВСТАВ(j). В
операторе ) , ,П(-АДРСОРТ 0 mMM нахо-
дится синхронизатор )(ОБР_ЗАКS , выпол-
няющий задержку вычислений до тех пор,
пока все ветви не закончат обработку.
После завершения выполнения синхрони-
затора имеем отсортированный массив М.
Более подробно метод параллельной адрес-
ной сортировки описан в [7].
2. Разработка приложений в интегриро-
ванном инструментарии проектирова-
ния и синтеза программ
В данном разделе рассматривается
процесс автоматизированного проектирова-
ния и генерации программ по формализо-
ванным спецификациям в САА-М с исполь-
зованием разработанного в [11] интегриро-
ванного инструментария. Инструментарий
основывается на методе диалогового конст-
руирования синтаксически правильных про-
грамм [9] и использует различные формы
представления алгоритмов в процессе их
проектирования – естественно-
лингвистическую (САА-схемы), алгебраи-
ческую (регулярные схемы) и граф-
схемную. Отметим, что интегрированный
инструментарий может быть настроен на
требуемый входной язык, представленный в
алгебре алгоритмов, и выходной (целевой)
язык программирования. В настоящее время
он поддерживает генерацию последова-
тельных и параллельных (многопоточных)
программ на языке Java по САА-схемам ал-
горитмов. Для синтеза программ совместно
с интегрированным инструментарием ис-
пользуются средства визуализированного
проектирования программ – язык UML и
система Rational Rose. Интегрированный
инструментарий состоит из следующих ос-
новных компонентов:
• ДСП-конструктора, предназначен-
ного для диалогового проектирования син-
таксически правильных схем алгоритмов и
синтеза программ;
• редактора граф-схем;
• трансформатора, осуществляюще-
го диалоговое преобразование регулярных
схем;
• генератора САА-схем по распреде-
ленным гиперсхемам;
• среды конструирования алгеброал-
горитмических описаний (СКАО) [10] сим-
вольной мультиобработки, содержащей
описание конструкций САА-М, базисных
понятий и их программных реализаций; ме-
таправила конструирования алгоритмов,
схемы алгоритмов, стратегии обработки и
гиперсхемы.
2.1. Диалоговое конструирование
схем алгоритмов. В основу функциониро-
вания ДСП-конструктора положен диалого-
вый режим с использованием меню подста-
новок и дерева конструирования алгоритма
(рис. 1). Меню состоит из конструкций
САА-М, суперпозиция которых позволяет
создавать алгоритмы в упомянутых ранее
ФИН,*)ОБР_ЗАК(*))АДР_ВЕТВЬ((*СТАРТ:: ) , ,П(- АДРСОРТ
1
0 SimMM
m
i=
∨=
,))(ОБР_ЗАК(*)}1(*)(]АДР_ВСТАВ{[*
*(,,ВЫЧ_ГР
2
121
iTjjjmj
mjmmii
+=>
== )*)( ::)АДР_ВЕТВЬ(
Інструментальні засоби і середовища програмування
61
формах. Выбранные пользователем конст-
рукции, а также операторные и логические
переменные, входящие в них, отображаются
в дереве с дальнейшей детализацией пере-
менных. В зависимости от типа выбранной
переменной система предлагает соответст-
вующий список операций САА-М или ба-
зисных понятий из СКАО. Отметим поуро-
вневый стиль конструирования алгоритма, а
также возможность переходов на различные
уровни (узлы дерева) с продолжением про-
цесса диалогового конструирования.
Процесс построения дерева констру-
ирования T для некоторого алгоритма мо-
жет быть представлен следующей РС:
ДСП_НАБОР(T) = ИНИЦ(T) *
*{[КОНЕЦ_ДСП(T)] ВНН * ВНК *
* ОБРАБОТКА_УЗЛА(T) * ВЫВОД},
где ИНИЦ(T) – формирование корневой
вершины дерева T с названием первого сос-
тавного оператора, а также его дочернего
узла, помеченного именем операторной
переменной; КОНЕЦ_ДСП(T) – условие,
истинное, если все переменные констру-
ируемой схемы проинтерпретированы; ВНН
– оператор выбора нужной непроинтер-
претированной переменной в дереве T; ВНК
– выбор нужной конструкции САА-М,
базисного или составного элемента;
ОБРАБОТКА_УЗЛА(T) – оператор, кото-
рый формирует дочернюю вершину для те-
кущего выбранного узла дерева и помечает
ее текстом выбранного элемента меню, а
также формирует вершины дерева с назва-
ниями операторных или логических пере-
менных (если выбранный элемент – опе-
рация САА). В процессе ДСП конструи-
рования операции ВНН и ВНК выпол-
няются пользователем. По полученному те-
кущему дереву конструирования T осу-
ществляется вывод текста схемы алгоритма
с помощью оператора ВЫВОД. Разра-
ботанная схема ДСП_НАБОР(T) подобна
схеме ДСП.БС, приведенной в [9]. В схеме
ДСП.БС осуществлялась обработка пере-
менных конструированной схемы лишь в
одном направлении (слева направо) и вы-
полнялся последовательный переход сверху
вниз от предыдущего уровня дерева кон-
струирования к следующему. В отличие от
упомянутой схемы, в построенной РС
ДСП_НАБОР(T) есть возможность выпол-
Рис. 1. Окно ДСП-конструктора с параллельным алгоритмом адресной сортировки
Інструментальні засоби і середовища програмування
62
нять конкретизацию переменных конструи-
руемой схемы в произвольном порядке,
переходя на различные уровни дерева T.
Пример дерева конструирования
показан на рис. 1 в окне ДСП-конструктора.
Отметим, что в ДСП-конструкторе дерево
для каждого из составных операторов
схемы алгоритма приводитя на отдельной
вкладке окна “Дерево алгоритма”. Текст
САА-схемы, соответствующий дереву кон-
струирования, отображается в отдельном
текстовом окне в аналитической или естес-
твенно-лингвистической форме в зависи-
мости от установленной опции (левое ниж-
нее окно в окне ДСП-конструктора).
2.2. Cинтез программ по схемам
алгоритмов. По полученному в процессе
конструирования алгоритма дереву, реали-
зациями элементарных операторов и усло-
вий на целевом объектно-ориентированном
языке программирования, а также другими
фрагментами, ДСП-конструктор выполняет
синтез программы. В процессе синтеза
управляющие конструкции САА-схемы ал-
горитма (асинхронная дизъюнкция, компо-
зиция, альтернатива, цикл и др.) отобража-
ются в соответствующие операторы языка
программирования, а вместо базисных опе-
раторов и предикатов подставляются их ре-
ализации на этом же языке из СКАО. Соста-
вные операторы могут быть представлены
как подпрограммы (методы). На вход синте-
затора поступает также файл, который со-
держит каркасное описание основного клас-
са программы (без реализаций методов), в
который выполняется подстановка синтези-
рованного кода. Проектирование классов
программы и их взаимосвязей, а также ге-
нерация каркасного программного кода вы-
полняется с помощью инструментария
Rational Rose. В файл, полученный в ре-
зультате моделирования в Rational Rose,
выполняется подстановка кода, сгенериро-
ванного в предлагаемом инструментарии.
В табл. 1 приведено описание в
СКАО [10] основных операторных опера-
ций САА (композиции, альтернативы, цик-
ла), реализации которых на языке Java ис-
пользуются в процессе генерации программ.
Приведенные реализации содержат строки
“^оператор1^” и “^оператор2^”, вместо ко-
торых процессе синтеза будут подстав-
лены тексты реализаций операндов этих
операций.
В табл. 2 приведены примеры описа-
ния в СКАО базисных элементов для алго-
ритмов сортировки. Естественно лингвисти-
ческая и аналитическая формы описания
базисного элемента содержат в себе имена
формальных параметров в скобках. Факти-
ческие параметры, которые задаются в
САА-схемах, заменяют при синтезе про-
граммы соответствующие формальные па-
раметры в тексте реализации базисного по-
нятия на языке программирования. Реализа-
ции базисных элементов написаны с ис-
пользованием компонента повторного ис-
пользования – класса Sorting, предназна-
ченного для решения различных задач сор-
тировки (более подробно этот класс рас-
сматривается далее в примере 2). Призна-
ком формального параметра в реализации
Таблица 1. Описание в СКАО операторных операций САА
Аналитическая
форма
Естественно-
лингвистическая форма
Реализация на языке Java
“оператор1” *
“оператор2”
“оператор1” ЗАТЕМ
“оператор2”
^оператор1^;
^оператор2^
([‘условие1’]
“оператор1”,
“оператор2”)
ЕСЛИ “условие1”
ТО “оператор1”
ИНАЧЕ “оператор2”
КОНЕЦ ЕСЛИ
if (^условие1^)
{
^оператор1^
}
else { ^оператор2^ }
{[‘условие1’]
“оператор1”}
ПОКА НЕ ‘условие1’
ЦИКЛ
“оператор1”
КОНЕЦ ЦИКЛА
while (!(^условие1^))
{
^оператор1^
}
Інструментальні засоби і середовища програмування
63
является символ “%”, за которым следует
порядковый номер параметра в тексте ба-
зисного оператора или предиката. Напри-
мер, в базисном операторе “Переставить l, r
по У(i) в (М)” присутствует параметр i –
номер указателя. Значение этого параметра
будет подставлено вместо соответству-
ющего формального параметра в реализа-
ции этого оператора, который имеет вид:
s.transp(%1), где s – экземпляр класса
Sorting; transp – метод данного класса, вы-
полняющий перестановку элементов масси-
ва М, соседних с указателем. Реализация
других базисных элементов, приведенных в
табл. 2, также являются вызовами методов
класса Sorting. Отметим, что в процессе ге-
нерации программы перед текстом реализа-
ции того или иного базисного элемента до-
бавляется его название в виде комментария.
Отображение в языке программиро-
вания для любого из элементов СКАО мо-
жет содержать несколько вариантов, один
из которых можно выбрать в зависимости
от решаемой задачи. Например, базисный
оператор инициализации (СТАРТ) имеет
различные варианты реализации на язы-
ке программирования для сортировки и
поиска.
В ДСП-конструкторе есть воз-
можность указать параметры генерации
программы по схеме алгоритма. Данные па-
раметры разделены на две группы: общие
параметры и параметры генерации для со-
ставных элементов схемы. Общие парамет-
ры включают имя входного файла, содер-
жащего каркасный программный код, и имя
результирующего файла генерации; пара-
метры подстановки сгенерированного кода
во входной файл. Код может быть подстав-
лен вместо указанной цепочки символов в
файле (например, “// <target>”) или в тело
указанной в параметрах функции, которая
описана во входном файле. В случае языка
Java код обычно подставляется в метод
main. В параметрах генерации для состав-
ных операторов и предикатов для каждого
из них можно задать имя метода, в тело ко-
торого будет подставлен сгенерированный
для них код на языке программирования.
Генерация кода в ДСП-конструкторе
осуществляется по дереву конструирования,
все терминальные вершины которого явля-
ются базисными операторами или предика-
тами (т.е. все переменные сконструирован-
ной схемы проинтерпретированы). В про-
цессе генерации обход дерева конструиро-
вания осуществляется в направлении слева
направо. Обработка начинается с нижнего
листа самой левой ветви дерева, затем обра-
батываются все листья и узлы дерева так,
что ветви рассматриваются слева направо, а
узел обрабатывается лишь после обхода
всех ветвей, которые исходят из него. Отме-
тим, что такой обход дерева обычно исполь-
зуется для получения постфиксной записи
при трансляции выражений [12]. Обработка
каждой вершины дерева конструирования
осуществляется в зависимости от ее типа, а
именно: базисное понятие, переменная, имя
составного элемента или операция САА.
Таблица 2. Описание в СКАО базисных операторов и предикатов для задач сортировки
Тип Естественно-
лингвистическая форма
Аналитическая
форма
Реализация на Java
Операторы “Переместить У(i) на (n)
по (М) вправо”
Р(У(i), (n)) s.moveR(%1, %2);
“Переставить l, r по У(i)
в (М)”
ТРАНСП(l, r|
У(i))
s.transp(%1);
“Установить У(i) на У(j)
в (М)”
УСТ(У(i), У(j)) s.place(%1,
s.getPointerPos(%2));
Предикаты ‘l > r по У(i) в (М)’ l > r| У(i) s.compare(%1, “>”)
‘Расстояние между У(i)
и У(j) в (М) равно (n)’
d(У(i), У(j)) = (n) s.distance(%1, %2) ==
%3
‘Указатель У(i) в конце
(М)’
d(У(i), К) s.atEnd(%1)
Інструментальні засоби і середовища програмування
64
Если текущий элемент дерева – базисный
оператор или предикат, то осуществляется
поиск реализации данного элемента на язы-
ке программирования в СКАО. Если най-
денная реализация содержит несколько воз-
можных вариантов, то из них выделяется
вариант, специально указанный пользовате-
лем для текущего проекта или вариант по
умолчанию (в случае, если вариант не был
выбран пользователем). Затем осуществля-
ется подстановка в реализацию значений
фактических параметров базисного понятия.
Далее перед полученной реализацией до-
бавляется текст базисного элемента схемы в
виде комментария и полученный текст за-
писывается в стек. Если текущая вершина –
операция САА, то в ее реализацию вместо
строк, которые соответствуют именам пе-
ременных, осуществляется подстановка
реализаций ее операндов, которые последо-
вательно изымаются из стека. Полученный
текст записывается в стек. Если текущий
обрабатываемый элемент дерева – перемен-
ная некоторой операции САА, то вершина
пропускается. Текущая вершина дерева
также может быть именем составного опе-
ратора или предиката, который соответст-
вует отдельному поддереву конструирова-
ния. В этом случае в стек записывается
текст реализации данного элемента, полу-
ченный при обработке его дерева конструи-
рования и сохраненный в специальной таб-
лице. Перед текстом составного элемента
добавляется комментарий с информацией о
том, что в данной части программы начина-
ется код, соответствующий составному опе-
ратору схемы алгоритма. Содержимое вер-
шины стека после обработки корневой вер-
шины дерева конструирования является ре-
зультирующим программным кодом, кото-
рый соответствует САА-схеме алгоритма.
Полученный текст вставляется в требуемые
позиции файла с каркасным программным
кодом, поступающего на вход генератора
программ перед началом генерации.
2.3. Синтез параллельных много-
поточных программ. Асинхронные алго-
ритмы, представленные в САА-М, в таких
языках программирования, как Java, C++,
Perl, Python, Delphi, могут быть реализо-
ваны с помощью подпроцессов или потоков
(threads). Поток в многопоточных операци-
онных системах – наименьшая единица вы-
полнения. Для каждого процесса (объекта,
создаваемого при запуске программы) ОС
создает один главный поток, который явля-
ется потоком команд центрального процес-
сора, которые выполняются поочередно.
При необходимости главный поток может
создавать другие потоки, пользуясь для это-
го программным интерфейсом ОС. Все по-
токи, созданные процессом, выполняются в
адресном пространстве этого процесса и
имеют доступ к его ресурсам. Если процесс
создал несколько потоков, то все они вы-
полняются параллельно, причем время цен-
трального процессора (или нескольких цен-
тральных процессоров в мультипроцессор-
ных системах) распределяется между этими
потоками. Каждому потоку дается опре-
деленный интервал времени, на протя-
жении которого он находится в активном
состоянии.
Текущая версия интегрированного
инструментария обеспечивает синтез парал-
лельных программ на языке программиро-
вания Java [13]. Отметим, что Java поддер-
живает многопоточность не только на уров-
не библиотек, но и на уровне самого языка,
который значительно облегчает построение
программ, которые надежно работают в
многопоточном режиме. Java предоставляет
возможность реализации подпроцессов с
помощью класса Thread (из пакета
java.lang), который содержит все средства,
необходимые для создания потоков, управ-
ления их состоянием и синхронизации. При
этом для организации многопоточных про-
грамм существует две возможности: первая
предусматривает создание подкласса класса
Thread, вторая – создание класса, который
реализует интерфейс Runnable. В этих клас-
сах переопределяется метод run, который
содержит код, предназначенный для выпол-
нения в рамках отдельного потока. Отме-
тим, что метод main в программах Java по
умолчанию является подпроцессом, и из не-
го или из другого активного метода, могут
начинать свое выполнение другие под-
процессы.
Потоки, работающие параллельно в
многопоточной системе, могут обращаться
одновременно к общим объектам в памяти,
что может привести к неправильной работе
Інструментальні засоби і середовища програмування
65
программ. Решением этой проблемы явля-
ется синхронизация потоков. Java обеспечи-
вает два уровня синхронизации:
• защита совместно используемых
ресурсов;
• сигнализация об изменениях в
состояниях между процессами.
Для синхронизации фрагмента кода,
осуществляющего доступ к разделяемым
ресурсам, этот фрагмент включается в блок
или метод, помеченный модификатором
synchronized. Когда поток начинает выпол-
нение синхронизированного фрагмента ко-
да, этот фрагмент блокируется. До окон-
чания выполнения синхронизированного
фрагмента либо до тех пор, пока блокировка
не будет явно отменена, ни один другой по-
ток не может начать выполнение аналогич-
ного фрагмента кода.
Другим важным аспектом процесса
синхронизации в Java является передача
подпроцессу сообщения, указывающего, что
на данный момент уже выполнено условие,
исполнения которого он “ждет” [13]. Если
подпроцесс в определенный момент вычис-
лений не может продолжать работу, так как
объект, с которым он связан, не находится в
надлежащем состоянии, он может вызвать
метод wait, который переведет этот подпро-
цесс в состояние ожидания. Ожидающий
поток может быть вновь активирован в слу-
чае, если другой поток вызовет для него ме-
тод notify или notifyAll. Метод notify возоб-
новляет работу одного потока, а метод
notifyAll активирует все потоки, ожидаю-
щие снятия блокировки, реализованной с
помощью некоторого объекта. Как и вызов
метода wait, вызовы методов notify и
notifyAll могут быть исходить только из
синхронизированного блока.
Методы wait, notify и notifyAll ис-
пользованы в интегрированном инструмен-
тарии для реализации средств синхрониза-
ции САА-М (контрольных точек и синхро-
низаторов), рассмотренных в разделе 2.
Пример 2. В качестве иллюстрации
рассмотрим реализацию многопоточной
программы на языке Java, сгенерированной
по регулярной схеме параллельной адрес-
ной сортировки (см. пример 1) с использо-
ванием интегрированного инструментария и
системы Rational Rose. На рис. 2 показана
диаграмма классов UML с основными клас-
сами разрабатываемого приложения. Класс
Adrsort – основной класс программы адрес-
ной сортировки. Выполнение программы
начинается с метода main данного класса, в
котором вводится сортируемый массив, вы-
зываются m параллельных потоков, осуще-
ствляется синхронизация (ожидание завер-
шения вычислений во всех ветвях) и выво-
дятся результаты сортировки. В методе ins
находится реализация составного оператора
АДР_ВСТАВ(j) схемы АДРСОРТ -
) , ,П( 0 mMM . Данный метод в процессе
сортировки вызывается параллельными по-
токами. В классе SortThread, наследующем
класс Thread, находится описание кода для
i-го параллельного потока (i = 1, …, m).
Классы Adrsort и SortThread используют ме-
тоды изображенного на диаграмме класса
Sorting – повторно используемого компо-
нента для решения различных задач сорти-
ровки (пузырьковой, челночной, адресной и
др.). Этот класс содержит описание данных
– обрабатываемого массива, указателей,
маркеров, контрольных точек, методы дос-
тупа к этим данным, а также методы оста-
новки и возобновления работы главного по-
тока и отсчета времени, истекшего с начала
сортировки.
В Rational Rose для класса Adrsort
была выполнена генерация файла с каркас-
ным программным кодом, не содержащим
реализаций методов main и ins. Дальнейшая
разработка алгоритмов этих методов, а так-
же синтез и подстановка кода, реали-
зующего эти функции, выполнены в интег-
рированном инструментарии. Генерация
класса SortThread полностью осуществлена
в ДСП-конструкторе.
В процессе синтеза кода программа
ДСП-конструктора использует шаблоны
программных реализаций конструкций САА
и базисных понятий из СКАО, примеры ко-
торых были приведены выше в табл. 1 и 2.
Далее рассмотрены примеры программных
реализаций операций, предназначенных для
формализации параллельных вычислений:
асинхронной дизъюнкции, синхронизатора,
контрольных точек. Приводится естест-
венно-лингвистическая форма представле-
ния каждой из этих операций и их отобра-
жение в текстовый шаблон на языке Java.
Інструментальні засоби і середовища програмування
66
В СКАО интегрированного инстру-
ментария для реализации операции m-мест-
ной асинхронной дизъюнкции A
m
i =
∨&
1
(есте-
ственно-лингвистическая форма этой опе-
рации – ПАРАЛЛЕЛЬНО (i = 1, ..., m)
(“оператор1”)) для рассматриваемой адрес-
ной сортировки был выбран следующий ва-
риант шаблона на языке Java:
int m = s.getThreadNum();
for (int i = 1; i <= m; i++)
{
SortThread st = new SortThread(s, c, i);
}
// $classes
class SortThread extends Thread
{
Sorting s;
Adrsort c;
int n, m, i, j;
/* Конструктор класса */
SortThread(Sorting s, Adrsort c, int i)
{
this.s = s;
this.c = c;
Рис. 2. Диаграмма классов для параллельной адресной сортировки
Інструментальні засоби і середовища програмування
67
this.i = i;
n = s.getDataLen();
m = s.getThreadNum();
new Thread(this).start(); /* Запустить поток на выполнение */
}
public void run()
{
^оператор1^
}
}
Приведенный фрагмент программ-
мной реализации разделен на две части
строкой “// $classes”. В первой части опи-
сан цикл, в котором создаются m парал-
лельных потоков (объектов класса
SortThread). Во второй части фрагмента
приведен класс SortThread (наследующий
класс Thread), в котором описан шаблон
класса потока (без реализации метода
run()). Конструктор класса SortThread
выполняет инициализацию данных и за-
пуск подпроцесса с помощью метода
start(). Через параметры этому конструк-
тору передается объект класса Sorting,
экземпляр основного класса программы и
номер i создаваемого потока. Метод run
класса SortThread содержит строку
“^оператор1^”, вместо которой в процес-
се генерации будет подставлен код реа-
лизации операнда асинхронной дизъ-
юнкции. В результате синтеза в том мес-
те программы Java, которое соответству-
ет асинхронной дизъюнкции, будет при-
веден цикл создания потоков. Текст клас-
са SortThread (с текстом реализации i-й
ветви алгоритма) будет включен после
текста основного класса программы.
Вместо строк “This_class”, приведенных
в данном фрагменте, в процессе синтеза
подставляется имя основного класса, ука-
занное в параметрах генерации кода (на-
пример, Adrsort – основной класс про-
граммы адресной сортировки).
Для реализации на языке Java опе-
рации синхронизатора (естественно-
лингвистическая форма этой операции –
ЖДАТЬ ‘условие1’) для рассматриваемо-
го алгоритма сортировки в СКАО был
выбран следующий вариант шаблона:
if (! (^условие1^))
s.waitMain(); // Приостановить работу
главного потока
Здесь waitMain – метод класса
Sorting, выполняющий задержку вычис-
лений в главном потоке программы, в
случае, если условие ^условие1^ не вы-
полнено. Вместо строки “^условие1^”
для рассматриваемого алгоритма в про-
цессе генерации будет подставлен вызов
метода s.procEnd(), который возвращает
истинное значение в случае, если все m
параллельных ветвей завершили вычис-
ления, и ложное в противном случае.
Описание метода waitMain в классе
Sorting имеет вид
public void waitMain()
{
notified = false; // Установить признак того,
// что поток mainThread находится
// в состоянии ожидания
synchronized (mainThread)
Інструментальні засоби і середовища програмування
68
{
try { // Приостановить поток mainThread
mainThread.wait();
}
catch (InterruptedException e) { e.printStackTrace(); }
}
}
Здесь mainThread – переменная класса
Thread, содержащая информацию о глав-
ном потоке выполняющейся программы.
Поток mainThread в приведенном фраг-
менте переведен в состояние ожидания с
помощью вызова стандартного метода
wait().
Для реализации на языке Java опе-
ратора контрольной точки (естествен-
но-лингвистическая форма этого опера-
тора – КТ ‘условие1’) для случая рас-
смотренной адресной сортировки в
СКАО был выбран следующий вариант
шаблона:
^условие1^
if (s.procEnd())
s.notifyMain(); // Возобновить работу
главного потока
Вместо строки “^условие1^” для
рассматриваемого алгоритма в процессе
генерации будет подставлена программ-
ная реализация базисного элемента
ОБР_ЗАК(i), а именно, вызов метода
s.setCtrlPoint(i, true) класса Sorting. Этот
метод присваивает контрольной точке с
номером i (соответствующим номеру по-
тока) истинное значение. После выпол-
нения этого метода проверяется истин-
ность всех контрольных точек, ассоции-
рованных с подпроцессами, с помощью
вызова упомянутой выше функции
s.procEnd(). После завершения вычисле-
ний во всех подпроцессах (s.procEnd()
возвратила истинное значение) выполня-
ется метод notifyMain() класса Sorting,
возобновляющий работу главного пото-
ка. Описание этого метода имеет вид
public void notifyMain()
{
if (! (notified))
{
synchronized (mainThread)
{
/* Возобновить работу потока mainThread */
mainThread.notify();
// Установить признак того,
// что работа потока mainThread возобновлена
notified = true;
}
}
}
Інструментальні засоби і середовища програмування
69
В приведенной функции работа по-
тока mainThread возобновляется с помощью
вызова стандартного метода notify().
Таким образом, по асинхронным ал-
горитмам, представленным в САА-М, мо-
жет быть синтезирован вручную или авто-
матизированным способом (с применением
разработанного интегрированного инстру-
ментария) код на языках программирова-
ния, которые поддерживают создание мно-
гопоточных программ.
Заключение
В работе рассмотрены средства фор-
мализованного проектирования и синтеза
последовательных и асинхронных программ
по их представлениям в алгебрах алгорит-
мов. Предложены алгоритмы диалогового
конструирования алгоритмов и генерации
программ на целевых языках программи-
рования. Описан метод синтеза многопоточ-
ных программ на языке Java по асинхрон-
ным алгоритмам, формализованным в
САА-М.
К ограничениям интегрированного
инструментария можно отнести то, что в
схемах алгоритмов не учитывается объек-
тная ориентированность генерируемой про-
граммы. Она присутствует лишь на уровне
программных реализаций элементов схемы
в среде конструирования алгеброалгори-
тмических описаний инструментария, а
также в каркасном файле, поступающим на
вход синтезатора. Тем не менее, данная
проблема может быть решена в дальнейшем
путем настройки инструментария на
объектные САА-схемы [14, 15].
К перспективам развития интегри-
рованного инструментария следует отнести
его настройку на синтез параллельных
программ, использующих технологию MPI.
1. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л.
Методы символьной мультиобработки. –
Киев: Наук. думка, 1980. – 252 с.
2. Многоуровневое структурное проектирова-
ние программ: Теоретические основы, инст-
рументарий // Е.Л. Ющенко, Г.Е. Цейтлин,
В.П. Грицай, Т.К. Терзян. – М.: Финансы и
статистика, 1989. – 208 с.
3. Кватрани Т. Rational Rose 2000 и UML. Ви-
зуальное моделирование / Пер. с англ. – М.:
ДМК, 2001. – 176 с.
4. Дорошенко А.Е. Математические модели и
методы организации высокопроизводитель-
ных параллельных вычислений. Алгеброди-
намический подход. – Киев: Наук. думка,
2000. – 176 с.
5. Дорошенко А.Ю., Фінін Г.С., Цейтлін Г.О.
Алгеброалгоритмічні основи програмуван-
ня. — К.: Наук. думка, 2004. — 458 c.
6. Дорошенко А.Е., Цейтлин Г.Е. Алгеброав-
томатные спецификации параллельных про-
грамм над общей и распределенной памятью
// Проблемы программирования. – 2003. –
№ 3. – C. 24–33.
7. Яценко Е.А. Регулярные схемы алгоритмов
адресной сортировки и поиска // УСиМ. –
2004. – № 5. – С. 61 – 66.
8. Цейтлин Г.Е. Проектирование алгоритмов
параллельной сортировки // Программиро-
вание. – 1989. – № 6. – С. 4–19.
9. Цейтлин Г.Е. Введение в алгоритмику. –
Киев: Сфера. – 1998. – 310 с.
10. Яценко О.А. Середовище конструювання
алгоритмічних знань та інструментарій син-
тезу програм // Проблемы программирова-
ния. – 2006. – № 1–2. – С. 349–358.
11. Яценко Е.А., Мохница А.С. Инструменталь-
ные средства конструирования синтаксиче-
ски правильных параллельных алгоритмов и
программ // Проблемы программирования. –
2004. – № 2–3. – С. 444–450.
12. Ахо А., Ульман Дж. Теория синтаксическо-
го анализа, перевода и компиляции. – М.:
Мир, 1973. – 1. – 612 с.
13. Бишоп Д. Эффективная работа: Java 2. –
Киев: BHV, 2002. – 592 с.
14. Цейтлин Г.Е., Теленик С.Ф., Амонс А.А. Ал-
гебро-логическая формализация в объектно-
ориентированных технологиях // Проблемы
программирования. – 2002. – № 1–2. –
С. 136–146.
15. Doroshenko A.E., Ragozin D.V. Retargetable
and tuneable code generation for high perform-
ance DSP // “Parallel Computing Technolo-
gies”, Proc. 7-th Int. Conf. PaCT’2003, LNCS,
2003. – 2763. – P. 452–466.
Получено 01.09.2006
Інструментальні засоби і середовища програмування
70
Об авторах:
Дорошенко Анатолий Ефимович,
доктор физ.-мат. наук, профессор,
зав. отделом теории компьютерных
вычислений,
Яценко Елена Анатольевна,
кандидат физ.-мат. наук,
научный сотрудник.
Место работы авторов:
Институт программных систем
НАН Украины,
проспект Академика Глушкова, 40.
03680, Киев-187, Украина.
тел. (044) 526 1538
е-mail: dor@isofts.kiev.ua, aiyat@i.com.ua
|
| id | nasplib_isofts_kiev_ua-123456789-2334 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Russian |
| last_indexed | 2025-11-29T09:56:48Z |
| publishDate | 2006 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Дорошенко, А.Е. Яценко, Е.А. 2008-09-17T15:02:11Z 2008-09-17T15:02:11Z 2006 О синтезе программ на языке Java по алгеброалгоритмическим спецификациям / А.Е. Дорошенко, Е.А. Яценко // Проблеми програмування. — 2006. — N 4. — С. 58-70. — Бібліогр.: 15 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/2334 681.3 Рассмотрены средства алгоритмических описаний для представления последовательных и асинхронных алгоритмов для их формализованного проектирования. Предложены алгоритмы диалогового конструирования алгоритмов и генерации программ на целевых языках программирования. Описан метод синтеза многопоточных программ на языке Java по схемам асинхронных алгоритмов. Розглянуто засоби алгоритмічних описів для подання послідовних і асинхронних алгоритмів для їх формалізованого проектування. Запропоновано алгоритми діалогового конструювання алгоритмів та генерації програм в цільових мовах програмування. Описано метод синтезу багатопоточних програм мовою Java за схемами асинхронних алгоритмів. The means of algorithmic descriptions for representation of sequential and asynchronous algorithms for their formalized designing are considered. The algorithms of dialogue constructing of algorithms and generating of programs in target programming languages are offered. The method of synthesis of multithreaded programs in Java corresponding to the schemes of asynchronous algorithms is described. ru Інститут програмних систем НАН України Інструментальні засоби і середовища програмування О синтезе программ на языке Java по алгеброалгоритмическим спецификациям Про синтез програм мовою Java за алгеброалгоритмічними специфікаціями About the synthesis of Java programs by algebraalgorithmic specifications Article published earlier |
| spellingShingle | О синтезе программ на языке Java по алгеброалгоритмическим спецификациям Дорошенко, А.Е. Яценко, Е.А. Інструментальні засоби і середовища програмування |
| title | О синтезе программ на языке Java по алгеброалгоритмическим спецификациям |
| title_alt | Про синтез програм мовою Java за алгеброалгоритмічними специфікаціями About the synthesis of Java programs by algebraalgorithmic specifications |
| title_full | О синтезе программ на языке Java по алгеброалгоритмическим спецификациям |
| title_fullStr | О синтезе программ на языке Java по алгеброалгоритмическим спецификациям |
| title_full_unstemmed | О синтезе программ на языке Java по алгеброалгоритмическим спецификациям |
| title_short | О синтезе программ на языке Java по алгеброалгоритмическим спецификациям |
| title_sort | о синтезе программ на языке java по алгеброалгоритмическим спецификациям |
| topic | Інструментальні засоби і середовища програмування |
| topic_facet | Інструментальні засоби і середовища програмування |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/2334 |
| work_keys_str_mv | AT dorošenkoae osintezeprogrammnaâzykejavapoalgebroalgoritmičeskimspecifikaciâm AT âcenkoea osintezeprogrammnaâzykejavapoalgebroalgoritmičeskimspecifikaciâm AT dorošenkoae prosintezprogrammovoûjavazaalgebroalgoritmíčnimispecifíkacíâmi AT âcenkoea prosintezprogrammovoûjavazaalgebroalgoritmíčnimispecifíkacíâmi AT dorošenkoae aboutthesynthesisofjavaprogramsbyalgebraalgorithmicspecifications AT âcenkoea aboutthesynthesisofjavaprogramsbyalgebraalgorithmicspecifications |