Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 137
Текст из файла (страница 137)
Это означает, что каждая часть оператора имеет определенный порядок выполнения. Но встречаются ситуации, когда недетерминированность позволяет упростить разработку программного обеспечения (см. обсуждение недетерминированного конечного автомата в разделе 3.3.2). Недетерминнрованное выполнение — зто такое выполнение, при котором возможны несколько альтернативных путей. Такая ситуация часто возникает при выполнении параллельных программ. Если в системе имеется л процессов, готовых к выполнению, не всегда понятно, который из них будет выполняться следующим. Хотя при разработке операционных систем зта проблема встречается очень часто, она горазло реже возникает при разработке отдельной программы, в основном потому, что в нашем распоряжении нет подходящих инструментов (например, операторов языка про~ раммирования), позволяющих нам мыслить в терминах педетерминированных вычислений.
498 Глава 11. Распределенная обработка данных Но существует и множество других путей. Если придерживаться только двух указанных траекторий, вы можете никогда не увидеть какие-нибудь достопримечательности, нахоляшнеся, например, на Восьмой авеню или на Шестнадцатой улице. Фактически все возможные пути можно описать следующей программой: иь11е нв в пункте назначения до агытгаг11у 1Г не на 1О-и авеню. иаи на восток 1 ог 1Г не на 20-й упине. иаи на север 1 епп Любой путь, который соответствует этому произвольному (то есть недетерминированному) маршруту, является правильным решением поставленной задачи. Вскоре мы увидим, что охраняемые команды, цредложепные Дейкстрой, являются общим решением этой задачи.
Сторожевые условия. Основным понятием является сторожеооеуслооие(йпагс!), которое обозначается символом — а. Если В является сторожевым условием, а 5— командой (то есть оператором), то охраняемая команда В а 5 означает, что оператор 5 разрешен или готов к выполнению, если сторожевое условие В истинна. Мы используем сторожевые условия в охраняемом операторе 1! и охраняемом операторе повторения. Охраняемый оператор з т. Если В, — множество условий, а 5, — множество операторов, тогда охраняемый оператор з ! записывается следующим образом: 1ГВв — +5~ НВг — +5гН„.НВз5ГП Смысл этого оператора в том, что по крайней мере одно из сторожевых условий должно быть истинным, и выполненно этого оператора заключается в выполнении соответствующего оператора. Обратите внимание па отличие этой конструкции от тех, которые мы уже изучили.
Она отличается от стандартной конструкции 1(-ю1зеп, так как в обычных случаях пе требуется, чтобы сторожевое условие было истинным. Далее, эта конструкция отличается от конструкции сепо языка ! 15Р, где выполняемым оператором был первый в последовательности, для которого условие оказывалось истинным. Определение охраняемого оператора з ! характеризуется истинной недетерминированностью. Мы произвольным образом выбираем любой из операторов 5н для которого условие В, истинно. Охраняемый оператор повторения.
Этот оператор является обобщением последовательного оператора нб11е и похож на охраняемый 1й Если В, — множество сторожевых условий, а 5, — множество операторов, то охраняемый оператор оо записывается так; Оо В~ -ч 5~ Н Вг — к 5г Н,. Н В -а 5 ое Этот оператор выполняется следующим образом: если некоторые сторожевые условия В, истинны, то выполняется один из соответствующих операторов 5,. Этот процесс повторяется, пока истинно хотя бы одно сторожевое условие. Если изначально ни одно из сторожевых условий не истинно, то охраняемый оператор бо пропускается, подобно тому, как это происходит с обычным оператором нп11е.
Как и в случае с охраняемым оператором ау, при наличии более чем одного истинного сторожевого условия возникает недетерминированность. 11.2. Параллельное программирование 499 Охраняемые команды часто упрощают разработку и понимание алгоритмов. Вернемся к рассмотренной выше задаче о маршруте по городу. Общее решение может быть задано недетерминированным способом; Аче - 3: !На 3 авеню) 51 = 12: !На 12 улице] оо Аче < 1О -» Яче - Аче » 1 ! ! 51 < 20 -» 51 = 51» 1 ол Корректным решением, получаемым с помощью этой программы, является любой маршрут, который начинается на пересечении Третьей авеню и Двенадцатой улицы и заканчивается на пересечении Десятой авеню и Двалцатой улицы. Ни в одном из распространенных языков не реализованы охраняемые команды в том виде, в котором онн были предложены Дейкстрой.
Тем не менее концепция недетерминированного выполнения действительно возникает прн разработке программного обеспечения операционных систем. В разделе 11.2.4 более полно рассматривается роль охраняемых команд при использовании задач и подпрограмм. 11.2.3. Обзор языка Ада История. Хоти изначально язык Аг!а разрабатывался для военных приложений, фактически он является универсальным языком и пригоден для решения большинства задач программирования. Аг!а имеет блочную структуру и похожие на существующие в языке Рааса! механизмы описания типов данных, хотя в нем есть расширения для разработки приложений, работающих в режиме реального времени, и распределенных приложений. Он предоставляет более защищенную форму инкапсуляции данных, чем Рааса1, а последний пересмотренный стандарт языка Аг!а был дополнен возможностями разработки объектов и наследования методов.
Язык Аг!а — уникальный язык, отличающийся от всех остальных, рассмотренных в этой книге, тем, что он стал международным стандартом до того, как появился первый работающий транслятор этого языка. Целью проекта, осуществлявшегося под руководством Министерства обороны США (Рерагггпепг оЕ РеЕепве, РОР), являлась разработка языка и фиксация полученной разработки при помоцаи стандарта до того, как появились бы несовместимые вариации. До некоторой степени эта цель была достигнута в 1983 г., хотя некоторые недостатки языка привели к пересмотру его стандарта в 1995 г.
В конце 70-х гг. в Министерстве обороны С Ш А возник интерес к созданию единого языка для использования во встроенных системах, работающих в режиме реального времени. Была создана Рабочая группа языков высокого порядка (Н!8!аег Оп)ег Е.апйпайе %от!г!пй Сгопр, НО~%С) для разработки такого языка, который позволил бы избавиться от царившего в этой области хаоса. В одном из обзоров, составленных группой НОЕЮС, было перечислено свыше пятисот языков, которые применялись в то время для поддержки различных военных приложений. С помощью ряда последовательных, все более точных спецификаций в период с 1975 по 1978 г. («Бггаччшап», «ЪЪ'оойпап», «Т!паап», «1гопшап» и, наконец, «Бгее!шап») были определены требования для такого языка. Хотя исходной целью было либо использовать, либо расширить какой-нибудь из существующих языков !наиболее вероятными кандидатами являлись Рааса!, АНСОН 68 или РЕ/1), вскоре обнару- 500 Глава 11. Распределенная обработка данных жилось, что ни один нз существующих языков не мог отвечать нуждам избранной области приложений и требовался совершенно новый язык.
Чтобы сократить огромный срок (приблизительно 20 лет), который потребовался бы для полной разработки нового языка, был испробован новый подход. Контракты на проектирование такого языка были заключены с несколькими разработчиками одновременно, и результаты этого соревнования проектов стали предметоьч интенсивного изучения как в промышленности, так и в академической среде с целью доведения сроков экспертных исследований до нескольких месяцев. Из семнадцати представленных вариантов языков было выбрано четыре, которым были присвоены кодовые названия «красный», «зеленый», «желтый» и «синий». После второго отборочного этапа в 1979 г. победителем оказался «зеленый» язык, представленный Жаном Ишбиа()еап 1сЬЬгаЬ) из Франг1ии.
Хотя изначально язык назывался ООО-1, вскоре его имя изменилось на Лда — в честь Ады Лавлейс (Лс1а ).оче1асе'), пионера в области машинных вычислений и помощницы Чарльза Бэббиджа (СЬаг!ез ВаЬЬайс), разработчика первого механического вычислительного устройства в 50-х гг. Х1Х столетия. При разработке языка Лс! а отправной точкой послужил Разса1, но получившийся в результате язык отличается от Рааса! во многих основных аспектах. В первую очерель, Аг1а гораздо более сложный язык, чем Раэса!, включает в себя большее количество языковых конструкций и имеет некоторые основные свойства, не имек1шие аналогов в Рекса!, — в частности, создание задач, параллельное выполнение, управление задачами в режиме реального времени, обработка исключений и возможность созлания абстрактных типов данных. Язык был стандартизован в 1983 г. одновременно как коммерческий стандарт СШЛ, военный стандарт США и международный стандарт [58!.
Чтобы убедиться в том, что трансляторы Аг)а соответствуют стандарту, в ООО был создан комитет Аг1а )о)гтс Ргойгаш Ойбсе (А )РО) для наблюдения за применением этого языка в военной области и разработки Лс1а Сошрг!ег чга!Маг!оп Вшге (АС'тГ8) — набора тестов, которые должен был пройти любой транслятор Лс1а, чтобы считаться реализацией языка. Для военных приложений США требовалось, чтобы любой компилятор, используемый в таком проекте, прошел тест АС»г8, тогда как для коммерческого или академического использования такой проверки не требовалось. Использование тестов АС'чг8 было еще одним отличием от обычного процесса стандартизации. Подмножества или расширения стандарта не допускались ни для одного сертифицированного транслятора.
Строгое соответствие стандарту требовалось и от содержания справочного руководства: ничего больше и ничего меньше, — хотя имелись и отступления от этого правила. Например, простой процессор, управляющий системой понижения токсичности выхлопа автомобиля, не использовал сложную систему управления файлами. Такие функции не требовались в компиляторах Аг(а, использовавшихся для приложений в этой области, если целевая система не имела этих возможностей. Первые эффективные трансляторы Лда появились только в 1986 или 1987 г. Использование этих новых трансляторов, а также академическое эксперименти- Кстати, дочери асли кого английского по»та лорда Джорджа Гордона Байрона.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
