Проблема обедающих философов
Жизнь философа состоит из чередующихся периодов поглощения пищи и размышлений. (Разумеется, это абстракция, даже применительно к философам, но остальные процессы жизнедеятельности для нашей задачи несущественны.) Когда философ голоден, он пытается получить две вилки, левую и правую, в любом порядке. Если ему удается завладеть двумя вилками, он некоторое время ест, затем кладет вилки обратно и продолжает размышления.
Вопрос состоит в следующем: можно ли написать алгоритм, который моделирует эти действия для каждого философа и никогда не оказывается заблокированным? (Кое-кто считает, что требование наличия двух вилок выглядит несколько искусственно. Возможно, нам следует заменить итальянскую пищу блюдами китайской кухни: спагетти — рисом, а вилки — палочками.)В листинге 2.9 представлено очевидное решение проблемы. Процедура take_ fork ждет, пока указанная вилка не освободится, и берет ее. К сожалению, это решение неверно — представьте себе, что все пять философов возьмут одновременно свои левые вилки. Каждый останется без правой вилки, то есть будет иметь место взаимная блокировка.
Листинг 2.9. Неверное решение проблемы обедающих философов
#define N 5 /* Количество философов */
void philosospher(int i) /* i — номер философа, от 0 до 4 */
/* Философ размышляет */
/* Берет левую вилку */
/* Берет правую вилку */
/* Спагети, ням-ням */
/* Кладет на стол левую вилку */ /* Кладет на стол правую вилку */
}
Можно изменить программу так, чтобы после получения левой вилки проверялась доступность правой.
Если правая вилка недоступна, философ кладет левую обратно, ждет некоторое время и повторяет весь процесс. Этот подход также не будет работать, хотя и по другой причине. Если не повезет, все пять философов могут начать процесс одновременно, взять левую вилку, обнаружить отсутствие правой, положить левую обратно на стол, одновременно взять левую вилку, и так до бесконечности. Ситуация, в которой все программы продолжают работать сколь угодно долго, но не могут добиться хоть какого-то прогресса, называется зависанием (starvation).Вы можете подумать: «Если философы будут размышлять в течение некоторого случайно выбранного промежутка времени после неудачной попытки взять правую вилку, вероятность того, что все процессы будут продолжать топтаться на месте хотя бы в течение часа, невелика». Это правильно, и для большинства приложений повторение попытки спустя некоторое время снимает проблему. Например, в локальной сети Ethernet в ситуации, когда два компьютера посылают пакеты одновременно, каждый должен подождать случайно заданное время и повторить попытку — на практике это решение хорошо работает. Тем не менее в некоторых приложениях предпочтительным является другое решение, работающее всегда и не зависящее от случайных чисел (например, в приложении, предназначенном для обеспечения безопасности на атомных электростанциях).
Листинг 2.9 можно улучшить, исключив взаимные блокировки и зависания процессов; для этого достаточно защитить пять команд, следующих за запросом think, бинарным семафором. Тогда философ должен будет выполнить операцию down для переменной mutex прежде, чем тянуться к вилкам. А после возврата вилок на место ему следует выполнить для переменной mutex операцию up. С теоретической точки зрения решение вполне подходит. С позиций практики возникают проблемы эффективности: в каждый момент времени может есть спагетти только один философ. Но вилок пять, поэтому логичней было бы разрешить есть в каждый момент времени двум философам.
Решение, представленное в листинге 2.10, исключает взаимные блокировки и позволяет реализовать максимально возможный параллелизм для любого числа философов.
Здесь используется массив state для отслеживания душевного состояния каждого философа: он либо ест, либо размышляет, либо голодает (пытаясь получить вилки). Философ может начать есть, только если ни один из его соседей не ест. Соседи философа i определяются макросами LEFT и RIGHT (то есть если i = 2, то LEFT = 1 и RIGHT = 3).В программе используется массив семафоров, по одному на философа, чтобы блокировать голодных философов, если их вилки заняты. Обратите внимание, что каждый процесс запускает процедуру philosopher в качестве своей основной программы, но остальные процедуры take_forks, put_forks и test являются обычными процедурами, а не отдельными процессами.
Листинг 2.10. Решение проблемы обедающих философов |
2.3.1.
Еще по теме Проблема обедающих философов:
- ШИШКА См. статью ОТЕК, ШИШКОВИДНАЯ ЖЕЛЕЗА (ПРОБЛЕМЫ) См. ЭПИФИЗ (ПРОБЛЕМЫ).
- «Проблема» в том виде, в каком мы ее себе представляем, редко оказывается настоящей проблемой
- БОЛЬШОЙ ПАЛЕЦ (ПРОБЛЕМЫ) См. статью ПАЛЬЦЫ (ПРОБЛЕМЫ).
- Политическая философия в Италии
- Прикладная философия
- ПСИХОЛОГИЯ И ФИЛОСОФИЯ
- Философия «долженствования»
- Философия космизма
- КРОВООБРАЩЕНИЕ (ПРОБЛЕМЫ) См. статью АРТЕРИИ (ПРОБЛЕМЫ).
- Философы
- Философия
- ЕСТЬ ЛИ ФИЛОСОФИЯ У НОВОСТЕЙ?
- СОЗДАЕМ ФИЛОСОФИЮ ВМЕСТЕ