Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

15.5. СИСТЕМЫ С ДИСКРЕТНЫМИ СОБЫТИЯМИ

825

среда поддержки процессов. Каждый процесс может находиться в одном из

четырех состояний, которые определяются с использованием так называе-

мого управляющего списка: строго упорядоченной очереди процессов, на-

значаемых на выполнение. В хорошей реализации классической модели этот

список скрыт.

Для каждого процесса определяется структура данных, достаточная для

полного запоминания его состояния в момент, когда дискретный шаг закон-

чен

. Запомненное состояние называется точкой возобновления.

Состояние называется

a) активным, когда (реально) выполняется программа процесса;

b) приостановленным, когда выполнение программы процесса прервано, но

запомнена точка возобновления и процесс находится в управляющем спис-

ке;

c) пассивным, когда процесс не выполняется и не находится в управляющем

списке, но точка возобновления активности запомнена;

d) завершенным, когда выполнение его программы прервано, и точка возоб-

новления активности не запомнена.

Конструкция управляющего списка имитирует время. Первый процесс все-

гда активный. Это единственный активный процесс. Если он прерывает свое

выполнение, то следующим активным становится следующий за ним при-

остановленный процесс. Процесс может быть вставлен в управляющий спи-

сок (перед каким-либо процессом в списке или после него, через определен-

ное время) или удален из него. Процесс также может быть назначен на опре-

деленное время, и это означает, что он вставляется перед тем процессом, вре-

мя выполнения которого — минимальное время, превосходящее назначае-

мое. Возможно случайное (псевдослучайное) действие по вставке процесса

в то или иное место управляющего списка.

Можно считать, что с помощью управляющего списка процессам задают-

ся относительные приоритеты.

Постулируется, что все оперирование с управляющим списком и с состо-

яниями активности процессов является следствием событий, дискретно про-

исходящих в системе. Пока какое-либо из событий не произошло, состояние

процесса и его положение в управляющем списке не могут изменяться.

Вспомните, что в системах с дискретными событиями целостность данных должна га-

рантироваться лишь в момент между шагами процесса.

826

ГЛАВА 15. МОДЕЛИРОВАНИЕ

Видно, что это именно имитационная модель, создающую структуру, для

внешнего наблюдателя практически неотличимую от реального параллелиз-

ма, причем с неограниченным количеством процессоров. Поскольку у нас

система с дискретными событиями, время модельное и нет нужды явно вы-

держивать временные задержки. Они являются лишь средством перестройки

управляющего списка.

Применительно к решаемой задаче копирование агентов означает

a) создание локальных структур данных агентов-процессов;

b) размещение агентов-процессов в управляющем списке;

c) перемещение каждого активного агента-процесса по управляющему спис-

ку на величину времени его задержки.

Согласно постулату о событиях, выполнение любого процесса-агента не мо-

жет привести к изменению планируемого порядка выполнения остальных

процессов,пока не произойдет событие. В данном случае событиями являют-

ся истечение временной задержки, а также самоликвидация активного аген-

та, в результате которой активным становится следующий процесс управля-

ющего списка.

К примеру, для обратного алгоритма с выставлением пометок-рекоменда-

ций схема программы агента, пришедшего в город из некоторого местополо-

жения (это параметр программы агента), сводится к следующему:

1. Ждать время,необходимое для перемещения из местоположения в дан-

ный город (фактически это означает лишь соответствующую переста-

новку себя в управляющем списке,сопровождающуюся приостановкой

процесса);

2. Если данный город уже посещался (в городе имеется пометка-рекомен-

дация), то ликвидировать себя, т. е. завершить процесс;

3. Сделать пометку-рекомендацию в данном городе, используя местопо-

ложение, из которого пришел агент;

4. Если данный город есть A, то построить путь, используя пометки ре-

комендации, и завершить процесс;

15.5. СИСТЕМЫ С ДИСКРЕТНЫМИ СОБЫТИЯМИ

827

5. Для каждой дороги, ведущей в данный город, породить процесс но-

вого агента, в качестве параметра которого задается данный город. На-

значить активизацию нового процесса непосредственно после прекра-

щения активности родительского процесса;

6. Завершить процесс.

↓

)

×)

τ(t

)

,B)

→ A

↓

→ A

↓

→ A

↓

→ A

…

→ A

b) трансформация состояний управляющего сп иска

a) модельное время

Рис. 15.3. Управляющий список

На рис. 15.3 изображено начало последовательности состояний управля-

ющего списка, которая получается при выполнении алгоритма с данными,

представленными на рис. 15.2с. В верхней части рисунка представлена мо-

дель времени: на горизонтальной оси изображены моменты, когда состояние

828

ГЛАВА 15. МОДЕЛИРОВАНИЕ

агентов меняется (τ — функция времени перемещения между городами; a, b,

c и d — моменты, отмеченные для дальнейшего пояснения). В нижней части

рисунка показана последовательность изменений управляющего списка (его

состояния выделены прямоугольными блоками, в которых для наглядности

вертикальные стрелки обозначают связи процессов, назначенных на одно и

то же время, а горизонтальные стрелки — упорядоченность процессов по

модельному времени).

Разбредание агентов начинается с порождения процессов

, что со-

ответствует двум дорогам, ведущим в город B. Это момент модельного вре-

мени, омеченный как a. Моменту b соответствуют четыре состояния, сменя-

ющие друг друга, c соответствует три, а d — одно состояние. Из сопоставле-

ния рисунков 15.3a и 15.3b видно, что никакого специального моделирования

времени, а тем более задержек не требуется: время изменяется «мгновенно»,

когда все события, назначенные к более ранним срокам отработали и в голо-

ве управляющего списка появляется событие, назначенное на более поздний

срок. Именно поэтому данная система носит название системы с дискретны-

ми событиями. В принципе здесь не требуется даже атрибут времени —

достаточно отношения порядка между событиями.

Очевидно, что даже бесконечное зацикливание не помешает выполнению

алгоритма, если только вместимость управляющего списка будет достаточ-

ной.

Необходимо подчеркнуть ряд важных моментов:

1. реального параллелизма в системе с дискретными событиями нет, но

есть эффект параллелизма, который лишен многих самых неприятных

неприятных ситуаций, требующих специальной заботы о синхрониза-

ции (например, коллапсы «макаронных» философов, см. ниже);

2. изначально в каждый модельный момент набор одновременно действу-

ющих агентов упорядочен частично,он становится упорядоченным пол-

ностью за счет соответствующей расстановки в управляющем списке;

3. управляющий список — общая структура данных для агентов-процес-

сов, но ее нельзя считать глобальной, так как явного доступа управля-

ющий список не имеет.

Пример 15.5.1. Рассмотрим следующую классическую задачу.

Чтобы воспитанный по европейским стандартам человек мог есть спа-

гетти, ему нужно две вилки: в левой и правой руке.

15.6. UML-МОДЕЛИРОВАНИЕ И RUP

829

Есть пять философов, погруженных в свои размышления и прогуливаю-

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

что на уровне подсознания следит, чтобы не столкнуться с ними физически.

В саду стоит курглый стол с пятью стульями, пятью тарелками со спа-

гетти, соответствующих стульям, и пятью вилками (между каждыми двумя

вилками по тарелке). Когда философ осознает, что он голоден, он занимает

первый попавшийся свободный стул (недетерминированное действие), бе-

рет две вилки, если они свободны, и насыщается. После чего возвращается к

размышлениям. Если свободна лишь одна вилка, он сидит за столом в ожи-

дании, когда освободится другая. Если нет свободных вилок, он поднимается

и опять на недетерминированное время предается размышлениям.

Если все пять философов сядут за стол одновременно, то они умрут с

голоду. Более того, даже если такого не случится, один из них может умереть

с голоду из-за постоянной блокировки вилок другими в моменты, когда он

подходит к столу.

Эта ситуация не может быть полностью проанализирована в рамках си-

стем с дискретным временем.

Конец примера 15.5.1.

Внимание!

Если попытаться реализовать систему с дискретными собы-

тиями с использованием реального распараллеливания, то все не-

приятности синхронизации появляются снова.

Впервые система с дискретными событиями возникла как библиотечная

надстройка над популярными в то время языками. Очень скоро была осо-

знана необходимость языкового оформления соответствующих средств, но

по-прежнему в рамках специальных языков, ориентированных на моделиро-

вание.

§ 15.6. UML-МОДЕЛИРОВАНИЕ И RUP

RUP

(Rational Uniﬁed Process) — одна из основных технологий инду-

стриального программирования. Поскольку она ориентирована на быстрое

удовлетворение достаточно примитивных запросов заказчиков, для которых

внешнее оформление интерфейса по крайней мере не менее важно, чем про-

граммное наполнение, она ориентирована на интерактивное выявление тре-

830

ГЛАВА 15. МОДЕЛИРОВАНИЕ

бований и их уточнение. Здесь автоматная версия ООП оказывается как раз

на месте.

Технология снабжена полуавтоматическими средствами получения ша-

блонов технологических документов и согласованной с автоматным предста-

влением программ версией полуформальной работы с требованиями заказчи-

ка. Она поддержана фабриками, генерирующими по спецификациям задачи

соответствующие типы и объекты. Опыт работы показал, что автоматизиро-

ванная генерация приводит к неудовлетворительным реализациям, кроме не-

которых самых простых и тривиальных случаев. Поэтому результаты работы

фабрик также рассматриваются как шаблоны для ручного заполения и моди-

фикации.

Предупреждение

Не пытайтесь применять эту технологию для задач, содержа-

щих концептуальные проблемы на уровне структуры проекта.

Вопросы для самопроверки

1. Оценить ошибку вычисления собственных значений двух матриц при

использовании стандартной программы:







. . .













. . .

ε 1







Глава 16

Подведение итогов

Давайте восклицать, давайте восхищаться!

(Б. Окуджава)

Где сказал впервые «Нет»?

На Большом Каретном

(В. Высоцкий)

Программирование является уникальной областью человеческой деятель-

ности, не зря вызвавшей к жизни такое внутренне противоречивое даже в

своем обозначении явление, как виртуальная реальность.

До сих пор человек создавал квазиискусственные объекты,когда свойства

исходных естественных маериалов значили по крайней мере не меньше, чем

замысел конструктора. Чисто искусственные объекты, созданные разумом

человека и подчиняющиеся лишь законам логики, встречались разве лишь

в математике.

Программирование впервые вывело искусственные объекты в общее поль-

зование. И сразу же выяснилось, что человек склонен воображать себя Де-

миургом

, не обладая основным свойством Творца: всесторонней оценкой

плана перед его реализацией. Внешне деятельность по созданию даже не

очень плохих программ походит на вульгаризированное описание Творения

в Книге Бытия: сначала реализовать самые общие понятия, затем конкрети-

зировать все необхожимые составные части, затем создать венец творения

(основные действующие объекты), увидеть, что это хорошо, почить от тру-

дов своих и наутро узнать, что Ева сожрала яблоко и все пошло наперекосяк.

Одна лишь первоуровневая логика не может застраховать от концептуальных

противоречий.

Творцом с маленькой буквы.

831

832

ГЛАВА 16. ПОДВЕДЕНИЕ ИТОГОВ

Поэтому в программировании особенно возрастает роль общего образо-

вания,прежде всего,логического и философского.Лозунг Оруэлла “Невежество —

сила” при внедрении в практику высокого уровня приводит к решениям, за

которые очень долго приходится расплачиваться.

Далее, сопротивление материала не ушло в прошлое и в программиро-

вании. При создании программ на машинных языках исходные примитивы

были столь просты, что они не навязывали своего стиля и, как правило, не

имели концептуальных противоречий внутри себя. Технических трудностей

было масса, но зато человек, преодолев их, мог следовать чистой логике сво-

его замысла.

Сейчас мы вынуждены следовать уже заранее извращенной логике, навя-

зываемой операционными системами, языками и используемыми пакетами.

Избавиться от этого нельзя, поскольку иначе не предолеешь барьер сложно-

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

свое творение? Для этого нужно прежде всего подняться в измерения, недо-

ступные достаточно примитивной чужой логике. Словом, нужно владеть как

минимум уровнем метода.

Конечно, не все могут подняться на этот уровень, но помочь подняться на

него тем, кто имеет потенциал — одна из основных задач этой книги.

Далее, сейчас популярен лозунг пользоваться ‘позитивным мышлением’.

Если разобраться в этом понятии, то позитивностью здесь и не пахнет. Это

систематическое закрывание глаз на трудности и наигранный оптимизм. Силь-

ной стороной ведущих русских специалистов было и остается негативное

мышление

Его основным принципом является ясное осознание ограничен-

ности и недостатков, а затем превращение вреда в пользу. Нужно понимать,

что негативное мышление помогает корректно поставить задачу и найти не-

приивальное высокоуровневое решение, а не вялый концептуально пороч-

ный компромисс.

Систематизируем самые важные методологические моменты,коотрые раз-

бросаны в тексте книги.

1. Нет универсальных систем. Каждая система специализирована, хоро-

шая система спецуиализирована явно. То, что рекламируется как уни-

версальная система — специализхированная система, пытающаяся пе-

рерасти те рамки, где ее разумно использовать.

2. Виртуозное владение одним инструментом заводит человека в концеп-

Этот термин здесь применен как нарочитая оппозиция позитивному.

833

туальный и жизненный тупик, поскольку через несколько лет этот ин-

струмент выйдет из пользования.

3. Умение чесать левой ногой за правым ухом является показателем низ-

кой квалификации человека как программиста-аналитика.Аналитик дол-

жен уметь найти способ и инструмент, чтобы решение оказалось есте-

ственным.

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

лишь их явное осознание позволяет сделать эту конструкцию гибкой и

переносимой.

5. Понятия высокого уровня не могут быть измыгшлены человеком про-

извольно, они жизнеспособны лишь тогда, когда они являются конкре-

тизациями высших Идей.

6. Понятия и конструкции высокого уровня способны сократить решение

и повысить его эффективность в башню экспонент раз, тогда как стан-

дартная оптимизация или повышение мощностей техники лишь в ли-

нейное число раз.

7. Лишние возможности являются страшнейшим врагом концептуально

глубоких систем. Система должна обобщаться лишь до тех пределов,

когда обобщение происходит без потерь.

8. Средства разного уровня и разной направленности нужно как можно

жестче разделять внутри программной системы. Их нельзя смешивать

в одном и том же тексте.

9. Нетривиальная система должна пользоваться несколькими разными под-

ходами для разных частей.

10. Уровни и стили разных частей системы могут быть независимы,вполне

возможно, когда интегрирующая программа написана с применением

низкоуровневых средств, а интегрируемые модули высокоуровневые

Тем более это возможно в нынешней обстановке, когда средства поддержки взаимодей-

ствия модулей, написанных с помощью разного инструментария, отстают от развития про-

граммных инструментов.

834

ГЛАВА 16. ПОДВЕДЕНИЕ ИТОГОВ

11. То,что предается анафеме большинством,не обязательно окажется худ-

шим решением для Вашей конкретной задачи. Наоборот,за такими среж-

ствами нужно следить, поскольку слишком часто в этой роли оказыва-

ются хорошие специализированные средства, которые пытаются при-

менять в неподходящей обстановке.

12. Напротив, то, что рекламируется как универсальное решение всех про-

блем, должно вызывать настороженность. Может быть, некоторое ядро

этого средства — хороший специализированный инструмент для тех

задач, для которых он ранее не существовал. Но этот инструмент на-

верняка почти безнадежно испорчен дополнительными концептуаль-

но противоречивыми с ним и друг с другом возможностями. Так что

при использовании модного средства сразу вырабатывайте жестокий

внутренний регламент.

13. Разные стили программирования не сводимы друг к другу и к конкрет-

ному языку. Один и тот же стиль может быть реализован разными сред-

ствами.

14. Если Вам предстоит несколько раз работать над сходными задачами ли-

бо даже длительное время заниматься одной и той же, не жалейте сил

на создание собственного инструментария и выработку собственного

регламента работы.

15. Ваши призраки могут быть реальными понятиями для пользователя

(заказчка) программы, а Ваши реальные понятия — не более чем при-

зраками для него. Учитывайте эту разницу точек зрения!

16. Читайте книги, которые выпущены 20 и более лет назад, если они при

первом просмотре показались Вам интересными. Они дадут Вам в жиз-

ни гораздо больше, чем какое-либо «Программирование в системе .Net

версии 2.00 для профессионалов», которое через два года надо будет

выбросить и забыть. Не думайте, что Ваши предки были глупее Вас!

Опыт показывает, что скорее наоборот.

17. То, что было отброшено,слишком часто содержит здравые идеи, не вы-

державшие в тот конкретный момент конкуренции. Их возрождение

в новых условиях может быть прекрасным решением концептуально

трудных проблем, вставших перед Вами.