Н. Джехани - Язык Ада (1988) (1160771), страница 33
Текст из файла (страница 33)
Задача об обедающих Философах Рассматриваемая здесь задача о пяти обедающих философах является модификацией задачи, предложенной Дейкстрой. Пять философов проводят свое время, размышляя и поедая макароны. Они едят за круглым обеденным столом. Вокруг стола стоят пять стульев, и за философом с номером 1 закреплен стул с номером 1 (1 < 1 < 5). На столе лежат пять вилок так, что между каждыми двумя стульями лежит одна вилка, т. е. слева и справа от каждого стула находится по вилке. Вилка с номером 1 находится слева от стула с номером !. Рис. 4.5. Пять философов.
Чтобы начать прием пищи, философ должен войти в столовую и занять закрепленный за ним стул. Для еды философу необходимо иметь две вилки (вилки находятся слева и справа от каждого стула). Если философ не может немедленно взять две вилки, то он ждет, когда сможет приступить к еде. Вилки поднимаются со стола по одной, причем левая вилка поднимается первой. Закончив еду (через конечный промежуток времени), философ кладет вилки на стол и выходит из комнаты. 6-797 !вг Глава 4 Задача об обедающих философах активно изучалась в литературе по информатике. Она используется для проверки пригодности средств параллельного программирования и методов доказательств для параллельных программ. Задача об обедающих философах весьма интересна, так как, несмотря на свою простоту, иллюстрирует многие проблемы, возникающие при параллельном программированин. Такими проблемами являются, например, проблема совместно используемых ресурсов и проблема тупиков.
В данной задаче совместно используемыми ресурсами являются вилки, а философы представляют параллельные процессы. Пять философов и пять вилок будут моделироваться задачами, которые используют два массива задач в процедуре 01Х1ХО. После активизации задача, моделирующая действия философов, получает идентификационный номер, равный тому индексу элемента массива, который связан с конкретным философом, Используя этот номер, можно определить идентификационные номера вилок слева и справа от философа.
Каждый философ смертен, поэтому, приняв пищу 100 000 раз, он переходит в лучший из миров. ргосеовге !)1Х1ХО!а ввЬ!уре НЗ 1з 1ХТЕОЕК гапке 1..5; !авй гуре РН1ЬОБОРНЕК !а еп!гу ОЕТ НЗО: ш 11)); — получить идентификационный номер епо РН)ЬОБОРНЕК; !авй !уре РОКК 1в евггу Р1СК ЫР; евзгу РОТ !ЗОЯХ; епо РОКК; Р: аггау(Н)) ог РОКК; — — 5 вилок Р: аггау(НЗ) о1 РН1ЬОБОРНЕК; — — 5 философов пгай Ьооу РОКК !а — В кажлый момент вилку может взять только один — философ. Ее необходимо положить на стол, прежде чем — взять снова.
Задача, моделирующая вилки, заканчивается, — когла заканчивается задача, моделирующая философов. Ьей!и 1оор ве!ес! ассер! Р1СК 1)Р; ассер! Р1)Т !ЗО%Х; ог гепп1паге; ево ве!есй ево 1оор; еп4 РОКК; Пл ллллльлаеть 1ЕЗ |аяЫин|у РН1ЬОБОРНЕВ |в 1; 10; — индекс или номер данного философа ЫГЕ 1.1М1Т: сопвпзп1: |00 000; Т1МЕБ ЕАТЕХ: 1ХТЕОЕВ: 0; ЬЕРТ, 111ОНТ: 1О; — номера вилок Ьея|п аскер| бЕТ 100: |п 10) оо — получить идентификационный номер 1: 1; епо бЕТ 1О; 1.ЕРТ; 1; — номер левой вилки Рх!ОНТ: 1 вин| 5 + 1; — номер правой вилки пЬ||е Т1МЕБ ЕАТЕХ l ЫГЕ ЫМ1Т 1оор — немного подумать; затем войти в столовую, сесть — за стол и взять вилки Р(К1ОНТ).Р1СК ЫР; Г(ЬЕГТ).Р1СК \)Р; — есть макароны положить вилки Р(ЬЕГТ).Р()Т 00%1Ч; Р(1(1ОНТ).Р(ЗТ 00%1Х; Т1МЕБ ЕАТЕЫ: Т1МЕБ ЕАТЕХ + |; — встать и выйти из столовой епо |оор; епо РН|ЬОБОРНЕ|1; Ьей|п 1ог К 1п 10 Ьюр — присвоить идентификационный номер философу Р(К).бЕТ 10(К); спи |оор; епо 01Х1Хб; И философы, и вилки моделировались с помощью массивов задач.
Реализация этой задачи стала бы проще, если бы в языке Ада допускалось использование задач, являющихся элементами массивов. Тогда на основании индекса задачу можно было бы выделить из массива. В этом случае приведенная программа упростится, так как не потребуется явное вычисление идентификационного номера для каждого философа. Читателю предоставляется возможность самому решить другой вариант задачи об обедающих философах, на этот раз исходя из предположения, что философ может сидеть на любом стуле. Это изменение условия задачи приводит к уменьшению для каждого философа среднего времени ожидания. Указание: данная схема может быть реализована путем описания новой задачи, которая вызывается задачей-философом всякий раз, когда философ запрашивает стул (лучше тот, око- Гяявя 4 Рис.
4ХК Кто букет есть следующим? ло которого есть свободные вилки). Закончив обед, философ сообщает своей задаче, что стул свободен. В приведенном решении задачи о философах ни один философ не может прекратить еду на неопределенное время, так как вилки поднимаются в порядке ЯРО (дисциплина обслуживания всех очередей к входам). Тем не менее в этом решении возможно наличие так называемых туликов.
Пусть, например, каждый философ берет одну вилку и, чтобы начать еду, ожидает получения второй вилки. Если предположить, что все философы очень упрямы и ни один из них не желает расстаться с вилкой, не получив вторую и не закончив еду, то вся система будет находиться в приостановленном состоянии. Подобных тупиков можно избежать, например, следующим образом: философ может взять две вилки, необходимые для еды, только в том случае, если обе они свободны. (Указание: использовать условие ттйев оператора отбора.) Другим способом избежать тупики является введение еще одной задачи НОБТ, гарантирующей, что в каждый данный момент времени в столовой находится не более четырех философов.
Каждый философ, прежде чем войти в комнату, должен получить разрешение задачи НОЯТ, а покидая столовую, уведомить задачу НОБТ об этом. Задача НОЯТ имеет следующее описание: сая1с НОЕТ 1в ев(гу ЕХТЕ)с; епггу ЬЕАЧЕ; епа НОЕТ; Фая3с Ьое)у НОЕТ )в 1: 1ХТЕСЕ)с: О; — количество философов в комнате П ьиоегь Ьей1а 1оор яе!ее! згЬеа ! < 4 > -философ может войти, если в столовой — менее четырех человек ассере Е1х1ТЕК; 1: 1+1; ог ассер! 1.ЕАЧЕ; — философ покидает комнату 1: 1 — 1; ог гегпз1аа!е; еас! яе!есй еай!оор; епд НОЕТ; Совершенно очевидно, что теперь, когда введено данное изменение, никаких тупиков быть не может, так как в комнате будет по крайней мере один философ, который может приступить к еде.
После еды, занимающей конечное время, он уйдет, и другой философ сможет начать прием пищи. 4.14.9. Управление лимитом В примере, демонстрирующем применение задач в режиме реального времени, используются практически все средства языка Ада, рассмотренные до сих пор: пакеты, задачи, операторы задержки и спецификации представления.
Необходимо Я;Щ~» в Рис. »Л. Вход в лифт. Главе 4 Рие. 4.8. Кнопки управления в лифте. разработать процедуру й1)Х ЕЬЕЧАТОй, управляющую движением лифта в 8-этажном здании. Этажи нумеруются с 1-го по 8-й (подвального этажа нет). На каждом этаже имеются две кнопки вызова лифта: ЫР (вверх) и ОО%М !вниз), за исключением первого и последнего этажа, где нет соответственно кнопок РОуу'Х и ЫР. Внутри кабины лифта имеется 8 кнопок Е ООй (этаж) с номерами этажей и кнопка ОРЕХ !открыть).
Пассажир, желающий выйти на этаже 1, нажимает кнопку ГЬООй с номером !. Чтобы задержать закрытие дверей, нужно нажать на кнопку ОРЕМ. 4.14.9.1. Описание лифта Лифт работает следующим образом: 1. Лифт обслуживает 8 этажей, двигаясь вверх и вниз. В исходном положении, т. е. когда нет вызовов, лифт находится на первом этаже. 2. При движении вверх лифт останавливается на всех этажах, с которых поступил вызов.
То же самое происходит при движении вниз. Лифт движется таким образом, чтобы направление менялось как можно реже 1Ни один, вызвавший лифт, не ждет бесконечно долго.) 3. Дверь лифта открывается на 5 с. Каждый раз при нажатии кнопки ОРЕХ зто время увеличивается на ! с. Если дверь закрыта, нажатие этой кнопки не имеет никакого эффекта. 4.14.9.2.
Физические подробности работы лифта Нажатие кнопки лифта вызывает прерывание (возможно, с параметрами) в ЭВМ, управляющей движением лифта. Эти прерывания автоматически ставятся в очередь. Прерываниям соответствуют следующие адреса оборудования: 167 П льноегь Кнопка !)о)чх (!) Адрес 8 Гь1000яь Функции Двигаться вниз с этажа 1 (!Р (1) 8 и 1010 ~к Двигаться вверх с этажа 1 Н.ООВ (1) 8 ьч 1020 й Остановиться на этаже 1 ОРЕХ 8 аь 1030 ж Задержать закрытие дверей иа 1 с Имеется пакет ЕЬЕЧАТОК (лифт) со следующей спецификацией: рас!цьяе ЕЬЕЧАТОК (а ргосе!иге МОЧЕ (!Р ОХЕ РЬООК; ргосейнге МОЧЕ !)О%Х ОХЕ ГЬООК; ргосейиге СЬОБЕ ВООК; ргосейпге ОРЕХ !)ООК; егия ЕЬЕЧАТОК; 4.14.9.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
