Главная » Мануалы

1 2 3 4 5 6 7 ... 32

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

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

2.2.2. Механизм рандеву

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

Читатель, знакомый с другими языками параллельного программирования, в которых операционными системами реализуется многозадачный режим, может заинтересоваться, насколько термин задача в языке Ада эквивалентен аналогичному термину в этих средах или используемому в них термину процесс. Ответ состоит в том, что Ада-задачи обладают одним дополнительным совершенно уникальным свойством, а именно: они предоставляют пользователю процедурный интерфейс, полностью аналогичный интерфейсу, который обеспечивается пакетом. Задачи могут иметь входы для обращений из других задач, и эти входы должны описываться в спецификации задачи точно так же, как пакетные процедуры - в спецификации пакета. Хотя обращения и к входам, и к процедурам происходят одинаково, они определяются и реализуются по-разному. Обращения к процедурам выполняются вызывающей программой, а к входам ~- вызываемой (принимающей)! программой; в по-




Траяиционнь|й подход.

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

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

Стандартные языки, такие, как Фортран, обычный Паскаль и многие другие, не предоставляют возможностей для организации многозадачной работы. В тех случаях, когда это требуется, такой рел<им должна обеспечивать базовая многозадачная операционная система. При этом программы на языке высокого уровня выполняются как прикладные программы, которые по мере необходимости обращаются к операционной системе для межзадачной синхронизации и установления связей. Обращения к операционной системе и механизмы межзадачных связей лежат вне языка высокого уровня. Этот подход проиллюстрирован на рис. 2,6, а. Его основная трудность заключается в логической СЛОЖНОСТИ, поскольку нет единой концептуальной модели для системы в целом, включающей набор прикладных программ и операционную систему.

Что касается языка Ада, то он предоставляет пользователю целостный механизм организации концептуально согласованной мел<задачной связи, не основанный на явных обращениях к базовой операционной системе и реализованный исключительно в рамках языка высокого уровня. Как показано на рис. 2.6, б, для этого требуется только базовое ядро, обеспечивающее механизм рандеву. Это базовое ядро невидимо на уров-


\6) Подход ейзыке Ада.

Рис, 2,6. Традиционный и реализованный в языке Ада подходы к организации прохождения задач.



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

ЗАДАЧА-ПРОИЗВОДИТЕЛЬ Вызов:

BUFFER. WRITE(CHARi

Символ БУФЕРИЗУЮЩАЯ ЗАДАЧА 4>ч


Вызов; BUFFER, READlCHAR)

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

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

Для иллюстрации природы межзадачных связей и использования механизма рандеву рассмотрим пример на рис. 2.7, где показаны взаимодействия между задачей-производителем, буферизующей задачей и задачей-потребителем. Эти задачи изо-бралсены в виде черных ящиков и немного напоминают пакеты, за тем исключением, что представлены параллелограммами, а не прямоугольниками, чтобы в символическом отображении подчеркнуть их параллельную природу. На рисунке задача-производитель и задача-потребитель автономны и не имеют входов. Напротив, буферизующая задача имеет входы записи и чтения, которые используются двумя другими задачами. Идея состоит в том, что буферизующая задача сглаживает расхождения между скоростью вывода в задаче-производителе и скоростью ввода, свойственной задаче-потребителю. Проницательный читатель может спросить: Почему бы не использовать пакет? Для чего нужна задача? Ответ состоит в том, что в про-



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

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

Читатели, знакомые с теорией и практикой параллельного программирования знают, что в других системах существуют свои средства обеспечения синхронизации, например команды проверки и установки признаков, семафоры, условные критические области, мониторы, обмен сообщениями и т. д. В языке Ада для этого требуется использование задач. Явное преимущество этого подхода с точки зрения проектирования заключается в том, что вся деятельность по взаимодействию и синхронизации осуществляется активными программными объектами на одном и том же логическом уровне. Так, синхронизация и взаимодействие явно присутствуют в обращениях программных объектов друг к другу. Здесь нет каких-то скрытых механизмов функционирования, завуалированных сигналами и сообщениями. Другое явное преимущество состоит в уменьшении числа понятий, привлекаемых для описания системы, в которой имеются и пакеты, и задачи. Оба типа объектов предоставляют пользователю сходные внешние интерфейсы.

На рис. 2.8, а приведена спецификация буферизующей задачи и показано, как к ней обращаются задача-производитель и задача-потребитель. На рис. 2.8, б представлен простейший вариант тела буферизующей задачи, которая в данной версии воспринимает один символ от производящей задачи через вход WRITE (ЗАПИСЬ) и затем ждет, пока потребляющая задача



считает его через вход READ (ЧТЕНИЕ), прежде чем вновь воспринять следующий символ от задачи-производителя. С помощью оператора приема ACCEPT буферизующая задача сообщает о своей готовности в данный момент воспринять обращение к входу, имя которого указано в операторе. Если обращение уже произошло, это будет означать, что какая-то задача стоит в очереди, связанной с данным входом, и рандеву состоится немедленно. Если же очередь на данном входе пуста, буферизующая задача ожидает обращения к нему. В случае когда вызывающая программа обращается к входу раньше, чем в буферизующей задаче достигнут соответствующий ему оператор приема, ей приходится стоять в очереди до тех пор, пока буферизующая задача не начнет воспринимать обращение к этому входу. Тело буферизующей задачи должно содержать по крайней мере по одному оператору приема для каждого входа, объявленного в ее спецификации; в противном случае программа, вызвавшая этот вход, будет ждать вечно.

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

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

Ясно, что конкретная реализация механизма взаимодействия, приведенная на рис. 2.8, б, неадекватно решает задачу буферизации, поскольку символы не накапливаются в рамках внутренней структуры данных. На рис. 2.8, в приведена более общая программа, основанная на использовании внутреннего кольцевого буфера. Для вызывающих программ ничего не изменилось, но время простоя из-за буферизующей задачи станет меньше. Тело этой задачи подвергалось значительным изменениям: теперь оно содержит оператор так называемого выборочного ожидания (selective wait), который определяет входы WRITE и READ как альтернативные. Этот оператор, а точнее весь текст между зарезервированными словами select и end select, следует рассматривать как единственную простую инструкцию, которая устанавливает буферизующую задачу в состояние ожидания первого вызова входа WRITE или READ. Производящая и потребляющая задачи могут теперь выпол-



--ЗАДАЧА-ПРОИЗВОДИТЕЛЬ

\оор

-- ФОРМИРОВАНИЕ

ОЧЕРЕДНОГО СИМВОЛА BUFFER.WRITE1CHAR); tend loop;

--ЗАДАЧА-ПОТРЕБИТЕЛЬ

loop

BUFFER.READ{CHAR);

--ИС ПОЛЬЗОВАНИЕ СИМВОЛА

end loop;

1--СПЕЦИФИКАЦИЯ БУФЕРА

task BUFFER Is

entry READ {С : out CHARACTER);

entry WRITE {C : in CHARACTER); end;

{a) Сопряжения задач.

task body BUFFER isi POOL: CHARACTER: begin loop

accept WRITE (C: in СНАйАСТЁй1 ddf

POOL : = C; end;

accept READ (C: out CHARACfER)

с : = POOL; end; end loop; end BUFFER;

(6) Буферизующая задача в простейшей форме,-

task body BUFFER is

POOL SIZE; constant INTEGER : = 100;

POOL V : array (1.. POOL SIZE) of CHARACTER;

IN INDEX, OUT INDEX! INTEGER range T .. POOL SiZE ! li begin loop

select

accept WRITE (C: in CHARACTER) do

POOL (IN INDEX): к C; end;

IN INDEX : = lN iNDEX mod POOL SIZE + 1)

accept READ (C: out CHARACTER) do 4 С : = POOL (OUT !NDEX); , end;

OUT INDEX : = OUT JNDEXmod POOL SIZE + 1? end select; end loop; end BUFFER;.

(e) Буферизующая задача с эыбордчным ожиданием,



task body BUFFER is

POOL SIZE : constant INTEGER : ь= ЮО;

POOL : array (1 .. POOL SIZE) of CHARACTER;

COUNT : INTEGER range 0.. POOL SIZE : = 0;

IN INDEX, OUT INOEX : INTEGER range 1,. POOL SIZE : = 1 begin

loop

select

when COUNT< POOL SiZE =>

accept WRITE (C : in CHARACTER) do

POOL (IN INDEX) : = C; end;

IN INDEX : = IN INDEX mod POOL SIZE + 1j COUNT : = COUNT + 1; or when COUNT >0 =>

accept READ (C ; out CHARACTER) do

С : = POOL (OUT INDEX); end;

OUT INDEX : = OUT INDEX mod POOL SIZE + Ij COUNT : = COUNT-1; end select; end loop; end loop; end BUFFER;

(г) Буферизующая задача с механизмом защиты (соответственно справочному руководству по языку Ада),

Рис. 2.8. Трехзадачная Ада программа с производящей, потребляющей и буферизующей задачами.

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

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



Обозначения ;

> <1-

указывают те моменты времени, Когда эьтолняютсп ,аажные действия

сплошной линией отмечено время, в течение которого задача выполняется

ЗАДАЧА-ПРОИЗВОДИТЕЛЬ БУФЕРИЗУЮЩАЯ ЗАДАЧА ЗАДАЧА - ПОТРЕБИТЕЛЬ

Рандеву

Вызов WRITE t>

Ожидание Возврат

О Выбор альтернативы i Ожидание ---------- <3 Прием вызова WRITE

Г

Выз9в WRITE {>

Ожидание

Выбор альтернативы Ожид Прием вызова REAO

Конец

Рандеву

:l

Конец

Рандеву

Ожидание

Дальнейшее ожидание Возврат t>

т

<3 Вызов READ Ожидание <3 Возврат

Выбор альтернативы Прием вызова WRITE

Конец

< Выбор альтернативы

Рис. 2.9. Временная диаграмма буферизации при отсутствии закрытых входов.

ка условий защиты с целью выбора входов, открытых для приема. В частности, в данном примере, если значение счетчика COUNT равно размеру пула POOL SIZE, то для приема будет открыт только вход чтения READ. Это означает, что после вызова входа записи WRITE вызывающая программа будет стоять в очереди к этому входу до тех пор, пока в результате изменения условий защиты он не окажется открытым. Заметим, что такое изменение условий может произойти только в результате приема обращения к другому входу. Ситуация, при которой все входы закрыты, означает ошибку программирования.



На рис. 2.9 и 2.10 приведены временные диаграммы, отражающие взаимодействия между производящей, буферизующей и потребляющей задачами в двух случаях: когда все альтернативные входы открыты и когда один альтернативный вход закрыт.

Язык Ада обладает еще рядом свойств, связанных с механизмом рандеву; эти свойства будут введены в рассмотрение

Обозначения:

Р> <q указывают те моменты времени, когда вьшолнягатся важные действия

- сплошной линией отмечено время

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

ЗАДАЧА-ПРОИЗВОДИТЕЛЬ БУФЕРИЗУЮЩАЯ ЗАДАЧА ЗАДАЧА-ПОТРЕБИТЕЛЬ

Буфер заполнен, поэтому входWR!T£ закрыт

вызов WRITE >

Выбор альтернзгисы Ожидание

Рандеву

Прием вызова READ [> Ожидание

Конец

Рандеву

Дальнейшее ожидание Возврй р>----

Времч

Снятие защиты от записи

< Вызов READ Ожидание

< Возврат

Выбор альтернативы Прием вызова WRITS Конец

\Выбор альтернативы

Рис. 2.10, Временная диаграмма буферизации при наличии одного закрытого



Основная программа

Параллельная часть

UUUU

Базисные элементы ядра

Лоследовательная часть


Рис. 2.11. Организация прохождения задач с помощью процедур на Паскале.

В ГЛ. 3 вместе с расширенной графической нотацией для всех альтернатив.

Сравним теперь подходы к организации прохождения задач в языке Ада и стандартном Паскале. Прежде всего следует отметить, что в стандартном Паскале нет средств обеспечения параллельности. Для создания параллельных программ стандартный Паскаль можно использовать единственным образом: написать специальные процедуры для организации прохождения задач, которые никогда не смогут быть вызваны и не сумеют осуществить нужного возврата в среде языка высокого уровня. Эти процедуры передаются ядру, которое следит за временем выполнения программ и обеспечивает параллельность с помощью ведущей Паскаль-программы; последняя же инициализирует ядро. В языке высокого уровня предполагается, что все это известно программисту. На рис. 2.11 дана структурная диаграмма, показывающая, как взаимодействуют различные компоненты параллельной системы, написанной на Паскале. Такой подход можно реализовать в любом языке высокого уровня, не обеспечивающем параллельности. Основное требование заключается в том, что текст калодой процедуры доллен храниться в ядре таким образом, чтобы код, сгенерированный компилятором языка высокого уровня для каждой задачи, взаимодействовал с соответствующим ей контекстом. Паскаль прекрасно под-



1 2 3 4 5 6 7 ... 32

Яндекс.Метрика