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

 

Рассмотрим ещё одну трактовку задачи предложенной Дейкстрой об обедающих философах. В некоем пансионе нашли пристанище пять философов. У каждого философа была своя комната, где он мог предаваться размышлениям. Была у них и общая столовая с круглым столом, вокруг которого стояли пять стульев, каждый помеченный именем того философа, которому он предназначался. В центре стола стояла большая миска спагетти, содержимое которой постоянно пополнялось. На столе также лежало пять вилок, по одной между соседними посадочными местами.

Звали философов ФИЛ ₀, ФИЛ ₁, ФИЛ ₂, ФИЛ ₃, ФИЛ ₄ и за столом они располагались в этом же порядке, против часовой стрелки. Почувствовав голод, философ шёл в столовую, садился на свой стул, брал сначала слева от себя вилку, затем справа и приступал к еде. Закончив трапезу, он клал на место обе вилки, выходил из-за стола, и возвращался к своим размышлениям. Разумеется, одной вилкой философы могли пользоваться только по очереди. Если вилка требовалась другому философу, ему приходилось ждать, пока она освободится.

Алфавиты

Теперь построим математическую модель этой системы. Сначала надо выбрать множества событий. Для ФИЛ _i определим это множество как

a ФИЛ _i = { i.садится, i.встаёт, i.берет вил.i, i.берет вил. (i +₅ 1),

i.кладёт вил.i, i.кладёт вил. (i +₅ 1)},

где +₅ - сложение по модулю 5.

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

Другие «действующие лица» —это пять вилок, каждая из которых имеет тот же номер, что и философ, которому она принадлежит. Вилку берет и кладет на место или сам этот философ, или его сосед слева. Алфавит i -й вилки определим как

a ВИЛКА _i = { i.берет вил.i, (i -₅ 1) .берет вил.i, i.кладёт вил.i, (i -₅ 1) .кладёт вил.i },

где -₅ - обозначает вычитание по модулю 5.

Таким образом, каждое событие, кроме садится и встает, требует участия ровно двух соседних действующих лиц — философа и вилки.

Поведение

Помимо не учитываемых нами процессов размышления и еды, жизнь каждого философа представляет собой повторение цикла из шести событий:

ФИЛ _i = (i. садится i.берет вил.i i.берет вил. (i +₅ 1)

i.кладет вил.i i.кладет вил. (i +₅ 1) → i.встаёт ФИЛ _i).

Вилку циклически берёт и кладёт на место кто-нибудь из соседних с ней философов:

ВИЛКА _i = (i.берет вил.i, i.кладёт вил.i ВИЛКА _i | (i -₅ 1) .берет вил.i

(i -₅ 1). кладёт вил.i ВИЛКА _i).

Поведение всего пансиона можно описать как параллельную комбинацию поведения компонент:

ФИЛОСОФЫ = (ФИЛ ₀ || ФИЛ ₁ || ФИЛ ₂ || ФИЛ ₃ || ФИЛ ₄)

ВИЛКИ = (ВИЛКА ₀ || ВИЛКА ₁ || ВИЛКА ₂ || ВИЛКА ₃ || ВИЛКА ₄)

ПАНСИОН = (ФИЛОСОФЫ || ВИЛКИ).

В одном из интересных вариантов этой историй философы могут брать и класть обе вилки в любом порядке. Рассмотрим поведение каждой руки философа в отдельности.

a ЛЕВАЯ _i = { i.садится, i.встаёт, i.берет вил.i, i.кладёт вил.i }.

a ФИЛ _i = { i.садится, i.встаёт, i.берет вил. (i +₅ 1), i.кладёт вил. (i +₅ 1)}.

ЛЕВАЯ _i = (i. садится i.берет вил.i i.кладет вил.i i.встаёт ЛЕВАЯ _i).

ПРАВАЯ _i = (i. садится i.берет вил. (i +₅ 1) i.кладет вил. (i +₅ 1)

i.встаёт ПРАВАЯ _i).

ФИЛ _i = (ЛЕВАЯ _i || ПРАВАЯ _i).

Синхронизацией процессов ЛЕВАЯ _i и ПРАВАЯ _i в момент, когда i -тый философ садится или встаёт, достигается то, что он не может поднять вилку, если не сидит за столом, и не может встать из-за стола, пока не положит вилку. Помимо этого, операции с обеими вилками произвольно чередуются.

Тупик!

Построенная математическая модель позволяет обнаружить опасность возникновения тупиковой ситуации, когда каждый из философов, сев за стол, возьмёт вилку в левую руку и потянется за второй – которой уже нет на месте. Несмотря на то, что каждый из участников способен к дальнейшим действиям, ни одна пара участников не в состоянии договориться о том, какое действие совершить следующим.

Одним из решений этой проблемы явилось введение в систему слуги. Слуге даётся указание следить за тем, чтобы за столом никогда не оказывалось больше четырех философов одновременно. Алфавит его определяется как C B, где

C = {0. садится, …, 4. садится }, B = {0. встаёт, …, 4. встаёт }.

Поведение слуги проще всего описать с помощью взаимной рекурсии. Пусть СЛУГА _j определяет поведение слуги, когда за столом сидят j философов:

СЛУГА ₀ =(x: C СЛУГА ₁),

СЛУГА _j =(x: C СЛУГА _j+1) | y: B СЛУГА _j-1), для j {1,2.3}.

СЛУГА ₄ =(y: B СЛУГА ₃).

Пансион, свободный от тупика, определяется как

НОВПАНСИОН = ((ПАНСИОН || СЛУГА ₀).

---

Дата добавления: 2015-12-20; просмотров: 23; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!