Мертвые и живые блокировки
Описанное выше явление иногда называют проблемой голодного философа. История этого колоритного названия восходит к модели, которую использовал для демонстрации описанного этого феномена.
Некоторое количество (у Э. Дейкстры – пять) философов сидят вокруг стола, на котором стоит блюдо спагетти (вместо спагетти можно взять, например, блины). Спагетти едят двумя вилками. В нашем случае, количество вилок равно количеству философов, так что соседи за столом разделяют вилку (гигиенический аспект проблемы мы опускаем).
Каждый философ некоторый (переменный) промежуток времени размышляет, затем пытается взять лежащие рядом с ним вилки (рис. 7.3). Если ему это удается, он принимается за еду. Ест он также переменный промежуток времени, после этого откладывает вилки и вновь погружается в размышления. Проблемы возникают, когда философ не может взять одну из вилок.
Рис. 7.3. Обедающие философы
Возможны несколько вариантов разрешения происходящих при этом коллизий. Если, например, каждый из философов всегда берет ту вилку, которая свободна, и не отпускает ее, пока не насытится, мы можем получить (хотя и не обязательно получим) классическую мертвую блокировку, в которую будут включены все философы, сидящие вокруг стола (рис. 7.4). Вариант, при котором философ сначала всегда дожидается правой вилки, и лишь взяв ее, начинает дожидаться левой, только повысит вероятность образования цикла.
Рис. 7.4. Мертвая блокировка в исполнении пяти философов
Цикл можно разомкнуть, пронумеровав вилки и потребовав, чтобы каждый философ брат сначала вилку с меньшим номером, и только потом – с большим. Если вилки пронумерованы по часовой стрелке, для всех философов, кроме одного, это требование совпадает с высказанным в предыдущем абзаце – сначала брать правую вилку, и лишь потом дожидаться левой. Однако для того, кто попал между пятой и первой вилками, это правило обращается – он должен сначала дождаться левой вилки, и только потом правую. Легко продемонстрировать, что этот философ в среднем будет своих вилок дольше, чем остальные четверо.
Если же философ берет вилки тогда и только тогда, когда они доступны обе одновременно, это может привести к проблеме голодного философа-согласовав свои действия, соседи бедняги могут неограниченно долгое время оставлять его голодным (рис. 7.5).
Рис. 7.5. Голодный философ