Модель актора и расчеты процесса

Эта статья номинирована на проверку на нейтральность . Обсуждение этой номинации можно найти на странице обсуждения . ( Апрель 2017 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Эта статья была успешно импортирована в Викиучебники под названием Модель акторов и расчет процессов . Если эту страницу можно переписать в энциклопедическую статью, сделайте это и удалите это сообщение и / или добавьте ссылку на Викиучебник с помощью {{ wikibooks }}.

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

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

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

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

Как работают каналы [ править ]

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

Синхронные каналы [ править ]

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

Простые синхронные каналы [ править ]

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

• Каждое putсообщение имеет сообщение и адрес, на который отправляется подтверждение, когда сообщение получено getсообщением из канала в порядке FIFO .
• У каждого get сообщения есть адрес, на который отправляется полученное сообщение.

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

Однако простых синхронных каналов недостаточно для вычислений процессов, таких как коммуникационные последовательные процессы (CSP) [Hoare 1978 и 1985], из-за использования команды защищенного выбора (после Дейкстры) (называемой альтернативной командой в CSP). В команде защищенного выбора несколько предложений (называемых охранниками) могут быть сделаны одновременно по нескольким каналам putи getсообщениям; однако для каждого выполнения защищенной команды выбора можно выбрать не более одного из охранников. Поскольку можно выбрать только одну защиту, команда защищенного выбора в целом фактически требует своего рода протокола двухфазной фиксации или, возможно, даже протокола трехфазной фиксации, если тайм-ауты разрешены в охранниках (как в 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; Д! Правда]]

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

1. stopсообщение принимается от X, в этом случае Yпередается значение FALSE и printпосылается значениеn
2. goсообщение принимается от Y, в этом случае nувеличивается , и Yпосылается значение верно .

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

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

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

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

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

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

Простой распределенный протокол [ править ]

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

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

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

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

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

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

• Когда prepare to putсообщение получено, ответьте, что оно подготовлено, если есть prepare to getожидающее сообщение, если terminateсообщение не было получено, и в этом случае выбросить исключение, которое он не может prepare to put.
• Когда prepare to getсообщение получено, ответьте, что оно подготовлено, если есть prepare to putожидающее сообщение, если terminateсообщение не было получено, и в этом случае выбросить исключение, которое он не может prepare to get.
  • Когда prepare to commit to putсообщение получено, ответьте, что оно подготовлено, если есть prepare to commit to getожидающее сообщение, если terminateсообщение не было получено, и в этом случае выбросить исключение, которое он не может prepare to commit to put.
  • Когда prepare to commit to getсообщение получено, ответьте, что оно подготовлено, если есть prepare to commit to putожидающее сообщение, если terminateсообщение не было получено, и в этом случае выбросить исключение, которое он не может prepare to commit to get.
    • Когда commit putсообщение получено, то в зависимости от того, что из следующего получено:
      • Когда commit getсообщение было получено, то , если не сделано выполнить putи getи очистить препараты.
      • Когда abort getсообщение получено, отмените приготовления.
    • Когда commit getсообщение получено, то в зависимости от того, что из следующего получено:
      • Когда commit putсообщение было получено, то , если не сделано выполнить getи putи очистить препараты.
      • Когда abort putсообщение получено, отмените приготовления.
    • Когда abort putсообщение получено, отмените приготовления.
    • Когда abort getсообщение получено, отмените приготовления.

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

Снова рассмотрим программу, написанную на 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может никогда не принять stopсообщение от X(явление, называемое голоданием ), и, следовательно, указанная выше программа может никогда ничего не распечатать.

В отличие от этого, рассмотрим простую систему Актеров, состоящую из Актеров X , Y , Z , и напечатайте, где

• Актер X создается со следующим поведением:
  • Если сообщение "start"получено, отправьте Z сообщение "stop"
• Актер Y создается со следующим поведением:
  • Если сообщение "start"получено, отправьте Z сообщение "go"
  • Если получено сообщение true , отправьте Z сообщение "go"
  • Если получено сообщение false , ничего не делать
• Актер Z создается со следующим поведением, значение счетчика nкоторого изначально равно 0 :
  • Если сообщение "start"получено, ничего не делать.
  • Если сообщение "stop"получено, то отправьте Y сообщение false и отправьте распечатайте сообщение count n.
  • Если сообщение "go"получено, а затем отправить Y сообщение верно и обработать следующее сообщение , полученное с графом nбытии n+1.

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

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

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], проблема вышеупомянутого протокола ( простого распределенного протокола ) заключается в том, что процесс Bidder2может никогда не принять заявку от Bid1или Bid2(явление, называемое живой блокировкой ) и, следовательно, process2может никогда ничего не послать. При каждой попытке принять сообщение Bidder2блокируется, потому что предложение, которое было предложено Bids1или Bids2отобрано им, Bidder1потому что оказывается, что он Bidder1имеет гораздо более быстрый доступ, чем Bidder2к Bids1и Bids2. Следовательно, он Bidder1может принять ставку, обработать ее и принять другую ставку, прежде чем Bidder2совершить принятие ставки.

Эффективность [ править ]

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

Сводка проблем [ править ]

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

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

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

Асинхронные каналы [ править ]

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

Простые асинхронные каналы [ править ]

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

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

Асинхронные каналы в технологических вычислениях [ править ]

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

Алгебры [ править ]

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

Денотационная семантика [ править ]

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

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

Ссылки [ править ]

• Карл Хьюитт, Питер Бишоп и Ричард Штайгер. Универсальный модульный актерский формализм для искусственного интеллекта IJCAI 1973.
• Робин Милнер. Процессы: математическая модель вычислительных агентов в логическом коллоквиуме 1973.
• Ирен Грейф и Карл Хьюитт. Актерская семантика конференции PLANNER-73 Запись симпозиума ACM по принципам языков программирования. Январь 1975 г.
• Ирен Грейф. Семантика параллельного общения профессоров MIT EECS Докторская диссертация. Август 1975 г.
• Гордон Плоткин. Powerdomain строительство SIAM Журнал по Компьютерной сентября 1976 года.
• Карл Хьюитт и Генри Бейкер Актеры и непрерывные функционалы Труды Рабочей конференции IFIP по формальному описанию концепций программирования. 1–5 августа 1977 г.
• Жиль Кан и Дэвид Маккуин. Сопрограммы и сети параллельных процессов ИФИП. 1977 г.
• Аки Ёнэдзава Методы спецификации и проверки параллельных программ на основе семантики передачи сообщений. Докторская диссертация MIT EECS. Декабрь 1977 г.
• Майкл Смит. Power domains Журнал компьютерных и системных наук. 1978 г.
• Джордж Милн и Робин Милнер . Параллельные процессы и их синтаксис JACM. Апрель 1979 г.
• АВТОМОБИЛЬ Хоар . Связь последовательных процессов CACM. Август 1978 г.
• Ниссим Франсез, К.А. Хор , Даниэль Леманн и Виллем де Ровер. Семантика недетермизма, параллелизма и коммуникации. Журнал компьютерных и системных наук. Декабрь 1979 г.
• Мэтью Хеннесси и Робин Милнер. О наблюдении недетерминизма и параллелизма LNCS 85. 1980.
• Уилл Клингер. Основы актерской семантики Докторская диссертация по математике Массачусетского технологического института. Июнь 1981 г.
• Мэтью Хеннесси. Терминная модель для синхронных процессов. Факультет компьютерных наук Эдинбургского университета. CSR-77-81. 1981 г.
• JA Bergstra и JW Klop. Алгебра процессов для синхронной передачи информации и управления. 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 г.
• Кохей Хонда и Марио Токоро. Объектное исчисление для асинхронной связи ECOOP 91.
• Хосе Месегер. Логика условного переписывания как унифицированная модель параллелизма в Избранных статьях Второго семинара по параллелизму и композиционности. 1992 г.
• Фредерик Кнабе. Распределенный протокол для связи на основе каналов с Choice PARLE 1992.
• Джефф Барретт. Справочное руководство Occam 3 INMOS. 1992 г.
• Бенджамин Пирс, Дидье Реми и Дэвид Тернер. Типизированный язык программирования высшего порядка, основанный на семинаре по исчислению пи по теории типов и ее применению в компьютерных системах. Киотский университет. Июль 1993 г.
• Милнер, Робин (январь 1993), «Элементы взаимодействия: Тьюринг лекции», коммуникации АСМА , ЦАОР, 36 : 78-89, DOI : 10,1145 / 151233,151240 CS1 maint: обескураженный параметр ( ссылка ).
• Р. Амадио и С. Прасад. Места и неудачи Конференция "Основы программных технологий и теоретической информатики". 1994 г.
• Седрик Фурне и Жорж Гонтье. Рефлексивная химическая абстрактная машина и объединенное исчисление POPL 1996.
• Седрик Фурне, Жорж Гонтье, Жан-Жак Леви, Люк Маранге и Дидье Реми. Расчет мобильных агентов CONCUR 1996.
• Тацуро Сэкигути и Акинори Ёнэдзава . Исчисление с кодом мобильности FMOODS 1997.
• Гаспари, Мауро; Заваттаро, Джанлуиджи (май 1997 г.), Алгебра актеров (технический отчет), Болонский университет
• Лука Карделли и Эндрю Гордон (1998), Морис Нива (редактор), «Мобильные окружающие среды», Основы науки о программном обеспечении и вычислительных структур , Лекционные заметки по компьютерным наукам, Springer, 1378
• Уго Монтанари и Кэролайн Талкотт. Могут ли актеры и пи-агенты жить вместе? Электронные заметки по теоретической информатике. 1998 г.
• Робин Милнер. Коммуникационные и мобильные системы: Pi-Calculus Cambridge University Press. 1999 г.
• М. Гаспари и Г. Заваттаро (1999), «Алгебра акторов», формальные методы для открытых объектно-ориентированных систем : 3–18, DOI : 10.1007 / 978-0-387-35562-7_2 , ISBN 978-1-4757-5266-3
• Давиде Санджорджи и Дэвид Уокер. Пи-исчисление: теория мобильных процессов Cambridge University Press. 2001 г.
• П. Тати, Р. Зиаи и Г. Ага. Теория майского тестирования для асинхронных вычислений с локальностью и без названия, совпадающей с алгебраической методологией и программными технологиями. Springer Verlag. Сентябрь 2002 г. LNCS 2422.
• Гул Ага и Прасанна Тати (2004), «Алгебраическая теория актеров и ее приложение к простому объектно-ориентированному языку» (PDF) , OO to FM (Dahl Festschrift) LNCS , Springer-Verlag, 2635 , заархивировано из оригинала ( PDF) от 20 апреля 2004 г. , дата обращения 15 декабря 2005 г.
• JCM Baeten, T. Basten и MA Reniers. Алгебра коммуникативных процессов Cambridge University Press. 2005 г.
• Хэ Цзифэн и ЦАР Хоар. Связывание теорий параллелизма Международный институт программных технологий Университета Организации Объединенных Наций Отчет UNU-IIST № 328. Июль 2005 г.
• Лука Ачето и Эндрю Д. Гордон (редакторы). Алгебраические вычисления процесса: первые двадцать пять лет и за его пределами. Алгебра процессов. Бертиноро, Форли, Италия, 1–5 августа 2005 г.
• Роско, AW (2005), Теория и практика параллелизма , Prentice Hall , ISBN 978-0-13-674409-2 CS1 maint: не рекомендуется параметр ( ссылка ) CS1 maint: ref дублирует значение по умолчанию ( ссылка )
• Карл Хьюитт (2006b) Что такое приверженность? Физическая, организационная и социальная сфера COIN @ AAMAS. 2006 г.