Глава 1. Акторы. Начало.

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

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

Без синхронизации — никак!

Машина Тьюринга

Состояние машины Тьюринга в любой момент времени – это совокупность значений всех ячеек памяти. Стартуя с какого-то определенного состояния, машина последовательно переходит из одного состояния в другое под воздействием одной атомарной операции. Иными словами, процесс вычислений можно воспринимать как последовательность шагов, где каждый шаг – переход из одного состояния Si-1 программы в Si под воздействием одной атомарной команды ci.  Схематично шаги машины показаны на рисунке

шаги машины тьюринга

Здесь c1, c2, …, cn – это атомарные команды, а S0, S1, …, Sn– это состояния машины.

Вот так неявно было введено требование глобального времени: все команды должны быть линейно упорядочены во времени.

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

этому перекрестку не помешает сихронизация

Результат выполнения параллельной программы зависит от последовательности, в которой выполняются команды из разных потоков. Это называется состоянием гонок (race condition).

Поясним состояние гонок на следующем примере:

Пусть у нас есть два потока команд и переменные x и y, которые используются обоими этими потоками. Такие переменные называются разделяемыми. Пусть
x = 1, а y = 3. В первом потоке выполняется выражение

x = y+2;

в во-втором:

y = x + 1;

Гонки здесь появляются из-за того, что эти команды не выполняются атомарно, то есть записываются с помощью нескольких машинных команд. Например, вот так можно записать первое выражение на ассемблере для 32 разрядной архитектуры процессоров Intel:

move eax, y    ; прочитать значение переменной y в регистр eax
add  eax, 2    ; сложить значение регистра eax и 2
mov x , eax    ; записать результат сложения в переменную y.

Аналогично записывается второе выражение.

move ebx, x    ; прочитать значение переменной y в регистр ebx
add  ebx, 2    ; сложить значение регистра ebx и 2
mov y , ebx    ; записать результат сложения в переменную y.

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

x = 5; y = 6; — сначала x присвоили значение 5, затем прочитали это значение во-втором потоке, а потом y присвоили 6.

x = 4; y = 2; — сначала y присвоили значение 2, затем прочитали значение y в первом потоке, а затем x присвоили значение 4.

x = 5; y= 2; — сначала в обоих потоках прочитали значения x и y соответственно, а затем выполнили присваивание.

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

развязка

Мы не будем углубляться в теорию многопоточного программирования. Познакомиться с ней можно в книге Грегори Эндюса:

Эндрюс

Писать многопоточные программы гораздо труднее, чем однопоточные. Об этом, например, пишет в своей статье Проблемы с потоками Эдвард Ли:

Non-trivial multithreaded programs are incomprehensible to human …

Трудность заключается в том, что параллельная программа имеет значительно больше вариантов выполнения по сравнению с последовательной. Настолько больше, что предусмотреть все возможные варианты исполнения удается немногим.  На моем личном опыте, лишь 1% программистов из тех, с кем я общался, умеет писать многопоточные программы сложнее, чем просто запустить задачу в фоновом потоке.

Что делать?

В 1973 году появилась статья Карла Хьюита, Питера Бишопа и Ричарда Штайгера «Универсальный акторный формализм для искусственного интеллекта», в которой авторы предложили новый подход к вычислимости, основанный на представлении процесса вычислений в виде совокупности независимых, параллельных, взаимодействующих между собой посредством отправки сообщений атомарных элементов, называемых акторами.

В ответ на входящее сообщение актор может:

  • отправить конечное число сообщений другим акторам;
  • создать конечное число акторов;
  • выбрать поведение для приема следующего сообщения.

Забегая вперед, скажем, что многие современные языки и библиотеки для разработки высоконагруженных параллельных приложений, например, Erlang, Scala/Akka, реализуют именно акторную модель вычислений.

Почему акторы?

Акторы – это независящие друг от друга элементы программы, которые не имеют общей, разделяемой памяти. Так что проблема синхронизации в модели акторов отсутствует в принципе. Понять разницу в программировании с разделяемой памятью и акторной модели можно на примере сравнения телефонного звонка и почтового отправления.

phone-mail

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

Телефонная линия – это разделяемый ресурс, за который конкурируют несколько пользователей. Поэтому, если у Вас серьезная организация и Вы не хотите терять звонки своих клиентов, то Вам нужны офисные АТС, многоканальные телефоны, функции удержания вызова – это «примитивы синхронизации», балансировки нагрузки, позволяющие обрабатывать входящие звонки пользователей.

В случае же с почтой, Вы сбросили письмо (сообщение) в почтовый ящик – Вам не нужно никого ждать и Вы можете продолжать заниматься своими делами. Потребность в синхронизации отсутствует в принципе! Это то, что делает модель акторов очень привлекательной для разработки параллельных приложений. Но, в случае с почтой все же есть свои особенности:

  • Может пройти значительное время между моментом отправления сообщения и его получением адресатом.
  • Письмо может вообще не дойти!

 Следующая глава >

Хотите узнать о выходе новых глав?

Подпишитесь! И по мере того, как буду появляться новые главы, Вы будете получать уведомления на email.

* Отписаться можно в любой момент!