Тема "обедающих философов" продолжает набирает плюсики в разных соцсетях, что означает необходимость выполнить свое обещание и представить решение на базе акторов с описанием. Над чем, собственно, сейчас и работаю.
Что пока удивило больше всего. Про саму задачу "обедающих философов" я знаю уже лет 25, если не больше. Даже помню, кто из преподавателей в нашем универе нам про нее на лекции впервые рассказывал. И помню, что за это время раза два мне приходилось ее реализовывать в, так скажем, иллюстративном варианте. Т.е. не находить оптимальное решение, а просто делать реализацию, которая лишена хотя бы проблемы дедлоков. А вот решать ее всерьез, чтобы устранить и дедлоки и голодания, да еще в строгом соответствии с исходной формулировкой... Вот этого не приходилось делать.
Сейчас по ходу написания реализации, которая использует арбитра и очередь "обиженных" философов (т.е. философов, которым вилка не досталась и они не смогли поесть), столкнулся с любопытным и изначально не очевидным для меня моментом.
В исходной статье, которая стала толчком для всей этой истории, реализация с арбитром и очередью называется WaiterFair (исходники этой реализации здесь). Хотя в этой реализации есть ошибка и проверяется там наличие только соседа справа.
Итак, в чем суть этой очереди и почему там нельзя проверять наличие обоих соседей?
Очередь нужна для того, чтобы предотвратить голодание философов. Допустим, у нас есть медлительный философ "A", у которого два гораздо более шустрых соседа по столу: "P" и "D". Когда "A" пытается поесть, то обнаруживается, что он либо не может взять левую вилку, т.к. она сейчас занята "P". Или не может взять правую вилку, т.к. она занята "D". После неудачной попытки "A" отправляется думать, в надежде, что "P" и "D" закончат есть и у него возникнет возможность взять обе вилки. "P" и "D" заканчивают рано или поздно, но на беду "A" кто-то из них вновь оказывается за столом быстрее "A".
Чтобы дать шанс "A" поесть и вводится очередь "обиженных" философов. Если "A" не смог взять обе вилки, то "A" вносится в эту очередь. И далее "P" и "D" не могут приступить к еде, пока "A" находится в очереди. Вместо того, чтобы разрешить "P" и "D" захватывать свободные вилки пока "A" нет за столом, мы отправляем самих "P" и "D" в очередь.
В коде это реализуется так, что когда мы решаем, можно ли философу с номером N сесть за стол, мы проверяем очередь "обиженных" философов. Если в этой очереди перед N нет его соседей (т.е. философов с номерами (N-1) и (N+1)), то N можно разрешить сесть за стол и взять свободные вилки. Если же перед N в очереди есть (N-1) или (N+1), то философу N нужно подождать, пока не будет удовлетворен голод его соседей. При этом, соседи, удовлетворив свой голод, не смогут сесть за стол повторно, пока не поест N.
Причем в очередь имеет смысл заглядывать только если обе вилки для N свободны. Т.е. проверили вилки, увидели, что они свободны, далее проверяем, а не помещаем ли мы кому-то, кто ждет дольше нас. Если же хотя бы одна вилка занята, то смысла смотреть в очередь нет, можно N сразу ставить в очередь (если там его еще нет, конечно).
Так вот, неожиданно для себя обнаружил, что если искать в очереди и соседа слева, и соседа справа, то качество обслуживания резко падает и все философы начинают голодать подолгу.
К сожалению, на словах это объяснить гораздо сложнее, чем осознать глядя на результаты тестового прогона. Вот, например, картинка, которая получается, если в очереди искать и (N-1), и (N+1):
Socrates: _______L______L____L_____L_______L____L_______L_____L_____LREEEEEEE_______L_____LREEEE
Plato: _______L____L_______L____L_____L____L_______L_______L____L_______L____LREEEE____L____
Aristotle: ____LREEEEE_______L_______L______L_______L____L____L____L____L_______L_____LREEEEE_
Descartes: ____L_____LREEEE________L____L_______L_____L_______L_____L____L_______L____L____L___
Spinoza: _____L_____L_____LREEEEE____L_____L_____L____L______L_____L_____L______L______L____L_
Kant: _____LREEEEEE____L______L_____LREEEEE____L______L_______L_____L____L______L_____L_____
Schopenhauer: ______L_______L_____LREEEEEE______L______L____LREEEEEEE____L_______L____L______L____L_
Nietzsche: ______LREEEEEEE_____L______L______LREEEEEEE____L____L______LREEEEE____L______L______L_
Wittgenstein: ______L_______L_____LREEEEEE______L_______L____LREEEE______L_____L____LREEEEEE______L_
Heidegger: ______L_______L_____L______L______LREEEEEEE____L____L______LREEEEE____L______L______LRE
Sartre: ______L_______L_____L______L______L_______L____LREEEE______L_____L____LREEEEEE______L_
Здесь подчеркиванием обозначается то, что философ думает. Буквой "E" обозначается то, что философ ест. Буква "L" -- это попытка захватить вилку слева, буква "R" -- попытка захватить вилку справа. Соответственно, последовательность "_LRE" означает, что философ подумал, затем взял вилку слева, потом взял вилку справа, потом стал есть. А последовательность "_L_" означает, что философ после раздумий попытался взять вилку слева, у него не получилось и он задумался вновь.
Так вот здесь видно, что "Ницше" успел схватить вилку слева и вилку справа. Это не позволило взять вилку слева "Витгенштейну". Т.о. в очереди оказался "Витгенштейн". Когда за вилками пришел "Хайдиггер", то он увидел две свободные вилки, заглянул в очередь и обнаружил там "Витгенштейна", своего соседа слева. Следовательно, "Хайдиггеру" брать вилки нельзя, т.к. он помешает "Витгенштейну". Поэтому в очередь отправился и "Хайдиггер". А следом за "Хайдиггером" туда же отправился и "Сатр", а потом и "Сократ". А следом и "Платон".
И фокус здесь в том, что "Сократ", который вообще не конкурирует с "Витгенштейном" за вилки, тем не менее, оказался в зависимости от того, когда сможет поесть "Витгеншетейн". Ведь пока не поест "Витгенштейн", не поест "Хайдиггер", следовательно, не поест "Сатр", а "Сократ" не может поесть перед "Сатром", т.к. "Сатр" сделал первую попытку поесть раньше.
По поводу самих статей. Пока план такой: сделать реализации задачи на базе акторов, а так же на базе CSP-шных каналов. Затем описать эти реализации в паре блог-постов на английском, дабы ссылки на эти посты можно было разместить на англоязычных ресурсах. А затем уже пойдет большая статья на русском языке на Хабре. С учетом объема предстоящей работы первых блог-постов можно ожидать не раньше начала следующей недели.
Комментариев нет:
Отправить комментарий