WikiSort.ru - Программирование

Задача о курильщиках (англ. Cigarette smokers problem) — проблема синхронизации в информатике, первоначально описанная в 1971 году Сухас С. Патилом^[1].

Ситуация

Изначально есть три заядлых курильщика, сидящих за столом. Каждому из них доступно бесконечное количество одного из трёх компонентов: у одного курильщика — табака, у второго — бумаги, у третьего — спичек. Для того чтобы делать и курить сигары, необходимы все три компонента.

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

Курильщики, по условию проблемы, честные: они не прячут компоненты, выданные барменом, — они лишь скручивают сигарету тогда, когда докурят предыдущую. Если бармен кладёт, например, табак и бумагу на стол, пока поставщик спичек курит, то табак и бумага останутся нетронутыми на столе, пока курильщик со спичками не докурит сигарету и только затем не возьмёт табак и бумагу.

Задача

Согласно доводу Патила, задача иллюстрирует ограниченность семафоров Дейкстры, так как обеспечить бесконечное продолжение процесса при соблюдении следующих условий невозможно:

1. алгоритм решения нельзя модифицировать;
2. в решении нельзя использовать условные выражения и массивы семафоров.

По мнению критиков работы Патила, второе ограничение является чрезмерным и делает невозможным решение любой нетривиальной задачи.

Решение

Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.

Если отбросить второе условие, задачу можно решить применением одноместных семафоров (мьютексов).

Данная задача при соблюдении условий решается на многопроцессорных системах с использованием параллельного программирования^{[источник не указан 1084 дня]}.

Примечания

Литература

• Современные операционные системы (2-е издание), Эндрю Таненбаум (ISBN 978-5-498-07306-4)
• The Little Book of Semaphores, by Allen B. Downey
• On a solution to the cigarette smokers' problem without conditional statements, by David Parnas (англ.)русск., Communications of the ACM, 18:181-183, March 1975

См. также

• Взаимная блокировка
• Проблема обедающих философов
• Проблема потребителя
• Проблема читателей-писателей
• Проблема спящего парикмахера

Ссылки

• ThreadMentor: The Cigarette Smokers Problem
• R.H. Campbell and P.E. Lauer A spectrum of solutions to the Cigarette Smokers Problem (неопр.). 40 years of Computing at Newcastle (1974). Проверено 8 апреля 2012. Архивировано 16 мая 2012 года.

Это заготовка статьи о программировании. Вы можете помочь проекту, дополнив её.