<<
>>

Проблема обедающих философов

В 1965 году Дейкстра сформулировал и решил проблему синхронизации, названную им проблемой обедающих философов. С тех пор каждый, кто изобретал еще один новый примитив синхронизации, считал своим долгом продемонстрировать достоинства нового примитива на примере решения проблемы обедающих философов.
Задачу можно сформулировать следующим образом: пять философов сидят за круглым столом и у каждого есть тарелка со спагетти. Спагетти настолько скользкие, что каждому философу нужны две вилки, чтобы управиться с яством. Но между каждыми двумя тарелками лежит только одна вилка (рис. 2.7).

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

Вопрос состоит в следующем: можно ли написать алгоритм, который моделирует эти действия для каждого философа и никогда не оказывается заблокированным? (Кое-кто считает, что требование наличия двух вилок выглядит несколько искусственно. Возможно, нам следует заменить итальянскую пищу блюдами китайской кухни: спагетти — рисом, а вилки — палочками.)

В листинге 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.

<< | >>
Источник: Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание. 2007

Еще по теме Проблема обедающих философов:

  1. ШИШКА См. статью ОТЕК, ШИШКОВИДНАЯ ЖЕЛЕЗА (ПРОБЛЕМЫ) См. ЭПИФИЗ (ПРОБЛЕМЫ).
  2. «Проблема» в том виде, в каком мы ее себе представляем, редко оказывается настоящей проблемой
  3. БОЛЬШОЙ ПАЛЕЦ (ПРОБЛЕМЫ) См. статью ПАЛЬЦЫ (ПРОБЛЕМЫ).
  4. Политическая философия в Италии
  5. Прикладная философия
  6. ПСИХОЛОГИЯ И ФИЛОСОФИЯ
  7. Философия «долженствования»
  8. Философия космизма
  9. КРОВООБРАЩЕНИЕ (ПРОБЛЕМЫ) См. статью АРТЕРИИ (ПРОБЛЕМЫ).
  10. Философы
  11. Философия
  12. ЕСТЬ ЛИ ФИЛОСОФИЯ У НОВОСТЕЙ?
  13. СОЗДАЕМ ФИЛОСОФИЮ ВМЕСТЕ