Программирование от приоритетов
Обсуждая событийное программирование, мы упомянули о том, что при программировании в этом стиле может возникнуть потребность в упорядочивании выполнения нескольких конкурирующих между собой реакций на события. Достаточно универсальным средством удовлетворения этой потребности является приписывание реакциям приоритетов: сначала выполняются те реакции, которые имеют больший приоритет. Этот прием, как выявилось на практике, пригоден для решения достаточно широкого круга задач. Он стал основой для формирования самостоятельного варианта событийного стиля: программирования от приоритетов.
Данная ипостась стиля порождена практическими потребностями. Она предназначена для организации работы многих взаимодействующих процессов, динамически порождаемых и исчезающих. Фундаментальных теоретических исследований в области программирования от приоритетов почти нет. В частности, в классической работе Хоара [29], в которой рассматривается управление взаимодействующими процессами, предполагается, что программа написана в традиционном структурном стиле и никаких попыток приспособить ее к обстановке, где имеется много процессов, нет2).
Стиль программирования от приоритетов не реализован систематически в виде законченного языка (в качестве некоторой попытки можно привести проект Joule, см. http://www.agorics.com/Library/joule.html), но часто используется в прикладных языках скриптов для управления процессами или событиями либо в распределенных системах, либо на полуаппаратном уровне (так называемые встроенные программы, являющиеся частью специализированного прибора или устройства).
В программировании от приоритетов, как и в сентенциальном программировании, порядок расположения операторов в программе не играет принципиальной роли, зато важен приоритет оператора, то есть некоторое значение, принадлежащее в самом общем случае частично-упорядоченному множеству и почти всегда рассматриваемое как элементарное. После завершения очередного оператора среди оставшихся выбирается оператор с максимальным приоритетом.
Если таких операторов с равными или несравнимыми приоритетами несколько, то, вообще говоря, в идеале надо было бы выбирать один из них недетерминированно.
Об операторах, имеющих приоритеты, можно говорить, когда программирование от приоритетов реализовано в специально предназначенном для этого стиля языке. Если же приходится моделировать программирование от приоритетов в обычном языке, то в качестве таких операторов могут выступать иные структурные единицы текста программы. В объектно-ориентированном языке, как правило, это методы объектов. Для краткости, в рамках настоящего параграфа мы будем говорить об операторах, имея в виду только что сделанное замечание.
При назначении приоритетов важно различать случаи, когда они задаются для операторов как элементов текста программы и когда приоритеты вводятся для динамических структурных единиц, то есть для тех элементов процесса вычислений, которые возникают в ходе выполнения программы, но связаны с тем или иным оператором, приоритет которого определяется в рамках конкретного экземпляра (например, объекта). Таким образом выстраиваются разные системы приоритетов, причем во втором случае система приоритетов вынужденно оказывается динамической.
На практике обычно используют жесткую дисциплину, базирующуюся на порядке операторов в программе. Часто управление по приоритетам соединяется с так называемой системой демонов, то есть процедур, вызываемых при выполнении некоторого условия, а не в тот момент, когда при движении по тексту программы мы подошли к их явному вызову (сидит такой демон в засаде и выжидает момент, когда можно будет начать исполняться). И текущий "нормальный" процесс, и проснувшиеся демоны имеют свои приоритеты, и демон начнет исполняться, даже если он активизирован, лишь в том случае, если среди активных не осталось процесса с большим, чем у демона, приоритетом. Эта схема реализована, в частности, в системе UNIX.
Уместно отметить, что событийно-ориентированное программирование порою может рассматриваться как вырожденный случай стиля программирования от приоритетов: для каждого экземпляра структурной единицы, способной реагировать на события, выставляется (бесконечно большой) приоритет, если этот экземпляр фактически должен активизировать реакцию, и не выставляется приоритет (выставляется бесконечно малый приоритет), если экземпляр не должен реагировать на событие.
Общий случай стиля событийно-ориентированного программирования также близок к стилю программирования от приоритетов, если считать, что всем обработчикам события, которые должны быть выполнены при его появлении, присвоены приоритеты, соответствующие фактическому порядку их выполнения. Когда такой порядок неизвестен, можно считать, что всем активизируемым обработчикам присвоены равные приоритеты.
Кардинальное различие между программированием от событий и от приоритетов состоит в принципах задания управления. В случае программирования от событий установлена прямая связь между событием и реакцией: если условие срабатывания открывает для обработчика возможность быть выполненным, то он обязательно будет выполнен в ответ на соответствующее событие. При программировании от приоритетов ситуация иная: задавая демону даже наивысший приоритет, можно лишь надеяться на то, что он сработает раньше других, причем, возможно, даже без появления какого бы то ни было события. Если абстрагироваться от механизма управления при оперировании с приоритетами и событиями, то можно считать эти два стиля вариантами одной сущности.
Варианты событийного программирования от событий и приоритетов хорошо совмещаются, взаимно дополняя друг друга, когда целесообразна следующая архитектурная схема разработки программного проекта. От событий строятся фрагменты системы, которые отвечают за реакцию на каждое из событий, реализуемую разными обработчиками, а программирование этих обработчиков ведется от приоритетов.
Рассмотрим написанный в двух вариантах на двух условных языках пример программы с приоритетами.
3: Цикл пока не будет все сделано { 5: Подготовка данных; 10: Обработка текущих изменений; } 4: Демон {Если Поступили данные То Прием рутинных данных}; 8: Демон {Если Поступили экстренные данные То Запоминание экстренных изменений}; 12: Демон {Если Авария То Аварийные действия};
Пример 13.2.1.
a: PRIO 3 {Prepare Data; SLEEP}; b: PRIO 10 {Process Changes; SLEEP}; c: PRIO 8 DAEMON IF Extra Data THEN Store Extra Data; AWAKE b FI; d: PRIO 12 DAEMON IF Alert THEN Emergency; FI; e: PRIO 2 DAEMON IF Idle THEN AWAKE a; FI;
Пример 13.2.2.
Видно, что в данном примере все приоритеты задавались статически. Именно к этому стремятся почти во всех случаях современной практики вычислений с приоритетами. Однако полной статичности можно добиться лишь в простейших случаях. Например, если процесс долго ждет своей очереди на исполнение, то естественно постепенно поднимать его приоритет. При этом приоритет такого "пользовательского" действия может превзойти приоритет системного процесса, и остается либо статически задавать каждому процессу допустимый максимальный приоритет, и мы вновь попадаем в ту же ловушку, либо задавать разным классам процессов приоритеты, просто не сравнимые по порядку, чтобы ни при каком нормальном исполнении приоритет пользовательского процесса не дорос, скажем, до 109, за которым начинаются приоритеты срочных системных демонов.
Заметим, что назначение приоритетов операционной системой, "сверху", принципиально ничего в данной картине не меняет. С точки зрения пользовательских программ эти приоритеты все равно статические.
Рассмотрим теоретически, какие классы программ можно описать при помощи статических и динамических приоритетов. Оказывается, при помощи статических приоритетов, являющихся натуральными числами, невозможно описать даже примитивно-екурсивные композиции исходных действий3).
Таким образом, концептуально натуральных чисел недостаточно для описания приоритетов, но оказывается, что для них хватает ординалов (см. курс математической логики). Поскольку ординалы до ?0 имеют хорошую вычислительную модель (см., напр., [20]), можно рассматривать целочисленные приоритеты как конкретную реализацию абстрактного класса таких ординалов.
В случае реально распределенных или параллельных действий проблема приоритетов еще важнее и сложнее. Часто управление по приоритетам - единственный шанс справиться со сложностью такой нелинейной во времени системы. Тут уже и линейно упорядоченного множества приоритетов не хватает.
В целом программирование от приоритетов является мощным, но специфическим орудием для описания глобальных совместных, параллельных или распределенных процессов.
Его элементы проникают и в традиционные системы программирования в виде обработки исключительных ситуаций в программах. Здесь, как и в программировании от событий с обособленными реакциями, всего два приоритета, которые налагаются на структуру использующей конструкции. Противоречивость этого средства со структурным программированием только в том, что не всегда ясно, что делается далее, когда обработка исключения завершается.
 |
|
|
Статическое вычисление некоторых частей программ - очень важный и имеющий в потенциале исключительно широкую область применения прием программирования. Если программист предусматривает, что его программа будет частично вычислена до основного выполнения программы, то он следует еще одному стилю - специализирующему программированию.
2)
По этой причине область применения языка OCCAM, непосредственно реализующего идеи Хоара, оказалась неоправданно суженной до тех ситуаций, когда процессы жестко привязаны друг к другу статически описываемыми каналами передачи данных.
3)
Правда, здесь мы отвлекаемся от реальных ограничений и считаем 1010000000000 столь же легко достижимым числом, как и 10.
