М. Бен-Ари - Языки программирования. Практический сравнительный анализ (2000) (1160781), страница 35
Текст из файла (страница 35)
Синхронная модель параллелизма может быть реализована в самом языке программирования или в виде услуги операционной системы: потоки (pipes),
гнезда (sockets) и т.д. Модели отличаются способами, которыми процессы адресуют друг друга, и способом передачи сообщений. Далее мы опишем три языка, в которых методы реализации синхронного параллелизма существенно различны.
12.6. Язык параллельного программирования оссаm
Модель синхронных сообщений была первоначально разработана Хоаром (С. A. R. Ноаге) в формализме, называющемся CSP (Communicating Sequential Processes — Взаимодействующие последовательные процессы). На практике он реализован в языке оссат, который был разработан для программирования транспьютеров — аппаратной многопроцессорной архитектуры для распределенной обработки данных.
В языке оссаm адресация фиксирована, и передача сообщений односторонняя, как показано на рисунке 12.2. Канал имеет имя и может использоваться только для отправки сообщения из одного процесса и получения его в другом:
CHAN OF INT с :
PAR
INT m:
SEQ
-- Создается целочисленное значение m
с! m
INT v:
SEQ
c? v
-- Используется целочисленное значение в v
с объявлено как канал, который может передавать целые числа. Канал должен использоваться именно в двух процессах: один процесс содержит команды вывода (с!), а другой — команды ввода (с?).
Интересен синтаксис языка оссаm. В других языках режим выполнения «по умолчанию» — это последовательное выполнение группы операторов, а для задания параллелизма требуются специальные указания. В языке оссаm параллельные и последовательные вычисления считаются в равной степени важными, поэтому вы должны явно указать, используя PAR и SEQ, как именно должна выполняться каждая группа (выровненных отступами) операторов.
Хотя каждый канал связывает ровно два процесса, язык оссаm допускает, чтобы процесс одновременно ждал передачи данных по любому из нескольких каналов:
[10]CHAN OF INT с : -- Массив каналов
ALT i = O FOR 10
c[i] ? v
-- Используется целочисленное значение в v
Этот процесс ждет передачи данных по любому из десяти каналов, а обработка полученного значения может зависеть от индекса канала.
Преимущество коммуникации точка-точка состоит в ее чрезвычайной эффективности, потому что вся адресная информация «скомпилирована». Не требуется никаких других средств поддержки во время выполнения кроме синхронизации процессов и передачи данных; в транспьютерных системах это делается аппаратными средствами. Конечно, эта эффективность достигается за счет уменьшения гибкости.
12.7. Рандеву в языке Ada
Задачи в языке Ada взаимодействуют друг с другом во время рандеву (rendezvous). Говорят, что одна задача Т1 вызывает вход (entry) e в другой задаче Т2 (см. рис. 12.3). Вызываемая задача должна выполнить accept-оператор для этого входа:
accept Е(Р1: in Integer; P2: out Integer) do
…
end E;
Когда задача выполняет вызов входа, и есть другая задача, которая уже выполнила accept для этого входа, имеет место рандеву.
• Вызывающая задача передает входные параметры принимающей задаче и затем блокируется.
• Принимающая задача выполняет операторы в теле accept.
• Принимающая задача возвращает выходные параметры вызывающей задаче.
• Вызывающая задача разблокируется.
Определение рандеву симметрично в том смысле, что, если задача выполняет accept-оператор, но ожидаемого вызова входа еще не произошло, она
будет заблокирована, пока некоторая задача не вызывет вход для этого accept-оператора*.
Подчеркнем, что адресация осуществляется только в одном направлении: вызывающая задача должна знать имя принимающей задачи, но принимающая задача не знает имени вызывающей задачи. Возможность создания серверов (servers), т. е. процессов, предоставляющих определенные услуги любому другому процессу, послужила мотивом для выбора такого проектного решения. Задача-клиент (client) должка, конечно, знать название сервиса, который она запрашивает, в то время как задача-сервер предоставит сервис любой задаче, и ей не нужно ничего знать о клиенте.
Одно рандеву может включать передачу сообщений в двух направлениях, потому что типичный сервис может быть запросом элемента из структуры данных. Издержки на дополнительное взаимодействие, чтобы возвратить результат, были бы сверхмерными.
Механизм рандеву чрезвычайно сложен: задача может одновременно ждать вызова различных точек входа, используя select-оператор:
select
accept El do ... end El;
or
accept E2 do . . . end E2;
or
accept E3 do . . . end E3;
end select;
Альтернативы выбора в select могут содержать булевы выражения, называемые охраной (guards), которые дают возможность задаче контролировать, какие вызовы она хочет принимать. Можно задавать таймауты (предельные времена ожидания рандеву) и осуществлять опросы (для немедленной реакции в критических случаях). В отличие от конструкции ALT в языке оссаm, select-оператор языка Ada не может одновременно ожидать произвольного числа входов.
Обратите внимание на основное различие между защищенными переменными и рандеву:
• Защищенная переменная — это пассивный механизм, а его операции выполняются другими задачами.
• accept-оператор выполняется задачей, в которой он появляется, то есть он выполняет вычисление от имени других задач.
Рандеву можно использовать для программирования сервера и в том случае, если сервер делает значимую обработку помимо связи с клиентом:
task Server is
begin
loop
select
accept Put(l: in Item) do
-- Отправить I в структуру данных
end Put;
or
accept Get(l: out Item) do
-- Достать I из структуры данных
end Get;
end select;
-- Обслуживание структуры данных
end loop;
end Server;
Сервер отправляет элементы в структуру данных и достает их из нее, а после каждой операции он выполняет дополнительную обработку структуры данных, например регистрирует изменения. Нет необходимости блокировать другие задачи во время выполнения этой обработки, отнимающей много времени.
В языке Ada чрезвычайно гибкий механизм параллелизма, но эта гибкость достигается ценой менее эффективной связи, чем коммуникации точка-точка в языке оссаm. С другой стороны, в языке оссаm фактически невозможно реализовать гибкий серверный процесс, так как каждый дополнительный клиентский процесс нуждается в отдельном именованном канале, а это требует изменения программы сервера.
12.8. Linda
Linda — это не язык программирования как таковой, а модель параллелизма, которая может быть добавлена к существующему языку программирования. В отличие от однонаправленной (Ada) или двунаправленной адресации (occam), Linda вообще не использует никакой адресации между параллельными процессами! Вместо этого процесс может по выбору отправить сообщение в глобальную кортежную область (Tuple Space). Она названа так потому, что каждое сообщение представляет собой кортеж, т. е. последовательность из одного или нескольких значений, возможно, разных типов.
Например:
(True, 5.6, 'С', False)
— это четверной кортеж, состоящий из булева с плавающей точкой, символьного и снова булева значений.
Существуют три операции, которые обращаются к кортежной области:
out — поместить кортеж в кортежную область;
in — блокировка, пока не существует соответствующего кортежа, затем его удаление
(см. рис. 12.4);
read — блокировка, пока не существует соответствующего кортежа (но без удаления его).
Синхронизация достигается благодаря тому, что команды in и read должны определять сигнатуру кортежа: число элементов и их типы. Только если кортеж существует с соответствующей сигнатурой, может быть выполнена операция получения, иначе процесс будет приостановлен. Кроме того, один или несколько элементов кортежа могут быть заданы явно. Если значение задано в сигнатуре, оно должно соответствовать значению в той же самой позиции кортежа; если задан тип, он может соответствовать любому значению этого типа в данной позиции. Например, все последующие операторы удалят первый кортеж в кортежной области на рис. 12.4:
in(True, 5.6, 'С', False)
in(B: Boolean, 5.6, 'С', False)
in(True, F: Float, 'С', Ё2: Boolean)
Второй оператор in возвратит значение True в формальном параметре В; третий оператор in возвратит значения 5.6 в F и False — в В2.
Кортежная область может использоваться для диспетчеризации вычислительных работ для процессов, которые могут находиться на разных компьютерах. Кортеж ("job", J, С) укажет, что работу J следует назначить компьютеру С. Каждый компьютер может быть заблокирован в ожидании работы:
in("job", J: Jobs, 4); -- Компьютер 4 ждет работу
Задача диспетчеризации может «бросать» работы в кортежную область. С помощью формального параметра оператора out можно указать, что безразлично, какой именно компьютер делает данную работу:
out("job", 6, С: Computers); -- Работа 6 для любого компьютера
Преимущество модели Linda в чрезвычайной гибкости. Обратите внимание, что процесс может поместить кортеж в кортежную область и завершиться;
только позднее другой процесс найдет этот кортеж. Таким образом, Linda-программа распределена как во времени, так и в пространстве (среди процес-сов, которые могут быть на отдельных ЦП). Сравните это с языками Ada и oссаm, которые требуют, чтобы процессы непосредственно связывались друг с другом. Недостаток модели Linda состоит в дополнительных затратах на поддержку кортежной области, которая требует потенциально неограниченной глобальной памяти. Хотя кортежная область и является глобальной, бы-ли разработаны сложные алгоритмы для ее распределения среди многих процессоров.
12.9. Упражнения
1. Изучите следующую попытку решать проблему взаимного исключения в рамках модели с разделяемой памятью, где В1 и В2 — глобальные булевы переменные с начальным значением «ложь»:
task body T1 is
| Ada |
loop
B1 :=True;
loop
exit when not B2;
B1 := False;
B1 :=True;
end loop;
Critical_Section;
B1 := False;
Non_Critical_Section;
end loop;
end T1;
task body T2 is
begin
loop
B2 := True;
loop
exit when not B1;
B2 := False;
B2 := True;
end loop;
Critical_Section;
B2 := False:
Non_Critical_Section;
end loop;
end T2;
Каков смысл переменных В1 и В2? Могут ли обе задачи находиться в своих критических областях в какой-нибудь момент времени? Может ли программа блокироваться? Достигнута ли жизнеспособность?
2. Проверьте решение проблемы взаимного исключения с помощью семафора. Покажите, что во всех чередованиях команд в любой момент времени в критической области может находиться не более одной задачи. Что можно сказать относительно взаимоблокировки, жизнеспособности и справедливости?
3. Что произойдет с решением проблемы взаимного исключения, если семафору задать начальное значение больше 1?
4. Попробуйте точно определить справедливость. Какая связь между справедливостью и приоритетом?
5. Как бы вы реализовали семафор?
6. Как диспетчер работ Linda обеспечивает, чтобы конкретная работа попадала на конкретный компьютер?
7. Напишите Linda-программу для умножения матриц. Получение каждого векторного произведения считайте отдельной «работой»; начальный процесс диспетчеризации заполняет кортежную область «работами»; рабочие процессы удаляют «работы» и возвращают результаты; заключительный процесс сбора удаляет и выводит результаты.
8. Переведите Linda-программу умножения матриц на язык Ada. Решите проблему дважды: один раз с отдельными задачами для диспетчера и сборщика и один раз в рамках единой задачи, которая выполняет обе функции в одном select-операторе.
4Программирование
больших
систем
Глава 13
Декомпозиция программ
И начинающие программисты, и руководители проектов, экстраполируя ту простоту и легкость, с какой один человек может написать отдельную программу, часто полагают, что разработать программную систему также просто. Нужно только подобрать группу программистов и поручить им работу. Однако существует глубокая пропасть между написанием (небольших) программ и созданием (больших) программных систем, и многие системы поставляются с опозданием, с большим количеством ошибок и обходятся в несколько раз дороже, чем по первоначальной оценке.
Разработка программного обеспечения (software engineering) имеет дело с методами организации и управления группами разработчиков, с системой обозначений и инструментальными средствами, которые поддерживают этапы процесса разработки помимо программирования. Они включают этапы технического задания, проектирования и тестирования программного обеспечения.
В этой и двух последующих главах мы изучим конструкции языков программирования, которые разработаны для того, чтобы поддерживать создание больших программных систем. Не вызывает сомнений компромисс: чем меньшую поддержку предлагает язык для разработки больших систем, тем больше потребность в методах, соглашениях и системах обозначений, которые являются внешними по отношению к самому языку. Так как язык программирования, несомненно, необходим, кажется разумным включить поддержку больших систем в состав самого языка и ожидать, что компилятор по возможности автоматизирует максимальную часть процесса разработки. Мы, разработчики программного обеспечения, всегда хотим автоматизировать чью-нибудь чужую работу, но часто приходим в состояние неуверенности перед тем, как включить автоматизацию в языки программирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
