Skip to content
This repository has been archived by the owner on Jan 23, 2022. It is now read-only.

Latest commit

 

History

History
262 lines (150 loc) · 59.1 KB

2019-11-06-asynchronous-programming-epm-theory.md

File metadata and controls

262 lines (150 loc) · 59.1 KB
Raw

Отличие между конкурентностью, параллелизмом и многопоточностю (Differences between concurrency, parallelism, and multithreading)

In progress

Materials from book by Riccardo Terrell. Concurrency in .NET. Modern patterns of concurrent and parallel programming. Publishing Hous "Manning", 2018

Source code for "Concurrency in .NET" book Manning publisher

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

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

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

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

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

Up

Конкурентное (Concurrency) программирование одновременно запускает несколько задач

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

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

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

Up

Параллельное программирование выполняет одновременно несколько задач

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

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

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

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

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

Концепция синхронизации является фундаментальной для одновременного выполнения операций параллельно. В такой программе операции синхронны, если они могут выполняться параллельно, и эти операции параллельны, если выполнение перекрывается во времени (Рисунок).

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

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

Up

Многозадачность выполняет несколько задач одновременно со временем

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

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

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

Существует два вида многозадачных операционных систем:

  • Совместные многозадачные системы (Cooperative multitasking systems), в которых планировщик позволяет каждой задаче запускатьcся до тех пор, пока она не завершит или явно не вернет управление выполнением в планировщик
  • Упреждающие многозадачные системы (Preemptive multitasking systems) (например, Microsoft Windows), где планировщик приоритизирует выполнение задач, а базовая система, учитывая приоритетность задач, переключает последовательность выполнения после завершения распределения времени, получая управление другими задачами

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

Up

Многопоточность для повышения производительности

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

ПРИМЕЧАНИЕ. Процесс является экземпляром программы, работающей в компьютерной системе. Каждый процесс имеет один или несколько потоков выполнения, и ни один поток не может существовать вне процесса.

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

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

Взаимосвязь между синхронностью (concurrency), параллелизмом (parallelism), многопоточностью (multithreading) и многозадачностью (multitasking) в одно- и многоядерном устройстве

Up

Итоги:

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

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

    Конкурентность(*)(concurrency) - это наиболее общий термин, который говорит, что одновременно выполняется более одной задачи. Например, вы можете одновременно смотреть телевизор и комментить фоточки в фейсбуке. Винда, даже 95-я могла (**) одновременно играть музыку и показывать фотки.

    (*) К сожалению, вменяемого русскоязычного термина я не знаю. Википедия говорит, что concurrent computing - это параллельные вычисления, но как тогда будет parallel computing по русски?

    (**) Да, вспоминается анекдот про Билла Гейтса и многозадачность винды, но, теоретически винда могла делать несколько дел одновременно. Хотя и не любых.

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

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

    Сергей Тепляков

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

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

    Параллельное исполнение - это строгое подмножество конкурентного исполнения. Это значит, что на компьютере с одним процессором параллельное программирование - невозможно ;)

    Сергей Тепляков

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

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

    Многопоточность - это один из способов реализации конкурентного исполнения путем выделения абстракции "рабочего потока" (worker thread).

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

    Сергей Тепляков

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

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

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

    CPU-bound и IO-Bound операции: Еще один важный момент, с точки зрения разработчика - разница между CPU-bound и IO-bound операциями. CPU-Bound операции нагружают вычислительные мощности текущего устройства, а IO-Bound позволяют выполнить задачу вне текущей железки. Разница важна тем, что число одновременных операций зависит от того, к какой категории они относятся. Вполне нормально запустить параллельно сотни IO-Bound операций, и надеяться, что хватит ресурсов обработать все результаты. Запускать же параллельно слишком большое число CPU-bound операций (больше, чем число вычислительных устройств) бессмысленно.

    Возвращаясь к исходному вопросу: нет смысла выполнять в 1000 потоков метод Calc, если он является CPU-Intensive (нагружает центральный процессор), поскольку это приведет к падению общей эффективности вычислений. ОС-ке придется переключать несколько доступных ядер для обслуживания сотен потоков. А этот процесс не является дешевым. Самым простым и эффективным способом решения CPU-Intensive задачи, заключается в использовании идиомы Fork-Join: задачу (например, входные данные) нужно разбить на определенное число подзадач, которые можно выполнить параллельно. Каждая подзадача должна быть независимой и не обращаться к разделяемым переменным/памяти. Затем, нужно собрать промежуточные результаты и объединить их. Именно на этом принципе основан PLINQ. О чем можно почитать тут: Джозеф Албахари. Параллельное программирование. Выглядит это очень интересно:

      	IEnumerable<Data> yourData = GetYourData();
  	var result = yourData.AsParallel()           // начинаем обрабатывать параллельно
                   .Select(d => ComputeMD5(d))  // Вычисляем параллельно
                   .Where(md5 => IsValid(md5))
                   .ToArray();                  // Возврвщаемся к синхронной модели

    В этом случае, число потоков будет контролироваться библиотечным кодом в недрах CLR/TPL и метод ComputeMD5 будет вызван параллельно N-раз на компьютере с N-процессорами (ядрами).

    Сергей Тепляков

Up

Зачем нужна параллельность?

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

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

Две хорошие иллюстрации - Google и Pixar. В 2012 году Google получал более 2 миллионов поисковых запросов в минуту; в 2014 году это число более чем удвоилось. В 1995 году Pixar выпустил первый полностью созданный компьютером фильм «История игрушек». В компьютерной анимации для каждого изображения должно быть представлено множество деталей и информации, таких как затенение и освещение. Вся эта информация изменяется со скоростью 24 кадра в секунду. В трехмерном фильме требуется экспоненциальное увеличение изменения информации.

Создатели «Истории игрушек» использовали 100 подключенных двухпроцессорных машин для создания своего фильма, а использование параллельных вычислений было незаменимым. Инструменты Pixar развивались для «Истории игрушек 2»; компания использовала 1400 компьютерных процессоров для цифрового редактирования фильмов, тем самым значительно улучшая качество цифрового видео и время редактирования. В начале 2000 года мощность компьютера Pixar увеличилась еще больше, до 3500 процессоров. Шестнадцать лет спустя компьютерная мощность, используемая для обработки полностью анимационного фильма, достигла абсурдных 24 000 ядер. Потребность в параллельных вычислениях продолжает экспоненциально возрастать.

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

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

Диспетчер задач Windows показывает программу, которая плохо использует ресурсы CPU.

Такая трата вычислительной мощности недвусмысленно иллюстрирует, что последовательный код не является правильной моделью программирования для многоядерных обработчиков. Чтобы максимально использовать доступные вычислительные ресурсы, платформа Microsoft .NET обеспечивает параллельное выполнение кода посредством многопоточности. Используя параллелизм, программа может в полной мере использовать имеющиеся ресурсы, о чем свидетельствует счетчик производительности процессора на рисунке ниже, где заметно, что все ядра процессора работают высоко, возможно, на 100%. Текущие тенденции оборудования предсказывают больше ядер вместо более высоких тактовых частот; поэтому разработчикам не остается иного выбора, кроме как охватить эту эволюцию и стать параллельными программистами.

Программа, написанная с учетом параллелизма, может максимизировать ресурсы CPU, возможно, до 100%

Up

Ловушки параллельного программирования

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

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

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

  • Как можно использовать синхронность и параллелизм для достижения невероятной вычислительной производительности и высокочувствительного приложения?
  • Как такие программы могут в полной мере использовать возможности, предоставляемые многоядерным компьютером?
  • Как можно согласовывать связь с одним и тем же местом памяти между потоками, обеспечивая при этом безопасность потока? (Метод называется потокобезопасным, когда данные и состояние не повреждаются, если два или более потока пытаются получить доступ и изменить данные или состояние в одно и то же время.)
  • Как программа может гарантировать детерминированное исполнение?
  • Как можно раскрыть выполнение программы, не подвергая риску качество конечного результата?

Up

Проблемы с параллелизмом

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

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

Рассмотрим случай двух потоков (Thread 1 и Thread 2), работающих параллельно, оба пытаются получить доступ и изменить общее значение x, как показано на рисунке. Потоку Thread 1 для изменения переменной требуется более одной инструкции CPU: значение должно быть считано из памяти, затем изменено и в конечном итоге записано обратно в память. Если Thread 2 пытается прочитать из той же ячейки памяти, пока Thread 1 записывает обновленное значение, значение x изменилось. Точнее, возможно, что Thread 1 и Thread 2 одновременно считывают значение x, тогда Thread 1 изменяет значение x и записывает его обратно в память, а Thread 2 также изменяет значение x. Результатом является повреждение данных. Это явление называется состояние гонки.

Два потока (Thread 1 и Thread 2) работают параллельно, оба пытаются получить доступ и изменить общее значение x. Если Thread 2 пытается прочитать из того же места в памяти, а Thread 1 записывает обновленное значение, значение x изменяется. Результатом этого является повреждение данных или состояние гонки.

Сочетание изменчивого состояния и параллелизма в программе является синонимом проблем. Решение с точки зрения императивной парадигмы заключается в защите изменяемого состояния путем блокировки доступа нескольким потокам. Этот метод называется взаимным исключением, поскольку доступ одного потока к определенному месту памяти предотвращает доступ к другим потокам в то время. Концепция синхронизации является центральной, поскольку несколько потоков должны одновременно получать одни и те же данные, чтобы воспользоваться этой технологией. Введение блокировок для синхронизации доступа несколькими потоками к общим ресурсам решает проблему повреждения данных, но вводит больше осложнений, которые могут привести к тупиковой ситуации. Рассмотрим случай на рисунке, где Thread 1 и Thread 2 ждут друг друга для завершения работы и блокируются на неопределенное время в ожидании. Thread 1 получает Lock A, и сразу после Thread 2 получает Lock B. В этот момент оба потока ожидают блокировки, которая никогда не будет выпущена. Это случай взаимной блокровки (deadlock).

В этом случае Thread 1 получает Lock A, а Thread 2 получает Lock B. Затем Thread 2 пытается получить Lock A, а Thread 1 пытается получить Lock B, который уже был приобретен Thread 2, который ожидает получения Lock A до освобождая Lock B. В этот момент оба потока ожидают блокировки, которые никогда не будут выпущены. Это случай взаимной блокровки.

Ниже приведен краткий перечень факторов риска параллелизма.

  • Состояние гонки - это состояние, которое возникает, когда совместно используемый изменяемый ресурс (например, файл, изображение, переменная или коллекция) используется одновременно многочисленными потоками, оставляя несогласованное состояние. Повреждение данных делает программу ненадежной и непригодной для использования.
  • Снижение производительности является общей проблемой, когда несколько потоков разделяющих состояний требующие методов синхронизации. Взаимные блокировки (или мьютексы), как следует из названия, предотвращают параллельный запуск кода, заставляя несколько потоков останавливать работу для связи и синхронизации доступа к памяти. Приобретение и освобождение блокировок происходит со снижением производительности, замедляя все процессы. По мере того как количество ядер становится больше, затраты на блокировку могут потенциально увеличиваться. По мере ввода большего количества задач для совместного использования одних и тех же данных накладные расходы, связанные с блокировками, могут негативно повлиять на вычисление.
  • Тупик (Deadlock) - это проблема параллелизма, возникающая из-за использования блокировок. Это происходит, когда существует цикл задач, в котором каждая задача блокируется в ожидании продолжения работы. Поскольку все задачи ждут выполнения другой задачи, они блокируются на неопределенный срок. Чем больше ресурсов распределяется между потоками, тем больше блокировок необходимо, чтобы избежать состояния гонки, и тем выше риск блокировок.
  • Отсутствие композиции - проблема дизайна, возникающая из-за введения блокировок в код. Блоктровк не сочитаются. Композиция способствует устранению проблем, разбивая сложную задачу на более мелкие кусочки, которые легче решить, а затем склеивают их вместе. Композиция является фундаментальным принципом в FP.

Up

Простой пример в реальном мире: параллельная быстродействующая сортировка

src

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

Quicksort - это алгоритм "Разделяй и властвуй"; он сначала делит большой массив на два меньших подмассива с меньшими элементами и большими элементами. Quicksort может затем рекурсивно сортировать подмассивы и поддается параллелизации. Он может работать на месте массива, требуя небольших дополнительных объемов памяти для выполнения сортировки. Алгоритм состоит из трех простых шагов, как показано на рисунке:

  • выберать pivot-элемент
  • разделить последовательность на подпоследовательности в соответствии с их порядком относительно вершины
  • отсортировать подпоследовательности.

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

Рекурсивные алгоритмы, особенно те, которые основаны на принципе "Разделяй и властвуй", являются отличным кандидатом для распараллеливания и вычислений, связанных с CPU. Библиотека Microsoft Task Parallel Library (TPL), представленная после выпуска .NET 4.0, упрощает реализацию и использование параллелизма для этого типа алгоритма. Используя TPL, можно разделить каждый шаг алгоритма и выполнить каждую задачу параллельно, рекурсивно. Это простая реализация, но нужно быть осторожным с уровнем глубины, с которым создаются потоки, чтобы не добавлять больше задач, чем необходимо.

Up

Глоссарий

  • Асинхронность (Asynchronicity) - Когда программа выполняет запросы, которые не выполняются немедленно, но которые выполняются позже, и где программа, выдающая запрос, должна делать тем временем значительную работу.
  • Конкурентность (Concurrency) - Когда нескольких вещей происходит одновременно. Обычно, конкурентные программы имеют несколько потоков выполнения, каждый из которых обычно выполняет разный код.
  • Параллелизм (Parallelism) - Состояние программы, когда одновременно выполняется несколько потоков, чтобы ускорить выполнение программы.
  • Процесс (Process) - стандартный процесс операционной системы. Каждый экземпляр .NET CLR работает в своем собственном процессе. Процессы обычно независимы.
  • Поток (Thread) - Самая маленькая последовательность запрограммированных команд, которыми ОС может управлять независимо. Каждый процесс .NET имеет много потоков, работающих в рамках одного процесса и использующих одну и ту же кучу.