Войти
проблема курильщиков сигарет - это проблема параллелизма в информатике, первоначально описанная в 1971 году Сухасом Патилом.
Предположим, что для производства и курения сигареты требуются три ингредиента: табак, бумага и спички. За столом сидят трое курильщиков, у каждого из которых есть бесконечный запас одного из трех ингредиентов: у одного курильщика бесконечный запас табака, у другого - бумага, а у третьего - спички.
Существует также агент для некурящих, который позволяет курильщикам делать свои сигареты произвольным (недетерминированным ) выбором двух предметов для размещения на столе. Курильщик, у которого есть третий запас, должен убрать два предмета со стола и использовать их (вместе со своим запасом), чтобы сделать сигарету, которую он выкурит некоторое время. Как только курильщик выкурит свою сигарету, агент кладет на стол два новых случайных предмета. Этот процесс продолжается вечно.
Три семафора используются для представления элементов в таблице; агент увеличивает соответствующий семафор, чтобы сигнализировать, что элемент был помещен в таблицу, а курильщики уменьшают семафор при удалении элементов. Кроме того, у каждого курильщика есть связанный семафор, который они используют, чтобы сигнализировать агенту, что конкретный курильщик бросил курить; у агента есть процесс, который ожидает семафора каждого курильщика, чтобы сообщить агенту, что он может разместить новые элементы на столе.
Простая реализация псевдокода курильщика, у которого есть запас табака, может выглядеть следующим образом:
def табак_smoker (): repeat: paper.wait () matches.wait () smoke ()bacco_smoker_done.signal ()
Однако это может привести к тупиковой ситуации; если агент кладет бумагу и табак на стол, курильщик с табаком может удалить бумагу, а курильщик со спичками может взять табак, в результате чего оба не смогут сделать свою сигарету. Решение состоит в том, чтобы определить дополнительные процессы и семафоры, предотвращающие взаимоблокировку, без изменения агента.
Патил наложил следующие ограничения на проблему курильщиков сигарет:
Патил использовал доказательство в терминах сетей Петри, чтобы заявить, что решение проблемы курильщиков сигарет с использованием примитивов семафоров Эдсгера Дейкстры невозможно, и предположил, что более нужен мощный примитив. Однако Дэвид Парнас продемонстрировал, что доказательство Патил неадекватно, если используются массивы семафоров, предложив решение, которое использует вспомогательные процессы, которые выполняют арифметические действия, чтобы сигнализировать соответствующему курильщику о необходимости продолжить.
Согласно Аллен Б. Дауни, первое ограничение имеет смысл, потому что, если агент представляет операционную систему, было бы неразумно или невозможно изменять его каждый раз, когда появлялось новое приложение. Однако Парнас утверждает, что второе ограничение неоправданно:
Ограничения, о которых сообщает Патил, являются ограничениями его примитивов, но не ограничениями примитивов, описанных Дейкстрой. … Однако важно, чтобы такое исследование [примитивов Дейкстры] не исследовало силу этих примитивов при искусственных ограничениях. Под искусственными мы понимаем ограничения, которые не могут быть оправданы практическими соображениями. По мнению автора, ограничения, запрещающие условные выражения или массивы семафоров, являются искусственными.
