Проблема курильщиков сигарет
 | этой статьи Начальный раздел может быть слишком коротким, чтобы адекватно суммировать ключевые моменты . ( июль 2023 г. ) |
Проблема курильщиков сигарет – это проблема параллелизма в информатике , первоначально описанная в 1971 году Сухасом Патилом . Проблему критиковали за наличие «ограничений, которые не могут быть оправданы практическими соображениями». [1]
Описание проблемы [ править ]
Проблема Патила включает в себя «весьма произвольную» [1] «Ограничение: процесс поставки ингредиентов не может быть изменен и не могут быть использованы никакие условные утверждения». [2]
Предположим, для изготовления и курения сигареты требуются три ингредиента: табак, бумага и спички. За столом сидят трое курильщиков, каждый из которых имеет бесконечный запас одного из трех ингредиентов: у одного курильщика бесконечный запас табака, у другого — бумага, у третьего — спички.
Существует также некурящий агент, который позволяет курильщикам изготавливать сигареты, произвольно ( недетерминированно ) выбирая два запаса для размещения на столе. Курильщик, имеющий третий запас, должен убрать два предмета со стола, используя их (вместе со своим запасом) для изготовления сигареты, которую он курит некоторое время. Как только курильщик докуривает сигарету, агент кладет на стол два новых случайных предмета. Этот процесс продолжается вечно.
Три семафора используются для представления элементов в таблице; агент увеличивает соответствующий семафор, чтобы сигнализировать о том, что предмет помещен на стол, а курильщики уменьшают значение семафора при удалении предметов. Кроме того, у каждого курильщика есть связанный семафор, который он использует, чтобы сигнализировать агенту о том, что конкретный курильщик закончил курить; у агента есть процесс, который ожидает семафора каждого курильщика, чтобы сообщить агенту, что он может разместить новые элементы на столе.
Простая реализация псевдокода курильщика, у которого есть запас табака, может выглядеть следующим образом:
def tobacco_smoker():
repeat:
paper.wait()
matches.wait()
smoke()
tobacco_smoker_done.signal()
Однако это может привести к тупику; если агент кладет бумагу и табак на стол, курильщик с табаком может удалить бумагу, а курильщик со спичками может взять табак, в результате чего оба не смогут зажечь сигарету. Решение состоит в том, чтобы определить дополнительные процессы и семафоры, предотвращающие взаимоблокировку, без изменения агента.
Критика [ править ]
Патил наложил следующие ограничения на проблему курильщиков:
- Код агента не подлежит изменению.
- В решении не допускается использование условных операторов.
Патил использовал доказательство в терминах сетей Петри, чтобы заявить, что решение проблемы курильщиков сигарет с помощью семафорных примитивов Эдсгера Дейкстры невозможно, и предположить, что необходим более мощный примитив. [3] [2] Однако Дэвид Парнас продемонстрировал, что доказательство Патил неадекватно, если используются массивы семафоров, предложив решение, использующее вспомогательные процессы, выполняющие арифметические действия, чтобы подать сигнал соответствующему курильщику продолжить работу. [1]
По мнению Аллена Б. Дауни , первое ограничение имеет смысл, поскольку, если агент представляет собой операционную систему , было бы неразумно или невозможно модифицировать ее каждый раз, когда появляется новое приложение. [4] Однако Парнас утверждает, что второе ограничение неоправданно:
Ограничения, о которых сообщает Патил, являются ограничениями его примитивов, но не являются ограничениями примитивов, описанных Дейкстрой. … Однако важно, чтобы такое исследование [примитивов Дейкстры] не исследовало силу этих примитивов в условиях искусственных ограничений. Под искусственными мы подразумеваем ограничения, которые не могут быть оправданы практическими соображениями. По мнению автора, ограничения, запрещающие использование условных операторов или массивов семафоров, являются искусственными. [1]
См. также [ править ]
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б с д Парнас, Дэвид Л. (март 1975 г.). «О решении проблемы курильщиков сигарет (без условных формулировок)» (PDF) . Коммуникации АКМ . 18 (3): 181–183. дои : 10.1145/360680.360709 . S2CID 24066507 .
- ^ Jump up to: Перейти обратно: а б Патил, Сухас. «Ограничения и возможности семафорных примитивов Дейкстры для координации процессов» (PDF) . Проверено 20 февраля 2022 г.
- ^ Патил, Сухас С. (февраль 1971 г.). Ограничения и возможности семафорных примитивов Дейкстры для координации процессов (технический отчет). MIT , Project MAC , Группа вычислительных структур. Памятка 57.
- ^ Дауни, Аллен Б. Маленькая книга семафоров (2-е изд.) . Проверено 29 июня 2015 г.
| Общий | |
|---|---|
| Процесс исчисления | |
| Классические задачи | |
