Pull to refresh

Comments 54

Прикольная нотация
this >>= st_wait_left;

Она не всем нравится, поэтому есть возможность использовать следующие альтернативы:


so_change_state(st_wait_left);
st_wait_left.activate();

Можно выбрать то, что нравится больше.

Цель была в том, чтобы показать, как это может выглядеть. И чтобы читатель решил для себя страшно это, не страшно, если страшно, то настолько.

Вот вы для себя вывод сделали. Уже результат. Если бы внимательно изучили код, на который сослались, может быть было бы еще лучше.
Я на этом фреймворке пишу с тех пор, как он появился, спасибо за рекомендацию.
Да не за что. Мне вот показалось, что там вообще другой алгоритм реализован. Или не показалось? Там каждый философ вилки по одной запрашивает или он просто обращается к table и ему вилки предоставляются сразу обе?

Ну и это мы еще оставим за скобками объем и читабельность кода, тут дело чисто субъективное.
В аппноте есть описание с картинками. Код читать тяжело, ага, а писать было ещё тяжелее, пока моделер не появился.
Так я-то посмотрел, отсюда и подозрение. А вот вы посмотрели? Наверняка да, поэтому вы, зная QP, сможете точно сказать, что там происходит. Ведь так?
Стол вилки выдаёт и собирает, условно. Философ сигналит, что ест, думает, или голодный. Как только философ поел, то стол проверяет, есть ли у него голодные соседи, и «выдаёт ему/им вилки» (сигналит «ешь»). Посмотрите в примерах в репе, там есть и для АРМ, и для позикса, и для виндовоза, на си и плюс-плюсе (EDIT: имелось в виду «соберите и погоняйте»).
> Стол вилки выдаёт и собирает, условно. Философ сигналит, что ест, думает, или голодный.

Ну так это совсем другой алгоритм решения, о чем я вам и намекал. Попробуйте сделать на QP хотя бы вариант no_waiter_simple, тогда можно будет сравнить.

А если на SO-5 делать вариант с таким же алгоритмом, как в примере из QP, то кода будет сильно меньше (может не 2 раза, но в 1.5 наверняка), да и само решение будет сильно проще.
А я разве где-то сказал, что он такой же? Мы же про разные решения одной задачи разговариваем. Или про одно и то же?

QP хорошо работает для случаев большого числа философов. Во времена постановки задачи памяти в машинах было мало, поэтому и извраты эти. В QP количество обслуживаемых философов равно длине очереди указателей на события, плюс фреймворк, стол и один философ (из опыта, всё, кроме первого пункта, нечувствительно на системах примерно в два раза толще Ардуино).
А я разве где-то сказал, что он такой же?

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


QP хорошо работает для случаев большого числа философов.

Количество философов тут не при чем. QP изначально рассчитывался на работу в нише встраиваемых систем. Именно отсюда те извраты.


Во времена постановки задачи памяти в машинах было мало, поэтому и извраты эти.

Нет, не поэтому.

Я не согласен, что выразительность и понятность следует сравнивать, глядя на код. QP пишется практически на UML, который понимается кем угодно с полпинка. Выражает он это потом через автосгенерённый код, написанный с целью делать всё с минимальной затратой циклов и прочих ресурсов. А смотреть на автосгенерённые switch statement'ы и сравнивать это с человеческим кодом глупо как-то, Вам не кажется?
Не знаю, что Вы имели в виду под нишей встраиваимых систем. Я на QP пишу везде, где могу — и в Андроиде, и в Линуксе, и во встраиваемых системах. Если слегка отвлечься от темы и интерпретировать «нишу», как «где можно капусты накосить», то она, по моим скромным запросам, более, чем адекватная.
Вдогонку: я сейчас сижу и порчу QP на microMIPS. Получаю от этой беседы огромное удовольствие, надеюсь, что и Вы тоже.
Я не согласен, что выразительность и понятность следует сравнивать, глядя на код.

Тогда что с чем сравнивается? Написанный вручную за полчаса код с тем, что сгенерировал какой-то генератор на основании нарисованного в визуальной тулзе?


Если вы это предлагаете, то это как сравнивать теплое с мягким.


Не знаю, что Вы имели в виду под нишей встраиваимых систем.

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


Я на QP пишу везде, где могу — и в Андроиде, и в Линуксе, и во встраиваемых системах.

Некоторые умудряются на Java системы реального времени делать. Что не означает, что Java для этого хороший выбор.

Мне у этой задачи нравится решение на CAS, когда либо берешь обе вилки сразу, либо не берешь ни одной. Отпадает ранжирование вилок. Правда, возникает ограничение на 32 философов (каждый бит у uint32 отвечает за одну вилку). Ну и никаких мьютексов, разумеется, одни сплошные спинлоки.

У этой задачи есть требование: философы не должны голодать, если захотят есть. Со спинлоками нет такой гарантии: не сильно удачливый философ будет все время промахиваться и пытаться взять снова и снова, но постоянно кто-то другой может мешать.

Ваше решение с мьютексами точно так же заставит кого-то голодать.
Так ведь в решении Дейкстры голодание всегда ограничено, разве нет?
Оно ограничено только тем, что каждый философ пользуется однажды полученными вилками конечное время. Однако можно представить себе ситуацию, когда один философ кладет вилки и тут же берет их снова. Если при этом мы спустимся до философоф-потоков и вилок-мьютексов, то указаный случай может привести к следующему: тот поток, который разблокирует мьютекс и в течение того же кванта времени блокирует его снова, просто не дает ОС разбудить другой поток, ожидающий этот же мьютекс.
Однако можно представить себе ситуацию, когда один философ кладет вилки и тут же берет их снова.

Вот это вряд ли. Поскольку в подходе Дейкстры философ, который захотел поесть, но не смог взять вилку, никуда не уходит, он следит за появлением вилки. Как только оная появляется, он ее сразу же хватает.


тот поток, который разблокирует мьютекс и в течение того же кванта времени блокирует его снова, просто не дает ОС разбудить ожидающий этого же мьютекса поток.

Это если мьютексы без очереди ожидания.

Ну, мы же говорим про сферическую архитектуру/ОС в вакууме, такую, что решение на CAS заставит кого-то голодать вечно.
Но ведь в случае с CAS-ом (если я правильно понимаю) нет никаких гарантий ни в сферических, ни в актуальных ОС.
Если уж на то пошло, то в случае с CAS ОС вообще не при чем почти. «Почти», потому что можно-таки в спинлоке периодически делать yield, если есть планировщик, кооперативная многозадачность и соответствующий системный вызов.
Ну так все, как я понимаю, упирается вот в какой момент: когда мы говорим про решение Дейкстры на нормальных семафорах ОС (для которых ОС поддерживает очередь ожидания), то ситуации, когда философ закончил есть, положил вилки и тут же сразу схватил их вновь, исключаются. ОС просто не позволит тому же самому потоку захватить семафор вновь.

Тогда как если мы делаем busy-waiting на CAS-ах сами, никаких гарантий у нас нет. Так что, теоретически, голодание какого-то из философов может длится долго, т.к. ситуациям «положил и сразу взял обратно» никто не препятствует.
Да. Так рассуждать можно. Но для этого надо придумать такую архитектуру процессора с соответствующей реализацией барьеров памяти и синхронизации кешей, в которой отпустив кеш-линию можно захватить ее снова не взирая на то, что между этими событиями данную кеш-линию затребовало другое ядро.
Поправьте меня, но ведь при busy-waiting-е у нас идет дискретный запрос значений. С высоким темпом, но дискретный. Т.е. cpu1 сделал CAS, получил результат, который его не устроил, делает следующую итерацию дабы выполнить CAS еще раз. Но как раз в этот момент cpu2 выполняет обновление значения, с cpu3 успешно выполняет свой CAS для только что обновленного значения. Таким образом cpu1 будет «пропускать» те моменты, когда у него есть шанс успешно выполнить свой CAS.
Обычно CAS используется совместно с барьерами памяти. Что гарантирует полную синхронизацию кешей и запрет OOE конвейеру убегать вперед. Т.е. кеш-линия, содержащая данные, которые требуются для CAS инвалидирована во всех остальных ядрах. Т.о. CAS-ы выстраиваются в своеобразную очередь. Это если мы не про ARM c их LL/SC
Спасибо за пояснения, настолько глубоко я не копаю.
Хотя я согласен, что ненулевая вероятность ждать вечно существует, я только лишь указал, что она существует и у семафоров при определенной их реализации. Например, можно слегка оптимизировать очередь и приступать к пробуждению ожидающего процесса только по истечению кванта времени текущего, например, если ядро только одно.
Да, еще одно. Если мы посмотрим на современные реализации мьютексов, то увидим там busy-wait на тысячу-другую (а то и десяток) попыток. И уже потом — системный вызов. Поэтому говорить, что там «честная» очередь, тоже нельзя.
> И уже потом — системный вызов.

И это делает ее чуточку честнее :)
Правда? ,) А мне кажется, что тот, кто ждет давно, находясь в спящем режиме, имеет меньше шансов захватить только что освободившийся мьютекс, чем тот, кто только начал ждать и находится в спинлоке.
Хорошее замечание. Наверное, даже правильное :)

Да, в решении Дейкстры подразумевается, что мьютексы честные, т.е. если мьютекс А захватил, затем мьютекс Б, то сначала его захватывает А, а затем Б. Стандартная реализация std::mutex этого не гарантирует. Но такой честный мьютекс можно сделать и самому, на основе обычного мьютекса и cond var.

«Устаревшие» обедающие философы на C++ без всяких извращений:


struct Fork {
    void take() {
        mut_.lock();
    }

    void put() {
        mut_.unlock();
    }

private:
    std::mutex mut_;
};

struct Philosopher {
    // Алгоритм Дейкстры
    void eat() {
        left_ > right_
            ? doEat(left_, right_)
            : doEat(right_, left_);
    }

private:
    void doEat(Fork* f1, Fork* f2) {
        f1->take();
        f2->take();
        // ням-ням
        f1->put(); // можно класть в любом порядке
        f2->put();
    }

    Fork* left_;
    Fork* right_;
};

Выводы очевидны.

Выводы очевидны.

Мне нет. Не понятно зачем этот комментарий. Не понятно, какие должны последовать выводы.

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

Собственно, статья и писалась для того, чтобы можно было наглядно оценить, сколько именно шума добавляют Акторы и CSP. Как это сделала первая статья с task-based подходом.

Кроме того, лично я исхожу из предположения о разумности читателей. Вряд ли кому-то в голову придет идея использовать Акторов там, где можно применить классику на семафорах. С другой стороны, можно составить впечатление о том, с чем придется иметь дело, если речь зайдет о масштабе хотя бы в сотни тысяч «вилок» и «философов».
Если речь именно об этой задаче, то приведенный выше код с ранжированием мьютексов (решение Дейкстры) масштабируется на любое количество потоков. Совсем другое дело, когда речь заходит о распределенной системе.
> масштабируется на любое количество потоков

Проблема в том, что создавать сотни тысяч рабочих потоков на одной ноде непрактично. Вместо нитей ОС нужно будет уходить в stackful-короутины. Или в таски или акторы.

Вот как раз интересно и будет сравнить подход на потоках, акторах, сопрограммах, CSP и проч. Мне кажется, сопрограммы по читабельности выиграют. При этом приведенный выше код легко переписывается на сопрограммы заменой std::mutex на synca::Mutex из https://habr.com/ru/post/340732/

> Мне кажется, сопрограммы по читабельности выиграют.

Выиграют.
Ой не факт.
Пытаюсь себе представить на сопрограммах отработку ситуации типа «пока transferor командует дозвоном, transferree решил сменить кодек», коими богат мой предметный домен… оно и на FSM тяжело отрабатывается, а на сопрограммах вообще превратится в нечитаемую кашу.
Я про конкретно задачу обедающих философов говорю.
В рамках такого ограничения — да, согласен. (Но не согласен с пользой такого ограничения в принципе, потому что подобные задачи нужны, чтобы на них показывать примеры решения целевых задач.)

Я вижу пользу* от таких статьей в том, что читатель, априори более-менее представляя себе особенности задачи и способы ее решения, может сам оценить объемы и сложность бойлерплейт кода, который пришлось бы написать с использованием конкретного фреймворка (или подхода). Бойлерплейт этот проистекает как от особенностей языка, так и от особенностей и ограничений фреймворка. Поэтому, в принципе, можно представить себе, сколько и какого кода может потребоваться написать для решения других задач.


Если с использованием какого-то другого инструмента получается меньше кода, а сам код более понятен и выразителей — так это же хорошо для всех, имхо.


Другое дело, что выбирая подход к решение конкретной прикладной (а не демонстрационной) задачи, а так же выбирая инструмент, приходится делать выбор на основании не только (и не столько) визуальной привлекательности, сколько на базе целого ряда разнообразных факторов. В плоть до количества звезд на github-е и дате последнего коммита :(


[*] Возможно, я заблуждаюсь, и никакой пользы от подобных статьей нет вообще. Но мое дело написать, а дальше уже пусть каждый сам решает :)

> Я вижу пользу* от таких статьей в том

На всякий случай: я как раз считаю статью полезной и против этого не возражал :)
Просто надо не забывать, в чём подобные образцовые задачи сходны с реальными, а в чём — нет. Хотя тут, как правило, каждый уже выбирает по своей специфике.
я как раз считаю статью полезной

Ну хорошо, что я не один такой :)

Кстати, synca::Mutex гарантирует FIFO, т.е. является честным, а значит будет удовлетворять требованию задачи.

Ох, какой интересный цикл статей, и почему-то прошел мимо меня! Спасибо.
Выводы действительно очевидны:

1. В вашем решении нет штатной возможности понять, что происходит, кто кого ждёт и почему. В решении на SO получение снимка состояния (которые дают все эти ...LRRR...) делается штатными средствами фреймворка. В аналогичном подходе на Erlang (называю его потому, что долго писал на нём аналогичные вещи) — то же самое. У вас этого нет, а если нужно распознать, какой философ на чём остановился — нужно на каждом действии явно вписывать отметку «я сел ждать вилку L».

Также у вас нет никаких механизмов таймаутов — то, что нужно в любой реализации подобного взаимодействия, если она хочет не заклинить в первый день продукции, и вводить их придётся явно и boilerplateʼом. Во фремворках акторов таймауты обычно встроены.

2. За счёт процедурной последовательности действий требуется по одной нити на каждого активного участника (тут — философа). При 5 философах и не на ардуине это ещё терпимо, но если больше — то идёт ненужная нагрузка на ОС. Под реальной нагрузкой (для начала возьмите 10000 активных участников, вслед за Kegelʼем; хотя с нынешними мощностями надо сразу рассматривать случай на 100000) это уже может переполнить допустимые ресурсы, в отличие от решения на FSM.

Ваше решение не пригодно за пределами демонстрационной песочницы. Оно могло бы сойти в качестве примера, от чего придётся уйти, переходя на акторы. Но и тут есть засада — примерно такая же, как в случае демонстрации рекурсии на факториале: образец слишком красив, чтобы давать представление о реальных задачах. В последних обычное линейно-процедурное построение слишком быстро превращается в тупую нечитаемую кашу. Поэтому я бы его и для сравнения не показывал — будет сбивать с толку.

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

Если кому-то интересно, то вот здесь еще немного на тему проблем обеспечения exception-safety в показанном CSP-шном решении.

Для тех, кто интересуется SObjectizer-ом (вдруг таковые есть): уже идет работа над следующей "большой" версией SObjectizer-5.6, в которой будет нарушена совместимость с веткой 5.5 (которая развивалась с серьезной оглядкой на совместимость более 4 лет). Мотивация и основные цели/планы для v.5.6 описаны здесь.


А для обсуждения связанных с SO-5.6 вопросов была реанимирована старая Google-группа. Так что если кто-то хочет оказать влияние на то, как и куда развивается SObjectizer, то имеет смысл заглядывать в эту группу и оставлять свое мнение по тем или иным вопросам. Причем "оказать влияние" — это не фигура речи: мы действительно прислушиваемся к замечаниям/предложениям пользователей и стараемся воплощать их в жизнь. PavelVainerman не даст соврать ;)

Sign up to leave a comment.

Articles