В.Ш. Кауфман - Языки программирования - концепции и принципы (1990) (1160787), страница 67
Текст из файла (страница 67)
n : constant integer := 3;
type вид_процесса is (spa, spy, sp0);
type pr; -- предобъявление
type ppr is access pr;
task type pa is
entry настройка (a : in real; слева, снизу : in ppr);
entry сверху (X : in real);
entry cправа (Y : in real);
end pa;
task type px is
entry настройка (j : in integer; cнизу : in pa);
end px;
task type pb is
entry настройка (bi : in integer; слева : in pa);
end px;
type pr (p : вид_процесса) -- p - дискриминант
record -- вариантного комбинированного типа pr
case p is
when spa => sa:pa; -- все поля различны!
when spy => sy:py;
when sp0 => s0:p0;
end case;
end record;
task type p0 is ...;
task type py is ...;
end координаты_1;
package body координаты_1 is
task body pa is
aij, xj, yi, aij_xj : real;
прт-слева, прт-снизу : ppr;
begin
accept настройка (a :in real; слева,снизу :in ppr) do
aij := a; прт-слева := слева; прт-снизу := снизу;
end настройка;
. . .
accept сверху . . .;
. . .
accept справа . . .;
. . .
case птр-слева.p is -- proc_слева(птр-слева, yi);
when spa => птр-слева.sa.справа(yi);
when spy => птр-слева.sy.справа(yi);
when sp0 => птр-слева.s0.справа(yi);
end case;
. . .
case птр-снизу.p is -- proc_снизу(птр-снизу, xj);
when spa => птр-снизу.sa.сверху(xj);
when spy => птр-снизу.sy.сверху(xj);
when sp0 => птр-снизу.s0.сверху(xj);
end case;
. . .
end pa;
. . . -- аналогично (но проще) для px, py, pb, p0
для_pa : array (1..n, 1..n) of ppr; -- только
для_py : array (1..n) of ppr; -- указатели
для_p0 : array (1..n) of ppr; -- порождены
для_px : array (1..n) of px;-- порождение и запуск процессов;
для_pb : array (1..n) of pb;-- ждут настройки на pa
begin -- часть пакета, исполняемая при его загрузке
-- порождение процессов
for i in 1....n loop
for j in 1....n loop
для_pa (i,j) := new pr(spa);
end loop; -- создано n**2 процессов типа pa и ссылки
end loop; -- на них - в переменной для_pa ждут настройки!
for i in 1...n loop
для_py (i) := new pr(spy); -- настройка не нужна (почему?)
end loop; -- ждут рандеву с pa
for i in 1...n loop
для_p0 (i) := new pr(sp0); -- настройка не нужна (почему?)
end loop; -- ждут рандеву с pa
-- настройка процессов
for i in 1...n loop -- настройка процессов px на верхние pa
для_px.настройка(j, для_pa(1,j)); -- доступ к ним не нужен,
end loop; -- эти процессы сами заказывают рандеву
... -- аналогично настройка pb
-- настройка процессов pa
for i in 1..n-1 loop -- кроме последней строки
for j in 2..n loop -- кроме последнего столбца
для_pa(i,j).sa.настройка (a(i,j),
для_pa(i,j-1),
для_pa(i+1,j));
end loop; -- коммутация с остальными pa
end loop;
for j in 2..n loop
для_pa(n,j).sa.настройка (a(n,j),
для_pa(n,j-1),
для_p0(j)); -- коммутация с p0
end loop;
for i in 1..n-1 loop
для_pa(i,1).sa.настройка (a(i,1),
для_py(i), -- коммутация с py
для_pa(i,1));
end loop;
для_pa(n,1).sa.настройка (a(n.1),
для_py(n), для_p0(1)); -- коииутация левого нижнего
end координаты_1;
Очевидна нерегулярность и сложность "вариантного" решения. Становится
особенно наглядным различие уровня адекватности выразительных средств
сущности параллелизма, достигнутый в Оккаме и в Аде. Решая средствами Ады
проблемы, ранее успешно решенные средствами Оккама, мы убедились в том, что
Ада-решение действительно приводит к лишним затратам во время исполнения
программы, а также существенно сложнее для понимания.
Упражнение (повышенной трудности). Придумайте более изящные Ада-решения
рассмотренных проблем.
Подсказка. Сравните свои достижения с решением, изложенным в 17.12.
17.10. Перечень неформальных теорем о параллелизме в Аде и Оккаме
Завершим рассмотрение концепции параллелизма в современных ЯП перечнем
неформальных теорем, "доказательство" которых фактически представлено в
предыдущих разделах. Читателю рекомендуется доказать (или опровергнуть) эти
утверждения самостоятельно. Представим сначала утверждения, критикующие
концепцию параллелизма в Аде, а затем и концепцию параллелизма в Оккаме.
Критика Ады "со стороны Оккама"
1. Нет естественной симметрии между последовательным и параллельным
исполнением. Другими словами, нельзя придать программе, в которой требуется
и последовательное, и параллельное комбинирование процессов, регулярную
структуру - приходится о параллелизме заботиться особо.
2. Нет естественных средств идентификации асинхронных процессов. Оккам
позволяет не изобретать имена для каждого асинхронного процесса. Однако Ада
вынуждает это делать. Чтобы прочувствовать, сколь обременительно подобное
требование, представьте себе, что нужно изобретать имя для каждого оператора
в Паскале.
3. Нет естественных (учитывающих структуру программы) выразительных
средств для запуска и завершения процессов. И об этом приходится заботиться
особо.
4. Нет средств статической коммутации коллектива процессов, точная
структура которого неизвестна при создании программы.
В Аде статическая коммутация ограничена явным указанием имен входов
задач.
5. Нет адекватной абстракции вида рандеву от процессов-партнеров (ср.
каналы и протоколы Оккама).
Критика Оккама "со стороны Ады"
Основная претензия - бедность "обычных" выразительных средств. Например
1. Нет определяемых программистом типов, нет исключений.
Однако самое интересное - сравнить эти ЯП в той области, для которой
предназначен Оккам.
2. Нет средств динамической коммутации процессов.
Хотя это можно объяснить стремлением к эффективности исполнения (в
частности, стремлением возложить распределение процессов по физическим
процессорам на транслятор), такое ограничение не позволяет работать с
коллективами процессов, структура которых становится известной лишь при
работе программы. Например, нельзя построить несбалансированное дерево
процессов, учитывающее свойства сортируемого потока.
Вопрос. Можно ли это сделать в Аде? Если можно, то как?
Подсказка. Мы совсем недавно занимались динамической коммутацией
процессов средствами Ады.
Таким образом, в Оккаме - высокая степень комфорта при программировании
статических коллективов разнородных процессов. Поэтому типизация обмена
(протоколы) отделена от процессов и связана с каналами. Ориентация на
реальную многопроцессорную аппаратуру с эффективным контролем структуры
программы. Оккамовскую программу можно "спаять" и запустить. И она должна
быть максимально надежной. Для этого и нужны протоколы с квазистатическим
контролем.
17.11. Единая модель временных расчетов
Некоторые существенные проблемы управления асинхронными процессами
остались вне нашего рассмотрения. В качестве примера проблемы, оставшейся
фактически открытой и в Аде, и в Оккаме, назовем проблему управления
временем исполнения процессов.
Суть проблемы в том, что программист должен иметь возможность оценить
время исполнения критичных фрагментов программы и рассчитывать на соблюдение
определенных гарантий в этом отношении. Такие оценки и гарантии должны быть
выражены в терминах, независимых от среды исполнения (точнее, среда должна
заранее предупреждать о невозможности предоставить требуемые программой
гарантии).
Ситуация вполне аналогична управлению численными расчетами, однако
никаких аналогов, касающихся времени исполнения процессов (не только
параллельных), т.е. своего рода "единой модели временных расчетов" ни в Аде,
ни в Оккаме нет, хотя без ее решения программирование систем реального
времени в терминах, независимых от среды исполнения, невозможно. Другими
словами, это критичная технологическая проблема для языка реального времени,
претендующего на достаточно высокий уровень абстракции.
Итак, в очередной раз содержательно работают общие критерии качества
абстракции-конкретизацмм, позволяя прогнозировать появление в перспективе
языковых средств, в совокупности предоставляющих в распоряжение программиста
единую модель временных расчетов.
Подчеркнем еще раз, что дело не столько в самих средствах, позволяющих
узнавать или заказывать допустимые интервалы времени для исполнения
процессов, сколько в гарантии соблюдения заказанных интервалов в любой
реализации ЯП (или обоснованного отказа принять программу к исполнению).
Считаю приятным долгом отметить, что внимание автора к рассмотренной
проблеме было привлечено М.Ж.Грасманисом, занимавшимся проблемами
параллелизма в ЯП под руководством автора в аспирантуре факультета ВМиК МГУ.
С другой стороны, приведенная формулировка проблемы, аналогия с моделью
числовых расчетов и соответствующий прогноз принадлежат автору.
17.12. Моделирование каналов средствами Ады (динамическое моделирование
средств Оккама).
С учетом критики решения из п.17.9 изложим решение задачи о
преобразовании координат, опирающееся на динамическое моделирование
соответствующей Оккам-программы средствами Ады. Преимущество такого решения
- ясность и адекватность сути параллелизма. Наиболее очевидный недостаток -
появление дополнительных процессов по сравнению с решением из 17.9.
Ключевая идея. Ввести задачный тип "канал" в качестве активного
мастера-посредника между "рабочими" процессами нашей программы с тем, чтобы
все рабочие процессы стали равноправными клиентами каналов.
Во-первых, отпадет надобность в заказах рандеву с процессами разных
типов. Во-вторых, отпадет надобность различать рандеву сверху-справа (как
активные) и слева-снизу (пассивные) - все рандеву рабочих процессов
становятся активными. (Кроме настройки! Почему?).
Схема решения на Аде:
1. Создаются коллективы процессов типа "канал". Для связи с ними
используются массивы ссылок соответствующего типа. Каждый канал служит для
связываня ровно двух процессов (как в Оккаме).
2. Создаются в нужном количестве процессы типов pa, px, py, pb, p0 и
посредством рандеву-настройки с основным запускающим процессом настраиваются
на соответствующий канал.
package координаты_2 is
n : constant integer := 3;
task type канал ;
type на_канал is access канал;
task type канал is
entry ввод (X : in real);
entry вывод (X : out real);
end канал;
верх_низ : array(1..n+1, 1..n) of на_канал;
право_лево : array(1..n, 1..n+1) of на_канал;
task type pa is
entry настройка (a : in real; сверху, справа, снизу,
слева : in на_канал);
end pa;
task type px is
entry настройка (j : in integer; снизу : in на_канал);
end px;
. . . -- аналогично для py, p0, pb
end координаты_2;
package body координаты_2 is
task body pa is
aij, xj, yi, aij_xj : real;
наверх, направо, вниз, влево : на_канал;
begin
accept настройка (a :in real; сверху, справа, снизу,
слева :in на_канал) do
aij := a; наверх := сверху; направо := справа;
вниз := снизу; влево := слева;
-- присваивать каналы нельзя (почему?)
-- приходится работать со ссылками на каналы
end настройка;
. . .
наверх.ввод(xj); --- верх ? xj
. . .
направо.ввод(yi); --- право ? yi
. . .
вниз.вывод(xj); --- низ ! xj
. . .
влево.вывод(yi); --- лево ! yi
. . .
end pa;
для_pa : array(1..n, 1..n) of pa;
-- процессы pa объявлены статически! Почему так можно?
. . . аналогично для px, py, pb, p0
begin -- начало активного тела пакета
-- все "рабочие" процессы запущены и ждут настройки,
-- но каналов еще нет!
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
