Задача обедающих философов

В 1965 году Дейкстра сформулировал, а затем решил проблему синхронизации, названную им задачей обедающих философов. С тех пор все изобретатели очередного примитива синхронизации считали своим долгом продемонстрировать его наилучшие качества, показав, насколько элегантно с его помощью решается задача обедающих философов.
Суть задачи довольно проста. Пять философов сидят за круглым столом, и у каждого из них есть тарелка спагетти. Эти спагетти настолько скользкие, что есть их можно только двумя вилками. Между каждыми двумя тарелками лежит одна вилка. Внешний вид стола показан на рис. 2.25.

Рис. 2.25. Обед на факультете философии


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

В листинге 2.13 показано самое простое решение этой задачи. Процедура 1акв_/отк ждет, пока вилка не освободится, и берет ее. К сожалению, это решение ошибочно.


Допустим, что все пять философов одновременно берут левую от себя вилку. Тогда никто из них не сможет взять правую вилку, что приведет к взаимной блокировке.


Можно без особого труда изменить программу так, чтобы после получения левой вилки программа проверяла доступность правой вилки. Если эта вилка недоступна, философ кладет на место левую вилку, ожидает какое-то время, а затем повторяет весь процесс. Это предложение также ошибочно, но уже по другой причине. При некоторой доле невезения все философы могут приступить к выполнению алгоритма одновременно и, взяв левые вилки и увидев, что правые вилки недоступны, опять одновременно положить на место левые вилки, и так до бесконечности. Подобная ситуация, при которой все программы бесконечно работают, но не могут добиться никакого прогресса, называется голоданием, или зависанием процесса. (Эта ситуация называется голоданием даже в том случае, если проблема возникает вне стен итальянского или китайского ресторана.)

Можно подумать, что стоит только заменить одинаковое для всех философов время ожидания после неудачной попытки взять правую вилку на случайное, и вероятность, что все они будут топтаться на месте хотя бы в течение часа, будет очень мала. Это правильное рассуждение, и практически для всех приложений повторная попытка через некоторое время не вызывает проблемы. К примеру, если в популярной локальной сети Ethernet два компьютера одновременно отправляют пакет данных, каждый из них выжидает случайный отрезок времени, а затем повторяет попытку. И на практике это решение неплохо работает. Но в некоторых приложениях может отдаваться предпочтение решению, которое срабатывает всегда и не может привести к отказу по причине неудачной череды случайных чисел.

Вспомним о системе управления безопасностью атомной электростанции.

В программу, показанную в листинге 2.13, можно внести улучшение, позволяющее избежать взаимной блокировки и зависания. Для этого нужно защитить пять операторов, следующих за вызовом think, двоичным семафором. Перед тем как брать вилки, философ должен выполнить в отношении переменной mutex операцию down. А после того как он положит вилки на место, он должен выполнить в отношении переменной mutex операцию up. С теоретической точки зрения это вполне достаточное решение. Но с практической — в нем не учтен вопрос производительности: в каждый момент времени может есть спагетти только один философ. А при наличии пяти вилок одновременно могут есть спагетти два философа.

Решение, представленное в листинге 2.14, не вызывает взаимной блокировки и допускает максимум параллелизма для произвольного числа философов. В нем используется массив state, в котором отслеживается, чем занимается философ: ест, размышляет или пытается поесть (пытается взять вилки). Перейти в состояние приема пищи философ может, только если в этом состоянии не находится ни один из его соседей. Соседи философа с номером i определяются макросами LEFT и RIGHT. Иными словами, если i равен 2, то LEFT равен 1, а RIGHT равен 3.

Листинг 2.14. Решение задачи обедающих философов

5 /* количество философов */

(1+1\1-1) /* номер левого соседа для 1-го философа */

(1+1) /* номер правого соседа для 1-го

философа */

0 /* философ размышляет */

1 /* философ пытается взять вилки */

2 /* философ ест спагетти */

/* Семафоры - особый вид целочисленных переменных */

/* массив для отслеживания состояния каждого философа */

/* Взаимное исключение входа в критическую область */

/* по одному семафору на каждого философа */

/* 1 - номер философа (от 0 до N-1) */

/* бесконечный цикл */

/* философ размышляет */

/* берет две вилки или блокируется */ /* ест спагетти */

/* кладет обе вилки на стол */ /* 1 - номер философа (от 0 до N-1) */

/* вход в критическую область */

/* запись факта стремления философа поесть */

/* попытка взять две вилки */

/* выход из критической области */

/* блокирование, если вилки взять не удалось */

/* 1 - номер философа (от 0 до N-1) */

/* вход в критическую область */

/* философ наелся */

/* проверка готовности к еде соседа слева */

/* проверка готовности к еде соседа

справа */

up(&mutex); /* выход из критической области */

}

void test(i) /* i - номер философа (от 0 до N-1) */

{

if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) { state[i] = EATING; up(&s[i]);

}

}

В программе используется массив семафоров, по одному семафору на каждого философа, поэтому голодный философ может блокироваться, если нужная ему вилка занята. Обратите внимание на то, что каждый процесс в качестве своей основной программы запускает процедуру philosopher, но остальные процедуры: take_forks, put_ forks и test — это обычные процедуры, а не отдельные процессы.

2.5.2.

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

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

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Политическая философия в Италии
  4. Прикладная философия
  5. Философия «долженствования»
  6. ПСИХОЛОГИЯ И ФИЛОСОФИЯ
  7. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  8. Философия космизма
  9. СОЗДАЕМ ФИЛОСОФИЮ ВМЕСТЕ
  10. ЕСТЬ ЛИ ФИЛОСОФИЯ У НОВОСТЕЙ?
  11. Философы