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


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


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

Логика алгоритмов поиска пути

Рис. 15.2.  Логика алгоритмов поиска пути

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

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

Возникает вопрос о средствах эмуляции дискретных событий. Имеются пакеты работы с дискретными событиями, но еще в 60-е гг. было показано, что мышление в терминах времени на самом деле требует собственного языка. Классическим примером здесь до сих пор является язык SIMULA 67. Он в явном виде провозглашает имитацию параллелизма и, следовательно, дает человеку возможность мыслить в терминах действующих агентов, что представляется более гибким и естественным способом выражения многих алгоритмов. Систему с дискретными событиями можно рассматривать в качестве общего метода преодоления противоречия между принципиальным параллелизмом и реальной последовательностью вычислений.

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




Начало  Назад  Вперед