Обедающие философы
Рис. 12.11. Блюдо спагетти обедающих философов
Знаменитые "обедающие философы" Дейкстры - искусственный пример, призванный проиллюстрировать поведение процессов операционной системы, конкурирующих за разделяемые ресурсы, является обязательной частью всякого обсуждения параллелизма. Пять философов, сидящих за столом, проводят время в размышлениях, затем едят, затем снова размышляют и т. д. Чтобы есть спагетти, каждому из них нужны две вилки, лежащие непосредственно слева и справа от философов, что создает предпосылку для возникновения блокировок.
Следующий класс описывает поведение философов. Благодаря механизму резервирования объектов с помощью сепаратных аргументов в нем, по существу, отсутствует явный код синхронизации (в отличие от обычно предлагаемых в литературе решений):
separate class PHILOSOPHER creation make inherit GENERAL_PHILOSOPHER PROCESS rename setup as getup undefine getup end feature {BUTLER} step is -- Выполнение задач философа do think eat (left, right) end feature {NONE} eat (l, r: separate FORK) is -- Обедать, захватив вилки l и r do ... end endВсе, что связано с синхронизацией, вложено в вызов eat, который использует аргументы left и right, представляющие обе необходимые вилки, резервируя тем самым эти объекты.
Простота этого решения объясняется способностью резервировать несколько сепаратных аргументов в одном вызове, здесь это left и right. Если бы мы ограничили число сепаратных аргументов в вызове одним, то в решении пришлось бы использовать один из многих опубликованных алгоритмов для захвата двух вилок без блокировки.
Главная процедура класса PHILOSOPHER не приведена выше, поскольку она приходит из класса поведения PROCESS: это процедура live, которая по определению в PROCESS просто выполняет from setup until over loop step end, поэтому все, что требуется переопределить, это step. Надеюсь, вам понравилось переименование обозначения начальной операции философа setup в getup.
Благодаря использованию резервирования нескольких объектов с помощью аргументов описанное выше решение не создает блокировок, но нет гарантии, что оно обеспечивает равнодоступность.
Некоторые из философов могут организовать заговор, уморив голодом коллег. Во избежание такого исхода предложены разные решения, которые можно интегрировать в описанную выше схему.
Чтобы избежать смешения жанров, независящие от параллельности компоненты собраны в классе GENERAL_PHILOSOPHER:
class GENERAL_PHILOSOPHER creation make feature -- Initialization make (l, r: separate FORK) is -- Задать l как левую, а r как правую вилки do left := l; right := r end feature {NONE} -- Implementation left, right: separate FORK -- Две требуемые вилки getup is -- Выполнить необходимую инициализацию do ... end think is -- Любое подходящие действие или его отсутствие do ... end endОстальная часть системы относится к инициализации и включает описания вспомогательных абстракций. У вилок никаких специальных свойств нет:
class FORK end Класс BUTLER ("дворецкий") используется для настройки и начала сессии: class BUTLER creation make feature count: INTEGER -- Число философов и вилок launch is -- Начало полной сессии local i: INTEGER do from i := 1 until i > count loop launch_one (participants @ i); i := i + 1 end end feature {NONE} launch_one (p: PHILOSOPHER) is -- Позволяет начать актуальную жизнь одному философу do p.live end participants: ARRAY [PHILOSOPHER] cutlery: ARRAY [FORK] feature {NONE} -- Initialization make (n: INTEGER) is -- Инициализация сессии с n философами require n >= 0 do count := n create participants.make (1, count); create cutlery.make (1, count) make_philosophers ensure count = n end make_philosophers is -- Настройка философов local i: INTEGER; p: PHILOSOPHER; left, right: FORK do from i := 1 until i > count loop p := philosophers @ i left := cutlery @ i right := cutlery @ ((i \\ count) + 1 create p.make (left, right) i := i + 1 end end invariant count >= 0; participants.count = count; cutlery.count = count endОбратите внимание, launch и launch_one, используя образец, обсужденный при введении ожидания по необходимости, основаны на том, что вызов p.live не приведет к ожиданию, допуская обработку следующего философа в цикле.