3.2. Средства описания параллелизма
Средства, которые могут быть использованы для описания параллелизма в программах, можно разделить на два вида: графические и языковые.
3.2.1. Графические средства
К графическим средствам относятся:
1. ГОСТ «Схемы алгоритмов, программ, данных и систем»
2. SDL-диаграммы
3. UML-диаграммы
4. графы
Графические средства представлены ГОСТ, который называется «Схемы алгоритмов, программ, данных и систем». В этом ГОСТе есть пункт, называемый «Параллельные действия».
В этом пункте есть следующие примеры:
1) Синхронизация двух или более параллельных операций
2
)
В данной схеме C, D, E начинаются только после завершения A, а F начинается только после завершения B, C, D.
В другом пункте есть значок - символ передачи управления от одного процесса к другому.
3.2.2. Языковые средства описания параллелизма
В традиционно используемых языках программирования средства описания параллелизма отсутствуют, т.к. эти языки изначально создавались для последовательного программирования. Исторически существовали два языка, в которых средства описания параллелизма присутствовали как стандартные.
В языке АДА существует следующее средство - если описать некоторые программные единицы как задачи - TASK, то с момента начала выполнения всей программы эти единицы начнут выполняться параллельно. Т. е. обработчик прерываний и средства замены контекста зашиты в АДЕ на уровне языка. Кроме того, АДА предлагает некоторый механизм взаимодействия задач, который называется РАНДЕВУ, тоже существующий на уровне языка.
В языке МОДУЛА-2, который весь построен на библиотечных модулях в соответствие со своим названием, есть модуль Process, который реализует временное разделение с помощью обработчика прерываний и содержит протокол и набор процедур-примитивов, позволяющий создавать из процедур параллельно выполняемые процессы и организовывать их взаимодействие. Модуль Process предлагает следующие возможные действия:
StartProcess: создать процесс;
StartScheduler: запуск планировщика задач с временным разделением;
StopScheduler: останов планировщика задач;
WAIT: ждать сигнал;
SEND: послать сигнал.
В настоящее время потоки поддерживаются в C++ стандарта 2011 г., который называется С++11.
Современные операционные системы предоставляют примитивы - API, позволяющие реализовывать многозадачность. Эти примитивы отличаются синтаксисом в зависимости от среды и могут трактоваться как расширения языка программирования, в точности соответствуя понятию ВЫЗОВ ПРОЦЕДУРЫ ОС.
Примеры
UNIX-подобные системы
fork() создание нового процесса. Вызывающий процесс дублируется и создается точная его копия, отличающаяся от порождающего процесса только идентификатором.
sleep(sec) приостанов процесса на sec секунд.
exit() завершение вызывающего процесса.
Windows
CreateProcess() создание процесса.
ExitProcess() завершение текущего процесса.
CreateThread() запуск потока.
ExitThread() завершение работы потока.
Sleep(ms) приостанов процесса на ms миллисекунд.
В каждой из перечисленных сред есть еще примитивы для работы с процессами и потоками. Это были только примеры, причем в примерах не приведены передаваемые параметры.
Существует еще набор абстрактных (не относящихся к конкретному языку программирования), но Паскале-подобных языковых конструкций, предложенных Виртом для описания параллелизма, которые мы сейчас и рассмотрим.
Нотация "and" позволяет программисту указывать предложения, которые выполняются параллельно.
Например,
(Уже не Вирт) «fork w» команда, выполненная процессом p, вызывает начало развития нового процесса q с команды, помеченной w. Далее процессы p и q развиваются одновременно.
«quit» - завершение процесса.
«join t, w» вызывает следующие действия:
---------------------
t = t - 1;
if (t == 0) goto w;
---------------------
Цель этой команды - обеспечить синхронизацию процессов, т. е. начать выполнение с метки w только после того как несколько процессов (их число определяет, в какое начальное значение инициализируется t) выполнят команду join. После нее обычно ставится команда quit. Только последний из перечисленных процессов пойдет на метку, остальные завершатся.
Пунктиром отмечен тот факт, что приведенные действия выполняются как неделимые.
Иллюстрация в виде графа
Обозначение по ГОСТ
Описание с помощью вышеприведенных языковых конструкций:
Введем переменные Т1 и Т2.
Т1 = 2; w1: P1; join T2,w5;
T2 = 2; join T1,w4; quit;
P0; quit; w4: P4;
fork w1; w2: P2; join T2,w5;
fork w2; join T1,w4; quit;
fork w3; quit; w5: P5;
quit; w3: P3; quit;
Обратим внимание на требование неделимости действий в команде join. Посмотрим, как правильно должна выполняться эта команда.
Предположим, что t = 2 и оба процесса подошли к выполнению этой команды.
--------------------- ---------------------
t = t - 1; t = t - 1;
if (t == 0) goto w; if (t == 0) goto w;
--------------------- ---------------------
quit; quit;
Если первым подойдет процесс 1, то t станет равным 1 и первый процесс перейдет к выполнению оператора quit без перехода на метку. Второй процесс сделает t, равным 0, и пойдет на метку w. Это так надо, чтобы выполнялось.
Что может произойти, если команда join не будет неделимой. Это значит, что когда первый процесс уменьшит t на 1, управление может передаться второму процессу, который тоже уменьшит t на единицу. После этого первый процесс пойдет на метку w и второй процесс пойдет на метку w, т. к. t = 0 для обоих процессов перед условным оператором. Это неправильно.