Проблема курильщиков сигарет

Проблема курильщиков сигарет - это проблема параллелизма в компьютерных науках , впервые описанная в 1971 году Сухасом Патилом .

Описание проблемы [ править ]

Предположим, что для изготовления и курения сигареты требуются три ингредиента: табак, бумага и спички. За столом сидят трое курильщиков, у каждого из которых бесконечный запас одного из трех ингредиентов: у одного курильщика бесконечный запас табака, у другого - бумага, а у третьего - спички.

Существует также агент для некурящих, который позволяет курильщикам делать свои сигареты, произвольно ( недетерминированно ) выбирая два предмета для хранения на столе. Курильщик, у которого есть третий запас, должен убрать два предмета со стола и использовать их (вместе со своим запасом), чтобы сделать сигарету, которую он выкурит некоторое время. После того, как курильщик закурил, агент кладет на стол два новых случайных предмета. Этот процесс продолжается вечно.

Для представления элементов в таблице используются три семафора ; агент увеличивает соответствующий семафор, чтобы сигнализировать, что элемент был помещен в таблицу, и курильщики уменьшают семафор при удалении элементов. Кроме того, у каждого курильщика есть связанный семафор, который они используют, чтобы сигнализировать агенту, что данный курильщик бросил курить; у агента есть процесс, который ожидает семафора каждого курильщика, чтобы сообщить агенту, что он может разместить новые элементы на столе.

Простая реализация псевдокода курильщика, у которого есть запас табака, может выглядеть следующим образом:

def  табак_smoker ():  повторить :  бумага . wait ()  соответствует . ждать ()  дым ()  табак_smoker_done . сигнал ()

Однако это может привести к тупиковой ситуации; если агент кладет бумагу и табак на стол, курильщик с табаком может удалить бумагу, а курильщик со спичками может взять табак, в результате чего оба не смогут сделать свою сигарету. Решение состоит в том, чтобы определить дополнительные процессы и семафоры, предотвращающие взаимоблокировку, без изменения агента.

Аргумент [ править ]

Патил поставила следующие ограничения на проблему курильщиков сигарет:

1. Код агента не подлежит изменению.
2. В решении не разрешено использовать условные операторы.

Патил использовал доказательство в терминах сетей Петри, чтобы заявить, что решение проблемы курильщиков сигарет с помощью семафорных примитивов Эдсгера Дейкстры невозможно, и предположить, что необходим более мощный примитив. ^[1] Однако Дэвид Парнас продемонстрировал, что доказательство Патил неадекватно, если используются массивы семафоров, предложив решение, в котором используются вспомогательные процессы, выполняющие арифметические действия, чтобы подавать сигнал соответствующему курильщику о необходимости продолжить. ^[2]

По словам Аллена Б. Дауни , первое ограничение имеет смысл, потому что, если агент представляет операционную систему , было бы неразумно или невозможно изменять его каждый раз, когда появлялось новое приложение. ^[3] Однако Парнас утверждает, что второе ограничение неоправданно:

Ограничения, о которых сообщает Патил, являются ограничениями его примитивов, но не ограничениями примитивов, описанных Дейкстрой. … Однако важно, чтобы такое исследование [примитивов Дейкстры] не исследовало силу этих примитивов при искусственных ограничениях. Под искусственными мы понимаем ограничения, которые не могут быть оправданы практическими соображениями. По мнению автора, ограничения, запрещающие использование условных операторов или массивов семафоров, являются искусственными. ^[2]

Ссылки [ править ]