Это новый вариантГлава 14
ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ
§1. ВВЕДЕНИЕПараллельные процессы играют важную роль в технике и многих других областях.
Определение параллельного процесса дано на рис. 147. Икона «параллельный процесс» показана на рис. 17, фигура И20.
Краткое описание процесса дано в §11 главы 13 (см. также рис. 144).
В данной главе следующие выражения рассматриваются как синонимы:
• параллельный процесс;
• процесс;
• параллельный алгоритм.
§2. ПАРАЛЛЕЛЬНЫЕ ПРОЦЕССЫ
В АЛГОРИТМЕ «ПРОВЕРКА АГРЕГАТА И РАКЕТЫ»На рис. 149 изображены 15 параллельных процессов:
• вызывающий алгоритм ПРОВЕРКА АГРЕГАТА И РАКЕТЫ;
• 14 вызываемых алгоритмов, каждый из которых обозначен иконой «параллельный процесс» (7 алгоритмов в первой ветке и 7 — во второй).
Все вызываемые процессы запускаются сигналом ПУСК. Момент запуска точно определен оператором синхронизатор. Например, процесс КОНТРОЛЬ ПРИБОРОВ запускается в момент 103с (103 секунды).
Параллельные процессы могут заканчиваться двумя способами:
• по команде «Останов» (см. пример на рис. 144, правая ветка);
• без использования команды «Останов», то есть естественным путем, когда каждый процесс решит свою задачу и достигнет конца.
На рис. 149 показан случай, когда все вызываемые процессы заканчиваются естественным путем. Поэтому команда ОСТАНОВ не используется.
Вложение:
Рис._149_png_Агрегат_и_ракета.png [ 74.66 КБ | Просмотров: 17123 ]
§3. ВРЕМЕННАЯ ДИАГРАММА ПАРАЛЛЕЛЬНЫХ ПРОЦЕССОВНа рис. 150 показана временная диаграмма, иллюстрирующая алгоритм на рис. 149. В верхней строке темным цветом выделен вызывающий алгоритм. Он имеет самую большую длительность. Ниже расположены вызываемые процессы.
В самом верху указано время запуска всех процессов по таймеру. Процессы имеют разную длительность, потому что каждый процесс выполняет задачу за разное время.
Вложение:
Рис._150_png_Циклограмма.png [ 55.41 КБ | Просмотров: 17123 ]
§4. ПАРАЛЛЕЛЬНЫЕ ПРОЦЕССЫ
В АЛГОРИТМЕ «ПРОВЕРКА ВОЗДУШНОГО СНАЙПЕРА»На рис. 149 показан упрощенный случай. Одна и та же операция повторяется 14 раз. 14 синхронизаторов задают 14 моментов времени, определяющих запуск 14 параллельных процессов.
На рис. 151 показан более сложный случай. Наряду с таймером, синхронизатором и процессами применяются следующие иконы: вывод, вставка, вопрос и полка.
В первой ветке имеются 4 синхронизатора. Два из них запускают процессы ЗАПРАВКА УСКОРИТЕЛЯ и АННИГИЛЯЦИЯ КВАРКОВ. Третий включает процедуру ЗАЩИТА НЕБЕСНОГО ЭКРАНА. Четвертый выдает команду НЕЙТРОННЫЙ ЗАЛП.
Используются не только синхронизаторы, но и две паузы длительностью 5 секунд каждая. Первая пауза задерживает пуск процесса ЗАЩИТА АТОМНЫХ ЯДЕР. Вторая задерживает выдачу команды БЛОКИРОВКА ШИФРА.
Во второй ветке выполняются операции:
• через синхронизатор (момент 319 секунд по таймеру) запускается процесс РАСКРУТКА ЭЛЕКТРОНОВ;
• устанавливаются два признака НЕТ НОРМЫ и ВКЛЮЧЕН РЕВЕРС;
• применяются две иконы вопрос: ПЕРЕХОД НА МАЛУЮ ТЯГУ? и КОНТРОЛЬ УРОВНЯ?
• выдается команда ВКЛЮЧИТЬ КАРУСЕЛЬ;
• запускается процесс ДЕРЖАТЬ УРОВЕНЬ;
• и т.д.
Подведем итоги. В данном алгоритме — наряду с другими операторами — используются пять вызываемых параллельных процессов. В первой ветке (через синхронизаторы) запускаются два процесса. Во второй ветке применяются три процесса. Один запускается через синхронизатор. Второй — через иконы пауза и вопрос. Третий — через более сложную схему.
Вложение:
Рис._151_Воздушный_снайпер_png_.png [ 72.77 КБ | Просмотров: 17123 ]
§5. КОМАНДЫ УПРАВЛЕНИЯ ПАРАЛЛЕЛЬНЫМИ ПРОЦЕССАМИКоманды управления пишут на верхнем этаже иконы «параллельный процесс».
Ниже представлен перечень команд управления:
• ПУСК — осуществляет пуск параллельного процесса;
• ОСТАНОВ — осуществляет останов параллельного процесса;
• СТОП — осуществляет приостановку запущенного параллельного про-цесса;
• РЕСТАРТ осуществляет повторный пуск приостановленного парал-лельного процесса.
§6. АЛЬТЕРНАТИВНЫЙ СПОСОБ ИЗОБРАЖЕНИЯ
ПАРАЛЛЕЛЬНЫХ ПРОЦЕССОВНа рис. 152 показан алгоритм «Последний этап строительства дома». Можно сказать, что этот алгоритм нарисован «на другом языке». Вводятся новые обозначения и правила.
1. Жирная горизонтальная линия обозначает начало нескольких параллельных процессов.
2. Треугольник означает, что происходит прием сигналов от N параллельных процессов и их обработка.
3. Сигнал на выходе треугольника появится только тогда, когда:
• на входы треугольника поступят (не обязательно одновременно) N процессов;
• каждый из N процессов не только начнется, но и закончится. Иначе говоря, выходной сигнал треугольника возникнет в тот момент, когда завершится последний из N процессов;
4. Выходной сигнал треугольника разрешает выполнение действия, находящегося после треугольника.
Рассмотрим детали алгоритма.
На рис. 152 изображены три жирных линии. Каждая из них символизирует начало параллельных процессов.
Верхняя жирная линия обозначает начало четырех процессов:
• Подводка электролинии.
• Закупка электропроводов.
• Монтаж электрощита.
• Закупка водопроводных труб.
Средняя жирная линия указывает на начало следующих процессов:
• Прокладка электропроводки.
• Устройство крыши.
• Установка окон.
• Прокладка водопровода.
Нижняя жирная линия «начинает» процессы:
• Установка электроламп.
• Отделочные работы.
На рис. 152 показаны 4 треугольника:
Левый верхний треугольник выполняет две функции:
• контролирует три процесса и дожидается, когда кончится последний из них;
• разрешает начать действие «Прокладка электропроводки».
Можно сказать иначе. Прокладка электропроводки начнется только после того, как закончатся процессы:
• Подводка электролинии.
• Закупка электропроводов.
• Монтаж электрощита.
Правый верхний треугольник выполняет две функции:
• контролирует два процесса и дожидается, когда кончится последний из них;
• разрешает начать действие «Прокладка водопровода».
Другими словами, «Прокладка водопровода» начнется лишь тогда, когда закончатся процессы:
• Монтаж электрощита.
• Закупка водопроводных труб.
Оставшиеся два треугольника работают аналогично.
Вложение:
Рис._152_png Конец стройки.png [ 44.71 КБ | Просмотров: 17121 ]
§7. ВРЕМЕННАЯ ДИАГРАММА
ПАРАЛЛЕЛЬНЫХ ПРОЦЕССОВ ПРИ СТРОИТЕЛЬСТВЕ ДОМАЦиклограмма процесса «Последний этап строительства дома» показана на рис. 153.
Вспомним, что на вход левого верхнего треугольника (рис. 152) поступают сигналы трех процессов:
• Подводка электролинии.
• Закупка электропроводов.
• Монтаж электрощита.
На циклограмме изображен частный случай, когда названные три процесса:
• не пересекаются;
• расположены в таком порядке: 1) Закупка…2) Подводка… 3) Монтаж…
В этом случае окончание процесса «Монтаж электрощита» разрешает начать процесс «Прокладка электропроводки», как показано на рис. 153.
Вложение:
Рис._153_Циклограмма_png.png [ 73.84 КБ | Просмотров: 17123 ]
§8. ОБРАБОТКА ИНФОРМАЦИИ,
ВЫПОЛНЯЕМАЯ СХЕМОЙ «ТРЕУГОЛЬНИК»Уже говорилось, что любой треугольник на рис. 152 выполняет операции по обработке информации. О каких операциях идет речь?
Выделим на рис. 152 фрагмент, содержащий левый верхний треугольник и присоединенные к нему процессы. Поместим этот фрагмент на рис. 154 и исследуем его.
Алгоритм, реализуемый треугольником, показан на рис. 155. Он состоит из двух веток. Первая ветка проверяет, что все три входных процесса НАЧАЛИ работать. Вторая — что все входные процессы КОНЧИЛИ работу.
Рассмотрим первую ветку. Три процесса могут образовать 6 комбинаций (перестановок). Перечислим все 6 комбинаций.
1) Подводка… линии. 2) Закупка… проводов. 3) Монтаж… щита.
1) Подводка… линии. 3) Монтаж… щита. 2) Закупка… проводов.
2) Закупка… проводов. 1) Подводка… линии. 3) Монтаж… щита.
2) Закупка… проводов. 3) Монтаж… щита. 1) Подводка… линии.
3) Монтаж… щита. 1) Подводка… линии. 2) Закупка… проводов.
3) Монтаж… щита. 2) Закупка… проводов. 1) Подводка… линии.
Первая ветка разветвляется на 6 маршрутов. Каждый маршрут описывает одну из 6 комбинаций. Вторая ветка имеет точно такую же структуру.
В начале первой ветки имеется цикл ЖДАТЬ. В исходном положении все три процесса не работают. Цикл ЖДАТЬ поочередно опрашивает эти процессы. И определяет, какой процесс ПЕРВЫМ начнет работать (рис. 155).
Предположим, что первым включился в работу процесс «Монтаж электрощита». Из иконы вопрос «Монтаж…» выходим через «да» и попадаем в следующий цикл ЖДАТЬ. Этот цикл поочередно опрашивает ДВА процесса (Подводка… линии. Закупка… проводов). И определяет, какой из них ПЕРВЫМ начнет работать (рис. 155).
Предположим, первым начал работу процесс «Закупка электропроводов». Из иконы вопрос «Закупка …» выходим через «да» и попадаем в следующий цикл ЖДАТЬ. Этот цикл периодически опрашивает ОДИН процесса (Подводка электролинии). И «терпеливо» ждет, когда он вступит в работу (рис. 155).
Когда ожидание увенчается успехом, из иконы вопрос «Подводка электролинии» выходим через «да». Это означает, что мы прошли первую ветку по маршруту:
Монтаж… щита. Закупка… проводов. Подводка… линии.
В этот момент можно констатировать, что эти три процесса работали или работают. Возможно, некоторые из них уже кончили работу. Но можно с уверенностью сказать, что процесс «Подводка электролинии» продолжает работать.
После этого переходим ко второй ветке алгоритма. Задача второй ветки — определить, что все три процесса закончили работу.
Вторая ветка работает, как первая. Только надписи «да» и «нет» всюду меняются местами.
В начале второй ветки имеется цикл ЖДАТЬ. В исходном положении, по крайней мере, один процесс работает. Однако, может быть и так, что все три процесса продолжают работать. Цикл ЖДАТЬ поочередно опрашивает три процесса и определяет, какой процесс первым кончит работать (рис. 155).
Предположим, что первым кончил работу процесс «Закупка электропроводов». Из иконы вопрос «Закупка …» выходим через «нет» и попадаем в следующий цикл ЖДАТЬ. Этот цикл поочередно опрашивает ДВА процесса (Подводка… линии. Монтаж… щита). И определяет, какой из них первым кончит работать (рис. 155).
Дальше вторая ветка работает аналогично первой. Когда вторая ветка определит, что три процесса закончились (см. точку Z на рис. 155), производится Пуск процесса «Прокладка электропроводки».
На этом алгоритм завершается.
В схеме на рис. 155 используются 20 циклов ЖДАТЬ. Для простоты икона «период» не показана.
Вложение:
Рис._154_png Фрагмент конца стройки.png [ 76.88 КБ | Просмотров: 17121 ]
Вложение:
Рис._155_png.png [ 104.81 КБ | Просмотров: 17095 ]
§9. РАЗДЕЛЕНИЕ И СЛИЯНИЕ ПРОЦЕССОВПункт разделения (concurrent fork) обозначает разделение одного процесса на несколько параллельных процессов (то есть разделение одного маршрута на несколько параллельных маршрутов). На рис. 154 пункт разделения обозначен жирной линией.
Пункт слияния (concurrent join) обозначает слияние параллельных процессов в один процесс (то есть слияние несколько параллельных маршрутов в один маршрут). На рис. 154 пункт слияния обозначен треугольником.
Таким образом, на рис. 154 пункт разделения и пункт слияния имеют разные обозначения.
Зачем нужны разные обозначения? Чтобы подчеркнуть, что в пункте слияния (в треугольнике) производится сложная обработка информации.
Всегда ли нужно это подчеркивать? Нет, не всегда.
Бывают случаи (и их немало), когда акцент на обработке информации в треугольнике является неуместным. В такой ситуации целесообразно убрать треугольник. И ввести ЕДИНОЕ обозначение (жирная горизонтальная линия) и для пункта разделения, и для пункта слияния.
Пример показан на рис. 155а.
Если удалить треугольники на рис. 152, получим рис. 155б.
Нетрудно заметить, что удаление треугольников упрощает схему и устраняет лишние изломы линий. Поэтому рис. 155б является более четким, чем рис. 152.
Вложение:
Рис._155а_png_Фрагмент конца стройки Без_треугольника.png [ 80.97 КБ | Просмотров: 17120 ]
Вложение:
Рис._155б_png_Конец_стройки_Без треугольника.png [ 43.86 КБ | Просмотров: 17120 ]
§10. НЕДОСТАТОК РИСУНКА 155аНа рис. 155а имеются две совершенно одинаковые жирные линии: верхняя и нижняя. Это обстоятельство скрывает от читателя тот факт, что эти линии выполняют принципиально разные функции:
• верхняя линия выполняет простейшую функцию, символизируя начало параллельных процессов;
• нижняя линия, напротив, выполняет очень сложную функцию. Она реализует алгоритм обработки информации, показанный на рис. 155.
Отсюда проистекает вывод. Если необходимо сделать акцент на обработке информации, надо пункт слияния изображать в виде треугольника, как на рис. 154. Если же такой акцент не нужен, треугольник следует убрать. И рис. 154 заменить на рис. 155а.
§11. СРАВНЕНИЕ ЯЗЫКОВВ данной книге все алгоритмы нарисованы на языке ДРАКОН. Но в этой главе (§§6, 7, 9, 10) мы отошли от этого принципа. При описании строительства дома использован другой язык (назовем его «язык Z». Последний значительно удобнее для изображения параллельных процессов типа «строительство дома».
В §8 мы снова вернулись к ДРАКОНу. Потому что язык Z принципиально не может описать обработку информации в схеме треугольника. А язык ДРАКОН решает эту задачу точно и подробно.
Общий вывод таков. Для разных задач нужны разные языки. В тех случаях, когда детали не нужны, когда требуется укрупненное и наглядное описание параллельных процессов, в некоторых случаях (но, разумеется, не всегда) язык Z оказывается более удобным.
Здесь нет противоречия. Язык ДРАКОН можно расширить, включив в его состав элементы языка Z.
§12. ВЫВОДЫ1. На языке ДРАКОН параллельный процесс запускается командой Пуск.
2. На языке ДРАКОН параллельные процессы могут заканчиваться двумя способами:
• командой Останов;
• без использования команды Останов, когда каждый процесс выполнит свою задачу и достигнет конца.
3. Рассмотрен альтернативный способ изображения параллельных процессов с помощью языка Z.
4. Язык Z — это условное название для различных нотаций, обозначающих пункты разделения параллельных процессов (concurrent fork) и пункты слияния параллельных процессов (concurrent join).
5. Указанные нотации включают жирные линии и треугольник.
6. На языке Z начало нескольких параллельных процессов обозначается жирной линией.
7. На языке Z конец параллельных процессов обозначается:
• либо треугольником (если нужно подчеркнуть, что в треугольнике выполняется сложная обработка информации);
• либо жирной линией (если акцент на обработке информации не ставится).
8. Выходной сигнал треугольника возникает в тот момент, когда завершится последний из N параллельных процессов.
9. Завершение всех процессов на входе треугольника позволяет выполнить действие на его выходе.
10. Схема Треугольник выполняет обработку информации по сложному алгоритму. Этот алгоритм нельзя описать на языке Z, но можно описать на языке ДРАКОН.
11. Для разных задач нужны разные языки. В тех случаях, когда детали не нужны, когда требуется укрупненное и наглядное описание параллельных процессов, в некоторых случаях язык Z оказывается более удобным.
12. Язык ДРАКОН целесообразно расширить и включить в его состав графоэлементы языка Z.