Инфологическое обеспечение | Когнитивное | Графит-букварь
Стр. 1 2 3 4 5 6 7 8 9 10 11 12
Содержание
Понятие о параллелизме и многозадачности. Виопы взаимодействия процессов
Понятие о параллелизме и многозадачности. Виопы взаимодействия процессов
Важный вопрос информатического моделирования – как отразить протекание многих процессов одновременно? Введём следующие понятия:
Параллелизм – существование в ходе решения одной задачи двух и более алгоритмов одновременно (в том смысле, что при выполнении очередного шага некоего алгоритма имеется по крайней мере ещё один алгоритм, решающий ту же задачу и не достигший конечного состояния); выполнение одного алгоритма может влиять на выполнение других.
Многозадачность – выполнение одним исполнителем двух и более алгоритмов (в том смысле, что возможно выполнить – последовательно или одновременно – очередные шаги для заданного числа алгоритмов, не достигших конечного состояния).
Если параллелизм есть свойство содержания задачи, то многозадачность (для информашин – мультипрограммность) – исключительно свойство исполнителя; алгоритмы не обязательно относятся к одной задаче.
Одну и ту же задачу часто можно решать и последовательно, и параллельно, причём это м.б. формализовано как ещё на математической стадии (получаем разные матмодели), так и уже на информатической стадии (одна матмодель приводит к разным алгомоделям).
Мультипрограммность в информашинах в первую очередь реализуется как последовательная (квазиодновременная) – машина в состоянии выполнить один или несколько шагов (операторов) то для одного, то для другого алгоритма; одновременная достигается за счёт особой реализации исполнителя – мультипроцессорной (напр. так устроены т.н. многоядерные микропроцессоры современных «персоналок») либо многомашинной (напр. при распределённом решении задачи в вычислительной сети). Переход машины между алгоритмами (т.н. переключение процессов) происходит подобно тому, как описано для вызова вставки, только здесь выделяется системный алгоритм (целью которого является не решение к.-л. задачи, а управление выполнением других алгоритмов); он и является вызывающим для алгоритмов, решающих задачи (как целевые, так и служебные); на уровне командных моделей (программного кода) этот алгоритм формализован как основа управляющей программы (ОС) информашины.
Параллельное решение всегда визуализируется как дракон-модель; в этом случае визуалы связаны отношением обмена данными в процессе выполнения. Ясно, что для решения нужен как минимум квазиодновременный исполнитель.
В техноязыке по исходному определению параллелизм визуализируется виопом Параллельный процесс , понимаемой как однонаправленный обмен данными между двумя визуалами по инициативе визуала-источника данных (в связи с этим в Д2М-редакции оператор переименован и имеет индекс Д25; см. п/п 3.5.1.1 Приложения 2). Явная форма предполагает, что один процесс передаёт другому управляющие сообщения, в первую очередь о пуске или останове, - возможно, с некими аргументами (напр., исходными данными, установками режима); на некоторые из них другой процесс должен ответить (скажем, переслать результаты своей работы или сообщить своё состояние).
Можно запускать несколько копий одного визуала как отдельные процессы; каждая будет работать со своими экземплярами величин и выдавать независимые результаты (для одинаковых или различных исходных данных).
Оператор Параллельный процесс в общем может использоваться по-разному. Кроме явного управления другим визуалом, можно принять соглашение, что визуал (очередная его копия) запускается при получении входного объекта из числа обрабатываемых им, а останавливается, когда им выработан выходной объект (и передан адресату либо сохранён в установленном месте), т.о. имеем неявный пуск и останов.
В любом случае виоп Д25 с сообщением Пуск визуализирует оператор, в текстовом виде обычно называемый fork, а с сообщением Останов – оператор join. Передача других сообщений соответствует оператору send.
Многозадачность (конкретно – N-задачность) визуализируется как дракон-модель из (N+1) головных визуалов, первый из которых системный, остальные решают каждый свою задачу (причём возможно, что решение включает параллельные процессы). Системный визуал должен вызываться первым, а завершаться последним; в информашине он может также иметь особые возможности выполнения (т.н. привилегированный режим) в виде недоступных остальным ресурсов исполнителя: команд процессора, областей памяти, внешних устройств.
Ресурсы реального исполнителя всегда ограничены, и одновременно выполняемые процессы принципиально могут конфликтовать из-за них; то же возможно и для квазиодновременного выполнения (в частности, какие-то операции в интересах одних процессов могут длиться дольше, чем допустимо для других). При многозадачности конфликты обнаруживает и разрешает системный алгоритм (процесс), используя механизмы координации выполнения, такие как семафоры или замки; в случае чистого параллелизма (когда среди выполняемых алгоритмов нет системного) в состав всех параллельных алгоритмов включаются элементы этих механизмов (разумеется, единообразные и взаимодействующие); детали их реализации относятся к системному программированию и здесь неважны (в информашине обычно координацию осуществляет управляющая программа).
С т. зр. теории параллельных процессов виоп Д25 реализует механизм т.н. рандеву – передачи/приёма сообщений через логический канал связи процессов «один к одному» (или «один адресат ко многим источникам»). Поэтому название виопа м.б. логично изменить, напр. на Сообщение процессу.
Принято, что в случае рандеву указывается как операция посылки сообщения, так и операция приёма. Поэтому логично будет дополнить алфавит ДРАКОН-2 виопом Сообщение от процесса, результат которой – значения перечисленных величин либо пустое значение (если к моменту выполнения нужные значения ещё не отправлены процессом-адресатом).
Введём такой виоп (Приход на рандеву под индексом Д26; см. п. 3.5.3 Приложения 2); он располагается в визуале процесса-адресата виопа Д25. С отправки сообщения и до получения этого сообщения адресатом процесс-источник приостанавливается; если процесс-адресат дошёл до своего виопа (Д26) раньше, то приостанавливается он.
Ещё один вопрос – как устанавливать соответствие между отправкой и получением сообщений? Ориентироваться на тождество содержания сообщений при отправке и получении (списков величин) нельзя – обмен одинаковыми сообщениями возможен неоднократно и возникнет неопределённость.
Можно индексировать сообщения в пределах модели номерами или литерами (строками); совпадение индекса в иконах Д25 и Д26 означает, что это одно и то же «рандеву». В параллельном программировании обычно говорят, что для рандеву открыт логический канал (связь) под этим индексом; по получении сообщения канал считается закрытым.
Канал может содержать память сообщений. В этом случае возможно асинхронное взаимодействие связанных им процессов: отправка сообщений источником возможна, даже если предыдущие сообщения ещё не приняты адресатом; они накапливаются в памяти. Такой канал всегда определяется как двухточечный («один к одному»).
Если канал не имеет памяти, он является синхронным. В этом случае допустима связь «один источник-много адресатов».
В случае, если одно и то же содержание посылается в разных сообщениях, индексы связей необходимы; однако они будут нелишними и при однократных посылках, облегчая читателю нахождение связи между источником и адресатом (тем более – адресатами).
В частном случае выполнение одного процесса не влияет на выполнение других; тогда говорят о независимости этих процессов. Независимые процессы можно выполнять в любом временном порядке – как последовательно, так и параллельно. Необходимое условие независимости алгопроцессов – отсутствие общих величин, т.н. несцепление по данным.
Чаще рассматривают зависимые процессы, образующие систему. Зависимость возникает за счёт:
вызова/завершения одних процессов другими;
межпроцессного обмена сообщениями, как указано выше;
наличия в том или ином процессе т.н. разделяемых объектов (переменных), доступных для операций, входящих в другие процессы;
ввода/вывода (если адресат/источник этих операций рассматривается как совместно протекающий процесс).
Очевидно, что исполнение каждого оператора (визуального ли, текстового – неважно) в записи алгоритма связано с элементарным переходом от текущего состояния алгопроцесса к следующему. При алгоритмизации сочинитель выделяет операторы вполне произвольно (прежде всего это касается действий); однако с т. зр. на алгоритм как часть системы взаимодействующих алгоритмов структурирование его на операторы должно подчиняться некоторым правилам.
Любой переход по маршруту исполнения алгоритма должен представлять такое изменение состояния, которое является неделимым, мгновенным с т. зр. внешней среды. Оператор, вызывающий такой переход, называется атомарным.
Атомарность м.б. определена только относительно другого процесса или внешнего наблюдателя. Любая совокупность операций (визуализируемая как простой шампур-блок либо маршрут сложного шампур-блока) атомарна, если не подразумевает взаимодействия с внешней средой алгоритма, как-то:
обращения извне к переменным алгоритма (разделяемым);
посылки/приёма сообщений другим процессам;
ввода/вывода значений;
обращения к разделяемым переменным других алгоритмов.
С этим связана возможность т.н. атомизации – объявления границ атомарного фрагмента, удовлетворяющего названным условиям; для целей моделирования систем этот фрагмент считается одним оператором, и значит, ему соответствует один переход (включающий изменения состояния, вызванные всеми операторами фрагмента); тем самым модель упрощается.
Как построить виопы взаимодействия с процессами? Это связано с общим представлением о визуальном соотношении исполнителя визуала и иных импер-сущностей (см. п. Смысл и графика виопов).
Вновь применим метафору «исполнитель как вертикаль», описанную в п. Смысл и графика виопов. И тут у нас получится, что виоп Параллельный процесс указывает туда же, куда виопы ввода/вывода; кроме того, оба её поля одинаковы по форме, т.е. не используется возможность визуального кодирования по этому признаку.
Для представления взаимодействия с другими исполняемыми процессами будет корректно представить взаимодействующий процесс уже как вертикаль слева от вертикали рассматриваемого визуала. И одно из полей также д.б. смещено уже влево на эту вертикаль – отражая взаимодействие с процессом данного вида.
Сдвинутое (влево) направленное поле нужно также сделать непрямоугольным – чтобы указывать направление сообщения аналогично вводу/выводу, но уже на вертикаль слева от шампура (а для парной виопы – от неё). Для дополнительного отграничения от ввода/вывода выберем и иную форму направленных полей – не плавную, а «рубленую».
Теперь о порядке полей.
В виопе Сообщение процессу порядок полей таков: в верхнем будет содержаться источник сообщения другому процессу, а в нижнем – имя этого процесса. Исходя из этого пишется текст поля.
В виопе Сообщение от процесса порядок полей обратный сообразно порядку событий при её исполнении.
Кроме того, взаимодействие процессов м.б. и неявным, когда нет особого действия по отправке сообщения. Явность/неявность не зависит от того, является ли дракон-модель задачи руководством (системой дракон-инструкции и дракон-программы; см. технологию визуализации в Разд.4).
Неявные сообщения процессу показаны как варианты виопов с изменённой формой направленного поля.
Новая форма зрительно выделяет неявное сообщение по сравнению с явным за счёт большего числа углов контура и наличия острых углов в «ласточкином хвосте». Впрочем, и если принять противоположный формат визуализации неявного/явного рандеву, то для него тоже можно подобрать убедительное обоснование – явное сообщение представлено как «разъёмное соединение» виопов Д20,21 через «ласточкин хвост», а неявное не имеет очевидной зрительной «стыкуемости».
Визуальный синтаксис этого оператора требует уточнения также в части записи действия и порождаемого им сообщения. Показаны два возможных варианта:
с записью их в одном поле, но на разных строках;
с разнесением их по разным полям, как для оператора вывода-сообщения выше (только размещённым как в виопе Полка).
По-видимому, второй вариант нагляднее, но окончательное решение, пожалуй, имеет смысл принять после обсуждения.
Возникает также вопрос: как визуализировать выдачу сообщения через внешнюю среду (напр. от косавта к человеку)?
В классическом ДРАКОНе-2 есть отдельные операторы сообщения процессу и вывода. Можно записать цепочку из вывода величин и сообщения тех же величин процессу-адресату. Однако это не соответствует сущности взаимодействия в данном случае – получается, что мы используем одни и те же программно-доступные элементы как источники двух разных операторов, а реально-то действие совершается одно и то же. Можно использовать в операторе сообщения результат оператора вывода, но это опять не то – получается, что сигналы с выхода устройства вывода трактуются как ПДЭ, а на самом деле эти сигналы программно недоступны – у нас есть только ПДЭ на входе устройства вывода (порт, значение в котором преобразуются в состояние выходов устройства).
В чём причина затруднения? Дело в том, что классический синтаксис сообщений процессу соответствует визуализации взаимодействия только между однородными по реализации исполнителями, связанными через ПДЭ (напр. общую память машин); в этом случае можно трактовать посылку/приём межпроцессного сообщения отдельно от ввода/вывода. Здесь же имеем связь через внешнюю среду, и факт вывода данных исполнителем процесса-источника одновременно означает и посылку сообщения исполнителю процесса-адресата.
Каково же решение? Возможный вариант – сконструировать новый тип оператора вывода-сообщения . Для этого включим нижнее поле виопа Д20 (модифицированное по форме) в вершину Д14 (модифицированную по порядку полей) в качестве нижнего (под вторым полем). Т.о. показывается, что вывод во внешнюю среду и есть посылка сообщения другому процессу.
При организации графики данных виопов приписывание поля рандеву к вершине отражает логику исполнения виопа.
Понятно, что теоретически возможен и совмещённый ввод-приём сообщения процессом-адресатом; для его визуализации в алфавит включается парная виоп (оператор ввода-сообщения).
Направленные (непрямоугольные) поля ввода/вывода и сообщения, сдвинутые в противоположные стороны от шампура, должны пониматься как единое событие исполнения – обмен со взаимодействующим процессом через внешнюю среду.
Чтобы порядок виопов по алфавиту был логичным, понадобилось перенумеровать виопы, следующие за Д20.
Реиндексирование исходного алфавита проводилось из условия минимального охвата существующих позиций. До начала следующего десятка индексов (который целесообразно использовать для возможных расширений с существенно иной семантикой) остаётся один индекс, но введение ещё одной элементарной вершины, похожей на предыдущие, пока не предвидится.
Комбинированные вершины обозначены сложным индексом, включающим номера производящих виопов через дробь. Отметим, что они не являются макроиконами – это единые операторы.
Здесь также отсутствует «управляющая полка», введённая ранее по определению в /1, Гл.11/ – на сегодня очевидно, что это дублирование оператора вывода на линии связи с объектом.
В связи со сказанным виоп Параллельный процесс переименован и имеет иную графику; также введены новые виопы взаимодействия:
Здесь (как и ранее и в дальнейшем) линия-«отводок» влево указывает возможность бокового присоединения виопа Синхронизатор, о котором см. в следующем пункте.
Видно, что присоединение не определено для операторов прихода на рандеву; этим подразумевается, что момент исполнения любого из них определяется только получением соответствующего сообщения.
Если допустить присоединение синхронизатора, то момент исполнения также будет определяться по таймеру (т.е. сообщение, полученное до момента по таймеру, извлекается из канала только по достижении этого момента). Возможно, в каких-то задачах это будет иметь смысл, что также требует и математического анализа.
В начало страницы | Оглавление | Версия для печати
Copyright © Жаринов В.Н.
