Cтраница 4
Агрегатные функции можно эффективно реализовать с помощью встроенного предиката, моделирующего недетерминизм. Такой предикат, называемый choice ( выбор), существует в языке LDL. [46]
Различие между языками ESTELLE и ОСА более тонко. В основном более сильно выраженные свойства неявности языка ESTELLE достигаются спонтанными переходами, недетерминизмом, хорошо развитыми средствами определения модулей и механизмами синхронизации, Язык ОСА ориентирован в первую очередь на автоматическую реализацию протоколов в конкретном окружении. Это не значит, что метод ограничен одним типом ЭВМ или одним языком программирования. Но он требует создания специального протокольного окружения, в рамках которого исполняются реализации. Соглашения, принятые в рамках протокольного окружения, позволили повысить конструктивность языка. В то же время модель РКА, лежащая в основе языков ESTELLE и ОСА, позволяет упростить процесс перехода от спецификаций одного к спецификациям другого, вплоть до применения автоматических методов. [47]
Режим вычислений, при котором в определенных точках процесса осуществляется выбор варианта его продолжения. Расчет может задаваться произвольным выбором из нескольких вариантов или разделением процесса на отдельные этапы в целях одновременной реализации всех альтернатив. Конкретная форма недетерминизма зависит от принятой формальной схемы вычислений. Turing machine) имеется выбор очередных шагов поведения в соответствии с заданным внутренним состоянием и считанным с ленты символом. [48]
Используемая модель РКА является недетерминированной в том смысле, что из данного состояния в данное время в некоторых случаях возможны различные переходы. Метод выбора конкретного перехода среди возможных оставлен на усмотрение реализатора компилятора с языка или реализатора непосредственно самого протокола. Описание протокола должно удовлетворять любой стратегии разрешения недетерминизма, в противном случае оно некорректно. [49]
Если на этот вопрос можно ответить да или нет, то проблема блокировок вычислений для предложенной модели разрешима. Иными словами, блокировки не возникают, если на бесконечном потоке входных сообщений при любом возможном развитии процессов для каждой альтернативы существует такая наименьшая неподвижная точка ( число сообщений), что композиция процессов может вырабатывать бесконечное число выходных сообщений. При этом учитываются все возможные сценарии вычислений с учетом недетерминизма процессов, которые обмениваются порциями данных произвольных размеров. Методы обнаружения и предотвращения блокировок вычислений описываются в гл. [50]
Еще одним примером может служить описание механизмов синхронизации при взаимодействии по межуров-невым интерфейсам. Если уровни реализованы в пределах одного процессора, то реализация этих механизмов может быть сведена просто к передаче ссылки, тогда как в случае реализации уровней в различных процессорах, не имеющих общей памяти, эти механизмы могут потребовать для их реализаций введения специальных протоколов. Как было отмечено во введении, принцип общности при определении стандартов играет важную роль, а недетерминизм служит способом его достижения. [51]
Только что описанный процесс является частным случаем важной общематематической конструкции, называемой порождающим-процессом. Описание порождающего процесса очень похоже на описание алгоритма, и сам порождающий процесс похож на процесс вычисления. Важным отличием является то, что в некоторых местах порождающего процесса есть точки неопределенности, ( недетерминизма), в которых однозначный вычислительный акт заменяется актом произвольного выбора, правда, из некоторого точно описанного ( Б нашем случае даже конечного) множества. Из-за наличия точек неопределенности порождающий процесс создает ( порождает) целое множество своих возможных исходов. [52]
Начиная с 60 - х годов в конструкциях ЭВМ повсеместно используется принцип прерывания ввода - вывода, который приводит к необходимости введения встроенного механизма некоторых общих ресурсов, задающих средства синхронизации процессов. В силу этого исполнение программы может оказаться недетерминированным. Кроме прерываний, в настоящее время применяются системы с параллельным режимом работы, которые могут эффективно реализовать недетерминизм ( одновременная проверка всех вариантов выбора альтернатив), но крайне неэффективны при реализации детерминированных алгоритмов. [53]