Основы многопоточного и распределенного программирования

       

Учебные примеры: язык Ada


Язык Ada бьи создан при содействии министерства обороны США в качестве стандарт­ного языка программирования приложений для обороны (от встроенных систем реального времени до больших информационных систем). Возможности параллелизма языка Ada явля­ются его важной частью; они критичны для его использования по назначению. В языке Ada также есть большой набор механизмов для последовательного программирования.

Язык Ada стал результатом широкого международного конкурса разработок в конце 1970-х годов и впервые был стандартизован в 1983 г. В языке Ada 83 был представлен механизм рандеву для межпроцессного взаимодействия. Сам термин рандеву был выбран потому, что руководителем группы разработчиков был француз. Вторая версия языка Ada была стандар­тизована в 1995 г. Язык Ada 95 совместим снизу вверх с языком Ada 83 (поэтому старые про­граммы остались работоспособными), но в нем появилось несколько новых свойств. Два са­мых интересных свойства, связанных с параллельным программированием, — это защищен­ные типы, подобные мониторам, и оператор requeue, позволяющий программисту более полно управлять синхронизацией и планированием.

В данном разделе сначала представлен обзор основных механизмов параллельности в языке Ada: задачи, рандеву и защищенные типы. Далее показано, как запрограммировать барьер в виде защищенного типа, а решение задачи об обедающих философах — в виде набо­ра задач, которые взаимодействуют с помощью рандеву. В примерах также демонстрируются возможности языка Ada для последовательного программирования.

8.6.1. Задачи

Программа на языке Ada состоит из подпрограмм, модулей (пакетов) и задач. Подпро­грамма — это процедура или функция, пакет — набор деклараций, а задача — независимый процесс. Каждый компонент имеет раздел определений и тело. Определения объявляют ви-

310                                                                            Часть 2. Распределенное программирование

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

декларации точек входа; end;

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

entry Identifier (параметры) ;

Параметры передаются путем копирования в подпрограмму (по умолчанию), копирования из подпрограммы или обоими способами. Язык Ada поддерживает массивы точек входа, кото­рые называются семействами точек входа.

Базовая форма тела задачи имеет следующий вид. task body Name  is

локальные декларации begin

операторы; end Name;



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

Пара "определение задачи-тело" определяет одну задачу. Язык Ada также поддерживает массивы задач, но способ поддержки не такой, как в других языках программирования. Про­граммист сначала объявляет тип задачи, а затем — массив экземпляров этого типа. Для дина­мического создания задач программист может использовать типы задач совместно с указате­лями (в языке Ada они называются типами доступа).

8.6.2. Рандеву

В языке Ada 83 первичным механизмом взаимодействия и единственной схемой синхро­низации было рандеву. (Задачи на одной машине могли также считывать и записывать значе­ния разделяемых переменных.) Все остальные схемы взаимодействия нужно было програм­мировать с помощью рандеву. Язык Ada 95 также поддерживает защищенные типы для син­хронизированного доступа к разделяемым объектам; это описано в следующем разделе.



Предположим, что в задаче т объявлена точка входа Е. Задачи из области видимости зада­чи т могут вызвать Е следующим образом. cal 1 Т. Е (аргументы) ;

Как обычно, выполнение call приостанавливает работу вызывающего процесса до тех пор, пока не завершится Е (будет уничтожена или вызовет исключение).

Задача Т обслуживает вызовы точки входа Е с помощью оператора accept, имеющего следующий вид.

accept E (параметры)   do

список операторов; end;

Выполнение оператора accept приостанавливает задачу, пока не появится вызов Е, копиру­ет значения входных аргументов во входные параметры и выполняет список операторов. Ко­гда выполнение списка операторов завершается, значения выходных параметров копируются

Глава 8. Удаленный вызов процедур и рандеву                                                                  311

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

Для поддержки недетерминированного взаимодействия задач в языке Ada используются операторы select трех типов: селективное ожидание, условный вызов точки входа и син­хронизированный вызов точки входа. Оператор селективного ожидания поддерживает защи­щенное взаимодействие. Его обычная форма такова.

select when Bi => accept оператор; дополнительные операторы; or  ...

or          when Bn => accept оператор; дополнительные операторы;

end select;

Каждая строка называется альтернативой. Каждое бд. — это логическое выражение, части when необязательны. Говорят, что альтернатива открыта, если условие B1. истинно или часть when отсутствует.

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


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

Оператор селективного ожидания может содержать необязательную альтернативу else, которая выбирается, если нельзя выбрать ни одну из остальных альтернатив. Вместо операто­ра accept программист может использовать оператор delay или альтернативу terminate. Открытая альтернатива с оператором delay выбирается, если истек интервал ожидания; этим обеспечивается механизм управления временем простоя. Альтернатива terminate вы­бирается, если завершились или ожидают в своих альтернативах terminate все задачи, ко­торые взаимодействуют с помощью рандеву с данной задачей (см. пример в листинге 8.18).

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

select вызов точки входа; дополнительные операторы; else      операторы; end select;

Вызов точки входа выбирается, если его можно выполнить немедленно, иначе выбирается альтернатива else.

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

select вызов точки входа; дополнительные операторы; or          delay оператор; дополнительные операторы;

end select;

Здесь выбирается вызов точки входа, если он может быть выполнен до истечения заданного интервала времени задержки.

Языки Ada 83 и Ada 95 обеспечивают несколько дополнительных механизмов для парал­лельного программирования. Задачи могут разделять переменные, однако обновление значе­ний этих переменных гарантированно происходит только в точках синхронизации (например, в операторах рандеву). Оператор abort позволяет одной задаче прекращать вы­полнение другой. Существует механизм установки приоритета задачи. Кроме того, задача имеет так называемые атрибуты. Они позволяют определить, можно ли вызвать задачу, или она уже прекращена, а также узнать количество ожидающих вызовов точек входа.



312                                                                            Часть 2. Распределенное программирование

8.6.3. Защищенные типы

Язык Ada 95 развил механизмы параллельного программирования языка Ada 83 по не­скольким направлениям. Наиболее существенные дополнения — защищенные типы, кото­рые   поддерживают  синхронизированный  доступ   к  разделяемым  данным,   и   оператор requeue, обеспечивающий планирование и синхронизацию в зависимости от аргументов вызова. Защищенный тип инкапсулирует разделяемые данные и синхронизирует доступ к ним. Экзем­пляр защищенного типа аналогичен монитору, а его раздел определений имеет следующий вид. protected type Name  is

декларации функций, процедур или точек входа; private

декларации переменных; end Name;

Тело имеет такой вид.

protected body Name  is

тела функций, процедур или точек входа;

end Name;

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

Вызовы защищенных процедур и точек входа обслуживаются в порядке FIFO, но в зави­симости от условий синхронизации точек входа. Чтобы отложить завершение обслуживае­мого вызова, в теле защищенной процедуры или точки входа можно использовать оператор requeue. (Его можно использовать и в теле оператора accept.) Он имеет следующий вид. requeue Opname;

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


В результате выполнения оператора requeue вызов помещается в очередь операции Opname, как если бы задача непо­средственно вызвала операцию Opname.

В качестве примера использования защищенного типа и оператора requeue рассмотрим код N-задачного барьера-счетчика в листинге 8.16. Предполагается, что N — глобальная кон­станта. Экземпляр барьера объявляется и используется следующим образом. В   :   Barrier;     --  декларация  барьера

В.Arrive;         —  или   "call  В.Arrive;"

Первые N-1 задач, подходя к барьеру, увеличивают значение счетчика барьера count и задержи­ваются в очереди на скрытой точке входа Go. Последняя прибывшая к барьеру задача присваивает переменной time_to_leave значение True; это позволяет запускать по одному процессы, за­держанные в очереди операции Go. Каждая задача перед выходом из барьера уменьшает значение count, а последняя уходящая задача переустанавливает значение переменной time_to_leave, поэтому барьер можно использовать снова. (Семантика защищенных типов гарантирует, что каж­дая приостановленная в очереди Go задача будет выполняться до обслуживания любого после­дующего вызова процедуры Arrive.) Читателю полезно сравнить этот барьер с барьером в листинге 5.12, который запрограммирован с использованием библиотеки Pthreads.



U.4. Пример: обедающие философы

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

В листинге 8.17 представлена главная процедура Dining_Philosophers. Перед проце­дурой находятся декларации with и use. В декларации with сообщается, что эта процедура использует объекты пакета Ada. Text_IO, a use делает имена экспортируемых объектов этого пакета непосредственно видимыми (т.е. их не нужно уточнять именем пакета).



яистинг 8.17. Решение задачи об обедающих философах на языке Ada; равная программа"

nth Ada.Text_IO;  use Ada.Text_IO; procedure Dining_Philosophers is subtype ID is Integer range 1..5;

task Waiter is              --  спецификация задачи-официанта

entry Pickup(I   :   in  ID);

entry Putdownd   :   in ID) ; end task body Waiter is separate;

task type Philosopher is       --  тип задачи-философа

"В теле задачи-философа отсутствует имитация случайных промежутков времени, в течение которых философы едят или думают. — Прим. ред.





В листинге 8.17 имя Philosopher определено как тип задачи, чтобы можно было объя­вить массив dp из пяти таких задач. Экземпляры пяти задач-философов создаются при обра­ботке декларации массива DP. Каждый философ сначала ждет, чтобы принять вызов своей инициализирующей точки входа init, затем выполняет rounds итераций. Переменная rounds объявлена глобальной по отношению к телу задач философов, поэтому все они могут ее читать. Переменная rounds инициализируется вводимым значением в теле главной про­цедуры (конец листинга 8.17). Затем каждому философу передается его индекс с помощью вызова DP (j) . init (j).

Листинг 8.18 содержит тело задачи Waiter (официант). Оно сложнее, чем процесс Waiter в листинге 8.6, поскольку условие when в операторе select языка Ada не может ссылаться на входные параметры. Waiter многократно принимает вызовы операций Pickup и Putdown. Принимая вызов Pickup, официант проверяет, ест ли хотя бы один сосед фило­софа i, вызвавшего эту операцию. Если нет, то философ i может есть. Но если хотя бы один сосед ест, то вызов Pickup должен быть вновь поставлен в очередь так, чтобы задача-философ не была слишком рано запущена вновь. Для приостановки ожидающих философов используется локальный массив из пяти точек входа wait (ID); каждый философ ставится в очередь отдельного элемента этого массива.

Поев, философ вызывает операцию Putdown. Принимая этот вызов, официант проверя­ет, хочет ли есть каждый сосед данного философа и может ли он приступить к еде.Если да, официант принимает отложенный вызов операции Wait, чтобы запустить задачу-философ, вызов операции Pickup которой был поставлен в очередь. Оператор accept, обслуживаю­щий операцию Putdown, мог бы охватывать всю альтернативу в операторе select, т.е. за­канчиваться после двух операторов if. Однако он заканчивается раньше, поскольку незачем приостанавливать задачу-философ, вызвавшую операцию Putdown.


Содержание раздела