Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 136
Текст из файла (страница 136)
Взаимодействие. Параллельные программы должны взаимодействовать между собой. Такое взаимодействие, как правило, осуществляется через совместно используемую память с обгдими объектамн данных, доступными для каждой из параллельных программ, или через сообгцеиия, когда каждая параллельная программа имеет собственную копию объекта данных и передает значения данных другим параллельным програмлгам.
Синхронизация. Параллельные программы должны быть способны упорядочивать выполнение своих различных потоков управления. Хотя для мно- По-внглнйскн чГогкч — вилка, рввветвленне. — Примеч. лер. обьекту данных. Чтобы рассматривать параллелизм в языках программиро- , следует обратиться к следующим пяти понятиям. Определение переменных. Переменные могут быть ианеияемыми или неиз- меняемыми. Изменяемые переменные — это обычные переменные, объяв- ляемые в большинстве последовательных языков программирования. Им можно присваивать различные значения, которые в процессе выполнения программы могут меняться.
Неизменяемой переменной значение можно присвоить только один раз. Смысл существования таких переменных за- ключается атом, чтобы избежать проблемы синхронизации. Когда такой пе- ременной присвоено некоторое значение, любая задача может обратиться к этой переменной и получить правильное значение, Параллельная композиция. Выпол пение движется от одного оператора ксле- дующему. Дополнительно к последовательным и условным операторам по- следовательных языков программирования нам нужно добавить параллель- ный оператор, создающий дополнительный поток управления, который начинает выполняться. Примерами таких структур являются оператор апб, описанный в разделе 11.2.1, и функция операционной системы 1огк', исполь- зуемая в языке С.
Структура программы. Параллельные программы в основном следуют од- ной из следующих двух моделей выполнения. а) Они могут быть трансформационными, когда целью является трансформация входных данных в соответствующие выходные значения. Параллелизм применяется для ускорения процесса вычисления, например быстрого перемножения матриц путем параллельного перемножения нескольких ее сечений. 11.2. Параллельное программирование 495 гих приложений подходит недетерминированное поведение, некоторым все же требуется определенная упорядоченность. Например, можно создать компилятор, в котором сканер и анализатор будут работать параллельно, но при этом обязательно должно выполняться требование, что сканер считывает каждую лексему до того, как анализатор начнет ее обрабатывать.
Описанный выше механизм взаимодействия позволит осуществить это упорядочение. В следующих подразделах мы обсудим некоторые из этих концепций более подробно. 11.2.1. Параллельное выполнение Основной механизм, вводящий параллельное выполнение в язык программирования, — это специально созданная конструкция, допускающая такое параллельное выполнение. Оператор ап6 оператор, апв оператор, ап6 . апв оператор„ выполняет поставленную задачу, и его семантика заключается в том, что каждый из операторов оператор, выполняется параллельно. Оператор, следующий за таким оператором ап6, не начинает выполняться, пока не будут выполнены все параллельные операторы. Хотя эта конструкция концептуально и проста, она предоставляет всю мощь параллельных вычислений, которую мы хотели бы иметь.
Например, если операционная система включает в себя задачу считывания с терминала, задачу вывода информации на экран монитора и процесс выполнения пользовательской программы, мы могли бы определить эту операционную систему следующим образом: са11 ПеаоРгосееа апв са11 Иг11ергосеаа ап6 са11 ЕхесоееэаегРгоргав Последовательности для параллельного выполнения — это лишь часть проблемы. Корректттое управление данными — другая ее часть.
Рассмотрилт следующий фрагмент: х;-1 хе=2 ап6 у = хтх 1*) ршпг1у), Поскольку оба помеченных звездочкой (*) оператора могут выполняться параллельно, мы не можем предсказать, какой из них завершится первым. Следовательно, переменной у может быть присвоено значение 2 (если оператор присваивания значения переменной у выполнится первым), 4 (если оператор присваивания значения переменной х выполнится первым) или даже 3 (если оператор присваивания значения переменной х завершится между двумя обращениями к переменной х в операторе присваивания значения переменной у). Мы должны скоординировать доступ параллельных программ к данным. Эту тему мы обсудим несколько позже прп рассмотрении семафоров в разделе 11.2.5.
Реализация. Существует два основных способа реализации конструкции ап6. Заметим, что если все параллельные задачи могут выполняться параллельно, то не делается никаких предположений о порядке их выполнения. Мы можем просто 496 Глава 11. Распределенная обработка данных выполнить их последовательно. Если исходная конструкция апд корректна, то замена апб на оператор последовательного выполнении «; в и оператор ыЬз1е привела бы к корректному выполнению. Например, приведенный выше пример мог бы быть переписан компилятором как нЫ1е МогеТо0о ео МагеТоэо:" Га1зе: са11 йеаоргосезз; са11 ИгыеРгосезз: са11 Ехесигевзегргойгап епе Если бы, например, подпрограмма йеабргосезв пыталась прочесть данные, которые еще не готовы для обработки, опа могла бы просто установить значение переменной МогеТо00 равным Ггоэ и вЕрНутьСя назад.
Этот цикл будет гювторяться до тех пор, пока не завершится каждая из подпрограмм, Более прямой способ реализовать эту конструкция заключается в использовании элементарных операций операционной системы, предназначенных для организации параллельного выполнения. Например, в С компилятор мог бы выполнить функцию Тоги, которая создает два выполняемых параллельно процесса. 1<аждый из этих процессов продолжал бы выполняться, пока не завершится.
Код, сгенерированный компилятором С, мог бы выглядеть примерно следующим образом'. Гоге йеаоргосезз. Тоги Иг1гергосезз: Гогй Ехесигепзегргойгаяс иа!1 !* идеи, пока не внпопнятся все 3 програиии *Г Возможности поддержки параллельных задач еще достаточно редки в языках программирования высокого уровня. Ни один из широко распространенных языков не предоставляет описанную здесь конструкцию апс1. Только Ас)а позволяет создавать задачи с параллельным выполнением, хотя тесная связь языка С с операционной системой позволяет С-программам вызывать функцию операционной системы Тоги для создания параллельных задач. 11.2.2. Охраняемые команды Второй класс конструкций имеет отношение к недетерминированному выполненикб когда невозможно определить, какой оператор должен будет выполняться следующим.
Конструкция апс1, вообще говоря, является детерминированной, поскольку в следующий момент времени на данном компьютере фактически будет выполняться только один из параллельных операторов. Тем не менее концепция оператора апо' относится к параллельному выполнению, а ее реализацией часто является последовательный проход через все операторы. В 1970 г. Дейкстра (ЩЫга) предложил действительно недетерминированную концепцию охраняемых команд как средство упрощения, разработки и верифика- втгп' пример только юстичио корректен, поскольку ляы старались слопать его максимально ярогтыль Иа самом лелс колгнилятор С сначала бы лплжеи был вызвать функцию Гоги лля созлвния лнух процессов, а затем вызнаешь функцию ехес лля нх выполнения. 11.2. Параллельное программирование 497 20 Улица '.
Пункт назначения " Точка начала маршрута Я Я Я х и Ф е е е е « < со аъ ю Я Я Я х х х е е Ж « < Оъ г ч'э Я Я х х Ф Ф Ю Рис. 11.2. Недетерминированное странствие по городу В качестве простого примера рассмотрим город, кварталы которого образуются из авеню, идущих в направлении с севера на юг, и улиц, идущих с запала на восток (рис. 11.2). Допустим, вы находитесь на пересечении Третьей авеню и Двенадцатой улицы и вам надо попасть ца пересечение Десятой авен ю и Двалцатой улицы, 1(акой путь следует выбрать? Если попросить запрограммировать решение на некотором условном языке, то типичными будут два возможных варианта программ: Вариант ! Двигаемся на восток от Третьей авеню до Десятой авеню Двигаемся на север от Двенадцатой улицы до Двадцатой улицы Вариант 2 Двигаемся на север от Двенадцатой улицы до Двадцатой улицы Двигаемся на восток от Третьей авеню до Десятой авеню ции программ [371, До сих пор все рассмотренные нами в атой главе структуры управления являются детерминированными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
