Распределенные алгоритмы — страница 13

  • Просмотров 11691
  • Скачиваний 574
  • Размер файла 960
    Кб

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

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

6). Если информация должна быть доступна всем процессам, или все процессы должны ждать выполнения некоторого глобального условия, необходимо иметь схему передачи сообщений, которая каким-либо образом «дозванивается» до всех процессов. (2)   Выборность (глава 7). Некоторые задачи должны быть осуществлены точно одним процессом из множества, например, генерирование вывода или инициализация структуры данных. Если, как иногда

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

результаты окончательными. (4)   Распределение ресурсов. Узел может потребовать доступ к некоторым ресурсам, которые доступны, где-либо в сети, но не знает, где этот ресурс находится. Поддержка таблицы, которая показывает местоположение каждого ресурса не всегда адекватна, потому что число потенциальных ресурсов может быть слишком большим для этого, или ресурсы могут мигрировать от одного узла к другому. В этом случае,

запрашивающий узел может опрашивать все или некоторые узлы на предмет доступности ресурса, например, используя широковещательный механизм. Алгоритмы для этой проблемы могут базироваться на волновых механизмах, описанных в главе 6, см., например Баратц и другие [BGS87]. (5)   Взаимное исключение. Проблема взаимного исключения встает, если процессы могут полагаться на общий ресурс, который может быть использован только одним