Задача Эдсгера Дейкстры о философах – великая задача великого программиста. Уж сколько лет, а она актуальна. Решая ее, прикасаешься к этому величию. И вот, перефразируя известное, «давно не было такого и вот опять», можно познакомиться с ее «новым прочтением» на Хабре[1].
Ну, как новое?… Но она стала тем триггером, который подвигнул меня к очередной попытке ее решения. Тем более, что с момента знакомства с философами пролетела уйма лет, а в багаже - опыт применения автоматной модели и значительно усовершенствованная среда их реализации.
Познакомился с проблемой обедающих философов – Dinning Philosopher Problem (DPP), я более двадцати лет тому назад (про DPP см. [2]). Результатом стала статья, в которой философы выполняли поставленную задачу, как минимум, не хуже, чем классические алгоритмы сортировок[3]. Позднее был сделан доклад на конференции по параллельным вычислениям в Саратове, где на суд научной общественности была предъявлена модель автоматных параллельных вычислений и пример ее приложения - задача Дейкстры[4].
Замечание 1. В рамках обсуждения статьи на Хабре было проигнорировано предложение поручить сортировку философам. Зря, конечно, т.к. надо же как-то убедиться, что предлагаемое решение работает хотя бы в первом приближении. К примеру, тот же DeepSeek, моментально выдавший свое решение DPP, так и не смог заставить их сортировать.
Не знаю, считается ли данная задача решенной, но то, с чем я знаком, по большей части беглое рассмотрение проблем, которые она отражает. У задачи есть теория, которая представлена монографией Хоара[5], или моделями сетей Петри у Питерсона[6] и В.Е. Котова[7] или другими подобными публикациям. Но, повторюсь, все это по большей части достаточно краткий анализ свойств модели и/или даже конкретного решения. Статья на Хабре из этой же серии. Все это ни как не окончательное решение описываемых ею проблем параллелизма. Правда, может, [авторами] вопрос так и не ставился, но все же ответ на него весьма желательно иметь.
Сейчас меня не устраивает и мое давнее решение (см. также [8]). А поскольку в моих руках имеется значительно усовершенствованные за прошедшее время средства, формальные – автоматная параллельная модель и инструментальные – среда ВКПа, то еще одна попытка подступиться к ее решению не представляется такой уж бессмысленной. А тут еще такой «мотивационный случай» – статья на Хабре!
О моем самом свежем решении проблем обедающих философов и пойдет далее речь.
Модель «философа на вилке»
Немного повозившись (больше времени ушло на адаптацию давнего решения к ВКПа), удалось создать более простую модель, которая показана на рис. 1. В соответствии с классикой она состоит из моделей философа и вилки. Реализация на С++ в ВКПа и последующее тестирование подтвердили ее правильность. Мы ее подробно рассматривать не будем, а перейдем к более простой, но эквивалентной ей однокомпонентной модели.
Такая модель была создана экспериментальным путем. Для этого в пошаговом режиме работы среды ВКПа отслеживались текущие состояния двухкомпонентной модели, которым ставились в соответствие состояния однокомпонентной модели. По ходу были определены предикаты и действия на переходах между ними. Заметим, что они при этом остались неизменными, т.к. формально мы лишь заменили управление программы.
Говоря другими словами, мы нашли композицию автоматов, которая находится путем операции умножения автоматов. Мы упростили себе задачу подобно тому, как калькулятор упрощает операцию умножения чисел. Здесь таким калькулятором стала среда ВКПа. Хотя делать подобные вещи нужно формальным путем или, действительно, на специализированном калькуляторе, а не «на глазок».
Созданный однокомпонентный автомат показан на рис. 2. Именно эту модель далее мы будем называть «философ на вилке». Имена состояний модели составлены из имен состояний исходной модели, когда, например, состоянию с именем «wf» соответствуют состояния компонентных автоматов «w» и «f» (см. рис. 1).
От размышлений к еде
Размышлениями и разговорами сыт не будешь. Как ни крути, а есть когда-то да захочется. Чтобы понять когда, рассмотрим подробнее предикаты и действия модели. Предикаты x2 и x3 принимают истинное значение, если философы слева и справа находятся соответственно в состояниях «wo» и «eo» (напомним, что соседи – это такие же автоматы). В состояние «eo» автомат попадает, когда философ желает приступить к еде и его вилка не занята. Так он фиксирует свою вилку. В состоянии «wo» философ находится, когда размышляет. Вилка в этот момент ему не нужна, и если его сосед слева в какой-то момент решит перекусить, то переходом в это состояние философ разрешает ему ее взять.
Рассмотрим поведение философа в состоянии «eo». Здесь философ хочет кушать, но вилка соседа справа может быть занята. Чтобы ожидание не перешло в голодание, нормальный философ немного подождет, например, посчитав число тактов «голодания». А когда они превысят заданное число, он добровольно откажется от еды, возвратившись в состояние «размышления» - «wf». А тут ему, действительно, будет, о чем подумать! Голод, что ни говори, не тетка!
Цикл в состоянии «eo» исключает ситуацию тупика. Дополнительно при завершении этого цикла философ в действии y4 устанавливает новое максимальное значение цикла ожидания. Так мы исключаем другую тупиковую ситуацию – коллективного голодания, т.е. синхронного попадания множества философов в состояние голода. В этом случае, когда они в следующий момент вдруг опять одновременно попрутся есть, то откажутся от еды уже в разное время. Тем самым, их поведение разнообразится и подобная ситуация в последующем не возникнет.
Замечание 2. Может показаться, что «смерть от голода» грозит философу и в состоянии «wo». Например, сосед справа застрянет в состоянии «eo» (обжора!?). Т.е., другими словами, как быть с викой, которую сосед не возвращает? Однако здесь такого быть не может. Философ справа переходит в «eo», имея свою вилку, и ему нужна только вилка соседа. А тот ее даст обязательно, перейдя в состоянии «wo». Это выведет соседа справа из состояния «eo», что в свою очередь переведет философа в состояние «wf». И «вилки целы и философы сыты»!
Теперь рассмотрим сортировку данных (процесс еды). На рис. 3 показан момент запуска действия y1, сортирующего вилки. Условием его запуска является нахождение текущего автомата в состоянии «eo», а соседа справа - в «wo». В этот момент вилки в наличии и тут «промедление смерти подобно» - срабатывает переход, запуская действие y1!
В процессе тестирования, если сортировка вилок выполняется, фон диалога философа изменяется на короткое время на зеленый цвет, если же так уж случилось, что они отсортированы – то желтым, а в режиме голодания - синим (см. Gif 1).
Стратегии кормления философа
Мы не рассмотрели предикат x6, который реализует различные стратегии моментов допуска философа к тарелке. Их можно разделить на управление извне и изнутри. Мы решили довериться философам: пусть они сами решают, когда приступать к еде. В другой ситуации пришлось бы вводить что-то типа слуги или мажордома, которые управляли бы доступом к столу.
Были созданы три варианта, когда предикат x6 принимает истинное значение. В первом случае философ приступает к еде, когда сосед справа размышляет. Во втором он приступает к еде, когда его номер совпадает со случайным числом. Это не исключает, что одновременно захотят кушать соседи, но мы на это пошли осознанно (посмотрим, как они из этого выкрутятся). Третья стратегия - интеллектуальная. Философ приступает к еде, когда его сосед справа размышляет и требуется сортировка вилок.
Результаты тестирования на наборе чисел 1, 5, 4, 16, 66 мы свели в таблицу (табл. 1). Дискретное время автоматного пространства (автоматной сети) в котором находились философы – 10 мсек. Можно видеть, что дискретное время выдерживает достаточно строго. Его можно было бы вычислить, поделив время сортировки на число шагов. Однако, если бы мы задали дискретное время 1 мсек, то это соответствие было бы нарушено. Например, при тестировании 1-й вариант при количестве шагов – 307 затратил на сортировку 0.421 сек.
Номер варианта | Время (сек) | шагов | Пересылок |
Right | 3.140 | 313 | 9 |
rand | 0.410 | 40 | 9 |
sort | 0.102 | 9 | 3 |
Табл. 1. Тест философов (дискретное время – 10 мсек)
То, что время разное от запуска к запуску, зависит от множества факторов - работы приложения и среды, в которой тест работает. Очень большое влияние на скорость и его стабильность оказывает графика и диалоги. Если их закрыть, то время даже при 1 мсек будет соответствовать числу шагов. В эксперименте для 301 шага получилось 0.301 сек. Время сортировки можно еще уменьшить, выбрав асинхронный режим работы автоматного пространства. В этом случае время работы стало меньше 0.1 сек, т.е. ускорилось еще в три раза.
Но скорость сортировки станет совсем фантастической, если реализовать модель философов вне среды ВКПа. Как проверено, на том же массиве данных она будет в пределах 0.001 сек. При этом, правда, придется пожертвовать возможностями визуального проектирования автоматов и моделью параллельных автоматных вычислений. Оно вам надо? Мне – нет. Но е��ли потребуется, то выход, как вы понимаете, есть. Только я бы в таком случае разработку делал (и делаю) в ВКПа, а саму реализацию – по максимально быстрому варианту. Например, разработка приложений для микроконтроллеров, которые достаточно ограничены, часто идет именно по такому сценарию. Благо, что он уже проработан[9].
Философы на конвейере
Отталкиваясь от прошлого опыта, не грех опробовать другие варианты алгоритмов для философов. Предположим, это будет работа на конвейере. В таком случае они не гуляют, а сидят на рабочих местах и приступают к еде/сортировке по очереди. В этом случае не будет конфликтов с ресурсами/вилками, а работа будет выполняться предположительно быстрее. По сути, так мы реализуем четно-нечетной параллельной сортировки.
Модель философа на конвейере показана на рис. 4.
Поневоле вызывает вопросы довольно «тупая» поочередная работа объектов. Сделаем поведение работника более адекватным, запуская сортировку (см. на графе действия y3 и y4) только тогда, когда это необходимо, а в остальные моменты пусть философ отдыхает (хотя и изменяет свое текущее состояние). Для этого дополним автомат все тем же предикатом x6, который будет проверять необходимость сортировки данных. Измененная модель показана на рис. 5.
Что это нам дает? Во-первых, выполняются только необходимые действия, а потому нагрузка на процессор меньше. Он используется еще эффективнее, когда отключена визуализация работы, которая тормозит программу буквально в разы. Проверим это, создав такую же таблицу, как и выше для обычных философов.
Что мы видим? Первый вариант выполняет сортировку за 5 шагов, делая три пересылки (сортировки) данных и девять «пустых действий». Последние – это действия на переходах между «P1» и «P2», которые не выполняют полезных действий. Второй вариант тратит много больше шагов – 62, пересылок данных - 9 и 19 пустых действий. Но самый эффективный - «умный». Здесь меньше всего шагов, всего три пересылки данных и нет «пустых действий». Потому-то и время работы у него меньше всех. А если мы закроем диалоги и графику, то время упадет до 0.02 сек. Это медленнее всего в два раза самого быстрого варианта философов (без ВКПа).
Номер варианта | Время (сек) | шагов | пересылок | пустых действий |
Right | 0.060 | 5 | 3 | 9 |
Rand | 0.381 | 37 | 9 | 7 |
Sort | 0.052 | 3 | 3 | 0 |
Табл. 2. Тест конвейера (дискретное время – 10 мс)
Почему автоматы, а не потоки?
А почему не потоки? Есть ли доказательства, что без потоков параллельное программирование невозможно? Мне они не попадались. Но есть практика тотального многопоточного программирования, убеждающая многих, что без многопоточности - ни куда. И что будет думать простой программист, которого «с пеленок» закармливают потоками, мьютексами, семафорами, гонками, тупиками и еще много-много чем? И пусть говорят, что многопоточность – это сложно и не очень хорошо и если вас не приставили к стенке, то лучше ее избегать. Но других-то вариантов не предлагают?! Бывает, конечно, что-то и предложат, но это «что-то» легко тонет в болоте многопоточности.
Полная безысходность? Возможно. Но кому-то это даж�� выгодно. Попробуйте разобраться в том, что другим понять не под силу? Это, как о квантовых компьютерах. Они, вроде, есть, их иногда даже демонстрируют, но их смысл и работу толком объяснить не могут. Но, ведь, легкой жизни в параллельном программировании никто не обещал. Не так ли?
С другой стороны, есть сонм научной литературы, где параллелизм существует без многопоточности. Возьмем тех же упомянутых - Хоара, Питерсона или Котова. Но тут другая проблема. Каким боком «прилепить» подобную теорию к практике? Много ли вы знаете тех, кто использует сети Петри? Что-то слабо в это верится. Точнее не верится совсем. Многопоточность, как тараканы, проникла во все языки программирования, а вот о нативной поддержке сетей Петри я что-то не слыхивал. Я точно знаю, что, например, в стандарте С++ этого нет. А вот потоки есть!
Но есть технология программирования, которая легко обходится без многопоточности, а самое главное без ее глубинных артефактов. Она разрешает естественным образом проблемы гонок и тупиков. Выше вы с ней познакомились. А вы о ней не знали? Ну, конечно, откуда, если о ней не расскажут ни в школе, ни в институте, ни даже в научных журналах или на конференциях (разве только здесь на Хабре)? А если и расскажут, то только для того, чтобы сообщить насколько потоки лучше? Соврут, конечно, но кто в этом потом покается?
Тем не менее, «какие Ваши доказательства»? Выше мы продемонстрировали возможности автоматов на примере классической параллельной задачи. Это же можно продемонстрировать и на примере любой другой. Мы же сейчас докажем, что потоки, мютексы и т.п. вещи противоречат здравому смыслу именно с формальной, научной точки зрения. Одновременно покажем, чем их можно заменить. Возможно, кто-то придерется к строгости доказательства, но только пусть сначала его опровергнет…
Будет совсем не сложно и достаточно кратко. Нужна, правда, небольшая подготовка, чтобы понять его смысл, но это уже проблемы иного рода. Мы в основу положим достаточно известные и, главное, научно доказанные факты. Подчеркнем, уже доказанные и уже известные весьма широко! Это важно. Если они вам не известны, то есть повод, чтобы этот пробел устранить.
Итак, первое. Нет алгоритма, который нельзя было бы представить в форме программы машины Тьюринга (МТ). Таким образом, поведение любой программы общем случае может быть описано МТ. Мы не погрешим, если будем считать, что программы и алгоритмы это одно и то же. Таким образом, любой программе (любой!) можно поставить в соответствие эквивалентную МТ.
Второе. Достаточно просто показать, что любой МТ можно поставить в соответствие эквивалентный конечный автомат[10]. При этом, несмотря на конечность числа состояний, их может быть любое число. Главный вывод, вместо МТ мы без потери общности можем рассматривать конечные автоматы (КА).
Третье. Из теории автоматов известно, что любой автомат можно разложить на множество параллельных автоматов, используя операцию декомпозиции автомата по операции умножения (см. алгебру автоматов [11]). Каждый компонентный автомат такого разбиения представляет отдельный параллельный процесс. При ��том, для синхронизации автоматам не нужны мьютексы, семафоры и другие подобные механизмы. В этом случае достаточно механизма доступа к состоянию автомата. А когда текущие состояния автоматов составят нужную комбинацию (она должна соответствовать тому или иному состоянию исходного однокомпонентного автомата), то это и будет моментом синхронизации поцессов. Затем определяется переход к новой комбинации текущих состояний и далее все повторяется.
Вот и все доказательство! Как Вам такое, Илон Маск?!
А какова перспектива автоматных вычислений? Не забудут ли их, как это фактически уже случилось с сетями Петри? Действительно, был период, когда автоматы задвинули на задворки истории, посчитав, что они исчерпали свои возможности. Именно с точки зрения параллелизма. Примечательно, что в это же время был наиболее активный интерес к сетям Петри. Но где теперь сети Петри, а где автоматы?
Не будем загадывать, но в настоящее время происходит расширение областей применения автоматов. Налицо буквально «автоматный ренессанс» (см. хотя бы [12]). Это достаточно очевидно и при этом их возможности далеко не исчерпаны. Мой опыт в среде ВКПа это только подтверждает.
Что есть у автоматов, но нет у потоков.
Строго говоря, у потоков нет алгоритмической модели. Есть интуитивное понятие потока и не более того. А много потоков – вот и многопоточность. Запредельный уровень фантазии. Но вот как считать и что считать – тут можно фантазировать. Программисты и фантазируют. За алгоритмическую модель взяли существующую модель блок-схем. Явно сильно не напрягались, т.к. взяли то, что лежит под ногами. Справедливости ради нужно признать, что выбора особого у них не было: все основные языки программирования и новые, и сильно старые, и совсем уж убогие стандартно реализуют именно эту модель. Тут не разгуляешься. Есть конечно другие языки – функциональные, логические… Но на мой взгляд это уже запредельный уровень фантазии.
Святое – взять то, что уже есть. И в этом есть свой плюс. Ведь, моделью вычислений потока (или в потоке?) может быть и автомат? Почему бы и нет? Например, есть асинхронные сети автоматов. Они идеологически вполне подходят, но … стоп! Давайте не будем измываться над автоматами, а вернемся к потокам.
Итак, есть потоки, а в них – блок-схемы. Заметим, реализуемые на любом языке программирования – Си, С++, Phyton, Go и далее по списку. Множество параллельных блок-схем – формальная модель многопоточности. Но есть одна большая проблема – аппаратная. Много потоков не организуешь даже при наличии большого числа ядер. Потоков, а тем более ядер, как и денег, всегда не хватает. Нужно … майнить. Тьфу, - имитировать.
Потоки моделируют программно. Для этого время от времени текущий поток прерывается, а управление, т.е. ресурс процессора, передается другому потоку. Для этого создали, а, скорее, даже использовали, систему прерываний. И так по кругу. С этого, кстати, начали во времена, когда было всего одно ядро. Боже, было ж, ведь, когда-то такое время или забыли?
Но, используя прерывания, с размаху «дали в штангу», т.к. не подумали об условиях и/или моментах порождения прерываний. Пошли по самому испытанному и простому пути – разрешили прерывать тогда, когда вздумается. Достаточно быстро выяснилось, что это не хорошо, но… дело-то сделано. И тут, не придумав кардинального решения проблемы (а, кстати, как это - кардинально?), пошли другим путем – перевели стрелки на программистов.
Программисты же в свою очередь не придумали ни чего лучшего для решения «проблемы бардака прерываний», как ввести атомарные переменные, мьютексы, семафоры и что-то там еще. В результате «бардак» чуть уменьшили, но добавились другие проблемы. Вот с этим мы и живем до сих пор, когда лучшим решением является совет - не использовать многопоточность, когда можно «не стрелять себе в ногу» (так и хочется сказать - в голову).
Не мне бы давать советы [конкурентам], но все же можно было бы заложить хотя бы атомарность в систему прерываний? Не на уровне, конечно, ассемблерных команд (их, кажется, не прерывают?), но хотя бы довести дело до уровня операторов языка программирования, а лучше сразу - функций. Спросите – как? Здесь могут быть разные варианты, но в любом случае это повысило бы надежность программирования, уменьшило бы количество проблем. Или, может, это уже сделано?
А что автоматы? Здесь (в ВКПа) атомарность доведена до уровня такта дискретного времени. В его пределах прерываний нет. Но, правда, есть нюансы. В пределах такта сначала выполняются все предикаты, а только потом все действия. А измененные значения памяти сначала фиксируются в теневой памяти и лишь после выполнения всех действий, но до начала следующего такта, становятся истинными значениями переменных. В первую очередь это актуально для выходных переменных автомата. К локальным переменным автомата такое правило может не применяться (но подробнее см. [13]).
Но даже здесь могут быть отклонения. Философы это демонстрируют. В борьбе за ресурсы «тормозить» негоже. Это демонстрирует переменная, которая разрешает философу приступать к еде. Она, хотя и внешняя, работает по принципу обычной переменной – устанавливается сразу после изменения (занятия ресурса). В ВКПа есть и такая возможность. Нарушение принципов модели? Нет, конечно. Мы здесь так делаем, чтобы упростить доступ к ресурсу. И это нормально. Принципиальность тоже имеет свои границы.
Все описанное выше – это требования вычислительной автоматной модели. Именно они обеспечивают корректность модели параллельных вычислений, делают ее простой и надежной. Вот этого у потоков нет и близко. Оттого у них такой «бардак», когда единственно надежный совет – не использовать потоки. Хотя что-то из качеств автоматной модели можно было бы перенести и в потоки, чтобы сделать их хотя бы предсказуемыми. Но о таких попытках слышать не довелось.
Выводы
Представленное в работе решение задачи Дейкстры не базируется на потоках. В нем нет ни мьютексов, ни семафоров. Сама модель философа проста, наглядна и у нее есть теория. Они не голодают, не попадают в тупики, могут сколь угодно гулять и свободно выбирать время, чтобы сытно поесть. Что еще надо для спокойной и счастливой жизни? Вот вам и практические доказательства параллелизма вне многопоточности.
Задача о философах демонстрирует проблемы доступа к общему ресурсу. Созданное решение показывает, что это можно сделать весьма просто – используя, с одной стороны, переменную обычного типа, управляющую доступом к ресурсу, а, с другой стороны, используя синхронизацию процессов на базе состояний, чтобы корректно запустить операцию доступа к ресурсу.
Безусловно, сортировка не тест, которому можно доверять на все «сто», но… DepSeek, выложивший моментально свое решение, когда я попросил на его базе создать сортировку, до сих пор эту проблему так и не решил. Хотя, если честно, я и не сильно настаивал. Почему? - это отдельный разговор и пример того, что создать код – это одно, а сделать его рабочим – другое. Я же просто озвучиваю то, что получилось из моих бесед с ИИ.
Часто спрашивают про эффективность автоматов в сравнении с потоками. Алгоритм параллельной четно-нечетной сортировки, созданный DeepSeek, на том же наборе данных затратил 0.03 сек и более. Его автоматный аналог – философы на конвейере – 0.02 сек. Не намного, но меньше. И это в режиме интерпретации автоматов и с диалогами. Но есть, ведь, еще и самое шустрое решение!
Литература
1. Обедающие философы на Go: как не умереть от взаимной блокировки и голодания. https://habr.com/ru/articles/951224/
2. Application Note Dining Philosophers Problem (DPP) Example. https://www.state-machine.com/doc/AN_DPP.pdf
3. Параллельные сортировки: быстрее, проще... умнее. https://www.osp.ru/os/2004/05/184293
4. ВЫСОКОПРОИЗВОДИТЕЛЬНЫЕ ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ НА КЛАСТЕРНЫХ СИСТЕМАХ
Самара, 30 сентября – 02 октября 2004 года. https://elibrary.ru/item.asp?edn=tisrrp
5. Хоар Ч. Взаимодействующие последовательные процессы: Пер. с англ. – М.: Мир, 1989. 264 с.
6. Питерсон Дж. Теория сетей Петри и моделирование систем: Пер с англ. – М.: Мир, 1984. – 264с.
7. Элементы параллельного программирования/В.А. Вальковский, В.Е. Котов, А.Г. Марчук, Н.Н. Миренков; Под ред. В.Е. Котова. – М.: Радио и связь, 1983. – 240с.
8. Обедающие философы Дейкстры (о модели параллельных процессов). http://www.softcraft.ru/auto/ka/fil/
9. Как избежать кошмара параллелизма в IoT: автоматы вместо потоков и корутин. https://habr.com/ru/articles/937448/
10. Машина Тьюринга, как модель автоматных программ. https://habr.com/ru/articles/481998/
11. Мелихов А.Н. Ориентированные графы и конечные автоматы. – М.: Наука, 1971. – 416 с.
12. Визуальное проектирование управляющей логики фитнес-браслета. https://habr.com/ru/companies/etmc_exponenta/articles/910114/
13. Автоматное программирование: определение, модель, реализация. https://habr.com/ru/articles/682422/