Модель актора и расчеты процесса - Actor model and process calculi

В Информатика, то Актерская модель и технологические расчеты два тесно связанных подхода к моделированию параллельные цифровые вычисления. Видеть Модель акторов и история расчетов процессов.

Между этими двумя подходами есть много общего, но есть и несколько различий (некоторые философские, некоторые технические):

• Здесь только один Актерская модель (хотя он имеет множество формальных систем для проектирования, анализа, проверки, моделирования, и Т. Д.); есть многочисленные технологические расчеты, разработанный для анализа различных видов параллельных систем на разных уровнях детализации (включая вычисления, которые включают время, стохастические переходы или конструкции, специфичные для таких областей приложения, как анализ безопасности).
• Модель Actor была вдохновлена ​​законами физика и зависит от них в своих основных аксиомах, т.е. физические законы (видеть Теория модели актера ); исчисления процесса изначально были вдохновлены алгебра (Милнер 1993 ).
• Процессы в процессных вычислениях анонимны и обмениваются сообщениями через именованные каналы (синхронный или асинхронный), или через окружающие (который также можно использовать для моделирования канальных коммуникаций (Карделли и Гордон 1998 )). Напротив, акторы в модели акторов обладают идентичностью и общаются, отправляя сообщения на почтовые адреса других акторов (этот стиль коммуникации также можно использовать для моделирования канальных коммуникаций - см. Ниже).

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

Как работают каналы

Косвенное общение с использованием каналов (например Gilles Kahn и David MacQueen [1977]) является важным вопросом для связи при параллельных и параллельных вычислениях, влияющих как на семантику, так и на производительность. Некоторые вычисления процессов отличаются от модели Актера тем, что они используют каналы, а не прямую коммуникацию.

Синхронные каналы

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

Простые синхронные каналы

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

• Каждый положить коммуникация имеет сообщение и адрес, на который отправляется подтверждение, когда сообщение получено получать общение с канала в ФИФО порядок.
• Каждый получать коммуникация имеет адрес, на который отправлено полученное сообщение.

Синхронные каналы в технологических расчетах

Однако простых синхронных каналов недостаточно для таких расчетов процессов, как Связь последовательных процессов (CSP) [Hoare 1978 и 1985] из-за использования осторожный выбор (после Дейкстры) команда (называемая альтернатива команда в CSP). В команде защищенного выбора несколько предложений (называемых охранниками) могут быть сделаны одновременно по нескольким каналам, чтобы положить и получать Сообщения; однако для каждого выполнения защищенной команды выбора можно выбрать не более одного из охранников. Поскольку можно выбрать только одного охранника, команда защищенного выбора в целом фактически требует своего рода протокол двухфазной фиксации или, возможно, даже протокол трехфазной фиксации если тайм-ауты разрешены в охранниках (как в Occam 3 [1992]).

Рассмотрим следующую программу, написанную на CSP [Hoare 1978]:

[X :: Z! Stop () || Y :: guard: логическое; охранник: = правда; * [охранник → Z! go (); Z? Охранник] || Z :: n: целое число; n: = 0; * [X? Stop () → Y! False; print! n; [] Y? Go () → n: = n + 1; Д! Правда]]

Согласно Клингеру [1981], эта программа иллюстрирует глобальный недетерминизм, поскольку недетерминизм возникает из-за неполной спецификации синхронизации сигналов между тремя процессами. Икс, Y, и Z. Повторяющаяся охраняемая команда в определении Z есть две альтернативы:

1. в остановка сообщение принято от Икс, в таком случае Y отправлено значение ложный и Распечатать отправлено значение п
2. а идти сообщение принято от Y, в таком случае п увеличивается и Y отправлено значение истинный.

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

В вышеприведенной программе есть синхронные каналы от Икс к Z, Y к Z, и Z к Y.

Аналогия с проблемой координации комитетов

Согласно Knabe [1992], Chandy and Misra [1988] описал это как аналог проблемы координации комитетов:

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

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

Простой распределенный протокол

В этом разделе представлен простой распределенный протокол для каналов в синхронных процессах. У протокола есть некоторые проблемы, которые рассматриваются в разделах ниже.

Поведение команды защищенного выбора следующее:

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

Поведение охранника следующее:

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

Поведение канала следующее:

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

Голодание при получении из нескольких каналов

Снова рассмотрим программу, написанную на CSP (обсуждается в Синхронные каналы в технологических расчетах над):

[X :: Z! Stop () || Y :: guard: логическое; охранник: = правда; * [охранник → Z! go (); Z? Охранник] || Z :: n: целое число; n: = 0; * [X? Stop () → Y! False; print! n; [] Y? Go () → n: = n + 1; Д! Правда]]

Как указано в Knabe [1992], проблема с вышеуказанным протоколом (Простой распределенный протокол ) заключается в том, что процесс Z может никогда не принять остановка Сообщение от Икс (явление, называемое голодание ) и, следовательно, вышеуказанная программа может никогда ничего не напечатать.

В отличие от этого, рассмотрим простую систему актеров, состоящую из актеров. Икс, Y, Z, и Распечатать куда

• актер Икс создается со следующим поведением:
  • Если сообщение "Начните" получено, затем отправьте Z сообщение "остановка"
• актер Y создается со следующим поведением:
  • Если сообщение "Начните" получено, затем отправьте Z сообщение "идти"
  • Если сообщение истинный получено, затем отправьте Z сообщение "идти"
  • Если сообщение ложный получен, то ничего не делать
• актер Z создается со следующим поведением, которое имеет счетчик п это изначально 0:
  • Если сообщение "Начните" получен, то ничего не делать.
  • Если сообщение "остановка" получено, затем отправьте Y сообщение ложный и отправить Распечатать сообщение счет п.
  • Если сообщение "идти" получено, затем отправьте Y сообщение истинный и обработать следующее полученное сообщение с помощью count п существование п + 1.

По законам семантики актеров, вышеупомянутая система актеров всегда останавливается, когда актеры Икс, Y, находятся Z каждому отправляется "Начните" сообщение, в результате которого отправляется Распечатать число, которое может быть неограниченно большим.

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

Livelock при получении с нескольких каналов

Рассмотрим следующую программу, написанную на CSP [Hoare 1978]:

[Bidder1 :: b: ставка; * [Bids1? B → process1! B; [] Bids2? B → process1! B;] || Bidder2 :: b: ставка; * [Bids1? B → process2! B; [] Bids2? B → process2! B;]]

Как указано в Knabe [1992], проблема с вышеуказанным протоколом (Простой распределенный протокол ) заключается в том, что процесс Участник торгов2 может никогда не принять ставку от Bid1 или же Bid2 (явление, называемое лайвлок ) и следовательно процесс2 может никогда ничего не послать. При каждой попытке принять сообщение, Участник торгов2 сорвано, потому что ставка, предложенная Ставки1 или же Ставки2 похищен Участник торгов1 потому что оказывается, что Участник торгов1 имеет гораздо более быстрый доступ, чем Участник торгов2 к Ставки1 и Ставки2. Как следствие, Участник торгов1 может принять ставку, обработать ее и принять еще одну ставку до Участник торгов2 может принять участие в торгах.

Эффективность

Как указано в Knabe [1992], проблема с вышеуказанным протоколом (Простой распределенный протокол ) - это большое количество сообщений, которые необходимо отправить, чтобы выполнить квитирование, чтобы отправить сообщение через синхронный канал. В самом деле, как показано в предыдущем разделе (Livelock ) количество коммуникаций может быть неограниченным.

Сводка проблем

В подразделах выше сформулированы следующие три проблемы, связанные с использованием синхронных каналов для расчетов процессов:

1. Голодание. Использование синхронных каналов может вызвать голод, когда процесс пытается получить сообщения из нескольких каналов в команде защищенного выбора.
2. Livelock. Использование синхронных каналов может привести к тому, что процесс будет захвачен живой блокировкой, когда он попытается получить сообщения из нескольких каналов в команде защищенного выбора.
3. Эффективность. Использование синхронных каналов может потребовать большого количества коммуникаций для получения сообщений из нескольких каналов в команде защищенного выбора.

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

Асинхронные каналы

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

Простые асинхронные каналы

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

• Каждый положить коммуникация имеет сообщение и адрес, на который немедленно отправляется подтверждение (не дожидаясь, пока сообщение будет получено получать коммуникация).
• Каждый получать коммуникация имеет адрес, на который отправляется полученное сообщение.

Асинхронные каналы в технологических расчетах

В языке программирования Join-Calculus (опубликованном в 1996 г.) реализованы локальные и распределенные параллельные вычисления. Он включает в себя асинхронные каналы, а также своего рода синхронный канал, который используется для вызовов процедур. Расчет Aπ Actor Аги (Ага и Тати 2004 ) основан на типизированной версии асинхронного π-исчисление.

Алгебры

Использование алгебраических методов было впервые использовано в расчетах процессов. Впоследствии несколько различных вычислений процессов, предназначенных для предоставления алгебраических рассуждений о системах Акторов, были разработаны в (Гаспари и Заваттаро 1997 ), (Гаспари и Заваттаро 1999 ), (Ага и Тати 2004 ).

Денотационная семантика

Уилл Клингер (опираясь на работы Ирен Грейф [1975], Гордон Плоткин [1976], Генри Бейкер [1978], Майкл Смит [1978] и Франсез, Hoare, Lehmann, and de Roever [1979]) опубликовали первые удовлетворительные математические денотационный теория Актерская модель с помощью теория предметной области в его диссертация в 1981 году. Его семантика противопоставляла неограниченный недетерминизм из Актерская модель с ограниченным недетерминизмом CSP [Hoare 1978] и Concurrent Processes [Milne and Milner 1979] (см. денотационная семантика ). Роско [2005] разработал денотационную семантику с неограниченным недетерминизмом для последующей версии Коммуникационных последовательных процессов Hoare [1985]. В последнее время Карл Хьюитт [2006b] разработал денотационную семантику для Актеров, основанную на временные диаграммы.

Уго Монтанари и Кэролин Талкотт [1998] внесли свой вклад в попытку примирить Актеров с процессными вычислениями.

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

• Карл Хьюитт, Питер Бишоп и Ричард Штайгер. Универсальный модульный актерский формализм для искусственного интеллекта IJCAI 1973.
• Робин Милнер. Процессы: математическая модель вычислительных агентов в Коллоквиуме по логике 1973.
• Ирен Грейф и Карл Хьюитт. Актерская семантика ПЛАНЕРА-73 Запись конференции ACM Symposium on Principles of Programming Languages. Январь 1975 г.
• Ирен Грейф. Семантика общения параллельных профессий Докторская диссертация MIT EECS. Август 1975 г.
• Гордон Плоткин. Конструкция энергетической области SIAM Journal on Computing сентябрь 1976 г.
• Карл Хьюитт и Генри Бейкер Актеры и непрерывные функционалы Материалы рабочей конференции ИФИП по формальному описанию концепций программирования. 1–5 августа 1977 г.
• Жиль Кан и Дэвид Маккуин. Сопрограммы и сети параллельных процессов ИФИП. 1977 г.
• Аки Ёнэдзава Методы спецификации и проверки параллельных программ на основе семантики передачи сообщений Докторская диссертация MIT EECS. Декабрь 1977 г.
• Майкл Смит. Силовые домены Журнал компьютерных и системных наук. 1978 г.
• Джордж Милн и Робин Милнер. Параллельные процессы и их синтаксис JACM. Апрель 1979 г.
• CAR Hoare. Связь последовательных процессов CACM. Август 1978 г.
• Ниссим Франсез, МАШИНА. Hoare, Даниэль Леманн и Виллем де Ровер. Семантика недетермизма, параллелизма и коммуникации Журнал компьютерных и системных наук. Декабрь 1979 г.
• Мэтью Хеннесси и Робин Милнер. О наблюдении недетерминизма и параллелизма LNCS 85. 1980.
• Уилл Клингер. Основы актерской семантики Докторская диссертация по математике Массачусетского технологического института. Июнь 1981 г.
• Мэтью Хеннесси. Термин модель для синхронных процессов Кафедра компьютерных наук Эдинбургского университета. CSR-77-81. 1981 г.
• J.A. Бергстра и Дж. Клоп. Алгебра процессов для синхронной связи Информация и контроль. 1984 г.
• Лука Карделли. Модель реализации рандеву-общения Семинар по параллелизму. Конспект лекций по информатике 197. Springer-Verlag. 1985 г.
• Роберт ван Глаббек. Ограниченный недетерминизм и принцип индукции аппроксимации в алгебре процессов Симпозиум по теоретическим аспектам компьютерных наук по STACS 1987.
• К. Мани Чанди и Джаядев Мишра. Разработка параллельных программ: основа Аддисон-Уэсли 1988.
• Робин Милнер, Иоахим Парроу и Дэвид Уокер. Расчет мобильных процессов Департамент компьютерных наук Эдинбург. Отчеты ECS-LFCS-89-85 и ECS-LFCS-89-86. Июнь 1989 г. Пересмотрено в сентябре 1990 г. и в октябре 1990 г. соответственно.
• Робин Милнер. Полиадическое исчисление пи: Учебное пособие Эдинбургский университет. Отчет LFCS ECS-LFCS-91-180. 1991 г.
• Кохей Хонда и Марио Токоро. Объектное исчисление для асинхронной связи ЕКООП 91.
• Хосе Месегер. Логика условного переписывания как единая модель параллелизма в Избранных статьях Второго семинара по параллелизму и композиционности. 1992 г.
• Фредерик Кнабе. Распределенный протокол для связи на основе каналов с выбором ПАРЛЬ 1992.
• Джефф Барретт. Справочное руководство Occam 3 ИНМОС. 1992 г.
• Бенджамин Пирс, Дидье Реми и Дэвид Тернер. Типизированный язык программирования высшего порядка на основе пи-исчисления Практикум по теории типов и ее применению в компьютерных системах. Киотский университет. Июль 1993 г.
• Милнер, Робин (Январь 1993 г.), «Элементы взаимодействия: лекция о премии Тьюринга», Коммуникации ACM, CACM, 36: 78–89, Дои:10.1145/151233.151240.
• Р. Амадио и С. Прасад. Локации и неудачи Конференция "Основы программных технологий и теоретической информатики". 1994 г.
• Седрик Фурне и Жорж Гонтье. Рефлексивная химическая абстрактная машина и объединенное исчисление ПОПЛ 1996.
• Седрик Фурне, Жорж Гонтье, Жан-Жак Леви, Люк Маранге и Дидье Реми. Подсчет мобильных агентов КОНКУР 1996.
• Тацуро Секигучи и Акинори Ёнэдзава. Исчисление с мобильностью кода FMOODS 1997.
• Гаспари, Мауро; Заваттаро, Джанлуиджи (май 1997 г.), Алгебра актеров (Технический отчет), Болонский университет
• Лука Карделли и Эндрю Гордон (1998), Морис Нива (редактор), "Mobile Ambients", Основы науки о программном обеспечении и вычислительных структур, Конспект лекций по информатике, Springer, 1378
• Уго Монтанари и Кэролайн Талкотт. Могут ли актеры и пи-агенты жить вместе? Электронные заметки по теоретической информатике. 1998 г.
• Робин Милнер. Коммуникационные и мобильные системы: Пи-исчисление Издательство Кембриджского университета. 1999 г.
• М. Гаспари и Г. Заваттаро (1999), «Алгебра актеров», Формальные методы для открытых объектно-ориентированных систем: 3–18, Дои:10.1007/978-0-387-35562-7_2, ISBN  978-1-4757-5266-3
• Давиде Санджорджи и Дэвид Уокер. Пи-исчисление: теория мобильных процессов Издательство Кембриджского университета. 2001 г.
• П. Тати, Р. Зиаи и Г. Ага. Теория майского тестирования для асинхронных вычислений с локальностью и без соответствия имен Алгебраическая методология и программные технологии. Springer Verlag. Сентябрь 2002 г. LNCS 2422.
• Гул Ага и Прасанна Тати (2004), «Алгебраическая теория актеров и ее приложение к простому объектно-ориентированному языку» (PDF), OO в FM (Dahl Festschrift) LNCS, Springer-Verlag, 2635, заархивировано из оригинал (PDF) на 2004-04-20, получено 2005-12-15
• J.C.M. Baeten, T. Basten и M.A. Reniers. Алгебра коммуникационных процессов Издательство Кембриджского университета. 2005 г.
• Хэ Цзифэн и C.A.R. Хоар. Связывание теорий параллелизма Международный институт программных технологий Университета Организации Объединенных Наций Отчет № 328 УООН-МИПО, июль 2005 г.
• Лука Ачето и Эндрю Д. Гордон (редакторы). Вычисления алгебраических процессов: первые двадцать пять лет и далее Алгебра процессов. Бертиноро, Форли, Италия, 1–5 августа 2005 г.
• Роско, А.В. (2005), Теория и практика параллелизма, Prentice Hall, ISBN  978-0-13-674409-2
• Карл Хьюитт (2006b) Что такое обязательство? Физические, организационные и социальные МОНЕТА @ AAMAS. 2006 г.