Шаблон соединения - Join-pattern

Шаблон соединения
Парадигмапараллельные вычисления, распределенное программирование
РазработчикINRIA Inria
Интернет сайтИнрия Присоединяйтесь
Основной реализации
Присоединяйтесь к Java, Полифонический C #, Унифицированный параллельный C, Cω, Присоединяется к библиотеке, Способствовать росту.
Под влиянием
Присоединяйтесь к исчислению

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

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

Описание

Образец соединения (или аккорд в Cω ) похож на супер конвейер с синхронизацией и сопоставлением. Фактически, эта концепция резюмируется путем сопоставления и присоединения к набору сообщений, доступных из разных очереди сообщений, а затем обрабатывает их все одновременно одним обработчиком.[1] Он может быть представлен ключевыми словами когда чтобы указать первое сообщение, которое мы ожидали, с и для присоединения / сопряжения других каналов и делать запускать несколько задач с разными собранными сообщениями. Сконструированный шаблон соединения обычно принимает такую ​​форму:

j.Когда(а1).И(а2). ... .И(ан).Делать(d)

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

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

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

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

J ::= // объединяем шаблоны| Икс<у> // шаблон отправки сообщения| Икс(у) // шаблон вызова функции| J | JBIS // синхронизация

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

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

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

История

π-исчисление - 1992

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

Соединительное исчисление - 1993

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

Распределенное объединенное исчисление - 1996

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

JoCaml, Funnel и Join Java - 2000

JoCaml [11][12] и воронка [13][14] - это функциональные языки, поддерживающие декларативные шаблоны соединения. Они представляют идеи для непосредственной реализации расчетов процесса в функциональной среде.

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

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

Карделли, Бентон и Фурнет предложили объектно-ориентированную версию шаблонов соединения для C # под названием Полифонический C #.[16]

Cω - 2003 г.

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

Scala присоединяется - 2007

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

Джерланг - 2009

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

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

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

учебный класс Симметричный барьер {общественный только чтение Синхронный.Канал Прибыть;общественный Симметричный барьер(int п) {    // создаем j и init каналы (исключены)    вар погладить = j.Когда(Прибыть);    за (int я = 1; я < п; я++) погладить = погладить.И(Прибыть);    погладить.Делать(() => { });}}
вар j = Присоединиться.Создавать();Синхронный.Канал[] голодный;Асинхронный.Канал[] палочка для еды;j.В этом(из голодный, п); j.В этом(из палочка для еды, п);за (int я = 0; я < п; я++) {    вар оставили = палочка для еды[я];    вар верно = палочка для еды[(я+1) % п];    j.Когда(голодный[я]).И(оставили).И(верно).Делать(() => {    есть(); оставили(); верно(); // заменяем палочки для еды    });}
учебный класс Замок {    общественный только чтение Синхронный.Канал Приобретать;    общественный только чтение Асинхронный.Канал Релиз;    общественный Замок() {        // создаем j и init каналы (опущены)        j.Когда(Приобретать).И(Релиз).Делать(() => { });        Релиз(); // изначально бесплатно    }}
учебный класс Буфер<Т> {    общественный только чтение Асинхронный.Канал<Т> Положить;    общественный только чтение Синхронный<Т>.Канал Получать;    общественный Буфер() {        Присоединиться j = Присоединиться.Создавать(); // выделяем объект Join        j.В этом(из Положить);        // привязываем его каналы        j.В этом(из Получать);        j.Когда(Получать).И(Положить).Делать // регистрируем аккорд        (т => { возвращаться т; });    }}
учебный класс ReaderWriterLock {    частный только чтение Асинхронный.Канал праздный;    частный только чтение Асинхронный.Канал<int> общий;    общественный только чтение Синхронный.Канал AcqR, AcqW, RelR, RelW;    общественный ReaderWriterLock() {    // создаем j и init каналы (исключены)    j.Когда(AcqR).И(праздный).Делать(() => общий(1));    j.Когда(AcqR).И(общий).Делать(п => общий(п+1));    j.Когда(RelR).И(общий).Делать(п => {    если (п == 1) праздный(); еще общий(п-1);    });    j.Когда(AcqW).И(праздный).Делать(() => { });    j.Когда(RelW).Делать(() => праздный());    праздный(); // изначально бесплатно}}
учебный класс Семафор {    общественный только чтение Синхронный.Канал Приобретать;    общественный только чтение Асинхронный.Канал Релиз;    общественный Семафор(int п) {        // создаем j и init каналы (опущены)        j.Когда(Приобретать).И(Релиз).Делать(() => { });        за (; п > 0; п--) Релиз(); // изначально n бесплатно    }}

Основные функции и концепции

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

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

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

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

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

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

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

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

Компиляция

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

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

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

пусть A (n) | B () = P (n) и A (n) | C () = Q (n) ;;

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

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

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

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

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

ДжерлангCBПрисоединяется к библиотекеПолифонический C #Параллельный C #CωScala присоединяетсяF #СхемаПрисоединяйтесь к JavaЮмJoCaml
Соответствие шаблоновдададададададададададада
Планировщик шаблонов соединенийДа: первый матчДа: первая / круговая системададададададаНетДа: случайныйДа: первая / круговая системаДа: случайный
ДженерикидаНет данныхдаНетНет данныхНетдадаНетНетНетНет
ОтменаНетдаНет данныхНет данныхНет данныхдададаНетдаНетНет

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

Присоединяйтесь к Java [29] это язык, основанный на Язык программирования Java позволяя использовать исчисление соединений. Он вводит три новых языковых конструкции:

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

Пример:

учебный класс JoinExample {    int фрагмент1() & фрагмент2(int Икс) {        // Вернет значение x вызывающей стороне фрагмента 1        возвращаться Икс;    }}
  • Асинхронные методы определяются с использованием типа возвращаемого сигнала. Он имеет те же характеристики, что и тип void, за исключением того, что метод вернется немедленно. Когда вызывается асинхронный метод, создается новый поток для выполнения тела метода.

Пример:

учебный класс ThreadExample {    сигнал нить(SomeObject Икс) {        // Этот код будет выполняться в новом потоке    }}
  • Модификаторы заказа

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

Пример:

учебный класс упорядоченный SimpleJoinPattern {    пустота А() & B() {    }    пустота А() & C() {    }    пустота А() & D() {    }    сигнал D() & E() {    }}

Ближайший родственный язык - это Полифонический C #.

Джерланг

В Erlang Синхронизация кодирования между несколькими процессами не является простой задачей. Вот почему Джерланг,[30] расширение Erlang был создан, J для присоединения. Действительно, чтобы преодолеть это ограничение, JErlang был реализован, Соединение-исчисление вдохновленное расширение Erlang. Особенности этого языка:

  • Присоединяется допускает семантику first Match и возможность наличия нескольких шаблонов с сохранением порядка сообщений.
операция() ->    получить        {Ok, сумма} и {вал, Икс} и {вал, Y} ->            {сумма, Икс + Y};        {Ok, мульт} и {вал, Икс} и {вал, Y} ->            {мульт, Икс * Y};        {Ok, суб} и {вал, Икс} и {вал, Y} ->            {суб, Икс - Y};    конецконец
  • Охранники обеспечивает дополнительную фильтрацию без использования шаблонов. Ограниченное количество выражений без побочных эффектов
получить    {Сделка, M} и {предел, Ниже, Верхний}        когда (Ниже <= M и M <= Верхний ) ->    commit_transaction(M, Сделка)конец
  • С Нелинейные паттерны, сообщения могут соответствовать нескольким соединениям
получить    {получать, Икс} и {набор, Икс} ->        {найденный, 2, Икс}конец...получить    {Штырь, я бы} и {авторизация, Штырь} и {совершить, Идентификатор} ->        выполнить_transaction(Штырь, Идентификатор)конец
  • распространение позволяет копировать правильные сообщения вместо их удаления.
получить    опора({сессия, Идентификатор}) и {действовать, Действие, Идентификатор} ->        Perform_action(Действие, Идентификатор);    {сессия, Идентификатор} и {выйти, Идентификатор} ->        logout_user(Идентификатор)конец...получить    {Штырь, я бы} и {авторизация, Штырь} и {совершить, Идентификатор} ->        выполнить_transaction(Штырь, Идентификатор)конец
  • Синхронные звонки
получить    {принимать, Pid1} и {асинхронный, Ценить}                   и {принимать, Pid2} ->        Pid1 ! {Ok, Ценить},        Pid2 ! {Ok, Ценить}конец

C ++

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

шаблон <typename V>учебный класс буфер: общественный соединение {общественный:  асинхронный<V> положить;  синхронизировать<V,пустота> получать;  буфер() {    аккорд(получать, положить, &буфер::chord_body);  }  V chord_body(void_t грамм, V п) {    возвращаться п;  }};

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

C #

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

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

общественный учебный класс Буфер {    общественный Нить получать() & общественный асинхронный положить(Нить s) {        возвращаться s;    }}

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

MC #

MC # language - это адаптация языка Polyphonic C # для параллельных распределенных вычислений.

общественный обработчик Get2 длинный () & канал c1 (длинный Икс)& канал c2 (длинный у){    возвращаться (Икс + у);}

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

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

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

с помощью Система; учебный класс Test13 {    int Получить() & асинхронный послать(int Икс) {        возвращаться Икс * Икс;    }     общественный статический пустота Главный(нить[] аргументы) {        Test13 т = новый Test13();        т.послать(2);        Консоль.WriteLine(т.Получить());    }}

Этот пример демонстрирует, как использовать объединения.[33]

Cω

Cω добавляет новые языковые функции для поддержки параллельное программирование (на основе более раннего Полифонический C # ). Библиотека Joins Concurrency Library для C # и других языков .NET является производной от этого проекта.[34][35]

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

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

  • Сообщение о краже неиспользованных ресурсов (разрешение баржа);
  • Ленивая очередь экономит как на выделении, так и потенциально на межпроцессорной связи, избегая выделения или постановки в очередь с оптимистичным быстрым путем;
  • Статус «WOKEN»: гарантирует, что заблокированный синхронный вызывающий абонент будет разбужен только один раз.

JoCaml

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

тип монеты = Никель | Дайми напитки = Кофе | Чайи кнопки = Bcoffee | BTea | BCancel;;(* def определяет предложение набора шаблонов соединения * "&" в левой части = означает соединение (синхронизация каналов) * "&" в правой части означает: параллельный процесс. * synchronous_reply: == "ответ" [x] "на" имя_канала * синхронные каналы имеют функционально-подобные типы (`a ->` b) * асинхронные каналы имеют типы (`Join.chan) * только последний оператор в выражении rhs шаблона может быть асинхронным сообщением * 0 в позиции асинхронного сообщения означает STOP («сообщение не отправлено» в терминологии CSP).   *)def положить(s) = print_endline s ; 0 (* ОСТАНОВКА *)   ;; (* положите: строка Join.chan *)def обслуживать(напиток) = матч напиток с                 Кофе -> положить("Кофе")                 | Чай -> положить("Чай")              ;; (* подавать: напитки Join.chan *)def возврат(v) = позволять s = Printf.спринт «Возврат% d» v в положить(s)     ;; (* возврат: int Join.chan *)позволять new_vending обслуживать возврат =  позволять продавать (Стоимость:int) (кредит:int) = если кредит >= Стоимость                      тогда (истинный, кредит - Стоимость)                      еще (ложный, кредит)  в  def монета(Никель) & ценить(v) = ценить(v+5) & Ответить () к монета  или же монета(Дайм) & ценить(v) = ценить(v+10) & Ответить () к монета  или же кнопка(BCoffee) & ценить(v) =      позволять should_serve, остаток = продавать 10 v в     (если should_serve тогда обслуживать(Кофе) еще 0 (* ОСТАНОВКА *))              & ценить(остаток) & Ответить () к кнопка  или же кнопка(BTea) & ценить(v) =      позволять should_serve, остаток = продавать 5 v в     (если should_serve тогда обслуживать(Чай) еще 0 (* ОСТАНОВКА *))              & ценить(остаток) & Ответить () к кнопка  или же кнопка(BCancel) & ценить(v) = возврат( v) & ценить(0) & Ответить () к кнопка  в порождать ценить(0) ;  монета, кнопка  (* монета, кнопка: int -> unit *)  ;; (* new_vending: drink Join.chan -> int Join.chan -> (int-> unit) * (int-> unit) *)позволять ccoin, cbutton = new_vending обслуживать возврат в  ccoin(Никель); ccoin(Никель); ccoin(Дайм);   Unix.спать(1); cbutton(BCoffee);   Unix.спать(1); cbutton(BTea);   Unix.спать(1); cbutton(BCancel);  Unix.спать(1) (* пусть появится последнее сообщение *)  ;;

дает

CoffeeTeaRefund 5

Юм

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

Юм не обеспечивает синхронный обмен сообщениями.

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

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

А провод статья определяет

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

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

данные Монеты = Никель | Дайм;данные Напитки = Кофе | Чай;данные Кнопки = BCoffee | BTea | BCancel;тип Int = int 32 ;тип Нить = нить ;Показать ты = ты в качестве нить ;коробка кофев ( монета :: Монеты, кнопка :: Кнопки, ценить :: Int ) - входные каналыиз ( drink_outp :: Нить, ценить’ :: Int, return_outp :: Нить)  - названные выходыматч- * подстановочные знаки для незаполненных выходов и неиспользованных входов  ( Никель, *, v)  -> ( *, v + 5, *)| ( Дайм, *, v)    -> ( *, v + 10, *)| ( *, BCoffee, v) -> продавать Кофе 10 v| ( *, BTea, v)    -> продавать Чай 5 v| ( *, BCancel, v) -> позволять возврат ты = "Возврат " ++ Показать ты ++ " п"                      в ( *, 0, возврат v);продавать напиток Стоимость кредит = если кредит >= Стоимость                      тогда ( обслуживать напиток, кредит - Стоимость, *)                      еще ( *, кредит, *);обслуживать напиток = дело напиток из               Кофе -> "Кофе п"               Чай -> "Чай п";коробка контрольв (c :: char)из (монета :: Монеты, кнопка:: Кнопки)матч 'п' -> (Никель, *) | 'd' -> (Дайм, *) | 'c' -> (*, BCoffee) | 'т' -> (*, BTea) | 'Икс' -> (*, BCancel) | _ -> (*, *);транслировать console_outp к "std_out" ;транслировать console_inp из "std_in" ;- проводка потока данных провод кофе    - входы (истоки каналов)    (контроль.монета, контроль.кнопка, кофе.ценить’ первоначально 0)       - выводит направления    (console_outp, кофе.ценить, console_outp); провод контроль    (console_inp)    (кофе.монета, кофе.кнопка);

Visual Basic

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

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

Модуль Буфер    Общественные Асинхронный Положить(ByVal s В качестве Нить)    Общественные Синхронный Брать() В качестве Нить    Частный Функция CaseTakeAndPut(ByVal s В качестве Нить) В качестве Нить _        Когда Брать, Положить             Возвращаться s    Конец ФункцияКонец Модуль

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

Библиотека объединений (C # и VB)

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

учебный класс Буфер {    общественный только чтение Асинхронный.Канал<нить> Положить;    общественный только чтение Синхронный<нить>.Канал Получать;    общественный Буфер() {        Присоединиться присоединиться = Присоединиться.Создавать();        присоединиться.Инициализировать(из Положить);          присоединиться.Инициализировать(из Получать);        присоединиться.Когда(Получать).И(Положить).Делать(делегировать(нить s) {             возвращаться s;     });    }}

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

Scala

В Scala есть библиотека под названием "Scala Joins". Scala присоединяется для использования шаблона соединения предлагается использовать сопоставление с шаблоном Соответствие шаблону как инструмент для создания моделей стыков. Вы можете найти примеры использования шаблона соединения в scala здесь: Определения соединений в Scala.

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

В Scala можно решить многие проблемы с сопоставлением с образцом и объединениями Scala, например, Reader-Writer.[26]

учебный класс ReaderWriterLock расширяет Присоединяется {  частный вал Обмен = новый AsyncEvent[Int]  вал Эксклюзивный, ReleaseExclusive = новый NullarySyncEvent  вал Общий, ReleaseShared = новый NullarySyncEvent  присоединиться {    дело Эксклюзивный() & Обмен(0) => Эксклюзивный Ответить    дело ReleaseExclusive() => { Обмен(0); ReleaseExclusive Ответить }    дело Общий() & Обмен(п) => { Обмен(п+1); Общий Ответить }    дело ReleaseShared() & Обмен(1) => { Обмен(0); ReleaseShared Ответить }    дело ReleaseShared() & Обмен(п) => { Обмен(п-1); ReleaseShared Ответить }  }  Обмен(0) }

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

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

вал Положить = новый Присоединиться1[Int]вал Получать = новый Присоединитьсяучебный класс Буфер расширяет JoinActor {  def действовать() {    получить { дело Получать() & Положить(Икс) => Получать Ответить Икс }  } }

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

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

Scala присоединиться и Химыст являются более новыми реализациями шаблона соединения, улучшающими работу доктора Филиппа Галлера Scala присоединяется.

Haskell

Присоединиться к языку - это реализация шаблона соединения в Haskell.

Схема

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

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

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

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

  • Шаблон последовательности: состоит из ожидания завершения одной задачи, чтобы переключиться на другую (классическая реализация).[43]
  • Шаблон разделения (параллельный раскол): выполнять несколько задач одновременно (например, Уменьшение карты ).[44]

Смотрите также

Рекомендации

Примечания

  1. ^ Таральский дракон (25 октября 2009 г.). «Присоединиться к исчислению». Проверено 2012. Проверить значения даты в: | accessdate = (помощь)
  2. ^ Руссо, Клаудио В. (23 октября 2008 г.). «Шаблоны соединения для Visual Basic». Уведомления ACM SIGPLAN. 43 (10): 10. Дои:10.1145/1449955.1449770.
  3. ^ «Параллельный C #». Проверено 2012. Проверить значения даты в: | accessdate = (помощь)
  4. ^ Руссо, Клаудио В. "Шаблоны соединения для Visual Basic": 2. Цитировать журнал требует | журнал = (помощь)
  5. ^ Фурне, Седрик; Гонтье, Жорж (2002). Прикладная семантика. Конспект лекций по информатике. 2395. Каминья. С. 268–332. CiteSeerX  10.1.1.4.4788. Дои:10.1007/3-540-45699-6_6. ISBN  978-3-540-44044-4.
  6. ^ а б c d е ж Присоединяйтесь к шаблонам для Visual Basic и Клаудио В. Руссо.
  7. ^ Руссо, Клаудио В. (23 октября 2008 г.). «Шаблоны соединения для Visual Basic». Уведомления ACM SIGPLAN. 43 (10): 5. Дои:10.1145/1449955.1449770.
  8. ^ Руссо, Клаудио В. (23 октября 2008 г.). «Шаблоны соединения для Visual Basic». Уведомления ACM SIGPLAN. 43 (10): 18. Дои:10.1145/1449955.1449770.
  9. ^ а б c Маранге, Люк; Ле Фессан, Фабрис (25 сентября 2007 г.). «Компиляция шаблонов соединений». Le Chesnay Франция. Цитировать журнал требует | журнал = (помощь)
  10. ^ Фурне, Седрик; Гонтье, Жорж; Леви, Жан-Жак; Маранге, Люк (1996). CONCUR '96: теория параллелизма. Конспект лекций по информатике. 1119. Ле Шене: теория параллелизма. С. 406–421. Дои:10.1007/3-540-61604-7_67. ISBN  978-3-540-61604-7.
  11. ^ Фурне, Седрик; Ле Фессан, Фабрис; Маранге, Люк; Шмитт, А. (сентябрь 2000 г.). «JoCaml: язык для параллельного распределенного и мобильного программирования». По углубленному функциональному программированию, 4-я международная школа, Оксфорд, август 2002 г.. 2638.
  12. ^ Conchon, S .; Ле Фессан, Ф. (1999). «JoCaml: мобильные агенты для Objective-Caml». В Первом международном симпозиуме по агентским системам и приложениям. (ASA'99) / Третий международный симпозиум по мобильным агентам (MA'99).
  13. ^ Одерский, Мартин (сентябрь 2000 г.). «Обзор функциональных сетей». Летняя школа, Каминья, Португалия, сентябрь 2000 г.. 2395.
  14. ^ Одерский, Мартин (2000). «Функциональные сети». В материалах Европейского симпозиума по программированию. Конспект лекций по информатике. Конспект лекций по информатике. 1782: 1–25. Дои:10.1007/3-540-46425-5_1. ISBN  978-3-540-67262-3.
  15. ^ Itzstein, G.S .; Кирни, Д. (2001). «Присоединяйтесь к Java: альтернативная семантика параллелизма для Java». Технический отчет ACRC-01-001, Университет Южной Австралии.
  16. ^ Benton, N .; Фурнет, К. (июнь 2002 г.). «Современные абстракции параллелизма для C #». В трудах 16-й Европейской конференции по объектно-ориентированному программированию (ECOOP 2002), номер 2374 в LNCS.
  17. ^ Benton, N .; Карделли, Л. (2004). «Современные абстракции параллелизма для C #. Транзакции ACM на языках программирования и системах». 26. Цитировать журнал требует | журнал = (помощь)
  18. ^ Сингх, Сатнам (6 января 2007 г.). «Комбинаторы высшего порядка для шаблонов соединения с использованием STM»: 1. Цитировать журнал требует | журнал = (помощь)
  19. ^ а б Аарон, Турон; Руссо, Клаудио В. (27 октября 2011 г.). Масштабируемые шаблоны соединений (PDF). Портленд, Орегон, США. п. 4. ISBN  9781450309400.
  20. ^ Аарон, Турон; Руссо, Клаудио В. (27 октября 2011 г.). Масштабируемые шаблоны соединений (PDF). Портленд, Орегон, США. п. 1. ISBN  9781450309400.
  21. ^ а б Аарон, Турон; Руссо, Клаудио В. (27 октября 2011 г.). Масштабируемые шаблоны соединений (PDF). Портленд, Орегон, США. п. 3. ISBN  9781450309400.
  22. ^ Аарон, Турон; Руссо, Клаудио В. (27 октября 2011 г.). Масштабируемые шаблоны соединений (PDF). Портленд, Орегон, США. п. 2. ISBN  9781450309400.
  23. ^ а б c Фурне, Седрик; Гонтье, Жорж; Леви, Жан-Жак; Маранге, Люк; Реми, Дидье (1996). CONCUR '96: теория параллелизма. Конспект лекций по информатике. 1119. Ле Шене: теория параллелизма. С. 406–421. Дои:10.1007/3-540-61604-7_67. ISBN  978-3-540-61604-7.
  24. ^ Малудзинский, Славомир; Добровольский, Гжегож (2007). «Среда агента и знания в распределенном исчислении соединений». Многоагентные системы и приложения V. Конспект лекций по информатике. 4696. С. 298–300. Дои:10.1007/978-3-540-75254-7_30. ISBN  978-3-540-75253-0.
  25. ^ Ма, Цинь; Маранге, Люк (5 апреля 2004 г.). CONCUR 2004 - Теория параллелизма. Конспект лекций по информатике. 3170. INRIA. С. 417–431. CiteSeerX  10.1.1.499.8443. Дои:10.1007/978-3-540-28644-8_27. ISBN  978-3-540-22940-7.
  26. ^ а б c Галлер, Филипп; Ван Катсем, Том (2008). Координационные модели и языки. Конспект лекций по информатике. 5052. Лозанна: координационные модели и языки. С. 1–15. CiteSeerX  10.1.1.210.1242. Дои:10.1007/978-3-540-68265-3_9. ISBN  978-3-540-68264-6.
  27. ^ а б c Руссо, Клаудио В. (23 октября 2008 г.). «Шаблоны соединения для Visual Basic». Уведомления ACM SIGPLAN. 43 (10): 53–72. Дои:10.1145/1449955.1449770.
  28. ^ а б c Зульцманн, Мартин; С. Л. Лам, Эдмунд. «Образцы параллельного соединения с защитой и размножением». Дания. Цитировать журнал требует | журнал = (помощь)
  29. ^ Hopf, J .; von Itzstein, G .; Стюарт и др. (2002). «Аппаратное объединение с Java: язык высокого уровня для разработки реконфигурируемого оборудования». Гонконг. Архивировано из оригинал 19 февраля 2013 г. Цитировать журнал требует | журнал = (помощь)
  30. ^ Плоциничак, Губерт; Айзенбах, Сьюзен (2009). "JErlang: Erlang с объединениями" (PDF). Конспект лекций по информатике. Лондон. 6116: 61–75. Bibcode:2010LNCS.6116 ... 61P. Дои:10.1007/978-3-642-13414-2_5. ISBN  978-3-642-13413-5. Архивировано из оригинал (PDF) на 2017-10-10. Получено 2012-12-10.
  31. ^ Лю, Игун (2007–2009). «Присоединиться - асинхронная библиотека координации сообщений и параллелизма». Проверено 2012. Проверить значения даты в: | accessdate = (помощь)
  32. ^ "Введение в полифонический C #". Проверено 2012. Проверить значения даты в: | accessdate = (помощь)
  33. ^ «Параллельный C #». Архивировано из оригинал в 2013-11-26. Проверено 2012. Проверить значения даты в: | accessdate = (помощь)
  34. ^ Ханус, Майкл (январь 2007 г.). Библиотека параллелизма Joins. 4354. ISBN  9783540696087. Проверено 2012. Проверить значения даты в: | accessdate = (помощь)
  35. ^ "Комега". Проверено 2012. Проверить значения даты в: | accessdate = (помощь)
  36. ^ Аарон, Турон; Руссо, Клаудио В. (27 октября 2011 г.). Масштабируемые шаблоны соединений (PDF). Портленд, Орегон, США. ISBN  9781450309400.
  37. ^ Фурне, Седрик; Ле Фессан, Фабрис; Маранге, Люк; Шмитт, Алан (2003). «JoCaml: язык для параллельного распределенного и мобильного программирования» (PDF). Расширенное функциональное программирование. Конспект лекций по информатике. Springer-Verlag. С. 129–158.
  38. ^ Хаммонд / Майклсон / Сан - Программирование реактивных систем в Юме
  39. ^ "Concurrent Basic". Архивировано из оригинал на 2015-04-25. Проверено 2012. Проверить значения даты в: | accessdate = (помощь)
  40. ^ Руссио, Клаудио (2007). «Библиотека параллелизма Joins». Практические аспекты декларативных языков. Конспект лекций по информатике. 4354. Кембридж: Практические аспекты декларативных языков. С. 260–274. CiteSeerX  10.1.1.187.8792. Дои:10.1007/978-3-540-69611-7_17. ISBN  978-3-540-69608-7.
  41. ^ «Библиотека параллелизма Joins». Проверено 2012. Проверить значения даты в: | accessdate = (помощь)
  42. ^ Галлер, Филипп; Одерский, Мартин (июнь 2007 г.). «Актеры, объединяющие темы и события». В Proc. КООРДИНАЦИЯ, LNCS. Цитировать журнал требует | журнал = (помощь)
  43. ^ МОНСЬЕР, Герт (2010), Координация на основе шаблонов в композициях услуг на основе процессов, Лёвен, Бельгия: Katholiek Universiteit Leuven, стр. 68
  44. ^ МОНСЬЕР, Герт (2010), Координация на основе шаблонов в композициях услуг на основе процессов, Лёвен, Бельгия: Katholiek Universiteit Leuven, стр. 70

внешняя ссылка