Комментарии 54
this >>= st_wait_left;
Вот вы для себя вывод сделали. Уже результат. Если бы внимательно изучили код, на который сослались, может быть было бы еще лучше.
Ну и это мы еще оставим за скобками объем и читабельность кода, тут дело чисто субъективное.
Ну так это совсем другой алгоритм решения, о чем я вам и намекал. Попробуйте сделать на QP хотя бы вариант no_waiter_simple, тогда можно будет сравнить.
А если на SO-5 делать вариант с таким же алгоритмом, как в примере из QP, то кода будет сильно меньше (может не 2 раза, но в 1.5 наверняка), да и само решение будет сильно проще.
QP хорошо работает для случаев большого числа философов. Во времена постановки задачи памяти в машинах было мало, поэтому и извраты эти. В QP количество обслуживаемых философов равно длине очереди указателей на события, плюс фреймворк, стол и один философ (из опыта, всё, кроме первого пункта, нечувствительно на системах примерно в два раза толще Ардуино).
А я разве где-то сказал, что он такой же?
Я вам все время прозрачно намекал на то, что сравнивать "страшность" нужно на одинаковых решениях. У задачи обедающих философов много разных решений, но выразительность и понятность кода имеет смысл сравнивать на аналогичных.
QP хорошо работает для случаев большого числа философов.
Количество философов тут не при чем. QP изначально рассчитывался на работу в нише встраиваемых систем. Именно отсюда те извраты.
Во времена постановки задачи памяти в машинах было мало, поэтому и извраты эти.
Нет, не поэтому.
Не знаю, что Вы имели в виду под нишей встраиваимых систем. Я на QP пишу везде, где могу — и в Андроиде, и в Линуксе, и во встраиваемых системах. Если слегка отвлечься от темы и интерпретировать «нишу», как «где можно капусты накосить», то она, по моим скромным запросам, более, чем адекватная.
Вдогонку: я сейчас сижу и порчу QP на microMIPS. Получаю от этой беседы огромное удовольствие, надеюсь, что и Вы тоже.
Я не согласен, что выразительность и понятность следует сравнивать, глядя на код.
Тогда что с чем сравнивается? Написанный вручную за полчаса код с тем, что сгенерировал какой-то генератор на основании нарисованного в визуальной тулзе?
Если вы это предлагаете, то это как сравнивать теплое с мягким.
Не знаю, что Вы имели в виду под нишей встраиваимых систем.
Именно нишу встраиваемых систем и имел в виду. Там, где нужно память экономить и такты считать, а то и вообще без ОС работать. Под это QP заточена, поэтому и интерфейс у нее именно такой. Поэтому там, например, под очереди сообщений память вручную размещать нужно.
Я на QP пишу везде, где могу — и в Андроиде, и в Линуксе, и во встраиваемых системах.
Некоторые умудряются на Java системы реального времени делать. Что не означает, что Java для этого хороший выбор.
У этой задачи есть требование: философы не должны голодать, если захотят есть. Со спинлоками нет такой гарантии: не сильно удачливый философ будет все время промахиваться и пытаться взять снова и снова, но постоянно кто-то другой может мешать.
Однако можно представить себе ситуацию, когда один философ кладет вилки и тут же берет их снова.
Вот это вряд ли. Поскольку в подходе Дейкстры философ, который захотел поесть, но не смог взять вилку, никуда не уходит, он следит за появлением вилки. Как только оная появляется, он ее сразу же хватает.
тот поток, который разблокирует мьютекс и в течение того же кванта времени блокирует его снова, просто не дает ОС разбудить ожидающий этого же мьютекса поток.
Это если мьютексы без очереди ожидания.
Тогда как если мы делаем busy-waiting на CAS-ах сами, никаких гарантий у нас нет. Так что, теоретически, голодание какого-то из философов может длится долго, т.к. ситуациям «положил и сразу взял обратно» никто не препятствует.
Да, в решении Дейкстры подразумевается, что мьютексы честные, т.е. если мьютекс А захватил, затем мьютекс Б, то сначала его захватывает А, а затем Б. Стандартная реализация 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_;
};
Выводы очевидны.
Выводы очевидны.
Мне нет. Не понятно зачем этот комментарий. Не понятно, какие должны последовать выводы.
Пример кода показывает, что использование акторов сильно усложняет решение, добавляя много ненужного "шума" в достаточно простой код.
Кроме того, лично я исхожу из предположения о разумности читателей. Вряд ли кому-то в голову придет идея использовать Акторов там, где можно применить классику на семафорах. С другой стороны, можно составить впечатление о том, с чем придется иметь дело, если речь зайдет о масштабе хотя бы в сотни тысяч «вилок» и «философов».
Проблема в том, что создавать сотни тысяч рабочих потоков на одной ноде непрактично. Вместо нитей ОС нужно будет уходить в 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.
Ваше решение не пригодно за пределами демонстрационной песочницы. Оно могло бы сойти в качестве примера, от чего придётся уйти, переходя на акторы. Но и тут есть засада — примерно такая же, как в случае демонстрации рекурсии на факториале: образец слишком красив, чтобы давать представление о реальных задачах. В последних обычное линейно-процедурное построение слишком быстро превращается в тупую нечитаемую кашу. Поэтому я бы его и для сравнения не показывал — будет сбивать с толку.
Увидел рекламу сопрограмм в соседнем комментарии. Если вы «топили» за них, то есть тоже сильные сомнения. В моей текущей области (телефония) очень часто получается, что какой-то сценарий должен вестись несколькими участниками, каждый из которых играет свою роль. Организовать единого ведущего на конкретный сценарий в такой ситуации практически невозможно, или он будет работать через костыли.
Вот здесь рассмотрен пример с таймаутами и нетривиальной параллельной обработкой: https://habr.com/ru/company/yandex/blog/240525/
Для тех, кто интересуется SObjectizer-ом (вдруг таковые есть): уже идет работа над следующей "большой" версией SObjectizer-5.6, в которой будет нарушена совместимость с веткой 5.5 (которая развивалась с серьезной оглядкой на совместимость более 4 лет). Мотивация и основные цели/планы для v.5.6 описаны здесь.
А для обсуждения связанных с SO-5.6 вопросов была реанимирована старая Google-группа. Так что если кто-то хочет оказать влияние на то, как и куда развивается SObjectizer, то имеет смысл заглядывать в эту группу и оставлять свое мнение по тем или иным вопросам. Причем "оказать влияние" — это не фигура речи: мы действительно прислушиваемся к замечаниям/предложениям пользователей и стараемся воплощать их в жизнь. PavelVainerman не даст соврать ;)
«Современные» обедающие философы на C++ посредством акторов и CSP