понедельник, 3 октября 2011 г.

Data Flow, или Данные управляют командами. Теория

Заметку про асинхронных агентов я начал с описания недостатка модели рабочих элементов. Поэтому, чтобы сохранить традицию, заметку о Data Flow я начну с критики агентов. А что, вы серьёзно ожидали, что таковой не будет?


Когда традиционные модели не могут…
Главным достоинством агентов называлась возможность организации сложных взаимодействий и настройки зависимостей. Но что, если эти зависимости слишком строгие?

Рассмотрим следующий пример. Допустим, вы разрабатываете некоторый командный интерпретатор. Ему на вход поступает последовательный поток команд в текстовой форме. Команды отделены друг от друга символом перевода строки. Интерпретатор должен распознать команду, выполнить её и записать результат выполнения в выходной поток. Большинство программистов поступит традиционно: они создадут агента, который будет принимать на вход очередную строку (выше мы договорились, что одна строка – одна команда), распознавать команду, выполнять её и отправлять результат на выход. Другой агент будет считывать строки из входного потока данных и порождать агентов-исполнителей.

Но постойте, если команды поступают последовательно в определённом порядке, то клиент, выдавший их, ожидает, что ответы будут поступать в том же самом порядке: результат выполнения первой команды должен появиться в выходном потоке первым, результат второй команды – вторым и так далее. Выходит, что агент-исполнитель не может отправить результат выполнения команды на выход, когда ему вздумается. Как минимум он должен синхронизировать свои действия с остальными агентами. Подобная синхронизация сама по себе приводит к тому, что все агенты выстраиваются в очередь и начинают последовательно по одному отправлять результат на выход. При этом одной синхронизации не достаточно – она лишь решает задачу атомарности записи результата одним агентом, чтобы гарантировать корректный порядок мы должны ввести очерёдность команд и так далее и тому подобное. При этом мы не учли возможность зависимости команд друг от друга. Многопоточное ли получилось в этом случае приложение? Однозначно – ДА! А вот многозадачное ли?… Скорее - нет…

На самом деле я немного слукавил в начале, сказав про критику агентов. Данная проблема характерна для любой классической модели многопоточной разработки. Она носит название Lock Convoys – это ситуация, при которой потоки выстраиваются в очередь на одной взаимоисключающей блокировке. А при реализации вышеозначенного интерпретатора, агента можно легко заменить рабочим элементом, чтобы получить ровно такую же ошибку.


Развернём разум на 90 градусов
Разрешите представить: модель Data Flow или конвейер обработки. Чтобы её понять и увидеть параллельность, нужно начать мыслить чуть-чуть по иному. Эта модель предписывает разбивать крупную задачу со всеми внутренними зависимостями на мелкие, таким образом, чтобы каждая подзадача зависела от предыдущей только входными данными. Выстроив подзадачи одну за другой, вы получаете последовательный конвейер обработки данных. Каждый узел конвейера (задача) запускается только при поступлении на вход всех необходимых данных, он обрабатывает их совершенно независимо и передаёт на вход следующему узлу.

А где же параллельность, спросит читатель, если данные обрабатываются последовательно? Всё очень просто. Если каждый узел конвейера запускать в отдельном потоке, то на вход конвейеру данные можно подавать непрерывно. В этом случае каждый узел в любой момент времени будет обрабатывать некоторую порцию данных. Просто для разных узлов это будут разные данные.

Возвращаясь к примеру с командным интерпретатором, мы можем выделить следующие узлы конвейера:
  1. узел-читатель – считывает очередную строку;
  2. узел-парсер – выполняет разбор строки и формирует объект-команду;
  3. узел-исполнитель – исполняет команду, поступившую ему на вход в виде объекта, и отправляет результат дальше по конвейеру;
  4. узел-писатель – записывает в выходной поток результат, поступивший ему от предыдущего узла.
Командный интерпретатор, выполненный в архитектуре Data Flow

В результате такого представления нашей задачи мы, с одной стороны, остались в рамках многопоточной реализации: пока узел-исполнитель обрабатывает очередную команду, узел-парсер разбирает следующую строку, а в это время узел-писатель записывает результат обработки предыдущей команды. С другой стороны, обрабатывая команды последовательно (хоть и параллельно ), мы добились последовательного вывода результатов без блокировок, очередей и дополнительных буферов. Тем самым упростили код и избавились от дорогих операций ожидания. Более того, мы ещё и решили проблему зависимости команд друг от друга. По-моему здорово.

Комментариев нет:

Отправить комментарий