Операционные системы. Управление ресурсами


Обедающие философы


Классической уже стала неформальная постановка задачи распределения ресурсов, носящая название "проблемы обедающих философов" и показанная на Рисунке 5.1.


Рис.5.1. Обедающие философы. Тупик

Пять философов сидят за круглым столом, в центре которого стоит блюдо с рисом. Между каждой парой философов лежит палочка для еды, палочек, следовательно, тоже пять. Для того, чтобы начать есть, философ должен взять две палочки - слева и справа от себя. Таким образом, если один из философов ест, его соседи справа и слева лишены такой возможности, так как им недостает палочек. Каждый философ "работает" по зацикленному алгоритму: сначала он некоторое время думает, затем берет палочки и ест, затем опять думает и т.д. Временные интервалы мышления и еды случайны, действия философов, следовательно, не синхронизированы. Ничего не говорится в условии о том, каким образом философ берет палочки, - наша задача как раз и состоит в том, чтобы обеспечить такую стратегию выделения палочек, которая бы исключала тупики и бесконечное откладывание.

Если мы установим, что каждый философ должен взять одну палочку и не выпускать ее из рук до тех пор, пока не возьмет вторую палочку, то мы можем получить ситуацию, показанную на Рис.5.1. (стрелка от философа к палочке означает, что философ хочет взять эту палочку, стрелка в обратном направлении - что эту палочку этот философ уже взял.) Каждый из философов взял палочку справа от себя, но не может взять палочку слева. Ни один из философов не может ни есть, ни думать. Эта ситуация и называется тупиком (deadlock).

Если же мы установим, что философ должен взять обе палочки сразу, то может возникнуть ситуация, показанная на Рис.5.2. Философ Чжуан хочет взять палочки, но обнаруживает, что его правая палочка занята философом Мо. Чжуан ожидает. Тем временем философ Мэн берет свои палочки и начинает есть. Мо есть заканчивает, но Чжуан не может начать есть, так как теперь занята его левая палочка. Если Мо и Мэн едят попеременно, то Чжуан попадает в положение, которое называется голоданием (starvation) или бесконечным откладыванием.




Начало  Назад  Вперед



Книжный магазин