Блокировка - вычисление
Cтраница 2
Во-первых, для обнаружения возможности блокировок вычислений необходимо учитывать детальную структуру данных, которыми обмениваются процессы. Однако требовать от стандарта гарантий согласованности данных, поступающих от разных процессов, конечно, нельзя. Это забота программиста, которому нужны адекватные модели, поддерживающие информационные зависимости между процессами и соответствующую структуру данных. [16]
После того как идея была подана, ее осуществление не вызвало уже особых затруднений, так как в Лиспе данные и программы представляются одинаково. Используемые при этом основные средства - это блокировка вычислений, при помощи которой можно при необходимости запретить вычисления; базовые функции; условные операторы и механизмы рекурсии и определения функции. [17]
 |
Пример иерархии наследования типов данных. [18] |
Недетерминизм процессов и разнородность сообщений создают опасность блокировки вычислений: процессы-потребители не могут быть инициированы, не имея достаточного количества токенов соответствующих типов во входных буферах от процессов-производителей. [19]
Таким образом, наличие гамаков может препятствовать достижимости стационарной разметки и соответственно реализуемости соответствующих моделей вычислений. Однако это вовсе не означает, что гамаки всегда приводят к блокировке вычислений. Так, М - сеть на рис. 3.3 содержит два гамака, образованных соответственно вершинами тэг 1, 5 тз и mit 5 Ш4 а также инцидентными им дугами. [20]
Недетерминированный обмен неоднородными сообщениями адекватно представляет многие черты функционирования масштабируемых систем, такие как массовый параллелизм, взаимодействия типа точка-точка, коммутация пакетов. Однако подобное сочетание свойств требует исследования реализуемости моделей ( проблем однозначности результата и блокировки вычислений) и алгоритмической разрешимости задач их анализа. [21]
Монография обобщает результаты исследований в области распределенных вычислений в масштабируемых средах, к которым можно отнести мультикомпьютеры, кластеры, симметричные мультипроцессоры, системы с распределенной памятью и ресурсы метакомпьютинга. Основное внимание уделяется различным формам модели обмена сообщениями и ее реализуемости, в том числе архитектурами с общей памятью. Рассматриваются вопросы семантики, однозначности результата и блокировки вычислений. Изучаются методы анализа свойств распределенных программ на маркированных графах и исследуется проблема алгоритмической разрешимости задачи анализа. Обосновываются принципы прогнозирования времени выполнения программ и их отображения на целевую архитектуру. Предлагаются методы планирования параллельных процессов в распределенных средах на основе масштабируемых моделей обработки. [22]
Теперь рассмотрим примеры противоположной ситуации, когда, несмотря на отсутствие ориентированных циклов в М - сетях, блокировка вычислений может возникать. Заметим, что возникновение дедлоков, как правило, связывается с наличием контуров в соответствующих графовых моделях обработки. Наличие контура в таком графе свидетельствует о возможности возникновения дедлока. Однако блокировки вычислений могут быть обусловлены и другими причинами, например взаимозависимостью параллельных путей передачи данных от одного процесса-производителя. Этот эффект был замечен при изучении некоторых акторных моделей, в частности SDF. [23]
Если на этот вопрос можно ответить да или нет, то проблема блокировок вычислений для предложенной модели разрешима. Иными словами, блокировки не возникают, если на бесконечном потоке входных сообщений при любом возможном развитии процессов для каждой альтернативы существует такая наименьшая неподвижная точка ( число сообщений), что композиция процессов может вырабатывать бесконечное число выходных сообщений. При этом учитываются все возможные сценарии вычислений с учетом недетерминизма процессов, которые обмениваются порциями данных произвольных размеров. Методы обнаружения и предотвращения блокировок вычислений описываются в гл. [24]
Страницы: 1 2