Стили и методы программирования



Взаимодействие процессов и распараллеливание - часть 5


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

Покажем, что решение задачи можно построить как систему взаимодействующих процессов с дискретным временем. Это - хороший метод структурирования задачи и отделения деталей от существенных черт: сначала мы строим абстрактное представление, а затем конкретизируем его, например укладывая, по сути своей, параллельный алгоритм в рамки последовательной программы3). Идея этого подхода восходит к У.-И. Далу и Ч. Хоору, которые использовали данную задачу для демонстрации возможностей системы с дискретными событиями, предоставляемой языками SIMULA 60 и SIMULA 67, совпадавшими по модели времени и структуре управления процессами.

Базовой концепцией в данной задаче естественно является

-параллелизм. Определение кратчайшего расстояния можно представить как соревнование действующих агентов4) , "разбредающихся" по разным дорогам. Сразу же разграничиваются два класса алгоритмов: прямые, когда общий процесс начинается с A, и обратные, для которых стартовым городом назначается B. Для показа принципиальных моментов достаточно рассмотреть по одному прямому и обратному алгоритму.

Прямой алгоритм разбредающихся агентов можно описать как поведение каждого агента по следующей схеме, в качестве параметра которой задается местонахождение агента:

  1. Если агент стоит в городе, то

    • Если местонахождение агента есть B, то цель достигнута. В качестве результата выдается пройденный путь.
    • Агент проверяет, является ли город запретным. Если это так, агент ликвидируется (понятно, что при этом информация по системе в целом не теряется - другие агенты продолжают действовать).
    • Город, в котором стоит агент, объявляется запретным.
    • Порождается столько наследников агента, сколько дорог исходит из текущего местонахождения данного агента. При этом в качестве локальных данных новых агентов задается пройденный путь, запомненный родительским агентом от A до текущего местонахождения (не принципиально, уничтожается ли родительский агент или он становится одним из экземпляров наследников).


      Содержание  Назад  Вперед