Зависимые объекты и цепочка обновлений

[Dmitriy40]

Мне в моём коде не нужна квитанция о приёме сигнала, факт его получения гарантируется системой передачи сигналов (сообщений) и если принимающий объект не убьётся до получения сигнала, то сигнал дойдёт гарантированно. Когда-то. Чтобы отловить момент дохода всех сигналов я и завёл глобальные переменные signals и objects. В результате как бы сигналы не ходили, когда-нибудь они дойдут все и тогда переменная обнулится и всё сработает правильно. Т.е. мой код не закладывается ни на синхронность сигналов или любых других операций, ни на асинхронность, он в обеих случаях будет работать правильно. Единственное исключение — атомизация доступа к глобальным переменным. Что решается стандартными средствами языка или библиотеки или ОС (тут уж на выбор кому что больше нравится). Код также не зависит от реализации системы передачи сигналов, главное чтобы они хоть когда-нибудь доходили, потому не обязательно пользоваться механизмами ОС (просто мне это проще для понимания, они уже есть и превосходно работают), можно использовать любую систему передачи сообщений/сигналов. Другим преимуществом кода является что он не привязан к количеству потоков выполнения, хоть по процессору на каждый объект, или хоть в один поток, всё всё равно всегда будет работать правильно (разумеется если работают другие стандартные механизмы синхронизации планировщика потоков). Плюс ни один объект не задерживает процессор дольше необходимого для приёма и передачи сигнала, нигде нет пустых или непустых циклов ожидания чего-то, самые длинные циклы лишь в передаче сигналов потомкам, а я изначально опёрся что обмен сигналами достаточно нетребователен к ресурсам. Плюс лёгкость расширения алгоритма действий объектов путём добавления новых сигналов или лёгкость встраивания сигналинга в уже существующую систему работы объектов. Плюс фиксированный требуемый объём памяти, не меняющийся в процессе обмена сигналами (добавление и удаление узлов игнорирую). И нет выделенного потока, который обрабатывает всю сцену, каждый объект отвечает только за себя и работает только сам с собой (и с системой передачи сигналов и парой глобальных переменных), всё. Это повышает надёжность. И исходно ТС этого и хотел, распределённую системы работы с объектами. А распределённые системы считается лучше проектировать именно с обменом сигналами/сообщениями, тогда нет привязки к характеристикам среды передачи данных между объектами (может два объекта на одном проце, может на соседних в одной плате, а может они на разных компах на разных материках), это легко масштабируется хоть на весь глобальный интернет. Ну и логика работы каждого объекта получается заметно проще, ведь с внешним миром он общается через простые формальные интерфейсы (а не методы классов или геттинги и сеттинги), фактически просто конечный автомат реагирования на внешние сигналы/сообщения. Для сложно связанных систем этот подход проще чем всё делать процедурно.
Но я ни на чём не настаиваю, выбор за ТС, что ему понятнее и ближе и проще и удобнее.

PS. Ну и ложка дёгтя: я не уверен что при обработке сигнала invalidate правильно модифицируется My.local. После изменения рассылки сигнала invalidate их количество уменьшилось, а сохранился ли подсчёт количества затронутых родителей в My.local (и был ли он правильным) не уверен. Так что мой код может быть и не рабочим, надо проверять ...
По смыслу всё просто: шлём две волны, сначала invalidate с подсчётом активных сигналов в signals и затронутых объектов в objects, когда она "погаснет" (signals обнулится), тогда волну done, когда она "погаснет" (обнулится objects), тогда сигнал перерисовки сцены; в каждом объекте считаем количество затронутых родителей в My.local; каждый объект пересчитываем когда получены сигналы done от всех родителей (проверяется лишь по количеству сигналов, неважно от кого, но посторонних сигналов в системе быть не может) и по окончании пересчёта уведомляем потомков (сигналами).

[george66]

rockclimber в сообщении #1479304 писал(а):

Удаление дочернего объекта должно случиться, только если у него "умерли" все родители, правильно?

Нет, тут всё просто - объект гибнет, если гибнет хотя бы один родитель (прямая, проведённая через две точки, исчезает, если убрать любую из точек)

-- 15.08.2020, 17:02 --

Dmitriy40 в сообщении #1479312 писал(а):

Но я ни на чём не настаиваю, выбор за ТС, что ему понятнее и ближе и проще и удобнее.

Мне очень нравится, но я должен продумать.

[george66]

Dmitriy40 в сообщении #1479152 писал(а):

По моему на сигналах задача решается двумя сигналами invalidate и done и двумя глобальными счётчиками signals и objects (их модификация должна быть защищена разделением доступа) и локальным счётчиком my.local принятых сигналов в каждом объекте и глобальным указателем ObjectStart на изначальный изменённый объект (ему защита не обязательна) (он заменяет пустой цикл ожидания обнуления signals в ModifyObject() перед посылкой себе сигнала done для начала пересчёта).

А почему вместо objects не считать сигналы done? И поясните, пожалуйста, про разделение доступа.

[george66]

Если вместо objects считать сигналы done, не решит ли это проблему гонок? Допустим, какой-то объект вздумал меняться, когда ещё идёт пересчёт от предыдущего изменения. Он начинает рассылать сигналы "готовься" (invalidate). Что делать его потомку, если он получил сигнал "готовься", ещё не получив всех сигналов done от родителей и не начав первый пересчёт? Я думаю, просто сделать

My.local++;

В этом случае он будет ждать, пока придут сигналы done от первого и второго обновлений, а только потом обновится сам. Рисование может зависнуть, если картинка сложная, а какой-то объект меняется непрерывно (держим нажатой кнопку "изменить параметр"), но когда кнопку отпустим, сразу нарисуется окончательный результат.

[Dmitriy40]

george66 в сообщении #1479328 писал(а):

А почему вместо objects не считать сигналы done? И поясните, пожалуйста, про разделение доступа.

Да, можно и done считать, в той же переменной signals, даже на одну глобальную переменную меньше будет. Но не будет общего числа затронутых объектов, если оно зачем-то нужно (в signals лишь мгновенное количество, не общее).

К глобальным переменным signals и objects (если она реализуется) из всех затронутых объектов осуществляется доступ не только на чтение, но и на запись, а в многопоточной системе надо исключать одновременный доступ на запись (и модификацию) к любой общей/глобальной переменной. Семафорами, критическими секциями или много чем ещё можно, включая и встроенные средства языка. Но запись (точнее модификация) должна быть атомарна, т.е. только от одного (но любого) объекта. Кстати именно поэтому у меня везде (надеюсь) сначала увеличиваются счётчики и лишь потом уменьшаются (на единицу для поглощения входящего сигнала), или увеличиваются сразу на скорректированное значение. Т.е. ни в какой момент времени счётчик не может обнулиться если волна не закончилась.
Переменную ObjectStart защищать нет необходимости, в неё пишется или до начала всего процесса, или по его полному завершению, и всегда только одним объектом (но в начале и в конце разными). В каком бы порядке объекты не выполнялись, совместиться эти операции не могут и потому защита не обязательна.

george66 в сообщении #1479346 писал(а):

Если вместо objects считать сигналы done, не решит ли это проблему гонок?

Проблема гонок не связана с повторной модификацией объекта до окончания просчёта всей сцены, засада в разном времени прохождения сигналов invalidate и done до каких-то объектов вдали от начального. И может получиться что сигнал done придёт ДО прихода сигнала invalidate, по приходу же последнего тогда произойдёт опасная чушь. Лишь поэтому надо ждать окончания волны invalidate и лишь потом запускать волну done.

george66 в сообщении #1479346 писал(а):

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

Хм, а ведь да, может получиться, даже ничего менять не надо, не могу придумать пример когда это не сработает. Выходит тут даже можно сколько угодно объектов модифицировать в любое время, даже во время пересчёта предыдущего состояния. Надо только будет снова разделить счётчики сигналов invalidate и done. И вместо одной переменной ObjectStart сделать список таких объектов, которым и рассылать сообщения done для начала пересчёта при обнулении signals. Или ждать окончания волны invalidate в запускающей процедуре ModifyObject() и лишь потом в ней же запускать волну done (но мне так не понравилось, не люблю пустых циклов ожидания, занимающих проц на 100% на неопределённое время).
Ещё будет полезно в обработке сигнала done первым делом проверить My.local на ноль и если да, то ничего не делать (кроме уменьшения счётчика сигналов done).
О как, оказывается код даже более универсальный получился чем думал.

-- 16.08.2020, 00:50 --

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

[EUgeneUS]

Dmitriy40 в сообщении #1479312 писал(а):

PS. Ну и ложка дёгтя: я не уверен что при обработке сигнала invalidate правильно модифицируется My.local. После изменения рассылки сигнала invalidate их количество уменьшилось, а сохранился ли подсчёт количества затронутых родителей в My.local (и был ли он правильным) не уверен. Так что мой код может быть и не рабочим, надо проверять ...

ИМХО, изначальный вариант неправильный (сломается волна пересчета). Скорректированный - правильный.

Dmitriy40 в сообщении #1479352 писал(а):

Хм, а ведь да, может получиться, даже ничего менять не надо, не могу придумать пример когда это не сработает. Выходит тут даже можно сколько угодно объектов модифицировать в любое время, даже во время пересчёта предыдущего состояния. Надо только будет снова разделить счётчики сигналов invalidate и done. И вместо одной переменной ObjectStart сделать список таких объектов, которым и рассылать сообщения done для начала пересчёта при обнулении signals. Или ждать окончания волны invalidate в запускающей процедуре ModifyObject() и лишь потом в ней же запускать волну done (но мне так не понравилось, не люблю пустых циклов ожидания, занимающих проц на 100% на неопределённое время).
Ещё будет полезно в обработке сигнала done первым делом проверить My.local на ноль и если да, то ничего не делать (кроме уменьшения счётчика сигналов done).
О как, оказывается код даже более универсальный получился чем думал.

1. Если вторая модификация началась пока не закончилась первая волна инвалидизации, то ничего страшного не происходит. Всё отработает штатно. Это всё равно, что "пожар" начался с некого (фиктивного) объекта, у которого дети - реально модифицуируемые объекты. В вашем варианте (доработанном),в роли такого фиктивного объекта будет список ObjectStart.

2. Хуже, когда второй пожар начался во время волны пересчета. Гонок между первой волной пересчета и второй волной инвалидизации вроде бы не происходит. Но, ИМХО, пересчет в таких случаях лучше останавливать, хотя бы из соображений исключения двойного пересчета объектов (когда этого можно избежать).

Сделать это можно так:
1. В обработке сигнала Done перед пересчетом объект проверяет переменную signals. Если не ноль, то это означает, что начался второй пожар, тогда объект не пересчитывает себя и не шлет сигнал Done потомкам, а прописывает себя в ObjectStart и запоминает свое специальное состояние (Wait = true), objects не изменяет.
2. В обработке сигнала Invalidate проверяется состояние объекта. Если Wait == true, удаляем себя из ObjectStart, увеличивает My.local, сигналы потомкам не шлет, signals уменьшается на единицу (входящий сигнал поглощен).

ИМХО, всё можно упростить, если
а) вместо My.local использовать просто флаг IsValid
б) подсчет количества невалидных родителей производить путем опроса их флагов, если есть такая возможность. (Вообщем-то нам даже не нужно количество, а просто наличие\отсутствие инвалидных)
Но это нарушает требование "взаимодействие между объектами только через сигналы".

[Dmitriy40]

EUgeneUS в сообщении #1479362 писал(а):

Но это нарушает требование "взаимодействие между объектами только через сигналы".

Вообще-то не нарушает, придётся лишь добавить два сигнала запрос от потомка и ответ родителя и обрабатывать их.
Но мне в принципе не нравится опрос всех родителей, он слишком нагружает сеть передачи сигналов, требует кроме списка потомков ещё и списка родителей в каждом узле/объекте, и не совсем понятно в какой именно момент данный объект должен опросить своих родителей может ли он запустить свой пересчёт.

EUgeneUS в сообщении #1479362 писал(а):

а прописывает себя в ObjectStart

Вот не хочу бесконтрольного разрастания списка начальных объектов, я бы их ограничил лишь реально модифицированными.
Исключить двойной пересчёт можно и по другому, например при получении done проверять signals>0 (именно волны invalidate) и если да, то пересчёт не запускать, а повторить самому себе сигнал done. Фактически это будет ожидание завершения волны invalidate всеми объектами, которые были готовы к пересчёту. Плюс при получении done проверять My.local==0 и если нет (был получен хоть один сигнал invalidate), то сигнал done себе не отправлять. Тогда постепенно ожидающих объектов будет становиться меньше, останутся только реально не зависящие от второй волны invalidate.
Тут сложно сказать что лучше, разрастание списка или спам сигналами done самому себе. Пожалуй даже выбор будет зависеть от конкретной ситуации (насколько сильно связна сеть, какие затраты на передачу сигнала, количество объектов в системе).

george66
Кстати, я тут подумал, ведь ObjectStart не является необходимым, можно просто в ModifyObject() вместо пустого цикла ожидания wait(signals>0){} поставить WaitForSingleObject() (из WinAPI, но аналогичное должно быть и в языке) с ожиданием семафора, который отпускать именно по обнулению signals. Тогда ModifyObject() будет выглядеть как-то так:

Используется синтаксис C

void ModifyObject() {
        OpenSemaphore(WaitSignalIs0);//Взведение семафора
        signals = 1;//Сигнал от фиктивного родителя
        SendSignal(My, INVALIDATE);//Оповещаем самого себя от фиктивного родителя о планируемом пересчёте
        WaitForSingleObject(WaitSignalIs0, 0);//Бесконечный пустой цикл ожидания завершения волны invalidate, правда надо бы проверить результат для контроля ошибок
        SendSignal(My, DONE);
}

И конечно вместо SendSignal(ObjectStart, DONE) в обработчике сигнала invalidate надо просто отпустить семафор командой ReleaseSemaphore(WaitSignalIs0).
И это прекрасно будет работать с множественными волнами пересчёта, без всяких разрастающихся списков. Просто каждый модифицируемый объект будет попадать в ожидание семафора (завершения всех волн invalidate) и потом запускать множественную волну done. Исключение — если стали модифицировать объект, который зависим по предыдущей волне, тут надо додумать что делать, скорее всего достаточно перед запуском волны done проверить My.local==0 (т.е. что мы не попали в первую волну пересчёта).
Но если ModifyObject() вызывается из обработки сообщений, то так делать нельзя, обработчик подвиснет до завершения волны invalidate и соответственно не обработает вторую волну invalidate.

[EUgeneUS]

Dmitriy40 в сообщении #1479434 писал(а):

Но мне в принципе не нравится опрос всех родителей, он слишком нагружает сеть передачи сигналов (1), требует кроме списка потомков ещё и списка родителей в каждом узле/объекте (2), и не совсем понятно в какой именно момент данный объект должен опросить своих родителей может ли он запустить свой пересчёт (3).

пронумеровал по тексту.

(1) - см. ниже.
(2) - да, если нет возможности или желания хранить на каждый объект ещё и список родителей, то вариант не проходной.
(3) - вместо if(My.local==0) писать if(IsInvalidParent()) и всё.

Dmitriy40 в сообщении #1479434 писал(а):

Исключить двойной пересчёт можно и по другому, например при получении done проверять signals>0 (именно волны invalidate) и если да, то пересчёт не запускать, а повторить самому себе сигнал done.

Тут решается проблема: если остановили волну пересчета из-за начала второй волны инвалидизации, то как её запустить снова, когда она закончится? Итого получилось два вараинта:
а) записать объекты, на которых остановились (может быть много объектов), в ObjectStart
б) либо каждый объект, на котором остановились (этом может быть много объектов), шлёт сам себе сигнал (может быть много сигналов).
ИМХО, если заботимся о пункте (1) выше, то ответ очевиден.

[EUgeneUS]

EUgeneUS в сообщении #1479441 писал(а):

Тут решается проблема: если остановили волну пересчета из-за начала второй волны инвалидизации, то как её волну пересчета запустить снова, когда она закончится вторая волна инвалидизации?

она-она

[Dmitriy40]

EUgeneUS в сообщении #1479441 писал(а):

(3) - вместо if(My.local==0) писать if(IsInvalidParent()) и всё.

Кажется я чего-то не понимаю. У меня эта проверка стоит в обработчике сигнала done и она проверяет что все затронутые (а не все вообще!) родители стали валидными. У Вас кто пошлёт сигнал done нашему объекту чтобы он стал проверять всех своих родителей? Если любой родитель, как я предполагаю, то зачем тогда проверять других родителей? Они же не послали сигнала done нам и значит не готовы. Или тут речь только про объекты попавшие в список ObjectStart? Что-то я запутался в вариантах.
Ну и выделенное жирным может быть критичным, обмениваться сигналами только с затронутыми родителями (точнее они нам шлют сигнал) или со всеми, если затронута малая часть всех родителей, разница для всей сцены может быть значительна.

Да, предложенная мной посылка done самому себе тоже плоха, но их количество хотя бы линейно от небольшого количества объектов, пересчитываемых прямо в данный момент, а не квадратична от них же (ведь родителей обычно не один у каждого), ведь каждый объект шлёт лишь один сигнал (самому себе), а не всем своим родителям. И надо бы додумать как оптимизировать вторичные волны, с этим согласен. Может и правда список ObjectStart будет лучшим решением.

[EUgeneUS]

Dmitriy40
Объект может начать пересчёт, только если все родители стали валидными. Вообще все. Это требование.

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

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

Если делать опрос на сигналах, то мой вариант их может потребовать больше в разы. "В разы" определяется количеством родителей, и какая часть из них затронута.
Но если внутри объекта имеем список родителей (а для моего варианта он необходим), то почему бы его не иметь в виде списка указателей на родителей. Просто пройтись по нему и проверить флаг IsValid у всех родителей. Без сигналов.

[Dmitriy40]

EUgeneUS
Как и зачем опрашивать родителей понятно. Непонятно в какой момент, чем и кем этот опрос инициируется. У меня — по сигналу done от любого родителя, проверяется что все стали валидными (по локальному счётчику) и тогда запускаем свой пересчёт. Когда и от кого у Вас наступает момент опроса объектом своих родителей?

PS. "Без сигналов" для меня недостаток, я объяснял выше почему многопоточные (и в частности распределённые как хотел ТС) системы лучше делать на сигналах. А то имея список потомков им тоже ничего слать не нужно, поменять их внутренние состояния прямо из родителя и всё, почти как rockclimber и предлагал. И будем сами париться добавляя многопоточность/параллельность если её вдруг захочется вместо того чтобы переложить на плечи ОС. Впрочем однопоточный вариант имеет свои преимущества.

[EUgeneUS]

Dmitriy40 в сообщении #1479491 писал(а):

У меня — по сигналу done от любого родителя, проверяется что все стали валидными (по локальному счётчику) и тогда запускаем свой пересчёт. Когда и от кого у Вас наступает момент опроса объектом своих родителей?

Точно также. Только вместо проверки локальной переменной if(My.local==0) проводится опрос родителей на наличие инвалидных if(IsInvalidParent()).
То есть:
1. Пришел сигнал done от какого-то родителя (не важно какого)
2. В обработке сигнала проверяем - а есть ли инвалиды среди родителей?
3. Если нет, то пересчитываем себя, ставим флаг IsValid=true и отправляем done потомкам.
upd: это в упрощенном виде. Так-то нужно еще проверить, а не начались ли вторая волна ковида инвалидизации.
4. Если есть, то беда-печалька, ничего не делаем.

-- 16.08.2020, 22:04 --

Dmitriy40 в сообщении #1479491 писал(а):

PS. "Без сигналов" для меня недостаток, я объяснял выше почему

У меня некая гибридная штука получается.
а) "Волны", как "пожара" (инвалидации или удаления), так и пересчета, распространяются на сигналах. (*)
б) Но для принятия некоторых решений внутри обработки сигналов происходят прямые опросы объектов.

Не знаю, насколько это хорошо или плохо...

(*) Под "пожаром" понимается такое распространение, когда "огонь" передается от родителя всем потомкам, которые ещё не "сгорели".
Волна пересчета не попадает под определение "пожара".

[Dmitriy40]

Уф, понял, проверку одной локальной переменной if(My.local==0) Вы заменяете на проверку кучи нелокальных переменных (параметров других объектов). При этом моя локальная переменная у Вас упрощается до булевой (валидны ли мы сами). Ну да, так повышается надёжность, но больше затраты ресурсов (надо опросить больше переменных, плюс надо иметь отдельный список родителей, и это в каждом объекте). Конечно опросить переменные быстрее обмена сигналами, но мне-то и не надо связываться с родителями, они сами сообщат что готовы. У Вас они тоже каждый сообщат, но плюс каждый их потомок всё равно проверит всех своих родителей по нескольку раз (полная проверка всех родителей на каждый сигнал от любого родителя о готовности, при 10 родителях и затронутых 4 из них получается 40 проверок).
Т.е. Вы ничего не экономите из сигналов, ведь done тоже передаёте всем потомкам, но добавляете лишние проверки родителей на каждый чих ... Ну, ради надёжности можно конечно, но ...
Или я опять не так понял.

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

[EUgeneUS]

Dmitriy40 в сообщении #1479509 писал(а):

Т.е. Вы ничего не экономите из сигналов, ведь done тоже передаёте всем потомкам, но добавляете лишние проверки родителей на каждый чих ... Ну, ради надёжности можно конечно, но ...

Ну да. Надежность. Аккуратный подсчет my.local требует внимательности при каждом изменени логики. И как-то заметно менялся при модификациях выше.

-- 16.08.2020, 23:00 --

Dmitriy40 в сообщении #1479509 писал(а):

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

Хороший вариант, может быть самый лучший.