Модель а́кторов — математическая модель параллельных вычислений, строящаяся вокруг понятия «актора» (англ. actor — актёр, действующий субъект), считающегося универсальным примитивом параллельного исполнения. Актор в данной модели взаимодействует путём передачи сообщений с другими акторами, в ответ на получаемые сообщения может принимать локальные решения, создавать новые акторы, посылать свои сообщения, устанавливать, как следует реагировать на последующие сообщения.
Создана в качестве варианта исчисления процессов и как теоретическая база для ряда практических реализаций параллельных систем.
Основные идеи и база для модели заложены в 1973 году публикации Хьюитта, Бишопа и Штайгера[1]. На процесс формирования модели оказали влияние языки программирования Лисп, Симула и ранние версии Smalltalk, а также методы параметрической защиты и коммутации пакетов. Основной мотивацией создания модели стала задача построения распределённых вычислительных систем на базе сотен и тысяч независимых компьютеров, оснащённых собственной локальной памятью и коммуникационными интерфейсами[2]. С появлением многопроцессорных систем и многоядерных архитектур интерес к модели акторов возрос также вне контекста распределённых систем.
В 1975 году разработана операционная семантика[en] для модели акторов[3][4]. В 1977 году выработана система аксиоматических законов для моделей акторов[5]. В 1981 году создана денотационная семантика[en] модели (семантика переходов)[2][6], развитая и обобщённая в 1985 году[7]; в результате этих работ теория моделей акторов признана развитой и проработанной.
В 1990-е годы созданы формализмы, не полностью соответствующие модели акторов (не формализующие гарантированную доставку сообщений), но имеющие практический интерес, в частности, несколько различных алгебр акторов[8][9] и интерпретацию на базе линейной логики[en][10].
По аналогии с философией объектно-ориентированного программирования, где каждый примитив рассматривается как объект, модель акторов выделяет в качестве универсальной сущности понятие «актора». Актор является вычислительной сущностью, которая в ответ на полученное сообщение может одновременно:
Не предполагается существования определённой последовательности вышеописанных действий и все они могут выполняться параллельно.
Отделение отправителя от посланных сообщений стало фундаментальным достижением модели акторов: тем самым обеспечивается асинхронная связь и управление структурами в виде формы передачи сообщений[11].
Получатели сообщений идентифицируются по адресу, который иногда называют «почтовым адресом». Таким образом, актор может взаимодействовать только с теми акторами, адреса которых он имеет, может извлечь адреса из полученных сообщений или знать их заранее, если актор создан им самим.
Модель характеризуется внутренне присущим параллелизмом вычислений внутри одного актора и между акторами, динамическим созданием акторов, включением адресов акторов в сообщения, а также взаимодействием только через прямой асинхронный обмен сообщениями без каких-либо ограничений на порядок прибытия сообщений.
Модель акторов может использоваться в качестве основы для моделирования, понимания и аргументации по широкому спектру параллельных систем, например:
Возможно, первыми параллельными программами были обработчики прерываний. В процессе работы, как правило, компьютеру необходимо реагировать на внешние события, которые могут происходить в заранее неизвестный момент времени (асинхронно по отношению к выполняющейся в данный момент программе) — например, получать информацию извне (символы с клавиатуры, пакеты из сети и так далее). Наиболее эффективно обработка таких событий реализуется с помощью так называемых прерываний. Когда происходит событие, выполнение текущей программы «прерывается», и запускается обработчик прерывания, который выполняет действия, необходимые для реагирования на событие (например, получает поступающую информацию и сохраняет её в буфер, откуда она может быть впоследствии считана), после чего основная программа продолжает свою работу с того места, где она была прервана[источник не указан 1043 дня].
В начале 1960-х годов прерывания стали использовать для имитации одновременного выполнения нескольких программ на одном процессоре[13]. Наличие параллелизма с общей памятью привело к проблеме управления параллелизмом. Первоначально эта задача задумывалась как один из мьютексов на отдельном компьютере. Эдсгер Дейкстра разработал семафоры, а позднее, в период между 1971 и 1973 годами, Чарльз Хоар и Пер Хансен для решения проблемы мьютексов разработали мониторы[14][15][16]. Однако, ни одно из этих решений не создавало в языках программирования конструкций, которые бы инкапсулировали доступ к совместным ресурсам. Инкапсуляцию сделали позже Хьюитт и Аткинсон, построив параллельно-последовательный преобразователь ([Hewitt, Atkinson 1977, 1979] и [Atkinson 1980]).
Первые модели вычислений (например, машина Тьюринга, машина Поста, лямбда-исчисление и тому подобные) были основаны на математике и использовали понятие глобального состояния, чтобы определить «шаг вычисления» (позднее эти понятия обобщены в работах Маккарти и Дейкстры[17][18]). Каждый шаг вычисления шёл от одного глобального состояния вычислений до следующего. Глобальный подход к состоянию был продолжен в теории автоматов для конечных автоматов и машин со стеком, в том числе их недетерминированные версии. Такие недетерминированные автоматы имеют свойство ограниченного недетерминизма. То есть, если машина всегда стоит перед тем, как она переходит в исходное состояние, то имеется ограничение на число состояний, в которых она может находиться.
Дейкстра развил дальше подход с недетерминированными глобальными состояниями. Модель Дейкстры породила споры о неограниченном недетерминизме — свойстве параллельных вычислений, при котором величина задержки в обслуживании запроса может стать неограниченной в результате арбитражного соперничества за общие ресурсы, в то же время гарантируется, что запрос в конечном итоге будет обслужен. Хьюитт утверждал, что модель акторов должна обеспечить гарантии на предоставление услуги. Хотя в модели Дейкстры не может быть неограниченного количества времени между выполнением последовательных операций на компьютере, параллельно выполняемая программа, которая начала свою работу в строго определённом состоянии, может быть прервана лишь в ограниченном числе состояний[18]. Следовательно, модель Дейкстры не может обеспечить гарантии предоставления услуги. Дейкстра утверждал, что невозможно осуществить неограниченный недетерминизм.
Хьюитт утверждал иное: не существует ограничения на время, которое затрачивается на работу участка вычислений, называемого арбитром для урегулирования конфликтов. Арбитры имеют дело с разрешением таких ситуаций. Часы компьютера работают асинхронно с внешними входами: вводом с клавиатуры, доступом к диску, сетевым входом и так далее. Так что для получения сообщения, отправленного на компьютер, может пройти неограниченное время, и за это время компьютер может пройти через неограниченное количество состояний.
Неограниченный недетерминизм является характерной чертой модели акторов, в которой используется математическая модель Клингера, основанная на теории областей[en][2]. В модели акторов не существует глобального состояния.
Сообщения в модели акторов не обязательно буферизуются. В этом её резкое различие с предшествующими подходами к модели одновременных вычислений. Отсутствие буферизации вызвало большое недоразумение во время развития модели акторов, и до сих пор эта тема является предметом споров. Некоторые исследователи утверждают, что сообщения буферизуются в «эфире» или «окружающей среде». Кроме того, сообщения в модели акторов просто посылаются (например, пакеты в IP). Никаких требований на синхронное рукопожатие с получателем не существует.
Естественным развитием модели акторов была возможность передачи адресов в сообщениях. Под влиянием сетей с коммутацией пакетов Хьюитт предложил разработать новую модель одновременных вычислений, в которой связь не будет иметь вообще никаких обязательных полей, все они могут быть пустыми. Конечно, если отправитель сообщения желает, чтобы получатель имел доступ к адресам, которых он ещё не имеет, адрес должен быть отправлен в сообщении.
В процессе вычислений, возможно, потребуется отправить сообщение получателю, от которого позже нужно получить ответ. Способ сделать это состоит в том, чтобы отправить сообщение, в котором записан адрес другого актора, называемого возобновлением (иногда его также называют продолжением или стеком вызовов). Получатель может затем создать ответное сообщение, которое будет отправлено на возобновление.
Создание акторов плюс включение адресов участников в сообщения означает, что модель акторов имеет потенциально переменную топологию в своих отношениях друг с другом, походя на объекты в языке Симула, которые в своих отношениях друг с другом также имеют переменную топологию.
В отличие от предыдущего подхода, основанного на комбинировании последовательных процессов, модель акторов была разработана как одновременная модель по своей сути. Как написано в теории моделей акторов, последовательность в ней представляет собой особый случай, вытекающий из одновременных вычислений.
Хьюитт был против включения требований о том, что сообщения должны прибывать в том порядке, в котором они отправлены на модель актора. Если желательно упорядочить входящие сообщения, то это можно смоделировать с помощью очереди акторов, которая обеспечивает такую функциональность. Такие очереди акторов упорядочивали бы поступающие сообщения так, чтобы они были получены в порядке FIFO. В общем же случае, если актор X отправляет сообщение M1 актору Y, а затем тот же актор X отправляет другое сообщение M2 к Y, то не существует никаких требований о том, что M1 придёт к Y раньше M2.
В этом отношении модель акторов зеркально отражает систему коммутации пакетов, которая не гарантирует, что пакеты будут получены в порядке отправления. Отсутствие гарантий порядка доставки сообщений позволяет системе коммутации пакетов буферизовать пакеты, использовать несколько путей отправки пакетов, повторно пересылать повреждённые пакеты и использовать другие методы оптимизации.
Например, акторы могут использовать конвейер обработки сообщений. Это означает, что в процессе обработки сообщения M1 актор может варьировать поведение, которое будет использоваться для обработки следующего сообщения. В частности, это означает, что он может начать обработку ещё одного сообщения M2 до завершения обработки M1. На том основании, что актору предоставлено право использования конвейера обработки сообщений, ещё не означает, что он этот конвейер обязан использовать. Будет ли сообщение конвейеризовано или нет — относится к задачам технического компромисса. Как внешний наблюдатель может узнать, что обработка сообщения актора прошла через конвейер? На этот счёт не существует никакой двусмысленности в отношении применения актором возможности конвейеризации. Только если в конкретной реализации выполнение конвейерной оптимизации сделано неправильно, может произойти не ожидаемое поведение, а нечто другое.
Другой важной характеристикой модели акторов является локальность: при обработке сообщения актор может отправлять сообщения только по тем адресам, которые он получил из этого сообщения, по адресам, которые он уже имел до получения сообщения, и по адресам, которые он создал при обработке сообщения.
Локальность также означает, что не может одновременно произойти несколько изменений адресов. В этом отношении модель акторов отличается от некоторых других моделей параллелизма, например, от сетей Петри, в которых реализации одновременно могут быть удалены из нескольких позиций и размещены по другим адресам.
Идея композиции систем акторов в более крупные образования является важным аспектом модульности, которая была разработана в докторской диссертации Гуля Ага[7], позже развитой им же вместе с Ианом Мейсоном, Скоттом Смитом и Каролин Талкотт[4].
Основным новшеством модели акторов было введение понятия поведения, определённого как математическая функция, выражающая действия актора, когда он обрабатывает сообщения, включая определение нового поведения на обработку следующего поступившего сообщения. Поведение обеспечивает функционирование математической модели параллелизма.
Поведение также освобождает модель акторов от деталей реализации, как, например, в Smalltalk-72 это делает маркер интерпретатора потока. Однако, важно понимать, что эффективное внедрение систем, описываемых моделью акторов, требует расширенную оптимизацию.
Другие системы параллелизма (например, исчисление процессов) могут быть смоделированы в модели акторов с использованием двухфазного протокола фиксации[19].
В модели акторов существует теорема вычислительных представлений для замкнутых систем, в том смысле, что они не получают сообщений извне. В математической записи замкнутая система, обозначаемая как S, строится как наилучшее приближение для начального поведения, называемого ⊥S, с использованием аппроксимирующей функции поведения progressionS, построенной для S следующим образом (согласно публикации Хьюитта 2008 года):
Таким образом, S может быть математически охарактеризована в терминах всех его возможных поведений (в том числе с учётом неограниченного недетерминизма). Хотя DenoteS не является реализацией S, она может быть использована для доказательства следующего обобщения тезиса Чёрча — Тьюринга[20]: если примитив актора замкнутой системы акторов являются эффективным, то его возможные выходы рекурсивно перечислимы. Доказательство непосредственно вытекает из теоремы вычислительных представлений.
Развитие модели акторов имеет интересную связь с математической логикой. Одной из ключевых мотиваций для её развития была необходимость управления аспектами, которые возникли в процессе развития языка программирования Planner. После того как модель акторов была первоначально сформулирована, стало важно определить мощность модели в отношении тезиса Роберта Ковальского о том, что «вычисления могут быть сгруппированы по логическим выводам». Тезис Ковальского оказался ложным для одновременных вычислений в модели акторов. Этот результат всё ещё является спорным и противоречит некоторым предыдущим представлениям, поскольку тезис Ковальского верен для последовательных вычислений и даже для некоторых видов параллельных вычислений, например, для лямбда-исчислений.
Тем не менее были предприняты попытки расширения логического программирования для одновременных вычислений. Однако, Хьюитт и Ага в работе 1999 года утверждают, что результирующая система не является дедуктивной в следующем смысле: вычислительные шаги параллельных систем программирования логики не следуют дедуктивно из предыдущих шагов.
Миграцией в модели акторов называется способность актора изменить своё местоположение. Например, Аки Йонезава в своей диссертации моделировал почтовую службу, в которой акторы-клиенты могли войти, изменить местоположение во время работы и выйти. Актор, который мог мигрировать, моделировался как актор с определённым местом, изменяющимся при миграции актора. Однако достоверность этого моделирования является спорной и служит предметом исследований.
Безопасность акторов может быть обеспечена одним из следующих способов:
Тонким моментом в модели акторов является возможность синтеза адреса актора. В некоторых случаях система безопасности может запрещать синтез адресов. Поскольку адрес актора — это просто битовая строка, то, очевидно, его можно синтезировать, хотя, если битовая строка достаточно длинная, подобрать адрес актора довольно трудно или даже невозможно. SOAP в качестве адреса конечной точки использует URL, по которому актор расположен. Так как URL является строкой символов, то, очевидно, её можно синтезировать, хотя если применить шифрование, то подобрать строку практически невозможно.
Синтезирование адресов акторов обычно моделируется с помощью отображения. Идея состоит в использовании системы акторов для выполнения отображения на фактические адреса акторов. Например, структура памяти компьютера может быть смоделирована как система акторов, которая даёт отображение. В случае адресов SOAP это моделирование DNS и отображение URL.
Первая из опубликованных работ Робина Милнера о параллелизме[21] была примечательна тем, что не была основана на композиции последовательных процессов, отличалась от модели акторов, потому что она была основана на фиксированном количестве процессов фиксированного числа связей в топологии строк, используемых для синхронизации связи. Оригинальная модель взаимодействующих последовательных процессов (CSP), опубликованная Энтони Хоаром[22], отличается от модели акторов, потому что основана на параллельной композиции фиксированного числа последовательных процессов, связанных в фиксированную топологию и общающихся с помощью синхронной передачи сообщений на основе имён процессов. Более поздние версии CSP отказались от связи на основе имён процессов, приняв принцип анонимной связи по каналам. Этот подход используется также в работе Милнера об исчислении общающихся систем и пи-исчислении.
Этим обеим ранним моделям Милнера и Хоара свойствен ограниченный недетерминизм. Современные теоретические модели взаимодействующих систем[23] прямо предусматривают неограниченный недетерминизм.
Через сорок лет после публикации закона Мура продолжающееся возрастание производительности микросхем происходит благодаря методам локального и глобального массового параллелизма. Локальный параллелизм задействован в новых микросхемах для 64-разрядных многоядерных микропроцессоров, в мульти-чиповых модулях и высокопроизводительных системах связи. Глобальный параллелизм в настоящее время задействован в новом оборудовании для проводной и беспроводной широкополосной пакетной коммутации сообщений. Ёмкость хранения за счёт как локального, так и глобального параллелизма, растёт в геометрической прогрессии.
Модель нацелена на решение следующих задач построения вычислительных систем:
Многие идеи, введённые в модели акторов, в настоящее время находят также применение в многоагентных системах по этим же причинам[24]. Ключевым отличием является то, что агент системы (в большинстве определений) накладывает дополнительные ограничения на акторов, как правило, требуя, чтобы они использовали обязательства и цели.
Модель акторов применяется также в клиентах облачных вычислений[25].
Список примеров в этом разделе не основывается на авторитетных источниках, посвящённых непосредственно предмету статьи или её раздела. |
Среди ранних языков программирования с поддержкой акторов — Act 1, 2 и 3[26][27], Acttalk[28], Ani[29], Cantor[30], Rosette[31]
Более поздние языки, ориентированные на модель акторов: Actor-Based Concurrent Language (ABCL), ActorScript, AmbientTalk[32], Axum[33]. Среди языков программирования общего назначения, где используется понятие актора — E, Elixir[34], Erlang, Io, SALSA[35], Scala[36][37].
Разработаны библиотеки и табличные структуры с акторами для обеспечения актороподобного стиля программирования на языках, которые не имеют встроенных акторов.
Библиотеки и табличные структуры с акторами | |||
---|---|---|---|
Название | Дата последнего выпуска | Лицензия | Языки программирования |
ActiveJava | 2008 | ? | Java |
Actor | 2013-05-31 | MIT | Java |
Actor-CPP | 2012-03-10[38][нет в источнике] | GPL 2.0 | C++ |
Actor Framework | 2013-11-13 | Apache 2.0 | .NET |
ActorKit | 2011-09-13[39] | BSD | Objective-C |
Akka[en] | 2015-04-23 | Apache 2.0 | Java and Scala |
Akka.NET | 2016-01-18 | Apache 2.0 | .NET |
C++ Actor Framework (CAF) | 2015-11-25[40] | Boost Software License 1.0 and BSD 3-Clause | C++11 |
Celluloid | 2016-01-19[41] | MIT | Ruby |
Cloud Haskell | 2015-06-17[42] | BSD | Haskell |
CloudI | 2015-12-24[43] | BSD | C/C++, Elixir/Erlang/LFE, Java, Javascript, Perl, PHP, Python, Ruby |
Functional Java | 2016-02-15[44] | BSD | Java |
GPars | 2014-05-09[45] | Apache 2.0 | Groovy |
Jetlang | 2013-05-30[46] | New BSD | Java |
Korus | 2010-02-04 | GPL 3 | Java |
Kilim[47] | 2011-10-13[48] | MIT | Java |
LabVIEW Actor Framework | 2012-03-01[49] | ? | LabVIEW |
libprocess | 2013-06-19 | Apache 2.0 | C++ |
NAct | 2012-02-28 | LGPL 3.0 | .NET |
OOSMOS | 2016-02-17[50] | GPL 2.0 и коммерческая | C, C++ |
Orbit | 2016-02-16[51] | New BSD | Java |
Orleans | 2016-01-20[52] | MIT | .NET |
Panini | 2014-05-22 | MPL 1.1 | Собственный язык программирования |
Peernetic | 2007-06-29 | LGPL 3.0 | Java |
PostSharp | 2014-09-24 | Коммерческая / Freemium | .NET |
Pulsar | 2016-11-24[53] | New BSD | Python |
Pulsar | 2016-02-18[54] | LGPL/Eclipse | Clojure |
Pykka | 2015-07-20[55] | Apache 2.0 | Python |
Remact.Net | ? | MIT | .NET |
Retlang | 2011-05-18[56] | New BSD | .NET |
S4 | 2012-07-31[57] | Apache 2.0 | Java |
SObjectizer | 2016-02-11 | New BSD | C++11 |
Termite Scheme | 2009-05-21 | LGPL | Scheme |
Theron | 2014-01-18[58] | MIT[59] | C++ |
Thespian | 2016-02-11 | GoDaddy Public Release[60] | Python |
QP[en] | 2015-09-29[61] | GPL 2.0 и коммерческая | C and C++ |
Quasar | 2016-01-18[62] | LGPL/Eclipse | Java |
|coauthors=
(справка)Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .