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

Дублируемые серверы


Опишем последнюю парадигму взаимодействия процессов — дублируемые серверы. Как уже говорилось, сервер — это процесс, управляющий некоторым ресурсом. Сервер можно дублировать, если есть несколько отдельных экземпляров ресурса; каждый сервер тогда управ­ляет одним из экземпляров. Дублирование также можно использовать, чтобы дать клиентам ил­люзию уникальности ресурса, когда в действительности экземпляров ресурса несколько. По-лобный пример был представлен при реализации дублирования файлов (см. раздел 8.4).

В этом разделе строятся два дополнительных решения задачи об обедающих философах  иллюстрируются два применения дублируемых серверов. Как обычно, в задаче есть пять философов и пять вилок, и для еды философу нужны две вилки. В виде распределенной про­граммы эту задачу можно решить тремя способами. Пусть РН— это процесс-философ, W— процесс-официант. В первом способе всеми пятью вилками управляет один процесс-официант (эта централизованная структура показана на рис. 9.5, а). Второй способ — распре­делить вилки, чтобы одной вилкой управлял один официант (распределенная структура на рис. 9.5, б). Третий способ — прикрепить официанта к каждому философу (децентрализованная структура на рис. 9.5, в). Централизованное решение было представлено з листинге 8.6, а распределенное и децентрализованное решения разрабатываются здесь.

• 9.7.1. Распределенное решение задачи об обедающих философах

Централизованное решение задачи об обедающих философах (см. листинг 8.6) свободно от блокировок, но не справедливо. Кроме того, узким местом программы может стать процесс-официант, поскольку с ним должны взаимодействовать все процессы-философы. Распределенное решение можно сделать свободным от блокировок, справедливым и не имеющим узкого места, но платой за это будет более сложный клиентский интерфейс и увеличение числа сообщений.

В листинге 9.15 приведено распределенное решение, в котором использована составная нотация из раздела 8.3. (Это приводит к короткой программе, хотя ее легко переписать с по­мощью только передачи сообщений или только рандеву.) Есть пять процессов-официантов, каждый из которых управляет одной вилкой.
Официант постоянно ожидает, пока философ возьмет вилку, а потом отдаст ее. Каждый философ, чтобы получить вилки, взаимодействует с двумя официантами. Чтобы не возникали блокировки, философы не должны выполнять одну и ту же программу. Вместо этого каждый из первых четырех философов берет левую, а затем правую вилки, а последний философ — сначала правую, а потом левую. Это решение очень похоже на решение с семафорами в листинге 4.6.

Распределенное решение в листинге 9.15 является справедливым, поскольку вилки за­прашиваются по одной, и вызовы операции get forks обслуживаются в порядке вызова. Та­ким образом, все вызовы операции getf orks в конце концов будут обслужены при условии, что философы когда-нибудь отдадут полученные вилки.



Глава 9. Модели взаимодействия процессов                                                                            361

9.7.2. Децентрализованное решение задачи об обедающих философах

Построим децентрализованное решение, в котором у каждого философа есть свой офици­ант. Схема взаимодействия процессов здесь похожа на использованную в задаче о дублируе­мых файлах (см. листинги8.1 и8.14). Алгоритм работы процессов-официантов— это еще один пример передачи маркера (маркерами являются пять вилок). Представленное здесь ре­шение можно адаптировать для управления доступом к дублируемым файлам или получить из него эффективное решение задачи распределенного взаимного исключения (см. упражнения).

Каждая вилка — это маркер, который находится у одного из двух официантов или в пути между ними. Когда философ хочет есть, он просит у своего официанта две вилки. Если у официанта в данный момент нет обеих вилок, он просит у соседних официантов. После этого официант контролирует вилки, пока философ ест.



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


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

Основная идея избавления от взаимных блокировок — официант должен отдать исполь­зованную вилку, но удерживать вилку, которую только что получил. Для этого, когда фило­соф начинает есть, официант помечает обе вилки как "грязные". Если вилка нужна другому официанту, и она уже грязная и не используется, первый официант моет вилку и отдает. Но грязную вилку можно использовать повторно, пока она не понадобится другому официанту.

Этот децентрализованный алгоритм приведен в листинге 9.16. (Из-за мытья вилок его часто называют "алгоритмом гигиеничных философов".) Решение запрограммировано с по­мощью составной нотации (см. раздел 8.3), поскольку его легче построить, используя и уда­ленные вызовы процедур, и рандеву, и передачу сообщений.

Желая поесть, философ вызывает операцию get forks, экспортируемую модулем. Опе­рация get forks реализована процедурой, чтобы скрыть, что получение вилок требует от­правки сообщения hungry и получения сообщения eat. Получая сообщение hungry, про­цесс-официант проверяет состояние двух вилок. Если обе вилки у него, философ получает разрешение поесть, а официант ждет, пока философ отдаст вилки.

Если у процесса-официанта нет двух нужных вилок, он должен их взять, используя для этого операции needL, needR, passL и passR. Когда философ голоден и его официанту нужна вилка, официант передает сообщение другому официанту, у которого есть эта вилка. Другой официант получает это сообщение, когда вилка уже грязная и не используется, и пе­редает вилку первому официанту. Операции needR и needL вызываются асинхронным вызо­вом send, а не синхронным call, поскольку одновременный вызов операций call двумя официантами может привести ко взаимной блокировке.



Для хранения состояния вилок каждый официант использует четыре переменные: haveL, haveR, dirtyL и dirtyR. Эти переменные инициализируются, когда в процессе Main вы­зываются операции forks модулей Waiter. Вначале официант 0 держит две грязные вилки, официанты 1-3 — по одной (правой) грязной вилке, а у официанта 4 вилок нет.

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





Философы не будут голодать, поскольку официанты всегда отдают грязные вилки. Если одному официанту нужна вилка, которую держит второй, он в конце концов ее получит. Если вилка грязная и не используется, второй официант немедленно отдаст ее первому. Если вилка грязная и используется, то второй философ когда-нибудь закончит есть, и его официант от­даст вилку первому. Чистая вилка означает, что другой философ захотел есть, его официант только что взял вилку или ждет вторую. По тем же причинам второй официант когда-нибудь обязательно получит вторую вилку, поскольку нет состояния, в котором каждый официант держит чистую вилку и просит еще одну. (Это еще одна причина, по которой нужна асиммет­ричная инициализация официантов.)


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