Дублируемые серверы
Опишем последнюю парадигму взаимодействия процессов — дублируемые серверы. Как уже говорилось, сервер — это процесс, управляющий некоторым ресурсом. Сервер можно дублировать, если есть несколько отдельных экземпляров ресурса; каждый сервер тогда управляет одним из экземпляров. Дублирование также можно использовать, чтобы дать клиентам иллюзию уникальности ресурса, когда в действительности экземпляров ресурса несколько. По-лобный пример был представлен при реализации дублирования файлов (см. раздел 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 вилок нет.
Во избежание взаимной блокировки вилки вначале распределяются принудительно, причем асимметрично, и все они грязные. Если бы, например, у каждого официанта вначале было по одной вилке, и все философы захотели есть, то каждый официант мог бы отдать свою вилку и затем удерживать полученную (взаимная блокировка!). Если бы какая-то вилка вначале была чистой, то официант не отдал бы эту удерживаемую вилку, пока философ не закончит есть; если процесс-философ завершился или философ никогда не захочет есть, то другой философ будет без конца ждать эту вилку.
Философы не будут голодать, поскольку официанты всегда отдают грязные вилки. Если одному официанту нужна вилка, которую держит второй, он в конце концов ее получит. Если вилка грязная и не используется, второй официант немедленно отдаст ее первому. Если вилка грязная и используется, то второй философ когда-нибудь закончит есть, и его официант отдаст вилку первому. Чистая вилка означает, что другой философ захотел есть, его официант только что взял вилку или ждет вторую. По тем же причинам второй официант когда-нибудь обязательно получит вторую вилку, поскольку нет состояния, в котором каждый официант держит чистую вилку и просит еще одну. (Это еще одна причина, по которой нужна асимметричная инициализация официантов.)
