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

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

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

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

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

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

Косвенная коммуникация с использованием каналов ( например, Жиль Кан и Дэвид МакКуин [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: boolean; guard := true;
     *[guard  →  Z!go(); Z?guard] ||
 Z :: n: integer; n:= 0;
       *[X?stop()  →  Y!false; print!n;
         [] Y?go()  →  n := n+1; Y!true]
]

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

тот stop сообщение принято от X, в этом случае Y отправляется значение false и print отправляется значение n
а go сообщение принято от Y, в этом случае n увеличивается и Y отправляется значение true .

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

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

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

Согласно Кнабе [1992], Чанди и Мисра [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: boolean; guard := true;
     *[guard  →  Z!go(); Z?guard] ||
 Z :: n: integer; n:= 0;
       *[X?stop()  →  Y!false; print!n;
         [] Y?go()  →  n := n+1; Y!true]
]

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

Напротив, рассмотрим простую систему Актеров, состоящую из Актеров X , Y , Z и print , где

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

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

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

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

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

[Bidder1 :: b: bid;
       *[Bids1?b  →  process1!b;
         [] Bids2?b  →  process1!b;] ||
 Bidder2 :: b: bid;
       *[Bids1?b  →  process2!b;
         [] Bids2?b  →  process2!b;] 
]

Как указано в Кнабе [1992], проблема с вышеуказанным протоколом ( простым распределенным протоколом ) заключается в том, что процесс Bidder2 может никогда не принять предложение от Bid1 или Bid2 (феномен, называемый livelock ) и, следовательно, process2 может никогда ничего не отправить. При каждой попытке принять сообщение Bidder2 отменяется, поскольку предложение, предложенное Bids1 или Bids2 похищен Bidder1 потому что оказывается, что Bidder1 имеет гораздо более быстрый доступ, чем Bidder2 к Bids1 и Bids2. Следовательно, Bidder1 может принять предложение, обработать его и принять еще одно предложение, прежде чем Bidder2 может обязаться принять предложение.

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

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

Краткое изложение проблем

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

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

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

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

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

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

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

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

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

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

Алгебры

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

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

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

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

Ссылки

Карл Хьюитт, Питер Бишоп и Ричард Стайгер. Универсальный модульный формализм актеров для искусственного интеллекта IJCAI 1973.
Робин Милнер. Процессы: математическая модель вычислительных агентов на логическом коллоквиуме 1973.
Ирен Грейф и Карл Хьюитт. Акторная семантика PLANNER-73 Протокол конференции симпозиума ACM по принципам языков программирования. Январь 1975 года.
Ирен Грейф. Семантика взаимодействия параллельных процессов Докторская диссертация MIT EECS. Август 1975 года.
Гордон Плоткин. Конструкция энергетической области . SIAM Journal on Computing, сентябрь 1976 г.
Карл Хьюитт и Генри Бейкер Актеры и непрерывные функционалы. Материалы рабочей конференции ИФИП по формальному описанию концепций программирования. 1–5 августа 1977 г.
Жиль Кан и Дэвид Маккуин. Сопрограммы и сети параллельных процессов ИФИП. 1977 год
Аки Йонезава Методы спецификации и проверки параллельных программ на основе семантики передачи сообщений Докторская диссертация MIT EECS. Декабрь 1977 года.
Майкл Смит. Силовые домены Журнал компьютерных и системных наук. 1978.
Джордж Милн и Робин Милнер . Параллельные процессы и их синтаксис JACM. Апрель 1979 года.
АВТОМОБИЛЬ Хоар . Коммуникация последовательных процессов CACM. Август 1978 года.
Ниссим Франсез, КАР Хоар , Дэниел Леманн и Виллем де Ровер. Семантика недетерминизма, параллелизма и коммуникации . Журнал компьютерных и системных наук. Декабрь 1979 года.
Мэтью Хеннесси и Робин Милнер. О наблюдении недетерминизма и параллелизма LNCS 85. 1980.
Уилл Клингер. Основы акторной семантики Докторская диссертация по математике Массачусетского технологического института. Июнь 1981 года.
Мэтью Хеннесси. Временная модель для синхронных процессов. Факультет компьютерных наук Эдинбургского университета. ЦСР-77-81. 1981.
Дж. А. Бергстра и Дж. В. Клоп. Алгебра процессов для синхронной связи . Информация и управление. 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.
Фредерик Кнабе. Распределенный протокол для канальной связи с возможностью выбора PARLE 1992.
Джефф Барретт. Справочное руководство по Occam 3 INMOS. 1992.
Бенджамин Пирс, Дидье Реми и Дэвид Тернер. Типизированный язык программирования высшего порядка, основанный на семинаре по пи-исчислению по теории типов и ее применению в компьютерных системах. Киотский университет. Июль 1993 года.
Милнер, Робин (январь 1993 г.), «Элементы взаимодействия: лекция о премии Тьюринга», Communications of the ACM , 36 , CACM: 78–89, doi : 10.1145/151233.151240 .
Р. Амадио и С. Прасад. Места и неудачи. Конференция «Основы программных технологий и теоретической информатики». 1994.
Седрик Фурне и Жорж Гонтье. Рефлексивная химическая абстрактная машина и исчисление соединений POPL 1996.
Седрик Фурне, Жорж Гонтье, Жан-Жак Леви, Люк Маранже и Дидье Реми. Расчет мобильных агентов CONCUR 1996.
Тацуро Секигути и Акинори Ёнезава . Расчет с мобильностью кода FMOODS 1997.
Гаспари, Мауро; Заваттаро, Джанлуиджи (май 1997 г.), Алгебра актеров (технический отчет), Болонский университет
Лука Карделли и Эндрю Гордон (1998), Морис Ниват (редактор), «Мобильные среды», Основы науки о программном обеспечении и вычислительных структур , Конспекты лекций по информатике, 1378 , Springer
Уго Монтанари и Кэролайн Талкотт. Могут ли актеры и пи-агенты жить вместе? Электронные заметки по теоретической информатике. 1998.
Робин Милнер. Коммуникационные и мобильные системы: Pi-Calculus Издательство Кембриджского университета. 1999.
М. Гаспари и Г. Заваттаро (1999), «Алгебра актеров», Формальные методы для систем на основе открытых объектов : 3–18, doi : 10.1007/978-0-387-35562-7_2 , ISBN 978-1-4757-5266-3
Давиде Санджорджи и Дэвид Уокер. Пи-исчисление: теория мобильных процессов Издательство Кембриджского университета. 2001.
П. Тати, Р. Зиаи и Г. Ага. Теория возможного тестирования асинхронных исчислений с локальностью и отсутствием имени, соответствующего алгебраической методологии и технологии программного обеспечения. Спрингер Верлаг. Сентябрь 2002 г. LNCS 2422.
Гул Ага и Прасанна Тати (2004), «Алгебраическая теория действующих лиц и ее применение к простому объектно-ориентированному языку» (PDF) , OO to FM (Dahl Festschrift) LNCS , 2635 , Springer-Verlag, заархивировано из оригинала ( PDF) от 20 апреля 2004 г. , получено 15 декабря 2005 г.
Ж. К. М. Бэтен, Т. Бастен и М. А. Ренье. Алгебра коммуникационных процессов Издательство Кембриджского университета. 2005.
Хэ Цзифэн и КАР Хоар. Связывание теорий параллелизма, Международный институт программных технологий Университета Организации Объединенных Наций, Отчет UNU-IIST № 328. Июль 2005 г.
Лука Ачето и Эндрю Д. Гордон (редакторы). Исчисление алгебраических процессов: первые двадцать пять лет и далее Алгебра процессов. Бертиноро, Форли, Италия, 1–5 августа 2005 г.
Роско, AW (2005), Теория и практика параллелизма , Prentice Hall , ISBN 978-0-13-674409-2
Карл Хьюитт (2006b) Что такое приверженность? Физический, организационный и социальный COIN@AAMAS. 2006.