Что такое параллелизм в программировании

Конкурентность: Параллелизм

В этой статье мне хотелось бы задокументировать всё, что я знаю о том, какие средства можно использовать для эффективного использования вычислительных ресурсов систем и/или удобства разработки.

И, надеюсь, кому-нибудь это может оказаться полезно, ибо кто-нибудь может чего-нибудь не знать, или, наоборот, окажется полезно мне, если кто-нибудь покажет что-нибудь ещё/укажет на изъяны в моих знаниях.

Параллелизм (часть 1, текущая)

• Потоки: scheduling, сон
• Синхронизация: Spinlock, семафоры, барьеры памяти
• Атомарность: TAS, CAS

Параллелизм

Когда-то процессоры были одноядерные (до 2001 года), а в системах был только один процессор (до 1966 года). А затем инструкции стали выполняться одновременно в рамках одной системы.

Потоки

Потоки — абстракция операционной системы, позволяющая выполнять некие куски кода параллельно. Каждый поток имеет «контекст», в который входит кусок памяти под стек и копию регистров процессора. Очевидно, что потоков в системе может быть запущено куда больше, чем у нас имеется процессоров и ядер, поэтому операционная система занимается тем, что schedule’ит (занимается диспетчеризацией, планированием) выполнение процессов, восстанавливая регистры в ядрах процессора для работы некоторого потока некоторое время, затем сохраняет обратно и даёт выполняться следующему.

Планирование должно быть хорошим, чтобы каждый поток работал примерно одинаковое время (но при этом достаточно малое, т.е. нас не удовлетворит, если каждый поток будет работать по несколько секунд), а так же само планирование занимало как можно меньше времени. Тут мы, традиционно, приходим к балансу latency/throughput: если давать потокам работать очень маленькие промежутки времени — задержки будут минимальны, но отношение времени полезной работы к времени на переключение контекстов уменьшится, и в итоге полезной работы будет выполнено меньше, а если слишком много — задержки станут заметны, что может проявиться на пользовательском интерфейсе/IO.

Тут же хотелось бы отметить довольно важную вещь, к которой будем отсылаться позже. Потоки можно погружать в сон. Мы можем попросить операционную систему усыпить поток на некоторое время. Тогда она может учитывать это при планировании, исключив этот поток из очереди на получение процессорного времени, что даст больше ресурсов другим потокам, либо снизит энергопотребление. Кроме того, в теории можно настраивать приоритеты, чтобы некоторые потоки работали дольше, либо чаще, чем другие.

Синхронизация

Ядер у нас стало много, а память как была одна сплошная, так и осталась (хотя в современной организации памяти можно ногу сломать, там и физическая, и виртуальная, и страницы туда-сюда ходят, что-то где-то кешируется, проверяется на ошибки, странно, что всё это до сих пор работает вообще).

И когда мы из нескольких потоков начинает менять одну и ту же память — всё может пойти совершенно не так, как мы этого хотели. Могут возникать «гонки», когда в зависимости от того, в каком порядке выполнятся операции, вас ожидает разный результат, что может приводить к потере данных. И, что ещё хуже — данные могут совсем портиться в некоторых случаях. К примеру, если мы записываем некоторое значение на невыровненный адрес памяти, нам нужно записать в две ячейки памяти, и может получиться так, что один поток запишет в одну ячейку, а другой в другую. И если вы записывали указатель, или индекс массива — то скорее всего вы получите падение программы через какое-то время, когда попытаетесь обратиться к чужой памяти.

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

Spinlock

Самый простой примитив: у нас есть boolean’овая переменная, если true — значит блокировка кем-то была получена, false — свободна. И два метода: Lock, Unlock. Unlock устанавливает значение в false. Lock в цикле делает либо TAS, либо CAS (об этом будет далее), чтобы атомарно сменить false на true, и пытаться до тех пор, пока не получится.

Имея такую штуку мы можем делать блоки кода, которые будут выполняться эксклюзивно (т.е. пока один выполняется, другой стартовать не может). В начале блока он выполняет метод Lock, в конце Unlock. Важно, чтобы он не попытался сделать Lock второй раз, иначе некому будет сделать Unlock и получится deadlock.

Возможно навешивание плюшек. Например, сохранение идентификатора потока, кто захватил блокировку, чтобы никто кроме захватившего потока, не мог сделать Unlock, и если мы сделали Lock второй раз — он не зациклился, такая реализация это называется «мьютексом». А если вместо boolean’а у нас беззнаковое число, а Lock ждёт числа больше нуля, уменьшая его на единицу, получается «семафор», позволяющий работать некоторому заданному числу блоков одновременно, но не более.

Поскольку блокировка работает в бесконечном цикле она просто «жгёт» ресурсы, не делая ничего полезного. Существуют реализации, которые при неудачах говорят планировщику «я всё, передай остаток моего времени другим потокам». Или, например, есть «адаптивные мьютексы», которые при попытке получить блокировку, которую удерживает поток, который в данный момент выполняется — использует spinlock, а если не выполняется — передаёт выполнение другим потокам. Это логично, т.к. если поток, который может освободить ресурс сейчас работает, то у нас есть шансы, что он вот-вот освободится. А если он не выполняется — есть смысл подождать чуть больше и передать выполнение другому потоку, возможно даже тому, кого мы ждём.

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

Лучшая альтернатива блокировкам — усыпление потока, чтобы планировщик исключил его из претендентов на процессорное время, а затем просьба из другого потока разбудить первый поток обратно, чтобы он обработал новые данные, которые уже на месте. Но это справедливо только для очень длительных ожиданий, если же скорости освобождения блокировок соразмерны с одним «тактом» выполнения потока — производительнее использовать спинлоки.

Барьер памяти

В погоне за скоростью работы, архитекторы процессоров создали очень много тёмной магии, которая пытается предсказывать будущее и может переставлять процессорные инструкции местами, если они не зависят друг от друга. Если у вас каждый процессор работает только со своей памятью — вы никогда не заметите, что инструкции a = 5 и b = 8 выполнились в другом порядке, не так, как вы написали в коде.

Но при параллельном исполнении это может привести к интересным случаям. Пример из википедии:

// Processor #1: while (f == 0); // Memory fence required here print(x);

// Processor #2: x = 42; // Memory fence required here f = 1;

Казалось бы, что здесь может пойти не так? Цикл завершится, когда f будет присвоена единица, на момент чего переменная x вроде как уже будет равна 42. Но нет, процессор может произвольно менять местами такие инструкции и в итоге сначала может выполниться f = 1 , а затем x = 42 и может вывестись не 42, а что-нибудь другое. И даже более того. Если с порядком записи всё нормально, может быть изменён порядок чтения, где значение x прочитается перед тем, как мы войдём в цикл.

Для противодействия этому используются барьеры памяти, специальные инструкции, которые препятствуют тому, чтобы инструкции были перемещены сквозь них. На хабре есть отличный перевод на эту тему.

Атомарность

Поскольку некоторые операции с памятью могут быть потоконебезопасны (например, прибавить к числу другое число и сохранить его обратно), существуют операции для проведения атомарных операций, для которых есть специальные процессорные инструкции.

Наиболее часто используемые:

• Test-and-Set — записывает значение, возвращает предыдущее.
• Compare-and-Swap — записывает значение только в том случае, если текущее значение переменной совпадает с неким ожидаемым, возвращает успех записи.

Возвращаясь к нашему спинлоку, операция получения блокировки может быть реализована как при помощи TAS:

void lock() < // Мы будем записывать 1 до тех пор, пока между нашими выполнениям кто-то не запишет в неё 0 while (test_and_set(&isLocked, 1) == 0); >

Так и при помощи CAS:

void lock() < // Пытаемся записать 1, ожидая 0 while (!compare_and_swap(&isLocked, 0, 1)) >

… как я сказал, мне бы хотелось задокументировать всё, но… получилось довольно много, поэтому я разобью это дело на три статьи. Stay tuned.

Параллелизм (информатика) — Concurrency (computer science)

Возможность выполнения различных частей или единиц программы, алгоритма или задачи вне очереди или в частичный порядок, не влияющий на конечный результат «Обеденные философы», классическая проблема, связанная с параллелизмом и общими ресурсами

В информатике, параллелизм — это способность различных частей или единиц программы, алгоритма или задачи выполняться вне очереди или в частичном порядке, не влияя на конечный результат. Это позволяет выполнять параллельное выполнение параллельных модулей, что может значительно повысить общую скорость выполнения в многопроцессорных и многоядерных системах. В более технических терминах параллелизм относится к свойству декомпозиции программы, алгоритма или проблемы на независимые от порядка или частично упорядоченные компоненты или единицы.

• 1 История
• 2 Проблемы
• 3 Теория
  • 3.1 Модели
  • 3.2 Логика

  История

  Как отмечает Лесли Лэмпорт (2015), «в то время как параллельное выполнение программы рассматривалось в течение многих лет, информатика параллелизма началось с основополагающей статьи Эдсгера Дейкстры 1965 года, в которой была представлена ​​проблема взаимного исключения. В последующие десятилетия наблюдался огромный рост интереса к параллелизму, особенно в distri бутилированные системы. Оглядываясь на истоки этой области, можно выделить фундаментальную роль, которую играет Эдсгер Дейкстра ».

  Проблемы

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

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

  Теория

  Теория параллелизма была активной областью исследований в теоретической информатике. Одно из первых предложений было Основополагающая работа Карла Адама Петри о сетях Петри в начале 1960-х годов. Поэтому было разработано множество формализмов для моделирования и рассуждений о параллелизме.

  Модели

  Был разработан ряд формализмов для моделирования и понимания параллельных систем, в том числе:

  • параллельная машина с произвольным доступом
  • модель актора
  • Вычислительные мостовые модели, такие как массовая синхронная параллельная (BSP) модель
  • Сети Петри
  • Технологические вычисления
    • Расчет взаимодействующих систем (CCS)
    • Последовательное взаимодействие процессы (CSP) модель
    • π-исчисление

    Некоторые из этих моделей параллелизма в первую очередь предназначены для поддержки рассуждений и спецификации, в то время как другие могут использоваться на протяжении всего цикла разработки, включая проектирование, реализацию, проверку, тестирование и моделирование параллельных систем. Некоторые из них основаны на передаче сообщений, в то время как другие имеют другие механизмы для параллелизма.

    Распространение различных моделей параллелизма побудило некоторых исследователей разработать способы объединения этих различных теоретических моделей. Например, Ли и Сангиованни-Винсентелли продемонстрировали, что так называемая модель «помеченного сигнала» может использоваться для обеспечения общей структуры для определения денотационной семантики множества различных моделей параллелизма, в то время как Нильсен, Сассон и Винскель продемонстрировали, что теорию категорий можно использовать для обеспечения аналогичного единого понимания различных моделей.

    Теорема представления параллелизма в модели акторов обеспечивает довольно общий способ представляют собой параллельные системы, которые закрыты в том смысле, что они не получают сообщений извне. (Другие системы параллелизма, например, вычисление процессов могут быть смоделированы в модели актора с использованием протокола двухфазной фиксации.) Математическое обозначение, обозначаемое закрытой системой S, строится все лучше приближения из начального поведения, называемого ⊥S, с использованием функции аппроксимации поведения прогрессия Sдля построения обозначения (значения) для S следующим образом:

    Обозначить S≡ ⊔ i∈ω прогрессия S(⊥S)

    Таким образом, S можно математически охарактеризовать в терминах всех его возможных вариантов поведения.

    Логика

    Различные типы временной логики могут использоваться, чтобы помочь рассуждать о параллельных системах. Некоторые из этих логик, например линейная темпоральная логика и логика дерева вычислений, позволяют делать утверждения о последовательностях состояний, через которые может проходить параллельная система. Другие, такие как логика Хеннесси-Милнера и логика действий Лэмпорта, строят свои утверждения из последовательностей действий (изменений состояния). Основное применение этой логики — написание спецификаций для параллельных систем.

    Практика

    Параллельное программирование охватывает языки программирования и алгоритмы, используемые для реализации параллельных систем. Параллельное программирование обычно считается более общим, чем параллельное программирование, потому что оно может включать произвольные и динамические шаблоны взаимодействия и взаимодействия, тогда как параллельные системы обычно имеют заранее определенный и хорошо структурированный шаблон взаимодействия. Основные цели параллельного программирования включают правильность, производительность и надежность. Параллельные системы, такие как Операционные системы и Системы управления базами данных, как правило, предназначены для работы в течение неограниченного времени, включая автоматическое восстановление после сбоя, и не прекращают работу неожиданно (см. Управление параллелизмом ). Некоторые параллельные системы реализуют форму прозрачного параллелизма, при которой параллельные вычислительные объекты могут конкурировать за один ресурс и совместно использовать его, но сложность этой конкуренции и совместного использования скрыта от программиста.

    Поскольку они используют общие ресурсы, параллельные системы обычно требуют включения какого-то типа арбитра где-нибудь в своей реализации (часто в базовом оборудовании) для управления доступом к этим ресурсам. Использование арбитров вводит возможность неопределенности в параллельных вычислениях, что имеет серьезные последствия для практики, включая правильность и производительность. Например, арбитраж вводит неограниченный недетерминизм, который вызывает проблемы с проверкой модели, потому что он вызывает взрыв в пространстве состояний и может даже привести к тому, что модели будут иметь бесконечное количество состояний.

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

    См. Также

    • Chu space
    • Клиент – сервер сетевые узлы
    • Clojure
    • Кластер узлы
    • Управление параллелизмом
    • Параллельные вычисления
    • Параллельные объектно-ориентированное программирование
    • Шаблон параллелизма
    • D (язык программирования)
    • Распределенные системные узлы
    • Elixir (язык программирования)
    • Erlang (язык программирования)
    • Go (язык программирования)
    • Gordon Паск
    • Международная конференция по теории параллелизма (CONCUR)
    • OpenMP
    • Параллельные вычисления
    • Разделенное глобальное адресное пространство
    • Процессы
    • Проект Птолемея
    • Rust (язык программирования)
    • Сноп (математика)
    • Потоки
    • X10 (язык программирования)

    Ссылки

    Дополнительная литература

    • Линч, Нэнси А. (1996). Распределенные алгоритмы. Морган Кауфманн. ISBN 978-1-55860-348-6 .
    • Tanenbaum, Andrew S.; Ван Стин, Маартен (2002). Распределенные системы: принципы и парадигмы. Прентис Холл. ISBN 978-0-13-088893-8 .
    • Курки-Суонио, Рейно (2005). Практическая теория реактивных систем. Springer. ISBN 978-3-540-23342-8 .
    • Гарг, Виджай К. (2002). Элементы распределенных вычислений. Wiley-IEEE Press. ISBN 978-0-471-03600-5 .
    • Маги, Джефф; Крамер, Джефф (2006). Параллелизм: модели состояний и программирование на Java. Вайли. ISBN 978-0-470-09355-9 .
    • Дистефано, С., и Брунео, Д. (2015). Количественные оценки распределенных систем: методологии и техники (1-е изд.). Сомерсет: John Wiley Sons Inc. ISBN 9781119131144
    • Бхаттачарья, С.С. (2013; 2014;). Справочник по системам обработки сигналов (Вторая; 2; 2-я 2013; ред.). Нью-Йорк, штат Нью-Йорк: Springer, 10.1007 / 978-1-4614-6859-2 ISBN 9781461468592
    • Уолтер, К. (2012; 2014;). Оценка устойчивости и оценка вычислительных систем (1. Aufl.; 1; ed.). Лондон; Берлин ;: Springer. ISBN 9783642290329

    Внешние ссылки

    • Параллельные системы в Виртуальная библиотека WWW
    • Представление шаблонов параллелизма на scaleconf

    Параллелизм (информатика)

    

    • В информатике параллели́зм — это свойство систем, при котором несколько вычислений выполняются одновременно, и при этом, возможно, взаимодействуют друг с другом. Вычисления могут выполняться на нескольких ядрах одного чипа с вытесняющим разделением времени потоков на одном процессоре, либо выполняться на физически отдельных процессорах. Для выполнения параллельных вычислений разработаны ряд математических моделей, в том числе сети Петри, исчисление процессов, модели параллельных случайных доступов к вычислениям и модели акторов.

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

    Ленивые вычисления (англ. lazy evaluation, также отложенные вычисления) — применяемая в некоторых языках программирования стратегия вычисления, согласно которой вычисления следует откладывать до тех пор, пока не понадобится их результат. Ленивые вычисления относятся к нестрогим вычислениям. Усовершенствованная модель ленивых вычислений — оптимистичные вычисления — переходит в разряд недетерминированных стратегий вычисления.

    Параллельные вычисления — способ организации компьютерных вычислений, при котором программы разрабатываются как набор взаимодействующих вычислительных процессов, работающих параллельно (одновременно). Термин охватывает совокупность вопросов параллелизма в программировании, а также создание эффективно действующих аппаратных реализаций. Теория параллельных вычислений составляет раздел прикладной теории алгоритмов.

    Декларати́вное программи́рование — это парадигма программирования, в которой задаётся спецификация решения задачи, то есть описывается, что представляет собой проблема и ожидаемый результат. Противоположностью декларативного является императивное программирование, описывающее на том или ином уровне детализации, как решить задачу и представить результат. В общем и целом, декларативное программирование идёт от человека к машине, тогда как императивное — от машины к человеку. Как следствие, декларативные.

    Исчисление процессов или алгебра процессов — семейство связанных подходов к формальному моделированию параллельных систем.

    Сопрограммы (англ. coroutines) — методика связи программных модулей друг с другом по принципу кооперативной многозадачности: модуль приостанавливается в определённой точке, сохраняя полное состояние (включая стек вызовов и счётчик команд), и передаёт управление другому. Тот, в свою очередь, выполняет задачу и передаёт управление обратно, сохраняя свои стек и счётчик.

    Упоминания в литературе

    Можно упомянуть об исследованиях Intel, посвященных динамическому регулированию интенсивности выполнения инструкций (energy per instruction, EPI) в зависимости от степени параллелизма реализации программного обеспечения [2]. Специалисты корпорации опытным путем показали эффективность регулирования тактовой частоты асимметричной многопроцессорной системы в зависимости от активности вычислительных ядер.

    Это дает возможность говорить об имплицитном присутствии диалектических аспектов в современных категориально-методологических системах, о наличии параллелизмов и генетических связей рассмотренных выше подходов с диалектической традицией. Таким образом, речь идет о сохраняющейся перспективности конституируемых на ее основе когнитивных моделей для нужд современности в познавательной, коммуникативной, образовательной сферах.

    Связанные понятия (продолжение)

    Формальная верификация или формальное доказательство — формальное доказательство соответствия или несоответствия формального предмета верификации его формальному описанию. Предметом выступают алгоритмы, программы и другие доказательства.

    Метапрограммирование — вид программирования, связанный с созданием программ, которые порождают другие программы как результат своей работы (в частности, на стадии компиляции их исходного кода), либо программ, которые меняют себя во время выполнения (самомодифицирующийся код). Первое позволяет получать программы при меньших затратах времени и усилий на кодирование, чем если бы программист писал их вручную целиком, второе позволяет улучшить свойства кода (размер и быстродействие).

    Побо́чные эффе́кты (англ. side effects) — любые действия работающей программы, изменяющие среду выполнения (англ. execution environment). Например, к побочным эффектам относятся.

    Чистота́ (в отношении языка программирования) — отсутствие побочных эффектов. Язык программирования является чистым в том случае, если все функции в программах этого языка являются чистыми.

    Паради́гма программи́рования — это совокупность идей и понятий, определяющих стиль написания компьютерных программ (подход к программированию). Это способ концептуализации, определяющий организацию вычислений и структурирование работы, выполняемой компьютером.

    Компилируемый язык программирования — язык программирования, исходный код которого преобразуется компилятором в машинный код и записывается в файл с особым заголовком и/или расширением для последующей идентификации этого файла, как исполняемого операционной системой (в отличие от интерпретируемых языков программирования, чьи программы выполняются программой-интерпретатором).

    Мона́да — это абстракция линейной цепочки связанных вычислений. Монады позволяют организовывать последовательные вычисления.

    Объектами первого класса (англ. first-class object, first-class entity, first-class citizen) в контексте конкретного языка программирования называются элементы, которые могут быть переданы как параметр, возвращены из функции, присвоены переменной.

    Интерпретируемый язык программирования — язык программирования, исходный код на котором выполняется методом интерпретации. Классифицируя языки программирования по способу исполнения, к группе интерпретируемых относят языки, в которых операторы программы друг за другом отдельно транслируются и сразу выполняются (интерпретируются) с помощью специальной программы-интерпретатора (что противопоставляется компилируемым языкам, в которых все операторы программы заранее оттранслированы в объектный код.

    Императи́вное программи́рование — это парадигма программирования (стиль написания исходного кода компьютерной программы), для которой характерно следующее.

    Идиома программирования — устойчивый способ выражения некоторой составной конструкции в одном или нескольких языках программирования. Идиома является шаблоном решения задачи, записи алгоритма или структуры данных путём комбинирования встроенных элементов языка.

    Предметно-ориентированный язык (англ. domain-specific language, DSL — «язык, специфический для предметной области») — язык программирования, специализированный для конкретной области применения (в противоположность языку общего назначения, применимому к широкому спектру областей и не учитывающему особенности конкретных сфер знаний). Построение такого языка и/или его структура данных отражают специфику решаемых с его помощью задач. Является ключевым понятием языково-ориентированного программирования.

    Процеду́рное программи́рование — программирование на императивном языке, при котором последовательно выполняемые операторы можно собрать в подпрограммы, то есть более крупные целостные единицы кода, с помощью механизмов самого языка.

    Вывод типов (англ. type inference) — в программировании возможность компилятора самому логически вывести тип значения у выражения. Впервые механизм вывода типов был представлен в языке ML, где компилятор всегда выводит наиболее общий полиморфный тип для всякого выражения. Это не только сокращает размер исходного кода и повышает его лаконичность, но и нередко повышает повторное использование кода.

    Динами́ческая типиза́ция — приём, широко используемый в языках программирования и языках спецификации, при котором переменная связывается с типом в момент присваивания значения, а не в момент объявления переменной. Таким образом, в различных участках программы одна и та же переменная может принимать значения разных типов. Примеры языков с динамической типизацией — Smalltalk, Python, Objective-C, Ruby, PHP, Perl, JavaScript, Lisp, xBase, Erlang, Visual Basic.

    Модель а́кторов — математическая модель параллельных вычислений, строящаяся вокруг понятия «актора» (англ. actor — актёр, действующий субъект), считающегося универсальным примитивом параллельного исполнения. Актор в данной модели взаимодействует путём передачи сообщений с другими акторами, в ответ на получаемые сообщения может принимать локальные решения, создавать новые акторы, посылать свои сообщения, устанавливать, как следует реагировать на последующие сообщения.

    Низкоуровневый язык программирования (язык программирования низкого уровня) — язык программирования, близкий к программированию непосредственно в машинных кодах используемого реального или виртуального (например, байт-код, Microsoft .NET) процессора. Для обозначения машинных команд обычно применяется мнемоническое обозначение. Это позволяет запоминать команды не в виде последовательности двоичных нулей и единиц, а в виде осмысленных сокращений слов человеческого языка (обычно английских).

    Логи́ческое программи́рование — парадигма программирования, основанная на автоматическом доказательстве теорем, а также раздел дискретной математики, изучающий принципы логического вывода информации на основе заданных фактов и правил вывода. Логическое программирование основано на теории и аппарате математической логики с использованием математических принципов резолюций.

    Обмен сообщениями в информатике — один из подходов реализации взаимодействия компонентов и систем, используемый в параллельных вычислениях, объектно-ориентированном программировании, также — одна из форм межпроцессного взаимодействия в операционных системах, в микроядерных операционных системах подход используется для обмена информацией между одним из ядер и одним или более исполняющих блоков.

    Каламбур типизации является прямым нарушением типобезопасности. Традиционно возможность построить каламбур типизации связывается со слабой типизацией, но и некоторые сильно типизированные языки или их реализации предоставляют такие возможности (как правило, используя в связанных с ними идентификаторах слова unsafe или unchecked). Сторонники типобезопасности утверждают, что «необходимость» каламбуров типизации является мифом.

    В информатике типобезопасность (англ. type safety) языка программирования означает безопасность (или надёжность) его системы типов.

    Примитивный (встроенный, базовый) тип — тип данных, предоставляемый языком программирования как базовая встроенная единица языка.

    Абстра́ктный тип да́нных (АТД) — это математическая модель для типов данных, где тип данных определяется поведением (семантикой) с точки зрения пользователя данных, а именно в терминах возможных значений, возможных операций над данными этого типа и поведения этих операций.

    Абстракция данных — популярная и в общем неверно определяемая техника программирования. Фундаментальная идея состоит в разделении несущественных деталей реализации подпрограммы и характеристик, существенных для корректного её использования. Такое разделение может быть выражено через специальный «интерфейс», сосредотачивающий описание всех возможных применений программы.

    Мо́дульное программи́рование — это организация программы как совокупности небольших независимых блоков, называемых модулями, структура и поведение которых подчиняются определённым правилам. Использование модульного программирования позволяет упростить тестирование программы и обнаружение ошибок. Аппаратно-зависимые подзадачи могут быть строго отделены от других подзадач, что улучшает мобильность создаваемых программ.

    Блок (также говорят блок кода, блок команд, блок инструкций) в программировании — это логически сгруппированный набор идущих подряд инструкций в исходном коде программы, является основой парадигмы структурного программирования.

    Сопоставление с образцом (англ. Pattern matching) — метод анализа и обработки структур данных в языках программирования, основанный на выполнении определённых инструкций в зависимости от совпадения исследуемого значения с тем или иным образцом, в качестве которого может использоваться константа, предикат, тип данных или иная поддерживаемая языком конструкция.

    По одной из классификаций, языки программирования неформально делятся на сильно и слабо типизированные (англ. strongly and weakly typed), то есть обладающие сильной или слабой системой типов. Эти термины не являются однозначно трактуемыми, и чаще всего используются для указания на достоинства и недостатки конкретного языка. Существуют более конкретные понятия, которые и приводят к называнию тех или иных систем типов «сильными» или «слабыми».

    Сема́нтика в программировании — дисциплина, изучающая формализации значений конструкций языков программирования посредством построения их формальных математических моделей. В качестве инструментов построения таких моделей могут использоваться различные средства, например, математическая логика, λ-исчисление, теория множеств, теория категорий, теория моделей, универсальная алгебра. Формализация семантики языка программирования может использоваться как для описания языка, определения свойств языка.

    В информатике и теории автоматов состояние цифровой логической схемы или компьютерной программы является техническим термином для всей хранимой информации, к которой схема или программа в данный момент времени имеет доступ. Вывод данных цифровой схемы или компьютерной программы в любой момент времени полностью определяется его текущими входными данными и его состоянием.

    Компонентно-ориентированное программирование (англ. component-oriented programming, COP) — парадигма программирования, существенным образом опирающаяся на понятие компонента — независимого модуля исходного кода программы, предназначенного для повторного использования и развёртывания и реализующегося в виде множества языковых конструкций (например, «классов» в объектно-ориентированных языках программирования), объединённых по общему признаку и организованных в соответствии с определёнными правилами.

    Контрактное программирование (design by contract (DbC), programming by contract, contract-based programming) — это метод проектирования программного обеспечения. Он предполагает, что проектировщик должен определить формальные, точные и верифицируемые спецификации интерфейсов для компонентов системы. При этом, кроме обычного определения абстрактных типов данных, также используются предусловия, постусловия и инварианты. Данные спецификации называются «контрактами» в соответствии с концептуальной метафорой.

    Оптимизирующий компилятор — компилятор, в котором используются различные методы получения более оптимального программного кода при сохранении его функциональных возможностей. Наиболее распространённые цели оптимизации: сокращение времени выполнения программы, повышение производительности, компактификация программного кода, экономия памяти, минимизация энергозатрат, уменьшение количества операций ввода-вывода.

    Фу́нкция вы́сшего поря́дка — в программировании функция, принимающая в качестве аргументов другие функции или возвращающая другую функцию в качестве результата. Основная идея состоит в том, что функции имеют тот же статус, что и другие объекты данных. Использование функций высшего порядка приводит к абстрактным и компактным программам, принимая во внимание сложность производимых ими вычислений.

    Языково-ориентированное программирование (ЯОП) (англ. Language Oriented Programming), также Расходящаяся разработка (англ. middle out development), также метаязыковая абстракция, также Разработка, опирающаяся на предметно-специфичный язык (англ. DSL-Based Development) — парадигма программирования, заключающаяся в разбиении процесса разработки программного обеспечения на стадии разработки предметно-ориентированных языков (DSL) и описания собственно решения задачи с их использованием. Стадии могут.

    Кодогенерация — часть процесса компиляции, когда специальная часть компилятора, кодогенератор, конвертирует синтаксически корректную программу в последовательность инструкций, которые могут выполняться на машине. При этом могут применяться различные, в первую очередь машинно-зависимые оптимизации. Часто кодогенератор является общей частью для множества компиляторов. Каждый из них генерирует промежуточный код, который подаётся на вход кодогенератору.

    Повторное использование кода (англ. code reuse) — методология проектирования компьютерных и других систем, заключающаяся в том, что система (компьютерная программа, программный модуль) частично либо полностью должна составляться из частей, написанных ранее компонентов и/или частей другой системы, и эти компоненты должны применяться более одного раза (если не в рамках одного проекта, то хотя бы разных). Повторное использование — основная методология, которая применяется для сокращения трудозатрат.

    Неблокирующая синхронизация — подход в параллельном программировании на симметрично-многопроцессорных системах, в котором принят отказ от традиционных примитивов блокировки, таких, как семафоры, мьютексы и события. Разделение доступа между потоками идёт за счёт атомарных операций и специальных, разработанных под конкретную задачу, механизмов блокировки.

    Распределённая система — система, для которой отношения местоположений элементов (или групп элементов) играют существенную роль с точки зрения функционирования системы, а, следовательно, и с точки зрения анализа и синтеза системы.

    Раскрутка компилятора (англ. bootstrapping — от boot и strap) — метод создания транслятора для некоторого языка программирования, при котором транслятор пишется на том же языке программирования, для трансляции которого создаётся; создание транслятором исполняемых файлов из исходного кода самого транслятора. Используется для переноса трансляторов на новые платформы. Появился в середине 1950-х годов. Позволяет создать транслятор, который генерирует сам себя. Применялся для создания трансляторов многих.

    Разделяемая память (англ. Shared memory) является самым быстрым средством обмена данными между процессами.

    Синтаксис языка программирования — набор правил, описывающий комбинации символов алфавита, считающиеся правильно структурированной программой (документом) или её фрагментом. Синтаксису языка противопоставляется его семантика. Синтаксис языка описывает «чистый» язык, в то же время семантика приписывает значения (действия) различным синтаксическим конструкциям.

    Многопото́чность — свойство платформы (например, операционной системы, виртуальной машины и т. д.) или приложения, состоящее в том, что процесс, порождённый в операционной системе, может состоять из нескольких потоков, выполняющихся «параллельно», то есть без предписанного порядка во времени. При выполнении некоторых задач такое разделение может достичь более эффективного использования ресурсов вычислительной машины.

    Обобщённое программирование (англ. generic programming) — парадигма программирования, заключающаяся в таком описании данных и алгоритмов, которое можно применять к различным типам данных, не меняя само это описание. В том или ином виде поддерживается разными языками программирования. Возможности обобщённого программирования впервые появились в виде дженериков (обобщённых функций) в 1970-х годах в языках Клу и Ада, затем в виде параметрического полиморфизма в ML и его потомках, а затем во многих объектно-ориентированных.

    Среда выполнения (англ. execution environment, иногда «ранта́йм» от англ. runtime — «время выполнения») в информатике — вычислительное окружение, необходимое для выполнения компьютерной программы и доступное во время выполнения компьютерной программы. В среде выполнения, как правило, невозможно изменение исходного текста программы, но может наличествовать доступ к переменным окружения операционной системы, таблицам объектов и модулей разделяемых библиотек.

    Что такое параллелизм в программировании

    Параллелизм — это стремление к тому, чтобы процессы протекали в системе одновременно. Конечно, параллелизм — это естественный феномен. В реальном мире в каждый момент времени одновременно происходит множество событий. При разработке программного обеспечения, которое отслеживает и управляет работой реальных систем, мы должны иметь дело с естественным параллелизмом.

    При работе с параллелизмом в системах программного обеспечения, важно принимать во внимание два главных аспекта: способность обнаружить и отреагировать на внешние события, происходящие в случайном порядке, и обеспечение минимального требуемого интервала отклика на события.

    Если каждое из параллельных действий происходит независимо от других, действительно параллельно, то этот случай относительно прост: для этого достаточно создать отдельные программы, выполняющие каждое действие. Трудности проектирования параллельных систем связаны главным образом с необходимостью взаимодействия параллельных процессов. При взаимодействии параллельных процессов требуется определенная координация.

    Рисунок 1: Пример параллелизма: параллельные процессы, которые не взаимодействуют, имеют простые параллельные выходы. Когда параллельные процессы взаимодействуют или используют общие ресурсы, параллельные выходы становятся важными.

    В качестве аналогии можно рассмотреть транспортный поток. Параллельные потоки движения на разных дорогах с небольшим взаимодействием создают мало проблем. Параллельные потоки на смежных полосах движения требуют некоторой координации для обеспечения безопасности взаимодействия, но самое сложное взаимодействие происходит на перекрестках, где необходима тщательная координация.

    Чем нам интересен Параллелизм?

    Некоторые из причин применения параллелизма являются внешними. То есть, они продиктованы требованиями среды. В реальных системах многие вещи происходят одновременно, и это должно быть отражено в программном обеспечении в «реальном времени». Для этого многие системы программного обеспечения, работающие в реальном времени, должны быть «реактивными». Они должны реагировать на внешние события, которые могут происходить в случайные моменты времени, в случайном порядке.

    Проектирование стандартной процедурной программы для обработки этих ситуаций является крайне сложным. Намного проще может оказаться разделить систему на отдельные элементы программного обеспечения для параллельной обработки каждого из этих событий. Ключевым словом при этом является слово «может», потому что сложность также обусловлена степенью взаимодействия между событиями.

    Для параллелизма могут также существовать внутренние причины [LEA97]. Параллельное выполнение задач может в значительной степени увеличить скорость работы системы при наличии нескольких CPU. Даже при наличии одного процессора многозадачность может существенно ускорить работу, предотвратив блокировку одного действия другим, например, при операциях ввода/вывода. Обычной ситуацией, в которой это происходит, является запуск системы. Часто бывает много компонентов, каждый из которых требует времени для готовности выполнить операцию. Последовательное выполнение этих операций может быть очень медленным.

    Управляемость системы также может быть увеличена посредством параллелизма. Например, одна функция может запустить, остановить или повлиять на работу другой функции, что очень сложно обеспечить без наличия параллельных компонентов.

    Что делает параллельное программное обеспечение сложным?

    Почему при всех этих преимуществах мы не используем параллельное программирование везде?

    Большинство компьютеров и языков программирования в своей основе являются последовательными. Процедура или процессор выполняют одну инструкцию в один момент времени. При использовании одного последовательного процессора иллюзия параллелизма создается чередованием выполнения различных задач. Трудность состоит не в механике этого, а в определении того, когда и как программные сегменты должны сменять друг друга, чтобы они могли взаимодействовать между собой.

    Хотя параллелизм легко достигается при наличии нескольких процессоров, взаимодействие становится более сложным. Прежде всего есть вопрос о коммуникации между задачами, выполняющимися на разных процессорах. Обычно в это вовлечено несколько уровней программного обеспечения, что увеличивает сложность и количество служебных данных, обеспечивающих синхронизацию. В многопроцессорных системах детерминизм уменьшается, поскольку часы и расчет синхронизации могут различаться, а выполнение компонентов может независимо друг от друга неудачно заканчиваться.

    Наконец, параллельные системы более сложны для понимания, потому что в них отсутствует явное общее состояние системы. Состояние параллельной системы — это совокупность состояний ее компонентов.

    Пример параллельной системы реального времени: система лифта

    В качестве примера обсуждаемой здесь концепции рассмотрим систему лифта. Точнее говоря, мы рассмотрим компьютерную систему, предназначенную для управления группой лифтов в одном помещении здания. Очевидно, что в группе лифтов может быть много параллельных вещей, или не быть их совсем! В любой момент времени кто-то на любом этаже может вызвать лифт, и другие запросы могут находиться в невыполненном состоянии. Некоторые из лифтов могут простаивать, в то время как другие перевозят пассажиров или перемещаются в ответ на вызов. Двери должны быть открыты или закрыты в соответствующие моменты времени. Пассажиры могут заблокировать двери, нажав кнопки закрытия или открытия дверей, или выбрав этаж, а затем изменив свой выбор. Табло необходимо обновлять, двигателями нужно управлять, и так далее. Все это должно происходить под контролем системы управления лифтами. В общем, это хорошая модель для изучения концепции параллелизма, которую мы хорошо понимаем и владеем набором рабочих понятий о ней.

    Рисунок 2: Сценарий, включающий два лифта и пять потенциальных пассажиров на 11 этажах.

    Потенциальные пассажиры помещают запросы в систему в различное время, система пытается найти оптимальный способ их выполнения, выбирая лифты на основании их текущего состояния и намеченного времени ответа. Например, когда первый потенциальный пассажир, Энди, вызывает лифт для движения вниз, а оба лифта простаивают, ближайший лифт, Лифт 2, отвечает на вызов, хотя он должен сначала подняться вверх, чтобы забрать Энди. С другой стороны, через несколько секунд, когда второй потенциальный пассажир, Боб, вызывает лифт для движения вверх, более отдаленный Лифт 1 отвечает на этот вызов, потому что известно, что Лифт 2 должен отправиться вниз на пока еще не определенную дистанцию, прежде чем он сможет ответить на вызов вверх.

    Параллелизм как стратегия упрощения

    Если система лифтов состоит только из одного лифта, и лифт может обслуживать в один момент времени только одного пассажира, мы можем склониться к идее, что управлять системой должна обычная последовательная программа. Но даже в этом «простом» случае программа требует многих ветвей для обработки различных условий. Например, если пассажир не вошел в лифт и не выбрал этаж, нужно сбросить состояние лифта, чтобы он мог ответить на другой вызов.

    Обычное требование обработки вызовов от нескольких потенциальных пассажиров иллюстрирует внешние причины параллелизма, которые мы обсуждали ранее. Поскольку потенциальные пассажиры проживают свои собственные параллельные жизни, они совершают вызовы лифта на вид случайным образом, не зависимо от состояния лифта. Чрезвычайно трудно спроектировать последовательную программу, которая сможет ответить на любое из этих внешних событий в любое время, продолжая управлять лифтом в соответствии с прежними решениями.

    Абстрагирование параллелизма

    Для того чтобы эффективно проектировать параллельные системы, мы должны понимать роль параллелизма в системе, и для этого нам необходима абстракция самого параллелизма.

    Основными строительными блоками параллельной системы являются «действия», выполняемых более или менее независимо друг от друга. Полезной графической абстракцией таких действий являются «временные нити» Бура. [BUH96] Наш сценарий лифта на рисунке 3 фактически использует их форму. Каждое действие представлено линией, вдоль которой оно движется. Большие точки указывают места начала действия или ожидания события перед продолжением. Одно действие может инициировать продолжение другого, что представлено в нотации временных нитей соприкосновением места ожидания и другой временной нити.

    Рисунок 3: Визуализация нитей выполнения

    Основными строительными блоками программного обеспечения являются процедуры и структуры данных, но сами по себе они недостаточны для рассуждений о параллелизме. Процессор выполняет процедуру, следуя определенному пути в зависимости от текущих условий. Этот путь можно назвать «нитью выполнения» или «нитью управления». Эта нить управления может разветвляться или зацикливаться в зависимости от условий, которые возникают в разное время, и в системах реального времени она может приостановиться на некоторый период времени или ожидать запланированного момента времени для возобновления.

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

    С точки зрения CPU, есть только одна главная нить выполнения, вплетенная в программное обеспечение, дополненная короткими отдельными нитями, которые выполняются в ответ на аппаратные прерывания. Поскольку все остальное строится на этой модели, проектировщикам важно это знать. Разработчики систем реального времени в большей степени, чем разработчики других типов программного обеспечения, должны понимать как работает система во всех подробностях. Однако, эта модель имеет такой низкий уровень абстракции, что она может только представлять параллелизм очень грубо, с точки зрения CPU. Для проектирования сложных систем полезно иметь возможность работать на разных уровнях абстракции. Конечно, абстракция создается из представления или модели, которая опускает лишние подробности, чтобы сфокусироваться на том, что является важным в данной проблеме.

    На следующем уровне абстракции мы обычно представляем себе программное обеспечение в терминах уровней. На самом фундаментальном уровне операционная система расположена между аппаратным обеспечением и программным обеспечением приложения. Она предоставляет приложению аппаратные службы, такие как память, синхронизацию и систему ввода/вывода, но она абстрагирует CPU для создания виртуальной машины, независимой от фактической конфигурации аппаратного обеспечения.

    Реализация параллелизма: механизмы

    Управление нитями

    Для поддержки параллелизма система должна обеспечить выполнение нескольких нитей управления. Абстракция нити управления может быть реализована различными способами с помощью аппаратного и программного обеспечения. Наиболее распространенными механизмами являются разновидности следующих [DEI84], [TAN86]:

    • Многопроцессорная обработка — несколько CPU выполняются параллельно
    • Многозадачность — операционная система имитирует параллелизм при наличии одного CPU,
      чередуя выполнение разных задач
    • Решения на основе приложения — программное обеспечение приложения берет на себя ответственность за
      переключение между различными ветвями исходного кода в соответствующее время

    Многозадачность

    Когда операционная система предоставляет многозадачность, обычным модулем параллелизма является процесс. Процесс обеспечивается, поддерживается и управляется операционной системой, единственным назначением которой является предоставление среды для выполнения программы. Процесс обеспечивает пространство памяти для исключительного использования его программой приложения, нить выполнения и, возможно, некоторые средства для отправки сообщений и получения их от других процессов. На самом деле, процесс — это виртуальный CPU для выполнения параллельной части приложения.

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

    • заблокирован — ожидает получение некоторого входа или контроля над некоторым ресурсом;
    • готов — ожидает от операционной системы своей очереди для выполнения;
    • выполняется — фактически использует CPU.

    Процессам также часто присваиваются относительные приоритеты. Ядро операционной системы определяет, какой процесс должен выполняться в данное время на основании их состояний, приоритетов и некоторой стратегии расписания. Многозадачные операционные системы в действительности используют одну общую нить управления для всех их процессов.

    Примечание: Термины ‘задача’ и ‘процесс’ часто используются взаимозаменяемо. К сожалению, термин ‘многозадачность’ в общем используется для обозначения способности управления несколькими процессами одновременно, в то время как ‘многопроцессорная обработка’ обозначает систему с несколькими процессорами (CPU). Мы придерживаемся такой договоренности, потому что она наиболее общепринята. Однако, мы мало используем понятие ‘задача’, и делаем это для четкого разграничения между модулем выполняющейся работы (задача) и сущностью, которая предоставляет ресурсы и среду для этого (процесс).

    Как мы говорили ранее, с точки зрения CPU, есть только одна главная нить выполнения. Точно так же, как прикладная программа может перепрыгивать из одной процедуры в другую при вызовах, так и операционная система может передавать управление от одного процесса другому при появлении прерывания, при завершении процедуры или при некоторых других событиях. Поскольку процесс осуществляет защиту памяти, такое «переключение между задачами» может вызвать значительную дополнительную нагрузку. Кроме того, поскольку стратегия расписания и состояния процессов мало контролируются со стороны приложения, чередование процессов имеет слишком низкий уровень абстракции для того, чтобы считать его разновидностью параллелизма, принимаемой в расчет в приложении.

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

    Многопотоковость

    Многие операционные системы, в особенности те, которые используются в приложениях реального времени, предлагают «упрощенную» альтернативу процессам — «нити» или «упрощенные нити».

    Нити — это способ достижения немного более высокого уровня дискретности параллелизма в процессе. Каждая нить принадлежит отдельному процессу, и все нити в процессе имеют общее пространство памяти и другие ресурсы, управляемые процессом.

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

    Примечание: К сожалению, термин ‘нить’ перегружен значениями. Когда мы используем само слово ‘нить’, как мы делаем это здесь, мы имеем в виду ‘физическую нить’, предоставляемую и управляемую операционной системой. Когда мы говорим о ‘нити управления’, ‘нити выполнения’ или ‘временной нити’, как в предшествующем обсуждении, мы имеем в виду абстракцию, которая не обязательно связана с физической нитью.

    Многопроцессорная обработка

    Конечно, наличие нескольких процессоров предоставляет возможность истинно параллельного выполнения. Чаще всего, каждая задача постоянно связана с процессом, выполняющимся в определенном процессоре, но в некоторых ситуациях задачи могут динамически назначаться другому доступному процессору. Возможно, наиболее доступный способ сделать это состоит в использовании «симметричной многопроцессорной обработки». В такой аппаратной конфигурации несколько CPU могут получать доступ к памяти через общую шину.

    Операционные системы, поддерживающие симметричную многопроцессорную обработку, могут динамически назначать нити любым доступным CPU. Примерами операционных систем, поддерживающих симметричную многопроцессорную обработку, являются SUN Solaris и Microsoft Windows NT.

    Основные проблемы параллельного программного обеспечения

    Ранее мы выдвинули на вид парадоксальное утверждение о том, что параллелизм одновременно усложняет и упрощает программное обеспечение. Параллельное программное обеспечение предоставляет более простое решение сложных проблем главным образом потому, что оно позволяет производить «разделение ответственности» среди параллельных действий. В этом отношении, параллелизм — это только лишь еще одно средство увеличения модульности программного обеспечения. Когда система должна выполнять преимущественно независимые действия или реагировать на преимущественно независимые события, назначение их отдельным параллельным компонентам естественно упрощает проект.

    Дополнительные сложности, связанные с параллельным программным обеспечением, возникают практически всегда в ситуациях, в которых эти параллельные действия почти, но не полностью независимы. Другими словами, сложности возникают из-за их взаимодействий. С практической точки зрения, взаимодействия между асинхронными действиями неизбежно вызывают обмен некоторого вида сигналами или информацией. Взаимодействия между параллельными нитями управления повышает количество проблем, свойственных параллельным системам, которые должны быть разрешены для обеспечения правильного поведения системы.

    Сравнение асинхронного и синхронного взаимодействия

    Хотя есть много различных специфических реализаций коммуникации между процессами (IPC) или механизмов коммуникации между нитями, все они в конечном счете могут быть разделены на две категории:

    При асинхронной коммуникации отправляющее действие посылает свою информацию независимо от того, готов ли получатель ее принять, или нет. После отправки информации таким образом, отправитель продолжает выполнять свою работу. Если получатель не готов получить информацию, то она помещается в некоторую очередь, из которой получатель сможет извлечь ее позже. И отправитель, и получатель, работают асинхронно по отношению друг к другу, и, следовательно, они не могут делать предположений о состоянии друг друга. Асинхронная коммуникация часто называется передачей сообщений.

    Синхронная коммуникация включает в себя синхронизацию между отправителем и получателем, кроме обмена информацией. В процессе обмена информацией выполнение двух параллельных действий фактически сливается вместе, разделяя общий сегмент кода, а затем разделяется снова, после завершения коммуникации. Таким образом, в течении некоторого времени они синхронизируются друг с другом и защищаются от конфликтов между собой. Если одно действие (отправитель или получатель) готово к коммуникации раньше другого, оно будет приостановлено до тех пор, пока другое также не станет готово. По этой причине, этот режим коммуникации иногда называют рандеву.

    Потенциальная проблема синхронной коммуникации состоит в том, что во время ожидания готовности своей пары действие не способно реагировать на другие события. Для многих систем реального времени это не всегда допустимо, потому что при этом невозможно обеспечить своевременную реакцию на важную ситуацию. Другой недостаток состоит в подверженности взаимоблокировке. Взаимоблокировка происходит, когда два или более действий вовлечены в дурной цикл ожидания друг друга.

    Когда необходимо обеспечить взаимодействие между параллельными действиями, проектировщик должен выбрать между асинхронным и синхронным типом. Под синхронным мы понимаем такое взаимодействие, при котором две или более параллельных нитей управления должны произвести «рандеву» в один момент времени. В общем смысле, это означает, что одна нить управления должна ожидать ответ другой на запрос. Самой простой и распространенной формой синхронного взаимодействия является случай, когда действие А требует информацию от параллельного действия В для продолжения своего собственного выполнения.

    Конечно, синхронные взаимодействия обычны для непараллельных компонентов программного обеспечения. Обычные вызовы процедур представляют из себя главный пример синхронного взаимодействия: когда одна процедура вызывает другую, инициатор немедленно передает управление вызываемой процедуре и «ожидает», когда оно будет передано ему назад. Однако, в мире параллелизма необходим дополнительный инструментарий для синхронизации независимых нитей управления.

    Асинхронные взаимодействия не требуют рандеву во времени, но для обеспечения коммуникации двух нитей управления все равно необходим дополнительный инструментарий. Часто этот инструментарий имеет вид каналов коммуникации с очередью сообщений, благодаря которому сообщения могут отправляться и приниматься асинхронно.

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

    Помните, что истинный параллелизм процессов или нитей возможен только при многопроцессорной обработке. При наличии только одного процессора иллюзия параллельного выполнения процессов или нитей создается с помощью планировщика операционной системы, который разделяет доступные ресурсы обработки на маленькие порции, благодаря чему все выглядит так, как будто параллельно выполняется несколько нитей или процессов. Неудачный проект аннулирует это разделение времени, создавая несколько процессов или нитей, которые часто синхронно взаимодействуют. Это приводит к тому, что процессы или нити тратят большую часть своей «порции времени» на ожидание ответа другого процесса или нити.

    Конфликт общих ресурсов

    Параллельные действия могут зависеть от недостаточных общих ресурсов. Типичным примером являются устройства ввода/вывода. Если действие требует ресурса, который используется другим действием, он должен подождать его освобождения.

    Условия состязания: проблема согласованного состояния

    Возможно, наиболее фундаментальной проблемой проектирования параллельных систем является избежание «условий состязания». Когда часть системы должна выполнять зависимые от состояния функции (то есть, такие функции, результат которых зависит от текущего состояния системы), необходимо гарантировать, чтобы состояние не менялось на протяжении операции. Другими словами, некоторые операции должны быть «атомарными». Всякий раз когда одна или несколько нитей имеют доступ к одной и той же информации о состоянии, необходима некоторая форма «управления параллелизмом» для обеспечения того, чтобы одна нить не изменила состояние при выполнении другой нитью атомарной зависимой от состояния операции. Одновременные попытки получить доступ к одной и той же информации о состоянии, что может привести состояние ко внутренней несовместимости, называется «условиями состязания».

    Типичным примером условия состязания является ситуация, которая может произойти в системе лифтов, когда пассажир выбирает этаж. Наш лифт работает со списком этажей, на которых нужно остановится при движении в каждом направлении. Каждый раз когда лифт прибывает на этаж, одна нить управления удаляет этот этаж из соответствующего списка и получает из него следующее место назначения. Когда список пуст, то лифт или изменяет направление при наличии этажей в другом списке, или простаивает, если другой список тоже пуст. Другая нить управления ответственна за размещение запросов на этажи в соответствующем списке при выборе их пассажирами. Каждая нить выполняет комбинацию операций в списке, которые по сути не являются атомарными. Например, проверка следующего доступного слота и его заполнение. Если операции нитей будут чередоваться, то они могут перезаписать один и тот же слот в списке.

    Взаимоблокировка

    Взаимоблокировка — это ситуация, в которой две нити управления блокируют друг друга, ожидая пока другая выполнит некоторое действие. По иронии судьбы, взаимоблокировка часто возникает именно потому, что мы применяем механизм синхронизации для избежания условий состязания.

    Пример условий состязания с лифтом может проиллюстрировать относительно легкий случай взаимоблокировки. Нить управления лифта считает, что список пуст, и поэтому никогда не едет на другие этажи. Нить запроса этажа считает, что лифт очищает список, и поэтому не уведомляет лифт о необходимости покинуть простаивающее состояние.

    Другие практические проблемы

    Кроме «фундаментальных» проблем, существует несколько практических проблем, которые должны быть явно разрешены в проекте параллельного программного обеспечения.

    Компромиссы быстродействия

    При наличии единственного CPU механизмы, имитирующие параллелизм с помощью переключения задач, используют циклы CPU, которые в противном случае могли бы быть использованы самим приложением. С другой стороны, если программному обеспечению приходится, например, ожидать устройства ввода/вывода, то выигрыш в быстродействии, достигнутый с помощью параллелизма, может быть нивелирован любой дополнительной нагрузкой.

    Компромиссы сложности

    Параллельное программное обеспечение требует координации и механизмов управления, которые не нужны в последовательных программах. Это делает параллельное программное обеспечение более сложным и увеличивает возможность ошибок. Проблемы параллельных систем также являются более трудными для диагностики из-за наличия множественных нитей управления. С другой стороны, как мы указывали ранее, когда параллелизм продиктован внешними причинами, параллельное программное обеспечение, которое независимо управляет разными событиями, может быть значительно проще последовательных программ, которые должны обрабатывать события в произвольном порядке.

    Неопределенность

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

    Роль программного обеспечения приложения в управлении параллелизмом

    Программное обеспечение приложения может быть вовлечено или, наоборот, не вовлечено в реализацию управления параллелизмом. Существует целый спектр возможностей, в том числе, в порядке увеличения степени вовлеченности:

    1. Задачи приложения могут в любой момент прерываться операционной системой (многозадачность с вытеснением).
    2. Задачи приложения могут определять атомарные элементы работы (критические разделы), которые не могут быть прерваны, и сообщать операционной системе о входе и выходе из них.
    3. Задачи приложения могут решать, когда нужно освободить управление CPU для других задач (совместная многозадачность).
    4. Программное обеспечение приложения может быть полностью ответственно за планирование и управление выполнением различных задач.

    Эти возможности не охватывают весь спектр и не исключают друг друга. В одной системе может применяться их комбинация.

    Абстрагирование параллелизма

    Обычной ошибкой в проектах параллельных систем является слишком ранний выбор специальных механизмов параллелизма в процессе проектирования. Каждый механизм имеет свои преимущества и недостатки, и выбор «лучшего» механизма в определенной ситуации часто определяется незначительными компромиссами. Чем раньше выбирается механизм, тем меньше информации имеется для его выбора. Закрепление механизма также уменьшает гибкость и адаптируемость проекта к разным ситуациям.

    Для наиболее сложных задач проектирования параллелизм лучше всего рассматривать на нескольких уровнях абстракции. Во-первых, функциональные требования системы следует понимать в терминах ее желаемого поведения. Далее, нужно исследовать возможные роли параллелизма. Это лучше всего сделать с помощью абстракции нитей без фиксации определенной реализации. Для расширения возможностей, окончательный выбор механизма реализации параллелизма должен оставаться открытым, чтобы позволить производить тонкую настройку быстродействия и гибкости распределенных компонентов различным образом для разных конфигураций продукта.

    «Концептуальный зазор» между предметной областью (например, системой лифта) и областью решения (программным обеспечением) остается одной из самых больших трудностей при проектировании систем. «Наглядные формализмы» чрезвычайно полезны для понимания сложных идей, таких как параллельное поведение, и они, по сути, устраняют этот разрыв. Среди средств, признанных полезными при решении таких проблем, находятся:

    • диаграммы модулей для наглядного представления параллельно действующих компонентов;
    • временные нити для наглядного представления параллельных и интерактивных действий (которые могут быть ортогональны компонентам);
    • последовательные диаграммы для визуализации взаимодействий между компонентами;
    • диаграммы перехода между состояниями для определения состояний и поведения компонентов, зависимого от них.

    Объекты как параллельные компоненты

    Для разработки систем параллельного программного обеспечения необходимо комбинировать составные блоки программного обеспечения (процедуры и структуры данных) с составными блоками параллелизма (нитями управления). Ранее мы обсуждали концепцию параллельных действий, но система состоит не из действий. Система состоит из компонентов, и имеет смысл составлять системы из параллельных компонентов. Взятые сами по себе, ни процедуры, ни структуры данных, ни нити управления, не являются естественными моделями для параллельных компонентов, но объекты могут очень хорошо скомбинировать все эти необходимые элементы в один подходящий пакет.

    Объект объединяет процедуры и структуры данных в один связный компонент со своим собственным поведением и состоянием. Он инкапсулирует специфическую реализацию сотояния и поведения, а также определяет интерфейс, с помощью которого другие объекты и программное обеспечение могут с ним взаимодействовать. В общем случае, объекты моделируют концепции или сущности реального мира и взаимодействуют с другими объектами посредством обмена сообщениями. Сегодня они признаны многими как лучший способ конструирования сложных систем.

    Рисунок 4: Простой набор объектов системы лифта.

    Рассмотрим модель объектов для нашей системы лифта. Объект устройства вызова на каждом этаже отслеживает кнопки вверх и вниз на этом этаже. Когда предполагаемый пассажир нажимает кнопку, объект устройства вызова посылает сообщение объекту диспетчера лифта, который выбирает наиболее подходящий лифт, отправляет его и подтверждает вызов. Каждый объект лифта параллельно и независимо управляет своим физическим лифтом, отвечая на выбор этажа пассажиром и вызовы диспетчера.

    В такой модели объектов параллелизм может иметь две формы. Меж-объектный параллелизм возникает, когда два или несколько объектов выполняют действия независимо друг от друга с помощью отдельных нитей управления. Внутри-объектный параллелизм возникает, когда несколько нитей управления активны в одном объекте. Сегодня в большинстве объектно-ориентированных языков программирования объекты «пассивны» и не имеют своих собственных нитей нитей управления. Нить(и) управления должна(ы) быть предоставлена(ы) внешней средой. Чаще всего, средой является стандартный процесс операционной системы, созданный для выполнения объектно-ориентированной «программы», написанной на языке, подобном C++ или Smalltalk. Если операционная система поддерживает многопотоковость, то в одном или разных объектах могут быть активны множественные нити.

    На рисунке ниже, пассивные объекты представлены круглыми элементами. Затененная внутренняя область каждого объекта — это информация о его состоянии, а сегментированный внешний круг — это набор процедур (методов), которые определяют поведение объекта.

    Рисунок 5: Иллюстрация взаимодействий объекта.

    Внутри-объектный параллелизм влечет за собой все проблемы параллельного программного обеспечения, такие как потенциальная возможность условий состязания, когда несколько нитей управления получают доступ к одному участку памяти, — в данном случае, к инкапсулированным в объект данным. Можно подумать, что инкапсуляция данных решает эту проблему. Но проблема, конечно, состоит в том, что объект не инкапсулирует нить управления. Хотя внутри-объектный параллелизм в основном избегает этих проблем, существует еще одна трудность. Для обеспечения взаимодействия двух параллельных объектов с помощью обмена сообщениями по крайней мере две нити управления должны контролировать сообщение и доступ к одному и тому же участку памяти. Связанная (но более трудная) проблема состоит в распределении объектов среди различных процессов или процессоров. Обмен сообщениями между объектами различных процессов требует поддержки взаимодействия между процессами и, в общем случает, требует кодирования сообщений в форму данных, которая может быть передана за пределы процесса.

    Конечно, ни одна из этих проблем не является неразрешимой. Фактически, как мы указывали в предыдущем разделе, все параллельные системы сталкиваются с такими проблемами, поэтому существуют проверенные решения. «Управление параллелизмом» только увеличивает объем работы и создает дополнительные возможности для ошибок. Кроме того, оно скрывает сущность проблемы приложения. По всем этим причинам, мы хотим минимизировать потребность программистов иметь с этим дело явно. Одним из способов достижения этого является построение объектно-ориентированной среды с поддержкой передачи сообщений между параллельными объектами (включая управление параллелизмом) и минимизация или устранение использования множественных нитей управления в одном объекте. Фактически, это инкапсулирует нить управления вместе с данными.

    Модель активного объекта

    Объекты со своими собственными нитями управления называются «активными объектами». Для поддержки асинхронного взаимодействия с другими объектами каждый активный объект снабжен очередью сообщений или «почтовым ящиком». При создании объекта среда предоставляет ему свою собственную нить управления, которую объект инкапсулирует на все время своего существования. Подобно пассивному объекту, активный объект простаивает до тех пор, пока снаружи не поступит сообщение. Объект выполняет исходный код, подходящий для обработки этого сообщения. Все сообщения, поступающие в то время, когда объект занят, помещаются в почтовый ящик. Когда объект завершает обработку сообщения, он выбирает следующее ожидающее сообщение из почтового ящика или ожидает поступления нового. В системе лифта подходящими кандидатами для активных объектов являются сами лифты, устройства вызова на этажах и диспетчер.

    В зависимости от их реализации активные объекты могут быть совершенно эффективны. Однако, они создают больший объем дополнительной нагрузки, чем пассивные объекты. Таким образом, поскольку не все операции должны быть параллельными, в одной системе обычно используются как активные, так и пассивные объекты. По причине различных способов их взаимодействия трудно сделать их равными, но активный объект является идеальной средой для пассивных объектов, заменяя процесс операционной системы, который мы использовали ранее. Фактически, если активный объект передает всю работу пассивным объектам, он по существу эквивалентен процессу операционной системы или нити со средствами обеспечения взаимодействия между процессами. Однако, наиболее интересные активные объекты выполняют свою собственную часть работы, передавая другие части пассивным объектам.

    Рисунок 6: ‘Активный’ объект предоставляет среду для пассивных классов

    Подходящими кандидатами для пассивных объектов внутри активного объекта лифта являются список этажей, на которых лифт должен остановиться при движении вверх, и другой список для движения вниз. Лифт должен иметь возможность извлекать из списка следующую остановку, добавлять в него новые остановки и удалять выполненные остановки.

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

    Хотя активный объект с единственной нитью не поддерживает истинный внутри-объектный параллелизм, передача работы содержащимся активным объектам является оправданной заменой для многих приложений. При этом сохраняется важное преимущество полной инкапсуляции состояния, поведения и нити управления на основе объекта, что упрощает разрешение проблем управления параллелизмом.

    Рисунок 7: Система лифта, иллюстрирующая вложенные активные объекты

    Рассмотрим систему лифта, описанную выше. Каждый лифт имеет двери, подъемник и панель управления. Каждый из этих компонентов легко моделируется параллельными активными объектами, где объект дверей управляет открытием и закрытием дверей, объект подъемника управляет положением лифта с помощью механического подъемника, а объект панели управления следит за кнопками выбора этажей и кнопками открытия/закрытия дверей. Инкапсуляция параллельных нитей управления в активных объектах приводит к более простому программному обеспечению, чем при управлении всего поведения единственной нитью управления.

    Проблема ‘Согласования состояний’ в объекте

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

    Для обеспечения правильного поведения объекта безусловно необходимо, чтобы его состояние было внутренне согласовано до и после обработки сообщения. В процессе обработки сообщения объект может оказаться в переходном состоянии или его состояние может быть неопределенным из-за частичного выполнения операций.

    Если объект всегда завершает свое ответное действие на одно сообщение, прежде чем реагировать на другое сообщение, переходное состояние не является проблемой. Прерывание выполнения одним объектом другого также не создает проблем, потому что каждый объект строго инкапсулирует свое состояние. (Строго говоря, это не совсем так, что будет показано далее.)

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

    Параллельный проект, в общем случае, является более простым, если объекты обрабатывают каждое сообщение полностью, прежде чем приступать к обработке другого. Такое поведение подразумевается в частом случае модели активного объекта, которую мы представили.

    Проблема согласованности состояний может проявиться в параллельных системах в двух разных формах, и их легче представить в терминах объектно-ориентированных параллельных систем. Первую форму мы уже обсудили. Если состояние одного объекта (пассивного или активного) доступно для одной или нескольких нитей управления, то атомарные операции должны быть защищены или с помощью естественной атомарности простых операций CPU, или механизмом управления параллелизмом.

    Вторая форма проблемы согласованности состояний является более тонкой. Если более одного объекта (активного или пассивного) содержат одинаковую информацию о состоянии, то объекты будут неизбежно рассогласованы относительно состояния, хотя бы на некоторое время. При плохом дизайне они могут быть рассогласованы надолго, иногда навсегда. Такое проявление несогласованного состояния может считаться другой формой математической «двойственности».

    Например, система управления движением лифта (подъемник) должна гарантировать, чтобы двери были закрыты и не могли открыться во время движения. Проект без соответствующих мер безопасности может позволить дверям открыться в ответ на нажатие пассажиром кнопки открытия дверей сразу после начала движения лифта.

    Легким решением проблемы может показаться размещение информации о состоянии только в одном объекте. Но хотя это может помочь, это также пагубно влияет на быстродействие, особенно в распределенных системах. Кроме того, это не является надежным решением. Даже если только один объект содержит информацию о состоянии, то поскольку другие параллельные объекты принимают решения на основании этого состояния в определенный момент времени, то изменение состояния может сделать решения других объектов неправильными.

    Не существует волшебного решения проблемы согласованности состояний. Все практические решения требуют от нас установить атомарные операции и защитить их каким-либо механизмом синхронизации, который блокирует параллельный доступ на допустимо короткий период времени. Каким является «допустимо короткий» период времени сильно зависит от контекста. Он может быть равным времени, в течение которого CPU сохраняет все байты в числе с плавающей точкой, или в течение которого лифт перемещается на следующий этаж.

    Системы реального времени

    • они используют асинхронную связь на основе сообщений с помощью Портов, применяющих определенные Протоколы;
    • они используют семантику выполнения-до-завершения для обработки сообщений;
    • они инкапсулируют пассивные объекты (что обеспечивает невозможность появления конфликта нитей).

    © Copyright IBM Corp. 1987, 2006. Все права защищены..

    Похожие публикации:

    1. Как копировать объект
    2. Как пишет по скрипту
    3. Какой шрифт в твиттере
    4. Почему не работает саундпад в дискорде