Interested Article - Задача о курильщиках
- 2021-02-18
- 1
Задача о курильщиках ( англ. Cigarette smokers problem ) — проблема синхронизации в информатике, первоначально описанная в 1971 году .
Ситуация
Изначально есть три заядлых курильщика, сидящих за столом. Каждому из них доступно бесконечное количество одного из трёх компонентов: у одного курильщика — табака , у второго — бумаги , у третьего — спичек . Для того чтобы делать и курить сигареты, необходимы все три компонента.
Также, кроме курильщиков, есть бармен, помогающий им делать сигареты: он недетерминированно выбирает двух курильщиков, берёт у них по одному компоненту из их запасов и кладёт их на стол. Третий курильщик забирает ингредиенты со стола и использует их для изготовления сигареты, которую он курит некоторое время. В это время бармен, завидев стол пустым, снова выбирает двух курильщиков случайным образом и кладёт их компоненты на стол. Процесс повторяется бесконечно.
Курильщики, по условию проблемы, честные: они не прячут компоненты, выданные барменом, — они лишь скручивают сигарету тогда, когда докурят предыдущую. Если бармен кладёт, например, табак и бумагу на стол, пока поставщик спичек курит, то табак и бумага останутся нетронутыми на столе, пока курильщик со спичками не докурит сигарету и только затем не возьмёт табак и бумагу.
Задача
Согласно доводу Патила, задача иллюстрирует ограниченность семафоров Дейкстры, так как обеспечить бесконечное продолжение процесса при соблюдении следующих условий невозможно:
- алгоритм решения нельзя модифицировать;
- в решении нельзя использовать условные выражения и массивы семафоров .
По мнению критиков работы Патила, второе ограничение является чрезмерным и делает невозможным решение любой нетривиальной задачи.
Решение
Если отбросить второе условие, задачу можно решить применением одноместных семафоров ( мьютексов ).
Данная задача при соблюдении условий решается на многопроцессорных системах с использованием параллельного программирования [ источник не указан 2882 дня ] .
См. также
- Взаимная блокировка
- Проблема обедающих философов
- Проблема потребителя
- Проблема читателей-писателей
- Проблема спящего парикмахера
Примечания
- Suhas S. Patil. Limitations and capabilities of Dijkstra’s semaphore primitives for co-ordination among processes (англ.) // Computational Structures Group Memo 57, Project MAC. — Massachusetts Institute of Technology, Feb. 1971.
Литература
- Современные операционные системы (2-е издание) , Эндрю Таненбаум ( ISBN 978-5-498-07306-4 )
- , by Allen B. Downey
- On a solution to the cigarette smokers' problem without conditional statements , by Communications of the ACM , 18:181-183, March 1975 ,
Ссылки
- R.H. Campbell and P.E. Lauer . 40 years of Computing at Newcastle (1974). Дата обращения: 8 апреля 2012. 16 мая 2012 года.
int main()
{
printf("Hi");
return 0;
}
|
Это
заготовка статьи
о
программировании
. Помогите Википедии, дополнив её.
|
- 2021-02-18
- 1