Правильная ссылка на эту страницу
http://az-design.ru/Support/SoftWare/Lng/C/D19840628Elc026.shtml

Применение новых средств языка Си для параллельной обработки

Рей Нейни (Ray Naeini)
Фирма Flexible Computer Corp. (Даллас, шт.Техас)

Ray Naeini. A few statement types adapt C language to parallel processing, pp.125—129.

Описаны новые средства компиляции для языка Си, применяемые при параллельной обработке. Расширенная версия этого языка, названная Параллельный Си (Concurrent С), позволяет применять разнообразные приемы организации взаимодействия и синхронизации распределенных процессов. В сочетании с построенной по модульному принципу аппаратной частью язык Параллельный Си обеспечивает гибкость и высокую производительность вычислительной системы.

На основе языка Си, успешно применяющегося в задачах обычной последовательной обработки, создан язык программирования Параллельный Си, который предназначается для параллельной обработки и выполнения процедур в реальном времени на мультипроцессорных системах. Он был задуман как инструментальное средство разработки серийных программ для компьютеров, ориентированных на выполнение нескольких потоков команд, обрабатывающих ряд потоков данных (см. «Гибкость аппаратных средств многомашинных комплексов»).

Параллельный Си построен на тех же лексемах и правилах, что и стандартный язык Си. Поэтому последний вертикально совместим с Параллельным Си по принципу «снизу вверх». При создании нового языка цель состояла в том, чтобы реализовать простой, структурированный синтаксис, аналогичный синтаксису языка Си, с минимальным количеством новых ключевых слов. К расширениям языка относятся родовые функции, воплощающие широкое разнообразие приемов программирования. Иначе говоря, Параллельный Си предлагает готовые модели без ограничения на методы их исполнения.

Новые ключевые слова и операторы этого языка обеспечивают оперативный контроль событий реального времени и параллельную обработку в мультипроцессорных системах; они могут применяться и при решении обычных задач последовательной обработки. Дополнительные возможности языку можно придать путем использования соответствующих средств Параллельного Си в сочетании с разнообразными приемами и методами программирования. Наличие простых родовых функций позволяет легко адаптировать описываемый язык к новой аппаратуре и будущим приложениям.

Параллельная обработка при помощи нескольких процессоров позволяет достичь более высокой производительности и скорости вычислений, а также делает возможным гибкое использование аппаратной части при изменении требований. Следует отметить, что термин «параллельность» имеет теперь уже не одно значение. Он часто применяется там, где следовало бы говорить о «кажущейся» параллельности, т.е. в тех случаях, когда несколько процессов совместно пользуются одним процессором, занимая его в течение выделенных им квантов времени. Более точным определением такого режима служит термин «мультизадачный», интерпретируемый иногда как режим мультипрограммирования.

Истинная параллельность — это мультипроцессорная обработка, при которой группа последовательных процессов выполняется на отдельных процессорах. Действия, связанные с такими процессами, в самом деле выполняются одновременно. Сочетание обеих методик, мультизадачного режима и мультипроцессорной обработки дает возможность лучше использовать ресурсы системы. Язык Параллельный Си предназначен для создания и выполнения программ обоих типов, а также управления ими (см. «Поэтапное создание программных комплексов параллельной обработки»).

Для мультипроцессорной обработки в системе из параллельных процессоров отдельные процессы должны координировать относящиеся к ним задачи, обмениваясь данными между собой и синхронизируя последовательности выполнения задач. Более того, для обеспечения целостности информации процессы должны работать с общими данными (если они вообще имеются) по принципу взаимного исключения.

Во избежание непредсказуемого поведения системы необходимо, чтобы каждый процесс пользовался обмениваемой информацией (в виде сообщений или общих данных) только после того, как ее перестанет занимать первоначальный процесс. Особое внимание следует уделить этой проблеме при решении задач параллельной обработки, где процессы работают с обмениваемыми данными в непредсказуемом порядке.

Для того чтобы установить очередность процессов в обмене данными, их необходимо синхронизировать. Синхронизация сводится к простому правилу, согласно которому каждый процесс при своей попытке обратиться к общим данным, занятым в это время другим процессом, будет отложен до тех пор, пока эти данные не освободятся.

Когда обмен данными происходит в форме сообщений, то процесс-отправитель и процесс-адресат синхронизируются моментами приема сообщений. Программист может использовать текст сообщения для изменения хода выполнения процесса-адресата.

Применение общих переменных для обмена данными между процессами влечет за собой использование других механизмов, таких, как ожидание по признаку «занято», семафоры, условные критические промежутки, мониторы и формулы маршрутов. Необходимы два основных типа синхронизации: условная синхронизация, которая осуществляет задержку процесса до того момента, когда совместно используемые данные придут в заранее определенное состояние; синхронизация взаимного исключения, когда гарантируется, что весь цикл работы процесса с общими данными будет представляться другим процессам как некая неделимая операция. Когда процесс выполняет эту операцию, считается, что он находится в так называемом критическом промежутке.

Синхронизирующие события

Для синхронизации процессов программист может также использовать события — определенные в явном виде ситуации, которые могут известным образом повлиять на ход выполнения процессов в непредсказуемый момент времени. Внешние прерывания, генерируемые, например, периферийными устройствами, составляют один из классов событий. События может, однако, порождать (или активизировать) и выполняющийся процесс. После обнаружения некоторого события процесс-адресат может, например, получить доступ к заранее определенной группе данных для обмена ими или перейти к выполнению любой запрашиваемой функции.

События могут действовать в пределах одного процесса. Такие внутрипроцессные события, как таймеры и ловушки, удобны для синхронизации внутренних (для процесса) операций, а также для обнаружения ошибок.

Обслуживать события можно, применяя либо процедурное, либо непроцедурное программирование. При процедурном методе в программе присутствует определенный оператор, заставляющий ее проверять наличие некоторого события и, если нужно, ждать его появления.

При непроцедурном методе обработки событий программа продолжает выполняться при появлении события, рассматриваемого как параллельная задача. Событие может произойти в любой момент выполнения программы. В этом случае естественный ход работы прерывается и управление передается предварительно заданному обработчику событий. По завершении его функций управление возвращается оператору, стоящему непосредственно за тем, который выполнялся в момент появления события. Прерывание может, например, быть разрешено для некоторой части основной программы и специального обработчика, рассчитанного на выполнение в случае появления этого прерывания.

Вообще говоря, для реализации мультипроцессорной обработки и программирования процессов реального времени язык должен обеспечивать следующие возможности:

— Защиту доступа к общим данным, для того чтобы предотвратить доступ одного процесса к информации, к которой в это время обращается другой процесс.

— Взаимодействие и синхронизацию процессов независимо от физического места их выполнения.

— Создание и параллельное выполнение процессов.

— Определение и контроль событий, позволяющие использовать их как эффективные инструменты внешней и внутренней синхронизации (для процессов), а также для обеспечения соответствующей реакции на события реального времени.

Переменные событий

Новые конструкции языка Параллельный Си подразделяются на два класса. Описания новых переменных включают переменные событий и общие переменные, а новые операторы потока управляющих данных применяются для организации взаимодействия процессов, управления ими, параллельной обработки и контроля событиями.

Так как все события реального времени представляют собой или таймеры, или особые ситуации, то соответствующие им переменные объявляются и описываются ключевыми словами Timer (таймер) и Exception (особая ситуация). Таймер активизирует событие в тот момент, когда связанное с ним значение, уменьшаясь от начальной величины, достигает некоторого, заранее определенного числа, включая нуль. После того как переменной таймера присвоено то или иное значение, ее уменьшение инициируется другим новым оператором Activate (активизировать). (Оператор Activate может также обновить значение работающего таймера таким образом, что он будет продолжать считать в сторону уменьшения от нового значения.)

Таймер представляет собой простую переменную, которой предшествует ключевое слово Timer. Описание таймера могло бы выглядеть следующим образом:

timer x_time = 30.

Однако значение таймера, выражаемое в единицах времени, величина которых определяется типом технических средств, не обязательно задавать сразу же. Если требуется, чтобы таймер автоматически перезапускался после достижения им нуля, то можно воспользоваться конструкцией, которая называется Cyclic Timer (циклический таймер).

Оператор Activate может применяться для активизации либо таймера, либо особой ситуации следующим образом:

activate (x_time);

Таймер можно исключить из работы, присвоив его переменной нулевое значение с последующей активизацией:

x_time = 0 activate (x_time);

Оператор Activate требует наличия только одного идентификатора — идентификатора события, который должен быть заранее описан как таймер или особая ситуация.

Ловушки и прерывания

Особая ситуация может быть причиной случайных событий, влияющих на ход либо задающего ее процесса (внутренние особые ситуации или ловушки), либо независимого процессора (внешние особые ситуации — прерывания). Переменные особых ситуаций рассматриваются как булевы переменные (в языке Си — это простые целые). Особой ситуации, которая не активизирована, соответствует переменная со значением «ложь» (логический 0). Активизация изменяет значение этой переменной на «истину» (логическая 1). После считывания переменной она снова примет значение «ложь»; переменная будет сохранять значение «истина» и, следовательно, не меняться до момента считывания. Таким образом, особые ситуации могут имитировать» прерывания.

При описании особой ситуации для нее задается также область действия: если эта область распространяется только на определяющий ее процесс, то особая ситуация считается для него внутренней. Некоторые внутренние особые ситуации зависят от характера средств обработки и могут использоваться без непосредственного описания в теле программы. К заранее заданным внутренним особым ситуациям относятся: переполнение, потеря значимости, Illinst (запрещенная кохманда) и Kill (аннулировать); последняя ситуация может применяться программистом для отмены выполнения процесса.

Всякий раз, когда средства обработки сталкиваются с одним из контролируемых явлений, происходит активизация соответствующих заранее заданных внутренних особых ситуаций. Программист может инициировать действия по обработке таких ситуаций по мере их появления, устанавливая, какие из них следует контролировать. Аналогичным образом программист может определить внутреннюю особую ситуацию, объявив в качестве такой ситуации некоторую переменную в области действия задающего ее процесса:

exception x_excep;

До тех пор пока переменная x_excep особой ситуации не активизируется оператором Activate, ее значение будет равно логическому нулю.

Внешняя особая ситуация отличается тем, что область ее действия распространяется более чем на один процесс с целью организации вещательной или прямой двусторонней связи между ними. Такая особая ситуация может быть активизирована любым процессом, входящим в область ее действия, и подвержена воздействию остальных процессов из этой области. Прямая взаимосвязь процессов может быть реализована путем такого описания особой ситуации, которое задает для нее конкретный процесс-отправитель или процесс-адресат. К примеру,

exception e1 p1 → > p2;

exception e2 p3, p4 → >p5;

Область действия особой ситуации e1 распространяется на два процесса: p1 и p2. При этом p1 определен как процесс-отправитель, а p2 — как процесс-адресат. Каждой особой ситуации может назначаться более чем по одному отправителю или адресату, как, например, для особой ситуации e2. Обычно объявление внешней особой ситуации позволяет создавать каналы однонаправленной передачи служебных сигналов между процессами, обеспечивающие быстрое взаимодействие. Процессы-отправители и процессы-адресаты приписываются к соответствующим каналам передачи, для которых определяется направление обмена сигналами (особыми ситуациями).

Контроль событий

События типа таймеров или особых ситуаций могут обрабатываться либо процедурным, либо непроцедурным способом. В Параллельном Си второй метод предусматривает использование оператора Whenever. Процедурная обработка ориентируется на условные операторы When или When-Else (с двумя ветвями).

Оператор When приостанавливает относящийся к нему процесс до момента появления заданного события, после чего начинают выполняться операторы из связанного с этим событием списка. Оператор When-Else в отличие от When проверяет определенное условие и ветвится на выполнение группы операторов, следующих за ключевым словом When (если результат указаний проверки положителен), или на выполнение операторов, идущих за ключевым словом Else (когда результат проверки отрицателен). Синтаксис оператора When-Else аналогичен синтаксису оператора If-Else.

Оператор Whenever определяет для конкретной области действия программы событие, рассматриваемое в качестве задачи, параллельной выполнению указанной программы. Оператор Whenever задает также программу — обработчик событий, которая выполняется при любом появлении контролируемого события. При этом нормальный ход программы приостанавливается до окончания работы программы-обработчика, после чего управление возвращается программе и она возобновляется с той точки, где была прервана.

Рассмотрим для примера программу, которая вычисляет значение факториала целого числа:

fact(number)
int number;
{
   int i, result;
   result = 1;
   if (number == 0) return (result);
   whenever(overflow) ovf_err();
   for (i=l; i<=number; i++) {
      result = result * i;
      return(result);
   }
}

Если во время работы программы возникает особая ситуация типа переполнения, то вызывается обработчик переполнения Ovf—err.

Механизм событий бывает полезен также для синхронизации процессов. Пусть имеются два процесса — отправитель и адресат. Тогда можно воспользоваться следующими описаниями переменных особых ситуаций и фрагментов программы:

exception msg_ready sender --> receiver;
exception msg_reved receiver --> sender;
exception msg_end sender --> receiver;
   . . .
/* Фрагмент процесса-отправителя: */ 
do {
   put_msg();
   activate(msg_ready);
   when (msg_rcved); 
} while(more_msg); 
activate(msg_end);
   . . .
/* И фрагмент процесса- адресата */ 
whenever(msg_end) recv_exit();
   . . .
for (;;) {
   when (msg_ready) get_msg();
   activate(msg_rcved);
}

В этом примере синхронизация передачи сообщений между отправителем и адресатом достигается путем использования особых ситуаций Msg_ready и Msg_rcved. Завершая цикл, процесс-отправитель посылает процессу-адресату особую ситуацию Msg_end. Оператор Whenever процесса-адресата контролирует появление Msg_end и инициирует выполнение стандартной программы Recv_exit, которая осуществляет выход из текущей функции.

Оператор When может применяться для синхронизации доступа к данным, которыми совместно пользуются процессы. Это реализуется при помощи оценки совокупности условий при необходимости обращения к данным. Условие — это выражение, вычисление которого дает значение «истина» или «ложь». Это значение как раз и контролирует, выполняется ли группа операторов, относящихся к оператору When.

Оператор When может служить инструментом непосредственной реализации метода условных критических промежутков для совместного доступа к данным. Процессы, пользующиеся общими переменными, могут либо распределяться между разными процессорами, либо выполняться одним процессором в мультизадачном режиме. Общие переменные, используемые процессами, которые связаны с различными процессорами, размещаются в памяти коллективного доступа. Поэтому такие переменные по своему характеру относятся к классу статических и глобальных.

В предположении, что данные достоверны. общие переменные перед обращением к ним со стороны процесса следует заблокировать. На общие данные накладывается защита, которая сохраняется до тех пор, пока текущий процесс не закончит работу с ними и не вернет их в уже известное состояние. Затем этот процесс может снять блокировку с общих данных. Если другой процесс попытается обратиться к заблокированным переменным, то он будет задержан до момента, когда они снова станут доступными. Период, в течение которого один процесс монопольно владеет общими переменными и работает с ними под защитой блокировки, называется критическим промежутком.

Идентификация общих переменных

Для идентификации общих переменных не требуется новых ключевых слов. Атрибуты external (внешний) и external-static (внешний статический) стандартного языка Си задают для общих переменных необходимые области действия и могут известить о них соответствующие процессы. Все переменные с атрибутами external или external-static, являющиеся общими для нескольких процессов (а не просто для функций одного процесса), однозначно относятся к категории общих переменных.

Процессы можно синхронизировать между собой методом условных критических промежутков при помощи операторов When и When-Else. Каждый процесс будет периодически откладываться до появления определенного условия; такая синхронизация считается условной. После появления заданного условия процесс получает возможность выполнить группу операторов, которые называют критическими. В этот период гарантируется монопольное использование общих данных — взаимного исключения, — и весь цикл работы критического промежутка программы воспринимается соответствующими процессами как одна неделимая операция.

Пусть, например, процесс p1 может использовать некий общий буфер с именем Buffer для записи данных, а процесс p2 — для чтения тех же данных. При синхронизации этих процессов применяется другая общая переменная с именем Buffer—status. Следующий фрагмент программы показывает, как осуществляется запись в буфер и чтение из него информации с гарантированной защитой общих переменных. Для синхронизации оба процесса проверяют состояние этого буфера:

/* Фрагмент процесса p1 */
when (buffer_ status == empty) {
   write_buffer();
   buffer_ status = FULL;
}
/* И фрагмент процесса р2 */ 
when (buffer_status == full) {
   read_buffer();
   buffer_status = EMPTY;
}

Каждый из приведенных в данном примере блоков с оператором When соответствует следующей последовательности: операторы Lock и If. группа критических операторов, оператор Unlock. Оператор When объединяет в себе функции защиты и синхронизации, автоматически порождая операторы Lock, Unlock и группу операторов оценки условий. Таким образом, оператор When скрывает от программиста всю последовательность операций, необходимых для приостановки и возобновления процесса в случае, когда недоступны «замки» или не удовлетворяется необходимое условие. Операторы Lock и Unlock относятся к более низкому уровню, который доступен программисту в качестве системных вызовов при непосредственном программировании.

Процесс представляет собой фундаментальное понятие для программирования мультипроцессорных задач. В языке Параллельный Си процесс задается и запускается при поме щи оператора Process. Он состоит из особого, отличного от других идентификатора, кода, используемого процессом в ходе выполнения, и, если это требуется, признака конкретного процессора для вы-еолнения процесса, а также системно-зависимых атрибутов, определяющих условия, в которых действует процесс, например приоритет или объем стека.

Если нужно, системно-зависимые атрибуты записываются в заранее определенную структуру и передаются средствам системной поддержки. Эту структуру можно подгонять для различных реализаций системы или вообще аннулировать. В качестве кода процесса может выступать любая функция языка Си, заданная в теле программы.

Идентификатор процесса определяется как целое число, а значение ему присваивается системой при выполнении оператора Process; таким образом, процессы можно порождать динамически. Оператор Process может пересылать новые значения аргументов той функции, которая задает тело процесса.

«Родитель» и «потомок»

Процесс, запущенный оператором Process, считается процессом-потомком, а процесс, выполняющий этот оператор, — процессом-родителем. Эта традиционная схема отличается простотой и позволяет полностью управлять многими параллельно выполняющимися процессами-потомками.

Оператор потока управляющих данных, Cobegin, предоставляет объединяющую структуру для параллельного выполнения процессов. Операторы, определенные внутри блока Cobegin, выполняются в заданном этим блоком порядке, а оператор, следующий сразу за блоком, не будет обслуживаться до завершения всех запущенных в данном блоке процессов:

cobegin {
   process(p1, fund(), processor1);
   process(p2, func2(argl), processor2);
   process(p3, func3(), processor2);
   <statements>  /* handled by parent process */
   process(p4, func4( )); /* default processor*/
}
i++

В блоке Cobegin запускаются процессы p1, p2, p3 и p4, а также выполняются процессом-родителем операторы <statements>. Процессы р2 и рЗ обслуживаются одним процессором, что служит примером мультизадачности. Процессор для выполнения процесса p4 выбирается системным загрузчиком и зависимости от загруженности системы и прочих факторов. Выполнение оператора i++ будет отложено до завершения всех запущенных в блоке процессов.

Если оператор Process используется вне блока Cobegin, то процесс-родитель не будет задержан. В этом случае «родитель» и «потомок» будут обрабатываться одновременно либо в истинном, либо в кажущемся параллельном режиме.

Альтернативой данному методу управления выполнением параллельных процессов служат конструкции диспетчерского контроля событий. Сигнализацию об окончании процессов-потомков обеспечивает активизация тех или иных особых ситуаций; задержать выполнение процесса-родителя можно при помощи оператора When до тех пор, пока не будут приняты все такие сигналы.

Дочерние статьи:

Гибкость аппаратных средств многомашинных комплексов

Поэтапное создание программных комплексов параллельной обработки

Выходные данные:

Журнал "Электроника" том 57, No.13 (694), 1984г - пер. с англ. М.: Мир, 1984, стр.41

Electronics Vol.57 No.13 June 28, 1984 A McGraw-Hill Publication

Ray Naeini. A few statement types adapt C language to parallel processing, pp.125—129.

Раздел: МЕТОДЫ, СХЕМЫ, АППАРАТУРА

Тема:     Информационные системы





Дата последнего изменения:
Thursday, 21-Aug-2014 09:10:56 MSK


Постоянный адрес статьи:
http://az-design.ru/Support/SoftWare/Lng/C/D19840628Elc026.shtml