Здравствуйте, thesz, Вы писали:

E>>>Если процесс получил несколько сообщений вида {OK, D}, где D в каждом экземпляре сообщения имеет собственное значение (например, {OK, 2007}, {OK, 2008}, {OK, 2009}), то гарантирует ли Эрланг, что эти сообщения (т.е. {OK, D}) будут извлекаться из хранилища сообщений процесса в ФИФО?

К>>Если это сообщения от одного отправителя — да.

T>Во.

T>А у нас их несколько, в общем случае.

T>Так что можно считать, что и нет никакого ФИФО.

Ну то, что никакого — это ты загнул. Это в однопоточном окружении у нас либо ФИФО, либо нет ФИФО. А в многопоточном либо нет ФИФО, либо per-producer fifo, либо causal-fifo (happened-before fifo), либо best-effort fifo.

Эрланг вычёркиваем. Только не считай, что парировав аргумент про Эрланг, ты одновременно парировал и все остальные библиотеки, которые обеспечивают честный causal-fifo (happened-before fifo).

Здравствуйте, Курилка, Вы писали:

К>Если это сообщения от одного отправителя — да.
К>Хотя есть некоторые ньюансы, см. здесь

На счет потери сообщений -- это вполне очевидно (при условии, что взаимодействующие процессы работают на нодах, соединенных лишь одним маршрутом).

Здравствуйте, thesz, Вы писали:

E>>Правильно ли я понимаю, что если в Эрланге процессу пришло несколько однотипных сообщений, то Эрланг не гарантирует их выборку в receive в порядке ФИФО?

T>Не "пришло", а "послали".

Послали -- это другой случай.

Не очень представляю себе, как можно обеспечить ФИФО для отсылки сообщений разными отправителями без использования какого-либо вида глобальной синхронизации между ними (на основании меток времени или меток предшествования, к примеру).

T>>Так что можно считать, что и нет никакого ФИФО.
R>Ну то, что никакого — это ты загнул. Это в однопоточном окружении у нас либо ФИФО, либо нет ФИФО. А в многопоточном либо нет ФИФО, либо per-producer fifo, либо causal-fifo (happened-before fifo), либо best-effort fifo.

R>Эрланг вычёркиваем. Только не считай, что парировав аргумент про Эрланг, ты одновременно парировал и все остальные библиотеки, которые обеспечивают честный causal-fifo (happened-before fifo).

Буду краток.

Наличие таких библиотек не говорит об эффективности программ с их использованием.

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

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

С моей точки зрения, конечно.

E>>>Правильно ли я понимаю, что если в Эрланге процессу пришло несколько однотипных сообщений, то Эрланг не гарантирует их выборку в receive в порядке ФИФО?

T>>Не "пришло", а "послали".
E>Послали -- это другой случай.
E>Не очень представляю себе, как можно обеспечить ФИФО для отсылки сообщений разными отправителями без использования какого-либо вида глобальной синхронизации между ними (на основании меток времени или меток предшествования, к примеру).

Я об этом же.

В общем случае, программу надо проектировать так, как будто нет никакого ФИФО.

Значит, его нет.

Здравствуйте, thesz, Вы писали:

T>В общем случае, программу надо проектировать так, как будто нет никакого ФИФО.

T>Значит, его нет.

Я смотрю на это со следующей точки зрения. Есть две составляющих механизма обмена сообщениями -- send и receive. Про send пока речь не идет, сейчас для меня важнее receive. Один из способов реализации receive -- это формирование для каждого агента (процесса, актера) очереди полученных им сообщений. Агент обращается к этой очереди и, если она не пуста, извлекает сообщение. Поэтому речь идет о том, обеспечиваются ли какие-либо ФИФО дисциплины по отношению к уже находящимся в очереди сообщениям.

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

Что же до send-а, то у меня так же существует сильное подозрение, что если не будет обеспечиваться ФИФО доставки сообщений одного отправителя одному получателю, то реализация некоторого множества задач будет являться просто геморроем.

Выше речь шла о равноприоритетных сообщениях.

E>Мое мнение состоит в том, что если для извлечения во время receive уже полученных агентом сообщений не обеспечивается ФИФО, то реализация целого ряда задач (управление оборудованием, например) будет крайне затруднена. И в таких условиях невыгодно заниматься проектированием в предположении об отсутствии ФИФО.

Ну вот та же миграция кода.

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

Если мы жестко закладываемся на ФИФО, то у нас возникают трудности в реализации произвольного сценария. ФИФО здесь внешний инвариант, нами не обеспеченный, но нами используемый.

Это полезно, но это и уменьшает гибкость.

E>Что же до send-а, то у меня так же существует сильное подозрение, что если не будет обеспечиваться ФИФО доставки сообщений одного отправителя одному получателю, то реализация некоторого множества задач будет являться просто геморроем.

E>Выше речь шла о равноприоритетных сообщениях.

Понятно.

Я смотрю на всё это с точки зрения динамического потока данных.

В этом случае особой важности в ФИФО нет. Но там и состояния. как такового, тоже нет.

Здравствуйте, eao197, Вы писали:

E>Мое мнение состоит в том, что если для извлечения во время receive уже полученных агентом сообщений не обеспечивается ФИФО, то реализация целого ряда задач (управление оборудованием, например) будет крайне затруднена. И в таких условиях невыгодно заниматься проектированием в предположении об отсутствии ФИФО.

Только совсем не обязательно при этом делать только ФИФО механику. Подобные задачки неплохо решаются при помощи обсуждаемых рядом фьючерсов — зависимость задач (сообщений) друг от друга задается наличием возвращаемого значения.
В более общем случае подобные ситуации разруливаются при помощи continuations. Если на пальцах, то к задаче (сообщению) по необходимости привязывается некий предикат, который определяет, может задача выполнится, или нет. При помощи такой механики можно строить сколь угодно хитрые цепочки зависимостей, и только там, где нужно.

Здравствуйте, AndrewVK, Вы писали:

AVK>Здравствуйте, eao197, Вы писали:

E>>Мое мнение состоит в том, что если для извлечения во время receive уже полученных агентом сообщений не обеспечивается ФИФО, то реализация целого ряда задач (управление оборудованием, например) будет крайне затруднена. И в таких условиях невыгодно заниматься проектированием в предположении об отсутствии ФИФО.

AVK>Только совсем не обязательно при этом делать только ФИФО механику. Подобные задачки неплохо решаются при помощи обсуждаемых рядом фьючерсов — зависимость задач (сообщений) друг от друга задается наличием возвращаемого значения.

Фьючерс -- это сторона отправителя. В процитированном абзаце я говорил только о стороне получателя.

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

Может быть. Есть только у меня подозрение, что обеспечение ФИФО на стороне получателя будет приводить к более простым решениям (в плане телодвижений программиста), чем использование предикатов. Если же перейти к распределенным системам, где отправитель и получатель работают на разных узлах, то передача предиката в сообщении будет возможна не всегда.

Здравствуйте, thesz, Вы писали:

E>>Мое мнение состоит в том, что если для извлечения во время receive уже полученных агентом сообщений не обеспечивается ФИФО, то реализация целого ряда задач (управление оборудованием, например) будет крайне затруднена. И в таких условиях невыгодно заниматься проектированием в предположении об отсутствии ФИФО.

T>Ну вот та же миграция кода.

T>"Оборудование" (а вообще — некоторый процесс) узнало об изменении адреса узла доставки раньше, чем ранее обрабатывавший сообщения узел, и поэтому последний стал отправлять уже пришедшие сообщения позже. Получилось, что некоторые сообщения от оборудования пришли на обработку раньше своих предшественников.

Не очень понимаю, о чем ты говоришь. Не могу представить себе реальный пример этого сценария

T>Если мы жестко закладываемся на ФИФО, то у нас возникают трудности в реализации произвольного сценария. ФИФО здесь внешний инвариант, нами не обеспеченный, но нами используемый.

Можно еще одну ситуацию вспомнить. Допустим, у нас есть агенты s и r. Они работают на узлах A и B (имеются в виду узлы локальной сети). Но эти узлы соеденены не напрямую, а через несколько других узлов. И путь от A к B может лежать через маршрут A -> D -> E -> B или через маршут A -> C -> B. Агент s с узла A отправляет сообщения m1, m2, m3. Сообщения m1 и m3 уходят по маршруту A->D->E->B, а сообщение m2 -- по маршруту A->C->B. В этом случае сообщения r может получить как m2, m1, m3, так и m1, m3, m2, так и m1, m2, m3. Если логика взаимодействия s и r построена на гарантиях ФИФО для сообщений от одного источника, то все накрывается медным тазом.

T>Я смотрю на всё это с точки зрения динамического потока данных.

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

Здравствуйте, eao197, Вы писали:

E>Фьючерс -- это сторона отправителя. В процитированном абзаце я говорил только о стороне получателя.

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

E>Может быть. Есть только у меня подозрение, что обеспечение ФИФО на стороне получателя будет приводить к более простым решениям (в плане телодвижений программиста)

И оно же будет приводить к тому, что у лоад балансера будет намного меньше возможностей. И, что касается телодвижений — их нужно будет сделать один раз. Зато там, где ФИФО не нужно его не будет. А там, где простенькая схема ФИФО не обеспечивает нужной эффективности, всегда можно сделать что то более хитрое.

E>передача предиката в сообщении будет возможна не всегда.

Почему?

T>>"Оборудование" (а вообще — некоторый процесс) узнало об изменении адреса узла доставки раньше, чем ранее обрабатывавший сообщения узел, и поэтому последний стал отправлять уже пришедшие сообщения позже. Получилось, что некоторые сообщения от оборудования пришли на обработку раньше своих предшественников.
E>Не очень понимаю, о чем ты говоришь. Не могу представить себе реальный пример этого сценария

Твой пример тоже неплох, надо сказать.

T>>Я смотрю на всё это с точки зрения динамического потока данных.
E>Я заметил, что мы находимся сильно в разных предметных областях. Отчего временами мне сложно понимать тебя. В частности, я мало чего понял из твоей статьи, ссылку на которую ты дал remark-у (с обсуждением задачи перемножения матриц на динамическом потоке данных).

Это дело я думаю исправить, но всё никак руки не дойдут.

Здравствуйте, AndrewVK, Вы писали:

E>>Фьючерс -- это сторона отправителя. В процитированном абзаце я говорил только о стороне получателя.

AVK>Только отправитель знает, что определенные сообщения должны дойти в определенном порядке.

Смотри, пусть отправитель вызывает:

future<ResetDevice> reset = sendResetDevice(...);
future<SetParams> set = sendSetParams(...);
future<WriteData> write = sendWriteData(...);

А получатель извлекает запросы из своей очереди в порядке WriteData, SetParams, ResetDevice. Даже не смотря на порядок отсылки отправителем. Имеет ли какой-то смысл то, что одноприоритетные сообщения перепутываются уже в очереди получателя? Или же ФИФО на стороне получателя -- это нормальное пожелание?

E>>Может быть. Есть только у меня подозрение, что обеспечение ФИФО на стороне получателя будет приводить к более простым решениям (в плане телодвижений программиста)

AVK>И оно же будет приводить к тому, что у лоад балансера будет намного меньше возможностей.

Load Balancer -- это слишком общее понятие. Боюсь, без более четкого органичения предметной области обсуждать load balancer-ы не имеет смысла.

E>>передача предиката в сообщении будет возможна не всегда.

AVK>Почему?

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

Здравствуйте, eao197, Вы писали:

E>Смотри, пусть отправитель вызывает:
E>

E>future<ResetDevice> reset = sendResetDevice(...);
E>future<SetParams> set = sendSetParams(...);
E>future<WriteData> write = sendWriteData(...);
E>

Налицо некоторое непонимание того, что такое фьючерс. Должно быть как то так:

var reset =
    new Future(() => ResetDevice(...))
    .ContinueWith(() => SetParams(...))
    .ContinueWith(() => WriteData(...));

AVK>>И оно же будет приводить к тому, что у лоад балансера будет намного меньше возможностей.

E>Load Balancer -- это слишком общее понятие.

Оно достаточно специализированно, для того чтобы понять, что жесткое ограничение фифой сильно свяжет ему руки. Тот же work stealing, к примеру, пойдет лесом.

E> Боюсь, без более четкого органичения предметной области обсуждать load balancer-ы не имеет смысла.

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

E>>>передача предиката в сообщении будет возможна не всегда.

AVK>>Почему?

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

Это решаемо. Например, в C# есть expression tree, в F# собственная похожая механика, в С++ уродец из буста. А в интерпретируемых языках можно просто передавать исходник.

Здравствуйте, AndrewVK, Вы писали:

AVK>Налицо некоторое непонимание того, что такое фьючерс. Должно быть как то так:
AVK>

AVK>var reset =
AVK>    new Future(() => ResetDevice(...))
AVK>    .ContinueWith(() => SetParams(...))
AVK>    .ContinueWith(() => WriteData(...));
AVK>

А это где такой фьючерс?

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

AVK>>>И оно же будет приводить к тому, что у лоад балансера будет намного меньше возможностей.

E>>Load Balancer -- это слишком общее понятие.

AVK>Оно достаточно специализированно, для того чтобы понять, что жесткое ограничение фифой сильно свяжет ему руки. Тот же work stealing, к примеру, пойдет лесом.

Это общие слова.

E>> Боюсь, без более четкого органичения предметной области обсуждать load balancer-ы не имеет смысла.

AVK>Предметная область достаточно ограничена — распределение задач обработки сообщений по имеющимся аппаратным потокам.

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

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

AVK>Это решаемо. Например, в C# есть expression tree, в F# собственная похожая механика, в С++ уродец из буста. А в интерпретируемых языках можно просто передавать исходник.

Это если задача позволяет использовать у себя кодогенерацию/интерпритацию и передачу кода между узлами.

Здравствуйте, eao197, Вы писали:

E>А это где такой фьючерс?

Конкретно в моем примере это TPL. Но это неважно, я хотел просто идею продемонстрировать.

E>Кроме того, все это несколько завуалированный механизм RPC.

Неа, RPC тут совсем никаким боком. Это совершенно обычный фьючерс.

E>Это общие слова.

Это не общие слова, это вполне конкретные вещи. Почитай по ссылочке, там вообще применительно к вполне конкретному Cilk описано.

E>Это если задача позволяет использовать у себя кодогенерацию/интерпритацию и передачу кода между узлами.

А почему она может не позволять?

Здравствуйте, AndrewVK, Вы писали:

E>>А это где такой фьючерс?

AVK>Конкретно в моем примере это TPL.

Понятно, просто я в C++ных примерах использования future никогда не видел continueWith.

E>>Кроме того, все это несколько завуалированный механизм RPC.

AVK>Неа, RPC тут совсем никаким боком. Это совершенно обычный фьючерс.

Аналогия с RPC тут в том смысле, что запуск SetParams(...) и WriteData(...) будет произведен только после получения сигнала об окончании (по каким-либо принчинам) работы ResetDevice(). Т.е. обработчик ResetDevice должен будет послать в ответ какой-то сигнал. Что очень похоже на механизм call/return (а поскольку call передает управление другому процессору/узлу, то это очень похоже на remote).

AVK>Это не общие слова, это вполне конкретные вещи. Почитай по ссылочке, там вообще применительно к вполне конкретному Cilk описано.

А каким боком Cilk к модели обмена сообщениями относится?

E>>Это если задача позволяет использовать у себя кодогенерацию/интерпритацию и передачу кода между узлами.

AVK>А почему она может не позволять?

Например, по соображениям безопасности (один из узлов находится внутри банка, а второй -- снаружи) или скорости работы.

Здравствуйте, eao197, Вы писали:

E>Понятно, просто я в C++ных примерах использования future никогда не видел continueWith.

Интересно, ты вообще мое исходное сообщение читал? Я ведь именно об этом и писал.

AVK>>Неа, RPC тут совсем никаким боком. Это совершенно обычный фьючерс.

E>Аналогия с RPC тут в том смысле, что запуск SetParams(...) и WriteData(...) будет произведен только после получения сигнала об окончании (по каким-либо принчинам) работы ResetDevice().

Оченно странная аналогия, надо сказать.

E>А каким боком Cilk к модели обмена сообщениями относится?

Это пример одной из методик балансинга — work stealing. Ее же можно для агентов применять, если мы агентов используем для распараллеливания вычислений. Ты ведь еще исходную тему топика, надеюсь, не забыл?

AVK>>А почему она может не позволять?

E>Например, по соображениям безопасности (один из узлов находится внутри банка, а второй -- снаружи) или скорости работы.

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

Здравствуйте, eao197, Вы писали:

E>Можно еще одну ситуацию вспомнить. Допустим, у нас есть агенты s и r. Они работают на узлах A и B (имеются в виду узлы локальной сети). Но эти узлы соеденены не напрямую, а через несколько других узлов. И путь от A к B может лежать через маршрут A -> D -> E -> B или через маршут A -> C -> B. Агент s с узла A отправляет сообщения m1, m2, m3. Сообщения m1 и m3 уходят по маршруту A->D->E->B, а сообщение m2 -- по маршруту A->C->B. В этом случае сообщения r может получить как m2, m1, m3, так и m1, m3, m2, так и m1, m2, m3. Если логика взаимодействия s и r построена на гарантиях ФИФО для сообщений от одного источника, то все накрывается медным тазом.
Вот мне в этом плане вот что интересно: протокол IP как раз описывает ровно эту ситуацию.
И есть традиционное решение для построения на нём FIFO порядка, которое не требует никакой синхронизации "в середине", широко известное под аббревиатурой TCP.

Я так понимаю, что концепция примерно такая:
1. В схеме single producer-single consumer можно построить FIFO на протоколе без упорядочивания, применив 1-в-1 стандартные техники из TCP/IP, выкинув обработку потери пакетов. Получатель упорядочивает сообщения на своей стороне. В характерных реалистичных примерах "окно просмотра" для таких получателей будет не очень большим. Затраты оценить навскидку сложно, но они не зависят от латентности канала между отправителем и получателем. Это означает, что всегда найдется такое значение латентности, начиная с которого этот механизм окажется выгоднее, чем классическая синхронизация на семафорных примитивах.

2. В схеме multiple producers-single consumer никакого порядка лучше не вводить. Ну то есть если есть желание устроить себе Bottleneck, то можно устроить генератор sequence и теребить его. Но в общем случае понятия порядка и одновременности один хрен становятся еще слабее, чем в специальной теории относительности. В том смысле, что могут происходить даже артефакты, выглядящие как нарушение принципа причинности.

3. Ничего сильно плохого от этого не произойдет. Не так уж много есть мест, где прямо так нужна вот эта упорядоченность. Управление устройством не делается толпой; над устройством висит агент-драйвер, который его мучает в эксклюзивном синхронном режиме. Все остальные должны договариваться с драйвером. Ну и там уже два варианта: либо протокол подразумевает произвольный порядок (вот тебе содержимое страницы номер X, сбрось ее на диск), либо см.п.1.

Здравствуйте, eao197, Вы писали:

E>Здравствуйте, AndrewVK, Вы писали:

E>>>Фьючерс -- это сторона отправителя. В процитированном абзаце я говорил только о стороне получателя.

AVK>>Только отправитель знает, что определенные сообщения должны дойти в определенном порядке.

E>Смотри, пусть отправитель вызывает:
E>

E>future<ResetDevice> reset = sendResetDevice(...);
E>future<SetParams> set = sendSetParams(...);
E>future<WriteData> write = sendWriteData(...);
E>

Это вредный пример. Зачем делать такой протокол?
Пусть отправитель шлет sendWriteDataWithParams(params, data).
А получатель самостоятельно делает resetDevice.