Технология программирования для распределенных параллельных систем: Курс лекций

Санкт-Петербургский государственный университет

Ю. К. Демьянович, О.Н.Иванцова

ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ ДЛЯ РАСПРЕДЕЛЕННЫХ ПАРАЛЛЕЛЬНЫХ СИСТЕМ Курс лекций

Санкт-Петербург 2005

ВВЕДЕНИЕ Высокопроизводительные вычисления необходимы для ряда важнейших задач, в числе которых задачи прогнозирования погоды и климата в целом, и в особенности, их катастрофических изменений (возникновения ураганов, тайфунов, резких изменений температуры и т.п.), задачи геологии и геофизики (предсказания землетрясений, вулканических извержений и т.д.), задачи астрономии и астрофизики (предсказания поведения Солнца, столкновений метеоритов и болидов с Землей, обоснование космогонических гипотез), задачи, связанные с биологией и с чрезвычайно значимой для человека областью — с медициной (последнее достижение — расшифровка генома человека — один из ярчайших примеров применения высокопроизводительных вычислительных систем). Конечно, имеется много других примеров сложных задач, решение которых без высокопроиводительных параллельных вычислительных систем невозможно. Высокопроизводительные вычисления в настоящее время не мыслятся без распараллеливания, ибо наиболее мощные вычислительные системы имеют сотни и тысячи параллельных процессоров (см., например, регулярно обновляемоый в Internet список TOP500, содержащий перечень наиболее мощных компьютеров в мире, чтобы убедиться в том, что все компьютеры в этом списке — параллельные системы). Благодаря распараллеливанию удается достичь производительности в десятки терафлопс (1012 операций в секунду с плавающей точкой), но для наиболее сложных современных задач и этого недостаточно: требуются вычислительные мощности с быстродействием в десятки пентафлопс. Достижение таких скоростей трудно представить без распараллеливания (к моменту написания этого введения уже достигнуто быстродействие 145 терафлопс). Распараллеливание алгоритмов и написание параллельных программ — весьма сложное дело. Причины возникающих трудностей различны: с одной стороны, идеология распараллеливания трудно воспринимается после приобретения навыков последовательного программирования, а с другой стороны, методы распараллеливания задач недостаточно разработаны. Заметим, что прямое численное моделирование соответствующих физических или физико-химических явлений, которые по3

существу представляют собой огромное количество физических процессов, взаимодействующих друг с другом, является наиболее естественным путем моделирования. Без связи с распараллеливанием моделирование процессов в том или ином смысле рассматривалось давно: метод частиц в ячейках, метод конечных элементов, метод сеток и другие методы, фактически, приводят к похожему результату. Конечно, распараллеливание несет в себе большие трудности, но и вселяет значительные надежды. Исследования в этой области, практическое освоение теоретических результатов, создание соответствующего программного обеспечения, отладка программ на параллельных системах и проведение эффективных вычислений представляются чрезвычайно важными. Предлагаемый курс лекций посвящен в основном параллельному программированию на вычислительных системах с распределенной памятью, хотя часть представленной информации можно отнести и к системам с общей памятью. Использование параллельных процессов существенно усложняет программирование: эффективность увеличивается с увеличением независимости процессов, но из-за этого приходится ослаблять контроль за вычислениями. Процессы находятся в постоянной конкурентной борьбе за ресурсы, но поскольку в совокупности они решают одну задачу, то необходимы моменты синхронизации и обмена полученной информацией. Для написании параллельных программ используются специальные средства, которые могут предоставляться в виде специальных библиотек или расширений известных языков (например, библиотеки MPI, Open MP, PVM, язык Linda для Fortran, C, C++); однако, основное внимание следует уделять принципам использования этих средств: именно эти принципы рассматриваются в первую очередь в данном курсе лекций. Поскольку курс расчитан на 36 лекционных часов, многие полезные аспекты здесь не рассмотриваются в надежде, что любознательный читатель сможет почерпнуть недостающие сведения из книг [1-7], содержание которых частично отражено в данном курсе лекций. Курс лекций содержит шесть глав, первая из которых посвящена программированию с использованием передачи сообщений, вторая — мониторам и условным переменным; в третьей главе вводится понятие рандеву и рассматриваются активные мониторы, а четвертая глава посвящена операторам взаимодействия. В пятой 4

главе дается представления о языках Occam, CSP, Linda. Наконец, шестая глава посвящена удаленному вызову процедур и взаимодействию процессов, вопросам неделимости операций, устранению взаимного вмешательства процессов, стратегиям планирования и критическим переменным. Во второй главе рассматривается задача о критической секции, активные блокировки, алгоритм разрыва узла, построению барьеров. В третьей главе излагаются вопросы синхронизации с помощью семафоров. Рассматриваются решения задач “об обедающих философах”, “о читателях и писателях”, “кратчайшее расстояние” и некоторых других. В лекциях широко использованы книги [1–6], а также Интернет и книга [7], из которых почерпнуты примеры и стиль изложения. Авторы курса надеются на быстрое усвоение читателями изложенных первоначальных сведений по методам параллельного программирования, что позволит им легко перейти к чтению более солидных книг, перечисленных в списке рекомендуемой литературы. Данная работа частично поддержана грантами РФФИ 04-0100692, 04-01-00026 и НШ-2268.2003.1.

5

Глава 1. ПРОГРАММИРОВАНИЕ С ИСПОЛЬЗОВАНИЕМ ПЕРЕДАЧИ СООБЩЕНИЙ § 1. О распределенном программировании В настоящее время широкое распространение получили вычислительные системы (ВС) — архитектуры с распределенной памятью. Зачастую это многомашинные комплексы и сети, а иногда — гибридные ВС, такие как сеть из рабочих станций и мультипроцессорных систем. В этом случае процессоры (вычислительные модули, кратко – ВМ) имеют собственную локальную память и общаются между собой с помощью коммуникационной сети, а не через разделяемую (т.е. общую) память; предполагается, что общая память отсутствует. Наиболее употребительны следуюшие виды коммуникационных сред: 1) масштабируемый когерентный интерфейс SCI (Scalable Coherent Interface); основными его элементами служат узлы SCI, представляющие собой стандартизованные фрагменты кэшпамяти, через которые ВМ с помощью адаптеров общаются с сетью; 2) коммуникационная среда MYRINET, в которой передачи осуществляются по схеме адаптер ВМ-источника – коммутаторы Myrinet – адаптер ВМ-приемника; 3) коммуникационная среда Raceway (с использованием кристалла-коммутатора Cypress Raceway Crossbar и адаптеров, работающая по схеме порт коммутатора – шина ВМ), 4) коннектор шин PCI: SRC 3266 DE (Serbing Ring Connection для PCI), позволяющая соединить до 256 шин PCI; 5) Memory Channel фирмы DEC для кластерных систем; 6) коммуникационные среды на базе транспьютероподобных микропроцессоров, характерными чертами которых является наличие специальной сети для инициализации и линий стробирования для передачи синхросигнала; 7) широко используются различные шинные структуры. Вычислительные модули поддерживают процессы, а взаимодействие между процессами поддерживает коммуникационнная среда с использованием каналов, связывающих отдельные процессы. Эти

6

каналы можно рассматривать как абстракцию сетей связи, обеспечивающих физическую связь между вычислительными модулями. Адаптеры, линки и коммутаторы обычно являются важными элементами коммуникационной среды. Для удобства программирования вводятся специальные операции, которые служат для передачи сообщений. Параллельные программы, использующие передачу сообщений называются распределенными программами. Заметим, что распределенные программы могут работать и на ВС с разделяемой (общей) памятью: в этом случае каналы генерируются с помощью разделяемой памяти. В распределенных программах каналы чаще всего являются важными, но не всегда единственными объектами, разделяемыми вычислительными модулями; кроме каналов могут быть общими также некоторые другие устройства (например, принтеры). Пока что будем считать, что каждый процесс выполняется на своем вычислительном модуле (иначе говоря, поток команд, обрабатываемых вычислительным модулем, рассматривается как отдельный процесс). В этом случае переменная оказывается локальной по отношению к своему процессу, который, таким образом, является ее владельцем (caretaker). Эта переменная никогда не должна становится объектом параллельного доступа, а значит она нуждается в использовании механизма взаимного исключения. Общение процессов между собой происходит разными путями; при этом должна производиться синхронизация межпроцессорного взаимодействия. Значение синхронизации здесь не меньше, а возможно и больше, чем при программировании систем с разделяемой памятью: как известно, важно постоянно поддерживать когерентность иерархической памяти системы с распределенной памятью. Взаимодействие процессов на разных стадиях может быть – асинхронным (неблокирующим), – синхронным (блокирующим). Различают: 1) асинхронную передачу сообщений, 2) синхронную передачу сообщений, 3) удаленный вызов процедур (remote procedure call — RPC), 4) рандеву.

7

Эти механизмы эквивалентны в том смысле, что программа, написанная с помощью одного из них, может быть переписана в программу, использующую другой механизм; однако, использование различных механизмов в различных обстоятельствах ведет к различной эффективности программной реализации алгоритма. Замечание. В дальнейшем применяется программная нотация, которая достаточна для описания примеров программ; она представляется достаточно ясной и не требующей формализации. § 2. Асинхронная передача сообщений Для асинхронной передачи сообщений канал является очередью FIFO (First In – First Out); при этом сообщения могут быть отправлены, но еще не получены. Объявление канала имеет вид chan ch(type1 id1 , . . . , typen idn );

(1)

Здесь ch — имя канала, typei — тип поля (обязателен), idi — имя поля (не является обязательным). Пример 1. chan input(char); chan disk_access(int cylinder, int block, int count, char*buffer); Здесь объявлены два канала. Первый канал input используется для передачи односимвольных сообщений. Второй канал disk_access содержит сообщения с четырьмя полями: номер цилиндра, номер блока, число символов, адрес буфера. Можно использовать массив каналов: chan result[n](int); здесь индексы (номера каналов) имеют значения от 0 до n-1. Отправка сообщения по каналу ch (см. (1)) имеет вид send ch(expr1 , . . . , exprn ); здесь выражение expri должно иметь тип typei . Выполнение операции send состоит в 1) в вычислении выражений expri ; 8

(2)

2) в отправке сообщения в конец очереди, связанной с каналом ch. Теоретически очередь не ограничена; поэтому посылка сообщения не вызывает задержку, и следовательно операция send является неблокирующим примитивом. Процесс получающий сообщение из канала выполняет операцию receive: receive ch(var1 , . . . , varn ); (3) Переменные должны иметь тот же тип, что и поля в объявлении канала (1). Процесс, получающий сообщение по команде (3), приостанавливается до тех пор, пока в очереди канала не появится хотя бы одно сообщение. Итак, операция receive может вызвать задержку — поэтому это блокирующий примитив; процесс, принимающий сообщение, не обязан использовать опрос канала для получения сообщения. Доступ к каждому каналу — неделимое действие; каждое переданное сообщение будет принято в том порядке, в каком отправлено (канал является очередью типа FIFO). Пример 2. Формирование строк из символов. chan input(char), output(char[MAXLINE]); process Char_to_Line{ char line[MAXLINE]; int i=0; while(true){ receive input(line[i]); while(line[i]!=CR and i<MAXLINE){ # line[0:i-1] содержит i входных символов i=i+1; receive input(line[i]); } line[i]=EOL; send output(line); i=0; } } П о я с н е н и я : сначала объявляется канал input для отдельных символов и канал output для получения строк. Далее объявляется процесс Char_to_Line, в котором, пока параметр “истина”, 9

получаем значения из канала input в переменную line[0] и до тех пор пока line[i] не совпадет с CR (символ возврата каретки) и i<MAXLINE присваиваем i=i+1 и получаем очередное line[i] из канала input. По окончании цикла присваиваем line[i] значение EOL и посылаем полученную строку в канал output. Каналы используются процессами совместно и потому объявляются глобальными относительно всех процессов (см. предыдущий пример). Любой процесс может отправлять данные в любой канал и принимать из любого канала. Если канал используется многими процессами, то он называется портом (или общим почтовым ящиком). В случае, когда у канала имеется только один получатель и много отправителей, то он называется входным портом (или индивидуальным почтовым ящиком), а если у канала много получателей и один отправитель его можно называть выходным портом. Наконец, если у канала один отправитель и один получатель, то он называется каналом связи. Замечание. При выполнении команды receive часто процесс вынужден ждать; однако, иногда предусматривается выполнение другой работы, для которой не требуется предполагаемое сообщение из затребованного канала. Процесс может определить пуста ли очередь канала с именем ch с помощью вызова empty(ch) который возвращает значение True, если канал пуст, и значение False — в противном случае. Однако, при таком запросе может получится ложная ситуация: при появлении значения True в действительности очередь может оказаться непустой, и, наоборот, при получении значения False к моменту запроса очередь уже может оказаться пустой. Таким образом, вызов empty следует применять с осторожностью. § 3. Сортировка, фильтры Фильтром называется процесс, получающий значения из одного или нескольких входных каналов, и отправляющий значения в выходные каналы (один или более).

10

Для иллюстрации рассмотрим процесс сортировки n чисел в порядке возрастания. Пусть имеется два канала: input — входной канал, output — выходной и sent[i] — i-е значение, отправляемое в output. Процесс сортировки может быть описан следующим образом: SORT: ( ∀ i: 1≤i
11

Пусть n является степенью двойки (n = 2k ). Для построения сортирующей сети упомянутый процесс GLUE скопируем в 2k−1 вычислительных модулей, подав на них по паре соседних элементов: в результате они соединятся в цепочки из двух упорядоченных чисел. Далее в 2k−2 вычислительных модулей направим пары этих цепочек, в результате получим 2k−2 упорядоченных цепочек по четыре числа. Продолжая процесс в конце концов получим дерево сортирующей сети, корень которого выдаст полностью отсортированный поток (см. рис. 1). Высота дерева log2 n, а ширина n/2. В сети имеются каналы; входные и выходные каналы должны быть разделяемыми.

Рис. 1. Распараллеливание процесса слияния Пример 3. Фильтр для слияния двух входных потоков. chan in1(int), in2(int), out(int); process GLUE{ int v1, v2; receive in1(v1); receive in2(v2); # получены первые два входных числа # меньшее из чисел отправить # в выходной канал и повторить while(v1!=EOS and v2!=EOS){ 12

if (v1<=v2) {send out(v1); receive in1(v1);} else # (v2
непустого входного канала

receive in2(v2);}

receive in1(v1);} выходной канал

Замечание. Процессы такого типа могут соединяться различными способами; требуется лишь, чтобы выход удовлетворял требованиям входа. § 4. Клиенты и серверы. Файловые системы Типичной схемой в параллельных программах является связь типа клиент-сервер. Процесс-клиент 1) запрашивает сервис; 2) ждет обработки запроса. Процесс-сервер 1) многократно ожидает запрос; 2) обрабатывает его; 3) посылает ответ. От клиента к серверу и обратно существует двунаправленный поток информации. Между клиентом и сервером возникают такие же отношения как между программой, вызывающей подпрограмму, и самой подпрограммой в последовательном программировании. Аналогично тому, как подпрограмма может быть вызвана несколькими программами, так и сервер может быть вызван многими клиентами. 13

Запросы каждого клиента должны обрабатываться независимо; они могут могут обрабатываться параллельно, однако, параллелизм ограничивается возможностями системы. Взаимодействие по схеме клиент-сервер происходит в операционных системах, объектно-ориентированных системах, сетях, базах данных и т.п. Наиболее типичная ситуация — чтение и запись файла. Модуль файлового сервера производит операции чтения (read) и записи (write). Если процесс-клиент хочет получить доступ к файлу на сервере, то он вызывает эти операции. На системе с разделяемыми файлами подобные операции реализуются соответствующими процедурами. При этом важно, чтобы лишь одному процессу-клиенту из обратившихся к данному файлу в один и тот же момент времени разрешалось писать в файл; остальные могут лишь читать из него. В распределенной системе клиенты и серверы обычно располагаются на различных вычислительных модулях. Такая ситуация возникает, например, при запросе через сеть World Wide Web; это получается, когда пользователь открывает на Web-браузере новый URL-адрес. URL-адрес косвенно указывает на другой вычислительный модуль, на котором располагается страница; последняя доступна для процесса-сервера, где располагается страница. Процесссервер может существовать или создаваться в момент запроса; в результате запрошенная страница возвращается на вычислительный модуль, где находится процесс-клиент (заметим, что при этом могут создаваться дополнительные процессы на промежуточных вычислительных модулях). На системе с разделяемой памятью сервер реализуется набором подпрограмм, которые создаются с использованием механизмов взаимного исключения и условной синхронизации. На системах с распределенной памятью сервер реализуется в виде одного или нескольких процессов, выполняющихся не на клиентских машинах. Сервер представляет собой многопоточную программу с одним потоком для каждого клиента.

14

Глава 2.

МОНИТОРЫ И УСЛОВНЫЕ ПЕРЕМЕННЫЕ

§ 1. Мониторы Мониторы представляют собой программные модули. Как и семафоры они являются мощным средством синхронизации; при этом они реализуются столь же эффективно. Семафоры представляют собой низкоуровенный механизм синхронизации: они глобальны по отношению ко всем процессам и это доставляет значительные неудобства. В противоположность семафорам мониторы обеспечивают большую структурированность и представляют собой механизм абстракции данных. Монитор содержит переменные, хранящие состояния объекта, и имеет набор операций (процедур) для работы с объектом. Взаимное исключение обеспечивается тем, что процедуры в одном мониторе не могут выполняться параллельно. Параллельная программа использует – активные процессы; – пассивные мониторы. При условии, что все разделяемые переменные находятся внутри монитора, два процесса взаимодействуют, вызывая процедуры одного монитора. В результате получается удобная модульность: – процесс, вызывающий процедуру монитора, может не знать о конкретной реализации процедуры; – программист монитора может не знать о конкретных способах использования монитора и изменять его “начинку”, сохраняя лишь видимую сторону процедур и результаты их работы. § 2. Структура монитора Монитор состоит из интерфейса и тела: – интерфейс определяет предоставляемые операции (методы); – тело содержит переменные (так называемые постоянные переменные), определяющие состояние ресурса и процедуры, реализующие интерфейс. Хотя в различных языках мониторы объявляются и создаются по-разному, будем считать монитор статичным объектом вида: 15

monitor Monname{ [объявление постоянных переменных] [операторы инициализации] [процедуры] } Процедуры реализуют видимые операции. Постоянные переменные разделяются всеми процедурами тела монитора (они называются постоянными, ибо существуют все время существования монитора). Монитор обладает тремя свойствами: 1) вне монитора видны только имена процедур, которые следует вызывать для изменения состояния ресурса, представленного теми или иными постоянными переменными, например, call Monname.opname(arguments), где opname — имя одной из операций (процедур) с аргументами arguments; 2) операторы внутри монитора не могут обращаться к переменным вне монитора; 3) постоянные переменные инициализируются до вызова его процедур. Монитор отличается от механизма абстракции данных в языках последовательного программирования тем, что совместно используется параллельными процессами (однако, каждая процедура монитора не может работать одновременно для нескольких процессов). § 3. Взаимное исключение в мониторе Обычно взаимное исключение в мониторе происходит неявно, т.е. его не нужно специально программировать при вызове монитора. Монитор при неявном исключении организуется так, что если процесс вызывает процедуру монитора, то 1) она становится активной; 2) в любой момент времени активной может быть только один экземпляр данной процедуры монитора (два или более процессов не могут работать одновременно с одной процедурой монитора); 16

3) программист, использующий монитор, не вмешивается и не отслеживает упомянутое взаимное исключение. § 4. Условные переменные В мониторах используются так называемые условные переменные. Условная переменная служит для остановки процесса, вызывающего монитор, в том случае, когда нормальное выполнение этого процесса в мониторе невозможно до перехода монитора в нужное состояние. Условную переменную используют и для запуска приостановленного процесса. Объявление условной переменной имеет вид: cond cv; Таким образом, cond — новый тип данных. Значением условной переменной является очередь приостановленных процессов (очередь задержки). В начале эта очередь пуста. Может быть объявлен массив условных переменных: cond cv[n]; Условные переменные можно объявлять и использовать только в пределах мониторов. Процесс не может обращаться непосредственно к условной переменной; он имеет лишь косвенный доступ к ней. Имеются следующие команды для работы с условной переменной: 1) процесс запрашивает состояние очереди: empty(cv); (возвращается “истина”, если очередь пуста); 2) процесс блокируется на условной переменной wait(cv); (в результате процесс ставится в очередь, соответствующую этой переменной, причем у вызывающего процесса отбирается исключительный доступ к монитору); 3) процесс, заблокированный на условной переменной cv, запускается оператором signal(cv); (если очередь пуста никакие действия не производятся, иначе — запускается процесс, находящийся в начале очереди). Итак, процессы wait и signal обеспечивают порядок сигнализации FIFO: 17

– процессы приостанавливаются в порядке вызовов wait; – процессы запускаются в порядке вызовов signal. § 5. Способы выполнения операции сигнализации Выполнение операции signal возможно процессом, работающем в мониторе и вызывавшем некоторую процедуру. Поскольку signal, вообще говоря, запускает другой процесс, то может получиться, что данную процедуру выполняют одновременно два процесса, что невозможно по определению монитора. Разрешение этого противоречия возможно с помощью использования одной из двух стратегий, определяемых при создании операции signal: 1) SC — “сигнализировать и продолжить” (signal and continue): сигнализирующий процесс продолжает работу, а процесс, получивший сигнал (и находящийся в очереди FIFO), выполняется после заверщения сигнализирующего процесса; 2) SW — “сигнализировать и ожидать” (signal and wait): сигнализирующий процесс приостанавливается, а процесс, получивший сигнал выполняется сразу. Стратегия “сигнализировать и продолжить” не прерывает обслуживания. Процесс, выполнивший операцию signal, сохраняет исключительный доступ к процедуре монитора до своего завершения, а процесс, получивший сигнал, будет иметь исключительный доступ к этой процедуре монитора сразу после завершения вызвавшего процесса. Стратегия “сигнализировать и ожидать” означает прерывание сигнализирующего процесса и немедленное начало выполнения вызванного процесса с возобновлением прерванного процесса после завершения вызванного. В этой стратегии имеются различные варианты выполнения: поскольку сигнализировавший процесс приостанавливается сразу, то это значит, что он помещается в очередь; может быть вариант, когда он помещается не в конец очереди, а в начало (это называется “сигнализировать и срочно ожидать”). Кроме того, возможны различные варианты поведения в случае, если вызванный процесс в свою очередь вызовет другой процесс. Иллюстрация работы монитора представлена на рис. 2.

18

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

Рис. 2. Работа монитора В качестве примера приведем реализацию семафора с помощью монитора. monitor Semaphore { int s=0; # s больше или равно нуля cond pos; # получает сигнал при s больше нуля procedure Psem(); { while (s==0) wait(pos); s=s-1; } procedure Vsem(); { s=s+1; signal(pos); # запуск самого "старого" процесса } } Здесь s — целочисленная переменная, представляющая значение семафора. Если s=0, то вызов процедуры Psem приводит к приостановке вызвавшего процесса на условной переменной pos (т. е. процесс 19

попал в очередь), а если s>0, то вызов этой процедуры ведет к уменьшению s на единицу. Вызов процедуры Vsem приведет к увеличению s на единицу и посылке сигнала на условную переменную pos, который воспринимается как сигнал к запуску очередного (первого в очереди на канале pos процесса). В случае стратегии “сигнализировать и продолжить” (SC) продолжается выполнение сигнализирующего процесса, а очередной (в канале pos) процесс готовится к захвату позиций (это произойдет после окончания сигнализирующего процесса). В случае стратегии “сигнализировать и ждать” (SW) происходит переход вызвавшего процесса в состояние ожидания, а очередной процесс (первый в очереди pos) захватывает ресурс и выполняется сразу, уменьшая значения семафора s. Замечание. При стратегии SC запускаемый процесс должен перепроверить значение s семафора и убедиться, что оно все еще положительно: это необходимо делать, поскольку в период времени с момента посылки сигнала до окончания вызвавшего процесса может другой процесс из очереди входа вызвать процедуру Psem и уменьшить s. Приведем другой вариант представления семафора с помощью монитора. monitor FIFOsemaphore { int s=0; cond pos; procedure Psem() { if (s==0) wait(pos); else s=s-1; } procedure Vsem() { if (empty(pos)) s=s+1; else signal(pos); } 20

} Примененный метод называется “методом передачи условия” : здесь в случае операций signal и wait значение семафора не меняется; это приводит к тому, что значение s передается тому процессу, который семафор запускает. Сравним операции wait и P, а также signal и V. Сходство операций в том, что операция wait аналогично P приостанавливает процесс, а signal аналогично V его запускает, а отличия состоят в следующем: 1) операция wait всегда приостанавливает процесс, в то время как операция P это делает лишь, если значение семафора равно нулю; 2) операция signal не производит никаких действий, если нет процессов приостановленных на условной переменной (т. е. факт выполнения операции signal не запоминается), в то время, как операция V либо запускает процесс, либо увеличивает значение семафора. Замечание. В дальнейшем будем предполагать, что используется стратегия SC, т. е. стратегия “сигнализировать и продолжить” (signal and continue). § 6. Операции с условными переменными Здесь приведен полный список операций с условными переменными, используемый в дальнейшем. Все приводимые ниже операции естественны и достаточно легко реализуются: они представляют собой операции с очередями. Т а б л и ц а № 1. Команда wait(cv) wait(cv,rank) signal(cv) signal_all(cv) empty(cv) minrank(cv)

Содержание

команды

Ждать в конце очереди Ждать в порядке возрастания значения ранга (rank) Запустить процесс из начала очереди и продолжить Запустить все процессы очереди и продолжить Истина, если очередь пуста, иначе — ложь Значение ранга процесса в начале очереди ожидания

21

Операциями wait и signal поддерживается обычная очередь FIFO (приоритетом является время задержки). Приоритетный оператор wait(cv, rank) позволяет влиять на порядок в очереди присвоением процессу того или иного ранга. Здесь cv — условная переменная, а rank — целочисленное выражение. Приостановленные процессы упорядочиваются в очереди согласно присвоенным им приоритетом (рангом) в порядке возрастания параметра rank (при одинаковых значениях rank (порядок следования не стандартизуется и может зависеть от реализации); хотя обычно запускается процесс, ожидавший дольше всех). Для избежания ошибок в программе следует применять только один тип оператора wait. При определении ранга процесса, находящегося в начале очереди задержки, применяется оператор minrank: вызов minrank(cv); возвращает ранг процесса в начале очереди, связанной с переменной cv, при условии, что очередь не пуста, и что при организации очереди используется приоритетный оператор wait; в противном случае возвращается непредсказуемое целое число. Операция signal_all применяется в виде signal_all(cv); посылает сигнал запуска всем процессам в очереди cv; каждый из них совершает перепроверку условий запуска и запускается в соответствии с правилами исключения (например, в одной очереди могут оказаться процессы, затребовавшие разные ресурсы, которые уже захвачены каким-либо процессом; некоторые ресурсы к этому моменту могут освободиться). В результате операции signal_all некоторые процессы могут остаться в очереди, другие — запустятся; заметим, что процесс выработавший сигнал, всегда продолжает работать в мониторе. Фактически операция signal_all(cv) эквивалентна строке while (!empty(cv)) signal(cv);

22

Замечание. Как было сказано, здесь и далее используется стратегия SC (signal and continue) — “сигнализировать и продолжить”. Если бы использовалась стратегия “сигнализировать и ждать”, то возникал бы вопрос о передаче исключительного права владения данной процедурой. Отметим также, что в Unix, Java, Pthreads использована стратегия SC. § 7. Монитор, реализующий кольцевой буфер Для представления очереди сообщений использован массив buf длины n, который “замкнут в кольцо”, т. е. индекс j определяется по модулю n. Целочисленные переменные front и rear указывают на первую заполненную и первую пустую ячейку (см. рис. 3). Условные переменные not_full и not_empty связаны с двумя очередями. Операции с буфером deposit (“вклад”) и fetch (“выборка”) — процедуры монитора.

Рис. 3. Кольцевой монитор monitor Bounded_Buffer { type T buf[n]; # массив некоторого типа T int front=0; # индекс первой заполненной ячейки rear=0; # индекс первой пустой ячейки count=0; # число заполненных ячеек ## rear=(front+count)%n cond not_full,

23

# - получает сигнал при count меньше n not_empty; # - получает сигнал при count больше нуля procedure deposit(type T data) { while (count==n) wait(not_full); buf[rear]=data; rear=rear+1%n; count++; signal(not_empty); } procedure fetch(type T &result) { while (count==0) wait(not_empty); result=buf[front]; front=(front+1)%n; count--; signal(not_full); } } Как и прежде, процесс, запущенный signal, начинает выполняться и сразу (из-за нашей стратегии) и потому в промежуточные моменты, например, другой процесс-производитель может обратиться к процедуре deposit и заполнить свободное место. Таким образом, процесс, запущенный signal должен перепроверить условия запуска, а при его выполнении он может работать. § 8. Задача о “читателях” и “писателях” Процесс-читатель может только читать записи базы данных, а процесс-писатель просматривает их и изменяет. Читатели обращаются к базе данных одновременно, а писатель должны иметь исключительный доступ, а именно: писатель в данной базе может быть единовременно только один; других писателей и читателей в этот промежуток времени быть не должно. В этой задаче упорядочивающий монитор RW дает разрешение на доступ к базе данных. Поскольку имеется два вида процессов (read и write) и два вида действий на каждый процесс (начало и конец), то в мониторе нужны четыре вида процедур: request_read запрос на чтение; release_read окончание чтения; request_write запрос на запись; release_write окончание записи. 24

Пусть постоянные переменные монитора RW: nr — число читателей, nw — число писателей. Правильная синхронизация должна удовлетворять условию RW: (nr==0 ∪ nw==0) ∩ nw<=1 (инвариант монитора). monitor RW_Contr { int nr=0, nw=0; cond oktoread; # получает сигнал при nw==0 cond oktowrite; # получает сигнал при nr==0 и nw==0 procedure request_read() { while (nw>0) wait(oktoread); nr=nr+1; } procedure release_read() { nr=nr-1; if (nr==0) signal(oktowrite); # запустить один процесс-писатель } procedure request_write() { while (nr>0 || nw>0) wait(oktowrite); nw=nw+1; } procedure release_write() { nw=nw-1; signal(oktowrite); # запустить один процесс-писатель signal_all(oktoread); # запустить все процессы-читатели } } При вызове 1) RW_Contr.request_read — запрос чтения: процесс-читатель должен приостановиться если nw>0, а в противном случае (nw=0) число читателей возрастает на единицу; 2) RW_Contr.release_read — уведомление о конце чтения: процесс-читатель уведомляет о том, что он кончил чтение; при этом

25

число читателей уменьшаем на единицу и если оказалось их число, равным нулю, то разрешается запустить один процесс-писатель; 3) RW_Contr.request_write — запрос записи: процесс-писатель хочет писать: если nr>0 или nw>0, ему приходится ждать в очереди oktowrite, иначе число писателей увеличивается на единицу; 4) RW_Contr.release_write — уведомление о конце записи: имеется возможность просигнализировать одного писателя и о запуске всех читателей. § 9. Распределение ресурсов по приоритетам Здесь воспользуемся приоритетным оператором wait(cv,rank), который располагает приостановленные процессы в порядке возрастания ранга. Схема “самое короткое задание” предполагает выполнения заданий в порядке возрастания требуемого ресурса времени. Для этого требуется две операции: request — запросить, release — освободить. После получения и использования ресурса процесс вызывает процедуру release, в результате чего ресурс передается процессу, который будет использовать его самое короткое время; если процессов больше нет, ресурс освобождается. monitor Shortest_Job { bool free=true; cond turn; # получает сигнал, когда ресурс доступен procedure request(int time) { if (free) free=false; # - процесс получает требуемый ресурс else wait(turn,time); # - процесс ждет в очереди по приоритетам } procedure release() { if (empty(turn)) free=true; else signal(turn); 26

} } Использующий этот монитор процесс должен иметь вид Shortest_Job.request(15); [получение и использование затребованного ресурса]; Shortest_Job.release; § 10. Организация “спящих” процессов Основой такой организации является интервальный таймер, позволяющий процессу перейти в состояние “сна” на некоторое количество единиц времени. Фактически речь идет о приостановке процесса. Необходимый здесь интервальный таймер реализуется в виде монитора, представляющего логические часы. С логическими часами возможны две операции: delay(interval) — операция, приостанавливающая процесс на interval “тиков” таймера; tick — операция, увеличивающая значение логических часов и периодически запускаемая аппаратным таймером с высоким приоритетом (для сохранения точности логических часов). Замечание. Особая точность логических часов не требуется, поскольку происходит проверка числа “тиков” и запуск или приостановка процесса может происходить только после очередного “тика”. Будем считать, что значение логических часов хранится в переменной tod (time of day) так что инвариантом требуемого монитора является V CLOCK: {tod>=0} {tod монотонно увеличивается на единицу} После вызова операции delay(interval) процесс “засыпает” на interval “тиков”. В процедуре (операции) delay вводится локальная переменная wake_time, в которой хранится желаемое время запуска wake_time=tod+interval; “Засыпающий” процесс вычисляет период своего “сна” interval и вызывает процедуру delay, в которой вычисляется упомянутое время запуска. Далее запускается цикл while с условием wake_time>=tod. 27

Процедура tick лишь увеличивает значение переменной tod на единицу; она регулярно запускается высокоприоритетным процессом, связанным аппаратным таймером. Один из вариантов реализации — использование так называемого накрывающего условия. Смысл этого условия в том, что его выполнение влечет запуск всех ожидающих процессов, которые после этого должны проверить условия своего выполнения. При этом в мониторе можно использовать одну условную переменную (назовем ее check) с накрывающим условием “значение tod увеличено”. В этом случае при каждом запуске процедуры tick будут запускаться все ожидающие процессы и будут проверять условия своего запуска; в результате запустятся те процессы, условия запуска которых выполнены. Остальные останутся в состоянии ожидания. Для запуска всех процедур в процедуре tick используется оповещающая операция signal_all. monitor Timer{ int tod=0; cond check; # получает сигнал при увеличении tod procedure delay(int interval){ int wake_time; wake_time=tod+interval; while (wake_time>tod) wait(check); } procedure tick(){ tod=tod+1; signal_all(check); } } Использование “покрывающих условий” подходит, если затраты на ложные сигналы невелики (т. к. при “ложном” сигнале процесс запускается, проверяет условия своего выполнения, а затем снова возвращается в состояние ожидания). Если же периоды “сна” велики, то скорее всего такой подход приводит к излишним затратам ресурсов. Для больших периодов “сна” более эффективно использовать в мониторе приоритетный оператор wait. Это удобно в тех случа28

ях, когда имеется статическая упорядоченность (т. е. упорядоченность, не меняющаяся во времени). В нашей ситуации процессы можно упорядочить в соответствии со временем их запуска (“пробуждения”). После этого можно использовать операцию minrank для того, чтобы определить, настало ли время запуска самого первого процесса, приостановленного с помощью check; если это так, то процесс получает сигнал для запуска. Теперь не нужен цикл while в процедуре delay, но он нужен в процедуре tick при посылке сигнала, ибо этого времени запуска могут ожидать несколько процессов. monitor Timer{ int tod=0; cond check; # получает сигнал, когда minrank<=tod procedure delay(int interval){ int wake_time; wake_time=tod+interval; if (wake_time>tod) wait(check, wake_time); } procedure tick(){ tod=tod+1; while(!empty(check) && minrank(check)<=tod) signal(check); } } Изложенный способ (использование приоритетного оператора wait) удобен в случае статических условий запуска процессов (не меняющихся со временем в зависимости от работы других процессов). В этих условиях он имеет явные преимущества перед “покрывающего условия”. В случае нестатических условий запуска удобно применение накрывающего условия; более мощным средством, но менее эффективным с точки зрения захвата ресурсов, является использование в мониторе отдельной условной переменной для каждого условия задержки.

29

Глава 3.

РАНДЕВУ И АКТИВНЫЕ МОНИТОРЫ

§ 1. Рандеву Рандеву — особый тип синхронизации, применяемый, например, при планировании работы головки дискового накопителя. Для наглядности эта синхронизация иллюстрируется “задачей о спящем парикмахере”. В тихом городке имеется парикмахерская с двумя дверями и несколькими креслами. Посетитель входит через одну дверь, ждет в кресле пока освободится парикмахер (если он занят), будит парикмахера (если он свободен), садится в кресло для обслуживания и засыпает (пока его стрижет парикмахер). После стрижки парикмахер открывает посетителю выходную дверь и закрывает за ним. Если есть ожидающие посетители, он будит и приглашает в кресло одного из них. Если нет посетителей, то парикмахер засыпает. Посетители и парикмахер — это процессы: посетители — это клиенты, которые запрашивают сервис (“стрижку”); парикмахер — это сервер, обеспечивающий этот сервис. Таким образом, рассматриваемые отношения имеют тип “клиент – сервер”. В реализации соответствующего монитора можно обойтись тремя процедурами get_haircut — запрос (“хочу постричься”); get_next_customer — запрос (“хочу следующего”); finished_cut — сообщение об окончании (“стрижки”). Постоянные переменные используются для хранения состояний процессов и предоставления “кресел”, в которых клиенты “спят”. Основная часть здесь — рандеву: для встречи – парикмахер должен дождаться прихода посетителя; – посетитель должен дождаться освобождения парикмахера. Таким образом, ситуация аналогична двухпроцессорному барьеру: для продолжения работы к нему должны придти оба процесса; однако, отличие состоит в том, что в качестве процесса-посетителя может быть любой процесс, нуждающимся в “стрижке”. Процесс-посетитель должен ждать, пока парикмахер закроет дверь после “стрижки”, а процесс-парикмахер должен открыть

30

дверь после стрижки и подождать, пока уйдет посетитель и после него закрыть дверь; кроме того, парикмахер ждет, если нет посетителей (находится в состоянии “сна”). Будем использовать возрастающие счетчики для запоминания числа процессов, достигших каждого этапа. У посетителей (client) имеется два важных этапа: 1) пребывание в кресле парикмахера (cinchair); 2) выход из парикмахерской (cleave). У парикмахера (barber) циклически проходят этапы: 1) освобождение от работы (bavail); 2) стрижка (bbusy); 3) завершение стрижки (bdone). Все счетчики в начале имеют значение нуль. Поскольку все этапы проходят последовательно, то справедлив следующий инвариант: V C1: cinchair>=cleave bavail>=bbusy>=bdone С другой стороны нужно учесть следующее: 1) посетитель не может садиться в кресло чаще, чем парикмахер освобождается от работы; 2) парикмахер не может начинать стрижку чаще, чем посетитель садится в его кресло. V C2: cinchair<=bavail bbusy<=cinchair Кроме того, посетители не могут выходить чаще, чем парикмахер завершает стрижку; поэтому C3: cleave <= bdone Итак, инвариант монитора имеетVвидV BARBER: C1 C2 C3 Недостаток возрастающих счетчиков: их значения не могут возрастать неограниченно. Этого можно избежать, изменив переменные. В данном случае введем три новые переменные: barber=bavail-cinchair chair=cinchair-bbusy open=bdone-cleave Все три переменные принимают лишь два значения нуль и единица:  1, если парикмахер ждет посетителя, barber = 0, если парикмахер обслуживает посетителя.

31

( 1, 0,

если посетитель уже сел в кресло, а парикмахер еще не занят, если посетитель обслуживается парикмахером.

1, 0,

если выходная дверь открыта, если выходная дверь закрыта.

chair =  open =

Имеется четыре условия синхронизации: 1) посетители дожидаются освобождения парикмахера; 2) посетители ждут, пока парикмахер откроет дверь; 3) парикмахер ждет прихода посетителя; 4) парикмахер ждет ухода посетителя. Для этого потребуется четыре условных переменных: barber_available получает сигнал при barber>0 (очередь, ожидающих парикмахера); chair_occupied получает сигнал при chair>0 (очередь на занятие кресла); door_open получает сигнал при open>0 (очередь, ожидающих окончание стрижки); customer_left получает сигнал при open=0 (очередь, окончивших стрижку). Процессы ждут выполнения условия с помощью операторов wait, заключенных в циклы. В момент истинности условий выполняется операция signal. monitor Barber_Shop{ int barber=0, chair=0, open=0; cond barber_available; # barber>0, то signal cond chair_occupied; # chair>0, то signal cond door_open; # open>0, то signal cond customer_left; # open=0, то signal procedure get_haircut(){ while(barber==0) wait(barber_available); barber=barber-1; chair=chair+1; signal(chair_occupied); while(open==0) wait(door_open); open=open-1; signal(customer_left);

32

} procedure get_next_customer(){ barber=barber+1; signal(barber_available); while(chair==0) wait(chair_occupied); chair=chair-1; } procedure finished_cut(){ open=open+1; signal(door_open); while(open>0) wait(customer_left); } } Особенности монитора таковы. I. В процедуре get_haircut имеется два обращения к процедуре wait: 1) посетителю нужно ждать освобождения парикмахера (канал barber_available); 2) посетителю приходиться ждать в процессе стрижки (канал door_open); II. Посетителю еще нужно ждать 3) в кресле перед началом стрижки (канал chair_occupied); 4) после стрижки до открытия выходной двери (канал customer_left). § 2. Активные мониторы Как видно из предыдущих параграфов, монитор управляет ресурсом, предоставляя набор процедур для доступа к нему. Процедуры выполняются со взаимным исключением и используют переменные для условий синхронизации. В некотором смысле рассмотренные ранее мониторы являются пассивными наборами процедур, а не активными процессами. В условиях распределенной памяти и взаимодействия процессов на основе передачи сообщений желательно программировать мониторы в виде активных процессов. Предположим, что в мониторе имеется лишь одна процедура op. Тогда структура монитора такова 33

monitor Mon{ [объявление постоянных переменных]; [код инициализации]; procedure op ([формальные параметры]){ [тело процедуры]; } } Для моделирования монитора Mon используем серверный процесс Server. Постоянные переменные монитора становятся локальными переменными этого процесса. Сервер сначала инициализирует переменные, затем выполняет один и тот же цикл, обслуживая “вызовы” процедуры op. Имитация вызова состоит в следующем: – сначала клиентский процесс отправляет сообщение в канал запроса; – ответ он получает из канала ответа. Для того, чтобы избежать перехвата ответа другим клиентским процессом, каждому клиенту нужен собственный канал ответа (или специальные примитивы, позволяющие определить отправителя). chan request(int clientID, [типы входных данных]); # - канал запроса chan reply[n]([типы результатов]); # - массив каналов ответов process Server { int clientID; [объявление других постоянных переменных]; [код инициализации]; while (true){ receive request(clientID, [входные значения]); [код из тела операции op]; send reply[clientID]([результаты]); } }

34

process Client[i=0 to n-1]{ send request(i, [аргументы-значения]); # - вызов op receive reply[i]([аргументы для результатов]); # - ожидания ответа } Заметим, что каналы глобальны по отношению к процессам, так что к каналам можно обращаться непосредственно (статическое именование). Динамическое именование также может быть применено: каждый клиент создает собственный канал ответа, передавая его в первом поле запроса. В этом случае у других процессов не будет доступа к ответу. Заметим, что если монитор имеет несколько процедур, то в сообщении запроса должно быть указание, какую операцию (процедуру) вызывает клиент. У различных операций могут быть разные наборы аргументов: это требует программирования записей с вариантами и объединениями. type op_kind=enum(op_1, ..., op_n); # объявление перечисляемого типа type arg_type=union(arg_1, ..., arg_n); # объявление типа объединения #(резервирование одного пространства) type res_type=union(res_1, ..., res_n); # объявление типа объединения #(резервирование одного пространства) chan request(int clientID, op_kind, arg_type); # канал запросов chan reply[n](res_type); # массив каналов ответов process Server { int clientID; op_kind kind; arg_type args; res_type results; [объявление других переменных]; [код инициализации]; while (true){ ## инвариант цикла

35

receive request(clientID, kind, args); if (kind==op_1) {[тело op_1]}; . . . . . . . . . . else if (kind==op_n) {[тело op_n]}; send reply[clientID](results); } } process Client[i=0 to n-1]{ arg_type myargs; res_type myresults; [поместить аргументы-значения в myargs]; send request(i, op_j, myargs); # вызов op_j receive reply[i](myresults); # ждать ответа } Заметим, что при обслуживании клиента рассмотренному монитору не приходится задерживаться, обслуживая запрос, т. к. тело операции содержит лишь последовательные операции. Однако, более общий вариант монитора использует условную синхронизацию и поддерживает несколько операций; при этом учитывается, что запрос может быть обработан с задержкой. Главное отличие реализующего его серверного процесса состоит в том, что сервер не может ждать, если нет доступного ресурса по данному запросу. Поэтому он запоминает запрос и откладывает посылку ответа до момента освобождения ресурса. После отправки запроса клиент ждет получения ресурса (хотя могут быть и другие варианты). После освобождения ресурса клиент посылает сообщение о его освобождении, но не ждет его обработки. Сначала приведем монитор, а потом — реализующий его сервер.

МОНИТОР monitor Resource_Allocator{ int avail=MAXUNITS; set units=[начальные значения]; cond free;

36

# - получает сигнал, когда процессу нужен ресурс procedure acquire(int &id){ if(avail==0) # нет доступа, wait(free); # уход в очередь else # есть доступ avail=avail-1; remove(units, id); # - удовлетворение запроса: использован ресурс } procedure release(int id){ insert(units, id); # окончание использования ресурса: # возврат его на место if(empty(free)) # нет очереди avail=avail+1; else signal(free); # сигнал "очереднику" } } СЕРВЕР РАСПРЕДЕЛЕНИЯ РЕСУРСОВ И КЛИЕНТЫ type op_kind=enum(ACQUIRE, RELEASE); chan request(int clientID, op_kind kind, int unitID); chan reply[n](int unitID); process Allocator { int avail=MAXUNITS; set units=[начальные значения]; # units - многоэлементный ресурс, # управляемый вставкой или удалением queue pending; # в начальном состоянии очередь пуста int clientID, unitID; op_kind kind; [объявление других локальных переменных]; while (true){ receive request(clientID, kind, unitID); if (kind==ACQUIRE) { if (avail>0){ # удовлетворить запрос: avail--; remove(units, unitID);

37

send reply[clientID](unitID); } else # запомнить запрос: insert(pending, clientID); } else { # kind==RELEASE, то освобождение ресурса if empty(pending){ # очередь пуста # возвратить unitID в множество элементов: avail++; insert(units, unitID); } else { # удовлетворить unitID для ожидающего клиента: remove(pending, clientID); send reply[clientID](unitID); } } } } process Client[i=0 to n-1]{ int unitID; send request(i, ACQUIRE, 0); # "вызов" запросов receive reply[i](unitID); # использовать ресурс unitID, затем освободить его send request(i, RELEASE, unitID); . . . } Замечание. Клиенты остаются без изменений. Здесь рассмотрен частный случай имитации монитора с помощью процесса-сервера; в этом мониторе программирование проводится с помощью метода передачи условия. Для моделирования мониторов, содержащих операторы wait или/и операторы signal, приходится сохранять ожидающий запрос и проверять очередь ожидающих запросов. Между программами с мониторами и с передачей сообщений имеется некоторое соответствие.

38

Т а б л и ц а № 2. Мониторы

Программы с передачей сообщений Постоянные переменные Локальные переменные сервера Идентификаторы процедур Канал запроса и виды операций Вызов процедуры send request(); receive reply(); Вход в монитор receive request(); Возврат в процедуру send reply(); Оператор wait Сохранение ожидающего запроса Оператор signal Получение и обработка ожидающего запроса Тела процедур Ветви оператора выбора по видам операций Относительная производительность двух стилей программирования определяется аппаратурой. Программирование с помощью мониторов обычно эффективнее для систем с разделяемой памятью, и потому на таких ВС обычно реализуются мониторы. Для распределенных систем эффективность мониторов часто ниже, ибо более естественно накладывается на архитектуру использование механизма передачи сообщений; однако, иногда используется оба механизма. § 3. Планирующий сервер Здесь рассмотрим решение задачи планирования доступа к диску. Для того, чтобы осуществлять планирование процесс должен просматривать все ожидающие запросы. Процесс получает сообщения, выполняя цикл, который завершается, когда канал request пуст и есть хотя бы один сохраненный запрос. Затем драйвер выбирает наиболее подходящий запрос, обращается к диску и отправляет ответ клиенту, приславшему запрос. Имеются различные стратегии планирования диска. Рассмотрим одну из них. Процесс записывает ожидающие запросы в одну из двух упорядоченных очередей left или right в зависимости от направления,

39

в котором для обработки запроса необходимо перемещать головки диска из их текущего положения. Запросы очереди left упорядочены по уменьшению номера цилиндра, а в очереди right — по возрастанию. Переменная headpos запоминает текущую позицию головок, а nsaved — число сохраненных запросов. Пусть cy1 — затребованный адрес (т.е. позиция, куда требуется переместить головку). Инвариант для внешнего цикла процесса можно записать в следующем виде. SST: {left — Vэто упорядоченная очередь от наибольшего к наименьшему} {все значения в left не больше headpos} V {right — V это упорядоченная очередь от наименьшего V к наибольшему} {все значения в right не меньше headpos} {если (nsaved==0), то и left и right пусты} Примитив empty в условии внутреннего цикла while позволяет определить, есть ли еще сообщение в очереди канала request. Здесь приводится пример метода программирования, называемого опросом. Процесс постоянно опрашивает канал request, чтобы определить, имеются ли ожидающие запросы. Если такие запросы есть, то процесс получает еще один запрос для того, чтобы расширить возможность выбора подходящего. Если ожидающих запросов нет, то процесс приступает к обслуживанию наиболее подходящих из сохраненных. ПЛАНИРУЮЩИЙ ПРОЦЕСС chan request(int clientID, int cy1, [типы других аргументов]); chan reply[n]([типы результатов]); process Disk_Driver { queue left, right; # упорядоченные очереди сохраненных запросов int clientID, cy1, headpos=1, nsaved=0; [переменные для запоминания других аргументов запроса]; while (true){ ## инвариант цикла SST while (!empty(request) or nsaved==0){ # если очередь не пуста или число сохраненных 40

# переменных равно нулю, то ждать первого # запроса или получать еще один запрос receive request(clientID, cy1, . . .); if (cy1<=headpos) insert(left, clientID, cy1, . . .); else insert(right, clientID, cy1, . . .); nsaved++; # число сохраненных запросов увеличивается } # выбрать наилучший запрос из очередей left и right if (size(left)==0) remove(right, clientID, cy1, args); else if (size(right)==0) remove(left, clientID, cy1, args); else [удалить запрос, который в left или в right ближе всего к headpos]; headpos=cy1; nsaved--; # число сохраненных запросов уменьшается на единицу [получить доступ к диску]; send reply[clientID](results); # отправлен ответ клиенту } } § 4. Файловые серверы и клиенты Рассмотрим процессы, обеспечивающие доступ к файлам на диске. Для работы с файлом клиент должен его открыть. После работы клиент закрывает файл. Будем предполагать, что одновременно могут быть открыты не более n файлов, а доступ к каждому открытому файлу обеспечивается отдельным процессом — отдельным файловым сервером. Итак, будем считать, что имеется n файловых серверов, причем все файловые серверы идентичны. Таким образом, клиенту подойдет любой свободный файловый сервер. 41

Распределять серверы по клиентам мог бы специальный распределяющий процесс, но в этом нет особой необходимости: можно выделить глобальный канал open, в который клиент и направляет запрос на получение доступа к свободному серверу. Каждый свободный файловый сервер опрашивает канал open и, обнаружив там запрос, отправляет клиенту ответ о готовности принять запрос (указав в ответе свой идентификатор) и ожидает запросы от этого клиента на открытие файлов. Клиент отправляет запрос на открытие файла в специальный канал access[i], где i — идентификатор файлового сервера, ожидающего этот запрос (т.е. сервера, ответившего клиенту о своей готовности). При закрытие файла сервер освобождается и снова ждет запросов. Взаимодействие между клиентом и сервером в приводимой ниже программе является отражением стиля программирования, называемого программированием “непрерывного диалога”: клиент начинает диалог с файловым сервером с помощью запроса open. Далее клиент продолжает общаться с тем же сервером. ПРОГРАММА “ФАЙЛОВЫЕ СЕРВЕРЫ И КЛИЕНТЫ” (“непрерывный диалог”) type kind=enum(READ, WRITE, CLOSE); chan open(string fname; int clientID); # запросы на открытие chan access[n](kind k; [типы других аргументов]); # канал доступа клиента к серверу chan open_reply[m](int serverID); # ответ сервера на запрос об открытии: # id сервера или ошибка chan access_reply[m]([типы результатов]); # канал передачи результатов клиенту: # данные, ошибки process File_Server[i=0 to n-1] { string fname; int clientID; kind k; [переменные для других аргументов]; bool more=false; [переменные для локального буфера, кэш-памяти и т. д.]; 42

while (true){ receive open(fname, clientID); # получить из канала open запрос # на открытие файла [открыть файл fname]; [если успешно, то:] send open_reply[clientID](i); more=true; # если успех, то послать ответ клиенту по его # собственному каналу # и указать идентификатор сервера while (more){ receive access[i](k, [другие аргументы]); # получить из канала access[i] # (собственность i-го сервера) запрос k if (k==READ) [обработать запрос на чтение]; else if (k==WRITE) [обработать запрос на запись]; else # k==CLOSE {[закрыть файл]; more=false;} send access_reply[clientID](results); # после получения от клиента команды CLOSE # закрыть файл, послать результаты клиенту и # закончить непрерывный диалог } } } process Client[j=0 to m-1]{ int serverID; [объявление других переменных]; send open("foo", j); # открыть файл "foo" # j - идентификатор клиента receive open_reply[j](serverID); # получить ID сервера # использовать файл, затем закрыть его; send access [serverID]([аргументы доступа]); receive access_reply[j]([результаты]); }

43

Замечание. Здесь фигурирует один канал open с запросами на открытие; он совместно используется всеми клиентами и серверами. Другие решения рассматриваемой задачи состоят в следующем. 1. Можно представить определенную диспетчеризацию распределения запросов: в этом случае должен иметься процессдиспетчер, который выделяет клиенту файловый сервер, а файловые серверы должны сообщать диспетчеру информацию о том, что они свободны. 2. В рассмотренном решении количества клиентов и файловых серверов фиксированы. Возможно создать динамическое определение файловых серверов и клиентов, но программа будет сложнее; однако, это, возможно, приведет к экономии при реализации. 3. Можно иметь по одному файловому серверу на каждый диск, но тогда либо серверы, либо клиенты должны отслеживать всю информацию по открытию и закрытию файлов и передавать эту информацию при каждом запросе; это усложняет программирование и увеличивает потоки информации. 4. Наконец, существует подход, использующий доступ к файлам с помощью удаленных процедур (этот подход используется в файловой системе Sun Network File System /NFS/): при этом “открытие” файла состоит в получении файлового дескриптора и набора атрибутов файла, которые затем передаются при каждом вызове процедуры доступа к файлу. В результате возрастают затраты на передачу аргументов, но существенно упрощается обработка сбоев как серверов, так и клиентов (если происходит сбой файлового сервера, то клиент просто повторяет запросы). § 5. Обмен значениями Пусть имеется n процессов P[0:n-1], в каждом из которых имеется локальная переменная v, принявшая некоторое значение. Задача состоит в том, чтобы определить наибольшее и наименьшее значения переменных v в упомянутых процессах и дать эту информацию всем процессам. Первый способ (асимметричное решение). Один из процессов (например, P[0]) собирает все n чисел, находит минимальное и максимальное среди них и рассылает результаты остальным процессам (см. рис. 4).

44

chan values(int), results[n](int smallest, int largest); process P[0] { # управляющий процесс int v; # переменная v считается инициализированной int new, smallest=v, largest=v; # начальное состояние # собрать числа, сравнить, # запомнить минимальное и максимальное: for [i=1 to n-1] { receive values(new); if (new<smallest) smallest=new; if (new>largest) largest=new; } # разослать результаты остальным процессам: for [i=1 to n-1] send results[i](smallest, largest); } process P[i=1 to n-1] { int v; # считается, что переменная v инициализирована int smallest, largest; send values(v); receive results[i](smallest, largest); }

Рис. 4. Структура взаимодействия при асимметричном решении 45

Второй способ (симметричное решение). Все процессы выполняют один и тот же алгоритм (в стиле SIMD – Single Instruction Multiple Data). Здесь каждый процесс отправляет свое значение всем остальным, затем все процессы вычисляют минимум и максимум из n значений (см. рис. 5).

Рис. 5. Структура взаимодействия при симметричном решении chan values[n](int); process P[i=0 to n-1] { int v; # считается, что v инициализирована int new, smallest=v, largest=v; # начальное условие # отправить мое значение всем остальным процессам: for [j=0 to n-1 st j!=i] # для каждого j от нуля до n-1, # исключая j=i send values[j](v); # собрать значения, найти и # заполнить минимум и максимум: for [j=1 to n-1] { receive values[j](v); if (new<smallest) smallest=new; if (new>largest) 46

largest=new; } } Третий способ (кольцевое решение). Здесь процессы организованы в логическое кольцо; каждый процесс получает сообщение от своего предшественника и отправляет сообщение преемнику (см. рис. 6).

Рис. 6. Структура взаимодействия при кольцевом решении Каждый процесс проходит две стадии: 1) получает два числа и, подключая свое число, находит минимальное и максимальное и отсылает преемнику; 2) получает значения глобально максимального и глобально минимального и отсылает преемнику. Это решение почти симметрично: немного отличается P[0] — это процесс инициализатор. chan values[n](int smallest, int largest); process P[0] { # процесс-инициализатор int v; # считается, что v инициализирована 47

int smallest=v, largest=v; # начальное состояние # послать v следующему процессу P[1]: send values[1](smallest, largest); # получить глобальные максимальное и # минимальное от P[n-1] и отправить # их процессу P[1]: receive values[0](smallest, largest); send values[1](smallest, largest); } process P[i=1 to n-1] { int v; # считается, что v инициализирована int smallest, largest; # получить текущие минимум и максимум # и обновить их, сравнивая с v: receive values[i](smallest, largest); if (v<smallest) smallest=v; if (v>largest) largest=v; # отправить результат следующему процессу и # ожидать получение глобальных результатов: send values[(i+1) mod n](smallest, largest); } Замечание. Симметричное решение — самое короткое, его легко программировать, но оно требует взаимодействия каждого с каждым. Хотя теоретически все сообщения могут быть посланы одновременно и пересылка может происходить параллельно с наименьшими временными затратами, но на практике пересылка большого количества сообщений требует значительных затрат времени, что может свести на нет ускорение, связанное с распараллеливанием. Заметим, что при симметричном решении устанавливаем n(n-1)/2 связей точка-точка, где n — число ВМ; это число весьма значительно, если число ВМ велико. Кольцевое решение напоминает конвейер: операнды umin и umax получают дополнительную обработку на каждом шаге конвейера. Однако, конвейер плохо загружен (особенно, если n велико); та48

ким образом, в рассматриваемой простой задаче кольцевое решение вряд ли эффективно. Оно может оказаться эффективным 1) при обработке потоков данных с числом элементов данных больше или равным n (например, при подсчете тех же минимумов и максимумов в i-й компоненте вектора v[0:n-1], i=0,1, . . . , n-1, если каждый ВМ имеет свой локальный вектор v); 2) при значительных вычислениях с упомянутыми (даже и скалярными) данными. Наиболее приемлемо централизованное решение в приведенном выше первом способе: здесь данные отправляются центральному ВМ без задержек и без задержек обрабатываются центральным ВМ.

49

Глава 4.

ОПЕРАТОРЫ ВЗАИМОДЕЙСТВИЯ И ЗАЩИТА

§ 1. Синхронная передача сообщений Команда send не приводит к блокировке программы, отправившей сообщение. В этом случае отправленное сообщение либо достигает адресата, либо (если адресат не может его принять) оно остается в канале в очереди у адресата; рано или поздно адресат примет сообщение. При этом отправитель продолжает свою работу. Такой способ обработки команды называется неблокирующим и асинхронным (он не требует синхронизации отправителя и адресата). В противоположность команде send команда synch_send является блокирующей, отправитель приостанавливается до получения подтверждения о приемке от адресата. Если адресат не готов принять послание, то начинается простой отправителя. При этом процесс-отправитель не может послать новое сообщение адресату. Физически сообщение находится в адресном пространстве отправителя до готовности адресата получить его; при такой реализации возникает очередь в канале отправителя из адресов сообщений нуждающихся в отправке. Синхронной передаче свойственны следующие недостатки. 1. Первый недостаток. При взаимодействии двух процессов по крайней мере один из них блокируется, в зависимости от того, кто первым попытается установить связь. Рассмотрим следующую программу “производитель – потребитель”: channel values(int); process Producer { int data[n]; for [i=0 to n-1] { [выполнить некоторые вычисления]; synch_send values(data[i]); } } process Consumer { int results[n]; 50

for [i=0 to n-1] { receive values(results[i]); [выполнить некоторые вычисления]; } } Если вычисления, производимые этим процессам таковы, что иной раз Producer выполняет их быстрее, а иной раз их быстрее выполняет Consumer, то простаивает то Producer, то Consumer, так что общее время простоя процессов складывается из этих слагаемых. При асинхронной работе весьма вероятно, что в канале будет скапливаться достаточное число сообщений и простоев не будет вовсе. 2. Второй недостаток блокировок состоит в том, что использующие синхронизацию процессы более предрасположены к взаимным блокировкам, так что программисту нужно наблюдать за тем, чтобы соблюдалось соответствие между операторами передачи и приема. При программировании синхронизации нужно проявлять известную осторожность; например, рассмотрим программу обмена значениями: channel in1(int), in2(int); process P1 { int value1=1, value2; synch_send in2(value1); receive in1(value2); } process P2 { int value1, value2=2; synch_send in1(value2); receive in2(value1); } Эта программа зависнет, поскольку оба процесса заблокируются в операторах synch_send. В одном из них (но не в обоих) нужно выполнить операцию receive сначала, а synch_send потом. 51

Здесь более уместна асинхронная передача сообщений: зависаний не будет, программа отработает без задержки. При асинхронной передаче легко модифицировать программу при увеличении числа процессов. Замечание. Недостаток асинхронных передач (и в отдельных случаях — весьма существенный) состоит в том, что резко ослабевает контроль за вычислительным процессом: в частности, может быть изменен порядок арифметических действий, что, как известно, может привести к большим вычислительным погрешностям. § 2. Операторы взаимодействия Предположим, что процесс А собирается передать значение процессу В, а процесс В — получить это значение. Это запишем, используя нотацию языка CSP (Communicating Sequential Process). process A {. . . process B {. . .

B!e; . . .} # оператор вывода: выдать A?x; . . .} # оператор ввода: запросить

Язык CSP характеризуется использованием так называемого защищенного взаимодействия, о котором речь пойдет ниже. В приведенном фрагменте использованы операторы: B!e — оператор вывода; лучше всего его читать так: “выдать e процессу B”. A?x — оператор ввода, который читается так: “запросить x у процесса A”. Если типы переменных e и x совпадают, то операторы ввода и вывода называются согласованными. Эти операторы приостанавливают каждый из процессов до тех пор пока другой процесс не подойдет к выполнению соответствующего согласованного оператора, после чего оба оператора выполняются одновременно. Выполнение согласованных операторов можно рассматривать как распределенное присваивание : здесь значение переменной из одного процесса присваивается переменной другого процесса. На момент такого присваивания процессы синхронизируются, а далее выполняются независимо. Общий вид операторов ввода и вывода таков:

52

Destination!port(e_1, . . ., e_n); # - выдать e_1, . . ., e_n процессу Destination # через порт с именем port Source?port(x_1, . . ., x_n); # - запросить x_1, . . ., x_n у процесса Source # через порт с именем port Здесь Destination и Source — процессы (соответственно процесс-приемник и процесс-источник), port — общее для обоих процессов имя порта (это имя можно не использовать, если имеется лишь один вид сообщений, при этом скобки можно не писать), e_1, . . ., e_n и x_1, . . ., x_n — имена переменных соответствующих типов. При использовании массива источников возможно обращение к определенному элементу этого массива в виде Source[i]?port(x_1, . . ., x_n); а также возможен запрос ко всем источникам массива в виде Source[*]?port(x_1, . . ., x_n); Простым примером является следующий процесс-фильтр: process Copy { char c; do true --> West?c; # запросить символ у процесса West East!c; # выдать символ процессу East od } Оператор ввода ждет, пока процесс West будет готов принять символ, а оператор вывода ждет, пока процесс East будет готов выдать символ; оба выполняются одновременно. Язык CSP использует понятие защищенных команд. Рассмотрим процесс отыскания наибольшего делителя двух положительных целых чисел x и y (алгоритм Евклида). 53

process Euc { int id, x, y; # ввести запрос от любого # клиента клиентского массива: do true --> Client[*]?args(id, x, y); do x>y --> x=x-y; [ ] x y=y-x; # или od # выдать результат # клиенту с идентификатором id : Client[id]!result(x); od } Клиент Client[i] взаимодействует с Euc соответствующим образом: . . . Euc!args(i, v1, v2); Euc?result(r); . . .

§ 3. Защищенное взаимодействие Защищенные операторы взаимодействия в языке CSP имеют вид: B; C --> S; Здесь B — логическое выражение, C — оператор взаимодействия, S — список операторов. B и C образуют защиту. Говорят, что защита (B,C) пропускает, если B истинно и не пропускает если B ложно. Если B истинно (защита пропускает), а оператор C пока не выполнен, то говорят, что защита пропускает, но блокирует; в противном случае говорят, что защита пропускает и не блокирует. Защищенные операторы взаимодействия используются в операторах if и do. Рассмотрим оператор if: if B_1; C_1 --> S_1; [ ] B_2; C_2 --> S_2; 54

fi; В этом операторе обе ветви являются защищенными операторами взаимодействия. Здесь сначала вычисляются логические выражения в защитах: 1) если обе защиты не пропускают, то выполнение оператора if заканчивается; 2) если одна из защит пропускает, а вторая — нет, то выбирается та, которая пропускает и происходит ожидание возможности выполнения соответствующего оператора C_i; 3) если обе защиты пропускают, но блокируют, то происходит ожидание, пока одна из них разблокируется; 4) если обе защиты пропускают и не блокируют, то выбирается одна из них (недетерминирование). Аналогично работает оператор do; отличие в том, что цикл повторяется до тех пор, пока все защиты перестанут пропускать. Рассмотрим примеры 1. В первом примере в защите нет логического выражения и потому цикл выполняется бесконечно (при готовности процессов West и East): process Copy { char c; do West?c --> East!c # запросить у процесса West и выдать процессу East od } 2. Во втором примере может буферизоваться один или два символа process Copy { char c1, c2; West?c1 # запросить из West do West?c2 --> East!c1 # - защита блокирована (может быть West не готов # выполнить запрос)

55

# запросить еще символ из West и # выдать предыдущий символ в East c1=c2; # - переприсвоить символы [ ] East!c1 --> West?c1; # - выдать символ в East и # запросить символ из West od } Процесс может заблокироваться и на East (если не готов принять) и на West (если не готов выдать запрос). Здесь обе защиты всегда пропускают и потому цикл никогда не завершается; однако, время от времени он может блокироваться. Если обе защиты не блокируют, то выполняется любая ветвь (недетерминирование). 3. Третий пример. Реализацию кольцевого буфера можно получить, реализуя программу Copy в виде process Copy { char buffer[10]; int front=0, rear=0, count=0; do count<10 West?buffer[rear] --> count=count+1; rear=(rear+1) mod 10; [ ] count>0; East!buffer[front] --> count=count-1; front=(front+1) mod 10; od } Здесь используется оператор do с двумя ветвями, но теперь в защитах имеются и логические выражения и операторы взаимодействия. Защита в первой ветви пропускает, когда в буфере есть свободное место, и эта защита не блокирует, если процесс West готов вывести запрашиваемый символ (в конец заполняемого буфера), а защита во второй ветви пропускает, если в буфере есть символы и процесс East готов получить символ (из начала массива заполненного буфера). Цикл здесь тоже никогда не завершается, ибо хотя бы одно из логических значений истинно. 56

4. В четвертом примере используется три порта: acquire, reply, release. Здесь рассмотрим распределитель ресурсов, использующий асинхронную передачу сообщений. process Allocator { int avail=MAXUNITS; set units=[начальные значения]; int index, unitid; do avail>0; Client[*]?acquire(index) --> avail--; remove(units, unitid); # удаление units из доступных Client[index]!reply(unitid); # ответ клиенту с указателем id [ ] Client[*]?release(index, unitid) --> avail++; insert(units, unitid); # вставить units на место od } Замечание. В этой программе не нужно сохранять запросы, поскольку получение сообщения acquire откладывается до тех пор, пока не появится доступные элементы (т. е. до тех пор, пока не станет avail>0). 5. Пятый пример. Симметричное решение в задаче об обмене значениями двух локальных переменных. process P1 { int value1=1, value2; if P2!value1 --> P2?value2; # процессу P2 выдать значение value1, # а затем запросить у него value2 [ ] P2?value2 --> P2!value1; # или наоборот fi } process P2 { int value1, value2=2; 57

if P1!value2 --> P1?value1; # выдать процессу P1 значение value2 # (если он готов принять), # у процесса P1 запросить значение value1 [ ] P1?value1 --> P1!value2; # у процесса P1 запросить значение value1 # выдать процессу P1 значение value2 fi } Замечание. Напомним, что в подобных ситуациях альтернатива выбирается недетерминированно. § 4. Программа генерации простых чисел Здесь опять воспользуемся языком CSP. Пусть нам нужно найти простые числа между 2 и n. Сначала задается список всех таких чисел 2 3 4 5 6 . . . n Вычеркнем числа, кратные двум, кроме первого, считая n нечетным числом, получим 2 3 5 7 9 . . . n Затем вычеркнем все числа, кратные трем, кроме первого. Если продолжить этот процесс далее, то останутся лишь простые числа от 2 до n. Приведенный алгоритм называется решето Эратосфена. Будем распараллеливать этот алгоритм, используя конвейер процессов-фильтров. Каждый фильтр получает поток чисел от своего предшественника, отделяет первое число и посылает своему преемнику все числа, некратные первому числу потока. Отделяемые числа являются простыми. process Sieve[1] { int p=2; for [i=3 to n by 2] Sieve[2]!i; # - передать нечетные числа Sieve[2] }

58

process Sieve[i=2 to L] { int p, next; Sieve[i-1]?p; # - запросить первое число у i-1-го, # p является простым do Sieve[i-1]?next --> # - запросить следующее число у i-1-го if (next mod p)!=0 --> # если оно не делится на p, # то передать его дальше: Sieve[i+1]!next; fi od } Замечание 1. Для нормального завершения всех процессов в конце списка можно поместить маркер, после получения которого каждый из рассмотренных процессов нормально завершается. Замечание 2. Когда программа заканчивается, то искомый набор простых чисел находится в переменных p рассматриваемых процессов.

59

Глава 5. О НЕКОТОРЫХ ЯЗЫКАХ ПРОГРАММИРОВАНИЯ § 1. О языке Occam (“Бритва Оккама”) Язык разрабатывался для работы с транспьютерами. Базовыми элементами языка являются декларации и три “процесса”: – присваивание; – ввод; – вывод. Ввод/вывод аналогичны таковым в языке CSP, но каналы глобальны по отношению к процессам и имеют имена. Каждый канал должен иметь одного отправителя и одного получателя. Базовые процессы объединяются в обычные процессы с помощью так называемых конструкторов; существуют – последовательные конструкторы; – параллельный конструктор; – защищенный оператор взаимодействия. Конструкторы PAR — параллельный, SEQ — последовательный. В синтаксисе Occam каждый базовый процесс, конструктор и декларация занимают отдельную строчку; а декларация заканчивается двоеточием, в записи используются отступы. Рекурсия не поддерживается. Пример 1. INT x,y: SEQ x:=x+1 y:=y+1

# последовательное # увеличение значений x и y

Замечание. Для параллельного исполнения вместо SEQ можно поставить PAR. В языке Occam существуют также конструкторы IF, CASE, WHILE, ALT (для защищенного взаимодействия). Кроме того, имеется механизм, называемый репликатором (похож на квантификатор).

60

Параллельные процессы создаются с помощью конструктора PAR; они взаимодействуют через каналы с помощью базовых процессов ввода ? и вывода !. Пример 2. Программа эхо с клавиатуры на экран: WHILE TRUE BYTE ch: SEQ keyboard?ch screen!ch Можно написать программу, где имеется один канал с накоплением и два процесса. Пример 3. CHAN OF BYTE comm: PAR WHILE TRUE # процесс вывода с клавиатуры BYTE ch: SEQ keyboard?ch comm!ch WHILE TRUE # процесс вывода на экран BYTE ch: SEQ comm?ch display!ch Замечание. Использование отступов делает ненужным закрывающие ключевые слова. Конструктор ALT обеспечивает защищенное взаимодействие. Защита состоит из 1) процесса ввода или; 2) логического выражения и процесса ввода или; 3) логического выражения и конструктора SKIP. Пример 4. Процедурный вариант копирования PROC Copy(CHAN OF BYTE West, Ask, East) 61

BYTE c1, c2, dummy: SEQ West?c1 WHILE TRUE ALT West?c2 SEQ East!c1 c1:=c2 Ask?dummy # процессу East нужен байт SEQ East!c1 West?c1

§ 2. О языке CSP Современные версии языка CSP позволяют его использовать в различных аспектах моделирования приложений: – протоколов взаимодействия; – протоколов безопасности; – протоколов отказоустойчивых систем. Все взаимодействия происходят в результате событий. Основными являются операторы: – присоединения (префиксации — последовательного выполнения); – рекурсии (повторения); – защищенного выбора (недетерминированного выбора). Оператор присоединения используется для задания последовательного порядка событий. Пример 1. Если red и green — события, то светофор, который один раз включает green, а потом red, задается так green --> red --> STOP Здесь STOP — простейший процесс в CSP, который не нуждается во взаимодействии. Пример 2. Для описания повторения используется рекурсия; в частности, циклическое включение green и red имеет вид LIGHT=green --> red --> LIGHT 62

Для описания взаимодействия процессов друг с другом используются каналы. Пример 3. COPY1=West?c:char --> East!c --> COPY1 # копирование по символу Пример 4. Программа вычисления НОД: GCD=Input?id, x, y --> GCD(id, x, y) GCD(id, x, y)= if (x=y) then Output!id, x --> GCD else if (x>y) then GCD(id, x-y, y) else GCD(id, x, y-x) Здесь используются два взаимно-рекурсивных процесса. Первый GCD ждет события ввода и вызывает второй процесс GCD(). Второй процесс повторяется до выполнения условия x=y, затем выводит результат и запускает первый процесс для ожидания еще одного события ввода. Пример 5. Следующая программа определяет поведение системы, буферизующей один или два символа. COPY=West?c1:char --> COPY2(c1) COPY2(c1)=West?c2:char --> East!c1 --> COPY2(c2) [ ] East!c1 --> West?c1:char --> COPY2(c2) Второй процесс использует оператор защищенного выбора [ ]: – защита в первой части ждет ввода из канала West; – защита во второй части ждет вывода из канала East. Выбор недетерминирован: возможны оба взаимодействия.

63

§ 3. О языке Linda В языке Linda обобщается идея разделяемых переменных и асинхронной передачи сообщений. Любой последовательный язык можно дополнить примитивами из Linda и получить параллельный вариант. Имеются кортежи процессов — процедуры которые выполняются асинхронно, и кортежи данных — помеченные записи. Здесь имеется шесть примитивов для доступа к пространству кортежей (разделяемой ассоциативной памяти); кортежем называется отмеченная запись данных. Пространство кортежей (ПК) похоже на единый разделяемый канал связи, но кортежи не упорядочены. OUT — операция помещения кортежа (запись — аналог send — в канал кортеж помещается); IN — операция извлечения кортежа (чтение — аналог receive — из канала кортеж извлекается); EVAL — операция создания процесса; INP — операция ввода (неблокирующая); RDP — операция чтения (неблокирующая); RD — операция просмотра (блокирующая). Пространство кортежей состоит: – из множества пассивных кортежей; – из множества активных кортежей. Каждый кортеж имеет вид ("tag", value_1, . . ., value_n) где метка "tag" является строкой (для различения кортежей). Значения (value_1, . . ., value_n) — это нуль или несколько значений данных (целых чисел, действительных чисел или массивов). Для обработки кортежей служат три базовых неделимых примитива: OUT, IN, RD. OUT("tag", expr_1, . . ., expr_n); — помещение кортежа в ПК (аналогично оператору send, но вместо канала рассматривается пространство кортежей). IN("tag", field_1, . . ., field_n); — извлечение кортежа из ПК (аналогично оператору receive).

64

Каждое поле field_i может быть выражением или формальным параметром вида ?var, где var — имя переменной выполняемого процесса. Аргументы примитива IN называются шаблоном. Процесс IN ждет, пока в ПК появится хотя бы один кортеж, соответствующий шаблону, и удаляет его из ПК. Кортеж d соответствует шаблону t, если 1) их метки идентичны; 2) число полей d и t одинаково; 3) значение каждого выражения в t (если оно указано) равно соответствующему значению в кортеже данных d. После того, как кортеж будет удален из ПК формальным параметрам шаблона присваивается соответствующие значения. Пример 1. Реализация семафора. Пусть sem — символьное имя семафора. Тогда операция V над семафором (увеличение семафора на единицу) будет иметь вид OUT("sem"), а операция P над семафором (ожидание увеличения семафора на единицу, если он был нуль) будет иметь вид IN("sem"). Замечание. Операции P и V состоят из следующих неделимых операций: P(s): 0); s=s-1;>, V(s): <s=s+1;>. Значение семафора — число кортежей sem в пространстве кортежей. Для моделирования массива семафоров используется дополнительное поле, представляющее индекс массива, например IN("sems", i); # P[sems[I]] OUT("sems", i); # V[sems[I]] Базовый примитив RD (блокирующий) используется для просмотра кортежей в пространстве кортежей (без их изъятия из этого пространства — в отличие от примитива IN). Если t — шаблон, то RD(t) приостанавливает процесс до тех пор, пока в пространстве кортежей не появится кортеж, соответствующий шаблону t. Примитивы INP и RDP выполняют те же действия, что IN и RD, но не являются блокирующими; они кроме того возвращают TRUE или FALSE в зависимости от того, есть или нет кортежа в пространстве кортежей с данным шаблоном. INP — извлекает кортеж из ПК (если он есть); 65

RDP — читает кортеж (но оставляет его в ПК). Пример 2. Реализация барьера-счетчика. OUT("barier", 0); # создание элемента barier в ПК с нулевым # значением счетчика Достигнув барьера тот или иной процесс извлекает счетчик из ПК: IN("barier", ?counter); # получение кортежа "barier" OUT("barier", counter=counter+1); # увеличение счетчика на единицу Далее процесс ждет, пока к барьеру придут все n процессов с помощью блокирующего чтения RD("barier", n); При появлении указанного кортежа в ПК процесс продолжает работу. Шестой (и последний) примитив в языке Linda — примитив, создающий новые кортежи EVAL("tag", expr_1, . . ., expr_n); Среди expr_i могут быть процедуры или функции. При создании кортежа они вычисляются, причем все поля кортежа вычисляются параллельно. Меткой кортежа становится метка "tag", а полями — значения после вычисления функций и процедур. Пример 3. Рассмотрим параллельный оператор co[i=1 to n] a[i]=f(i); Ему соответствует C-программа, обогащенная примитивами Linda for(i=1; i<=n; i++) EVAL("a", i, f(i)); В пространстве кортежей оказывается соответствующие n кортежей. Пример 4. Обмен сообщениями “с помощью каналов” OUT("ch", expressions); — посылка в “канал”. IN("ch", expressions); — получение из “канала”.

66

§ 4. Портфель задач Реализация параллельных вычислений возможна с использованием так называемого портфеля задач. Задача здесь представляет независимую единицу работы. Задачи помещаются в “портфель”, разделяемый всеми процессами, работающими по программе while(true) { [получить задачу из "портфеля"]; if([задач больше нет]) break; # выход из цикла fi } Парадигма портфеля задач имеет следующие положительные черты: 1) она весьма проста: – нужно дать представление задач; – определить портфель (набор задач, их расположение); – дать программу выполнения задачи; – определить критерий ее окончания; 2) программы с использованием портфеля задач легко масштабируются: нужно просто изменить число процессов (но производительность может не измениться, если число процессов больше числа задач); 3) упрощается балансировка нагрузки: освободившиеся процессы берут на себя решение новых задач из портфеля (пока задач в два или три раза больше, чем процессов, загрузка процессов окажется более или менее одинаковой). Рассмотрим решение задачи о генерации простых чисел (решето Эратосфена) с помощью портфеля задач, используя C-Linda (эта задача уже рассматривалась ранее на языке CSP). Числа-кандидаты на простое число хранятся в пространстве кортежей. Управляющий процесс собирает результаты и помещает числа-кандидаты в портфель. Каждый процесс удаляет число-кандидат из портфеля и проверяет, является ли оно простым, деля его на м´еньшие простые числа. Для реализации этой схемы (т. е. для того, чтобы все м´еньшие 67

простые числа уже имелись) проверять кандидатов нужно в возрастающем порядке. Возможна приостановка рабочего процесса в ожидании, что другой процесс сгенерирует м´еньшее простое число, но взаимная блокировка исключается. Генерация простых чисел на языке C-Linda РАБОЧИЙ ПРОЦЕСС # include "linda.h" # define LIMIT 1000 /* верхняя граница числа простых чисел */ void worker() { /* функция без параметров */ int primes[LIMIT]={2,3} /* таблица простых чисел */ int numPrimes=1, i, candidate, isprime; /* numPrimes - номер очередного простого числа */ /* циклическое получение кандидатов и их проверка */ while(true) { if(RDP("stop")) /* проверка завершения: появился ли в пространстве кортежей "stop" */ return; /* выход из функции */ IN("candidate", ?candidate); /* получить кандидата */ OUT("candidate", candidate+2); /* вывод следующего нечетного в качестве кандидата погружаем в ПК */ i=0; isprime=1; while(primes[i]*primes[i]<=candidate) { /* далее нет необходимости проверять ибо на остальные числа делится не может */ if(candidate%primes[i]==0){ isprime=0; break; } i++; if(i>numPrimes) { /* требуется следующее простое */ numPrimes++; RD("prime", numPrimes, ?primes[numPrimes]); } } 68

/* сообщаем результат управляющему процессу */ OUT("result", candidate, isprime); /* погружаем в ПК результат */ } }

УПРАВЛЯЮЩИЙ ПРОЦЕСС real_main(int argc, char*argv[ ]) { /* argc - число аргументов командной строки (больше или равно единицы) char*argv[ ] - массив символьных указателей, в котором каждый элемент указывает на аргумент командной строки */ int primes[LIMIT]={2,3} /* локальная таблица простых чисел */ int limit, numWorkers, i, isprime; int numPrimes=2, value=5; limit=atoi(argv[1];) /* считать командную строку */ numWorkers=atoi(argv[2]); /* создать рабочие процессы и поместить их в портфель число пять (первый кандидат): */ for (i=1; i<=numWorkers; i++) EVAL("worker", worker()); /* создание рабочих процессов в ПК */ OUT("candidate", value); /* - создание кандидата в ПК; получить результаты рабочих процессов в порядке возрастания: */ while(numPrimes
69

value=value+2; } /* завершить рабочие процессы, вывести простые числа */ OUT("stop"); /* погрузить "stop" в ПК */ for (i=0; i<=limit; i++) printf("%d\n", primes[i]); /* распечатать массив primes */ } Замечание. Генерацией новых кандидатов в ПК занимаются рабочие процессы. Головная программа сначала выполняет один процесс: 1) она начинает с чтения аргументов командной строки для определения, сколько нужно простых чисел и сколько процессов можно использовать; 2) затем используется примитив EVAL для создания рабочих процессов; 3) далее используется примитив OUT для помещения в пространство кортежей числа-кандидата пять; 4) для получения результатов от рабочих процессов используется примитив IN (извлекает простые числа из ПК), причем результаты получаются в порядке возрастания простых чисел; 5) получив простое число программа помещает его и его номер в пространство кортежей, а также дополняет таблицу простых чисел; 6) работа завершается, когда real_main получает limit простых чисел: управляющий процесс сообщает об остановке, помещая в ПК кортеж "stop"; 7) real_main распечатывает таблицу простых чисел primes. Что делают рабочие процессы? 1) каждый рабочий процесс многократно получает числокандидат из ПК; 2) проверяет, простое ли оно; 3) отправляет его управляющему процессу, помещая в ПК; 4) помещает следующее нечетное число в ПК (таким образом, в ПК находится не более одного числа-кандидата); 5) каждый рабочий процесс поддерживает локальную таблицу простых чисел и дополняет ее, извлекая простые числа из ПК, 70

причем в строго возрастающем порядке; 6) на каждой итерации рабочий процесс проверяет, не нужно ли ему остановиться с помощью RDP (неблокирующий), который вырабатывает “истина”, если есть кортеж "stop". Замечание. Пока будет получено limit простых чисел, будет проверено больше чисел-кандидатов, чем необходимо; для исключения этого эффекта нужно существенно увеличить число передаваемых сообщений.

71

Глава 6. УДАЛЕННЫЙ ВЫЗОВ ПРОЦЕДУР И ВЗАИМОДЕЙСТВИЕ ПРОЦЕССОВ § 1. Удаленный вызов процедур Удаленный вызов процедур будем обозначать RPC (Remote Procedure Call). Ранее рассматривались мониторы, которые инкапсулируют разделяемые переменные, а также процессы, которые синхронизируются при вызове процедур монитора. При удаленном вызове процедуры используется модуль, в котором имеются и процессы и процедуры, при этом модули могут находиться не в одном, а в разных адресных пространствах (см. рис. 7).

Рис. 7. Использование модулей при удаленном вызове процедуры Процессы в одном адресном пространстве называют облегченными потоками. При переключении контекста1 такому потоку приходится сохранять относительно мало информации. Заметим, однако, что это не относится к процессам в UNIX, ибо последние жестко отделены друг от друга: каждый процесс имеет свое адресное пространство и при переключении контекста требует сохранения таблиц управления памятью и состояния регистров. Процессы внутри модуля могут разделять переменные и вызывать процедуры, объявленные в этом модуле, но процессы из другого модуля могут вызывать лишь те процедуры модуля, которые 1 Контекстом данного процесса в тот или иной момент времени можно назвать программное окружение и ресурсы, используемые процессом в рассматриваемый момент времени. При прерывании данный процесс прерывается и заменяется другим процессом с другим контекстом, так что при этом происходит смена контекстов. При возврате из состояния прерывания к продолжению приостановленного процесса прежний контекст восстанавливается.

72

экспортируются этим модулем. Процессы внутри модуля (локальные процессы) называются фоновыми. Модуль характеризуется следующей схемой: module mname [заголовки операций]; body [объявления переменных]; [код инициализации]; [процедуры для экспортируемых операций]; [локальные процедуры и процессы]; end mname Заголовок операции opname задается декларацией op, а именно op opname([параметры]){returns[результат]} Здесь указываются типы, и могут указываться имена параметров и возвращаемого значения. Фигурные скобки означают, что данный раздел необязателен. Процедуры для экспортируемых операций задаются в виде proc opname(параметры) returns идентификатор результатов [объявления локальных переменных]; [операторы]; end Здесь не обязательно указывать типы параметров и результата (они указаны в объявлении заголовка операции op). Аналогично использованию мониторов процесс (или процедура) модуля вызывает процедуру другого модуля при обращении вида call mname.opname(аргументы) Ключевое слово call не обязательно. Заметим, что при локальных вызовах (т. е. внутри тела модуля) имя модуля можно не использовать: opname(аргументы) Межмодульный вызов порождает обслуживающий его новый процесс (процесс-сервер), а аргументы передаются в виде сообщений от вызывающего модуля. После вызова вызывающий модуль

73

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

Рис. 8. Приостановка вызывающего процесса, работа процесса-сервера В случае если вызывающий процесс и процедура находятся в одном адресном пространстве, то новый процесс не создается: вызывающий процесс временно становится серверным. § 2. Вопросы взаимно исключающего доступа и синхронизации (внутри модуля) В модулях может быть много процессов: – процессы-серверы (осуществляющие удаленные вызовы); – фоновые процессы; поэтому в них необходимо обеспечивать взаимно исключающий доступ к разделяемым переменных, а также необходима синхронизация процессов. Имеется два способа реализации взаимного исключения и синхронизации: все процессы одного модуля выполняются 1) со взаимным исключением и в каждый момент активен лишь один процесс; 2) параллельно (и явным образом программируется взаимное исключение и синхронизация по условию; при этом каждый модуль становится параллельной программой, в которой могут использоваться семафоры или мониторы, а также передача сообщений). При первом способе – модули проще программировать;

74

– можно достичь б´ ольшей эффективности при реализации на однопроцессорной системе. Второй способ позволяет исключать является зацикливающиеся процессы и является – более общим, чем первый; – более естественным для мультипроцессоров с разделяемой памятью, на каждом из которых работает свой модуль. В дальнейшем будет использоваться второй способ, а именно будем считать, что 1) процессы внутри модуля выполняются параллельно; 2) программируется взаимное исключение и условная синхронизация. § 3. Модуль сервера времени Пусть в модуле определены две операции get_time delay Клиент может получить текущее время суток, вызывая операцию get_time, и может заблокироваться (“уснуть”), вызывая операцию delay. Сервер времени имеет внутренний процесс, который постоянно запускает аппаратный таймер и при возникновении прерывания увеличивает счетчик времени. module TimeServer op get_time() returns int; # - получить время op delay (int interval, myid); # - "заснуть" на interval "тиков" body int tod=0; # tod - время (суток) sem m=1; # m - семафор исключения sem d[n]=([n]0); # d[n] - скрытые семафоры задержек queue of (int waketime, int process_id) napQ # napQ - очередь приостановленных # процессов (при m=1 tod<waketime) proc get_time() returns time { 75

time=tod; # никаких блокировок не требуется # процесс лишь читает tod } proc delay(interval, myid) { # здесь interval>0 int waketime=tod+interval; P(m); # закрыть семафор, если он открыт # приостановить процесс, если семафор закрыт [вставить (waketime, myid) в подходящее место очереди napQ] # очередь упорядочена по времени waketime V(m); # открыть семафор P(d[myid]); # ждать пропуска = закрыть семафор для myid = # = включен спящий режим для процесса myid } process Clock { [запустить аппаратный таймер]; while(true) { [ждать прерывания, затем перезапустить аппаратный таймер]; tod=tod+1; P(m); # закрыть семафор, если он не закрыт # приостановить процесс, если он закрыт while (tod>=[наименьшее waketime из napQ]) { [удалить (waketime,id) из napQ]; V(d[id]); # - разбудить спящий процесс id # (т.е. открыть семафор для id) } V(m); # - открыть семафор (теперь возможно # обслуживание других процессов) } } end TimeServer Здесь класс queue поддерживает очередь с односторонним до76

ступом (с помощью соответствующих операций). Замечание. Здесь предполагается, что myid принимает значения от 0 до n-1. § 4. Распределенная файловая система Пусть прикладной процесс вызывает файл процедурой read или write в локальном модуле FileCache. Локальный модуль FileCache, вообще говоря, получает данные от модуля FileServer, который управляет блоками данных, расположенных на диске. Для того, чтобы прочитать или записать файл на диск модуль FileCache должен вызвать процедуры readblk или writeblk. Естественно, если FileCache имеет у себя требуемые данные, то он может быстро обработать запрос клиента, иначе ему придется обратиться к модулю FileServer. Иногда FileCache может производить упреждающие чтение или запись с диска в свою память, если по характеру запросов видно, что делаются последовательные обращения к файлу. ФАЙЛОВЫЙ КЭШ В РАСПРЕДЕЛЕННОЙ ФАЙЛОВОЙ СИСТЕМЕ module FileCache # рабочая станция без диска op read (int count; result char buffer[*]); op write (int count; char buffer[ ]); body [кэш файловых блоков]; [переменные для хранения информации дескриптора файла]; [семафоры для синхронизации доступа к кэш-памяти]; proc read(count, buffer) { if ([нужные данные не находятся в кэш-памяти]) { [выбрать блок кэш-памяти для использования]; # предполагается освободить место ... if ([необходимо записать блок кэш-памяти]) FileServer.writeblk(...); FileServer.readblk(...); } buffer=[количество count байт блока кэш-памяти]; 77

} proc write(count, buffer) { if ([ блок не находится в кэш-памяти]) { [выбрать блок в кэш-памяти для использования]; # предполагается освободить место ... if ([необходимо записать выбранный блок]) FileServer.writeblk(...); } [блок кэш памяти = count байт из buffer]; } end FileCache ФАЙЛОВЫЙ СЕРВЕР В РАСПРЕДЕЛЕННОЙ ФАЙЛОВОЙ СИСТЕМЕ module FileServer # находится на файловом сервере op readblk (int fileid, offset; result char blk[1024]); op writeblk (int fileid, offset; char blk[1024]); body [кэш-память дисковых блоков]; [очередь запросов на доступ к диску]; [семафоры для синхронизации доступа к кэш-памяти и к очереди]; proc readblk(fileid, offset, blk) { if ([нужный блок не находятся в кэш-памяти]) { [сохранить запрос на чтение в очереди диска]; [ждать выполнения операции чтения]; } blk=[подходящий дисковый блок]; } proc writeblk(fileid, offset, blk) { [выбрать блок из кэш-памяти]; if ([необходимо записать выбранный блок]) { [сохранить запрос на запись в очереди диска]; [ждать записи блока на диск]; } [блок кэш-памяти]=blk;

78

} process DiskDriver { while(true) { [ждать запроса на доступ к диску]; [начать дисковую операцию; ждать прерывания; запустить процесс, ожидающий завершения данного запроса]; } } end FileServer Замечание 1. Если у каждого прикладного процесса есть отдельный модуль FileCache, то внутренняя синхронизация не нужна (ибо в каждый момент времени выполняется один запрос чтения или записи). В случае использования несколькими процессами одного модуля FileCache, или если в нем реализуется упреждающее чтение, то потребуется использовать семафоры для обеспечения взаимных исключений. Замечание 2. В файловом сервере взаимные исключения необходимы, поскольку он используется несколькими модулями FileCache и, кроме того, содержит внутренний процесс DiskDriver. § 5. Фильтр слияния в Remote Procedure Call (RPC) Фильтр слияния получает два входных отсортированных потока, а на выходе образуется один отсортированный поток. Предполагается, что конец входного потока отмечен маркером EOS. Ранее фильтр слияния рассматривался в случае наличия примитивов передачи сообщений send и receive; здесь нет таких примитивов, и потому нужно явно реализовывать межпроцессорное взаимодействие. Кроме того, труднее связать экземпляры фильтров, ибо нет единых входного и выходного каналов. Поэтому используется динамическая ссылка, представляемая в виде мандата доступа (capability) ко входному потоку, который можно рассматривать как указатель на операцию.

79

ФИЛЬТРЫ СОРТИРОВКИ СЛИЯНИЕМ optype stream=(int); # тип операций с потоком данных module Merge[i=1 to n] op in1 stream, in2 stream; # входные потоки # (экспортируемые операции) op initialize (cap stream); # ссылка на входной поток body int v1,v2; # входные значения из потоков 1 и 2 cap stream out; # мандат доступа ко входному потоку sem empty1=1, full1=0, empty2=1, full2=0; proc initialize(output) { # обеспечить выходной поток out=output; } proc in1(value1) { # создать новое значение для потока 1 P(empty1); v1=value1; V(full1); } proc in2(value2) { # создать новое значение для потока 2 P(empty2); v2=value2; V(full2); } process M { P(full1), P(full2); # ожидать два входных значения while(v1!=EOS and v2!=EOS) if(v1<=v2) {call out(v1); V(empty1); P(full1);} else # v2
мы параграфа 3 из главы 1, которая была основана на примитивах передачи сообщений. Процесс M повторяет действия процесса GLUE из упомянутого параграфа. Однако, этот процесс использует оператор call для помещения значения в выходной канал, а не send; для получения следующего числа из потока используются семафоры. Внутри модуля серверные процессы, обрабатывающие вызовы in1 и in2 являются производителями, а M — потребителем. Каждый модуль экспортирует операции in1 и in2. Они обеспечивают входные потоки и могут использоваться другими модулями для получения входных значений. Главный модуль вызывает из модулей третью операцию initialize для того, чтобы передать фильтру мандат на доступ к используемому выходному потоку; например, главный модуль может дать фильтру Merge[i] мандат доступа к операции in2 фильтра Merge[j] с помощью строки call Merge[i].initialize(Merge[j].in2) Сравнение программы из параграфа 3 главы 1 с этой программой показывает основной недостаток: длина программы велика (требуются дополнительные фрагменты). § 6. Обмен значениями в RPC При взаимодействии равных процессов программирование с использованием удаленного вызова процедур (RPC) также ведет к удлинению программы по сравнению с использованием посылки сообщений. Предположим, что модули находятся на разных компьютерах. ОДИН ИЗ ВАРИАНТОВ ОБМЕНА ЗНАЧЕНИЯМИ module Exchange[i=1 to 2] op deposit(int); body int othervalue; sem ready=0; # семафор используется для сигнализации proc deposit(other) { # - процедура вызывается из другого модуля othervalue=other; 81

# - сохраняем полученное значение V(ready); # - разрешаем процессу Worker забрать это значение } proc Worker { int myvalue; call Exchange[3-i].deposit(myvalue); # - отсылаем значение myvalue другому P(ready); # - ждем получение значения # из другого процесса } end Exchange § 7. Операторы ввода Если модуль экспортирует операцию op opname([типы параметров]); то процесс-сервер осуществляет рандеву с процессом, вызвавшем операцию opname и выполняет оператор ввода, простейший вариант которого имеет вид in opname([параметры]) --> S; ni Область между ключевыми словами in и ni называется защищенной операцией. Защита распространяется на идентификаторы для параметров операции opname (если они есть). Здесь S означает последовательность операторов, реализующих данную операцию. Область видимости параметров — вся защищенная операция, так что операторы из S могут считывать или записывать значения параметров. Оператор ввода приостанавливает работу процесса-сервера до появления вызова операции opname. Затем процесс-сервер 1) выбирает самый старый из ожидающих вызовов; 2) копирует его аргументы в параметры; 3) выполняет список параметров S; 4) возвращает результирующие параметры вызвавшему процессу. С этого момента процесс-сервер, выполняющий операцию, и

82

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

Рис. 9. Работа процесса-сервера и процесса-клиента Ранее приведенный оператор ввода выполняет одну операцию. Однако, защищенное взаимодействие позволяет иметь несколько условий in op_1(параметры) and B_1 by e_1 --> S_1; [ ] . . . [ ] op_n(параметры) and B_n by e_n --> S_n; ni Каждая ветвь является защищенной операцией. Часть кода перед символом --> называется защитой. Символы S_i служат для обозначения последовательностей операторов. Выражение and B_i называется условием синхронизации, а выражение e_i называется условием планирования. Говорят, что защита в операторе ввода пропускает, если была вызвана операция и соответствующее условие синхронизации истинно (или его нет). Условие синхронизации может зависеть от значений параметров (т. к. их область видимости включает всю защищенную операцию), так что один вызов может привести к тому, что защита пропустит, а в другом случае — не пропустит. Выполнение in приостанавливает работу процесса, пока какаянибудь защита, наконец, пропустит. Если несколько защит пропускает, то (при отсутствии условий планирования) оператор обслуживает первый по времени вызов, пропуская через одну из ветвей, причем выбор срабатывающей ветви стандартом не определяется (фактически, ее выбор определяется конфигурированием системы; допуская очевидную вольность формулировок, говорят, что ветвь выбирается недетерминировано). Выражение планирования используется для изменения порядка 83

обработки вызовов: первым обслуживается самый старый вызов, который имеет минимальное значение выражения планирования. Заметим, что как и условие синхронизации выражение планирования может ссылаться на параметры операции, так что его значение, вообще говоря, зависит от аргументов вызова операции. § 8. Взаимодействие типа “клиент-сервер” Пусть имеется процесс с локальным кольцевым буфером из n элементов, который обслуживает две операции deposit и fetch: deposit — производитель помещает элемент в буфер; fetch — потребитель извлекает элемент из буфера. Рассмотрим кольцевой буфер, построенный в помощью рандеву. КОЛЬЦЕВОЙ БУФЕР НА ОСНОВЕ РАНДЕВУ module BoundedBuffer op deposit(type T), fetch(result type T); body process Buffer { type T buf[n]; int front=0; rear=0; count=0; # count - число обращений производителя к # буферу минус число изъятий while(true) # вызывая deposite() производитель # помещает товар в буфер: in deposite(item) and count buf[rear]=item; # - помещение товара в буфер rear=(rear+1) mod n; # - номер следующего пустого ящика count=count+1; [ ] # вызывая fetch(), потребитель # забирает товар из буфера: fetch(item) and count>0 --> item=buf[front]; front=(front+1) mod n; 84

# - продвижение фронта заполненных ящиков count=count-1; ni } end BoundedBuffer Далее приведем модуль, представляющий собой централизованное решение задачи “об обедающих философах”. РЕАЛИЗАЦИЯ ЗАДАЧИ “ОБ ОБЕДАЮЩИХ ФИЛОСОФАХ” module Table op getforks(int), relforks(int); body process Waiter { bool eating[5]=([5] false); # булевский массив while(true) # защита может не пропустить, если вилки заняты in getforks(i) and not(eating[left(i)]) and not(eating[right(i)]) --> eating[i]=true; [ ] relforks(i) --> eating[i]=false; ni } end Table process Philosopher[i=0 to 4] { while(true) { call getforks(i); # запрос вилки [поесть]; call relforks(i); # освобождение вилки [поразмышлять]; } } Приведем пример модуля сервера времени, аналогичый рассмотренному ранее.

85

РЕАЛИЗАЦИЯ МОДУЛЯ СЕРВЕРА ВРЕМЕНИ module TimeServer op get_time() returns int; # вызов дать времени op delay(int); # вызов задержки op tick(); # вызывается обработчиком прерывания часов body process Timer { int tod=0; # время суток while(true) # если для delay(waketime) имеем waketime<=tod, # то пробуждение, иначе задержка in get_time() returns time --> time=tod; [ ] delay(waketime) and waketime<=tod --> [ ] tick() --> { tod=tod+1; [запуск таймера]} ni } end TimeServer Здесь операции get_time и delay экспортируются для клиентов, а tick — для обработчика прерывания часов. При вызове delay используется условие синхронизации. В следующем примере наряду с условием синхронизации используется выражение планирования. Это пример распределения ресурсов по принципу “кратчайшее задание”; в енм фигурирует условие планирования by time, что при выполнении условия синхронизации (в данном случае and free) ведет к первоочередному выполнению наиболее раннего вызова с минимальным параметром time. РАСПРЕДЕЛЕНИЯ РЕСУРСОВ ПО ПРИНЦИПУ “КРАТЧАЙШЕЕ ЗАДАНИЕ” module SJN_Allocator op request(int time), release(); body process SJN { bool free=true; # free - занятость ресурса, 86

# free=true - ресурс свободен while(true) in request(time) and free by time --> free=false; # and free - условие синхронизации # by time - выражение планирования # оно ведет к первоначальному исполнению # запроса с наименьшим time [ ] release() --> free=true; ni } end SJN_Allocator

§ 9. Обмен значениями Здесь возвращаемся к задаче, рассмотренной в параграфе 6; решение дадим с использованием рандеву. При этом процессы могут связываться друг с другом непосредственно. Однако, следует предостеречь от ошибки: процессы, сделавшие вызов одновременно, заблокируют друг друга. Поэтому один процесс должен выполнять операторы call и in в одном порядке, а другой — в противоположном. module Exchange[i=1 to 2] op deposit(int); body proc Worker { int myvalue, othervalue; if (i==1) { # один процесс вызывает call Exchange[2].deposit(myvalue); in deposit(othervalue) --> skip; ni } else { # другой процесс получает in deposit(othervalue) --> skip; ni call Exchange[1].deposit(myvalue); } } end Exchange

87

§ 10. Объединенная нотация Здесь рассматривается программная нотация, объединяющая RPC (Remote Procedure Call), рандеву и асинхронную передачу сообщений в единое целое. В этой нотации операция может быть вызвана – либо синхронным оператором call; – либо асинхронным оператором send в виде строк call Modname.opname([аргументы]); send Modname.opname([аргументы]); Оператор call завершается, как только операция обслужена и возвращены результирующие аргументы, а оператор send — как только вычислены аргументы. Если операция возвращает результат (как функция), то она может быть использована в выражении; в остальных случаях функциональный результат игнорируется. Операция может быть обслужена либо в процедуре proc, либо с помощью рандеву (оператором in). Если обслуживание происходит с помощью proc, то это производится немедленно без использования очередей. При обслуживании оператором in создается очередь процессов, вызывающих операцию (отметим, что доступ к очереди неделимый); в этом случае использование вызова call ведет к приостановке вызывающего процесса, а при использовании вызова send отправитель продолжает работу. Таким образом, имеется четыре комбинации: два способа вызова операции (call и send) и два способа обслуживания (proc и in). Приведем соответствующую таблицу.

88

Т а б л и ц а № 3. Вызов

Обслуживание

Результат

call

proc

call

in

send

proc

send

in

Вызов процедуры Рандеву Динамическое создание процесса Асинхронная передача сообщения

Приостановка вызвавшего да

Образование очереди нет

да

да

нет

нет

нет

да

Замечание. Операцию нельзя одновременно обслуживать с помощью proc и in, ибо возникает неопределенность, помещать ли в очередь. Однако, она может обслуживаться в нескольких операторах in, находящихся в нескольких процессах модуля; в этом случае образуется единая очередь с неделимым доступом. Для мониторов и асинхронной передачи сообщений ранее был определен примитив empty, определяющий есть ли объекты в канале сообщений или в очереди условной переменной. Здесь определим функцию ?opname, возвращающую число ожидающих вызовов операции opname. Пример: in op1 ( . . . ) --> S1; [ ] op2 ( . . . ) and ?op1==0 --> S2; Здесь операции op1 и op2 находятся в неравном положении: вызов op2 возможен только в том случае, если не было вызовов op1, а вызов op1 возможен всегда. § 11. Очередь и кольцевой буфер Здесь продемонстрируем различные способы вызова и обслуживания операций. ПОСЛЕДОВАТЕЛЬНАЯ ОЧЕРЕДЬ module Queue op deposit(type T), fetch(result type T); body 89

type T buf[n]; int front=1, rear=1, count=0; # front - передняя граница, rear - задняя граница, # count - количество элементов в buf proc deposit(item) { if (count0) { item=buf[front]; # при вызове fetch из buf извлекается элемент front=(front+1) mod n; count=count-1; } else [действия, соответствующие опустошению]; } end Queue Замечание 1. Если deposit вызван оператором call, то вызывающий процесс ждет, а если deposit вызвана оператором send, то вызывающий процесс продолжает работу. Замечание 2. Модуль Queue пригоден для использования одним процессом в другом модуле, но его не могут использовать одновременно несколько процессов, ибо в нем нет критических секций для защиты переменных модуля; при параллельном вызове операций может возникнуть взаимное влияние. Введем теперь оператор receive, а именно, следующий оператор ввода in op(f_1, . . ., f_n) --> v_1=f_1; . . .; v_n=f_n; ni обозначим 90

receive op(v_1, . . ., v_n) Введем еще операцию empty(), которая не имеет аргументов, и вызывается оператором send, а обслуживается оператором receive. Такая операция эквивалентна семафору, где send выступает в качестве V, а receive — в качестве P. Начальное значение семафора равно нулю. Его текущее значение, это число “пустых” сообщений, переданных операции, минус число полученных сообщений. В следующей программе буфера для реализации исключения использованы семафоры. КОЛЬЦЕВОЙ БУФЕР С СЕМАФОРАМИ module BoundedBuffer op deposit(type T), fetch(result type T); body type T buf[n]; int front=1, rear=1; # локальные операции для имитации семафоров: op empty(), full(), D(), F(); send D(); send F(); for [i=1 to n] # инициализация пустого "семафора" send empty(); proc deposit(item){ receive empty(); receive D(); buf[rear]=item; rear=(rear+1) mod n; send D(); send full(); } proc fetch(item) { receive full(); receive F(); item=buf[front]; front=(front+1) mod n; send F(); send empty(); } end BoundedBuffer

91

Список литературы [1] Воеводин В.В. Математические модели и методы в параллельных процессах. М., 1986. 296 с. [2] Корнеев В.В. Параллельные вычислительные система. М., 1999. 320 с. [3] Yukiya Aoyama, Jun Nakato. RS/6000 SP:Practical MPI Programming. IBM. Tachnical Support Organization., 2000. 221 p. www.redbook.ibm.com [4] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб., 2002. 608 с. [5] Бурова И.Г., Демьянович Ю.К. Лекции по параллельным вычислениям. СПб., 203. 132 с. [6] Грегори Р. Эндрюс. Основы многопоточного параллельного и распределенного программирования. М., 2003. 512 с. [7] Математическая Энциклопедия. М., 1977. Т.1, 1152 с.

92

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Глава 1. ПРОГРАММИРОВАНИЕ С ИСПОЛЬЗОВАНИЕМ ПЕРЕДАЧИ СООБЩЕНИЙ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 § 1. О распределенном программировании . . . . . . . . . . . . . . . . . . 6 § 2. Асинхронная передача сообщений . . . . . . . . . . . . . . . . . . . . . . 8 § 3. Сортировка, фильтры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 § 4. Клиенты и серверы. Файловые системы . . . . . . . . . . . . . . . 13 Глава 2. МОНИТОРЫ И УСЛОВНЫЕ ПЕРЕМЕННЫЕ . . 15 § 1. Мониторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 § 2. Структура монитора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 § 3. Взаимное исключение в мониторе . . . . . . . . . . . . . . . . . . . . . 16 § 4. Условные переменные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 § 5. Способы выполнения операции сигнализации . . . . . . . . . 18 § 6. Операции с условными переменными . . . . . . . . . . . . . . . . . . 21 § 7. Монитор, реализующий кольцевой буфер . . . . . . . . . . . . . 22 § 8. Задача о “читателях” и “писателях” . . . . . . . . . . . . . . . . . . . .24 § 9. Распределение ресурсов по приоритетам . . . . . . . . . . . . . . 25 § 10. Организация “спящих” процессов . . . . . . . . . . . . . . . . . . . . . 26 Глава 3. РАНДЕВУ И АКТИВНЫЕ МОНИТОРЫ . . . . . . . . 30 § 1. Рандеву . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 § 2. Активные мониторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 § 3. Планирующий сервер . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 § 4. Файловые серверы и клиенты . . . . . . . . . . . . . . . . . . . . . . . . . .42 § 5. Обмен значениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Глава 4. ОПЕРАТОРЫ ВЗАИМОДЕЙСТВИЯ И ЗАЩИТА 49 § 1. Синхронная передача сообщений . . . . . . . . . . . . . . . . . . . . . . 49 § 2. Операторы взаимодействия . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 § 3. Защищенное взаимодействие . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 § 4. Программа генерации простых чисел . . . . . . . . . . . . . . . . . . 57

93

Глава 5. О НЕКОТОРЫХ ЯЗЫКАХ ПРОГРАММИРОВАНИЯ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 § 1. О языке Occam (“Бритва Оккама”) . . . . . . . . . . . . . . . . . . . . 59 § 2. О языке CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 § 3. О языке Linda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 § 4. Портфель задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Глава 6. УДАЛЕННЫЙ ВЫЗОВ ПРОЦЕДУР И ВЗАИМОДЕЙСТВИЕ ПРОЦЕССОВ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 § 1. Удаленный вызов процедур . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 § 2. Вопросы взаимно исключающего доступа и синхронизации (внутри модуля) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .73 § 3. Модуль сервера времени . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 § 4. Распределенная файловая система . . . . . . . . . . . . . . . . . . . . 75 § 5. Фильтр слияния в Remote Procedure Call (RPC) . . . . . . 78 § 6. Обмен значениями в RPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 § 7. Операторы ввода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 § 8. Взаимодействие типа ”клиент-сервер” . . . . . . . . . . . . . . . . . 82 § 9. Обмен значениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 § 10. Объединенная нотация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 § 11. Очередь и кольцевой буфер . . . . . . . . . . . . . . . . . . . . . . . . . . 87 СПИСОК ЛИТЕРАТУРЫ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

94