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

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


Язык синхронизирующих ресурсов (synchronizing resources — SR) был создан в 1980-х го­дах. В его первой версии был представлен механизм рандеву (см. раздел 8.2), затем он был до­полнен поддержкой совместно используемых примитивов (см. раздел 8.3). Язык SR поддер­живает разделяемые переменные и распределенное программирование, его можно использо­вать для непосредственной реализации почти всех программ изданной книги. SR-программы могут выполняться на мультипроцессорах с разделяемой памятью и в сетях рабочих станций, а также на однопроцессорных машинах.

Хотя язык SR содержит множество различных механизмов, все они основаны на несколь­ких ортогональных концепциях. Последовательный и параллельный механизмы объединены,

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

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

8.7.1. Ресурсы и глобальные объекты

Программа на языке SR состоит из ресурсов и глобальных компонентов. Декларация ре­сурса определяет схему модуля и имеет почти такую же структуру, как и module, resource name         # раздел описаний

описания импортируемых объектов

декларации операций и типов body name (параметры)     #  тело

декларации переменных и других локальных объектов

код инициализации

процедуры и процессы

код завершения end name

Декларация ресурса содержит описания импортируемых объектов, если ресурс использует декларации, экспортируемые другими ресурсами или глобальными компонентами. Декла­рации и код инициализации в теле могут перемежаться; это позволяет использовать дина­мические массивы и управлять порядком инициализации переменных и создания процес­сов.
Раздел описаний может быть опущен. Раздел описаний и тело могут компилироваться отдельно.

Экземпляры ресурса создаются динамически с помощью оператора create. Например, код



reap   := create name (аргументы)

передает аргументы (по значению) новому экземпляру ресурса name и затем выполняет код инициализации ресурса. Когда код инициализации завершается, возвращается мандат дос­тупа к ресурсу, который присваивается переменной reap. В дальнейшем эту переменную можно использовать для вызова операций, экспортируемых ресурсом, или для уничтожения экземпляра ресурса. Ресурсы уничтожаются динамически с помощью оператора destroy. Выполнение destroy останавливает любую работу в указанном ресурсе, выполняет его код завершения (если есть) и освобождает выделенную ему память.

По умолчанию компоненты SR-программы размещаются в одном адресном пространстве. Оператор create можно также использовать для создания дополнительных адресных про­странств, которые называются виртуальными машинами. vmcap   :=  create vm()   on machine

Этот оператор создает на указанном узле виртуальную машину и возвращает мандат доступа к ней. Последующие операторы создания ресурса могут использовать конструкцию "on vmcap", чтобы размещать новые ресурсы в этом адресном пространстве. Таким обра­зом, язык SR, в отличие от Ada, дает программисту полный контроль над распределением ре­сурсов по машинам, которое может зависеть от входных данных программы.

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

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

этого при создании ресурса неявно создаются все глобальные объекты, из которых он импор­тирует (если они не были созданы ранее).

SR-программа содержит один отдельный главный ресурс.


Выполнение программы начи­нается с неявного создания одного экземпляра этого ресурса. Затем выполняется код ини­циализации главного ресурса; обычно он создает экземпляры других ресурсов.

SR-программа завершается, когда завершаются или блокируются все процессы, или когда выполняется оператор stop. В этот момент система поддержки программы (run-time system) выполняет код завершения (если он есть) главного ресурса и затем коды завершения (если есть) глобальных компонентов. Это обеспечивает программисту управление, чтобы, напри­мер, напечатать результаты или данные о времени работы программы.

В качестве простого примера приведем SR-программу, которая печатает две строки. resource silly()

write("Hello world.") final

write("Goodbye world.") end end

Этот ресурс создается автоматически. Он выводит строку и завершается. Тогда выполняется код завершения, выводящий вторую строку. Результат будет тем же, если убрать слова final и первое end.

8.7.2. Взаимодействие и синхронизация

Отличительным свойством языка SR является многообразие механизмов взаимодействия и синхронизации. Переменные могут разделяться процессами одного ресурса, а также ресур­сами в одном адресном пространстве (с помощью глобальных компонентов). Процессы также могут взаимодействовать и синхронизироваться, используя все примитивы, описанные в раз­деле 8.3, — семафоры, асинхронную передачу сообщений, RPC и рандеву. Таким образом, язык SR можно использовать для реализации параллельных программ как на мультипроцес­сорных машинах с разделяемой памятью, так и в распределенных системах.

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


Эта возможность поддерживает непре­рывность диалога (см. раздел 7.3).

Операция вызывается с помощью синхронного оператора call или асинхронного send. Для указания вызываемой операции оператор вызова использует мандат доступа к операции или поле мандата доступа к ресурсу. Внутри ресурса, объявившего операцию, ее мандатом фактически является ее имя, поэтому в операторе вызова можно использовать непосредст­венно имя операции. Мандаты ресурсов и операций можно передавать между ресурсами, по­этому пути взаимодействия могут изменяться динамически.

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

Оператор ввода in поддерживает рандеву. Его вид указан в разделе 8.2; он может содер­жать условия синхронизации и выражения планирования, зависящие от параметров. Опера­тор ввода может содержать необязательную часть else, которая выбирается, если не пропус­кает ни одна из защит.

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

Язык SR содержит несколько механизмов, являющихся сокращениями других конструк­ций. Декларация process — это сокращение декларации ор и определения ргос для обслу­живания вызовов операции. Один экземпляр процесса создается неявным оператором send при создании ресурса. (Программист может объявлять и массивы процессов.) Декларация procedure также является сокращением декларации ор и определения ргос для обслужи­вания вызовов операции.

Еще два сокращения — это оператор receive и семафоры. Оператор receive выполня­ется так же, как оператор ввода, который обслуживает одну операцию и просто записывает значения аргументов в локальные переменные. Декларация семафора (sem) является сокра­щенной формой объявления операции без параметров.


Оператор Р представляет собой част­ный случай оператора receive, a V — оператора send.

Язык SR обеспечивает несколько дополнительных полезных операторов. Оператор re­ply — это вариант оператора return. Он возвращает значения, но выполняющий его про­цесс продолжает работу. Оператор forward можно использовать, передавая вызов другому процессу для последующего обслуживания. Он аналогичен оператору requeue языка Ada. Наконец, в языке SR есть оператор со для параллельного вызова операций.



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

Глобальный компонент CS экспортирует две операции: CSenter и CSexit. Тело CS со­держит процесс arbitrator, реализующий эти операции. Для ожидания вызова операции CSenter в нем использован оператор ввода.

in CSenter(id)   by id ->

write( "user",   id,   "in its CS at",   ageO) ni

Это механизм рандеву языка SR. Если есть несколько вызовов операции CSenter, то выби­рается вызов с наименьшим значением параметра id, после чего печатается сообщение. За­тем процесс arbitrator использует оператор receive для ожидания вызова операции CSexit. В этой программе процесс arbitrator и его операции можно было бы поместить внутрь ресурса main. Однако, находясь в глобальном компоненте, они могут использоваться другими ресурсами в большей программе.

Ресурс main считывает из командной строки два аргумента, после чего создает numus-ers экземпляров процесса user. Каждый процесс с индексом i выполняет цикл "для всех" (for all — fa), в котором вызывает операцию Csenter с аргументом i, чтобы полу­чить разрешение на вход в критическую секцию. Длительность критической и некритиче­ской секций кода имитируется "сном" (пар) каждого процесса user в течение случайного числа миллисекунд. После "сна" процесс вызывает операцию CSexit. Операцию CSenter можно вызвать только синхронным оператором call, поскольку процесс user должен ожидать получения разрешения на вход в критическую секцию.


Это выражено ог­раничением {call} в объявлении операции CSenter. Однако операцию CSexit можно вызывать асинхронным оператором send, поскольку процесс user может не задерживать­ся, покидая критическую секцию.

В программе использованы несколько предопределенных функций языка SR. Оператор write печатает строку, a getarg считывает аргумент из командной строки. Функция age в операторе write возвращает длительность работы программы в миллисекундах. Функ­ция пар заставляет процесс "спать" в течение времени, заданного ее аргументом в миллисекундах. Функция random возвращает псевдослучайное число в промежутке от О до значения ее аргумента. Использована также функция преобразования типа int, чтобы преобразовать результат, возвращаемый функцией random, к целому типу, необходимому для аргумента функции пар.

Историческая справка

Удаленный вызов процедур (RPC) и рандеву появились в конце 1970-х годов. Исследо­вания по семантике, использованию и реализации RPC были начаты и продолжаются раз­работчиками операционных систем. Нельсон (Bruce Nelson) провел много экспериментов по этой теме в исследовательском центре фирмы Xerox в Пало-Альто (PARC) и написал от­личную диссертацию [Nelson, 1981]. Эффективная реализация RPC в ядре операционной системы представлена в работе [Birrell and Nelson, 1984]. Перейдя из PARC в Стэнфорд-ский университет, Спектор [Alfred Spector, 1982] написал диссертацию по семантике и реа­лизации RPC.

Бринч Хансен [Brinch Hansen, 1978] выдвинул основные идеи RPC (хотя и не дал этого на­звания) и разработал первый язык программирования, основанный на удаленном вызове процедур. Он назвал свой язык "Распределенные процессы" (Distributed Processes— DP). Процессы в DP могут экспортировать процедуры. Процедура, вызванная другим процессом, выполняется в новом потоке управления. Процесс может также иметь один "фоновый" по­ток, который выполняется первым и может продолжать работу в цикле. Потоки в процессе



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

выполняются со взаимным исключением. Они синхронизируются с помощью разделяемых переменных и оператора when, аналогичного оператору await (глава 2).

RPC был включен в некоторые другие языки программирования, такие как Cedar, Eden, Emerald и Lynx. На RPC основаны языки Argus, Aeolus, Avalon и другие. В этих трех языках RPC объединен с так называемыми неделимыми транзакциями. Транзакция — это группа опе­раций (вызовов процедур). Транзакция неделима, если ее нельзя прервать и она обратима. Если транзакция совершается (commit), выполнение все* операций выглядит единым и неде­лимым. Если транзакция прекращается (abort), то никаких видимых результатов ее выполне­ния нет. Неделимые транзакции возникли в области баз данных и использовались для про­граммирования отказоустойчивых распределенных приложений.

В статье [Stamos and Gifford, 1990] представлено интересное обобщение RPC, которое на­звано удаленными вычислениями (remote evaluation — REV). С помощью RPC серверный мо­дуль обеспечивает фиксированный набор предопределенных сервисных функций. С помо­щью REV клиент может в аргументы удаленного вызова включить программу. Получая вызов, сервер выполняет программу и возвращает результаты. Это позволяет серверу обеспечивать неограниченный набор сервисных функций. В работе Стамоса и Гиффорда показано, как ис­пользование REV может упростить разработку многих распределенных систем, и описан опыт разработчиков с реализацией прототипа. Аналогичные возможности (хотя чаще всего для клиентской стороны) предоставляют аплеты Java. Например, аплет обычно возвращается сервером и выполняется на машине клиента.

Рандеву были предложены в 1978 г. параллельно и независимо Жаном-Раймоном Абриалем (Jean-Raymond Abrial) из команды Ada и автором этой книги при разработке SR.' Термин рандеву был введен разработчиками Ada (многие из них были французами).


На ран­ деву основан еще один язык — Concurrent С [Gehani and Roome, 1986, 1989]. Он дополняет язык С процессами, рандеву (с помощью оператора accept) и защищенным взаимодействи­ем (с помощью select). Оператор select похож на одноименный оператор в языке Ada, а оператор accept обладает большей мощью. Concurrent С позаимствовал из SR две идеи: ус­ловия синхронизации могут ссылаться на параметры, а оператор accept — содержать выра­жение планирования (часть by). Concurrent С также допускает вызов операций с помощью send и call, как и в SR. Позже Джехани и Руми [Gehani and Roome, 1988] разработали Concurrent C++, сочетавший черты Concurrent С и C++.

Совместно используемые примитивы включены в несколько языков программирования, самый известный из которых — SR. Язык StarMod (расширение Modula) поддерживает син­хронную передачу сообщений, RPC, рандеву и динамическое создание процессов. Язык Lynx поддерживает RPC и рандеву. Новизна Lynx заключается в том, что он поддерживает дина­мическую реконфигурацию программы и защиту с помощью так называемых связей.

Обзор [Bal, Steiner and Tanenbaum, 1989] представляет исчерпывающую информацию и ссылки по всем упомянутым здесь языкам. Антология [Gehani and McGettrick, 1988] содер­жит перепечатки основных работ по нескольким языкам (Ada, Argus, Concurrent С, DP, SR), сравнительные обзоры и оценки языка Ada.

Кэширование файлов на клиентских рабочих станциях реализовано в большинстве рас­пределенных операционных систем. Файловая система, представленная схематически в лис­тинге 8.2, по сути та же, что в операционной системе Amoeba. В статье [Tanenbaum et al., 1990] дан обзор системы Amoeba и описан опыт работы с ней. Система Amoeba использует RPC в качестве базовой системы взаимодействия. Внутри модуля потоки выполняются параллель­но и синхронизируются с помощью блокировок и семафоров.

В разделе 8.4 были описаны способы реализации дублируемых файлов. Техника взвешен­ного голосования подробно рассмотрена в работе [Gifford, 1979].


Основная причина исполь­зования дублирования — необходимость отказоустойчивости файловой системы. Отказо­устойчивость и дополнительные способы реализации дублируемых файлов рассматриваются в исторической справке к главе 9.

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

\

Удаленный вызов методов (RMI) появился в языке Java, начиная с версии 1.1. Пояснения к RMI и примеры его использования можно найти в книгах [Flanagan, 1997] и [Hartley, 1998]. (Подробнее об этих книгах и их Web-узлах сказано в конце исторической справки к главе 7.) Дополнительную информацию по RMI можно найти на главном Web-узле языка Java www. Javasoft. com.

В 1974 году Министерство обороны США (МО США) начало программу "универсального языка программирования высокого уровня" (как ответ на рост стоимости разработки и под­держки программного обеспечения). На ранних этапах программы появилась серия докумен­тов с основными требованиями, которые вылились в так называемые спецификации Стил-мена (Steelman). Четыре команды разработчиков, связанных с промышленностью и универ­ситетами, представили проекты языков весной 1978 г. Для завершающей стадии были выбраны два из них, названные Красным и Зеленым. На доработку им было дано несколько месяцев. "Красной" командой разработчиков руководил Intermetrics, "зеленой" — Cii Honey Bull. Обе команды сотрудничали с многочисленными внешними экспертами. Весной 1979 г. был выбран Зеленый проект. (Интересно, что вначале Зеленый проект основывался на син­хронной передаче сообщений, аналогичной используемой в CSP; разработчики заменили ее рандеву летом и осенью 1978 г.)

МО США назвало новый язык Ada в честь Августы Ады Лавлейс, дочери поэта Байрона и помощницы Чарльза Бэббеджа, изобретателя аналитической машины. Первая версия языка Ada с учетом замечаний и опыта использования была усовершенствована и стандартизована в 1983 г. Новый язык был встречен и похвалой, и критикой; похвалой за превосходство над другими языками, которые использовались в МО США, а критикой — за размеры и слож­ность.


Оглядываясь в прошлое, можно заметить, что этот язык уже не кажется таким слож­ным. Некоторые замечания по Ada 83 и опыт его использования в следующем десятилетии привели к появлению языка Ada 95, который содержит новые механизмы параллельного программирования, описанные в разделе 8.6.

Реализации языка Ada и среды разработки для множества различных аппаратных плат­форм производятся несколькими компаниями. Этот язык описан во многих книгах. Особое внимание на большие возможности языка Ada обращено в книге [Gehani, 1983]; алгоритм решения задачи об обедающих философах (см. листинги 8.17 и 8.18) в своей основе был взят именно оттуда. В книге [Burns and Wellings, 1995] описаны механизмы параллельного про­граммирования языка Ada 95 и показано, как его использовать для программирования систем реального времени и распределенных систем. Исчерпывающий Web-источник информации по языку Ada находится по адресу www. adahome. com.

Основные идеи языка SR (ресурсы, операции, операторы ввода, синхронные и асинхрон­ные вызовы) были задуманы автором этой книги в 1978 г. и описаны в статье [Andrews, 1981]. Полностью язык был определен в начале 1980-х и реализован несколькими студентами. Энд-рюс и Олсон (Olsson) разработали новую версию этого языка в середине 1980-х годов. Были добавлены RFC, семафоры, быстрый ответ и некоторые дополнительные механизмы [Andrews et al., 1988]. Последующий опыт и желание обеспечить оптимальную поддержку для параллельного программирования привели к разработке версии 2.0. SR 2.0 представлен в книге [Andrews and Olsson, 1992], где также приведены многочисленные примеры и обзор реализации. Параллельное программирование на SR описано в книге [Hartley, 1995], заду­манной как учебное руководство по операционным системам и параллельному программиро­ванию. Адрес домашний страницы проекта SR и реализаций: www. cs. arizona. edu/sr.

Основная тема этой книги — как писать многопоточные, параллельные и/или распреде­ленные программы. Близкая тема, но имеющая более высокий уровень, — как связывать су­ществующие или будущие прикладные программы, чтобы они совместно работали в распре­деленном окружении, основанном на Web.


Программные системы, которые обеспечивают такую связь, называются микропрограммными средствами (middleware). CORBA, Active-X и DCOM — это три наиболее известные системы. Они и большинство других основаны на

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

объектно-ориентированных технологиях. CORBA (Common Object Request Broker Architecture — технология построения распределенных объектных приложений) — это набор спецификаций и инструментальных средств для обеспечения возможности взаимодействия программ в распределенных системах. Active-X— это технология для объединения таких приложений Web, как броузеры и Java-аплеты с настольными сервисами типа процессоров документов и таблиц. DCOM (Distributed Component Object Model — распределенная модель компонентных объектов) служит основой для удаленных взаимодействий, например, между компонентами Active-X. Эти и многие другие технологии описаны в книге [Umar, 1997). По­лезным Web-узлом по CORBA является www. omg. org, а по Active-X и DCOM — www.activex.org.



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

Stamos, J. W, and D. К. Gifford. 1990. Remote evaluation. ACM Trans, on Prog. Languages and Systems 12, 4 (October): 537-565.

Tanenbaum, A. S, R. van Renesse, H. van Staveren, G. i. Sharp, S. J. Mullender, J. Jansen, and G. van Rossum. 1990. Experiences with the Amoeba distributed operating system. Comm. ACM 33, 12 (December): 46-63.

Umar, A. 1997. Object-Oriented Client/Server Internet Environments. Englewood Cliffs, NJ: Prentice-Hall.

Упражнения

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



8.2.    Рассмотрим распределенную файловую систему в листинге 8.2:

а)   разработайте законченные программы модулей кэширования файлов и файлового сервера. Разработайте реализацию кэша, добавьте код синхронизации и т.д.;

б)   модули распределенной файловой системы запрограммированы с помощью RPC. Перепрограммируйте файловую систему, используя примитивы рандеву, опреде­ленные в разделе 8.2. Уточните программу, чтобы по степени детализациии она была сравнима с программой в листинге 8.2.

8.3.    Предположим, что модули имеют вид, показанный в разделе 8.1, а процессы разных модулей взаимодействуют с помощью RPC. Кроме того, пусть процессы, которые обслуживают  удаленные   вызовы,   выполняются   со   взаимным   исключением   (как в мониторах).   Условная   синхронизация   программируется   с   помощью   оператора when В, который приостанавливает выполняемый процесс до тех пор, пока логическое условие в не станет истинным. Условие В может использовать любые переменные из области видимости выражения:

а)   перепишите модуль сервера времени (см. листинг 8.1), чтобы он использовал эти механизмы;

б)   перепрограммируйте модуль фильтра слияния (см. листинг 8.3), используя эти ме­ханизмы.

8.4.    Модуль Merge (см. листинг 8.3) имеет три процедуры и локальный процесс. Измените реализацию, чтобы избавиться от процесса М (процессы, обслуживающие вызовы операций inl и in2, должны взять на себя роль процессам).

8.5.    Перепишите процесс TimeServer (см. листинг 8.7), чтобы операция delay задавала интервал времени, как в листинге 8.1, а не действительное время запуска программы. Используйте только примитивы рандеву, определенные в разделе 8.2. (Указание. Вам понадобится одна или несколько дополнительных операций, а клиенты не смогут просто вызывать операцию delay.)

8.6.    Рассмотрим процесс планирующего драйвера диска (см. листинг 7.7). Предположим, что процесс экспортирует только операцию request (cylinder,   . . .). Покажите, как использовать рандеву и оператор in для реализации каждого из следующих алгоритмов планирования работы диска: наименьшего времени поиска, циклического сканирования (CSCAN) и лифта. (Указание. Используйте выражения планирования.)



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

8.7.    Язык Ada обеспечивает примитивы рандеву, аналогичные определенным в разделе 8.2 (подробности — в разделе 8.6). Но в эквиваленте оператора in в языке Ada условия синхронизации не могут ссылаться на параметры операций. Кроме того, язык Ada не поддерживает выражения планирования.

Используя примитивы рандеву, определенные в разделе 8.2, и указанную ограниченную форму оператора in или примитивы языка Ada select и accept, перепрограммируйте следующие алгоритмы:

а)  централизованное решение задачи об обедающих философах (см. листинг 8.6);

б)   сервер времени (см. листинг 8.7);

в)   диспетчер распределения ресурсов по принципу "кратчайшее задание" (см. лис­тинг 8.8).

8.8.    Рассмотрим следующее описание программы поиска минимального числа в наборе целых чисел. Дан массив процессов Min[l:n]. Вначале каждый процесс имеет одно целое значение.  Процессы  многократно  взаимодействуют,  и  при  взаимодействии каждый процесс пытается передать другому минимальное из увиденных им значений. Отдавая свое минимальное значение, процесс завершается. В конце концов останется

' один процесс, и он будет знать минимальное число исходного множества:

а)  разработайте программу решения этой задачи, используя только примитивы RPC, описанные в разделе 8.1;

б)   напишите программу решения задачи с помощью только примитивов рандеву (см. раздел 8.2);

в)   разработайте программу с помощью совместно используемых примитивов, описан­ных в разделе 8.3. Ваша программа должна быть максимально простой.

8.9.    В алгоритме работы читателей и писателей (см. листинг 8.13), предпочтение отдается читателям:

а)  измените оператор ввода в процессе Writer, чтобы преимущество имели писатели;

б)   измените оператор ввода в процессе Writer так, чтобы читатели и писатели полу­чали доступ к базе данных по очереди.

8.10.  В модуле FileServer (см. листинг 8.14) для обновления удаленных копий использован оператор call.


Предположим, что его заменили асинхронным оператором send. Работает ли программа? Если да, объясните, почему. Если нет, объясните, в чем ошибка.

8.11.  Предположим, что процессы взаимодействуют только с помощью механизмов RPC, определенных в разделе 8.1, а процессы внутри модуля— с помощью семафоров. Перепрограммируйте каждый из указанных ниже алгоритмов:

а) модуль BoundedBuf f er (см. листинг 8.5); •б)  модуль Table (см. листинг 8.6);

в)   модуль SJN_Allocator (см. листинг 8.8);

г)   модуль ReadersWriters (см. листинг 8.13);

д)   модуль FileServer (см. листинг 8.14).

8.12.  Разработайте серверный процесс, который реализует повторно используемый барьер для п рабочих процессов.  Сервер имеет одну операцию —  arrive ().  Рабочий процесс вызывает операцию arrive, когда приходит к барьеру. Вызов завершается, когда к барьеру приходят все n процессов. Для программирования сервера и рабочих процессов   используйте   примитивы   рандеву   из   раздела 8.2.   Предположим,   что

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

доступна функция ?opname, определенная в разделе 8.3, которая возвращает число задержанных вызовов операции opname.

8.13.  В листинге 7.12 был представлен алгоритм проверки простоты чисел с помощью решета из   процессов-фильтров,   написанный   с   использованием   синхронной   передачи сообщений языка CSP. Другой алгоритм, представленный в листинге 7.13, использовал управляющий процесс и портфель задач. Он был написан с помощью пространства кортежей языка Linda:

а)   перепишите алгоритм из листинга 7.12 с помощью совместно используемых прими­тивов, определенных в разделе 8.3;

б)   измените алгоритм из листинга 7.13 с помощью совместно используемых примити­вов (см. раздел 8.3);

в)   сравните производительность ответов к пунктам а и б. Сколько сообщений необхо­димо отправить для проверки всех нечетных чисел от 3 до п? Пара операторов send-receive учитывается как одно сообщение, а оператор call — как два, даже если нет возвращаемых значений.



8.14.  Задача о счете. Несколько людей (процессов) используют общий счет. Каждый из них может помещать средства на счет и снимать их. Текущий баланс равен сумме всех вложенных средств минус сумма всех снятых. Баланс никогда не должен становиться отрицательным.

Используя составную нотацию, разработайте сервер для решения этой задачи, представьте его клиентский интерфейс. Сервер экспортирует две операции: de­posit (amount) и withdraw (amount). Предполагается, что значение amount положительно, а выполнение операции withdraw откладывается, если на счету недостаточно денег.

8.15.  В комнату входят процессы двух типов А и в. Процесс типа А не может выйти, пока не встретит два процесса в, а процесс в не может выйти, пока не встретит один процесс А. Встретив необходимое число процессов другого типа, процесс сразу выходит из комнаты:

а)  разработайте серверный процесс для реализации такой синхронизации. Представьте серверный интерфейс процессов А и в. Используйте составную нотацию, опреде­ленную в разделе 8.3;

б)   измените ответ к пункту а так, чтобы первый из двух процессов в, встретившихся с процессом А, не выходил из комнаты, пока процесс А не встретит второй процесс в.

8.16.  Предположим, что в компьютерном центре есть два принтера, а и в, которые похожи, но не одинаковы. Есть три типа процессов, использующих принтеры: только типа А, только типа в, обоих типов.

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

8.17. Американские  горки.      Есть   n   процессов-пассажиров   и   один   процесс-вагончик. Пассажиры ждут очереди проехать в вагончике, который вмещает с человек, С < п. Вагончик может ехать только заполненным:

а)   разработайте коды процессов-пассажиров и процесса-вагончика с помощью состав­ной нотации;

б)   обобщите ответ к пункту а, чтобы использовались m процессов-вагончиков, m > 1.


Поскольку есть только одна дорога, обгон вагончиков невозможен, т.е. заканчивать

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

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

8.18.  Задача об устойчивом паросочетании (о стабильных браках) состоит в следующем. Пусть Мап[1:п]   и Woman[l:n] — массивы процессов. Каждый мужчина (man) оценивает женщин (woman) числами от 1 до п, и каждая женщина так же оценивает мужчин. Паросочетание — это взаимно однозначное соответствие между мужчинами и женщинами. Паросочетание устойчиво, если для любых двух мужчин mi и т2 и двух женщин wi и w2, соответствующих им в этом паросочетании, выполняются оба следующих условия:

•    mi оценивает wi выше, чем w2, или w2 оценивает m2 выше, чем mi;

•    m2 оценивает w2

выше, чем wi, или wi оценивает mi выше, чем т2.

Иными словами, Паросочетание неустойчиво, если найдутся мужчина и женщина, предпочитающие друг друга своей текущей паре. Решением задачи является множество n-паросочетаний, каждое из которых устойчиво:

а)   с помощью совместно используемых примитивов напишите программу для решения задачи устойчивого брака;

б)   обобщением этой задачи является задача об устойчивом соседстве. Есть 2п человек. У каждого из них есть список предпочтения возможных соседей. Решением задачи об устойчивом соседстве является набор из п пар, каждая из которых стабильна в том же смысле, что и в задаче об устойчивых браках. Используя составную нота­цию, напишите программу решения задачи об устойчивом соседстве.

8.19.  Модуль FileServer в листинге 8.14 использует по одной блокировке на каждую копию файла. Измените программу так, чтобы в ней использовалось взвешенное голосование, определенное в конце раздела 8.4.

8.20.  В листинге 8.14 показано, как реализовать дублируемые файлы, используя составную нотацию (см. раздел 8.3). Для решения этой же задачи напишите программу на языке:



а)   Java. Используйте RMI и синхронизированные методы;

б)   Ada;

в)   SR.

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

8.21.  Проведите   эксперименты   с   Java-программой   для   удаленной   базы   данных   (см. листинг 8.15). Запустите программу и посмотрите, что происходит. Измените программу для работы с несколькими клиентами. Измените программу для работы с более реалистич­ной базой данных (по крайней мере, чтобы операции занимали больше времени). Составьте краткий отчет с описанием ваших действий и полученных результатов.

8.22.  В листинге 8.15 представлена Java-программа, реализующая простую удаленную базу данных. Перепишите программу на языке Ada или SR, проведите эксперименты с ней. Например, добавьте возможность работы с несколькими клиентами, сделайте базу данных более реалистичной (по крайней мере, чтобы операции занимали больше времени). Составьте краткий отчет о том, как вы реализовали программу на SR или Ada, какие эксперименты провели, что узнали.

8.23.  В листингах 8.17 и 8.18 представлена программа на языке Ada, которая реализует имитацию задачи об обедающих философах:

а)   запустите программу;

б)   перепишите программу на Java или SR.

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

Проведите эксперименты с программой. Например, пусть философы засыпают на слу­чайные промежутки времени во время еды или размышлений. Попробуйте использо­вать разные количества циклов. Составьте краткий отчет о том, как вы реализовали программу на SR или Java (для пункта б), какие эксперименты провели, что изучили.

8.24.  В листинге 8.19 показана SR-программа моделирования решения задачи критической секции:

а)  запустите программу;

б)   перепишите программу на языке Java или Ada.

Поэкспериментируйте с программой. Например, измените интервалы задержки или приоритеты планирования.


Составьте краткий отчет о том, как вы реализовали про­грамму на SR или Ada (для пункта б), какие эксперименты провели, что изучили.

8.25.  В упражнении 7.26 описаны несколько проектов для параллельного и распределенного программирования. Выберите один из них или подобный им, разработайте и реализуйте решение,  используя язык Java, Ada,  SR или библиотеку подпрограмм,  которая поддерживает RPC или рандеву. Закончив работу, составьте отчет с описанием вашей задачи и решения, продемонстрируйте работу программы.








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