Шаблон соединения

Шаблон соединения

Парадигма	параллельные вычисления , распределенное программирование
Разработчик	ИНРИА Инрия
Веб-сайт	Инрия Присоединяйтесь
Основные реализации
Присоединяйтесь к Java , Polyphonic C #, Unified Parallel C , Cω , присоединяется к библиотеке , Boost .
Под влиянием
Присоединяйтесь к исчислению

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

Этот шаблон основан на методе соединения и использует сопоставление с образцом . Конкретно, это делается путем разрешения определения объединения нескольких функций и/или каналов путем сопоставления шаблонов одновременных вызовов и сообщений. Это тип шаблона параллелизма , поскольку он упрощает и делает более гибким взаимодействие этих объектов и работу с парадигмой многопоточного программирования.

Описание

Шаблон соединения (или аккорд в Cω ) похож на суперконвейер с синхронизацией и сопоставлением. Фактически, эта концепция суммирует путем сопоставления и объединения набор сообщений, доступных из разных очередей сообщений , а затем обрабатывает их все одновременно с помощью одного обработчика. Это может быть представлено ключевыми словами when чтобы указать первое сообщение, которое мы ожидали, с and для подключения/сопряжения других каналов и do запустить несколько задач с разными собранными сообщениями. Созданный шаблон соединения обычно имеет следующую форму:

j.When(a1).And(a2). ... .And(an).Do(d)

Аргумент а1 из When(a1) может быть синхронным или асинхронным каналом или массивом асинхронных каналов. Каждый последующий аргумент вот и все And(ai) (для i > 1) должен быть асинхронным каналом.

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

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

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

Шаблон соединения определяется набором каналов пи-исчисления. x , который поддерживает две разные операции: отправку и получение, для его реализации нам нужны два имени вычисления соединения: имя канала x для отправки (сообщения) и имя функции x для получения значения (запроса). Смысл определения соединения заключается в том, что вызов x() возвращает значение, которое было отправлено по каналу x<>. Каждый раз, когда функции выполняются одновременно, инициируется процесс возврата и синхронизируется с другими объединениями.

J ::= //join patterns
| x<y> //message send pattern
| x(y) //function call pattern
| J | JBIS //synchronization

С точки зрения клиента, канал просто объявляет метод с тем же именем и сигнатурой. Клиент отправляет сообщение или отправляет запрос, вызывая канал в качестве метода. Метод продолжения должен ждать до тех пор, пока (если) на каждый из каналов, следующий за предложением When продолжения, не поступит одиночный запрос или сообщение. Если продолжение запускается, аргументы каждого вызова канала выводятся из очереди (таким образом, используются) и передаются (атомарно) в параметры продолжения.

Диаграмма классов шаблона соединения

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

История

π-исчисление – 1992 г.

принадлежит π-исчисление к семейству исчислений процессов , позволяет использовать математические формализмы для описания и анализа свойств параллельных вычислений с использованием имен каналов, передаваемых по самим каналам, и таким образом оно может описывать параллельные вычисления, конфигурация сети которых может быть изменена. изменяться в ходе вычислений.

Джойн-исчисление – 1993 г.

Шаблоны соединений впервые появились в основополагающем исчислении соединений Фурне и Гонтье, алгебре асинхронных процессов, предназначенной для эффективной реализации в распределенной среде. Соединение -исчисление — это исчисление процессов, столь же выразительное, как и полное π-исчисление . Он был разработан, чтобы обеспечить формальную основу для проектирования распределенных языков программирования, и поэтому намеренно избегает коммуникационных конструкций, встречающихся в других расчетах процессов, таких как рандеву- коммуникации.

Распределенное объединенное исчисление – 1996 г.

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

JoCaml, Funnel и Join Java – 2000 г.

ДжоКамл и воронка — это функциональные языки, поддерживающие декларативные шаблоны соединений. Они представляют идеи по прямой реализации процесса исчисления в функциональной обстановке.

Другое расширение (необщего) Java, JoinJava , было независимо предложено фон Ицштейном и Кирни.

Полифонический C # - 2002 г.

Карделли, Бентон и Фурне предложили объектно-ориентированную версию шаблонов соединений для C#, названную Polyphonic C# .

Ко – 2003 г.

Cω — это адаптация исчисления соединений к объектно-ориентированной среде. Этот вариант Polyphonic C# был включен в публичную версию Cω (также известного как Comega) в 2004 году.

Присоединение Скалы – 2007 г.

Scala Joins — это библиотека, позволяющая использовать Join-Pattern со Scala в контексте расширяемого сопоставления шаблонов для интеграции объединений в существующую структуру параллелизма на основе актеров.

Ерланг – 2009 г.

Erlang — это язык, который изначально поддерживает парадигму параллельного программирования, реального времени и распределенности. Параллелизм между процессами был сложным, поэтому в рамках проекта был создан новый язык JErlang ( J означает Join ), основанный на методе Join-исчисления.

Шаблон соединения в классической литературе по программированию

«Шаблоны соединения можно использовать для простого кодирования связанных идиом параллелизма, таких как актеры и активные объекты».

• Барьеры

class SymmetricBarrier
{
    public readonly Synchronous.Channel Arrive;

    public SymmetricBarrier(int n)
    {
        // Create j and init channels (elided)
        var pat = j.When(Arrive);
        for (int i = 1; i < n; i++)
            pat = pat.And(Arrive);
        pat.Do(() => { });
    }
}

• Проблема обедающих философов

var j = Join.Create();
Synchronous.Channel[] hungry;
Asynchronous.Channel[] chopstick;
j.Init(out hungry, n);
j.Init(out chopstick, n);

for (int i = 0; i < n; i++)
{
    var left = chopstick[i];
    var right = chopstick[(i+1) % n];
    j.When(hungry[i]).And(left).And(right).Do(() => {
        eat();
        left();
        right(); // replace chopsticks
    });
}

• Взаимное исключение

class Lock
{
    public readonly Synchronous.Channel Acquire;
    public readonly Asynchronous.Channel Release;

    public Lock()
    {
        // Create j and init channels (elided)
        j.When(Acquire).And(Release).Do(() => { });
        Release(); // initially free
    }
}

• Производители/Потребители

class Buffer<T>
{
    public readonly Asynchronous.Channel<T> Put;
    public readonly Synchronous<T>.Channel Get;

    public Buffer()
    {
        Join j = Join.Create(); // allocate a Join object
        j.Init(out Put);
        // bind its channels
        j.Init(out Get);
        j.When(Get).And(Put).Do // register chord
        (t => { return t; });
    }
}

• Блокировка чтения-записи

class ReaderWriterLock
{
    private readonly Asynchronous.Channel idle;
    private readonly Asynchronous.Channel<int> shared;
    public readonly Synchronous.Channel AcqR, AcqW, RelR, RelW;

    public ReaderWriterLock()
    {
        // Create j and init channels (elided)
        j.When(AcqR).And(idle).Do(() => shared(1));
        j.When(AcqR).And(shared).Do(n => shared(n+1));
        j.When(RelR).And(shared).Do(n => {
            if (n == 1)
            {
                idle();
            }
            else
            {
                shared(n-1);
            }
        });
        j.When(AcqW).And(idle).Do(() => { });
        j.When(RelW).Do(() => idle());
        idle(); // initially free
    }
}

• Семафоры

class Semaphore
{
    public readonly Synchronous.Channel Acquire;
    public readonly Asynchronous.Channel Release;

    public Semaphore(int n)
    {
        // Create j and init channels (elided)
        j.When(Acquire).And(Release).Do(() => { });
        for (; n > 0; n--)
            Release(); // initially n free
    }
}

Основные особенности и концепции

• Исчисление соединений : первое проявление шаблона соединения появляется вместе с этим исчислением процессов.
• Передача сообщений : шаблон соединения работает с системой передачи сообщений по параллельной причине.
• Канал : каналы используются для синхронизации и передачи сообщений между одновременно выполняющимися потоками. В общем, канал может участвовать в более чем одном шаблоне соединения, каждый шаблон определяет другое продолжение, которое может запускаться при вызове канала.
• Синхронный : шаблон соединения может использовать синхронный канал, возвращающий результат. Продолжение синхронного шаблона выполняется в потоке синхронного отправителя.
• Асинхронный : он также может использовать асинхронный канал, который не возвращает результата, но принимает аргументы. Продолжение асинхронного шаблона выполняется во вновь созданном потоке. Шаблон соединения может быть чисто асинхронным при условии, что его продолжением является подпрограмма, а в предложении When перечислены только асинхронные каналы.
• Объедините синхронный и асинхронный: объединение объявлений синхронного и асинхронного буфера приведет к созданию модуля, поддерживающего два типа связи потребителей.
• Планировщик : существует планирование между шаблонами соединений (например, циклический планировщик , планировщик первого совпадения).
• Шаблоны проектирования . Шаблон соединения — это, прежде всего, шаблон поведения и параллелизма.
• Параллельное программирование : оно выполняется одновременно.
• Сопоставление с образцом . Шаблон объединения работает с задачами сопоставления.
• Параллельное программирование : оно выполняет задачи параллельно.
• Распределенное программирование . С помощью этого шаблона задания можно распределять по разным агентам и средам.
• Программная транзакционная память : Программная транзакционная память (STM) является одной из возможных реализаций связи между соединениями.
• Перекрытие : шаблон может допускать шаблоны, объявленные для перекрывающихся наборов каналов.

Домен приложения

Мобильный агент

Мобильный агент — это автономный программный агент, обладающий определенными социальными способностями и, самое главное, мобильностью. Он состоит из компьютерного программного обеспечения и данных, которые могут автоматически перемещаться между разными компьютерами, продолжая выполнение.

Мобильные агенты можно использовать для согласования параллелизма и распределения, если использовать метод соединения. Вот почему была создана новая концепция под названием «распределенное объединение-исчисление»; это расширение соединения-исчисления с местоположениями и примитивами для описания мобильности. Это нововведение использует агентов в качестве запущенных процессов с их коммуникационными возможностями, чтобы дать представление о местоположении, которое представляет собой физическое место, выражающее фактическое положение агента. Благодаря Join-исчислению одно место можно атомарно переместить на другой сайт.

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

Таким образом, Join-исчисление является ядром языка распределенного программирования. В частности, операционная семантика легко реализуется в распределенной среде с ошибками. Таким образом, распределенное исчисление соединений рассматривает имена каналов и названия местоположений как значения первого класса с лексическими областями действия. Локация сама контролирует свои перемещения и может двигаться только к той локации, имя которой она получила. Это обеспечивает прочную основу для статического анализа и безопасной мобильности. Этого достаточно для выражения распределенных конфигураций. Однако при отсутствии сбоев выполнение процессов не зависит от распределения. Прозрачность местоположения важна для разработки мобильных агентов и очень полезна для проверки их свойств.

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

Сборник

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

• Join Compiler: компилятор языка под названием «join langage». Этот язык был создан только для исчисления соединений.
• Компилятор Jocaml. Архивировано 1 октября 2005 г. на Wayback Machine : компилятор расширения Objectif Caml, созданного для использования исчисления соединений.

Эти два компилятора работают с одной и той же системой — автоматом.

let A(n) | B() = P(n)
and A(n) | C() = Q(n)
;;

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

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

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

Реализации и библиотеки

Существует множество вариантов использования шаблонов соединения в разных языках. Некоторые языки используют шаблоны соединения в качестве основы своих реализаций, например Polyphonic C# или MC#, но другие языки интегрируют шаблон соединения с помощью такой библиотеки, как Scala Joins. для Scala или библиотеки Joins для VB. Более того, шаблон соединения используется в некоторых языках, таких как Scheme, для обновления шаблона соединения.

	ПРОЗРАЧНЫЙ	КБ	Присоединяется к библиотеке	Полифонический C#	Параллельный C#	Ко	Скала присоединяется	Ф#	Схема	Присоединяйтесь к Java	Хьюм	ДжоКамл
Сопоставление шаблонов	Да	Да	Да	Да	Да	Да	Да	Да	Да	Да	Да	Да
Планировщик между шаблонами соединения	Да: первый матч	Да: первая/круговая система	Да	Да	Да	Да	Да	Да	Нет	Да: случайный	Да: первая/круговая система	Да: случайный
Дженерики	Да	—	Да	Нет	—	Нет	Да	Да	Нет	Нет	Нет	Нет
Переопределение	Нет	Да	—	—	—	Да	Да	Да	Нет	Да	Нет	Нет

Присоединяйтесь к Java

Присоединяйтесь к Java — это язык, основанный на языке программирования Java, позволяющий использовать исчисление соединений. Он вводит три новые языковые конструкции:

• Методы соединения определяются двумя или более фрагментами соединения. Метод Join будет выполнен после вызова всех фрагментов шаблона Join. Если тип возвращаемого значения является стандартным типом Java, то ведущий фрагмент будет блокировать вызывающую сторону до тех пор, пока шаблон соединения не будет завершен и метод не выполнится. Если тип возвращаемого значения имеет тип сигнала, то ведущий фрагмент вернется немедленно. Все конечные фрагменты асинхронны, поэтому не блокируют вызывающую сторону.

Пример:

class JoinExample {
    int fragment1() & fragment2(int x) {
        // Will return value of x to caller of fragment1
        return x;
    }
}

• Асинхронные методы определяются с использованием типа возвращаемого сигнала. Он имеет те же характеристики, что и тип void, за исключением того, что метод возвращает значение немедленно. При вызове асинхронного метода создается новый поток для выполнения тела метода.

Пример:

class ThreadExample {
    signal thread(SomeObject x) {
        // This code will execute in a new thread
    }
}

• Модификаторы порядка

Фрагменты соединения могут повторяться в нескольких шаблонах соединения, поэтому может возникнуть ситуация, когда несколько шаблонов соединения завершаются при вызове фрагмента. Такой случай может произойти в приведенном ниже примере, если вызываются B(), C() и D(), а затем A(). Последний фрагмент A() завершает три шаблона, поэтому можно вызвать три возможных метода. Модификатор упорядоченного класса используется здесь, чтобы определить, какой метод соединения будет вызван. По умолчанию и при использовании модификатора неупорядоченного класса один из методов выбирается случайным образом. При использовании модификатора order приоритеты методов устанавливаются в соответствии с порядком их объявления.

Пример:

class ordered SimpleJoinPattern {
    void A() & B() {
    }
    void A() & C() {
    }
    void A() & D() {
    }
    signal D() & E() {
    }
}

Ближайшим родственным языком является Polyphonic C# .

ПРОЗРАЧНЫЙ

В кодировании Erlang синхронизация между несколькими процессами не является простой. Вот почему Ерланг, было создано расширение Erlang : J означает «Join». Действительно, чтобы преодолеть это ограничение, был реализован JErlang, Join-Calculus вдохновленное расширение Erlang, . Особенностями этого языка являются:

• Объединения допускают семантику первого сопоставления и возможность использования нескольких шаблонов с сохранением порядка сообщений.

operation() ->
    receive
        {ok, sum} and {val, X} and {val, Y} ->
            {sum, X + Y};
        {ok, mult} and {val, X} and {val, Y} ->
            {mult, X * Y};
        {ok, sub} and {val, X} and {val, Y} ->
            {sub, X - Y};
    end
end

• Guards обеспечивает дополнительную фильтрацию, не выражающуюся в шаблонах. Ограниченное количество экспрессий без побочных эффектов

receive
    {Transaction, M} and {limit, Lower, Upper}
        when (Lower <= M and M <= Upper ) ->
    commit_transaction(M, Transaction)
end

• Благодаря нелинейным шаблонам сообщения могут соответствовать нескольким соединениям.

receive
    {get, X} and {set, X} ->
        {found, 2, X}
end
...
receive
    {Pin, id} and {auth, Pin} and {commit, Id} ->
        perform_transaction(Pin, Id)
end

• распространение позволяет копировать правильные сообщения вместо их удаления.

receive
    prop({session, Id}) and {act, Action, Id} ->
        perform_action(Action, Id);
    {session, Id} and {logout, Id} ->
        logout_user(Id)
end
...
receive
    {Pin, id} and {auth, Pin} and {commit, Id} ->
        perform_transaction(Pin, Id)
end

• Синхронные звонки

receive
    {accept, Pid1} and {asynchronous, Value}
                   and {accept, Pid2} ->
        Pid1 ! {ok, Value},
        Pid2 ! {ok, Value}
end

С++

Игун Лю написал несколько классов для шаблона соединения, включая все полезные инструменты, такие как асинхронные и синхронные каналы, аккорды и т. д. Он интегрирован в проект Boost c++ .

template <typename V>
class buffer: public joint {
public:
  async<V> put;
  synch<V,void> get;
  buffer() {
    chord(get, put, &buffer::chord_body);
  }
  V chord_body(void_t g, V p) {
    return p;
  }
};

В этом примере показан потокобезопасный буфер и очередь сообщений с основными операциями put и get.

С#

Полифонический C#

Polyphonic C# — это расширение языка программирования C#. Он представляет новую модель параллелизма с синхронными и асинхронными (которые возвращают управление вызывающей стороне) методами и аккордами (также известными как «шаблоны синхронизации» или «шаблоны объединения»).

public class Buffer
{
    public String get() & public async put(String s)
    {
        return s;
    }
}

Это простой пример буфера.

МК#

Язык MC# представляет собой адаптацию языка Polyphonic C# для случая параллельных распределенных вычислений.

public handler Get2 long () & channel c1 (long x)
& channel c2 (long y)
{
    return (x + y);
}

Этот пример демонстрирует использование аккордов в качестве инструмента синхронизации.

Параллельный C#

Parallel C# основан на Polyphonic C# и добавляет некоторые новые концепции, такие как методы перемещения и функции высокого порядка.

using System;

class Test13
{
    int Receive() & async Send(int x)
    {
        return x * x;
    }

    public static void Main(string[] args)
    {
        Test13 t = new Test13();
        t.Send(2);
        Console.WriteLine(t.Receive());
    }
}

В этом примере показано, как использовать соединения.

Ко

Cω добавляет новые возможности языка для поддержки параллельного программирования (на основе более ранней версии Polyphonic C# ). Библиотека параллелизма соединений для C# и других языков .NET является производной от этого проекта.

Масштабируемые шаблоны соединений

Это простая в использовании декларативная и масштабируемая библиотека шаблонов соединений. Напротив библиотеки Руссо, у него нет глобальной блокировки. Фактически, он работает с CAS сравнения и обмена и системой сообщений Atomic. Библиотека используйте три улучшения для шаблона соединения:

• Кража сообщения для неиспользуемых ресурсов (разрешение баржа);
• Ленивая очередь экономит как на выделении, так и, возможно, на межпроцессорном взаимодействии, избегая выделения или постановки в очередь с помощью оптимистичного быстрого пути;
• Статус «ПРОБУЖДЕН»: гарантирует, что заблокированный синхронный абонент будет разбужен только один раз.

ДжоКамл

JoCaml — первый язык, в котором был реализован шаблон соединения. Действительно, вначале все различные реализации были скомпилированы с помощью компилятора JoCaml. Язык JoCaml является расширением языка OCaml . Он расширяет OCaml поддержкой параллелизма и синхронизации, распределенного выполнения программ и динамического перемещения активных фрагментов программы во время выполнения.

type coins = Nickel | Dime
and drinks = Coffee | Tea
and buttons = BCoffee | BTea | BCancel;;

(* def defines a Join-pattern set clause
 * "&" in the left side of = means join (channel synchronism)
 * "&" in the right hand side means: parallel process
 * synchronous_reply :== "reply" [x] "to" channel_name
 * synchronous channels have function-like types (`a -> `b)
 * asynchronous channels have types (`a Join.chan)
 * only the last statement in a pattern rhs expression can be an asynchronous message
 * 0 in an asynchronous message position means STOP ("no sent message" in CSP terminology).
   *)

def put(s) = print_endline s ; 0 (* STOP *)
  ;; (* put: string Join.chan *)

def serve(drink) = match drink with
                 Coffee -> put("Cofee")
                 | Tea -> put("Tea")
              ;; (* serve: drinks Join.chan *)

def refund(v) = let s = Printf.sprintf "Refund %d" v in put(s)
    ;; (* refund: int Join.chan *)

let new_vending serve refund =
  let vend (cost:int) (credit:int) = if credit >= cost
                      then (true, credit - cost)
                      else (false, credit)
  in
  def coin(Nickel) & value(v) = value(v+5) & reply () to coin
  or coin(Dime) & value(v) = value(v+10) & reply () to coin

  or button(BCoffee) & value(v) = 
     let should_serve, remainder = vend 10 v in
     (if should_serve then serve(Coffee) else 0 (* STOP *))
             & value(remainder) & reply () to button

  or button(BTea) & value(v) = 
     let should_serve, remainder = vend 5 v in
     (if should_serve then serve(Tea) else 0 (* STOP *))
             & value(remainder) & reply () to button

  or button(BCancel) & value(v) = refund( v) & value(0) & reply () to button
  in spawn value(0) ;
  coin, button  (* coin, button: int -> unit *)
  ;; (* new_vending: drink Join.chan -> int Join.chan -> (int->unit)*(int->unit) *)

let ccoin, cbutton = new_vending serve refund in
  ccoin(Nickel); ccoin(Nickel); ccoin(Dime);
  Unix.sleep(1); cbutton(BCoffee);
  Unix.sleep(1); cbutton(BTea);
  Unix.sleep(1); cbutton(BCancel);
  Unix.sleep(1) (* let the last message show up *)
  ;;

дает

Coffee
Tea
Refund 5

Хьюм

Хьюм — это строгий , строго типизированный функциональный язык для платформ с ограниченными ресурсами, с параллелизмом, основанным на асинхронной передаче сообщений, программировании потоков данных и синтаксисе, подобном Haskell .

Хьюм не обеспечивает синхронную передачу сообщений.

Он оборачивает набор шаблонов соединения общим каналом в виде блока , перечисляя все каналы во входном кортеже и определяя все возможные выходные данные в выходном кортеже.

Каждый шаблон соединения в наборе должен соответствовать типу входного кортежа поля, указывая «*» для необязательных каналов, давая выражение, тип которого соответствует выходному кортежу, отмечая «*» не подаваемые выходные данные.

В пункте Wire указывается

1. кортеж соответствующих входных источников или источников и, возможно, начальные значения
2. кортеж выходных пунктов назначения, являющихся каналами или приемниками (stdout, ..).

В блоке можно указать обработчики исключений с выражениями, соответствующими выходному кортежу.

data Coins = Nickel | Dime;
data Drinks = Coffee | Tea;
data Buttons = BCoffee | BTea | BCancel;

type Int = int 32 ;
type String = string ;
show u = u as string ;

box coffee
in ( coin :: Coins, button :: Buttons, value :: Int ) -- input channels
out ( drink_outp :: String, value’ :: Int, refund_outp :: String)  -- named outputs

match
-- * wildcards for unfilled outputs, and unconsumed inputs
  ( Nickel, *, v)  -> ( *, v + 5, *)
| ( Dime, *, v)    -> ( *, v + 10, *)
| ( *, BCoffee, v) -> vend Coffee 10 v
| ( *, BTea, v)    -> vend Tea 5 v
| ( *, BCancel, v) -> let refund u = "Refund " ++ show u ++ "\n"
                      in ( *, 0, refund v)
;

vend drink cost credit = if credit >= cost
                      then ( serve drink, credit - cost, *)
                      else ( *, credit, *);

serve drink = case drink of
               Coffee -> "Cofee\n"
               Tea -> "Tea\n"
;

box control
in (c :: char)
out (coin :: Coins, button:: Buttons)
match
 'n' -> (Nickel, *)
 | 'd' -> (Dime, *)
 | 'c' -> (*, BCoffee)
 | 't' -> (*, BTea)
 | 'x' -> (*, BCancel)
 | _ -> (*, *)
;

stream console_outp to "std_out" ;
stream console_inp from "std_in" ;

-- dataflow wiring

wire cofee
    -- inputs (channel origins)
    (control.coin, control.button, coffee.value’ initially 0)
    -- outputs destinations
    (console_outp, coffee.value, console_outp)
;

wire control
    (console_inp)
    (coffee.coin, coffee.button)
;

Визуальный Бейсик

Параллельный базовый уровень – CB

Расширение Visual Basic 9.0 с конструкциями асинхронного параллелизма, называемое Concurrent Basic (сокращенно CB), предлагает шаблоны соединения. CB (основан на более ранней работе над Polyphonic C#, Cω и библиотекой соединений) использует простой синтаксис, подобный событиям, знакомый программистам VB, позволяет объявлять общие абстракции параллелизма и обеспечивает более естественную поддержку наследования, позволяя подклассу дополнять набор. узоров. Класс CB может объявить метод, который будет выполняться , когда связь происходит по определенному набору локальных каналов, асинхронных и синхронных, образуя шаблон соединения.

Module Buffer

    Public Asynchronous Put(ByVal s As String)
    Public Synchronous Take() As String

    Private Function CaseTakeAndPut(ByVal s As String) As String _
        When Take, Put
            Return s
    End Function

End Module

В этом примере показаны все новые ключевые слова, используемые Concurrent Basic: Asynchronous, Synchronous и When.

Соединяет библиотеку (C# и VB)

Эта библиотека представляет собой высокоуровневую абстракцию шаблона соединения с использованием объектов и дженериков. Каналы — это специальные значения делегата из некоторого общего объекта Join (вместо методов).

class Buffer
{
    public readonly Asynchronous.Channel<string> Put;
    public readonly Synchronous<string>.Channel Get;

    public Buffer()
    {
        Join join = Join.Create();
        join.Initialize(out Put);
        join.Initialize(out Get);
        join.When(Get).And(Put).Do(delegate(string s) {
            return s;
        });
    }
}

В этом примере показано, как использовать методы объекта Join.

Скала

В Scala есть библиотека под названием «Scala Joins». Scala Joins использует шаблон соединения. Она предлагает использовать сопоставление с образцом Pattern Matching в качестве инструмента для создания моделей соединений. Примеры использования шаблона соединения в Scala можно найти здесь: Определения соединений в Scala .

Средства сопоставления с образцом этого языка были обобщены, чтобы обеспечить независимость представления объектов, используемых при сопоставлении с образцом. Итак, теперь в библиотеках можно использовать новый тип абстракции. Преимущество шаблонов соединений состоит в том, что они позволяют декларативно определять синхронизацию между различными потоками. Часто шаблоны соединения близко соответствуют конечному автомату, который определяет допустимые состояния объекта.

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

class ReaderWriterLock extends Joins {

  private val Sharing = new AsyncEvent[Int]
  val Exclusive, ReleaseExclusive = new NullarySyncEvent
  val Shared, ReleaseShared = new NullarySyncEvent
  join {
    case Exclusive() & Sharing(0) => Exclusive reply
    case ReleaseExclusive() => { Sharing(0); ReleaseExclusive reply }
    case Shared() & Sharing(n) => { Sharing(n+1); Shared reply }
    case ReleaseShared() & Sharing(1) => { Sharing(0); ReleaseShared reply }
    case ReleaseShared() & Sharing(n) => { Sharing(n-1); ReleaseShared reply }
  }
  Sharing(0) }

С помощью класса мы объявляем события в обычных полях. Таким образом, можно использовать конструкцию Join, чтобы включить сопоставление с образцом через список объявлений регистра. Этот список представляет собой => с частью объявления на каждой стороне. Слева — это модель шаблона соединения, показывающая комбинацию асинхронных и синхронных событий, а справа — тело соединения, которое выполняется с завершением модели соединения.

В Scala также можно использовать библиотеку актеров Scala. с шаблоном соединения. Например, неограниченный буфер:

val Put = new Join1[Int]
val Get = new Join
class Buffer extends JoinActor {
  def act() {
    receive { case Get() & Put(x) => Get reply x }
  } }

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

Практически те же инструменты доступны в F # для использования шаблона соединения.

Scala Join и Chymyst — это новые реализации шаблона соединения, усовершенствованные по сравнению с Scala Joins доктора Филиппа Халлера .

Хаскелл

Язык соединения — это реализация шаблона соединения в Haskell.

Схема

Шаблоны соединений позволяют использовать новый тип программирования, особенно для многоядерных архитектур, доступных во многих ситуациях программирования с высокими уровнями абстракции. Это основано на Охране и Распространении. Итак, пример этого нововведения был реализован в Scheme.

Защита необходима для того, чтобы гарантировать, что обновляются/извлекаются только данные с совпадающим ключом. Распространение может отменить элемент, прочитать его содержимое и вернуть элемент в хранилище. Конечно, во время чтения товар также находится в магазине. Охранники выражаются с помощью общих переменных. Новизна заключается в том, что шаблон соединения теперь может содержать расширенные и упрощенные части. Таким образом, в Scheme часть до / распространяется, а часть после / удаляется. Использование Goal-Based позволяет разделить работу на множество задач и объединить все результаты в конце с помощью шаблона соединения. В системе под названием «MiniJoin» реализована возможность использования промежуточного результата для решения других задач, если это возможно. Если это невозможно, он ждет решения других задач, чтобы решиться сам.
Таким образом, приложение шаблона параллельного соединения, выполняемое параллельно в многоядерной архитектуре, не гарантирует, что параллельное выполнение приведет к конфликтам. Чтобы гарантировать это и высокую степень параллелизма, используется программная транзакционная память (STM) в хорошо настроенной параллельной структуре данных, основанной на атомарном сравнении и обмене (CAS). Это позволяет параллельно выполнять множество одновременных операций в многоядерной архитектуре. Более того, атомарное выполнение используется для предотвращения «ложного конфликта» между CAS и STM.

Другие похожие шаблоны проектирования

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

• Шаблон последовательности: состоит из ожидания завершения задачи для переключения на другую (классическая реализация).

• Шаблон разделения ( параллельное разделение ): параллельное выполнение нескольких задач (например, сокращение карты ).

См. также

• Join Java . Join Java — это язык программирования, расширяющий стандартный язык программирования Java.
• Joins (библиотека параллелизма) . Joins — это API асинхронных параллельных вычислений от Microsoft Research для .NET Framework.
• Исчисление соединений . Исчисление соединений было разработано, чтобы обеспечить формальную основу для разработки распределенных языков программирования.

Ссылки

• Седрик, Фурне; Люк, Маранге (15 августа 2006 г.). «Язык JOIN-исчисления» . Национальный институт исследований в области компьютерных наук и автоматизации . Проверено 9 октября 2012 г.
• «Присоединяйтесь к расчету» . Cunningham & Cunningham, Inc., 25 октября 2009 г. Проверено 9 октября 2012 г.
• Фурне, Седрик; Гонтье, Жорж; Леви, Жан-Жак; Маранге, Люк (1996). «Исчисление мобильных агентов». CONCUR '96: Теория параллелизма . Конспекты лекций по информатике. Полет. 1119. Ле Шене: Теория параллелизма. стр. 406–421. дои : 10.1007/3-540-61604-7_67 . ISBN  978-3-540-61604-7 .
• Малудзинский, Славомир; Добровольский, Гжегож (2007). «Агентная среда и знания в исчислении распределенных соединений». Мультиагентные системы и приложения V . Конспекты лекций по информатике. Том. 4696. стр. 298–300. дои : 10.1007/978-3-540-75254-7_30 . ISBN  978-3-540-75253-0 .
• Руссио, Клаудио (2006). «Библиотека параллелизма соединений». Практические аспекты декларативных языков . Конспекты лекций по информатике. Том. 4354. Кембридж: Практические аспекты декларативных языков. стр. 260–274. CiteSeerX   10.1.1.187.8792 . дои : 10.1007/978-3-540-69611-7_17 . ISBN  978-3-540-69608-7 .
• Маранге, Люк; Ле Фессан, Фабрис (25 сентября 2007 г.). «Составление шаблонов соединений» . Ле Шене Франция.
• Халлер, Филипп; Ван Катсем, Том (2008). «Реализация соединений с использованием расширяемого сопоставления с образцом». Координационные модели и языки . Конспекты лекций по информатике. Том. 5052. Лозанна: Координационные модели и языки. стр. 135–152. CiteSeerX   10.1.1.210.1242 . дои : 10.1007/978-3-540-68265-3_9 . ISBN  978-3-540-68264-6 .
• Сульцманн, Мартин; С.Л. Лам, Эдмунд. «Шаблоны параллельного соединения с защитой и распространением» . Дания.
• Фурне, Седрик; Гонтье, Жорж (2002). «Исчисление соединений: язык распределенного мобильного программирования». Прикладная семантика . Конспекты лекций по информатике. Том. 2395. Спрингер. стр. 268–332. CiteSeerX   10.1.1.4.4788 . дои : 10.1007/3-540-45699-6_6 . ISBN  978-3-540-44044-4 .
• Ма, Цинь; Маранге, Люк (5 апреля 2004 г.). «Компиляция сопоставления шаблонов в шаблонах соединения». КОНКУР 2004 — Теория параллелизма . Конспекты лекций по информатике. Том. 3170. ИНРИА. стр. 417–431. CiteSeerX   10.1.1.499.8443 . дои : 10.1007/978-3-540-28644-8_27 . ISBN  978-3-540-22940-7 . S2CID   9956643 .
• Сингх, Сатнам (6 января 2007 г.). «Комбинаторы высшего порядка для шаблонов соединения с использованием STM» .
• МОНЬЕ, Герт (2010), Координация на основе шаблонов в структурах услуг, основанных на процессах , Левен, Бельгия: Katoliek Universiteit Leuven
• Руссо, Клаудио В. (23 октября 2008 г.). «Шаблоны соединений для Visual Basic». Уведомления ACM SIGPLAN . 43 (10): 53–72. дои : 10.1145/1449955.1449770 .
• Аарон, Турон; Руссо, Клаудио В. (27 октября 2011 г.). Масштабируемые шаблоны соединений (PDF) . Нью-Йорк: Ассоциация вычислительной техники. ISBN  978-1-4503-0940-0 .
• Гузев, Вадим Б. (апрель 2008 г.). «Параллельный C#: использование аккордов и функций высшего порядка при разработке языков параллельного программирования». Материалы Международной конференции по методам и приложениям параллельной и распределенной обработки 2008 г., PDPTA 2008 (PDF) . ЦСРЭА Пресс. ISBN  978-1601320841 .

Внешние ссылки

• Параллельный базовый
• Масштабируемые соединения
• Библиотека параллелизма соединений
• INRIA, домашняя страница Присоединяйтесь к исчислению