Модель а́кторов — математическая модель параллельных вычислений, строящаяся вокруг понятия актора ( «актёр; действующий субъект»), считающегося универсальным примитивом параллельного исполнения. Актор в данной модели взаимодействует путём обмена сообщениями с другими акторами, и каждый в ответ на получаемые сообщения может принимать локальные решения, создавать новые акторы, посылать свои сообщения, устанавливать, как следует реагировать на последующие сообщения.
Создана как теоретическая база для ряда практических реализаций параллельных систем.
История Основные идеи и база для модели заложены в 1973 году в публикации Хьюитта, Бишопа и ШтайгераКарл Хьюитт, Питер Бишоп, Ричард Штайгер: Универсальный модульный формализм акторов для искусственного интеллекта. IJCAI, 1973. На процесс формирования модели оказали влияние языки программирования Лисп, Симула и ранние версии Smalltalk, а также методы параметрической защиты и коммутации пакетов. Основной мотивацией создания модели стала задача построения распределённых вычислительных систем на базе сотен и тысяч независимых компьютеров, оснащённых собственной локальной памятью и коммуникационными интерфейсамиУильям Клингер, Основы семантики акторов. MIT, докторская диссертация по математике, июнь 1981 . С появлением многопроцессорных систем и многоядерных архитектур интерес к модели акторов возрос также вне контекста распределённых систем.
В 1975 году разработана для модели акторов[Ирен Грейф, Семантика коммуникативных параллельных процессов. MIT, докторская диссертация, август 1975]Г. Ага, И. Мейсон, С. Смит, К. Талкотт. Основания для вычислений акторов. Journal of Functional Programming, январь, 1993. В 1977 году выработана система аксиоматических законов для моделей акторовГ. Бейкер, К. Хьюитт. Законы взаимодействующих параллельных процессов. IFIP, август 1977 года. В 1981 году создана модели (семантика переходов)Карл Хьюитт. Что такое обязательство? Физическое, организационное и социальное. , развитая и обобщённая в 1985 годуГуль Ага, Акторы: Модель параллельных вычислений в распределенных системах. MIT Press, докторская диссертация, 1986 ; в результате этих работ теория моделей акторов признана развитой и проработанной.
В 1990-е годы созданы формализмы, не полностью соответствующие модели акторов (не формализующие гарантированную доставку сообщений), но имеющие практический интерес, в частности, несколько различных алгебр акторовM. Gaspari, G. Zavattaro. An Algebra of Actors. Technical Report UBLCS-97-4. University of Bologna, 1997 и интерпретацию на базе линейной логики.
Фундаментальные концепции По аналогии с философией объектно-ориентированного программирования, где каждый примитив рассматривается как объект, модель акторов выделяет в качестве универсальной сущности понятие «актора». Актор является вычислительной сущностью, которая в ответ на полученное сообщение может одновременно: отправить конечное число сообщений другим акторам; создать конечное число новых акторов; выбрать поведение, которое будет использоваться при обработке следующего полученного сообщения.
Не предполагается существования определённой последовательности вышеописанных действий и все они могут выполняться параллельно.
Отделение отправителя от посланных сообщений стало фундаментальным достижением модели акторов: тем самым обеспечивается асинхронная связь и управление структурами в виде формы передачи сообщенийCarl Hewitt. Viewing Control Structures as Patterns of Passing Messages Journal of Artificial Intelligence. June 1977..
Получатели сообщений идентифицируются по адресу, который иногда называют «почтовым адресом». Таким образом, актор может взаимодействовать только с теми акторами, адреса которых он имеет, может извлечь адреса из полученных сообщений или знать их заранее, если актор создал их сам.
Модель характеризуется внутренне присущим параллелизмом вычислений внутри одного актора и между акторами, динамическим созданием акторов, включением адресов акторов в сообщения, а также взаимодействием только через прямой асинхронный обмен сообщениями без каких-либо ограничений на порядок прибытия сообщений.
Применения Модель акторов может использоваться в качестве основы для моделирования, понимания и аргументации по широкому спектру параллельных систем, например: электронная почта (e-mail) может быть смоделирована как система акторов: клиенты моделируются как акторы, а адреса электронной почты — как адреса акторов; веб-сервисы с конечными точками SOAP могут быть смоделированы как адреса акторов; объекты с блокировками (например, в Java и C#) могут быть смоделированы как сериализаторы, при условии, что их реализация такова, что сообщения могут приходить постоянно (возможно, они хранятся во внутренней очереди). Сериализатор является важным видом актора, характеризующийся тем, что он постоянно доступен для прихода новых сообщений. Каждое сообщение, отправленное в сериализатор, гарантированно будет получено; язык программирования SmallTalk построен исключительно на взаимодействии объектов посредством сообщений друг другу. Код каждого объекта при этом исполняется изолированно от соседей в параллельной среде. нотация тестирования и управления тестами (как TTCN-2, так и TTCN-3) довольно близко соответствует модели акторов — в TTCN актором является тест компонента: либо параллельный тест компонента (PTC), либо главный тест компонента (MTC); тесты компонентов могут отправлять и получать сообщения на/от удалённых партнеров (равноправные тесты компонентов или тест интерфейса системы), причём последний идентифицируется по его адресу; каждый тест компонента имеет дерево поведения, связанное с ним; тесты компонентов запускаются параллельно, и могут быть динамически созданы родительскими тестами компонентов; встроенные языковые конструкции позволяют определить действия, которые необходимо выполнить, когда сообщение получено из внутренней очереди сообщений, а также отправить сообщения другим равноправным субъектом или создать новые тесты компонентов.
Семантика передачи сообщений
Неограниченные недетерминированные разногласия Возможно, первыми параллельными программами были обработчики прерываний. В процессе работы, как правило, компьютеру необходимо реагировать на внешние события, которые могут происходить в заранее не известный момент времени (асинхронно по отношению к выполняющейся в данный момент программе) — например, получать информацию извне (символы с клавиатуры, пакеты из сети и так далее). Наиболее эффективно обработка таких событий реализуется с помощью так называемых прерываний. Когда происходит событие, выполнение текущей программы «прерывается», и запускается обработчик прерывания, который выполняет действия, необходимые для реагирования на событие (например, получает поступающую информацию и сохраняет её в буфер, откуда она может быть впоследствии считана), после чего основная программа продолжает свою работу с того места, где она была прервана.
В начале 1960-х годов прерывания стали использовать для имитации одновременного выполнения нескольких программ на одном процессореП. Хансен. Истоки параллельного программирования: от семафоров к удалённому вызову процедур. Springer, 2002. Наличие параллелизма с общей памятью привело к проблеме управления параллелизмом. Первоначально эта задача задумывалась как один из мьютексов на отдельном компьютере. Эдсгер Дейкстра разработал семафоры, а позднее, в период между 1971 и 1973 годами, Чарльз Хоар и Пер Хансен для решения проблемы мьютексов разработали мониторыPer Hansen, Monitors and Concurrent Pascal: A Personal History, Comm. ACM 1996, pp 121—172Hansen, P., Operating System Principles, Prentice-Hall, July 1973.C.A.R. Hoare, Monitors: An Operating System Structuring Concept, Comm. ACM Vol. 17, No. 10. October 1974, pp. 549—557. Однако, ни одно из этих решений не создавало в языках программирования конструкций, которые бы инкапсулировали доступ к совместным ресурсам. Инкапсуляцию сделали позже Хьюитт и Аткинсон, используя конструкции сериализатора ([Hewitt, Atkinson 1977, 1979] и [Atkinson 1980]).
Первые модели вычислений (например, машина Тьюринга, машина Поста, лямбда-исчисление и тому подобные) были основаны на математике и использовали понятие глобального состояния, чтобы определить «шаг вычисления» (позднее эти понятия обобщены в работах Маккарти и Дейкстры[McCarthy and Hayes 1969][Dijkstra 1976]). Каждый шаг вычисления шёл от одного глобального состояния вычислений до следующего. Глобальный подход к состоянию был продолжен в теории автоматов для конечных автоматов и машин со стеком, в том числе их недетерминированные версии. Такие недетерминированные автоматы имеют свойство ограниченного недетерминизма. То есть, если машина всегда стоит перед тем, как она переходит в исходное состояние, то имеется ограничение на число состояний, в которых она может находиться.
Дейкстра развил дальше подход с недетерминированными глобальными состояниями. Модель Дейкстры породила споры о неограниченном недетерминизме — свойстве параллельных вычислений, при котором величина задержки в обслуживании запроса может стать неограниченной в результате арбитражного соперничества за общие ресурсы, в то же время гарантируется, что запрос в конечном итоге будет обслужен. Хьюитт утверждал, что модель акторов должна обеспечить гарантии на предоставление услуги. Хотя в модели Дейкстры не может быть неограниченного количества времени между выполнением последовательных операций на компьютере, параллельно выполняемая программа, которая начала свою работу в строго определённом состоянии, может быть прервана лишь в ограниченном числе состояний. Следовательно, модель Дейкстры не может обеспечить гарантии предоставления услуги. Дейкстра утверждал, что невозможно осуществить неограниченный недетерминизм.
Хьюитт утверждал иное: не существует ограничения на время, которое затрачивается на работу участка вычислений, называемого арбитром для урегулирования конфликтов. Арбитры имеют дело с разрешением таких ситуаций. Часы компьютера работают асинхронно с внешними входами: вводом с клавиатуры, доступом к диску, сетевым входом и так далее. Так что для получения сообщения, отправленного на компьютер, может пройти неограниченное время, и за это время компьютер может пройти через неограниченное количество состояний.
Неограниченный недетерминизм является характерной чертой модели акторов, в которой используется математическая модель Клингера, основанная на . В модели акторов не существует глобального состояния.
Прямая связь и асинхронность Сообщения в модели акторов не обязательно буферизуются. В этом её резкое различие с предшествующими подходами к модели одновременных вычислений. Отсутствие буферизации вызвало большое недоразумение во время развития модели акторов, и до сих пор эта тема является предметом споров. Некоторые исследователи утверждают, что сообщения буферизуются в «эфире» или «окружающей среде». Кроме того, сообщения в модели акторов просто посылаются (например, пакеты в IP). Никаких требований на синхронное рукопожатие с получателем не существует.
Создание новых акторов и передача адресов в сообщениях означают изменяемую топологию Естественным развитием модели акторов была возможность передачи адресов в сообщениях. Под влиянием сетей с коммутацией пакетов Хьюитт предложил разработать новую модель одновременных вычислений, в которой связь не будет иметь вообще никаких обязательных полей, все они могут быть пустыми. Конечно, если отправитель сообщения желает, чтобы получатель имел доступ к адресам, которых он ещё не имеет, адрес должен быть отправлен в сообщении.
В процессе вычислений, возможно, потребуется отправить сообщение получателю, от которого позже нужно получить ответ. Способ сделать это состоит в том, чтобы отправить сообщение, в котором записан адрес другого актора, называемого возобновлением (иногда его также называют продолжением или стеком вызовов). Получатель может затем создать ответное сообщение, которое будет отправлено на возобновление.