Это одна из моих ранних работ по параллельному программированию. Вряд ли она имеет сейчас практическое значение, разве что для тех, кому приходится программировать встроенные микро-эвм, используемые для автоматизации технологических процессов и работающие под управлением MSDOS. Для меня эта работа важна как некоторый завершенный этап, который во многом определил направление моих дальнейших работ.
В статье обсуждаются вопросы параллельного объектно ориентированного программирования на языке С++. Базовое понятие такого подхода - параллельный процесс, рассматриваемый как дальнейшее развитие методов структуризации программ. Изложение материала ведется на основе разработанной автором библиотеки классов 2KLIB (текущая версия 2.04), что позволяет пояснить не только принципиальные моменты, но также и вопросы практической реализации. Статья построена на примерах программ, последовательно вводящих понятия параллельного программирования: процесс, массив процессов, состояния процесса, приоритет, процессы-устройства, взаимодействие и синхронизация процессов, обмен сообщениями, недетерминированное ожидание событий, рандеву.
Библиотека 2KLIB разрабатывалась как средство программирования систем реального времени, представляет собой параллельное расширение языка Си++ и дает программисту набор понятий-классов, позволяющих строить программу в терминах параллельных процессов и их взаимодействий. Программы, написанные с использованием библиотеки, можно транслировать компилятором Borland C++ 3.1 и выполнять на машинах IBM PC под управлением операционной системы MSDOS. Библиотека позволяет в рамках DOS-программы запускать квази-параллельные процессы, разделяющие время процессора. Фактически можно считать, что библиотека предоставляет DOS-программе надстроечную многозадачную операционную среду. Основное понятие библиотеки и базовая единица работы - процесс. Процессы выполняются параллельно и могут взаимодействовать друг с другом, обмениваясь сообщениями. При взаимодействии происходит их синхронизация. Взаимодействие процессов может выполняться через механизм программных каналов, рандеву или посредством разделяемых переменных. Поскольку библиотека создавалась в основном для задач управления аппаратурой систем реального времени, большое внимание уделялось методологии программного определения аппаратуры. В терминах параллельного объектно-ориентированного подхода аппаратные устройства описываются как процессы-классы, наследующие свойства параллельного процесса и взаимодействующие с другими процессами. Под устройствами также понимается все многообразие логических устройств, непосредственно управляющих реальными физическими устройствами. С программной точки зрения устройства можно рассматривать как данные некоторого более или менее сложного типа.
Основная задача управляющих систем реального времени - сбор и обработка данных от физических устройств и управление физическими устройствами. Введение понятия параллельного процесса отражает тот факт, что физические устройства работают в реальном времени параллельно друг с другом и для естественного, адекватного описания их поведения, программные компоненты также должны работать параллельно (по крайней мере, с точки зрения программиста). Использование для этой цели последовательных языков ведет к неадекватному описанию, так как на последовательном языке приходится в рамках одной последовательности увязывать действия устройств в некоторую неестественную логическую временную цепь, хотя сами устройства такими логическими связями не обладают. Поэтому построение программ реального времени на основе параллельных процессов - это такое же мощное средство структуризации, как и введение процедур и функций в последовательных программах. С более общей точки зрения можно считать понятие параллельного процесса развитием понятий процедуры, функции, класса и рассматривать параллельное программирование не только как специфический тип программирования систем реального времени, но и как достаточно общую методологию разработки программного обеспечения.
Начнем с примера простой программы, которая по уже установившейся традиции для языка Си, выводит на экран дисплея текст приветствия и завершается. При описании мы предполагаем, что читатель достаточно хорошо знаком с языком Си++ и основами объектно-ориентированного программирования, поэтому будем рассматривать только те особенности программы, которые связаны с параллельным программированием.
#include <iostream.h> #include "2k.h" void ТСценарий::тело_процесса(void) { cout << "Здравствуй, мир\n"; }
В отличие от обычных программ на Си, начинающих свое выполнение с главной функции main(), программы с использование библиотеки 2KLIB начинаются с выполнения главного процесса (создаваемого исполняющим ядром библиотеки). Главный процесс имеет тип ТСценарий. ТСценарий - это класс, порождаемый от базового абстрактного класса ТПроцесс. Для каждого порождаемого от ТПроцесс класса необходимо переопределить чистую виртуальную функцию тело_процесса(), которая собственно и содержит исполняемый код. В нашем случае в теле процесса выполняется вывод строки в стандартный файл вывода, после чего программа завершается. Определения библиотеки 2KLIB подключаются к программе через файл 2k.h. В дальнейших примерах мы будем, для краткости, опускать указание включаемых файлов.
class Т : public ТПроцесс { public: void тело_процесса(void) { cout << "Параллельный процесс\n"; } }; void ТСценарий::тело_процесса(void) { new Т; cout << "Сценарий\n"; }
В этой программе в теле процесса-сценария создается новый процесс, описываемый классом Т, после чего оба процесса существуют одновременно. Выполнение программы завершится после того, как завершатся оба процесса. В ходе выполнения в стандартный вывод будут направлены строки: "Сценарий" и "Параллельный процесс". Класс Т порождается от базового класса ТПроцесс, наследуя его доступные члены. В классе Т не вводится никаких новых свойств процесса, а только определяется его тело - это самый тривиальный случай определения нового типа процессов. Создается новый процесс оператором new. Это приводит к тому, что выделяется память под контекст процесса и процесс устанавливается в очередь процессов, готовых для выполнения. После завершения процесс удаляется из очереди процессов и затем вызывается его деструктор, освобождая занятую процессом память. В данном примере процесс создается явно и динамически - оператором new, а уничтожается неявно (диспетчером процессов) после завершения тела процесса. Родительский процесс не контролирует завершение дочерних процессов и, после их создания, выполняется независимо, поэтому родственных связей между процессами нет. При создании каждому процессу назначается собственная область стека, размер которой можно указать как аргумент конструктора ТПроцесс. По умолчанию размер стека равен 1 КБайт. Вторым (необязательным) параметром конструктора ТПроцесс является строка имени процесса - она используется только для диагностики ошибок.
class Т : public ТПроцесс { private: int индекс; public: Т(int а_индекс) { индекс = а_индекс; } void тело_процесса(void) { cout << "Параллельный процесс " << индекс << '\n'; } }; void ТСценарий::тело_процесса(void) { for (int i = 1; i <= 300; ++i) new Т(i); }
В этой программе процесс-сценарий создает массив из трехсот параллельных процессов, причем каждый процесс получает при своем создании уникальный индекс. Каждый элемент массива процессов порождается от базового класса ТПроцесс и кроме обязательной функции тело_процесса() имеет конструктор, аргументом которого является индекс процесса в массиве.
class Т : public ТПроцесс { public: void тело_процесса(void); ~Т() { cout << "Уничтожение процесса Т\n"; } }; void Т::тело_процесса(void) { for (;;) { cout << "Параллельный процесс\n"; пауза(100); } } void ТСценарий::тело_процесса(void) { Т* процесс = new Т; пауза(1000); delete процесс; }
В этой программе процесс-сценарий создает параллельный процесс Т, приостанавливается на 1 секунду и затем уничтожает процесс Т. Программа демонстрирует явное динамическое завершение процесса - такое действие используется при естественном завершении циклических процессов или в случае аварийной ситуации. Определение процесса Т имеет деструктор, вызываемый при завершении процесса.
Деструктор процесса используется для выполнения завершающих операций, например, закрытия файла, что гарантирует целостность данных, изменяемых в теле процесса. В случае управления аппаратными устройствами, конструктор должен выполнять все инициализирующие действия (например, начальный сброс), а деструктор - все завершающие действия (например, выключение привода).
Для приостановки текущего (активного) процесса используется глобальная функция пауза(), аргумент которой - время приостановки в миллисекундах. Семантика этой функции состоит в удалении процесса из очереди активных процессов (очередь диспетчера) и перемещении его в очередь ожидания к таймеру. После того, как пройдет заданный интервал времени, процесс будет возвращен в очередь активных процессов и его выполнение будет продолжено. Когда процесс не находится в очереди диспетчера, он выполняет пассивное ожидание, не занимая процессорного времени и предоставляя его другим активным процессам.
Здесь следует отметить, что алгоритм диспетчеризации процессов таков, что процесс выполняется до тех пор, пока самостоятельно не перейдет в состояние ожидания некоторого события (в данном примере - ожидания конца секундного интервала времени). Существуют два принципиально различных подхода к диспетчеризации процессов - первый основан на внутреннем поведении процесса, а второй - на принудительном внешнем ограничении выполнения процесса по времени (квантование времени) или по внешнему событию, например, появлению более приоритетного процесса (алгоритм с вытеснением). Выбор способа диспетчеризации многофакторный, определяется типами процессов (часто весьма разнокачественными) и вряд ли можно сделать совершенно однозначное предпочтение. Мы выбрали первый способ исходя из следующих причин:
Таким образом, активный процесс выполняется до тех пор, пока самостоятельно не перейдет к ожиданию некоторого события. В библиотеке определен ряд операций, вызывающих ожидание различных событий. Наиболее простая - пауза(). Эта перегруженная функция может вызываться с одним аргументом - временем ожидания или без аргументов - в этом случае процесс не удаляется из очереди активных процессов, а остается в ней, но управление передается следующему готовому процессу.
Учитывая принятый способ диспетчеризации параллельных процессов было решено также отказаться от понятия явного приоритета процесса. Это довольно рискованное решение, особенно для систем реального времени, но оно было принято из-за весьма тяжелой реализации явной системы приоритетов, которая, в частности, требует перехода от простых и эффективных очередей типа FIFO (первым пришел - первым обслуживается) к приоритетным очередям, причем как для процессов, так и для межпроцессных сообщений. Вместо явной системы приоритетов вводится понятие неявной системы приоритетов, причем приоритетность закладывается на этапе программирования. Идея состоит в том, чтобы рассматривать приоритет как относительную частоту активизации процесса - приоритет тем выше, чем большее время процесс находится в активном состоянии. Недостатком такого решения является трудность обеспечения быстрой реакции на особо приоритетные процессы, хотя эту трудность можно обойти для наиболее важного случая - активизации процесса по аппаратному прерыванию - в этом случае обработка разделяется на две фазы - быстрое предварительное реагирование в драйвере обслуживания прерывания и последующая дообработка в теле процесса, активизируемого сообщением. Продемонстрируем введение неявных приоритетов на примерах:
// цикл, расположенный в теле высокоприоритетного процесса for (i = 0; i < 1000; ++i) { некоторое_действие(); } // цикл, расположенный в теле процесса со средним приоритетом for (i = 0; i < 1000; ++i) { некоторое_действие(); пауза(); } // цикл, расположенный в теле низкоприоритетного процесса for (i = 0; i < 1000; ++i) { некоторое_действие(); пауза(приоритет); }
В первом примере процесс активен все время, пока выполняется цикл. Во втором примере процесс после каждой итерации отдает процессорное время другим параллельным процессам не уходя при этом из очереди готовых процессов. В третьем примере процесс после каждой итерации уходит в ожидание на время, зависящее от значения переменной 'приоритет'. Изменяя значение этой переменной процесс может изменять частоту активизации - это соответствует понятию динамического приоритета. Отметим, что если переменную 'приоритет' сделать доступной для других процессов, то приоритетом данного процесса можно управлять внешним образом, исходя из некоторого глобального критерия.
Так как динамический процесс может быть завершен в любой момент времени, при выполнении операций с ним необходимо быть уверенным в том, что процесс еще существует. Для реализации такого контроля каждый процесс при создании снабжается уникальной меткой которую можно получить функцией "идентификатор()". Контроль процесса выполняет глобальная логическая функция "существует()", принимающая два параметра - указатель процесса и его идентификатор. Эта функция проверяет целостность внутренней структуры процесса и соответствие его идентификатора. Например:
Т* процесс = new Т; int идентификатор_Т = процесс->идентификатор(); if (существует(процесс, идентификатор_Т)) действие_с_процессом... else восстановительные_действия...
Исполняющее ядро библиотеки всегда контролирует целостность процессов и при попытке доступа к несуществующему процессу аварийно завершает программу с выдачей диагностического сообщения. Естественно, что для систем реального времени такое поведение программы будет недопустимым. Практика надежного программирования динамических процессов состоит в том, что перед операциями доступа к процессу нужно проверять его существование и, в зависимости от существования процесса, выполнять то или иное действие, например, попытку восстановления.
class ТЧасы : public ТПроцесс { public: void тело_процесса(void); }; void ТЧасы::тело_процесса(void) { ТВремя* время; for (;;) { время = текущее_время(); cout << время->час << ':' << время->минута << ':' << время->секунда << '\n'; пауза(1000); } } static ТЧасы часы; void ТСценарий::тело_процесса(void) { пауза(10000); }
В этом примере процесс-сценарий вообще не выполняет никаких полезных действий, а просто приостанавливается на 10 секунд, после чего завершается. Полезную работу выполняет параллельный процесс ТЧасы; это статический процесс, который создается не оператором new, а описанием: "static ТЧасы часы". Это означает, что конструктор такого процесса вызывается до начала программы, а деструктор - после завершения программы. Программа выполняется до тех пор, пока существует хотя бы один динамический параллельный процесс (в данном случае - сценарий). Аргумент функции пауза() фактически и определяет в нашем случае время выполнения программы. Поскольку деструктор статического процесса обязательно вызывается в конце программы, статический процесс не может быть явно уничтожен в ходе программы. Обычно статические процессы содержат в теле оператор бесконечного цикла for(;;).
Статический процесс обеспечивает удобную абстракцию для тех процессов, которые по своей природе бесконечны. Это наиболее приемлемый способ описать процессы, управляющие аппаратными устройствами. В теле процесса "часы" выполняется бесконечный цикл for, в каждой итерации которого процесс запрашивает текущее значение времени и выводит значение времени в стандартный файл вывода. Итерации следуют друг за другом через 1 секунду. Отметим, что значение времени может быть получено также функцией системное_время(), возвращающей время в миллисекундах от старта программы.
class Т : public ТПроцесс { public: ТКанал<int> канал; void тело_процесса(void); }; void Т::тело_процесса(void) { int i; канал >> i; cout << "Принято сообщение " << i << '\n'; } void ТСценарий::тело_процесса(void) { Т* процесс = new Т; int i = 123; процесс->канал << i; }
В этом примере показано взаимодействие двух параллельных процессов: сценарий передает процессу Т сообщение целого типа, а процесс Т принимает его и отображает принятое значение. Обмен сообщениями реализован в библиотеке на основе понятия "канал". Канал - это параметризованный экземпляр класса, порожденного от базового класса ТКанал. Канал формирует собственную очередь сообщений. Сообщения ставятся в очередь в порядке их поступления (дисциплина FIFO). Канал является типизируемой структурой данных - это означает, что тип сообщений, который канал может обрабатывать, явно определен и известен на момент компиляции. Для декларации канала используются шаблоны (templates). Синтаксис декларации канала следующий:
ТКанал<тип_сообщения> имя_канала;
Тип сообщения (указываемый в угловых скобках) может быть любым предопределенным типом или типом, который определил программист, например, запись (struct). В нашем случае декларируется, что создается канал целого типа (int). В примере канал определен как доступный член процесса Т, но такая принадлежность не является обязательной - канал это самостоятельный объект и может быть декларирован независимо от процесса. Процесс может использовать множество каналов, в том числе и однотипных. Массив однотипных каналов удобно использовать для организации системы приоритетных очередей.
Для канала определены две основных операции: передать в канал << и принять из канала >>. В обоих случаях в левой части операторов должно стоять имя канала, а в правой части - имя переменной, тип которой соответствует типу канала.
Семантика оператора >> (принять) состоит в следующем: вначале проверяется, есть ли в очереди канала сообщения: если есть, то из очереди выбирается первое сообщение и процесс, выполнивший операцию приема, продолжает выполняться дальше без задержки. Если же очередь канала пуста, то процесс переводится из очереди готовых процессов в очередь ожидания событий. Отметим, что ожидать сообщения в канале в один момент времени может только один процесс, попытка выполнения операции приема из канала, в котором уже ожидает некоторый процесс, является ошибкой и приведет к аварийному завершению программы с выдачей диагностического сообщения. Семантика оператора << (передать) состоит в том, что сообщение упаковывается в конверт и ставится в конец очереди сообщений канала. Процесс, выполнивший операцию передачи при этом не приостанавливается, а продолжает выполняться дальше. Длина очереди канала не ограничена. При выполнении оператора передачи проверяется, есть ли у канала ожидающий процесс, если есть, то он активизируется, т.е. переводится в очередь готовых процессов. Таким образом, каналы предоставляют процессам буферизованный несимметричный механизм взаимодействия, в котором получатель сообщения приостанавливается при отсутствии сообщений, а процесс, передающий сообщение, всегда выполняется без приостановки.
Кроме основных операций << (передачи) и >> (приема) для канала определена также операция <<= (передача в начало канала). В отличие от операции <<, которая записывает сообщения в конец очереди канала, операция <<= записывает сообщения в начало очереди канала. Таким образом, структура канала является промежуточной между очередью и деком: в такую очередь можно записывать данные с обоих концов, а удалять только из начала. Операция <<= может быть использована для различных целей, например:
Кроме того, канал предоставляет еще несколько сервисных функций:
if (канал >> i) cout << "Принято сообщение " << i << '\n'; else cout << "Таймаут\n";
Введение таймаута позволяет элегантно решать задачи, возникающие при приеме сообщений от потенциально ненадежного источника сообщений без зависания программы.
enum ТТег { целое, строка }; struct ТКонтейнер_Целого { int значение; }; struct ТКонтейнер_Строки { char значение[10]; }; ТКанал<ТТег> канал_тега; ТКанал<ТКонтейнер_Целого> канал_целых; ТКанал<ТКонтейнер_Строки> канал_строк; простой_процесс(ТГенератор_Целых) { ТТег тег = целое; ТКонтейнер_Целого контейнер; контейнер.значение = 123; пауза(случайное_число(10, 60)); канал_тега << тег; канал_целых << контейнер; } простой_процесс(ТГенератор_Строк) { ТТег тег = строка; ТКонтейнер_Строки контейнер; strcpy(контейнер.значение, "ABCDEF"); пауза(случайное_число(10, 60)); канал_тега << тег; канал_строк << контейнер; } static ТГенератор_Строк генератор_строк; static ТГенератор_Целых генератор_целых; void ТСценарий::тело_процесса(void) { ТТег тег; ТКонтейнер_Целого контейнер_целого; ТКонтейнер_Строки контейнер_строки; канал_тега.таймаут(30); if (канал_тега >> тег) { switch (тег) { case целое: канал_целых >> контейнер_целого; break; case строка: канал_строк >> контейнер_строки; break; } } else cout << "Таймаут\n"; }
Этот пример демонстрирует реализацию операции недетерминированного ожидания (ее семантика напоминает семантику оператора select языка Ада или блока ALT языка Оккам). В программе определяются следующие объекты:
Каждый из статических процессов заполняет свои контейнеры сообщений и передает их в соответствующие каналы. Кроме того, передача контейнера сообщения сопровождается передачей типа сообщения в канал тега. Время передачи определяется случайным числом в диапазоне от 10 до 60 миллисекунд. Сценарий принимает тип сообщения из канала тега и, в зависимости от того, какое из трех событий (2 сообщения и таймаут) наступило быстрее, выполняет то или иное действие.
В этом примере используется техника сильной типизации сообщений: вместо предопределенных типов "int" и "char[]" сообщения определяются как записи (struct), содержащие всего по одному элементу. Отметим также, что все каналы создаются как самостоятельные объекты (не принадлежащие конкретному процессу).
Для определения процессов в примере используется макроопределение "простой_процесс()", аргумент которого - имя типа процесса. Это макроопределение позволяет более лаконично записывать декларацию типа процесса и его тела в часто используемом случае, когда процесс переопределяет только одну функцию базового класса: тело_процесса(). Таким образом, лаконичное определение процесса Т:
простой_процесс(Т)
{
пауза(1000);
}
полностью эквивалентно такому явному определению:
class Т : public ТПроцесс { public: void тело_процесса(void); }; void Т::тело_процесса(void) { пауза(1000); }
ТРандеву<int> рандеву; простой_процесс(ТПроизводитель) { int i = 0; for (;;) { пауза(случайное_число(1000, 6000)); рандеву << ++i; } } простой_процесс(ТПотребитель) { int i; for (;;) { пауза(3000); рандеву >> i; } } static ТПроизводитель производитель; static ТПотребитель потребитель; void ТСценарий::тело_процесса(void) { пауза(20000); }
В этом примере иллюстрируется взаимодействие двух асинхронно выполняемых процессов - процесса-производителя, готового к взаимодействию через случайный промежуток времени в диапазоне от 1 до 6 секунд и процесса-потребителя, который готов к взаимодействию не ранее, чем через 3 секунды после взаимодействия с процессом-производителем. Взаимодействие выполняется на основе механизма "рандеву", синхронизирующего взаимодействие двух параллельных процессов. Семантика рандеву такова: если к взаимодействию готов только один процесс, то он приостанавливает свое выполнение (переводится в очередь ожидания событий) до того момента, когда к взаимодействию будет готов второй процесс, после чего оба процесса обмениваются данными и продолжают выполняться асинхронно. Рандеву обеспечивает небуферизованное симметричное взаимодействие процессов - оба процесса выступают как равноправные, в отличие несимметричного обмена сообщениями через канал.
Синтаксис рандеву аналогичен синтаксису обмена сообщениями с тем отличием, что вместо канала используется параметризованный объект класса, порожденного от базового класса ТРандеву. Синтаксис операторов приема и передачи тот же. Для рандеву также можно ограничивать время ожидания, используя функцию таймаут().
void ТСценарий::тело_процесса(void) { ТКанал<ТСобытие> канал; ТСобытие клавиша; клавиатура.соединить(канал); канал >> клавиша; }
Данный пример демонстрирует технику работы с устройством. Клавиатура (как устройство) - это статический процесс, создаваемый исполняющим ядром библиотеки. В отличие от традиционного способа, когда по ходу программы вызывается функция получения кода клавиши, в библиотеке 2KLIB используется обмен сообщениями. Для этого создается канал типа ТСобытие, который связывается с процессом "клавиатура". Связка выполняется с помощью функции, определенной в процессе "клавиатура" - соединить(). Аргументом этой функции является канал, в который клавиатура будет посылать сообщения о нажатых клавишах. Процесс, использующий клавишные события, выполняет операцию приема из данного канала.
Библиотека параллельного программирования 2KLIB продолжает мои исследования, связанные с программированием систем реального времени. Разработке библиотеки предшествовала работа, связанная с реализацией программных моделей многопроцессорных систем и процессора, микропрограммно поддерживающего конструкции параллельного программирования. Эти попытки привели к разработке и реализации экспериментального языка параллельного программирования 2K и компилятора для него. В компиляторе было использовано гибкое решение проблемы кодогенерации на основе синтеза программной модели процессора, обладающего желаемой виртуальной системой команд - это позволило довольно оперативно вносить изменения в язык, компилятор и экспериментировать с различными конструкциями и алгоритмами параллельного программирования.
Реализация и практическая работа с первой версией библиотеки 2KLIB показала удачность выбранных решений. В версии 2.04 были сделаны следующие изменения:
Дополнительно к библиотеке 2KLIB была разработана библиотека классов 2KWIN, предоставляющая основные возможности по созданию программ с текстовым многооконным интерфейсом: окна, блоки диалогов, меню, гипертекстовая help-система. Библиотека 2KWIN построена на той же технологической основе, что и библиотека 2KLIB, позволяет параллельным процессам выполняться в различных окнах и организовывать интерактивное взаимодействие с пользователем используя процессы клавиатуры и мыши с передачей сообщений по каналам.
Библиотеки 2KLIB и 2KWIN были применены в двух практических разработках - системе автоматизации производства счетчиков электрической энергии и системе управления аппаратурой кукольного театра 2+КУ. Аппаратура обоих систем построена по магистрально-модульному принципу и соединяется с компьютером через параллельный (принтерный) порт.
В настоящее время разрабатывается версия библиотеки 2KLIB для Windows, что позволит применить ее для решения задач моделирования сложных динамических систем, требующих больших объемов памяти и развитых средств графической визуализации. Задачи этого типа, как и задачи реального времени, хорошо поддаются декомпозиции на взаимодействующие процессы.
Статья была опубликована в журнале "Монитор" 6, 1995.
2klib.zip - Версия 2.04 от 4 мая 1995 (284K)
Архив включает в себя: