Искусство выжить. Простое руководство для настоящих программистов
Задача Эдсгера Дейкстры о философах – великая задача великого программиста. Уж сколько лет, а она актуальна. Решая ее, прикасаешься к этому величию. И вот, перефразируя известное, «давно не было такого и вот опять», можно познакомиться с ее «новым прочтением» на Хабре[1].
Ну, как новое?… Но она стала тем триггером, который подвигнул меня к очередной попытке ее решения. Тем более, что с момента знакомства с философами пролетела уйма лет, а в багаже - опыт применения автоматной модели и значительно усовершенствованная среда их реализации.
Познакомился с проблемой обедающих философов – Dinning Philosopher Problem (DPP), я более двадцати лет тому назад (про DPP см. [2]). Результатом стала статья, в которой философы выполняли поставленную задачу, как минимум, не хуже, чем классические алгоритмы сортировок[3]. Позднее был сделан доклад на конференции по параллельным вычислениям в Саратове, где на суд научной общественности была предъявлена модель автоматных параллельных вычислений и пример ее приложения - задача Дейкстры[4].
Замечание 1. В рамках обсуждения статьи на Хабре было проигнорировано предложение поручить сортировку философам. Зря, конечно, т.к. надо же как-то убедиться, что предлагаемое решение работает хотя бы в первом приближении. К примеру, тот же DeepSeek, моментально выдавший свое решение DPP, так и не смог заставить их сортировать.
Не знаю, считается ли данная задача решенной, но то, с чем я знаком, по большей части беглое рассмотрение проблем, которые она отражает. У задачи есть теория, которая представлена монографией Хоара[5], или моделями сетей Петри у Питерсона[6] и В.Е. Котова[7] или другими подобными публикациям. Но, повторюсь, все это по большей части достаточно краткий анализ свойств модели и/или даже конкретного решения. Статья на Хабре из этой же серии. Все это ни как не окончательное решение описываемых ею проблем параллелизма. Правда, может, [авторами] вопрос так и не ставился, но все же ответ на него весьма желательно иметь.
Читать далее