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

Эта статья посвящена проблеме информатики. Информацию о проблемах, которые могут возникнуть у курильщиков сигарет, см. Влияние табака на здоровье.

В проблема курильщиков сигарет это параллелизм проблема в Информатика, первоначально описанный в 1971 г. Сухас Патил.

Описание проблемы

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

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

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

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

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

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

Аргумент

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

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

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

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

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

Рекомендации

  1. ^ Патил, Сухас С. (Февраль 1971 г.). Ограничения и возможности семафорных примитивов Дейкстры для координации между процессами (Технический отчет). Массачусетский технологический институт, Проект MAC, Группа вычислительных структур. Памятка 57.
  2. ^ а б Парнас, Дэвид Л. (Март 1975 г.). «О решении проблемы курильщиков сигарет (без условных формулировок)» (PDF). Коммуникации ACM. 18 (3): 181–183. Дои:10.1145/360680.360709.
  3. ^ Дауни, Аллен Б. Маленькая книга семафоров (2-е изд.). Получено 29 июн 2015.